(57)【要約】【課題】  データマイニングの対象となる観測項目の状態を指標する変数間の関係性を表すグラフを高い確率で得るとともに、出力されるグラフの信頼性を向上すること。【解決手段】  変数間の関係性を表すグラフを生成する方法において、グラフの生成数を設定するステップＳ２と、グラフ生成回毎に、全変数集合Ｖを構成する変数Ｘの順序をランダムに設定するステップＳ５と、変数間の関係性を表すグラフの復元処理を実行するステップＳ６と、グラフの生成回毎にそれぞれ生成されるいずれかのグラフに存在するすべてのエッジを含む包括グラフを出力するステップＳ１０とを有する。グラフの復元処理においては、相関係数行列の逆行列を計算して、条件付き独立の判定対象である２変数に係るいずれかの対角要素が所定の閾値より大きい場合には、当該２変数に係る条件付き独立判定を実施するための演算処理を省略する。【選択図】  図６
2007207101.tif 000002
【特許請求の範囲】
【請求項１】
与えられた全変数集合を構成するすべての変数に対応するノードを設定するとともに、すべてのノード対を無向エッジで結ぶことで構成される完全無向グラフを設定するステップと、
所定の順序で並ぶ変数から構成される全変数集合から第１の変数および第２の変数を選択するとともに、空集合あるいは前記第１の変数および前記第２の変数以外の１以上の変数から成る集合として与えられる部分集合を選択するステップと、
前記部分集合が与えられたときに前記第１の変数と前記第２の変数とが条件付き独立であるかを判定して、条件付き独立である場合には、前記第１の変数に対応するノードと前記第２の変数に対応するノードとを結ぶ無向エッジを削除するステップと、
Ｖ字合流に係る判定に基づいて、無向エッジを矢線に変更するステップと、
少なくとも１つのオリエンテーションルールに基づいて、無向エッジを矢線に変更するステップとを有し、変数間の関係性を表すグラフを出力するグラフ生成方法において、
条件付き独立判定の対象となる前記第１の変数および前記第２の変数並びに条件付き独立判定に用いられる前記部分集合から成る変数列についての相関係数行列の逆行列を計算して、当該逆行列の前記第１の変数に係る対角要素が所定の閾値より大きいか、あるいは当該逆行列の前記第２の変数に係る対角要素が所定の閾値より大きい場合には、前記第１の変数と前記第２の変数との条件付き独立を判定するための演算処理を省略することを特徴とするグラフ生成方法。
【請求項２】
グラフの生成数を設定するステップと、
グラフの生成回毎に、与えられた全変数集合を構成する変数の順序をランダムに設定するステップと、
全変数集合を構成するすべての変数に対応するノードを設定するとともに、すべてのノード対を無向エッジで結ぶことで構成される完全無向グラフを設定するステップと、
設定された順序で並ぶ変数から構成される全変数集合から第１の変数および第２の変数を選択するとともに、空集合あるいは前記第１の変数および前記第２の変数以外の１以上の変数から成る集合として与えられる部分集合を選択するステップと、
前記部分集合が与えられたときに前記第１の変数と前記第２の変数とが条件付き独立であるかを判定して、条件付き独立である場合には、前記第１の変数に対応するノードと前記第２の変数に対応するノードとを結ぶ無向エッジを削除するステップと、
Ｖ字合流に係る判定に基づいて、無向エッジを矢線に変更するステップと、
少なくとも１つのオリエンテーションルールに基づいて、無向エッジを矢線に変更するステップと、
グラフの生成回毎に変数間の関係性を表すようにそれぞれ生成されるいずれかのグラフに存在するすべてのエッジを含む包括グラフを出力するステップとを有することを特徴とするグラフ生成方法。
【請求項３】
所定の生成数だけ生成される複数のグラフから構成されるグラフ集合においてそれぞれのエッジがグラフ内に存在する累計数をグラフの生成数で割ることで得られる存在確率を計算するステップを有し、
出力される包括グラフにおいて、存在するそれぞれのエッジについて対応する存在確率が示されることを特徴とする請求項２に記載のグラフ生成方法。
【請求項４】
各エッジについて、少なくとも、無向エッジの累計数、第１の方向を向く矢線の累計数および第１の方向と反対の第２の方向を向く矢線の累計数を計算するステップと、
各エッジについて、無向エッジの累計数、第１の方向を向く矢線の累計数および第２の方向を向く矢線の累計数をグラフの生成数で割ることで得られるそれぞれのエッジ種類に対応する存在確率を計算するステップとを有し、
出力される包括グラフにおいて、存在確率の最も大きな種類のエッジおよび当該種類のエッジの存在確率が示されることを特徴とする請求項２に記載のグラフ生成方法。
【請求項５】
与えられた全変数集合を構成するすべての変数に対応するノードを設定するとともに、すべてのノード対を無向エッジで結ぶことで構成される完全無向グラフを設定するステップと、
所定の順序で並ぶ変数から構成される全変数集合から第１の変数および第２の変数を選択するとともに、空集合あるいは前記第１の変数および前記第２の変数以外の１以上の変数から成る集合として与えられる部分集合を選択するステップと、
前記部分集合が与えられたときに前記第１の変数と前記第２の変数とが条件付き独立であるかを判定して、条件付き独立である場合には、前記第１の変数に対応するノードと前記第２の変数に対応するノードとを結ぶ無向エッジを削除するステップと、
Ｖ字合流に係る判定に基づいて、無向エッジを矢線に変更するステップと、
少なくとも１つのオリエンテーションルールに基づいて、無向エッジを矢線に変更するステップとを有し、変数間の関係性を表すグラフを出力するグラフ生成プログラムにおいて、
条件付き独立判定の対象となる前記第１の変数および前記第２の変数並びに条件付き独立判定に用いられる前記部分集合から成る変数列についての相関係数行列の逆行列を計算して、当該逆行列の前記第１の変数に係る対角要素が所定の閾値より大きいか、あるいは当該逆行列の前記第２の変数に係る対角要素が所定の閾値より大きい場合には、前記第１の変数と前記第２の変数との条件付き独立を判定するための演算処理を省略することを特徴とするグラフ生成プログラム。
【請求項６】
グラフの生成数を設定するステップと、
グラフの生成回毎に、与えられた全変数集合を構成する変数の順序をランダムに設定するステップと、
全変数集合を構成するすべての変数に対応するノードを設定するとともに、すべてのノード対を無向エッジで結ぶことで構成される完全無向グラフを設定するステップと、
設定された順序で並ぶ変数から構成される全変数集合から第１の変数および第２の変数を選択するとともに、空集合あるいは前記第１の変数および前記第２の変数以外の１以上の変数から成る集合として与えられる部分集合を選択するステップと、
前記部分集合が与えられたときに前記第１の変数と前記第２の変数とが条件付き独立であるかを判定して、条件付き独立である場合には、前記第１の変数に対応するノードと前記第２の変数に対応するノードとを結ぶ無向エッジを削除するステップと、
Ｖ字合流に係る判定に基づいて、無向エッジを矢線に変更するステップと、
少なくとも１つのオリエンテーションルールに基づいて、無向エッジを矢線に変更するステップと、
グラフの生成回毎に変数間の関係性を表すようにそれぞれ生成されるいずれかのグラフに存在するすべてのエッジを含む包括グラフを出力するステップとを有することを特徴とするグラフ生成プログラム。
【請求項７】
所定の生成数だけ生成される複数のグラフから構成されるグラフ集合においてそれぞれのエッジがグラフ内に存在する累計数をグラフの生成数で割ることで得られる存在確率を計算するステップと、
出力される包括グラフにおいて、存在するそれぞれのエッジについて対応する存在確率を示すステップとを有することを特徴とする請求項６に記載のグラフ生成プログラム。
【請求項８】
各エッジについて、少なくとも、無向エッジの累計数、第１の方向を向く矢線の累計数および第１の方向と反対の第２の方向を向く矢線の累計数を計算するステップと、
各エッジについて、無向エッジの累計数、第１の方向を向く矢線の累計数および第２の方向を向く矢線の累計数をグラフの生成数で割ることで得られるそれぞれのエッジ種類に対応する存在確率を計算するステップと、
出力される包括グラフにおいて、存在確率の最も大きな種類のエッジおよび当該種類のエッジの存在確率を示すステップとを有することを特徴とする請求項６に記載のグラフ生成プログラム。
【請求項９】
観測されたデータ群から観測項目の状態を指標する変数間の関係性を表すグラフを生成するデータマイニングシステムにおいて、
少なくとも観測データおよびグラフの生成数を入力する入力手段と、
グラフの生成回毎に、与えられた全変数集合を構成する変数の順序をランダムに設定して複数のグラフを生成するとともに、所定の生成数だけ生成される複数のグラフから構成されるグラフ集合においてそれぞれのエッジがグラフ内に存在する累計数をグラフの生成数で割ることで得られる存在確率を計算して、変数間の関係性を表すグラフの構造に係るデータ並びにエッジの存在確率を出力する演算手段と、
少なくとも観測データ、グラフの生成数、グラフの構造に係るデータ並びにエッジの存在確率を記憶するとともに、数値演算を実行する際のワークスペースを提供する記憶手段と、
少なくとも出力データを基にしたグラフを表示する表示手段とを有して構成され、
変数間の関係性を表す包括グラフにおいて存在確率が０より大きいエッジが全て前記表示手段に表示されることを特徴とするデータマイニングシステム。
【請求項１０】
前記表示手段において、エッジに存在確率が付記して表示されることを特徴とする請求項９に記載のデータマイニングシステム。
【請求項１１】
前記表示手段において、存在確率に応じてエッジの太さまたはエッジの色が変化して表示されることを特徴とする請求項９に記載のデータマイニングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、グラフ生成方法、グラフ生成プログラム並びにデータマイニングシステムに係り、特に非循環的有向独立グラフを復元する手法を用いることで、観測されたデータ群から、観測項目の状態を指標する変数間の関係性を表すグラフを生成するためのグラフ生成方法およびグラフ生成プログラム、並びに当該グラフをユーザに対して表示するデータマイニングシステムに関するものである。
【０００２】
非巡回的有向独立グラフは、グラフ用語として与えられるものである。非巡回的とは、巡回閉路のないグラフを意味する。有向グラフとは、ノード（頂点）間を結ぶすべてのエッジ（辺）が片側矢印または両側矢印をもつ矢線であるグラフを意味する。また、非巡回的有向グラフが、それぞれがノードとして表される変数から成る変数集合の同時確率密度関数をグラフにしたがう遂次的因数分解の形に規定できるとき、そのグラフを非巡回的有向独立グラフという。また、すべてのエッジが無向のグラフを無向グラフといい、無向のエッジと矢線とが混在するグラフを部分無向グラフという。なお、以下の説明では、無向のエッジを無向エッジと称するとともに有向のエッジを矢線と称し、無向エッジと矢線とを総称する用語として「エッジ」を用いるものとする。さらに、演算により得られた複数のグラフに存在するエッジをすべて含むように生成されるグラフを包括グラフと称するものとする。
【背景技術】
【０００３】
近年、数学的手法を用いて、蓄積された大量のデータから、観測される事象や対象物間の関係性、あるいは観測される事象や対象物等の属性として与えられる複数の項目間の関係性（以下、観測項目間の関係性と称する）を発見するデータマイニングが注目を浴びている。データマイニングの一つの手法として、非巡回的有向独立グラフを復元することで観測項目間の関係性を発見する方法がある。図１は、非巡回的有向独立グラフの一例を示す図である。図１において、Ｘｉ（ｉ＝１〜５）は観測項目に係る状態を量的に指標する観測変数を表すノードである。本手法では、観測変数に数学的手法を適用することで、ノード間の関係性を示すエッジの存在並びにエッジの種類および矢線の向きを特定する。ノードＸｉからノードＸｊに向かう矢線が存在する場合、観測変数Ｘｉに係る観測項目は観測変数Ｘｊに係る観測項目の原因となる。
【０００４】
非巡回的有向独立グラフを復元することで実現されるデータマイニングで取り扱う観測項目をそれぞれ表す変数の全体集合として与えられる全変数集合をＶ＝｛Ｘ１，Ｘ２，・・・，Ｘｐ｝とする。観測可能な全変数集合Ｖを構成する各変数Ｘは、連続変数でもよく、また離散変数でもよい。例えば、自動車ボディの塗装条件の解析においては、連続変数が用いられる。各変数としては、次のようなものが与えられる。
Ｘ１：希釈率，Ｘ２：粘度，Ｘ３：ガンスピード，Ｘ４：吹付距離，Ｘ５：霧化エアー圧，Ｘ６：パターン幅，Ｘ７：吐出量，Ｘ８：塗料温度，Ｘ９：室温，Ｘ１０：湿度，Ｘ１１：塗着率
【０００５】
所定の回数Ｎ（例えばＮ＝５０）にわたって、それぞれの塗装工程についての上記の１１変数の値を測定する。すなわち、塗料の希釈率Ａ，粘度Ｂ，ガンスピードＣ，吹付距離Ｄ・・・という条件で塗料が吹き付けられたときの塗着率がＥであったという１１組のデータから成る測定を、５０回にわたって実施する。そして、後述するＰＣアルゴリズムを適用して変数間の関係性を非巡回的有向独立グラフを用いて表現する。これにより、塗着率と他の観測項目との間の関係性を把握することが可能となる。
【０００６】
非巡回的有向独立グラフが得られれば、各観測変数間の関係性強度を求めることが可能となる。図２は、図１に示された非巡回的有向独立グラフに、関係性強度を示す偏回帰係数βを付記した図である。このグラフからは、以下の重回帰式を設定することができる。
Ｘ３＝β３１Ｘ１＋β３２Ｘ２＋ｅ３
Ｘ４＝β４１Ｘ１＋ｅ４
Ｘ５＝β５３Ｘ３＋β５４Ｘ４＋ｅ５
最小二乗法を用いて、上記の重回帰式を解法することにより、偏回帰係数βおよび誤差項ｅを推定する。すなわち、各変数に測定回数分のデータを代入して、二乗誤差の総和が最小となる偏回帰係数βおよび誤差項ｅを求める。
【０００７】
また、全変数集合Ｖを構成する各変数Ｘは、離散変数でもよい。例えば、商品の質感の解析においては、段階的な値を有する以下のような変数が設定される。
Ｘ１：｛柔らかい−硬い｝を段階的（７段階）に指標する変数
Ｘ２：｛平面的な−立体的な｝を段階的（７段階）に指標する変数
Ｘ３：｛光沢のある−光沢のない｝を段階的（７段階）に指標する変数
Ｘ４：｛粗い−繊細な｝を段階的（７段階）に指標する変数
対象商品について、ある人が例えば、Ｘ１＝１，Ｘ２＝３，Ｘ３＝２，Ｘ４＝７と評価したとする。所定の人数Ｎ（例えばＮ＝５０）に対して、このような評価を行うものとする。｛Ｘ１，Ｘ２，Ｘ３，Ｘ４｝を全変数集合Ｖとして、得られたデータ群に対してＰＣアルゴリズムを適用して所定の演算を実施することで、連続変数の場合と同様に、観測項目間の関係性を表す非巡回的有向独立グラフを得ることができる。
【０００８】
次に、ＰＣアルゴリズムについて説明する。ＰＣアルゴリズムは以下の工程に沿って実施される。
ステップ１：全変数集合Ｖに含まれる変数に対応するノードについて全てのノード対を無向エッジで結ぶことで構成される完全無向グラフを、非巡回的有向独立グラフＣの初期設定のグラフとして与える。
ステップ２：グラフ復元を段階的に行うために、各段階を指標する変数ｎを設定する。また、ｎの初期値として、０を与える。
【０００９】
ステップ３：グラフＣにおいて隣接している（エッジで連結されている）順序のあるノード対（Ｘｉ，Ｘｊ）として、Ａｄ（Ｃ，Ｘｉ）￥｛Ｘｊ｝の要素数がｎ以上のノード対を選択する。また、Ａｄ（Ｃ，Ｘｉ）￥｛Ｘｊ｝の部分集合Ｓで、要素数がｎのものを選択する。そして、部分集合Ｓを与えたとき変数Ｘｉと変数Ｘｊとが条件付き独立ならば、ノードＸｉとノードＸｊとを結ぶエッジＥｉｊを削除し、Ｓの要素を集合Ｓｅｐｓｅｔ（Ｘｉ，Ｘｊ）の要素として登録する。これをＡｄ（Ｃ，Ｘｉ）￥｛Ｘｊ｝の要素数がｎ以上のすべての順序のあるノード対（Ｘｉ，Ｘｊ）について行う。
ここで、Ａｄ（Ｃ，Ｘｉ）は、与えられたグラフＣにおいてノードＸｉと隣接しているノードの集合を表す。また、Ａｄ（Ｃ，Ｘｉ）￥｛Ｘｊ｝は、与えられたグラフＣにおいて、ノードＸｉと隣接しているノードの集合のなかから、ノードＸｊを除いたノードの集合を表す。
なお、以下の説明においては、変数Ｘｉと変数Ｘｊとが独立であることは、「Ｘｉ＿Ｘｊ」と表すものとする。また、空集合、あるいは変数Ｘｉおよび変数Ｘｊ以外の１以上の変数から構成される集合として与えられる部分集合Ｓを与えたときに、変数Ｘｉと変数Ｘｊとが条件付き独立であることは、「Ｘｉ＿Ｘｊ｜Ｓ」と表すものとする。
【００１０】
次に、部分集合Ｓを与えたときに変数Ｘｉと変数Ｘｊとが条件付き独立であるか否かを判定する判定方法について説明する。いま、変数ベクトル（Ｘ１，Ｘ２，・・・，Ｘｐ）がｐ次元の多変量正規分布にしたがっているとする。分散共分散行列をΣ＝（σｉｊ）とし、その逆行列をΣ−１＝（σｉｊ）と表記する。このとき、「σｉｊ＝０」と「変数Ｘｉと変数Ｘｊとは、変数Ｘｉおよび変数Ｘｊ以外の残りの（ｐ−２）個の変数から成る部分集合を与えたときに条件付き独立である」とは同値となる。また、σｉｊ＝０のとき、偏相関係数Ｐｉｊ＝０となる。したがって、Ｐｉｊが０とみなせれば、変数Ｘｉと変数Ｘｊとが条件付き独立であると判定することができる。
【００１１】
変数Ｘｉ、変数Ｘｊおよび部分集合Ｓから成る変数列について、相関行列をΠ＝（ρｉｊ）とし、その逆行列をΠ−１＝（ρｉｊ）とすれば、変数Ｘｉと変数Ｘｊとの偏相関係数Ｐｉｊは、次のように表される。
Ｐｉｊ＝−ρｉｊ／｛（ρｉｉ）１／２（ρｊｊ）１／２｝
また、Ｐｉｊ＝０とみなせるか否かについては、統計的仮説検定を用いて判定する。部分集合Ｓが与えられる条件をｐａで表現するものとすると、偏相関係数Ｐｉｊ｜ｐａのｔ検定（帰無仮説Ｈ０：Ｐｉｊ｜ｐａ＝０）には、Ｐｉｊ｜ｐａの正規性が要求される。実際には、標本偏相関係数が正規性の仮定を満たすことは必ずしも保証されないために、Ｐｉｊ｜ｐａを［数１］によりＺ変換する。
【００１２】
【数１】
2007207101.tif 000003
【００１３】
また、Ｚ統計量は、［数２］で表される。
【００１４】
【数２】
2007207101.tif 000004
【００１５】
［数２］において、“ｐａ”は条件付き次数、すなわち部分集合Ｓに含まれる変数の数を示し、ｍは観測されたデータ数を示す。漸近的に、Ｚ統計量は自由度ｍ−３−ｐａのΧ２分布をする。有意水準をαとすると、Ｚ＞Ｚ２／αの場合に、帰無仮説Ｈ０：Ｐｉｊ｜ｐａ＝０を棄却する。帰無仮説Ｈ０を棄却できない場合には、Ｐｉｊ｜ｐａ＝０とみなして、部分集合Ｓが与えられたときに変数Ｘｉと変数Ｘｊとは条件付き独立であると判定する。なお、部分集合Ｓが空集合の場合には、偏相関係数Ｐｉｊの代わりに相関係数Ｒｉｊを用いて、ｐａ＝０として上記方法を適用することで、条件付き独立を判定する。
【００１６】
ステップ４：任意の順序のあるノード対（Ｘｉ，Ｘｊ）に対して、Ａｄ（Ｃ，Ｘｉ）￥｛Ｘｊ｝の要素数がｎ以下ならば、ステップ５へ進む。そうでなければ、ｎ＝ｎ＋１と更新してステップ３を行う。
ステップ５：グラフＣにおいて、Ｘｉ−Ｘｊ−Ｘｋという構造（ＸｉとＸｋとは隣接していない）があり、Ｓｅｐｓｅｔ（Ｘｉ，Ｘｋ）の要素にＸｊがないならば、Ｘｉ→Ｘｊ←Ｘｋと矢印をつける。エッジのつながりは道と称されるが、連結されるＸｉ，Ｘｊ，Ｘｋから成る道が上記のような関係を満たす場合には、この道がＶ字合流であると表現される。
Ｓｅｐｓｅｔ（Ｘｉ，Ｘｋ）の要素にＸｊが存在する場合には、Ｘｊが与えられたときにＸｉとＸｋとは条件付き独立となり、Ｘｉ＿Ｘｋ｜Ｘｊが成立する。非巡回有向独立グラフにおいては、Ｘｉ→Ｘｊ←ＸｋというＶ字合流があれば、ＸｉとＸｋとは、Ｘｊを含む任意の変数集合を与えたときに条件付き独立にならないという性質がある。したがって、上記のように、Ｓｅｐｓｅｔ（Ｘｉ，Ｘｋ）の要素にＸｊがないならば、Ｘｉ→Ｘｊ←Ｘｋと矢印をつけることができる。
【００１７】
以下のステップ６およびステップ７においては、ステップ５までの工程を実施することで得られたグラフＣに対して、オリエンテーションルールを適用することで、エッジを矢線に変更する。図３は、オリエンテーションルールを示す図である。図３（ａ）には、オリエンテーションルールのルール１が示されている。ルール１では、ステップ５までの工程により全てのＶ字合流が検出されるという観点に基づいて、エッジの矢印の方向が決定される。また、図３（ｂ）には、オリエンテーションルールのルール２が示されている。ルール２では、巡回する道が存在しないという観点に基づいて、エッジの矢印の方向が決定される。
【００１８】
ステップ６：グラフＣに幾つかの矢印が加わったグラフにおいて、Ｘｉ→Ｘｊ−Ｘｋという構造が存在し、ＸｉとＸｋとが隣接していない場合には、オリエンテーションルールのルール１に基づいて、Ｘｊ→Ｘｋと矢印を付ける。
ステップ７：グラフＣに幾つかの矢印が加わったグラフにおいて、ＸｉからＸｋに有向道があり、かつＸｉとＸｋとの間に無向エッジがある場合には、オリエンテーションルールのルール２に基づいて、そのエッジにＸｉ→Ｘｋと矢印を付ける。
【００１９】
次に、ＰＣアルゴリズムを適用した非巡回的有向独立グラフの復元の具体例について説明する。図１に示された非巡回的有向独立グラフが背後に潜んでいる場合を想定して、Ｘ１〜Ｘ５の５変数に対して、ＰＣアルゴリズムを適用する。ステップ１では、５変数を全変数集合とする完全無向グラフを初期設定する。ステップ２では、ｎに初期値として０を与える。
【００２０】
ステップ３については、ｎの値に応じて段階的に説明する。図４は、非巡回的有向独立グラフが生成される過程で生成される無向グラフである。図５は、非巡回的有向独立グラフが生成される過程で生成される部分無向グラフである。独立性の判定については、既に述べたように変数Ｘｉおよび変数Ｘｊと部分集合Ｓ（空集合の場合あり）とから成る変数列に係る偏相関係数Ｐｉｊを求めて、Ｐｉｊ＝０とみなせるか否かを統計的仮説検定を用いることで判定する。まずｎ＝０では、２変数間の独立性を調べることになる。ここで、Ｘ１＿Ｘ２とＸ２＿Ｘ４とが認識されるので、変数Ｘ１と変数Ｘ２との間のエッジおよび変数Ｘ２と変数Ｘ４との間のエッジが削除される。これらの変数対のＳｅｐｓｅｔはそれぞれ空集合である。
【００２１】
次に、ｎ＝１では、１つの変数を与えたときの、（Ｘ１，Ｘ２）および（Ｘ２，Ｘ４）以外の変数対の条件付き独立関係を調べる。例えば、変数対（Ｘ３，Ｘ４）については、「Ｘ３＿Ｘ４｜Ｘ１」，「Ｘ３＿Ｘ４｜Ｘ２」，「Ｘ３＿Ｘ４｜Ｘ５」のいずれかが成立しているか否かが調べられる。ここで、「Ｘ３＿Ｘ４｜Ｘ１」が成立するので、変数Ｘ３と変数Ｘ４とを結ぶエッジが削除され、Ｓｅｐｓｅｔ（Ｘ３，Ｘ４）の要素にＸ１が登録される。さらに、ｎ＝２では、「Ｘ１＿Ｘ５｜（Ｘ３，Ｘ４）」の成立が確認され、Ｓｅｐｓｅｔ（Ｘ１，Ｘ５）の要素に（Ｘ３，Ｘ４）が登録される。このｎ＝２の段階で、図４の無向グラフが得られることになる。次に、ｎ＝３に進むが、図４において既に４つのノードと隣接するようなノードがないので、ステップ３の処理を完了して、ステップ５の処理に移行する。
【００２２】
ステップ５では、グラフ上に存在するＸｉ−Ｘｊ−Ｘｋというそれぞれの構造について、Ｓｅｐｓｅｔ（Ｘｉ，Ｘｋ）の要素にＸｊが存在するか否かを判定する。図４に示される無向グラフにおいて、Ｘｉ−Ｘｊ−Ｘｋという構造を列挙すると、「Ｘ２−Ｘ３−Ｘ１」，「Ｘ３−Ｘ１−Ｘ４」，「Ｘ１−Ｘ４−Ｘ５」，「Ｘ１−Ｘ３−Ｘ５」，「Ｘ２−Ｘ３−Ｘ５」および「Ｘ３−Ｘ５−Ｘ４」の６つが挙げられる。ここで、例えば「Ｘ３−Ｘ１−Ｘ４」においては、Ｓｅｐｓｅｔ（Ｘ３，Ｘ４）の要素にＸ１が存在するから、この道がＶ字合流でないと判定される。また、「Ｘ２−Ｘ３−Ｘ１」においては、Ｓｅｐｓｅｔ（Ｘ２，Ｘ１）の要素にＸ３が存在しないから、この道がＶ字合流であると判定され、「Ｘ２→Ｘ３」および「Ｘ１→Ｘ３」と矢印を付ける。上記の６つの構造についてこのような判定を実施することで、図５に示されるような部分無向グラフが得られる。
【００２３】
次に、本来であればステップ６およびステップ７の処理を実行するところであるが、図５に示される部分無向グラフに対しては、オリエンテーションのルール１およびルール２を適用できる構造が存在しない。実際、ノードＸ１とノードＸ４とを結ぶエッジにどちら向きの矢印を付けても、グラフ全体で成立している独立性および条件付き独立性は同じである。なお、以上に説明したＰＣアルゴリズムについては、例えば「シリーズ＜予測と発見の科学＞１，統計的因果推論−回帰分析の新しい枠組み−，宮川  雅巳著，朝倉書店刊，２００４年」に説明が為されている。また、非巡回的有向独立グラフを復元する手法は、ＰＣアルゴリズムに限られるものではなく、他にＳＧＳアルゴリズム等の方法も存在する。
【００２４】
【非特許文献１】「シリーズ＜予測と発見の科学＞１，統計的因果推論−回帰分析の新しい枠組み−，宮川  雅巳著，朝倉書店刊，２００４年」
【発明の開示】
【発明が解決しようとする課題】
【００２５】
上記のように非巡回的有向独立グラフを復元することに基づくデータマイニングでは、例えばＸｉ＿Ｘｊ｜Ｓ等で表される条件付き独立を判定するために、偏相関係数行列を計算する必要がある。然るに、Ｘｉ，Ｘｊ，Ｓ間の多重共線性が高い場合すなわちＸｉ，Ｘｊ，Ｓ間に強い線形関係が存在する場合には、演算過程において除数が非常に小さくなる。これにより、オーバーフロー等に起因して演算にエラーが生じて、演算が中断するかあるいは演算を最後まで実行できなくなり、非巡回的有向独立グラフを得られない場合があるという課題があった。また、非巡回的有向独立グラフが得られても、標本データ数の不足やデータ観測の際に生じるノイズ等に起因して、全変数集合Ｖを構成する各変数Ｘの順序に応じて、出力される非巡回的有向独立グラフが異なるという課題があった。
【００２６】
本願発明は上記課題を解決するためになされたものであり、非巡回的有向独立グラフを高い確率で得ることができるグラフ生成方法およびグラフ生成プログラムを提供することを目的とする。また、得られた非巡回的有向独立グラフの信頼性を高めることが可能なグラフ生成方法およびグラフ生成プログラムを提供することを目的とする。さらに、上記のグラフ生成プログラムに基づいて動作して、信頼性の高い非巡回的有向独立グラフを得ることができるデータマイニングシステムを得ることを目的とする。
【課題を解決するための手段】
【００２７】
上記の技術的課題を解決するために、本願発明に係るグラフ生成方法およびグラフ生成プログラムは、与えられた全変数集合を構成するすべての変数に対応するノードを設定するとともに、すべてのノード対を無向エッジで結ぶことで構成される完全無向グラフを設定するステップと、所定の順序で並ぶ変数から構成される全変数集合から第１の変数および第２の変数を選択するとともに、空集合あるいは第１の変数および第２の変数以外の１以上の変数から成る集合として与えられる部分集合を選択するステップと、部分集合が与えられたときに第１の変数と第２の変数とが条件付き独立であるかを判定して、条件付き独立である場合には、第１の変数に対応するノードと第２の変数に対応するノードとを結ぶ無向エッジを削除するステップと、Ｖ字合流に係る判定に基づいて、無向エッジを矢線に変更するステップと、少なくとも１つのオリエンテーションルールに基づいて、無向エッジを矢線に変更するステップとを有し、条件付き独立判定の対象となる第１の変数および第２の変数並びに条件付き独立判定に用いられる部分集合から成る変数列についての相関係数行列の逆行列を計算して、当該逆行列の第１の変数に係る対角要素が所定の閾値より大きいか、あるいは当該逆行列の第２の変数に係る対角要素が所定の閾値より大きい場合には、第１の変数と第２の変数との条件付き独立を判定するための演算処理を省略するようにしたものである。
【００２８】
また、本願発明に係るグラフ生成方法およびグラフ生成プログラムは、グラフの生成数を設定するステップと、グラフの生成回毎に、与えられた全変数集合を構成する変数の順序をランダムに設定するステップと、全変数集合を構成するすべての変数に対応するノードを設定するとともに、すべてのノード対を無向エッジで結ぶことで構成される完全無向グラフを設定するステップと、設定された順序で並ぶ変数から構成される全変数集合から第１の変数および第２の変数を選択するとともに、空集合あるいは第１の変数および第２の変数以外の１以上の変数から成る集合として与えられる部分集合を選択するステップと、部分集合が与えられたときに第１の変数と第２の変数とが条件付き独立であるかを判定して、条件付き独立である場合には、第１の変数に対応するノードと第２の変数に対応するノードとを結ぶ無向エッジを削除するステップと、Ｖ字合流に係る判定に基づいて、無向エッジを矢線に変更するステップと、少なくとも１つのオリエンテーションルールに基づいて、無向エッジを矢線に変更するステップと、グラフの生成回毎に変数間の関係性を表すようにそれぞれ生成されるいずれかのグラフに存在するすべてのエッジを含む包括グラフを出力するステップとを有するようにしたものである。
【００２９】
また、本願発明に係るグラフ生成方法およびグラフ生成プログラムは、所定の生成数だけ生成される複数のグラフから構成されるグラフ集合においてそれぞれのエッジがグラフ内に存在する累計数をグラフの生成数で割ることで得られる存在確率を計算するステップを有し、出力される包括グラフにおいて、存在するそれぞれのエッジについて対応する存在確率が示されるようにしたものである。
【００３０】
また、本願発明に係るグラフ生成方法およびグラフ生成プログラムは、各エッジについて、少なくとも、無向エッジの累計数、第１の方向を向く矢線の累計数および第１の方向と反対の第２の方向を向く矢線の累計数を計算するステップと、各エッジについて、無向エッジの累計数、第１の方向を向く矢線の累計数および第２の方向を向く矢線の累計数をグラフの生成数で割ることで得られるそれぞれのエッジ種類に対応する存在確率を計算するステップとを有し、出力される包括グラフにおいて、存在確率の最も大きな種類のエッジおよび当該種類のエッジの存在確率が示されるようにしたものである。
【００３１】
また、本願発明に係るデータマイニングシステムは、少なくとも観測データおよびグラフの生成数を入力する入力手段と、グラフの生成回毎に、与えられた全変数集合を構成する変数の順序をランダムに設定して複数のグラフを生成するとともに、所定の生成数だけ生成される複数のグラフから構成されるグラフ集合においてそれぞれのエッジがグラフ内に存在する累計数をグラフの生成数で割ることで得られる存在確率を計算して、変数間の関係性を表すグラフの構造に係るデータ並びにエッジの存在確率を出力する演算手段と、少なくとも観測データ、グラフの生成数、グラフの構造に係るデータ並びにエッジの存在確率を記憶するとともに、数値演算を実行する際のワークスペースを提供する記憶手段と、少なくとも出力データを基にしたグラフを表示する表示手段とを有して構成され、変数間の関係性を表す包括グラフにおいて存在確率が０より大きいエッジが全て前記表示手段に表示されるようにしたものである。
【００３２】
また、本願発明に係るデータマイニングシステムは、表示手段において、エッジに存在確率が付記して表示されるようにしたものである。
【００３３】
また、本願発明に係るデータマイニングシステムは、表示手段において、存在確率に応じてエッジの太さまたはエッジの色が変化して表示されるようにしたものである。
【発明の効果】
【００３４】
本願発明によれば、条件付き独立判定の対象となる第１の変数および第２の変数並びに条件付き独立判定に用いられる部分集合から成る変数列についての相関係数行列の逆行列を計算して、当該逆行列の第１の変数に係る対角要素が所定の閾値より大きいか、あるいは当該逆行列の第２の変数に係る対角要素が所定の閾値より大きい場合には、第１の変数と第２の変数との条件付き独立を判定するための演算処理を省略するように構成したので、高い多重線形性に基づいて発生するエラーに起因する演算の中断や中止を回避することが可能となり、観測項目の状態を指標する変数間の関係性を表すグラフを高い確率で得ることができるという効果を奏する。
【００３５】
本願発明によれば、グラフの生成数を設定するステップと、グラフの生成回毎に、与えられた全変数集合を構成する変数の順序をランダムに設定するステップと、ランダムに設定された変数から成る全変数集合に対してグラフを生成するステップと、生成回毎に変数間の関係性を表すようにそれぞれ生成されるいずれかのグラフに存在するすべてのエッジを含む包括グラフを出力するステップとを有するように構成したので、標本データ数の不足やデータ観測の際に生じるノイズ等に起因して変数間の関係性を表すグラフを一義的に特定できない場合でも、各回に生成されたグラフを包括的に表現できるグラフを得ることができ、変数間の関係性についてユーザが誤った認識を有することを防止することができるという効果を奏する。
【００３６】
本願発明によれば、所定の生成数だけ生成される複数のグラフから成るグラフ集合においてそれぞれのエッジがグラフ内に存在する累計数をグラフの生成数で割ることで得られる存在確率を計算するステップを有し、出力される包括グラフにおいて、存在するそれぞれのエッジについて対応する存在確率が示されるように構成したので、変数間の関係性をより正確に把握することができるという効果を奏する。
【００３７】
本願発明によれば、各エッジについて、少なくとも、無向エッジの累計数、第１の方向を向く矢線の累計数および第１の方向と反対の第２の方向を向く矢線の累計数を計算するステップと、各エッジについて、無向エッジの累計数、第１の方向を向く矢線の累計数および第２の方向を向く矢線の累計数をグラフの生成数で割ることで得られるそれぞれのエッジ種類に対応する存在確率を計算するステップとを有し、出力される包括グラフにおいて、存在確率の最も大きな種類のエッジおよび当該種類のエッジの存在確率が示されるように構成したので、変数間の関係性の種類の詳細をより正確に把握することができるという効果を奏する。
【００３８】
本願発明によれば、変数間の関係性を表す包括グラフにおいて存在確率が０より大きいエッジが全て表示手段に表示されるように構成したので、存在確率の小さなエッジをも含めた包括的なグラフがユーザに対して提示されるから、変数間の関係性についてユーザが誤った認識を有することを防止することができるという効果を奏する。
【００３９】
本願発明によれば、表示手段においてエッジに存在確率が付記して表示されるように構成したので、データマイニングを実施するユーザが変数間の関係性を容易かつ正確に把握することができるという効果を奏する。
【００４０】
本願発明によれば、表示手段において存在確率に応じてエッジの太さまたはエッジの色が変化して表示されるように構成したので、データマイニングを実施するユーザが変数間の関係性をより直感的に把握することができるという効果を奏する。
【発明を実施するための最良の形態】
【００４１】
以下、添付の図面を参照して本願発明に係る実施の形態を説明する。
実施の形態１．
図６は、この発明の実施の形態１によるグラフ生成方法のアルゴリズムを示すフローチャートである。本願発明では、非巡回的有向独立グラフを復元する手法を用いて、観測項目の状態を指標する変数間の関係性を表すグラフを生成することを特徴とする。図５に示されるように、変数間の関係性を表すグラフは、最終的に部分無向グラフとなることもある。そこで、以下の説明においては、非巡回的有向独立グラフを復元する手法を用いて最終的に得られ、変数間の関係性を表すグラフを関係グラフと称するものとする。この関係グラフには、非巡回的有向独立グラフおよび部分無向グラフが含まれることは、自明であろう。図６に示されるグラフ生成方法は、グラフをユーザによって設定された所定数Ｎだけ生成して、生成されたＮ個の関係グラフからエッジの存在確率を求めて、エッジ毎の存在確率を付記した包括グラフを出力するようにしたものである。Ｖ＝｛Ｘ１，Ｘ２，・・・，Ｘｐ｝とする全変数集合が与えられれば、全変数集合Ｖを構成する変数に係るすべての変数対（Ｘｉ，Ｘｊ）について、ノードＸｉとノードＸｊとの間のエッジＥｉｊに係るカウント数の初期値として０を設定する（ステップＳ１）。
【００４２】
次に、ＰＣアルゴリズムを用いた復元処理により生成する関係グラフの個数Ｎを設定する（ステップＳ２）。グラフの生成数Ｎが設定されれば、グラフの生成回数を示すｋの初期値として０を設定する（ステップＳ３）。次に、各回における関係グラフの生成工程に移行して、まずｋの値を１だけ増分する（ステップＳ４）。グラフの生成回数ｋが確定すれば、第ｋ回の関係グラフを生成するために、全変数集合Ｖを構成するＸｉ（ｉ＝１〜ｐ）の順序をランダムに設定する（ステップＳ５）。図１の例であれば、Ｖ＝｛Ｘ１，Ｘ２，Ｘ３，Ｘ４，Ｘ５｝として全変数集合が与えられる。後述する関係グラフの復元処理においては、全変数集合における各変数の順序に応じて、条件付き独立判定の対象となる（Ｘｉ，Ｘｊ）と部分集合Ｓとの組合せの順序が異なることとなる。先の組合せで判定される条件付き独立の存否が、後の組合せで判定される条件付き独立の存否に影響を与えることが知られている。したがって、全変数集合Ｖを構成する変数Ｘの順序が、復元される関係グラフの形態に影響を及ぼすことになる。ステップＳ５では、関係グラフの復元に係るこのような性質に鑑みて、変数Ｘｉ（ｉ＝１〜ｐ）の順序をランダムに設定するものである。例えば、ランダム変数等を用いることで、Ｖ＝｛Ｘ３，Ｘ１，Ｘ４，Ｘ５，Ｘ２｝といった順序形態を有する全変数集合Ｖが、ＰＣアルゴリズムを用いた非巡回的有向独立グラフの復元処理の対象として設定される。
【００４３】
全変数集合Ｖが与えられれば、ＰＣアルゴリズムを用いて、関係グラフの復元処理を実行する（ステップＳ６）。なお、この復元処理の詳細については後述する。ステップＳ６における処理により、関係グラフが復元されれば、復元された関係グラフに存在するそれぞれのエッジＥｉｊについて、当該Ｅｉｊに係るカウント数を１だけ増分する（ステップＳ７）。以上で第ｋ回の関係グラフの復元は完了するので、生成回数ｋがＮに等しいか否かを判定する（ステップＳ８）。生成回数ｋがＮに等しくないと判定された場合には、Ｎ個の関係グラフが未だ生成されていないことを意味するから、処理をステップＳ４に移行して次回のグラフ復元処理を実行する。
【００４４】
ステップＳ８において、生成回数ｋがＮに等しいと判定された場合には、それぞれのエッジＥｉｊに係るカウント数をグラフの生成数Ｎで割る（ステップＳ９）。カウント数をＮで割った値Ｃｉｊは、それぞれのエッジＥｉｊの存在確率を示す。例えば、Ｖ＝｛Ｘ１，Ｘ２，Ｘ３，Ｘ４，Ｘ５｝として与えられる全変数集合Ｖについて、生成数Ｎ＝１０として１０回にわたって非巡回的有向独立グラフを生成したとする。この結果、「Ｘ１→Ｘ３」のカウント数が１０回、「Ｘ２→Ｘ３」のカウント数が９回、「Ｘ１−Ｘ４」のカウント数が５回、「Ｘ３→Ｘ５」のカウント数が１０回、「Ｘ４→Ｘ５」のカウント数が８回であったとする。この場合、「Ｘ１→Ｘ３」の存在確率は１．０、「Ｘ２→Ｘ３」の存在確率は０．９、「Ｘ１−Ｘ４」の存在確率は０．５、「Ｘ３→Ｘ５」の存在確率は１．０、「Ｘ４→Ｘ５」の存在確率は０．８となる。
【００４５】
それぞれのエッジＥｉｊに係る存在確率が求められれば、当該存在確率を対応するエッジに付記した包括グラフを出力する。図７は、各エッジの存在確率を付記した包括グラフの例を示す図である。図７に示される部分無向グラフには、上述した例により求められた存在確率が、エッジの概ね中間位置において丸印により囲まれて示されている。このように全変数集合を構成する変数の順序をランダムに設定して複数回にわたって関係グラフを復元することにより、標本データ数の不足やデータ観測の際に生じるノイズ等に起因して関係グラフを一義的に特定できない場合でも、各回に生成された関係グラフを包括的に表現できる包括グラフを得ることができるという効果を奏する。また、包括グラフに存在するそれぞれのエッジについて存在確率を付記するようにしたので、変数間の関係性をより正確に把握することが可能になるという効果を奏する。なお、関係グラフを複数回生成する際にエッジＥｉｊとして異なる種類のエッジが出現した場合には、出力される包括グラフにおいて最も多く出現した種類のエッジによりノードＸｉとノードＸｊとを結ぶものとする。
【００４６】
上記の実施例では、エッジＥｉｊについて、エッジの種類に関係なく各回に生成された関係グラフにおいて当該エッジが存在する場合にカウント数を１ずつ増分する構成とした。ノードＸｉとノードＸｊとを結ぶエッジの種類には、「Ｘｉ−Ｘｊ」で示される無向エッジ、「Ｘｉ→Ｘｊ」で示される第１の向きを持つ矢線、「Ｘｉ←Ｘｊ」で示される第１の向きと反対の第２の向きを持つ矢線がある。さらに、特定の態様において形成される有向グラフにおいては、「Ｘｉ←→Ｘｊ」で示されるように、第１および第２の両方の向きを有する矢線がある。そこで、エッジの種類毎にカウント数を設定するような構成としてもよい。この場合、最終的には、エッジの種類毎のカウント数を比較して、最も大きなカウント数を有する種類のエッジをグラフ上に表示するとともに、当該種類のカウント数を生成数Ｎで割った存在確率をエッジに付記するものとする。例えば、グラフの生成数が１０の場合において、ノードＸｉとノードＸｊとを結ぶエッジＥｉｊについて、無向エッジの存在を示すカウント数が７であり、第１の向きを持つ矢線の存在を示すカウント数が３であれば、ノードＸｉとノードＸｊとは無向エッジで結ばれ、その存在確率は０．７となる。上記のように出力される包括グラフにおいて存在確率の最も大きな種類のエッジおよび当該種類に係る存在確率が示されることで、変数間の関係性の種類の詳細をより正確に把握することが可能となる。
【００４７】
次に、上述したステップ６における関係グラフの復元処理について説明する。図８は、関係グラフの復元処理アルゴリズムを示すフローチャートである。ランダムに順序が設定された全変数集合Ｖが与えられれば、復元される関係グラフの初期グラフとして、完全無向グラフを設定する（ステップＳ２１）。この完全無向グラフは、全変数集合Ｖを構成するすべての変数対（Ｘｉ，Ｘｊ）について、ノードＸｉとノードＸｊとを無向エッジで結ぶことにより構成される。初期グラフが設定されれば、所定の要件を満たす変数対（Ｘｉ，Ｘｊ）に係る条件付き独立判定を実行して、条件付き独立であると判定された場合には、ノードＸｉとノードＸｊとの間のエッジＥｉｊを削除する（ステップＳ２２）。なお、条件付き独立判定に基づくエッジの削除処理の詳細については後述する。
【００４８】
条件付き独立判定に基づくエッジの削除処理が完了すれば、Ｖ字合流に係る判定を実行して、Ｖ字合流が確認された構造については、ノード間のエッジを矢線に変更する（ステップＳ２３）。具体的には、例えば図４に示されるように条件付き独立判定に基づくエッジの削除処理が完了したグラフにおいて、Ｘｉ−Ｘｊ−Ｘｋという構造（ＸｉとＸｋとは隣接していない）があり、条件付き独立判定処理で用いられたＳｅｐｓｅｔ（Ｘｉ，Ｘｋ）の要素にＸｊがない場合には、この道がＶ字合流であると判定されて、Ｘｉ→Ｘｊ←Ｘｋと矢印を付ける。
【００４９】
Ｖ字合流の確認処理が完了すれば、オリエンテーションルールのルール１を適用して、ルール１に基づいてノード間の無向エッジを矢線に変更する（ステップＳ２４）。具体的には、例えば図５に示されるようにＶ字合流の確認に基づく矢線変更処理が完了したグラフにおいて、Ｘｉ→Ｘｊ−Ｘｋという構造（ＸｉとＸｋとは隣接しない）がある場合には、変数Ｘｊと変数Ｘｋとの間の無向エッジを矢線に変更して、Ｘｉ→Ｘｊ→Ｘｋとする。
【００５０】
オリエンテーションルールのルール１の適用による矢線変更処理が完了すれば、オリエンテーションルールのルール２を適用して、ルール２に基づいてノード間の無向エッジを矢線に変更する（ステップＳ２５）。具体的には、ステップＳ２４の処理を完了したグラフにおいて、Ｘｉ−ＸｋかつＸｉ→Ｘｊ→Ｘｋがある場合には、変数Ｘｉと変数Ｘｋとの間の無向エッジを矢線に変更して、Ｘｉ→Ｘｋとする。
【００５１】
次に、上述したステップＳ２２における条件付き独立判定に基づくエッジの削除処理について説明する。図９および図１０は、条件付き独立判定に基づくエッジの削除処理アルゴリズムを示すフローチャートである。図９に記載された符号Ａ，Ｂ，Ｃ，Ｄ，ＥおよびＦは、図１０に記載された符号Ａ，Ｂ，Ｃ，Ｄ，ＥおよびＦに合致するものであり、これらの符号により図９に記載されたフローチャートと図１０に記載されたフローチャートとは接続される。関係グラフの初期グラフとして完全無向グラフが設定されれば、条件付き独立判定の段階数を示す変数ｎの初期値として０を設定する（ステップＳ４１）。なお、以下の説明では完全無向グラフからエッジを削除していくことで生成されるグラフをグラフＣと表すものとする。
【００５２】
ｎの値が設定されれば、グラフＣのなかからＡｄ（Ｃ，Ｘ）の要素数がｎ＋１以上である変数Ｘを逐次的に抽出して、この条件を満たす変数Ｘの変数セットを設定する（ステップＳ４２）。なお、上述したように条件付き独立の判定に係る演算には変数の順序が影響を及ぼすので、この変数セット内の変数Ｘの順序は、ステップＳ５において設定された全変数集合における各変数の順序に整合させるものとする。変数セットが設定されれば、変数セット内の順序に応じて１つずつ変数を取り出して、条件付き独立判定の対象となる変数Ｘｉを特定する（ステップＳ４３）。
【００５３】
条件付き独立判定の対象となる変数Ｘｉが特定されれば、Ａｄ（Ｃ，Ｘｉ）の要素となる変数Ｘから成る変数セットを設定する（ステップＳ４４）。なお、この変数セット内の変数Ｘの順序についても、ステップＳ５において設定された全変数集合における各変数の順序に整合させるものとする。変数セットが設定されれば、変数セット内の順序に応じて１つずつ変数を取り出して、条件付き独立判定の対象となる変数Ｘｊを特定する（ステップＳ４５）。
【００５４】
条件付き独立判定の対象となる変数Ｘｊが特定されれば、Ａｄ（Ｃ，Ｘｉ）￥｛Ｘｊ｝の要素から成る集合で要素数がｎのものから成る部分集合を逐次的に抽出して、１または複数の部分集合から成る集合セットを設定する（ステップＳ４６）。この集合セットが設定されれば、当該集合セットのなかから、条件付き独立判定に用いられる部分集合Ｓを特定する（ステップＳ４７）。
【００５５】
条件付き独立判定の対象となる変数Ｘｉおよび変数Ｘｊ並びに条件付き独立判定に用いられる部分集合Ｓが特定されれば、変数Ｘｉ、変数Ｘｊおよび部分集合Ｓから成る変数列を対象として相関係数行列の逆行列を計算する。当該逆行列において変数Ｘｉに係る対角要素をＲｉｉと表し、変数Ｘｊに係る対角要素をＲｊｊと表す。ここで、変数Ｘｉおよび変数Ｘｊに係る多重共線性を評価する尺度としてＶＩＦ（Ｖａｒｉａｎｃｅ  Ｉｎｆｌａｔｉｏｎ  Ｆａｃｔｏｒ）という指標を導入する。変数Ｘｉに係るＶＩＦ（Ｘｉ）はＲｉｉに等しく、変数Ｘｊに係るＶＩＦ（Ｘｊ）はＲｊｊに等しい。ＶＩＦ（Ｘｉ）の値が所定の閾値Ｔｈより大きい場合、あるいはＶＩＦ（Ｘｊ）の値が所定の閾値Ｔｈより大きい場合には、Ｘｉ，Ｘｊ，Ｓにおける多重共線性が高い、すなわちＸｉ，Ｘｊ，Ｓ間に強い線形関係が存在するものと判定される。ここでは、Ｘｉ，Ｘｊ，Ｓから成る変数列において、ＶＩＦ（Ｘｉ）＞ＴｈまたはＶＩＦ（Ｘｊ）＞Ｔｈが成立するか否かを判定する（ステップＳ４８）。
【００５６】
ステップＳ４８において、ＶＩＦ（Ｘｉ）＞ＴｈまたはＶＩＦ（Ｘｊ）＞Ｔｈが成立する場合には、ノードＸｉとノードＸｊとの間のエッジＥｉｊをロックする。すなわち、上述したように、Ｘｉ，Ｘｊ，Ｓ間の多重共線性が高い場合には、変数Ｘｉと変数Ｘｊとの条件付き独立を判定するための偏相関係数行列の演算でエラーが生じる可能性が高く、エラーに起因する演算の中断や中止を回避するために、変数Ｘｉと変数Ｘｊとを対象とした条件付き独立判定に係る全ての演算を省略して、処理をステップＳ４５に移行する。
【００５７】
ステップＳ４８において、ＶＩＦ（Ｘｉ）＞ＴｈまたはＶＩＦ（Ｘｊ）＞Ｔｈが成立しない場合には、部分集合Ｓが与えられたときに変数Ｘｉと変数Ｘｊとが条件付き独立となるか否かを判定する（ステップＳ４９）。具体的には、変数Ｘｉおよび変数Ｘｊ並びに部分集合Ｓから成る変数列において、偏相関係数Ｐｉｊを算出する。偏相関係数Ｐｉｊが求められれば、統計的仮説検定を用いて、帰無仮説Ｈｏ：Ｐｉｊ｜ｐａ＝０（部分集合Ｓが与えられる条件をｐａで表現する）を棄却できるか否かを判定する。帰無仮説Ｈｏを棄却できない場合には、Ｐｉｊ｜ｐａ＝０とみなして、部分集合Ｓが与えられたときに変数Ｘｉと変数Ｘｊとは条件付き独立であると判定する。
【００５８】
ステップＳ４９において、変数Ｘｉと変数Ｘｊとが条件付き独立であると判定された場合には、ノードＸｉとノードＸｊとの間のエッジＥｉｊをグラフＣから削除する（ステップＳ５０）。また、Ｓｅｐｓｅｔ（Ｘｉ，Ｘｊ）の要素として部分集合Ｓを登録する（ステップＳ５１）とともに、Ｓｅｐｓｅｔ（Ｘｊ，Ｘｉ）の要素として部分集合Ｓを登録する（ステップＳ５２）。ステップＳ５０における処理によりノードＸｉとノードＸｊとの間のエッジＥｉｊは削除されたので、これ以上変数Ｘｉと変数Ｘｊとの条件付き独立についての演算を実行する必要はなくなるから、ステップＳ５２の処理が完了すれば、処理をステップＳ４５に移行する。
【００５９】
ステップＳ４９において、変数Ｘｉと変数Ｘｊとが条件付き独立ではないと判定された場合には、ステップＳ４６において定義された要件を満たす集合セットを構成するすべての部分集合Ｓについて条件付き独立判定が完了したか否かを判定する（ステップＳ５３）。すべての部分集合Ｓについて条件付き独立判定が為されていないと判定された場合には、処理をステップＳ４７に移行して、新たな部分集合Ｓを特定する。
【００６０】
ステップＳ５３において、集合セットに含まれるすべての部分集合Ｓについて条件付き独立判定が完了したと判定されれば、ステップＳ４４において定義された要件を満たす変数セットを構成するすべての変数Ｘｊについて条件付き独立判定が完了したか否かを判定する（ステップＳ５４）。すべての変数Ｘｊについて条件付き独立判定が為されていないと判定された場合には、処理をステップＳ４５に移行して、新たな変数Ｘｊを特定する。
【００６１】
ステップＳ５４において、変数セットに含まれるすべての変数Ｘｊについて条件付き独立判定が完了したと判定されれば、ステップＳ４２において定義された要件を満たす変数セットを構成するすべての変数Ｘｉについて条件付き独立判定が完了したか否かを判定する（ステップＳ５５）。すべての変数Ｘｉについて条件付き独立判定が為されていないと判定された場合には、処理をステップＳ４３に移行して、新たな変数Ｘｉを特定する。
【００６２】
ステップＳ５５において、変数セットに含まれるすべての変数Ｘｉについて条件付き独立判定が完了したと判定されれば、条件付き独立判定の段階数を示す変数ｎを１増分する（ステップＳ５６）。次に、Ａｄ（Ｃ，Ｘ）の要素数がｎ＋１以上である変数ＸがグラフＣにおいて存在するか否かを判定する（ステップＳ５７）。当該要件を満たす変数Ｘが存在する場合には、処理をステップＳ４２に移行して、当該要件を満たす変数Ｘの新たな変数セットを設定する。当該要件を満たす変数Ｘが存在しない場合には、条件付き独立判定に基づくエッジの削除処理を終了する。
【００６３】
上記の条件付き独立判定に基づくエッジの削除処理においては、条件付き独立判定の対象となる変数Ｘｉおよび変数Ｘｊ並びに条件付き独立判定に用いられる変数の部分集合Ｓから成る変数列についての相関係数行列の逆行列を計算して、当該逆行列の変数Ｘｉに係る対角要素Ｒｉｉが所定の閾値Ｔｈより大きいか、あるいは当該逆行列の変数Ｘｊに係る対角要素Ｒｊｊが所定の閾値Ｔｈより大きい場合には、変数Ｘｉと変数Ｘｊとの条件付き独立を判定するための演算処理を省略するように構成したので、エラーに起因する演算の中断や中止を回避することが可能となり、関係グラフを高い確率で得ることができるという効果を奏する。
【００６４】
図１１は、本願発明に係るグラフ生成プログラムを用いてデータマイニングを実施するシステムの構成の例を示す図である。図１１において、１はグラフ生成に係る各種の演算を実行するとともにシステムの構成要素を制御する演算制御部（ＣＰＵ）、２はグラフ生成プログラムのロード領域としてまた演算処理用のワークスペース等として使用されるＲＡＭ、３はグラフ生成プログラムや観測データ等が記憶される例えばＨＤＤとして与えられる大容量記憶装置、４はＣＤ、ＤＶＤ等の可搬性のある記憶媒体から観測データ等の各種データを読み込むためのディスク読み取り装置、５はインターネット等の通信ネットワークに接続されて各種データを送受信する通信制御部、６はグラフの生成数や観測データ等の各種情報を入力するためのキーボード、７はコマンド等の各種情報を入力するためのマウス、８は初期設定となる完全無向グラフや存在確率が付記された包括グラフ等を表示するディスプレイである。
【００６５】
図１１に示されたシステムは、例えばパーソナルコンピュータやワークステーションとして実現することが可能である。図６および図８〜図１０に記載されたフローチャートに表されたアルゴリズムを実現するプログラムは、例えば大容量記憶装置３に格納され、実行時にＲＡＭ２にロードされる。また、大容量記憶装置３には、各種の観測データを体系化したデータマイニング用データベースが構築されるのが好適である。これらの観測データについては、ディスク読み取り装置４を用いてＣＤ、ＤＶＤ等の可搬性記憶媒体から読み取るか、あるいは通信制御部５を用いてネットワークに接続されるサーバ等から受信するか、あるいはキーボード６を用いてデータ入力すること等により、大容量記憶装置３内に格納する。また、本願発明に係るグラフ生成方法を用いて得られた包括グラフは、ディスプレイ８上に表示される。この際、図７に示されるように、各エッジの存在確率を付記してグラフを表示するのが好適である。なお、エッジの存在確率については、必ずしも数字で表現する必要はない。例えば、存在確率をエッジの太さやエッジの色などで表現するような構成としてもよい。
【００６６】
本願発明に係るデータマイニングシステムは上記のように、ディスプレイ上において、各エッジの存在確率を付記してグラフを表示するように構成したので、データマイニングを実施するユーザが、変数間の関係性を容易かつ正確に把握することが可能になるという効果を奏する。また、各エッジの存在確率をエッジの太さやエッジの色で表現するように構成すれば、データマイニングを実施するユーザが、変数間の関係性をより直感的に把握することが可能になるという効果を奏する。
【００６７】
なお、上記の実施の形態により説明されるグラフ生成方法、グラフ生成プログラム並びにデータマイニングシステムは、本願発明を限定するものではなく、例示することを意図して開示されているものである。本願発明の技術的範囲は特許請求の範囲の記載により定められるものであり、特許請求の範囲に記載された技術的範囲内において種々の設計的変更が可能である。例えば、上記の実施の形態においては、非巡回的有向独立グラフを復元するアルゴリズムとしてＰＣアルゴリズムを用いているが、特許請求の範囲に記載された手続きにより表される非巡回的有向独立グラフの復元手法を適用したグラフ生成方法の範疇に含まれる種々のアルゴリズム、例えばＳＧＳアルゴリズムを用いる構成としてもよい。
【産業上の利用可能性】
【００６８】
本願発明は、各種の観測データを基にして観測項目間の関係性を発見、検証等するためのデータマイニングシステムに広く適用できるものである。
【図面の簡単な説明】
【００６９】
【図１】非巡回的有向独立グラフの一例を示す図である。
【図２】偏回帰係数が付記された非巡回的有向独立グラフの一例を示す図である。
【図３】オリエンテーションルールを示す図である。
【図４】非巡回的有向独立グラフが生成される過程で生成される無向グラフの一例を示す図である。
【図５】非巡回的有向独立グラフが生成される過程で生成される部分無向グラフの一例を示す図である。
【図６】実施の形態１によるグラフ生成方法のアルゴリズムを示すフローチャートである。
【図７】各エッジの存在確率を付記した包括グラフの一例を示す図である。
【図８】関係グラフの復元処理アルゴリズムを示すフローチャートである。
【図９】条件付き独立判定に基づくエッジの削除処理アルゴリズムを示すフローチャートである。
【図１０】条件付き独立判定に基づくエッジの削除処理アルゴリズムを示すフローチャートである。
【図１１】本願発明に係るグラフ生成方法を用いてデータマイニングを実施するシステムの構成の例を示す図である。
【符号の説明】
【００７０】
１  演算制御部、２  ＲＡＭ、３  大容量記憶装置、４  ディスク読み取り装置、５  通信制御部、６  キーボード、７  マウス、８  ディスプレイ
【図１】
2007207101.tif 000005
【図２】
2007207101.tif 000006
【図３】
2007207101.tif 000007
【図４】
2007207101.tif 000008
【図５】
2007207101.tif 000009
【図６】
2007207101.tif 000010
【図７】
2007207101.tif 000011
【図８】
2007207101.tif 000012
【図９】
2007207101.tif 000013
【図１０】
2007207101.tif 000014
【図１１】
2007207101.tif 000015