JP6232522B2 - 計算機及びグラフデータ生成方法 - Google Patents

Description

本発明は、グラフデータを用いたビックデータ解析における計算機及びグラフデータ生成方法に関する。

Ｗｅｂやセンサ等から得られた大量のデータ（ビックデータ）を使用して、有用な知見（情報）を抽出するビックデータ解析が注目されている。ビックデータ解析では、統計学、パターン認識、及び人工知能等のデータ解析の技法を大量のデータに網羅的に適用することによって、データの中に潜む項目間の相関関係及びパターンを、知識として抽出する。データの中に隠れた潜在的な情報を「採掘（ｍｉｎｉｎｇ）」することから、ビックデータ解析はデータマイニングとも呼ばれる。ビックデータ解析の技法としては、例えば、統計学における相関分析、回帰分析、及び主成分分析、並びに、パターン認識、人工知能における機械学習、及びクラスタリング等がある。

ビックデータ解析において有用な知識を得るためには、膨大なデータの解析する必要がある。しかし、データ量の増加及びデータ解析方法の高度化に伴って、処理時間及びメモリ使用量の増加等がハードウェアリソースに対して過度な負担がかかることが課題となっている。特に、社会インフラ分野では、限られたハードウェアリソースを用いて、限られた時間内に必要精度を保ちながら効率的に結果を出力することが求められる。

例えば、統計的なデータ解析手法として基本的な相関分析及び主成分分析では、ビックデータから指標（特徴量、項目）を生成し、指標間の相関関係を導出する。このとき、指標の数がｍである相関関係はｍ列ｍ行の相関行列として与えられ、相関分析及び主成分分析は、相関行列の演算によって実行される。しかし、行列演算は全ての要素について演算処理を実行するために、全ての要素のデータを蓄積しなければならない。そのため、ビックデータを扱うシステムでは、計算量、及びメモリ使用量の観点から非常に効率が悪くなる。その結果、大量の指標から構成されるビックデータ（相関行列）の蓄積及び演算処理は、ハードウェアリソースに対して大きな負担となる。

ビックデータを圧縮して処理を効率化する方法としては、米国特許出願公開第２００１／００１１９５８号明細書（特許文献１）に記載の技術がある。特許文献１には、データの蓄積と通信コストの低減を目的に、ビックデータを多変量のデータ解析手法を用いて変換し、圧縮・再構成する技術が開示されている。特許文献１に開示されている方法は、サンプル数ｎ、指標数ｍとして、ｎ列ｍ項目のオリジナルデータからｍ列ｍ行の相関行列を得るステップと、相関行列の固有値と固有ベクトルを求めるステップと、固有値と固有ベクトルから因子負荷量の行列を求めるステップと、ｌ列ｐ行のランダム行列を生成するステップと、ランダム行列と因子負荷量の行列の乗算によってｌ列ｍ行の中間データ行列を得るステップと、中間データ行列をスケールすることでｌ列ｍ行の再構成されたデータ行列を得るステップと、を有する。データの再構成を可能とすることによって、通
信及びデータの蓄積のコストを削減することができることが記載されている。

米国特許出願公開第２００１／００１１９５８号明細書

特許文献１に記載の方法は、データの蓄積及び通信のコストを低減するために、オリジナルデータのサンプル数ｎを圧縮することを主な課題としており、分析処理時におけるハードウェアリソースの制約までは十分に考慮されていない。また、特許文献１記載の方法では、相関分析又は主成分分析を行う場合、圧縮されたデータ列を再構築し、元のフォーマットに変換してから相関行列の演算を行い、その後に分析処理を実行する必要がある。そのため、特許文献１の方法では、指標数ｍはサンプル数ｎに対して十分に小さいことが前提とされている。

指標数ｍの増大に伴って、ｍ列ｍ行の相関行列がメモリに格納できないほど大きい場合、相関分析又は主成分分析などのデータ解析を行えなくなるという課題がある。社会インフラシステムの分析などにおいては、説明指標が１００万規模になることも想定されるため、分析処理の必要精度を保った上で、データや処理を簡略化して、指標数の増加に伴う分析処理を効率化する方法が必要になる。

本発明は、上述のような課題を解決するためになされたもので、大量の指標から構成される相関行列の分析処理において、データ量を圧縮することによって処理量を削減し、分析処理の必要精度を保った上で、処理を効率化することを目的とする。

本願において開示される発明の代表的な一例を示せば以下の通りである。すなわち、プロセッサ、前記プロセッサに接続されるメモリ及び記憶装置を備え、複数の指標間の相関値を要素とする相関行列データから、一つの指標に対応する頂点、相関関係のある二つの前記頂点を接続するエッジ、及び前記要素の値であるエッジの重みから構成されるグラフデータを生成する計算機であって、前記記憶装置より前記相関行列データを取得し、取得した前記相関行列データに含まれる指標に対応する頂点を連結する全域木を構成する要素と所定の閾値以上の値の要素とを抽出し、抽出した前記要素に基づき、前記グラフデータを生成するグラフ処理部を備えることを特徴とする。

また、他の一例を示せば以下の通りである。すなわち、プロセッサ、及び前記プロセッサに接続されるメモリを備え、複数の指標間の相関値を要素とする相関行列データを用いた処理を実行する計算機であって、前記計算機は、記憶装置から取得される前記相関行列データから、一つの指標に対応する頂点、相関関係のある二つの前記頂点を接続するエッジ、及び前記要素の値であるエッジの重みから構成されるリスト構造の第１のグラフデータを生成するグラフ処理部を備え、前記グラフ処理部は、前記相関行列データを用いた処理を所定時間内に完了するために、前記第１のグラフデータに含めることが可能な最大エッジ数を算出する制御因子算出部と、前記相関行列データをリスト構造の第２のグラフデータに変換し、前記第２のグラフデータの全ての頂点及び一部のエッジで構成される全域木である第３のグラフデータを生成する全域木生成部と、前記最大エッジ数を用いて、前記第２及び前記第３のグラフデータに基づき、前記第１のグラフデータを生成するグラフデータ生成部とを備えることを特徴とする。

本発明によれば、制約条件に従って、大量の指標から構成される相関行列データから精度破綻の生じない圧縮されたグラフデータに変換することができる。これによって、データ量を削減し、必要精度を保った相関分析又は主成分分析等の高速なグラフ処理が可能となる。

上記した以外の課題、構成及び効果は、以下の実施例の説明により明らかにされる。

本発明の実施例1のグラフ処理装置の構成例を示すブロック図である。 本発明の実施例１のグラフ処理装置が適用されるシステム構成の一例を示すブロック図である。 本発明の実施例１における業務データの一例を示す説明図である。 本発明の実施例１における相関行列データの一例を示す説明図である。 本発明の実施例１のグラフ処理装置が実行する処理の概要を説明するフローチャートである。 本発明の実施例１のエッジ情報量算出処理の一例を説明するフローチャートである。 本発明の実施例１の相関値の頻度分布表の一例を示す説明図である。 本発明の実施例１のエッジ情報量の一例を示す説明図である。 本発明の実施例１の制御因子算出処理の一例を説明するフローチャートである。 本発明の実施例１の推定処理時間関数ｆ（Ｅ）の一例を示す説明図である。 本発明の実施例１の制御因子の決定時に用いられる推定用エッジ情報量の一例を示す説明図である。 本発明の実施例１のグラフデータ生成処理の一例を説明するフローチャートである。 本発明の実施例１のグラフデータ生成処理に用いられる頂点リストの一例を示す説明図である。 本発明の実施例１のグラフデータ生成処理に用いられるエッジリストの一例を示す説明図である。 本発明の実施例１のグラフデータ生成処理における制御因子を用いた相関値の切り捨ての概念を示す説明図である。 本発明の実施例１のグラフデータ生成処理の実行後の頂点リスト及びエッジリストを示す説明図である。 本発明の実施例１のグラフデータ生成処理の実行後の頂点リスト及びエッジリストを示す説明図である。 本発明の実施例１のグラフデータに基づいて表示されるグラフの一例を示す説明図である。 本発明の実施例２のグラフ処理装置の構成例を示すブロック図である。 本発明の実施例２の制御因子算出処理の一例を説明するフローチャートである。 本発明の実施例２の推定メモリ使用量関数ｇ（Ｅ，Ｂ）の一例を示す説明図である。 本発明の実施例２の推定メモリ使用量関数ｇ（Ｅ，Ｂ）の一例を示す説明図である。 図１９は、本発明の実施例２の相関値の表現ビット数の丸めの一例 本発明の実施例３のグラフ処理装置の構成例を示すブロック図である。 本発明の実施例３における相関行列データの一例を示す説明図である。 本発明の実施例３のグラフ処理装置が実行する処理の概要を説明するフローチャートである。 本発明の実施例３の全域木生成処理の一例を説明するフローチャートである。 本発明の実施例３の全域木生成処理の概念を示す説明図である。 本発明の実施例３の全域木生成処理の実行後の頂点リスト及びエッジリストを示す説明図である。 本発明の実施例３の全域木生成処理の実行後の頂点リスト及びエッジリストを示す説明図である。 本発明の実施例３の処理装置の全域木生成処理のエッジ候補リストを示す説明図である。 本発明の実施例３の全域木生成処理の全域木生成ステップの一例を説明するフローチャートである。 本発明の実施例３のグラフデータ生成処理の概念を示す説明図である。 本発明の実施例３のグラフデータ生成処理の実行後の頂点リスト及びエッジリストを示す説明図である。 本発明の実施例３のグラフデータ生成処理の実行後の頂点リスト及びエッジリストを示す説明図である。 本発明の実施例３のグラフデータに基づいて表示されるグラフの一例を示す説明図である。 本発明の実施例３のグラフデータ生成処理の一例を説明する説明図である。

以下、添付図面を参照して本発明の実施例について説明する。添付図面では、機能的に同じ要素は同じ番号で表示されている。なお、添付図面は本発明の原理に則った具体的な実施例を示しているが、これらは本発明の理解のためのものであり、決して本発明を限定的に解釈するために用いられるものではない。

まず、本発明の概要について説明する。

業務データに対する相関分析等の分析処理の実行時には、業務データから指標（特徴量、項目等）間の相関関係を示す相関行列データが生成される。指標の数がｍ個の場合、相関行列データはｍ行ｍ列の行列データとなる。相関行列データは行列の要素を識別する指標の組合せ、及び要素の値から構成されるデータである。

ビックデータ解析では指標の数が大きいため、相関行列データのサイズも大きい。そのため、メモリに相関行列データを格納することができない。そのため、業務データの解析処理の実行時には、相関行列データを取得するためにストレージ装置等に頻繁にアクセスする必要がある。したがって、ストレージ装置へのアクセスに伴う処理遅延が発生する。

また、ｍ行ｍ列の相関行列データは（ｍ×ｍ）個の要素を持ち、解析処理では、全ての要素のデータを処理する必要がある。指標間の相関がないことを示す値「０」の場合であっても、「０」という値を保持する必要がある。そのため、指標の数が増大すると、処理コスト及びデータ量が増大する。

（１）グラフデータへの変換
前述した課題を解決するために、本発明のグラフ処理装置１００（図１参照）は、相関行列データをグラフデータに変換する。ここで、グラフデータは、指標を表す頂点、相関のある二つの頂点を接続するエッジ、及び要素の値を表すエッジの重みから構成されるデータ構造のデータであり、頂点間の接続関係をグラフとして把握することができる。エッジの重みが当該エッジで接続される二つの指標の間の相関関係の強さを表す。

相関関係が存在しない頂点との間にはエッジが存在しないため、グラフデータでは、相関関係がないことを示すデータを保持する必要がない。また、いずれの頂点とも接続されないものはデータとして保持する必要がない。一方、相関行列データでは、二つの指標の間に相関関係がない場合であっても「０」を値とする要素としてデータを保持する必要がある。そのため、グラフデータは、相関行列データよりデータ量が少ない。

したがって、相関行列データをグラフデータに変換することによって、データ量を削減することができる。本発明では、グラフ処理装置１００は、単に、相関行列データをグラフデータに変換するのではなく、制約条件に基づいて、可能な限り精度破綻の生じない圧縮されたグラフデータに変換する点に特徴がある。

具体的には、以下の３つの処理を含むことに特徴がある。

（２）グラフデータに含めるエッジ数の調整
相関行列データをそのままグラフデータに変換しても、十分にデータ量を削減することができない可能性がある。そのため、本発明のグラフ処理装置１００（図１参照）は、解析処理の処理完了時間である目標処理時間に応じて、グラフデータに含まれるエッジ数を調整する。

具体的には、グラフ処理装置１００は、目標処理時間に基づいて、相関値を切り捨てるための閾値を決定する。さらに、グラフ処理装置１００は、各要素の値の大きさ（絶対値）が閾値以下の要素の値を「０」に設定し、その上で、グラフデータに変換する。前述したように、「０」は二つの指標間に相関関係がないことを示し、また、相関関係がない場合にはエッジも存在しない。そのため、グラフデータに含まれるエッジ数を削減することができる。

（３）エッジの重みの表現ビット数の丸め
本発明のグラフ処理装置１００は、メモリ容量に応じて、エッジの重みの表現ビット数を丸める。これによって、グラフデータを、メモリに格納可能なデータサイズに更に圧縮する。

（４）全域木（スパニングツリー）構造を保持したグラフデータの生成
閾値によるエッジ数の削減だけでは、目標処理時間の制約が厳しいと、グラフ処理の精度を維持できくなる可能性がある。すなわち、閾値によって「０」に設定された要素が多い場合、変換されるグラフデータの構造は疎（スパース）なものとなり、グラフが分裂することで連結グラフが維持できなくなる可能性がある。連結グラフは、グラフ上の任意の２ノード間にエッジが存在するグラフのである。また、連結な部分グラフを連結成分と言う。隣接ノードの間でトラーバス処理を行うグラフ処理において、連結成分が複数に分裂すると、連結成分間で情報の遷移が不能となり、結果を正しく求めることができない。そのため、本発明のグラフ処理装置１００は、全ての有用なノードが少なくとも一辺は別のノードへの接続を保持するように、グラフの全域木構造を保持したグラフデータを作成する。全域木（スパニングツリー）は、グラフの全てのノードとエッジの一部からなる木構造であり、グラフデータの連結性を保障する。

具体的には、グラフ処理装置１００は、相関行列データを元に全域木を作成する。さらに、グラフ処理装置１００は、閾値以下の要素の値を除去しつつ、作成した全域木構造の要素データを保持するようにグラフデータを生成する。全域木構造の要素データを保持することで、精度破綻を引き起こす可能性のあるグラフの分裂を防ぐことができる。

以上のような処理を実行することによって、処理に必要なデータ量を削減することができる。すなわち、全てのグラフデータをメモリに格納することができるため、処理の高速化が可能となり、また、データ量の削減によって処理コストを抑制することができる。さらに、グラフ分裂を防ぐように、生成するグラフデータに全域木構造を保持することで、必要精度を保った上で、グラフ処理の効率化が実現できる。

図１は、本発明の実施例1のグラフ処理装置１００の構成例を示すブロック図である。図２は、本発明の実施例１のグラフ処理装置１００が適用されるシステム構成の一例を示すブロック図である。

図２に示すシステムは、グラフ処理装置１００、基地局２００、ユーザ端末２１０、及びセンサ群２２０から構成される。

グラフ処理装置１００、基地局２００及びセンサ群２２０に含まれる複数のセンサ２２１は、ネットワーク２４０を介して互いに接続される。ネットワーク２４０は、例えば、ＷＡＮ、ＬＡＮ等が考えられるが、本発明はネットワーク２４０の種別に限定されない。

ユーザ端末２１０は、基地局２００を介して無線通信を介して、グラフ処理装置１００等と接続される。なお、ユーザ端末２１０と基地局２００との間は有線通信を介して接続されてよいし、ユーザ端末２１０が直接ネットワーク２４０と接続されてもよい。

グラフ処理装置１００は、センサ群２２０に含まれる各センサ２２１から業務データ１３０を取得し、取得された業務データ１３０をストレージ装置１０４に格納する。また、グラフ処理装置１００は、ユーザ端末２１０の指示に従って、グラフ処理を実行する。

ユーザ端末２１０は、例えばパーソナルコンピュータ又はタブレット端末等の装置である。ユーザ端末２１０は、プロセッサ（図示省略）、メモリ（図示省略）、ネットワークインタフェース（図示省略）、及び入出力装置（図示省略）を備える。入出力装置には、ディスプレイ、キーボード、マウス、及びタッチパネル等が含まれる。

ユーザ端末２１０は、グラフ処理装置１００を操作するためのユーザインタフェース２１１を提供する。ユーザインタフェース２１１は、グラフ処理装置１００に目標処理時間を入力し、また、グラフ処理装置１００から出力されたグラフデータ及びグラフ処理の結果等を受け付ける。

グラフ処理装置１００は、ハードウェア構成としてプロセッサ１０１、メモリ１０２、ネットワークインタフェース１０３、及びストレージ装置１０４を備える。

プロセッサ１０１は、メモリ１０２に格納されるプログラムを実行する。プロセッサ１０１がプログラムを実行することによって、グラフ処理装置１００が有する各種機能部を実現できる。以下の説明では、機能部を主体に処理の説明をするときには、当該機能部を実現するプログラムがプロセッサ１０１によって実行されていることを示す。

メモリ１０２は、プロセッサ１０１によって実行されるプログラム及び当該プログラムの実行時に用いられる情報を格納する。メモリ１０２は、ＤＲＡＭ等が考えられる。メモリ１０２に格納されるプログラム及び情報については後述する。ネットワークインタフェース１０３は、ＷＡＮ、ＬＡＮ等のネットワークを介して外部の装置と接続するためのインタフェースである。

ストレージ装置１０４は、各種情報を格納する。ストレージ装置１０４は、ＨＤＤ又はＳＳＤ等が考えられる。本実施例では、ストレージ装置１０４に業務データ１３０が格納される。なお、業務データ１３０における各種データの相関関係を示す相関行列データが格納されてもよい。

ここで、図３及び図４を用いて業務データ１３０及び相関行列データ４００の一例について説明する。図３は、本発明の実施例１における業務データ１３０の一例を示す説明図である。図４は、本発明の実施例１における相関行列データ４００の一例を示す説明図である。

図３には、店舗における業務データ１３０を示す。業務データ１３０には、顧客毎の購入金額、購入点数、滞在時間、立ち止り時間などの情報が格納される。「購入金額」、「購入点数」、「滞在時間」、及び「立ち止り時間」を指標と呼ぶ。

相関行列データ４００は、指標間の相関関係を要素とする行列データである。例えば、本実施例の行列データには、指標１「購入金額」と指標２「購入点数」との間の相関関係を示す情報が要素として含まれる。ここで、指標１と指標２との間の相関関係は、相関値として与えられる。例えば、下式（１）を用いて相関値が算出される。

ここで、Ｓ１は指標１の標準偏差、Ｓ２は指標２の標準偏差、Ｓ１２は指標１と指標２との間の共分散を表す。相関値は、「−１」以上「１」以下であり、相関値が「１」に近いほど「正の相関」が強いことを表し、相関値が「−１」に近いほど「負の相関」が強いことを表す。また、「０」に近いほど指標間に相関がないことを表す。

すなわち、相関行列データ４００は、全ての指標の組合せに対する相関値を要素とする行列形式のデータ構造であり、指標間の関係性を示すデータである。以下の説明では、業務データ１３０から算出された相関行列データ４００が、予め、ストレージ装置１０４に格納されるものとする。

図１の説明に戻る。次に、メモリ１０２に格納されるプログラム及び情報について説明する。

メモリ１０２には、グラフ処理部１１０を実現するプログラムを格納する。グラフ処理部１１０は、相関行列データ４００をグラフデータに変換し、すなわち、相関行列データ４００からグラフデータを生成する。また、グラフ処理部１１０は、グラフデータを用いて任意のグラフ処理を実行する。グラフ処理部１１０は、複数のプログラムモジュールから構成される。具体的には、グラフ処理部１１０は、エッジ情報量算出部１１１、制御因子算出部１１２、グラフデータ生成部１１３、グラフ処理部１１４、グラフデータ格納部１１５を含む。

エッジ情報量算出部１１１は、ストレージ装置１０４から相関行列データ４００の要素を読み出し、相関値とエッジ数との間の関係を示すエッジ情報量を算出する。また、エッジ情報量算出部１１１は、算出されたエッジ情報量を制御因子算出部１１２に出力する。ここで、エッジ情報量は、相関行列データ４００をグラフデータに変換する場合に含めることが可能なエッジの数を推定するための情報である。エッジ情報量算出部１１１が実行する処理の詳細は、図６を用いて後述する。

制御因子算出部１１２は、相関行列データ４００をグラフデータに変換する場合に、データの圧縮に用いられる制御因子を算出する。本実施例では、制御因子算出部１１２は、エッジ情報量及び目標処理時間に基づいてグラフデータに含めるエッジ数を調整するための閾値を制御因子として算出する。また、制御因子算出部１１２は、算出された制御因子をグラフデータ生成部１１３に出力する。制御因子算出部１１２が実行する処理の詳細は、図８を用いて後述する。

グラフデータ生成部１１３は、算出された制御因子を用いて相関行列データ４００からグラフデータを生成する。グラフデータ生成部１１３は、グラフデータ格納部１１５に生成されたグラフデータを格納し、また、ユーザ端末２１０に生成されたグラフデータを送信する。グラフデータ生成部１１３が実行する処理の詳細は、図１１を用いて後述する。

グラフ処理部１１４は、グラフデータを用いて任意のグラフ処理を実行する。グラフ処理としては、例えば、行列演算の固有値計算に利用可能なＰａｇｅＲａｎｋ処理、中心性計算処理等が考えられる。本発明は、グラフ処理の処理内容に限定されず、汎用的に用いられる様々なグラフアルゴリズムを適用することができる。グラフ処理部１１４は、ユーザ端末２１０にグラフ処理の結果を送信する。

次に、本実施例のグラフ処理装置１００が実行する処理について説明する。図５は、本発明の実施例１のグラフ処理装置１００が実行する処理の概要を説明するフローチャートである。

グラフ処理装置１００は、ユーザ端末２１０から処理の開始時を受信した場合、又は周期的に、以下で説明する処理を実行する。

グラフ処理装置１００は、ストレージ装置１０４に格納される業務データ１３０から相関行列データ４００を生成する（ステップＳ５０１）。具体的には、グラフ処理部１１０が相関行列データ４００を生成する。なお、ストレージ装置１０４に相関行列データ４００が格納されている場合には、ステップＳ５０１の処理は省略することができる。

グラフ処理装置１００は、エッジ情報量算出処理を実行する（ステップＳ５０２）。具体的には、エッジ情報量算出部１１１が、相関行列データ４００を解析し、解析結果に基づいてエッジ情報量を算出する。エッジ情報量算出部１１１が実行するエッジ情報量算出処理の詳細は、図６を用いて後述する。

グラフ処理装置１００は、ユーザ端末２１０から目標処理時間を取得する（ステップＳ５０３）。具体的には、グラフ処理部１１０が、ユーザ端末２１０に対して目標処理時間の入力を要求する。このとき、ユーザインタフェース２１１は、当該要求を受け付けると、ディスプレイ等に目標処理時間を入力するための操作画面を表示し、当該操作画面を用いて入力された目標処理時間をグラフ処理装置１００に送信する。グラフ処理装置１００は、ユーザ端末２１０から受信した目標処理時間を制御因子算出部１１２に入力する。

グラフ処理装置１００は、エッジ情報量及び目標処理時間を用いて制御因子算出処理を実行する（ステップＳ５０４）。具体的には、制御因子算出部１１２が、エッジ情報量及び目標処理時間を用いて、圧縮されたグラフデータの生成に用いる制御因子を算出する。制御因子算出部１１２が実行する制御因子算出処理の詳細は、図８を用いて後述する。

グラフ処理装置１００は、制御因子を用いてグラフデータ生成処理を実行する（ステップＳ５０５）。具体的には、グラフデータ生成部１１３が、算出された制御因子を用いて、相関行列データ４００からグラフデータを生成する。グラフデータ生成部１１３が実行するグラフデータ生成処理の詳細は、図１１を用いて後述する。

グラフ処理装置１００は、生成されたグラフデータを用いてグラフ処理を実行する（ステップＳ５０６）。具体的には、グラフ処理部１１４が、生成されたグラフデータを用いて所定のグラフ処理を実行し、グラフ処理の結果をユーザ端末２１０に送信する。

図６は、本発明の実施例１のエッジ情報量算出処理の一例を説明するフローチャートである。図７Ａは、本発明の実施例１の相関値の頻度分布表７００の一例を示す説明図である。図７Ｂは、本発明の実施例１のエッジ情報量の一例を示す説明図である。

エッジ情報量算出部１１１は、相関行列データ４００における相関値の頻度分布表（ヒストグラム）７００を生成する（ステップＳ６０１）。

ここで、相関値の頻度分布表７００は、相関値を所定の値の範囲毎にカウントした度数分布を表す柱状グラフであり、図７Ａに示すようなグラフとなる。図７Ａでは、値の範囲は「０．０１」である。なお、相関値の頻度分布表７００における値の範囲は予め設定されているものとする。ただし、外部からの入力に基づいて、値の範囲を変更することができる。

エッジ情報量算出部１１１は、相関行列データ４００の要素のループ処理を開始する（ステップＳ６０２）。まず、エッジ情報量算出部１１１は、相関行列データ４００から要素を一つ選択し、選択された要素の値（相関値）を読み出す。

エッジ情報量算出部１１１は、読み出された要素の値の絶対値、すなわち、相関値の絶対値を算出する（ステップＳ６０３）。エッジ情報量算出部１１１は、算出された相関値の絶対値に基づいて、相関値の頻度分布表７００を更新する（ステップＳ６０４）。具体的には、エッジ情報量算出部１１１は、相関値の絶対値が含まれる値の範囲の度数を１加算する。なお、エッジ情報量算出部１１１は、相関値の頻度分布表７００の更新後、読み出された要素の値を削除する。

エッジ情報量算出部１１１は、相関行列データ４００の全ての要素について処理が完了したか否かを判定する（ステップＳ６０５）。相関行列データ４００の全ての要素について処理が完了していないと判定された場合、エッジ情報量算出部１１１は、ステップＳ６０２に戻り、同様の処理を実行する。一方、相関行列データ４００の全ての要素について処理が完了したと判定された場合、エッジ情報量算出部１１１は、ステップＳ６０６に進む。

相関行列データ４００の要素のループ処理が完了すると、相関値の頻度分布表７００は図７Ａに示すような状態になる。

エッジ情報量算出部１１１は、相関値の頻度分布表７００に基づいてエッジ情報量を算出し（ステップＳ６０６）、制御因子算出部１１２に算出されたエッジ情報量を出力する（ステップＳ６０７）。その後、エッジ情報量算出部１１１は処理を終了する。具体的には、以下のような処理が実行される。

エッジ情報量算出部１１１は、相関値の絶対値「ｋ」までの度数の合計値、すなわち、度数の累積頻度を算出する。横軸を相関値の絶対値、横軸を度数の累積頻度として、算出された度数の累積頻度をプロットする。エッジ情報量算出部１１１は、プロット結果から相関値の絶対値と累積頻度との間の関係を示す関数Ｅ（ｋ）をエッジ情報量として算出する。本実施例では、エッジ情報量Ｅ（ｋ）は、図７Ｂに示すようなグラフ７０１として与えられる。

累積頻度は、相関値の頻度分布表７００における相関値の絶対値が「ｋ」までの度数の合計値を表す。例えば、Ｅ（０．３）は相関値の絶対値が「０」から「０．３」までの度数の合計値である。したがって、Ｅ（１）は相関行列データ４００の全要素の数と一致する。

図８は、本発明の実施例１の制御因子算出処理の一例を説明するフローチャートである。図９は、本発明の実施例１の推定処理時間関数ｆ（Ｅ）の一例を示す説明図である。図１０は、本発明の実施例１の制御因子の決定時に用いられる推定用エッジ情報量の一例を示す説明図である。

制御因子算出部１１２は、エッジ情報量が入力されると処理を開始する。制御因子算出部１１２は、エッジ情報量Ｅ（ｋ）を変数とする推定処理時間関数ｆ（Ｅ）を求める（ステップＳ８０１）。

制御因子算出部１１２は、グラフ解析処理のアルゴリズムに基づいて推定処理時間関数ｆ（Ｅ）を算出することができる。例えば、グラフ分析処理において、主成分分析に用いる固有値問題を解く場合、アルゴリズムの収束計算の繰り返し回数をａ、単位エッジ当たりの処理時間をｂ、変数Ｅとして場合、下式（２）で与えられる。

図９には、式（２）によって求められた推定処理時間関数ｆ（Ｅ）を示す。なお、エッジ情報量Ｅ（ｋ）は推定処理時間関数ｆ（Ｅ）の定義域として与えられる。

次に、制御因子算出部１１２は、ユーザ端末２１０から目標処理時間を取得する（ステップＳ８０２）。例えば、制御因子算出部１１２は、ユーザ端末２１０に対して、目標処理時間の入力を要求する。ユーザ端末２１０は、ユーザインタフェース２１１を介して当該要求を受け付けると、ディスプレイに目標処理時間を入力するための操作画面等を表示する。以下の説明では取得された目標処理時間がＴであるものとする。

制御因子算出部１１２は、目標処理時間及び推定処理時間関数ｆ（Ｅ）を用いて、目標処理時間内にグラフ処理が完了可能な最大エッジ数Ｅ_ＭＡＸを算出する（ステップＳ８０３）。

本実施例では、制御因子算出部１１２は式（２）から最大エッジ数Ｅを算出できる。具体的には下式（３）のように最大エッジ数Ｅ_ＭＡＸが算出される。図９の点線は、式（３）を用いて算出される最大エッジ数Ｅ_ＭＡＸを示す。

制御因子算出部１１２は、エッジ情報量Ｅ（ｋ）及び最大エッジ数Ｅ_ＭＡＸを用いて相関値の閾値を算出する（ステップＳ８０４）。具体的には、以下のような処理が実行される。

制御因子算出部１１２は、まず、エッジ情報量Ｅ（ｋ）を用いて推定用エッジ情報量Ｅ’（ｋ）を求める。本実施例では、下式（４）に示すように推定用エッジ情報量Ｅ’（ｋ）が求められる。推定用エッジ情報量Ｅ’（ｋ）は、図１０に示すようなグラフ１０００として与えられる。

制御因子算出部１１２は、推定用エッジ情報量Ｅ’（ｋ）及び最大エッジ数Ｅ_ＭＡＸを用いて相関値の閾値を算出する。具体的には、制御因子算出部１１２は、式（４）の左辺をＥ_ＭＡＸとし、下式（５）のように変更することによって相関値の絶対値ｋを算出する。算出された相関値の絶対値ｋが相関値の閾値となる。図１０の点線は、式（５）を用いて算出された相関値の閾値を示す。相関値の閾値は、後述するように、グラフデータ生成処理において相関値の切り捨ての閾値（制御因子）として用いられる。

制御因子算出部１１２は、グラフデータ生成部１１３に、算出された相関値の閾値を制御因子として出力し（ステップＳ８０５）、処理を終了する。

図１１は、本発明の実施例１のグラフデータ生成処理の一例を説明するフローチャートである。図１２Ａは、本発明の実施例１のグラフデータ生成処理に用いられる頂点リスト１２００の一例を示す説明図である。図１２Ｂは、本発明の実施例１のグラフデータ生成処理に用いられるエッジリスト１２１０の一例を示す説明図である。図１３は、本発明の実施例１のグラフデータ生成処理における制御因子を用いた相関値の切り捨ての概念を示す説明図である。図１４Ａ及び図１４Ｂは、本発明の実施例１のグラフデータ生成処理の実行後の頂点リスト１２００及びエッジリスト１２１０を示す説明図である。図１５は、本発明の実施例１のグラフデータに基づいて表示されるグラフの一例を示す説明図である。

まず、頂点リスト１２００及びエッジリスト１２１０について説明する。

頂点リスト１２００は、グラフデータにおける頂点（指標）、及び頂点を接続するエッジの情報を管理するための情報である。図１２Ａに示す頂点リスト１２００は、頂点ＩＤ１２０１、指標ＩＤ１２０２、及び接続エッジ情報１２０３を含む。

頂点ＩＤ１２０１は、頂点を一意に識別するための識別情報を格納する。一つの頂点に対して一つの頂点ＩＤが付与される。指標ＩＤ１２０２は、頂点に対応する指標の識別情報である。グラフデータでは、一つの指標が一つの頂点として管理される。接続エッジ情報１２０３は、頂点ＩＤ１２０１に対応する頂点に接続されるエッジの情報である。

エッジリスト１２１０は、グラフデータにおけるエッジ（辺）を管理するための情報である。図１２Ｂに示すエッジリスト１２１０はエッジＩＤ１２１１、接続頂点Ａ１２１２、接続頂点Ｂ１２１３、及び重み１２１４を含む。

エッジＩＤ１２１１は、エッジを一意に識別するための識別情報を格納する。一つのエッジに対して一つのエッジＩＤが付与される。接続頂点Ａ１２１２及び接続頂点Ｂ１２１３は、エッジによって接続される二つの頂点の識別情報を格納する。重み１２１４は、エッジの重み、すなわち、相関値を格納する。

グラフデータ生成部１１３は、制御因子が入力されると処理を開始する。グラフデータ生成部１１３は、まず、頂点リスト１２００及びエッジリスト１２１０を初期化する（ステップＳ１１０１）。

具体的には、グラフデータ生成部１１３は、相関行列データ４００の全ての指標の数だけ頂点リスト１２００にエントリを生成し、生成されたエントリの指標ＩＤ１２０２に指標の識別情報を設定する。グラフデータ生成部１１３は、各指標に頂点ＩＤを付与し、各エントリの頂点ＩＤ１２０１に付与された頂点ＩＤを設定する。この時点では、接続エッジ情報１２０３は空の状態である。また、グラフデータ生成部１１３は、空のエッジリスト１２１０を生成する。

グラフデータ生成部１１３は、相関行列データ４００の要素のループ処理を開始する（ステップＳ１１０２）。まず、グラフデータ生成部１１３は、相関行列データ４００から要素を一つ読み出す。なお、グラフデータ生成部１１３が要素を一つずつ読み出すと、頻繁にＩ／Ｏが発生するため、例えば、相関行列データ４００の行単位に要素を読み出し、読み出された要素をメモリ１０２に一時的に保持してもよい。

グラフデータ生成部１１３は、読み出された要素の相関値の絶対値が相関値の閾値（制御因子）より小さいか否かを判定する（ステップＳ１１０３）。読み出された要素の相関値の絶対値が相関値の閾値（制御因子）より小さいと判定された場合、グラフデータ生成部１１３は、ステップＳ１１０５に進む。

読み出された要素の相関値の絶対値が相関値の閾値（制御因子）以上であると判定された場合、グラフデータ生成部１１３は、頂点リスト１２００及びエッジリスト１２１０を更新する（ステップＳ１１０４）。具体的には、以下のような処理が実行される。

グラフデータ生成部１１３は、エッジリスト１２１０にエントリを追加し、追加されたエントリのエッジＩＤ１２１１にエッジの識別情報を設定する。また、グラフデータ生成部１１３は、追加されたエントリの接続頂点Ａ１２１２及び接続頂点Ｂ１２１３に、読み出された要素に対応する二つの指標を設定する。さらに、グラフデータ生成部１１３は、追加されたエントリの重み１２１４に読み出された要素の相関値を設定する。

グラフデータ生成部１１３は、頂点リスト１２００を参照し、指標ＩＤ１２０２が接続頂点Ａ１２１２に設定された指標の識別情報と一致するエントリを検索する。グラフデータ生成部１１３は、検索されたエントリの接続エッジ情報１２０３に、エッジＩＤ１２１１に設定されたエッジの識別情報を設定する。グラフデータ生成部１１３は、同様に、指標ＩＤ１２０２が接続頂点Ｂ１２１３に設定された指標の識別情報と一致するエントリを検索し、当該エントリの接続エッジ情報１２０３にエッジの識別情報を設定する。

なお、接続エッジ情報１２０３に、追加予定のエッジの識別情報と同一のエッジの識別情報が格納されている場合、グラフデータ生成部１１３は、追加予定のエッジの識別情報を設定しない。これは追加する必要がないためである。

以上がステップＳ１１０４の処理の説明である。

グラフデータ生成部１１３は、相関行列データ４００の全ての要素について処理が完了したか否かを判定する（ステップＳ１１０５）。相関行列データ４００の全ての要素について処理が完了していないと判定された場合、グラフデータ生成部１１３は、ステップＳ１１０２に戻り、同様の処理を実行する。一方、相関行列データ４００の全ての要素について処理が完了したと判定された場合、グラフデータ生成部１１３は、ステップＳ１１０６に進む。

相関行列データ４００の要素のループ処理は、図１３に示すように、相関値の絶対値が相関値の閾値（制御因子）より小さい要素の値を「０」に設定して、その後グラフデータを生成する処理に対応する。

グラフデータ生成部１１３は、頂点リスト１２００を参照し、いずれのエッジにも接続されていない頂点のエントリを当該頂点リスト１２００から削除する（ステップＳ１１０６）。具体的には、グラフデータ生成部１１３は、接続エッジ情報１２０３にエッジの識別情報が一つも格納されていないエントリを検索し、当該エントリを頂点リスト１２００から削除する。

以上の処理が終了すると、頂点リスト１２００及びエッジリスト１２１０は、図１２４Ａ及び図１４Ｂに示すような状態になる。

グラフデータ生成部１１３は、頂点リスト１２００及びエッジリスト１２１０をグラフデータとして出力し（ステップＳ１１０７）、処理を終了する。本実施例では、グラフデータ生成部１１３は、頂点リスト１２００及びエッジリスト１２１０をグラフデータ格納部１１５に出力し、また、ユーザ端末２１０に送信する。ユーザ端末２１０は、受信したグラフデータに基づいて図１５に示すようなグラフを表示することができる。

本実施例では、グラフデータは、頂点リスト１２００及びエッジリスト１２１０から構成されるものとするが、本発明はリスト表現に限定されず、そのほかのグラフ表現方法を用いてもよい。

ここで、図４、図１４Ａ、図１４Ｂ、及び図１５を用いて相関行列データ４００とグラフデータとのデータ量について説明する。

図４に示すように、５行５列の相関行列データ４００では、２５個の指標の組合せのそれぞれについて相関値を保持する必要がある。一方、グラフデータでは、５個の頂点の情報と、エッジの重みを含む１０個のエッジの情報とを保持すればよい。したがって、グラフ処理装置１００は、相関行列データ４００をグラフデータに変換することによって、データ量を圧縮することができる。

実施例１によれば、グラフ処理装置１００は、単に相関行列データ４００をグラフデータに変換するだけではなく、目標処理時間内に処理が完了できるように制御因子を用いてグラフデータに含まれるエッジの数を調整し、その後、グラフデータを生成する。これによって、生成されたグラフデータは更に圧縮されたデータとなるため、メモリ１０２にデータを配置することができ、当該メモリ１０２上のグラフデータを用いて高速なグラフ解析処理が可能となる。すなわち、相関行列データをグラフデータとして圧縮し、大量の指標の相関分析又は主成分分析等のビックデータ解析において、データ量を削減し、かつ、高速な処理を実現できる。
（変形例）
実施例１では、相関値の絶対値が相関値の閾値より小さい要素の値を「０」とすることによってエッジとして保持するデータ量を削減したが、本発明はこれに限定されない。例えば、グラフデータ生成部１１３は、相関値の絶対値が相関値の閾値より大きい要素のみを抽出し、抽出された要素からグラフデータを生成してもよい。

次に実施例２について説明する。実施例２では、目標処理時間だけではなく、ユーザによって指定されたメモリ制限量をも考慮して、さらに、圧縮されたグラフデータを生成する。具体的には、制御因子算出部１１２が、グラフデータに含めるエッジ数を調整するため閾値、及びエッジの重みの表現ビット数を制御因子として算出する。これによって、グラフ処理装置１００は、エッジ数の削減し、さらに、エッジの重みの表現ビット数を丸めることによって、さらに、データ量を圧縮する。以下実施例１との差異を中心に実施例２について説明する。なお、実施例１と同一の構成には同一の符号を付し、詳細な説明は省略する。

図１６は、本発明の実施例２のグラフ処理装置１００の構成例を示すブロック図である。なお、グラフ処理装置１００が適用されるシステム構成例は実施例１と同一であるため説明を省略する。

図１６に示すように、ユーザ端末２１０は、目標処理時間に加え、メモリ制限量を入力する点が実施例１と異なる。制御因子算出部１１２は、目標処理時間及びメモリ制限量に基づいて、相関値の閾値及びエッジの重みに対する丸めビット数を算出する。その他の構成は実施例１と同一である。

相関行列データ４００のデータ形式は、実施例と同一であるため説明を省略する。グラフ処理装置１００が実行する処理の概要も実施例１と同一であるため説明を省略する。また、エッジ情報量算出処理も実施例１と同一であるため説明を省略する。実施例２では、制御因子算出処理及びグラフデータ生成処理の一部の内容が異なる。

図１７は、本発明の実施例２の制御因子算出処理の一例を説明するフローチャートである。図１８Ａ及び図１８Ｂは、本発明の実施例２の推定メモリ使用量関数ｇ（Ｅ，Ｂ）の一例を示す説明図である。図１９は、本発明の実施例２の相関値の表現ビット数の丸めの一例を示す説明図である。

実施例２の制御因子算出処理では、制御因子算出部１１２は、推定処理時間関数ｆ（Ｅ）を求めた後、相関値の表現ビット数毎に、エッジ情報量に対する推定メモリ使用量関数ｇ（Ｅ，Ｂ）を求める（ステップＳ１７０１）。ここで、Ｅはエッジ数、Ｂは表現ビット数を表す。

推定メモリ使用量関数ｇ（Ｅ，Ｂ）はエッジの重みを何ビットで表現するかによって複数存在する。例えば、１ビットで重みを表現した場合の一つのエッジ当たりのメモリ使用量をｘ、エッジ数をＥ、エッジのビット数ｙとして場合、推定メモリ使用量関数ｇ（Ｅ，Ｂ）は、下式（６）ように求められる。

図１８Ａ及び図１８Ｂには、式（６）によって求められた推定メモリ使用量関数ｇ（Ｅ，Ｂ）を示す。なお、エッジ情報量Ｅ（ｋ）は推定メモリ使用量関数ｇ（Ｅ，Ｂ）の定義域として与えられる。

ステップＳ１７０１の後、制御因子算出部１１２は、ユーザ端末２１０から目標処理時間及びメモリ制限量を取得する（ステップＳ１７０２）。メモリ制限量の取得方法は、目標処理時間と同様の方法を用いればよい。以下の説明では取得された目標処理時間がＴ、メモリ制限量がＧであるものとする。

制御因子算出部１１２は、最大エッジ数Ｅ_ＭＡＸを算出した後（ステップＳ８０３）、最大エッジ数、メモリ制限量、及び推定メモリ使用量関数ｇ（Ｅ，Ｂ）に基づいて、エッジの重みの表現ビット数を決定する（ステップＳ１７０３）。具体的には、以下のような処理が実行される。

制御因子算出部１１２は、各推定メモリ使用量関数ｇ（Ｅ，Ｂ）に最大エッジ数Ｅ_ＭＡＸを代入し、推定メモリ使用量を算出する。制御因子算出部１１２は、算出された推定メモリ使用量が下式（７）を満たすものを抽出する。

制御因子算出部１１２は、式（７）を満たす推定メモリ使用量の中から最も大きいビット数を特定し、特定されたビット数をエッジの重みの表現ビット数に決定する。

例えば、図１８Ａに示す例ではエッジの重みの表現ビット数は３ビットと決定され、図１８Ｂに示す例ではエッジの重みの表現ビット数は２ビットと決定される。

制御因子算出部１１２は、相関値の閾値を算出した後（ステップＳ８０４）、グラフデータ生成部１１３に、当該相関値の閾値及び表現ビット数を制御因子として出力し（ステップＳ１７０４）、処理を終了する。

実施例２のグラフ生成処理の流れは、実施例１のグラフ生成処理（図１１参照）と同一である。ただし、ステップＳ１１０４の処理が一部異なる。

具体的には、グラフデータ生成部１１３は、エッジリスト１２１０に追加されたエントリの重み１２１４に相関値を設定する場合、制御因子として入力された表現ビット数に基づいて相関値を丸めて、丸められた相関値を重み１２１４に設定する。

例えば、丸める前の相関値の表現ビット数が４ビットであり、これを３ビットに丸める場合、最上位ビットは符号ビットとする。例えば、「０」の場合「正」の相関値に対応し、「１」の場合「負」の相関値に対応するようにすればよい。また、相関値の絶対値の大きさに応じて図１９に示すような符号化を与えればよい。なお、符号は図１９に示す以外の符号化であってもよい。

その他の処理は実施例１と同一である。

実施例２によれば、メモリ制限量に従って、エッジの重みの表現ビット数を丸めることによって、グラフデータを更に圧縮することができる。すなわち、システムにおいて使用可能なメモリ容量の制約のもと、目標処理時間内に処理可能なデータ量のグラフデータを生成することができる。これによって、相関行列データ４００から生成されたグラフデータを全てメモリ１０２上に配置し、メモリ１０２上に配置されたデータを用いて高速なグラフ処理が可能となる。

次に実施例３について説明する。実施例３では、目標処理時間に基づく閾値(制御因子)によるエッジの削減だけではなく、グラフの分裂による精度破綻を防ぐために、全てのノードがエッジで閉路なく接続された全域木構造の要素データを保持したグラフデータを生成する。具体的には、予め相関行列データを元に全域木を作成し、さらにその上で、作成した全域木構造の要素データを保持するように、閾値以下の要素の値を除去する。すなわち、木構造に含まれる要素は例え閾値以下であっても除去せずに、この要素を用いてグラフデータを生成する。これによって、グラス処理装置１００は、精度破綻を引き起こす可能性のあるグラフの分裂を防ぐことができる。以下実施例１との差異を中心に実施例３について説明する。なお、実施例１と同一の構成には同一の符号を付し、詳細な説明は省略する。

図２０は、本発明の実施例３のグラフ処理装置１００の構成例を示すブロック図である。なお、グラフ処理装置１００が適用されるシステム構成例は実施例１と同一であるため説明を省略する。

図２０に示すように、グラフ処理部１１０は、エッジ情報量算出部１１１、制御因子算出部１１２、グラフデータ生成部１１３、グラフ処理部１１４に加え、全域木生成部１１６を含む点が実施例１と異なる。全域木生成部１１６は、相関行列データ４００を入力として全域木データを生成する。全域木生成部１１６が実行する処理の詳細は、図２３を用いて後述する。

相関行列データ４００のデータ形式は、実施例と同一であるため説明を省略する。また、図２１は、実施例３を説明するための相関行列データ４００の一例である。

本実施例のグラフ処理装置１００が実行する処理について説明する。図２２は、グラフ処理装置１００が実行する処理の概要を説明するフローチャートである。実施例３の処理では、相関行列データの生成（ステップＳ５０１）とグラフデータ生成処理（ステップＳ２２０２）の間に、全域木生成処理（ステップＳ２２０１）を実行する。図２２では、グラフデータ生成処理（ステップＳ２２０２）の直前に、全域木生成処理（ステップ２２０１）を挿入したが、相関行列データを生成（ステップＳ５０１）とグラフデータ生成処理（ステップＳ２２０２）の間であれば、いずれの場所に挿入してもよい。

全域木生成処理（ステップ２２０１）は、具体的には、全域木生成処理部１１６が、相関行列データ４００を入力として全域木データを生成する。実施例３の全域木生成部１１６が実行する処理の詳細は、図２３を用いて後述する。

エッジ情報量算出処理は実施例１と同一であるため説明を省略する。制御因子算出処理も実施例１および実施例２と同様であるため説明を省略する。実施例３では、グラフデータ生成処理の一部の内容が異なる。実施例３のグラフデータ生成処理の詳細は、図３１を用いて後述する。

図２３は、本発明の実施例３の全域木生成処理の一例を説明するフローチャートである。図２４は、本発明の実施例３の全域木生成処理の概念を示す説明図である。相関行列データのなかから、他の全ての指標との相関が低い指標（ノイズ）を除去し、ノイズを除去した残りの指標をノードとして構成する全域木を生成するまでの一連の処理の流れを概念的に示している。

図２５Ａ及び図２５Ｂは、本発明の実施例３の全域木生成処理の実行後の頂点リスト１２００及びエッジリスト１２１０の一例を示す説明図である。図２６は、本発明の実施例３の全域木作成処理に用いられるエッジ候補リスト２６０１の一例を示す説明図である。

頂点リスト１２００及びエッジリスト１２１０は、実施例１と同様であるため説明を省略する。エッジ候補リスト２６０１は、エッジリストに追加するためのエッジの候補を管理するための情報であり、エッジリスト１２１０と同様に、エッジＩＤ１２１１、接続頂点Ａ１２１２、接続頂点Ｂ１２１３、及び重み１２１４を含む。

全域木生成部１１６は、頂点リスト１２００及びエッジリスト１２１０及びエッジ候補リスト２６０１を初期化する（ステップＳ２３０１）。具体的には、全域木生成部１１６は、相関行列データ４００の全ての指標の数だけ頂点リスト１２００にエントリを生成し、生成されたエントリの指標ＩＤ１２０２に指標の識別情報を設定する。全域木生成部１１６は、各指標に頂点ＩＤを付与し、各エントリの頂点ＩＤ１２０１に付与された頂点ＩＤを設定する。この時点では、接続エッジ情報１２０３は空の状態である。また、全域木生成部１１６は、空のエッジリスト１２１０及びエッジ候補リスト２６０１を生成する。

全域木生成部１１６は、有用頂点の抽出処理（ステップＳ２３０１〜Ｓ２３０７）を開始する。有用頂点の抽出処理（ステップＳ２３０１〜Ｓ２３０７）は、相関行列データの中から、該指標以外の全ての指標に対して相関の低い不要な指標を除外する。具体的には、相関行列データ４００の行（指標）毎に、その行の全て要素が相関値の閾値以上か否かの判定を行う（ステップＳ２３０４）。ここでの相関値の閾値は、図８のＳ８０４で算出された閾値（制御因子）とは異なる値である。制御因子よりも更に小さい値を事前に設定しておくことで、不要と判断し得る十分に小さな値を除去する。図２１の例では「０.０１」である。

該指標以外で一つでも読み出された要素の相関値の絶対値が相関値の閾値以上の場合であると判定された場合、ステップＳ２３０５、ステップＳ２３０６を飛ばし、ステップＳ２３０７に進む。

その行の全ての要素が閾値以下と判定された場合、全域木生成部１１６は、不要な指標を除外するように、頂点リスト１２００を更新する（ステップＳ２３０６）。具体的には、全域木生成部１１６は、頂点リスト１２００から該指標ＩＤに対応する頂点ＩＤのエントリを削除する。図２１の例では、閾値が「０．０１」に設定されているので、「指標４」のエントリが削除される。

全域木生成部１１６は、相関行列データ４００の行の要素について処理が完了したか否かを判定する（ステップＳ２３０７）。相関行列データ４００の全ての要素について処理が完了していないと判定された場合、全域木生成部１１６は、ステップＳ２３０２に戻り、同様の処理を実行する。一方、相関行列データ４００の全ての要素について処理が完了したと判定された場合、全域木生成部１１６は、ステップＳ２３０８に進む。

以上が有用頂点の抽出処理（ステップＳ２３０１〜Ｓ２３０７）である。なお、本処理を省略することも可能である。

次に、全域木生成部１１６は、エッジ候補リストの作成処理（ステップＳ２３０８〜Ｓ２３１１）を実行する。エッジ候補リスト２６０１は、エッジリスト１２１０に追加するためのエッジの候補を管理するための情報であり、中間データとして機能する。

全域木生成部１１６は、相関行列データ４００の要素のループ処理を開始する（ステップＳ２３０８）。まず、グラフデータ生成部１１３は、相関行列データ４００から要素を一つ読み出す。全域木生成部１１６は、接続頂点が頂点リスト１２００に含まれるか否かの判定を行う（ステップＳ２３０９）。

頂点リスト１２００に接続頂点が含まれると判定された場合、全域木生成部１１６は、エッジ候補リスト２６０１を更新する（ステップ２３１０）。具体的には、全域木生成部１１６は、エッジ候補リストにエントリを追加し、追加されたエントリのエッジＩＤ１２１１にエッジの識別情報を設定する。また、全域木生成部１１６は、追加されたエントリの接続頂点Ａ１２１２及び接続頂点Ｂ１２１３に、読み出された要素に対応する二つの指標を設定する。さらに、全域木生成部１１６は、追加されたエントリの重み１２１４に読み出された要素の相関値を設定する。

頂点リスト１２００に接続頂点が含まれないと判定された場合、全域木生成部１１６は、ステップＳ２３１１に進む。全域木生成部１１６は、相関行列データ４００の全ての要素について処理が完了したか否かを判定する（ステップＳ２３１１）。相関行列データ４００の全ての要素について処理が完了していないと判定された場合、全域木生成部１１６は、ステップＳ２３０８に戻り、同様の処理を実行する。一方、相関行列データ４００の全ての要素について処理が完了したと判定された場合、全域木生成部１１６は、ステップＳ２３１２に進む。

以上がエッジ候補リストの作成処理（ステップＳ２３０８〜Ｓ２３１１）である。以上の処理が終了するとエッジ候補リストは図２６に示すような状態となる。

全域木生成部１１６は、全域木生成ステップを実行する（Ｓ２３１２）。具体的には、全域木生成部１１６は、頂点リスト１２００とエッジ候補リスト２６０１を元に、全域木生成ステップ（Ｓ２３１２）を実行し全域木を構築する頂点リスト１２００とエッジリスト１２１０を更新する。

ここで、全域木生成ステップは、全域木を作成することが可能な任意の方法を利用することができる。例えば、計算量をかけることなく、単純に隣接番号と接続するようにしてもよい。例えば、クラスカル法やプリム法などの全域木生成アルゴリズムを利用してもよい。分析精度を高めるために最も期待される構造は、最大全域木を求めることである。クラスカル法を用いた最大全域木を求めるステップの一例は、図２７を用いて後述する。

なお、上記、全域木生成ステップは、複数の手法を用意し、ユーザ端末２１０からの入力を受け付けて、選択できるようにしてもよい。以上の処理が終了すると、頂点リスト１２００及びエッジリスト１２１０は、図２５Ａ及び図２５Ｂに示すような状態になる。

全域木生成部１１６は、頂点リスト１２００及びエッジリスト１２１０を全域木データとして出力し（ステップＳ２３１３）、処理を終了する。本実施例では、全域木生成部１１６は、頂点リスト１２００及びエッジリスト１２１０をグラフデータ生成部１１３へ入力する。

図２７は、本発明の実施例３の全域木生成ステップの処理の一例を説明するフローチャートである。図２７は、クラスカル法を用いた最大全域木を求める方法の例である。

全域木生成部１１６は、頂点リスト１２００及びエッジ候補リスト２６０１を取得する（ステップＳ２７０１）。

全域木生成部１１６は、エッジ候補リスト２６０１を降順にソートする（ステップＳ２７０３）。具体的には、エッジ候補リスト２６０１の重み１２１４の全体値の値を用いて、エッジ候補リスト１２１４を値の大きな順番に並び替える。

全域木生成部１１６は、エッジ候補リスト２６０１の要素のループを開始する（ステップＳ２７０３）。そして、エッジ候補リスト２６０１の上位のエントリから順にエッジを１つ選択して読み出す(ステップＳ２７０４)。

全域木生成部１１６は、読み出されたエッジがエッジリスト１２１０を構成するグラフの２つの木(連結で閉路を持たない無向グラフ)を連結するか否かを判定する。すなわち、同じ木を連結するエッジでないか否かを判定する。読み出されたエッジが２つの木を連携するエッジでないと判定された場合、全域木生成部１１６は、ステップＳ２７０７に進む。

読み出されたエッジが２つの木を連結するエッジと判断された場合、エッジリスト１２１０を更新する（ステップＳ２７０６）。具体的には、読み出されたエッジを新たなエントリとして、エッジリスト１２１０に追加する。また、頂点リスト１２００に接続エッジ情報を設定する。

エッジリスト１２１０にエッジを追加した場合、全域木生成部１１６は、カウンタをインクリメントすることにより、エッジリストに含まれるエッジ数をカウントする（Ｓ２７０７）。また、追加したエッジをエッジ候補リストから削除する（Ｓ２７０８）。ステップＳ２７０８の処理が完了すると、全域木生成部１１６は、ステップＳ２７０４に戻り、エッジ候補リストから次のエントリのエッジを選択する。

全域木生成部１１６は、エッジ候補リスト２６０１全ての要素について処理完了したか否かを判定する(ステップＳ２７０９）。エッジ候補リストの全ての要素の処理が完了していないと判断された場合、全域木生成部１１６は、ステップＳ２７０３に戻り、同様の処理を実行する。一方、エッジ候補リストの全ての要素の処理が完了したと判断された場合、全域木生成ステップを終了し、ステップＳ２３１３（図２３参照）に進む。以上の処理により、エッジリスト１２１０には、頂点リスト１２００に含まれる全ての頂点から構成される全域木のエッジの一覧が格納される。

図２８は、本発明の実施例３のグラフデータ生成処理の概念を示す説明図である。相関行列データの網掛範囲は全域木データを、太線枠で囲まれた範囲は図８のＳ８０４で算出された閾値(制御因子)以下の値のデータを示す。例えば実施例１では、太線枠の範囲の値は０に設定されていたが、実施例３では、網掛範囲と重複する範囲の値を０に設定せずに元の値を残す。これにより全域木のエッジは保持されるので、精度破綻を引き起こす可能性のあるグラフの分裂を防ぐことができる。

図２９Ａ及び図２９Ｂは、本発明の実施例３のグラフデータ生成処理の実行後の頂点リスト１２００及びエッジリスト１２１０を示す説明図である。図３０は、本発明の実施例３のグラフデータに基づいて表示されるグラフの一例を示す説明図である。

図３１は、実施例３のグラフデータ生成処理(ステップＳ２２０２)の一例を説明するフローチャートである。

グラフデータ生成部１１３は、全域木生成部１１６が出力した頂点リスト１２００及びエッジリスト１２１０、及び中間データとして保持しているエッジ候補リスト２６０１を取得する(ステップＳ２８０１)。全域木生成処理後のエッジ候補リスト２６０１には、全域木生成処理前のエッジ候補リスト２６０１から全域木のエッジが削除されたエッジの一覧が格納されている。

グラフデータ生成部１１３は、制御因子算出部１１２で算出された最大エッジ数よりエッジ候補リストに含まれる全域木のエッジ数を引いた数を、追加可能エッジ数として算出する（Ｓ２８０２）。そして、追加可能エッジ数の範囲内で、エッジ候補リスト２６０１のエッジを選択し読み出す（Ｓ２８０３）。

例えば、追加可能エッジ数に届くまで、エッジ候補リスト２６０１のエッジの重みの大きいものから順にエッジを選択する。また、単に重みの大きいものから順に追加可能エッジ数まで選択するのではなく、例えば、エッジ候補リストの中からランダムに追加可能エッジ数までサンプリングしてもよい。このとき、重みの大きいもの（エッジ候補リストの上位要素）を優先的に選択するように重みつきのサンプリングでもよい。重みの低い要素を取得しないように、閾値（サンプリングされたエッジが閾値以下であれば追加しない）を設定してもよい。

グラフデータ生成部１１３は、選択したエッジをエッジリスト１２１０に追加し、頂点リスト１２００を更新し（Ｓ２８０５）、グラフデータとして出力する（Ｓ２８０５）。

ここでは、全域木生成処理のために作成したエッジ候補リストを利用してグラフデータを生成する処理について説明したため、最大エッジ数を制御因子として利用しているが、実施例１や実施例２のように、最大エッジ数に基づき算出された要素の閾値を制御因子として利用してもよい。この場合、図２８に示したように、相関行列データから、全域木を構成する要素と制御因子となる閾値に基づき決定される要素とを特定し、そのグラフデータを生成する構成となる。

グラフデータ生成処理が終了すると、頂点リスト１２００及びエッジリスト１２１０は、図１４Ａ及び図１４Ｂに示すような状態になる。グラフデータ生成部１１３は、頂点リスト１２００及びエッジリスト１２１０をグラフデータ格納部１１５に出力し、また、ユーザ端末２１０に送信する。ユーザ端末２１０は、受信したグラフデータに基づいて図３０に示すようなグラフを表示することができる。

実施例３によれば、全ての有用なノードが少なくとも一辺は別のノードへの接続を保持するような全域木構造を保持したグラフデータを作成することができる。すなわち、実施例３によれば、精度破綻を引き起こす可能性のあるグラフが複数の連結成分に分かれるグラフ分裂は生じない。よって、作成するグラフデータに全域木構造を保持し、必要精度を保ったグラフ処理が可能となる。

なお、本発明は上記した実施例に限定されるものではなく、様々な変形例が含まれる。また、例えば、上記した実施例は本発明を分かりやすく説明するために構成を詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、各実施例の構成の一部について、他の構成に追加、削除、置換することが可能である。

また、上記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、本発明は、実施例の機能を実現するソフトウェアのプログラムコードによっても実現できる。この場合、プログラムコードを記録した記憶媒体をコンピュータに提供し、そのコンピュータが備えるプロセッサが記憶媒体に格納されたプログラムコードを読み出す。この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施例の機能を実現することになり、そのプログラムコード自体、及びそれを記憶した記憶媒体は本発明を構成することになる。このようなプログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ハードディスク、ＳＳＤ（Ｓｏｌｉｄ Ｓｔａｔｅ Ｄｒｉｖｅ）、光ディスク、光磁気ディスク、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどが用いられる。

また、本実施例に記載の機能を実現するプログラムコードは、例えば、アセンブラ、Ｃ／Ｃ＋＋、ｐｅｒｌ、Ｓｈｅｌｌ、ＰＨＰ、Ｊａｖａ（登録商標）等の広範囲のプログラム又はスクリプト言語で実装できる。

さらに、実施例の機能を実現するソフトウェアのプログラムコードを、ネットワークを介して配信することによって、それをコンピュータのハードディスクやメモリ等の記憶手段又はＣＤ−ＲＷ、ＣＤ−Ｒ等の記憶媒体に格納し、コンピュータが備えるプロセッサが当該記憶手段や当該記憶媒体に格納されたプログラムコードを読み出して実行するようにしてもよい。

上述の実施例において、制御線や情報線は、説明上必要と考えられるものを示しており、製品上必ずしも全ての制御線や情報線を示しているとは限らない。全ての構成が相互に接続されていてもよい。

Claims (10)

1. プロセッサ、及び前記プロセッサに接続されるメモリを備え、複数の指標間の相関値を要素とする相関行列データを用いた処理を実行する計算機であって、
   前記計算機は、記憶装置から取得される前記相関行列データから、一つの指標に対応する頂点、相関関係のある二つの前記頂点を接続するエッジ、及び前記要素の値であるエッジの重みから構成されるリスト構造の第１のグラフデータを生成するグラフ処理部を備え、
   前記グラフ処理部は、
   前記相関行列データを用いた処理を所定時間内に完了するために、前記第１のグラフデータに含めることが可能な最大エッジ数を算出する制御因子算出部と、
   前記相関行列データをリスト構造の第２のグラフデータに変換し、前記第２のグラフデータの全ての頂点及び一部のエッジで構成される全域木である第３のグラフデータを生成する全域木生成部と、
   前記最大エッジ数を用いて、前記第２及び前記第３のグラフデータに基づき、前記第１のグラフデータを生成するグラフデータ生成部と
   を備えることを特徴とする計算機。
2. 請求項１に記載の計算機であって、
   前記全域木は、エッジの重みの和が最大となる最大全域木であることを特徴とする計算機。
3. 請求項２に記載の計算機であって、
   前記第１のグラフデータは前記第３のグラフデータを含むことを特徴とする計算機。
4. 請求項３に記載の計算機であって、
   前記グラフデータ生成部は、エッジの合計数が前記最大エッジ数になるまで、前記第３のグラフデータに前記第２のグラフデータのみに含まれるエッジを重み順に追加することで、前記第１のグラフデータを生成することを特徴とする計算機。
5. 請求項１乃至４のいずれかに記載の計算機であって、
   前記全域木生成部は、前記相関行列データに含まれる指標のうち、他の全ての指標との相関値が所定値以下である指標の要素を、前記相関行列データから削除し、前記指標の要素が削除された相関行列データをリスト構造の前記第２のグラフデータに変換することを特徴とする計算機。
6. プロセッサ、及び前記プロセッサに接続されるメモリを備え、複数の指標間の相関値を要素とする相関行列データを用いた処理を実行する計算機におけるグラフデータ生成方法であって、
   前記計算機は、記憶装置から取得される前記相関行列データから、一つの指標に対応する頂点、相関関係のある二つの前記頂点を接続するエッジ、及び前記要素の値であるエッジの重みから構成されるリスト構造の第１のグラフデータを生成するグラフ処理部を備え、
   前記グラフ処理部は、
   前記相関行列データを用いた処理を所定時間内に完了するために、前記第１のグラフデータに含めることが可能な最大エッジ数を算出し、
   前記相関行列データをリスト構造の第２のグラフデータに変換し、前記第２のグラフデータの全ての頂点及び一部のエッジで構成される全域木である第３のグラフデータを生成し、
   前記最大エッジ数を用いて、前記第２及び前記第３のグラフデータに基づき、前記第１のグラフデータを生成することを特徴とするグラフデータ生成方法。
7. 請求項６に記載のグラフデータ生成方法であって、
   前記全域木は、エッジの重みの和が最大となる最大全域木であることを特徴とするグラフデータ生成方法。
8. 請求項７に記載のグラフデータ生成方法であって、
   前記第１のグラフデータは前記第３のグラフデータを含むことを特徴とするグラフデータ生成方法。
9. 請求項８に記載のグラフデータ生成方法であって、
   エッジの合計数が前記最大エッジ数になるまで、前記第３のグラフデータに前記第２のグラフデータのみに含まれるエッジを重み順に追加することで、前記第１のグラフデータを生成することを特徴とするグラフデータ生成方法。
10. 請求項６乃至９のいずれかに記載のグラフデータ生成方法であって、
    前記相関行列データに含まれる指標のうち、他の全ての指標との相関値が所定値以下である指標の要素を、前記相関行列データから削除し、前記指標の要素が削除された相関行列データをリスト構造の前記第２のグラフデータに変換することを特徴とするグラフデータ生成方法。

Images