(57)【特許請求の範囲】
【請求項１】
事象の履歴を格納したデータベースと、該データベースに格納されているデータから因果関係を検出するコンピュータとを備えた因果関係検出装置において、前記コンピュータが、
前記データベースに格納されている事象の時系列データを取り出し、発生時刻順に事象をソートした事象リストを生成するソート処理部と、
該ソート処理部から出力される事象リストを記憶する主記憶部と、
該主記憶部に記憶されている事象リストを読出し、第１の事象の集合の発生時刻から、あらかじめ定めた時間が経過するまでに第２の事象の集合が起こるような事象集合対の出現回数、並びに第１の事象の集合及び第２の事象の集合の出現回数を該事象リストから求める頻度処理部と、
該頻度処理部から出力される前記事象集合対の前記出現回数及び前記各事象集合の前記出現回数を用いて、第１の事象の集合が原因となって前記あらかじめ定めた時間内に第２の事象の集合が起こる因果関係の有意性を判定する因果性判定処理部とを有することを特徴とする因果関係検出装置。
【請求項２】
前記頻度処理部は、前記第１の事象の集合の発生した時刻と第２の事象の集合の発生した時刻との中間の時刻において、該第１及び第２の事象の集合のいずれの事象も発生していない場合に、前記出現回数を求めるように構成されていることを特徴とする請求項１に記載の装置。
【請求項３】
前記因果性判定処理部は、各事象集合対に対し、因果関係があると仮定するモデルと因果関係がないとするモデルとの双方に対し、モデルの対数尤度及びモデルに使用するパラメータ数から求めた情報量基準の値をそれぞれ算出し、該算出した情報量基準の値の比較から因果関係の有意性判定を行うように構成されていることを特徴とする請求項１又は２に記載の装置。
【請求項４】
前記因果性判定処理部は、因果関係があると仮定した時の情報量基準の値が因果関係がないと仮定した時の情報量基準の値より小さい場合に、因果関係が有意であると判定するように構成されていることを特徴とする請求項１から３のいずれか１項に記載の装置。
【請求項５】
前記ソート処理部は、生成した事象リストの一部分であるローカルリストを求め、該ローカルリストを時間的に逆順に順次更新して事象リストを提供するように構成されていることを特徴とする請求項１から４のいずれか１項に記載の装置。
【請求項６】
前記頻度処理部は、時刻ｔｉ（ｉは０以上の整数である）で発生する第１の事象集合Ｘ（＝｛ｅｘ１，ｅｘ２，…，ｅｘｎ，…｝、ｅｘｎは事象を示し、ｎは自然数である）と、時刻ｔｋ（ｔｉ＜ｔｋ＜ｔｉ＋ｗ、ｉ，ｋは０以上の整数であり、ｗは前記あらかじめ定めた時間である） に発生する第２の事象集合Ｙ（＝｛ｅｙ１，ｅｙ２，…，ｅｙｎ，…｝、ｅｙｎは事象を示し、ｎは自然数である）とが、ｔｉ＜ｔｊ＜ｔｋ（ｊは０以上の整数である）を満たす任意の時刻ｔｊで発生する第３の事象集合Ｚ（＝｛ｅｚ１，ｅｚ２，…，ｅｚｎ，…｝、ｅｚｎは事象を示し、ｎは自然数である）について、∀ｅｘ∈Ｘ，ｅｙ∈Ｙ，ｅｚ∈Ｚ，ｅｘ≠ｅｚかつｅｙ≠ｅｚとなる順序条件を満たしている事象集合対〈Ｘ，Ｙ〉の事象リストにおける出現回数を求める際、前記ソート処理部によって更新された事象リストの一部分であるローカルリスト（時刻ｔｐ，ｔｐ＋１，…，ｔｍ（ｐ）（ｍ（ｐ）は自然数である）の事象のリスト、ｔｍ（ｐ）＜ｔｐ＋ｗ＜ｔｍ（ｐ）＋１）を参照して、時刻ｔｐ＋１から時刻ｔｑ（ｐ＜ｑ≦ｍ（ｐ））に発生する事象の集合ＮＢｑと、時刻tｐ＋１の任意の事象と時刻ｔｑ（ｐ＜ｑ＜ｍ（ｐ））の第４の事象集合Ｅ′（＝｛ｅｅ１，ｅｅ２，…，ｅｅｎ，…｝、ｅｅｎは事象を示し、ｎは自然数である）のうち前記順序条件を満たす事象の集合Ｈｑを更新することにより、事象集合対の出現回数を求めることを特徴とする請求項１から５のいずれか１項に記載の装置。
【請求項７】
事象の履歴を格納したデータベースと、該データベースに格納されているデータから因果関係を検出するコンピュータとを備えた因果関係検出装置において、前記コンピュータが、
前記データベースに格納されている事象の時系列データを取り出し、発生時刻順に事象をソートした事象リストを生成するソート処理部と、
該ソート処理部から出力される事象リストを記憶する主記憶部と、
該主記憶部に記憶されている事象リストを読出し、第１の事象の発生時刻から、あらかじめ定めた時間が経過するまでに第２の事象が起こるような事象対の出現回数、並びに第１の事象及び第２の事象の出現回数を該事象リストから求める頻度処理部と、
該頻度処理部から出力される前記事象対の前記出現回数及び前記各事象の前記出現回数を用いて、第１の事象が原因となって前記あらかじめ定めた時間内に第２の事象が起こる因果関係の有意性を判定する因果性判定処理部とを有することを特徴とする因果関係検出装置。
【請求項８】
前記頻度処理部は、前記第１の事象の発生した時刻と第２の事象の発生した時刻との中間の時刻において、該第１及び第２のいずれの事象も発生していない場合に、前記出現回数を求めるように構成されていることを特徴とする請求項７に記載の装置。
【請求項９】
前記因果性判定処理部は、各事象対に対し、因果関係があると仮定するモデルと因果関係がないとするモデルとの双方に対し、モデルの対数尤度及びモデルに使用するパラメータ数から求めた情報量基準の値をそれぞれ算出し、該算出した情報量基準の値の比較から因果関係の有意性判定を行うように構成されていることを特徴とする請求項７又は８に記載の装置。
【請求項１０】
前記因果性判定処理部は、因果関係があると仮定した時の情報量基準の値が因果関係がないと仮定した時の情報量基準の値より小さい場合に、因果関係が有意であると判定するように構成されていることを特徴とする請求項７から９のいずれか１項に記載の装置。
【請求項１１】
前記ソート処理部は、生成した事象リストの一部分であるローカルリストを求め、該ローカルリストを時間的に逆順に順次更新して事象リストを提供するように構成されていることを特徴とする請求項７から１０のいずれか１項に記載の装置。
【請求項１２】
前記頻度処理部は、時刻ｔｉ（ｉは０以上の整数である）で発生する第１の事象ｅｘと、時刻ｔｋ（ｔｉ＜ｔｋ＜ｔｉ＋ｗ、ｉ，ｋは０以上の整数であり、ｗは前記あらかじめ定めた時間である） に発生する第２の事象ｅｙが、ｔｉ＜ｔｊ＜ｔｋ（ｊは０以上の整数である）を満たす任意の時刻ｔｊで発生する第３の事象ｅｚについて、ｅｘ≠ｅｚかつｅｙ≠ｅｚとなる順序条件を満たしているような前記第１の事象ｅｘ 及び前記第２の事象ｅｙ の事象対〈ｅｘ ，ｅｙ 〉の事象リストにおける出現回数を求める際、前記ソート処理部によって更新された事象リストの一部分であるローカルリスト（時刻ｔｐ，ｔｐ＋１，…，ｔｍ（ｐ）（ｍ（ｐ）は自然数である）の事象のリスト、ｔｍ（ｐ）＜ｔｐ＋ｗ＜ｔｍ（ｐ）＋１）を参照して、時刻ｔｐ＋１から時刻ｔｑ（ｐ＜ｑ≦ｍ（ｐ））に発生する事象の集合ＮＢｑと、時刻tｐ＋１の任意の事象と時刻ｔｑ（ｐ＜ｑ＜ｍ（ｐ））の第４の事象ｅｅのうち前記順序条件を満たす事象の集合Ｈｑを更新することにより、事象対の出現回数を求めることを特徴とする請求項７から１１のいずれか１項に記載の装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、データベースから役に立つ情報を発見するデータマイニングにおける因果関係検出装置に関し、特に事象の履歴から原因となる事象と結果となる事象との組を自動的に検出するようにした因果関係検出装置に関する。本発明は、例えば、システムのログから障害原因を推定したり、障害を予測したりする障害管理や、販売促進等の分野において外的要因と各商品の売り上げ高との因果関係の推定に用いられる。
【０００２】
【従来の技術】
事象の履歴を記録したデータベースから因果関係を発見する問題の基本となる技術として、Ｒ．Ａｇｒａｗａｌ及びＲ．Ｓｒｉｋａｎｔによる文献、「Ｆａｓｔ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｍｉｎｉｎｇ  Ａｓｓｏｓｉａｔｉｏｎ  Ｒｕｌｅｓ」、２０ｔｈ  ＶＬＤＢ、ｐｐ．４８７−４９９、１９９４で提案されている相関ルールの発見問題がある。
【０００３】
この公知の相関ルール発見のアルゴリズムは、各トランザクションがいくつかのアイテムの集合で構成されているデータベースから、あらかじめ定められたしきい値（ｍｉｎｓｕｐ）以上のサポートをもつアイテム集合をまず生成し、生成したアイテム集合の中からあらかじめ定められたしきい値（ｍｉｎｃｏｎｆ）以上の確信度をもつ相関ルールを生成するものである。
【０００４】
ここで、Ｘ及びＹをアイテム集合としたときの相関ルールＸ⇒Ｙのサポート及び確信度は、以下のように定義される。
0003721735.tif 000002
【０００５】
以下にこのアイテム集合の生成のアルゴリズムを示す。
0003721735.tif 000003
【０００６】
このアルゴリズムは、しきい値ｍｉｎｓｕｐ以上のサポートをもつアイテム集合を生成するアルゴリズムであり、ここでＬk は、サポートのしきい値ｍｉｎｓｕｐを有するｋ個のアイテムのアイテム集合（ｋ−ｉｔｅｍｓｅｔｓ）の集合を意味しており、Ｃk はｋ個のアイテムのアイテム集合候補（ｃａｎｄｉｄａｔｅｋ−ｉｔｅｍｓｅｔｓ）の集合を意味している。各集合における各アイテム集合は、アイテム集合とサポートとの２つのフィールドを備えている。
【０００７】
上述したアルゴリズムでは、まず、全てのアイテムに対し、単一アイテムだけからなるアイテム集合をＬ1 として設定する。次に、以下のように順次ｋをインクリメントしながら、ｋ個のアイテムからなるアイテム集合の候補の集合Ｃk を生成し、データベースＤ中の各トランザクションｔｒに対して、ｔｒの中に集合Ｃk 中の候補を含むような候補の集合Ｃtrを得て、集合Ｃtrに含まれる各候補ｃに対して、候補ｃの出現回数の記録をインクリメントする。そして、全てのトランザクションについての処理が終わったら、集合Ｃk の内出現回数の記録がしきい値ｍｉｎｓｕｐ以上であるような候補の集合をＬk として設定する。この集合Ｌk が空集合なら集合Ｌ1 から集合Ｌk の和集合が生成すべきアイテムの集合となる。
【０００８】
次に示すアルゴリズムは、アイテム集合を生成する上述したアルゴリズムを用いて得たアイテム集合から、しきい値ｍｉｎｃｏｎｆ以上の確信度をもつ相関ルールを生成するアルゴリズムである。
【０００９】
0003721735.tif 000004
【００１０】
このアルゴリズムでは、生成した各アイテム集合Ｉに対しその部分集合Ｊをとりだし、相関ルール「Ｉ−Ｊ⇒Ｊ」の確信度がそのしきい値ｍｉｎｃｏｎｆ以上であれば出力する。
【００１１】
【発明が解決しようとする課題】
このような従来の相関ルール発見のアルゴリズムによれば、１つのトランザクション内でのアイテムの共起関係を検出することはできるが、異なるトランザクション間でのアイテムの共起関係を検出することができず、あるトランザクションに含まれる事象が別のトランザクションで発生する事象の原因となっていることを検出できない。
【００１２】
事象同士の共起性を検出するためには事象対の頻度計算を行う必要があるが、異なるトランザクションに含まれる事象同士の共起性を検出するべく出現する全ての事象から事象対を構成して頻度計算を行うと、事象の組み合わせ数が爆発的に増大してしまう。
【００１３】
また、従来のアルゴリズムでは、ｍｉｎｃｏｎｆというルールの信頼性に関わるしきい値の設定が必要である。このしきい値ｍｉｎｃｏｎｆは、実用的には、データベースの内容を考慮して経験的に設定する必要があり、そのためには経験を積んだオペレータが必要とされる。
【００１４】
従って本発明は、従来検出できなかった、異なるトランザクション間の共起性から因果関係を検出可能な因果関係検出装置を提供することを目的としている。
【００１５】
本発明の他の目的は、そのために必要な事象対の効率良い頻度計算が行え、しかも因果関係の信頼性に関わるしきい値を不要とする因果関係検出装置を提供することにある。
【００１６】
【課題を解決するための手段】
本発明によれば、事象の履歴を格納したデータベースと、このデータベースに格納されているデータから因果関係を検出するコンピュータとを備えた因果関係検出装置において、コンピュータが、データベースに格納されている事象の時系列データを取り出し、発生時刻順に事象をソートした事象リストを生成するソート処理部と、ソート処理部から出力される事象リストを記憶する主記憶部と、主記憶部に記憶されている事象リストを読出し、第１の事象の集合Ｘ（＝｛ｅｘ１，ｅｘ２，…，ｅｘｎ，…｝、ｅｘｎは事象を示し、ｎは自然数である）の発生時刻から、あらかじめ定めた時間（ウインドウサイズｗ）が経過するまでに第２の事象の集合Ｙ（＝｛ｅｙ１，ｅｙ２，…，ｅｙｎ，…｝、ｅｙｎは事象を示し、ｎは自然数である）が起こるような共起関係を持つ事象集合対〈Ｘ、Ｙ〉の出現回数、並びに第１の事象の集合Ｘ及び第２の事象の集合Ｙの出現回数を事象リストから求める頻度処理部と、頻度処理部から出力される事象集合対〈Ｘ、Ｙ〉の出現回数及び各事象集合Ｘ、Ｙの出現回数を用いて、第１の事象の集合Ｘが原因となってウインドウサイズｗ内に第２の事象の集合Ｙが起こる因果関係の有意性を判定する因果性判定処理部とを有する因果関係検出装置が提供される。
【００１７】
本発明によれば、さらに、事象の履歴を格納したデータベースと、このデータベースに格納されているデータから因果関係を検出するコンピュータとを備えた因果関係検出装置において、コンピュータが、データベースに格納されている事象の時系列データを取り出し、発生時刻順に事象をソートした事象リストを生成するソート処理部と、ソート処理部から出力される事象リストを記憶する主記憶部と、主記憶部に記憶されている事象リストを読出し、第１の事象ｅｘ の発生時刻から、あらかじめ定めた時間（ウインドウサイズｗ）が経過するまでに第２の事象ｅｙが起こるような共起関係を持つ事象対〈ｅｘ，ｅｙ〉の出現回数、並びに第１の事象ｅｘ及び第２の事象ｅｙの出現回数を事象リストから求める頻度処理部と、頻度処理部から出力される事象対〈ｅｘ，ｅｙ〉の出現回数及び各事象ｅｘ，ｅｙの出現回数を用いて、第１の事象ｅｘが原因となってウインドウサイズｗ内に第２の事象ｅｙが起こる因果関係の有意性を判定する因果性判定処理部とを有する因果関係検出装置が提供される。
【００２０】
第１の事象の集合Ｘ又は第１の事象ｅx の発生した時刻と第２の事象の集合Ｙ又は第２の事象ｅy の発生した時刻との中間の時刻において、第１及び第２の事象の集合Ｘ及びＹ又は第１及び第２の事象ｅx 及びｅy のいずれの事象も発生していない場合に、出現回数を求めるようにすることが好ましい。
【００２１】
各事象集合対〈Ｘ、Ｙ〉又は各事象対〈ｅx ，ｅy 〉に対し、因果関係があると仮定するモデルと因果関係がないとするモデルとの双方に対し、モデルの対数尤度及びモデルに使用するパラメータ数から求めた情報量基準の値をそれぞれ算出し、算出した情報量基準の値の比較から因果関係の有意性判定を行うことが好ましい。このように構成することによって、従来必要とされていた、因果関係ルールの信頼性の判定に必要なパラメータが不要となる。
【００２２】
その場合、因果関係があると仮定した時の情報量基準の値が因果関係がないと仮定した時の情報量基準の値より小さい場合に、因果関係が有意であると判定することが望ましい。
【００２３】
生成した事象リストの一部分であるローカルリストを求め、このローカルリストを時間的に逆順に順次更新して事象リストを提供することも好ましい。
【００２４】
時刻ｔi （ｉは０以上の整数である）で発生する第１の事象集合Ｘ（＝｛ｅx1，ｅx2，…，ｅxn，…｝、ｅxnは事象を示し、ｎは自然数である）又は第１の事象ｅx と、時刻ｔk （ｔi ＜ｔk ＜ｔi ＋ｗ、ｉ，ｋは０以上の整数であり、ｗは前記あらかじめ定めた時間である) に発生する第２の事象集合Ｙ（＝｛ｅy1，ｅy2，…，ｅyn，…｝、ｅynは事象を示し、ｎは自然数である）又は第２の事象ｅy とが、ｔi ＜ｔj ＜ｔk （ｊは０以上の整数である）を満たす任意の時刻ｔj で発生する第３の事象集合Ｚ（＝｛ｅz1，ｅz2，…，ｅzn，…｝、ｅznは事象を示し、ｎは自然数である）又は第３の事象ｅz について、∀ｅx ∈Ｘ，ｅy ∈Ｙ，ｅz ∈Ｚ，ｅx ≠ｅz かつｅy ≠ｅz となる順序条件を満たしている事象集合対〈Ｘ，Ｙ〉又は事象対〈ｅx ，ｅy 〉の事象リストにおける出現回数を求める際、事象リストの一部分であるローカルリスト（時刻ｔp ，ｔp+1 ，…，ｔm(p)（ｍ（ｐ）は自然数である）の事象のリスト、ｔm(p)＜ｔp ＋ｗ＜ｔm(p)+1）を更新しながら、時刻ｔp+1 から時刻ｔq （ｐ＜ｑ≦ｍ（ｐ））に発生する事象の集合ＮＢq と、時刻tp+1の任意の事象と時刻ｔq （ｐ＜ｑ＜ｍ（ｐ））の第４の事象集合Ｅ′（＝｛ｅe1，ｅe2，…，ｅen，…｝、ｅenは事象を示し、ｎは自然数である）又は第４の事象ｅe のうち上述の順序条件を満たす事象の集合Ｈq を更新することにより、事象集合対又は事象対の出現回数を求めることが好ましい。これによって、事象集合対又は事象対の出現回数を効率的に求めることができる。
【００２５】
【発明の実施の形態】
以下、本発明の一実施形態を図面を参照して説明する。
【００２６】
初めに、全ての事象の集合をＥ、最後の事象の生じた時刻をＴとする。ある時刻ｔi （０≦ｉ≦Ｔ）、又は時刻ｔi の前後の一定時間内に起こった事象の集合Ｅi ＝｛ｅi1，ｅi2，…｝（Ｅi ⊆Ｅ）をトランザクションとする。ただし、トランザクションを構成する事象の発生時刻に幅があったとしても、異なるトランザクションでは事象の発生時刻が重ならないとする。
【００２７】
原因が生じてから結果が生じるまでの経過時間の最大値（ウィンドウサイズ）をｗとし、時刻ｔi に起こった事象ｅx と、時刻ｔk （ｔi ＜ｔk ≦ｔi ＋ｗ）に起こった事象ｅy が、以下の条件を満たす時、ｅx からｅy への因果関係がある可能性があり、これをＣw （ｅx ，ｅy ）で表わす。
【００２８】
Ｃw （ｅx ，ｅy ）の条件：ｔi ＜ｔj ＜ｔk となる時刻ｔj の事象ｅz に対し、ｅx ≠ｅz であり、かつ、ｅy ≠ｅz である。
【００２９】
「時刻ｔi に起こった事象ｅx が原因となって、時刻ｔk （ｔi ＜ｔk ≦ｔi ＋ｗ）に事象ｅy が起こる」という因果関係ルールを以下の形式で表現することとする。
【００３０】
【数１】
0003721735.tif 000005
【００３１】
この因果関係ルールの発見を行うために、本発明では、因果関係のありそうな全ての候補に対してその出現頻度を求めると共に、そのルールが正確かどうか統計的な判定手法を用いる。以下、Ｃw （ｅx ，ｅy ）であるような事象対〈ｘ，ｙ〉の出現回数及び事象ｘの出現回数を、それぞれｎ1 （ｘ，ｙ）及びｎ（ｘ）で表わす。このとき、ｘを本体、ｙを頭部と呼ぶ。
【００３２】
図１は本発明の因果関係検出装置の基本的構成を表わすブロック図であり、図２はそのアルゴリズムを示すフローチャートである。以下、これらの図を用いて本発明による因果関係の検出動作を説明する。
【００３３】
ソート処理部１１では、データベース１２に格納されている事象の時系列データからトランザクションを時間の順に並べた事象リストを生成する（ステップ１０１）。このソート処理部１１は、一般的なデータベース制御機能等を用いて実現することができる。生成される事象リストは、例えば表１に示すように、時刻ｔ1 〜ｔT における事象の集合Ｅ1 〜ＥT のリストである。
【００３４】
【表１】
0003721735.tif 000006
【００３５】
この事象リストが巨大な場合、事象リスト全体をそのままコンピュータの主記憶部１３に配置することは不可能となる。そこで、本発明では、事象リストの内、ある時刻ｔp からウィンドウサイズｗ内の時刻のトランザクションのみを時間順に並べたローカルリストを主記憶部１３に記憶させる（ステップ１０２）。得られるローカルリストは、例えば表２に示すように、時刻ｔp 〜ｔp+m(p)における事象の集合Ｅp 〜Ｅp+m(p)のリストである。
【００３６】
【表２】
0003721735.tif 000007
【００３７】
ローカルリストの先頭トランザクションの時刻と最終トランザクションの時刻とを更新しながら、事象リストの全データをスキャンする（ステップ１０３）。ここで重要な点は、ローカルリストの更新を、事象リストの最終時刻ｔT から時間の逆順に行うことである。
【００３８】
頻度処理部１４は、ローカルリストを更新しながら、表３及び表４に示す２種類の頻度表を更新する（ステップ１０４）。表３の頻度表は事象リスト中の各事象の出現回数を記録するためのもので、表４の頻度表は事象対の出現回数を記録するためのものである。
【００３９】
【表３】
0003721735.tif 000008
【００４０】
【表４】
0003721735.tif 000009
【００４１】
頻度処理部１４の頻度処理アルゴリズムは、以下のように表わされる。
【００４２】
0003721735.tif 000010
【００４３】
ここで、ＮＢq は、時刻ｔp+1 から時刻ｔq （ｑ＞ｐ）までのトランザクションに現れる事象の集合を表わしており、「時刻ｔp の事象ｘを本体に、時刻ｔq の事象ｙを頭部とする場合、ｘ∈ＮＢp であれば、Ｃw （ｘ，ｙ）ではない」という性質を有している。Ｈq は、時刻ｔp+1 のある事象を本体に、時刻ｔq の事象を頭部とした場合、Ｃw （ｘ，ｙ）であるような事象ｙの集合を表わしており、「時刻ｔp の事象ｘ′を本体に、時刻ｔq の事象ｙ′を頭部とする場合、ｘ′∈Ｈp −Ｅp であれば、Ｃw （ｘ′，ｙ）である」という性質を有している。また、ｍ（ｐ）は、ローカルリスト中のトランザクション数より１少ない数である。従って、ローカルリスト中で最後の時刻は、ｔp+m(p)である。
【００４４】
上述したように、時間の逆順（ｐ＝Ｔ−１，Ｔ−２，…，０）にローカルリストを更新して計算することによって、時刻ｔp においては、ＮＢq 及びＨq が既知となっており、その分、計算が省略できるので、出現頻度を効率良く求めることができる。
【００４５】
因果性判定処理部２３では、表４の頻度表に現わる全事象対に対して、因果関係の有無を統計的に判定する。事象集合対〈ｘ，ｙ〉の判定には、以下のｎ1 、ｎ2 、ｎ3 及びｎ4 の４つのパラメータを使用する。
【００４６】
ｎ1 ＝Ｃw （ｘ，ｙ）となる事象ｘを含むトランザクションの数
ｎ2 ＝事象ｘを含むトランザクションの内、Ｃw （ｘ，ｙ）となるべき事象ｙを含むトランザクションがないトランザクションの数
ｎ3 ＝事象ｙを含むトランザクションの内、Ｃw （ｘ，ｙ）となるべき事象ｘを含むトランザクションがないトランザクションの数
ｎ4 ＝事象ｘも事象ｙも含まないトランザクションの数
これらの数（ｎ1 ，ｎ2 ，ｎ3 ，ｎ4 ）は、以下の式で計算する。ただし、ｎ1 （ｘ，ｙ）は表４の頻度表より、ｎ（ｘ）は表３の頻度表より、全トランザクション数はデータベースの機能から又はローカルリストの更新時にカウントすることによりそれぞれ得る。
ｎ1 ＝ｎ1 （ｘ，ｙ）
ｎ2 ＝ｎ（ｘ）−ｎ1 （ｘ，ｙ）
ｎ3 ＝ｎ（ｙ）−ｎ1 （ｘ，ｙ）
ｎ4 ＝ (全トランザクション数) −（ｎ1 ，ｎ2 ，ｎ3 ，ｎ4 ）
【００４７】
因果関係の有無の統計的判定は、因果関係が有るとするモデルによる情報量基準量Ｉ1 と因果関係が無いと仮定するモデルの情報量基準量Ｉ2 とを求め、因果関係があるとするモデルの方が適切ならば、対象となっている事象対〈ｘ，ｙ〉を因果関係ありとする。
【００４８】
情報量基準量の求め方としては、例えば赤池の情報量基準（ＡＩＣ）やベイズの情報量基準（ＢＩＣ）を用いて得ることできる。ＡＩＣを用いた場合の判定アルゴリズムを以下に示す。
【００４９】
【数２】
0003721735.tif 000011
【００５０】
因果関係を有りと仮定した時の対数尤度ＭＬＬ1 から情報量基準量Ｉ1 を求め、因果関係無しと仮定した時の対数尤度ＭＬＬ2 から情報量基準量Ｉ2 を求める。これら情報量基準量Ｉ1 と情報量基準量Ｉ2 とを求める式を以下に示す。
【００５１】
【数３】
0003721735.tif 000012
【００５２】
因果関係有りとする場合、自由パラメータはｎ1 、ｎ2 及びｎ3 の３つであり、因果関係無しの場合は、自由パラメータはｎ1 とｎ2 との比率及びｎ1 とｎ3 との比率の２つである。ＡＩＣを用いた判定アルゴリズムに示したように、情報量基準量Ｉ1 が情報量基準量Ｉ2 より小さければ、因果関係有りと判定する。
【００５３】
以下、この因果関係の有無の統計的判定手法をシミュレーションによって得た履歴データに適用した性能評価実験の結果について説明する。
【００５４】
シミュレーションとしては、ポワソン過程に従う事象発生源から特定の事象（原因）が発生した場合、正規分布に従う経過時間後に関連する事象（結果）を発生するシミュレーションとして、図３に示すように、以下の性質を有する事象発生モデルを仮定した。
（１）系ＳＹＳA 及び系ＳＹＳB は、それぞれシンボル発生源Ａ1 ，Ａ2 ，…，ＡN 及びＢ1 ，Ｂ2 ，…，ＢN を有する（Ｎ＝１００００）。
（２）Ａi が発生するシンボルをｐi1，ｐi2，…、Ｂj が発生するシンボルをｑj1，ｑj2，…とする。発生するシンボル数は２項分布Ｂ（ｎ，ｐ）に従うとする（ｎ＝１０，ｐ＝０．７）。
（３）ＳＹＳA 中からｃ個のシンボル発生源をランダムに選び出す（ｃ＝１０００）。選ばれた各シンボル発生源は、（２）で定めたシンボル以外にもシンボルを発生するとする。余分に発生するシンボルの数は２項分布Ｂ（ｃ1 ，ｐc1）に従うとする（ｃ1 ＝５，ｐc1＝０．７）。
（４）Ａi のシンボル発生間隔はポワソン分布Ｐ（λi ）に従うとする。ただし、λi は正規分布Ｎ（μ，σ）に従う（μ＝３６００，σ＝７２０）。ＳＹＳB の各シンボル発生源のシンボル発生間隔も同様にして定める。
（５）（３）で定めた余分に発生するシンボルがＡj からｐjuとして発生した時、ＳＹＳB の特定のシンボル発生源（Ｂl とする）から特定のシンボルｑlvが発生するという因果関係を仮定する。ｐjuの発生からｑlvが発生するまでの時間は正規分布Ｎ（１０，１）に従うとする。
【００５５】
シミュレータは、ＳＹＳA 及びＳＹＳB から出力される記号の時系列を履歴データとして、ｐju及びｑlv等の因果関係の相当するシンボル同士の対応表を検証用データとして出力する。履歴データでは、シンボルがどちらの系から発生したか明示されるが、どの情報源から発生したか及び因果関係に関わるかどうかは明示されない。
【００５６】
一定期間内に生じる事象の組み合わせは非常に多くなる。そこで、膨大なルール候補を減少させることを目的として、因果関係無しの判定（棄却判定）を行っているのである。そこで、評価項目として以下の項目を測定する。
・棄却判定の対象となったルールの数
・棄却されずに残ったルールの数
棄却されずに残ったルールの質が良いことも重要であるため、残ったルールに対して以下の項目を測定する。
見逃し率：実際は因果関係があるのに因果関係ルールとならなかったものの数と全因果関係数との比
誤検出率：実際は因果関係が無いのに棄却されずに因果関係ルールとなった数の因果関係ルールの総数に対する割合
【００５７】
棄却判定の対象となるルールの数及び棄却されなかったルールの数は、ウインドウサイズｗ及び履歴データの期間とに依存する。図４は履歴データの期間に対する判定対象ルールの数の関係、図５は履歴データの期間に対する残ったルールの数の関係をそれぞれ示している。これらの図より、本統計的判定手法によれば、非常に多くの候補を棄却できることが分かる。シミュレーションでは因果関係にある事象同士の時間間隔をＮ（１０，１）に設定したため、平均間隔より４σ小さいｗ＝６で正しいルールが発見されたり、ｗ＝１２で発見されなかった正しいルールがｗ＝１５で発見されることはほとんど無いはずである。このため、適切な棄却手法によれば、ｗ＝６では全ルールが棄却され、ｗ＝１２とｗ＝１５とにおける残ったルールの数が一致するはずである。図５にはこのような適切な特性が示されている。
【００５８】
図６は履歴データの期間に対する見逃し率の関係を示している。同図においては、履歴の期間が長くなるにつれて見逃し率が単調減少している。これは、期間が長くなれば、発生頻度の低い共起関係が発見できることを反映したものとなっている。
【００５９】
誤検出率については、常に０であった（因果関係の無い候補は全て棄却された）。このように、大量のルールを棄却できること、及び誤検出率が低いことから、因果関係有無のこの統計的判定手法は、正しく無いルールに対する適切な棄却能力を有すると評価できることとなる。
【００６０】
本発明は、データベースから役に立つ情報を発見するデータマイニングにおける因果関係を検出する場合に適用可能であり、例えば、システムのログから障害原因を推定したり、障害を予測したりする障害管理や、販売促進の分野において外的要因と各商品の売り上げ高との因果関係の推定に用いられる。
【００６１】
以上述べた実施形態は全て本発明を例示的に示すものであって限定的に示すものではなく、本発明は他の種々の変形態様及び変更態様で実施することができる。従って本発明の範囲は特許請求の範囲及びその均等範囲によってのみ規定されるものである。
【００６２】
【発明の効果】
以上詳細に説明したように本発明によれば、事象の履歴を記録したデータベースから因果関係を検出する場合に、発生時刻順に事象をソートした事象リストを生成し、第１の事象の集合Ｘ（＝｛ｅx1，ｅx2，…，ｅxn，…｝、ｅxnは事象を示し、ｎは自然数である）の発生時刻から、あらかじめ定めた時間（ウインドウサイズｗ）が経過するまでに第２の事象の集合Ｙ（＝｛ｅy1，ｅy2，…，ｅyn，…｝、ｅynは事象を示し、ｎは自然数である）が起こるような共起関係を持つ事象集合対〈Ｘ、Ｙ〉の出現回数、並びに第１の事象の集合Ｘ及び第２の事象の集合Ｙの出現回数を事象リストから求め、事象集合対〈Ｘ、Ｙ〉の出現回数及び各事象集合Ｘ、Ｙの出現回数を用いて、第１の事象の集合Ｘが原因となってウインドウサイズｗ内に第２の事象の集合Ｙが起こる因果関係の有意性を判定するようにしているので、因果関係の信頼性に関わるしきい値を不要とし、異なるトランザクション間の事象の共起性から因果関係を効率的に検出できる。
【図面の簡単な説明】
【図１】本発明の因果関係検出装置の基本的構成を表わすブロック図である。
【図２】図１の装置における因果関係検出のアルゴリズムを示すフローチャートである。
【図３】本発明の統計的判定方法の性能評価を行うために用いる事象発生モデルを示す図である。
【図４】履歴データの期間に対する判定対象ルールの数の関係を示す図である。
【図５】履歴データの期間に対する残ったルールの数の関係を示す図である。
【図６】履歴データの期間に対する見逃し率の関係を示す図である。
【符号の説明】
１１  ソート処理部
１２  データベース
１３  主記憶部
１４  頻度処理部
１５  因果関係判定処理部
【図１】
0003721735.tif 000013
【図２】
0003721735.tif 000014
【図３】
0003721735.tif 000015
【図４】
0003721735.tif 000016
【図５】
0003721735.tif 000017
【図６】
0003721735.tif 000018