頻出変化パターン抽出装置
【課題】時々刻々変化するネットワーク構造から頻出する変化パターンを抽出する。
【解決手段】頂点がデータに対応し、辺がデータ間の繋がりに対応するグラフの時間的変化を示す複数のグラフからなるグラフ系列毎に、当該グラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、前記第１のグラフを前記第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、前記グラフ系列を前記操作オペレータの系列に変換する変換部１２と、複数の前記グラフ系列に対応する複数の前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、前記複数の操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する抽出部１８とを備える。
【解決手段】頂点がデータに対応し、辺がデータ間の繋がりに対応するグラフの時間的変化を示す複数のグラフからなるグラフ系列毎に、当該グラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、前記第１のグラフを前記第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、前記グラフ系列を前記操作オペレータの系列に変換する変換部１２と、複数の前記グラフ系列に対応する複数の前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、前記複数の操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する抽出部１８とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフで示されたデータのデータマイニング技術に関し、特に、グラフの時間的な変化系列から当該変化系列に頻出する変化のパターンを抽出する頻出変化パターン抽出装置に関する。
【背景技術】
【０００２】
近年、膨大なデータの中から有用な、あるいは興味のあるパターンを知識として発掘しようとするデータマイニングの研究が盛んに行われている。有用性は人それぞれ異なるので定義するのは難しいが、一般に多くの事例を説明できる知識は有用と考えられる（例えば、非特許文献６参照）。１９９４年に複数のアイテム集合からなるデータから頻出アイテム集合を列挙するＡｐｒｉｏｒｉアルゴリズム（例えば、非特許文献１参照）が提案されて以来、様々なデータ構造に対して頻出パターン列挙アルゴリズムが提案されている。近年では、グラフのような複雑な構造に頻出する部分構造パターンを高速列挙する手法が提案されている（例えば、非特許文献９参照）。
【０００３】
図１４〜図１６は、Ａｐｒｉｏｒｉアルゴリズムを用いた頻出アイテム集合の列挙方法の一例について説明するための図である。Ａｐｒｉｏｒｉアルゴリズムを使用することにより、例えば、複数のデータ組に頻出するデータの組み合わせを高速に抽出することができる。
【０００４】
図１４に示すように４つのデータ組｛Ｒ，Ｙ，Ｐ｝、｛Ｂ，Ｙ，Ｇ｝、｛Ｒ，Ｂ，Ｙ，Ｇ｝及び｛Ｂ，Ｇ｝の中から、２回以上出現するデータの組み合わせを抽出する場合について考える。これらのデータ組には、Ｒ、Ｂ、Ｙ、Ｐ及びＧという５種類のデータが存在する。したがって、データの組み合わせとしては、データ数が１つの組み合わせが５（＝5Ｃ1）種類、２つの組み合わせが１０（＝5Ｃ2）種類、３つの組み合わせが１０（＝5Ｃ3）種類、４つの組み合わせが５（＝5Ｃ4）種類、５つの組み合わせが１（＝5Ｃ5）種類それぞれ存在し、計３１種類のデータの組み合わせが存在する。
【０００５】
図１５は、各頂点が１種類のデータの組み合わせに対応する探索木を示す図である。同図に示す頂点ラベルは、データの組み合わせとともに、その組み合わせを含むデータ組の個数を示している。例えば、データの組み合わせ｛Ｒ，Ｙ｝が出現するデータ組は２つ（｛Ｒ，Ｙ，Ｐ｝及び｛Ｒ，Ｂ，Ｙ，Ｇ｝）存在する。このため、頂点ラベルに「ＲＹ2」と記載されている。同図では、根に近づくほどデータ数が少なくなり、葉に近づくほどデータ数が多くなる。また、辺で接続された頂点について着目すると、子の頂点のデータの組み合わせは、親の頂点のデータの組み合わせに１つデータを付加したものになっている。総当りで探索木の探索を行なうためには、３１種類のデータの組み合わせについて出現回数の計算を行なわなければならない。
【０００６】
図１６は、Ａｐｒｉｏｒｉアルゴリズムにより、２回以上出現するデータの組み合わせの抽出方法について説明するための図である。まず、データ数が１つのデータの組み合わせ（｛Ｒ｝、｛Ｂ｝、｛Ｙ｝、｛Ｐ｝及び｛Ｇ｝）について上述の出現回数を計算すると、それぞれ２回、３回、３回、１回及び３回となる。データの組み合わせ｛Ｐ｝の出現回数は１回であるため、組み合わせ｛Ｐ｝を含む他の組み合わせについても出現回数は２回未満である。このため、組み合わせ｛Ｐ｝を含む他の組み合わせ（探索木では頂点ラベルＰ1の子孫の頂点）については、探索を行なう必要がないため、出現回数の計算を打ち切る。同様に、データ数が２つのデータの組み合わせのうち、組み合わせ｛Ｒ，Ｂ｝及び｛Ｒ，Ｇ｝の出現回数は１回であるため、これらの組み合わせを含む他の組み合わせについても出現回数の計算を打ち切る。これにより、高速に出現回数が２回以上のデータの組み合わせを求めることができる。以上説明したように、Ａｐｒｉｏｒｉアルゴリズムでは、目標に到達する見込みがないパターンの探索を途中で打ち切ることにより、高速に頻出パターンを探索することができる。
【０００７】
これまでグラフマイニングが対象としてきたグラフは、主に時間とともに変化しないグラフである。
【非特許文献１】R. Agrawal, R. Srikant. Fast Algorithms for Mining Association Rules in Large Databases. Proc. of Very Large Data Base, pp. 487-499, 1994.
【非特許文献２】A. Inokuchi et. al. An Apriori-based Algorithm for Mining Frequent Substructures from Graph Data. Proc. of European Conf. on Principles of Data Mining and Knowledge Discovery, pp. 13-23, 2000.
【非特許文献３】A. Inokuchi, T. Washio, Y. Nishimura, & H. Motoda. A Fast Algorithm for Mining Frequent Connected Subgraphs. IBM Research Report, RT0448 Feb., 2002.
【非特許文献４】M. Kuramochi & G. Karypis. Frequent Subgraph Discovery. Proc. of Int'l Conf. on Data Mining, pp.313-320, 2001.
【非特許文献５】M. Kuramochi & G. Karypis: Finding Frequent Patterns in a Large Sparse Graph. Proc. of SIAM Data Mining, 2004.
【非特許文献６】元田浩. 明示的理解に魅せられて 人工知能学会学会誌 pp. 615-625, 1999.
【非特許文献７】S. Nijssen & J. Kok. A Quickstart in Frequent Structure Mining can Make a Difference. Proc. of Int'l Conf. on Knowledge Discovery and Data Mining, pp. 647-652, 2004.
【非特許文献８】J. Pei, et. al. PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth. Pro. of Int'l Conf. on Data Engineering, pp. 215-224, 2001.
【非特許文献９】T. Washio & H. Motoda. State of the Art of Graph-based Data Mining. SIGKDD Explorations, Vol. 5, No. 1, pp. 59-68, 2003.
【非特許文献１０】X. Yan & J. Han. gSpan: Graph-Based Substructure Pattern Mining. Proc. of Int'l Conf. on Data Mining, pp. 721-724, 2002.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかし、例えば、グラフが１つの表現法である人間関係ネットワークに於いて将来ハブ（中核、中心）となる人は、ネットワーク参加時からハブの役割を果たしているわけでなく、時間とともにネットワーク構造を変化させながらハブとなりうる位置に変化していく。人間関係ネットワークにおいては、１つのコミュニティをグラフ全体だと考えると、人の参加、脱退が頂点の増減であり、そこで変化する関係の変化が辺の増減である。ホームページによって構成されるネットワーク構造も同様に、発展の過程において、ホームページやハイパーリンクの増減によって、その構造を変化させている。また遺伝子ネットワークにおいても、新規遺伝子の獲得、欠落、突然変異を含む進化の過程においてネットワーク構造が変化している。ディスカッションスレッドに於いては、新たな発言が新たな頂点の発生であり、以前のコメントに対する参照が辺の発生となる木、あるいは有向非巡回グラフの成長だとみなせる。このようなネットワーク構造の変化に関する研究は、今後重要なテーマの１つになると考えられる。
【０００９】
しかしながら、従来の部分構造パターンを高速列挙する手法は、静的なデータ構造を対象としているため、時々刻々変化するネットワーク構造から頻出する変化パターンを抽出することができなかった。
【００１０】
本発明は、上述の課題を解決するためになされたものであり、時々刻々変化するネットワーク構造から頻出する変化パターンを抽出する頻出変化パターン抽出装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、本発明に係る頻出変化パターン抽出装置は、頂点がデータに対応し、辺がデータ間の繋がりに対応するグラフの時間的変化を示す複数のグラフからなるグラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、前記第１のグラフを前記第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、前記グラフ系列を前記操作オペレータの系列に変換する変換部と、前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、前記操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する抽出部とを備えることを特徴とする。
【００１２】
具体的に、前記操作オペレータは、前記頂点の挿入、前記頂点の削除、前記頂点のラベルの変更、前記辺の挿入、前記辺の削除及び前記辺のラベルの変更の少なくとも１つを含むことを特徴とする。
【００１３】
この構成によると、グラフの変化を操作オペレータにより表現している。このため、グラフ（ネットワーク構造）の変化をオペレーション系列でとらえることができ、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、頻出する操作オペレータの系列を抽出することができる。操作オペレータの系列は、グラフの変化を表しているため、頻出するグラフの変化パターンを抽出することができる。
【００１４】
好ましくは、上述の頻出変化パターン抽出装置は、さらに、前記グラフ系列に含まれる前記複数のグラフの頂点の和集合及び辺の和集合からなるグラフから他の頂点と接続されない頂点が除外されたグラフである和グラフに対応する操作オペレータの系列を作成する和グラフ対応系列作成部を備え、前記抽出部は、前記和グラフ対応系列作成部で作成された前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、当該操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出することを特徴とする。
【００１５】
和グラフに接続されないグラフは、人間にとって理解困難なグラフと解すことができる。このため、和グラフに接続されたにグラフを除外し、和グラフに含まれる操作オペレータの系列のみを処理の対象とすることにより、人間にとって有用な操作オペレータの系列（グラフの変化パターン）のみを抽出することができる。また、抽出部が評価すべき操作オペレータの系列数を減らすことができ、処理を高速に行なうことができる。
【００１６】
さらに好ましくは、上述の頻出変化パターン抽出装置は、さらに、前記変換部で変換された前記操作オペレータの系列で示されるグラフの時間的変化が頂点数が増加するような時間的変化となるように、当該系列に含まれる操作オペレータの順序を変更する順序変更部を備え、前記抽出部は、前記順序変更部で変更された後の前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、当該操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出することを特徴とする。
【００１７】
オペレータの操作順序を入れ替えることにより、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用し易くなる。
【００１８】
なお、本発明は、このような特徴的な手段を備える頻出変化パターン抽出装置として実現することができるだけでなく、頻出変化パターン抽出装置に含まれる特徴的な手段をステップとする頻出変化パターン抽出方法として実現したり、頻出変化パターン抽出方法に含まれる特徴的なステップをコンピュータに実行させるプログラムとして実現したりすることもできる。そして、そのようなプログラムは、ＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）等の記録媒体やインターネット等の通信ネットワークを介して流通させることができるのは言うまでもない。
【発明の効果】
【００１９】
本発明によると、時々刻々変化するネットワーク構造から頻出する変化パターンを抽出する頻出変化パターン抽出装置を提供することができる。
【発明を実施するための最良の形態】
【００２０】
本発明では、グラフマイニング手法を基にして、時間とともに変化するグラフ系列からなるデータに埋もれた頻出変化パターンを効率良く列挙する手法を提案する。
【００２１】
本発明が対象とするグラフ変化は、頂点や辺が増減することで起こる構造変化を考慮する。つまり、ネットワーク（グラフ）上を流れる情報や、頂点間の距離なども、構造の変化の原因となりうる重要な要素ではあるが、問題の簡単化のために、本発明では、グラフの構造のみに着目して、議論する。
【００２２】
以下、図面を参照しながら本発明の実施の形態に係る頻出変化パターン抽出装置について説明する。
【００２３】
図１は、本発明の実施の形態に係る頻出変化パターン抽出装置の機能的な構成を示すブロック図である。
【００２４】
頻出変化パターン抽出装置１００は、時間とともに変化するグラフ系列の中から頻出する変化パターンを抽出する装置であり、グラフ変化系列記憶部１０と、変換部１２と、和グラフ対応系列作成部１４と、順序変更部１６と、抽出部１８と、系列候補作成部２０と、出現回数算出部２２とを備えている。頻出変化パターン抽出装置１００は、コンピュータにより構成され、グラフ変化系列記憶部１０は、コンピュータ上のメモリ又はハードディスク等の外部記憶装置から構成される。その他の処理部の処理は、コンピュータのＣＰＵ上でプログラムを実行させることにより実現される。
【００２５】
グラフ変化系列記憶部１０は、頂点がデータに対応し、辺がデータ間の繋がりに対応するグラフの時間的変化を示す複数のグラフからなるグラフ系列を複数記憶している記憶装置である。
【００２６】
変換部１２は、グラフ変化系列記憶部１０に記憶されているグラフ変化系列毎に、当該グラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、第１のグラフを第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、グラフ系列を操作オペレータの系列に変換する処理部である。
【００２７】
和グラフ対応系列作成部１４は、複数の操作オペレータの系列毎に、当該操作オペレータの系列に対応するグラフ系列に含まれる複数のグラフの頂点の和集合及び辺の和集合からなるグラフから他の頂点と接続されない頂点が除外されたグラフである和グラフに対応する操作オペレータの系列を作成する処理部である。
【００２８】
順序変更部１６は、和グラフ対応系列作成部１４で作成された操作オペレータの系列毎に、当該系列で示されるグラフの時間的変化が頂点数が増加するような時間的変化となるように、当該系列に含まれる操作オペレータの順序を変更する処理部である。
【００２９】
抽出部１８は、複数のグラフ系列に対応する複数の操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、複数の操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する処理部であり、系列候補作成部２０と、出現回数算出部２２とを含む。
【００３０】
系列候補作成部２０は、含まれる操作オペレータの数を１つずつ増やしながら操作オペレータの系列候補を作成する処理部である。
【００３１】
出現回数算出部２２は、複数の操作オペレータの系列における操作オペレータの系列候補の出現回数を算出する処理部である。
【００３２】
なお、系列候補作成部２０は、操作オペレータの系列候補のうち、出現回数算出部２２で算出された出現回数が所定回数以上の操作オペレータの系列候補に対してのみ、操作オペレータの数を１つ増やし、操作オペレータの系列候補を更新する。
【００３３】
以上のように構成された頻出変化パターン抽出装置１００の処理について、以下に説明する。
【００３４】
＜１．問題定義＞
図２に、グラフ変化系列記憶部１０に記憶されているグラフ変化系列の例を示す。ｇ(t)は系列の中でｔ番目のグラフであり、各ｇ(t)はラベル付きグラフである。本発明では、このようなグラフ変化系列から、頻出変化パターンを列挙するアルゴリズムを提案することを目的とする。この問題を解決するために、課題として考えられるのは、１点目としてグラフ系列の変化を如何に簡潔に表現し、同時に可能な表現の多様性を小さくすることで探索すべき空間を小さくするかが課題となる。図２のｇ(1)とｇ(2)は３頂点からなる部分構造が共通であるので、各ｔにおいて全ての頂点、辺の情報を保持することは簡潔な表現であるとはいえない。そこで本発明では、ｇ(t)とｇ(t+1)の差分に注目した記述によってグラフ変化系列を表すことを考える。
【００３５】
２点目の課題として、どのような特徴をもつパターンｐ＝＜ｇs(1)…ｇs(m)＞を探索するのかが課題となる。例えば、探索するグラフ系列の各グラフｇs(t)を制約のないグラフとした場合、探索すべきパターン数が膨大になり、さらに出力されたパターンを理解可能であるとは限らない。例えば、ｇs(t)に非連結グラフを認めると図３のようなパターンが出力される可能性がある。図３をホームページのネットワーク構造だとした場合に、頂点のＢとＣは鷲尾研究室のページ、Ａはブラジルのある組織のホームページという構造など、至る所に存在しうる部分系列であるので、頻出パターンとして取り出される可能性が大きいが、ＡとＢには何の関連もないために、このようなパターンの意味を理解することは一般には困難であり、人間の興味から外れる場合がある。一方で、各ｔに於けるグラフが連結であると制約を課すと、図２のようなパターンは探索されない。頂点３３と頂点３４は各ｔに於けるグラフ内では繋がっていないが、それらは頂点３５を介してなんらかの関係があると理解でき、このようなパターンは探索の対象としたい。汎用性の観点からは、探索対象とするパターンはより制約が少ないパターンであるほうがよいと考えられる。このように、本発明のような問題で探索すべきパターンも自明ではないために、パターンの定義についても議論を行う。
【００３６】
ラベル付きグラフｇはｇ＝（Ｖ、Ｅ、Ｌ、ｆ）で定義される。ここでＶ＝｛ｖ1，ｖ2，…，ｖn｝は頂点集合、
【数１】
は辺集合、Ｌはラベル集合であり、
【数２】
である。本発明で提案する手法は無向グラフについて議論するが、有向グラフにも適用可能である。グラフｇとｇs＝（Ｖs，Ｅs，Ｌs，ｆ）が
【数３】
を満たすような関数φが存在するとき、ｇsをｇの部分グラフと呼び、
【数４】
と表す。頂点ｖiからｖjに至る辺の集合をパスという。グラフの任意の２頂点間にパスがあるとき、そのグラフを連結グラフという。グラフ系列をｄ＝＜ｇ(1)ｇ(2)…ｇ(n)＞と表す。本発明の目的は入力としてグラフの系列ｄが与えられたときに、頻出系列ｐ＝＜ｇs(1)ｇs(2)…ｇs(m)＞を探索・発見する手法を提案することである。ここで、１≦ｊ1＜ｊ2…＜ｊm≦ｎに対して、
【数５】
であり、この時、
【数６】
と書く。
【００３７】
＜例１．＞ 例えば、ホームページのネットワークは、各ページが頂点、ハイパーリンクを辺とするグラフ構造である。グラフの構造は、編集されるたびに構造が変化する。例えば、ｇ(t)はあるサイトにおける第ｔ期目のグラフ構造である。また、各ページはラベルを持たない構造として扱ってもよいが、『大学のページ』、『金融系企業ページ』、『製造業企業ページ』などのようなラベルをもつグラフとして扱ってもよい。ラベルは分析の意図に応じて設定されるものであり、本発明では具体的に特定はしない。
【００３８】
どのようなパターンを探索するかについて議論するために和グラフ（Ｕｎｉｏｎ Ｇｒａｐｈ）を定義する。グラフの各頂点ｖiはユニークＩＤ ｉｄ（ｖi）を持ち、ユニークＩＤは時間が経過しても変わらないものとする。前述のホームページの例では、ＵＲＬがユニークＩＤに相当する。グラフ集合｛ｇ1，…，ｇn｝が与えられたとき
【数７】
を
【数８】
と定義する。ここでＶ（ｇi）、Ｅ（ｇi）はそれぞれ、グラフｇiの頂点集合、辺集合である。
【００３９】
【数９】
の頂点数は｛ｇ1，…，ｇn｝の頂点のユニークＩＤの異なり数になる。以上の定義より本発明が対象とするパターンを以下のように定義できる。パターンをｐ＝＜ｇs(1)ｇs(2)…ｇs(m)＞とするとき、
【数１０】
が連結であるグラフ系列ｐを探索する。また、この条件を満たすグラフ系列ｐに含まれる頂点は、“互いに関連している”という。パターンに現れる各グラフｇs(i)は非連結かもしれないが、パターンに現れる任意の２頂点は、対象とする期間で互いに関連しているので、出力されるパターン全てが可読（理解可能）であり、先に述べた目的に反しない。
【００４０】
文献（例えば、非特許文献５参照）では時間変化のない巨大なグラフを対象として頻出部分グラフをマイニングするＳＩＧＲＡＭを提案している。ＳＩＧＲＡＭは頻度集計法を提案しているがパターン列挙法は既存のグラフマイニング手法であるＦＳＧ（例えば、非特許文献４参照）を用いている。すなわちパターン列挙法と頻度集計法は別に定義できるものであり、本発明が対象としている問題でも同様である。従って、本発明ではパターン列挙法に主眼をおき、その効率の良い列挙法について提案する。入力データベースＤＢはグラフ系列ｄiとデータ識別子ｔｉｄiの集合として、ＤＢ＝｛（ｔｉｄi，ｄi）｜ｄi＝＜ｇi(1)ｇi(2)…ｇi(ti)＞｝とする。このようなデータベースに対し、支持度を
【数１１】
と定義する。指定された閾値σ´以上の支持度をもつパターンを頻出パターンと呼ぶ。
【００４１】
次に、１つ目のパターン列挙問題について説明する。
【００４２】
〈パターン列挙問題１（Ｓｉｍｐｌｅ Ｐｒｏｂｌｅｍ）〉
グラフの系列の集合ＤＢ＝｛（ｔｉｄi，ｄi）｜ｄi＝＜ｇi(1)…ｇi(ti)＞｝とσ´が入力として与えられた時、
【数１２】
が連結である頻出パターンｐ＝＜ｇs(1)…ｇs(m)＞を全て列挙することである。
【００４３】
パターンであるグラフの系列を構成する各グラフｇs(t)は必ずしも連結であるとは限らない。パターン列挙アルゴリズムとして最も単純な方法は、非連結グラフも出力する頻出部分グラフ列挙アルゴリズムを動かし、各頻出部分グラフをアイテムとして既存の系列パターンマイニングを動作させ、和グラフが連結でないパターンを後処理で除く手法である。しかし、この方法では後処理の直前の段階で、パターンの和グラフが連結であるという条件を満たさないパターンが大量に得られるので非効率である。
【００４４】
また、従来の系列パターンマイニング（例えば、非特許文献８参照）のように時間順にアイテムｉkを１つずつ追加して拡張する方法を考える。取り出したいパターンがｉ1ｉ2（ｉ2ｉ3）ｉ4だとすると、ｉ1，ｉ1ｉ2，ｉ1ｉ2（ｉ2），ｉ1ｉ2（ｉ2ｉ3），ｉ1ｉ2（ｉ2ｉ3）ｉ4、と順にパターンを拡張していく。新たに追加されるアイテムは時間順にみて、必ず最後に発生したアイテムが追加される。しかし、分析の対象がグラフの場合、頻出パターンの１つとして図２が頻出であると事前に分かっていれば、図２のｇs(1)に赤い頂点を追加してｇs(2)を生成できるが、＜ｇs(1)ｇs(2)＞が頻出で、＜ｇs(1)ｇs(2)ｇs(3)＞が非頻出の場合には、赤色の頂点を加えたことが無駄であり、非効率である。事前にどのようなパターンが頻出であるか分からない状態で探索するので、上記の目的を達成するには効率の良い探索手法が必要となる。
【００４５】
既存の頻出部分グラフマイニング問題との関連を述べると、パターン列挙問題１のｔiが全て１であれば、ＡｃＧＭ（例えば、非特許文献３参照）、ＦＳＧ（例えば、非特許文献４参照）、ｇＳｐａｎ（例えば、非特許文献１０参照）が対象とした問題と同一となる。また、ｔi＝１でかつ、和グラフの制約を除き、取り出されるパターンがデータベース中のグラフに誘導部分グラフとして含まれるという制約を課すとＡＧＭ（例えば、非特許文献２参照）が対象とした問題と同一である。
【００４６】
＜２．グラフ変更操作オペレータ＞
変換部１２は、グラフの変化を表現するために、グラフの編集距離を決める手法の１つを用いてｇ(t)とｇ(t+1)の差分のみを保持する。具体的には、２グラフの類似度は頂点、辺の追加、削除、ラベルの変更を２グラフが同一なるまで繰り返し適用した最短数により決められる。表１の６種の操作を変更操作オペレータと呼ぶ。
【００４７】
【表１】
【００４８】
ｇ(1)とその後の差分を保持するのも１つの手ではあるが、ｇ(0)を頂点数がゼロのグラフだと考え、ｇ(0)とｇ(1)の差分を含め、データを保持することで、データを統一的にあつかう。以後、ｇ(0)を
【数１３】
と表す。各グラフが比較的大きな場合でも、その変更箇所が少なければ、簡潔にデータを保持できる。
【００４９】
＜例２．＞ 例えば、図４のような系列を考える。図４は図５のように、頂点、辺の追加、削除の系列によって表すことができる。各頂点の右肩の数字は頂点のユニークＩＤを表している。このとき、グラフの変化を以下のように表すことができる。
【００５０】
【数１４】
データベース中のデータｄiをｄｉ＝＜ｇi(1)ｇi(2)…ｇi(n)＞で表すことをグラフ系列表記と呼び、
【数１５】
で表すことを変更操作表記、
【数１６】
を変更操作系列表記と呼ぶ。変更操作系列表記ｓに、ある操作オペレータ
【数１７】
が含まれるとき、
【数１８】
と書き、グラフ系列表記ｄに対する変更操作系列表記をｓｅｑ（ｄ）と書く。変更操作系列表記
【数１９】
から幾つかのオペレータを除いて生成される系列ｓ´をｓの部分系列であると呼び、
【数２０】
で表す。ｓ´がｓの部分系列であり、その対応関係をφで表すと、
【数２１】
に対し、
【数２２】
である。
【００５１】
＜仮定１．＞ 変更操作オペレータはｇ(t)とｇ(t+1)の最短の編集距離から生成される。従って、１つの変更操作表記中の
【数２３】
と
【数２４】
に対して、頂点を追加して、即座に削除というようなｔ1＝ｔ2かつｏ1＝ｏ2という値の組み合わせはないものとする。
【００５２】
変更操作系列表記
【数２５】
が与えられたとき、ｓに対する和グラフＧ＝（Ｖ、Ｅ）を
【数２６】
と定義する。また、ＤＢ＝｛（ｔｉｄi，ｄi）｜ｄi＝＜ｇi(1)…ｇi(ti)＞｝に対し、変更操作系列表記のパターンｓの支持度を
【数２７】
とする。和グラフＧは、和グラフ対応系列作成部１４により作成される。
【００５３】
＜パターン列挙問題２．（Ｅｘｔｅｎｄｅｄ Ｐｒｏｂｌｅｍ）＞
グラフ系列の集合ＤＢ＝｛（ｔｉｄi，ｄi）｜ｄi＝＜ｇi(1)…ｇi(ti)＞｝とσ´が入力として与えられた時、和グラフが連結であるグラフ変更操作系列表記の頻出パターン
【数２８】
を全て列挙することである。この処理は、抽出部１８により実行される。
【００５４】
＜定理１＞ 支持度はパターンの系列長に対し、逆単調性の性質を持つ。
【００５５】
＜定理２＞ グラフデータの系列の集合ＤＢ＝｛（ｔｉｄi，ｄi）｜ｄi＝＜ｇi(1)ｇi(2)…ｇi(ti)＞｝とσ´が与えられた時、パターン列挙問題１、および２で出力される全パターンの集合をそれぞれＰ1、Ｐ2とすると、
【数２９】
である。
【００５６】
前述のように、本発明では可読なパターンでかつ、制約が少ない（汎用的な）パターンをマイニングすることを目的としている。変更操作系列表記の和グラフの定義より、変更操作系列表記の和グラフが連結であれば、変更操作系列表記中の２頂点ｖiとｖjは関連しているといえる。従って、パターン列挙問題２で出力されるパターンは可読性がある。紙面の都合上証明は省略するが、定理２より、パターン列挙問題１で出力されるパターンは、パターン列挙問題２で出力されるパターンに制約を課す（増やす）ことで出力可能であると考える。よって、以降ではパターン列挙問題２について議論する。
【００５７】
操作オペレーションＯＰを定義した際、その適用順序の詳細までは議論しなかった。以下では、操作オペレータの可換性について述べる。ラベルの変更を含む性質は紙面の都合上省略するが同様に定義可能である。以下の説明で、ｔ＜ｔ´＜ｔ´´を前提とする。なお、操作オペレータの順序変更は、順序変更部１６により行なわれる。
【００５８】
＜頂点の追加→頂点の追加＞
ユニークＩＤがｉとｊの頂点を追加する場合を考える。グラフｇ（ｔ）にユニークＩＤがｉの頂点を追加し、続いてｊの頂点を追加してグラフｇ(t´´)が生成されるとき、その追加の順序を以下のように入れ替えても同型のグラフｇ(t´´)が生成される。
【００５９】
【数３０】
【００６０】
＜頂点の追加→頂点の削除＞
ユニークＩＤがｉである頂点を追加し、続いてｊである頂点を削除する場合を考える。ｉ≠ｊの場合、この操作でｇ(t´´)が生成されるとき、その追加の順序を以下のように入れ替えても同型のグラフｇ(t´´)が生成される。一方、ｉ＝ｊの場合は、追加した頂点を削除する操作なので、順序を入れ替えることはできない。
【００６１】
【数３１】
【００６２】
＜頂点の削除→頂点の追加＞
ユニークＩＤがｉである頂点を削除し、次にｊである頂点を追加する。削除される頂点はユニークＩＤがｉでない頂点から選ばれるので、順序を入れ替え可能である。
【００６３】
【数３２】
【００６４】
＜頂点の追加→辺の変更＞
辺の追加は
【数３３】
、辺の削除は
【数３４】
で表されるが、ここでは辺の変更を
【数３５】
と表す。
【００６５】
【数３６】
【００６６】
＜辺の変更→頂点の追加＞
【数３７】
【００６７】
＜頂点の削除→頂点の削除＞
【数３８】
【００６８】
＜頂点の削除→辺の変更＞
【数３９】
【００６９】
＜辺の変更→頂点の削除＞
【数４０】
【００７０】
＜辺の変更→辺の変更＞
【数４１】
【００７１】
＜３．パターン列挙アルゴリズム＞
前節で示したようにグラフの変化は操作オペレータによって表すことができる。またそれら操作の可換性について示した。パターン列挙アルゴリズムの詳細を示す前に具体例でイメージを示す。なお、パターンの列挙は、抽出部１８に含まれる系列候補作成部２０及び出現回数算出部２２により行なわれる。図６を出力されるパターンの１つとすると、
【数４２】
で表される。各オペレータの適用毎に分けて表したのが表２である。可換な範囲でこれらのオペレータの順序を入れ替えることを考える。入れ替えの１つとしては表３であり、それを図示したのが図７である。図７を見ると１つの頂点の追加とそれに付随する幾つかの辺を１つのまとまりとしてグラフを徐々に拡張していくのが分かる。各オペレータの適用順に再度並び替えることで、元のグラフ変化系列パターン（１）が得られる。
【００７２】
【表２】
【００７３】
一方、表４、及び図８は１つの辺の追加、あるいは１つの辺の追加を頂点の追加を１つのまとまりとしてグラフを拡張させる方法である。適用順序ｔなどを無視したトポロジーのみの成長のみに着目すると、前者はＡｃＧＭ（例えば、非特許文献３参照）のパターン成長（ＡｃＧＭ、ＦＳＧはＰａｔｔｅｒｎ Ｇｒｏｗｔｈ法ではなく、Ｃａｎｄｉｄａｔｅ ＆ Ｔｅｓｔ法であるが、ここではどちらもパターン成長という言葉を使う。）であり、後者はｇＳｐａｎ（例えば、非特許文献１０参照）のパターン成長法である。また異なるオペレータ順序によってＧａｓｔｏｎ（例えば、非特許文献７参照）のように、パス、根無し木、グラフの順にパターンを成長させることも可能である。以上のように提案手法はオペレータの入れ替えにより様々な既存の頻出グラフマイニング法を統合可能な非常に汎用的な手法である。
【００７４】
変更操作系列表記ｓの骨格（ｓｃａｆｆｏｌｄ）系列ｓ´を
【数４３】
に対し、ｔ1＜ｔ2かつｏ1＝ｏ2であるとき、ｓ´は
【数４４】
によって構成されるｓの部分系列であると定義する。表３のｇ1からｇ8までで形成される操作オペレータ、及び表４のｇ1からｇ8までで形成される操作オペレータが、それぞれの系列の骨格である。
【００７５】
【表３】
【００７６】
＜定理３．＞ 変更操作系列表記パターンｓとその骨格系列をｓ´とし、その対応関係をφとすると、以下が満たされる。
【００７７】
【数４５】
【００７８】
＜定理４．＞ 変更操作系列表記であるパターンｓの和グラフとｓの骨格系列から得られる和グラフは同型である。
【００７９】
以上より、変更操作系列表記で表される頻出パターンｓを得るための１つの手段として、ｓの骨格系列ｓ´を生成し、ｓ´のグラフ和を変えない範囲でｓ´に変更操作オペレータを加えて拡張していく方法が考えられる。実際、表３のｇ9以降、及び表４のｇ9以降の操作オペレータは、骨格の和グラフを変えない範囲でパターンを拡張しているのが分かる。従って、
１．はじめに取り出すべき全パターンの骨格系列を全列挙すること、
２．骨格系列の和グラフを変えない範囲で、骨格系列に含まれない操作オペレータを付け加えてパターンを順次拡張していくこと
の２点からなるアルゴリズムが考えられる。上記のステップ１で骨格系列ｓの拡張操作をｅｘｐａｎｄ（ｓ）と書く。
【００８０】
【表４】
【００８１】
＜３．１．骨格系列の拡張＞
図９は和グラフの頂点数が２までの骨格系列を探索した探索木の一部を表している。図の三角形も探索空間を示しているが、紙面の都合上省略する。骨格系列の探索は、系列候補作成部２０及び出現回数算出部２２により行なわれる。頂点ラベルの種類はＡとＢの２種、辺ラベルの種類は−の１種とし、ラベル変更はないものとする。系列候補作成部２０が１頂点のパターン候補を作成し、出現回数算出部２２が骨格パターンの出現回数を算出することにより、はじめに１頂点のパターンから探索する。このとき、探索木のルートノードの子ノードとして、１頂点で存在可能な全骨格パターン
【数４６】
に相当するノードが生成される。パターン内の頂点のユニークＩＤは１からはじまる整数値とする。続いて、
【数４７】
を拡張して、その子ノードを生成する。パターン拡張は、変更操作オペレータの適用順序ｔが増えるように拡張するのではなく、骨格パターンの和グラフが連結であるように拡張する。拡張法がＡｃＧＭであれば、１つの頂点とそれに付随する辺を追加する。拡張法が、ＦＳＧ、ｇＳｐａｎ、Ｇａｓｔｏｎのいずれかであれば、１つの辺とそれに付随する頂点で拡張する。骨格に既に含まれるｏをもつ変更操作オペレータでは拡張しない。
【００８２】
注意すべきパターンとしては、
【数４８】
である。パターン（２）は、ｔ＝０でラベルがＡ、ユニークＩＤが１である頂点を追加し、同時に頂点対（１，２）に辺を追加する。続いて、ｔ＝１でラベルがＡ、ユニークＩＤが２である頂点を追加するというパターンである。この情報だけをみると、ユニークＩＤが２である頂点を追加する前に、辺（１，２）を追加しているため、辺の追加が不可能のように思える。しかし、
【数４９】
が頻出であれば、支持度の逆単調性より、その部分系列であるパターン（２）も頻出であるので、パターン（２）も列挙する必要がある。
【００８３】
また、パターン（３）は
【数５０】
を拡張することで生成されたパターンであるが、ユニークＩＤが１である頂点の追加順序が変更されている。パターンの操作オペレータ
【数５１】
のｔは、２つの操作オペレータの適用順序の情報を示すものであるので、このようにパターン中の操作オペレータの適用順序はパターンを拡張するに従って変更されうることに注意されたい。
【００８４】
探索木の中で、同型のパターンが唯一現れるとは限らない。例えば、２つの系列
【数５２】
は同型である。同型のパターンであるが表記が異なるパターンが何度も生成されると効率が悪くなる。この場合は、骨格パターンの和グラフとその頂点のユニークＩＤから生成されるグラフコードが正準形（ｃａｎｏｎｉｃａｌ ｃｏｄｅ）であるときに、そのパターンを探索空間に残す。グラフコードは、骨格パターン拡張にＡｃＧＭ、ｇＳｐａｎ、ＦＳＧ、Ｇａｓｔｏｎなどいずれの手法を使うかに依存する。
【００８５】
＜３．２．射影データからのパターン拡張＞
前節で述べた手法を用いて骨格系列ｓを生成し、続いて本節で述べるようにｓの和グラフを変えない範囲で、骨格系列に含まれない操作オペレータを加えて拡張していく。図４のｇ8まで、及び図５のｇ8までがパターンの骨格であり、本節では、ｇ9以降の手続きについて説明する。
【００８６】
ある骨格系列ｓとそれを含むデータ（ｔｉｄi，ｄi）、その対応関係をφとする。このとき、射影関数ｐｒｏｊｅｃｔを
【数５３】
と定義する。ここで、ｄ´iは以下を満たす。
【００８７】
【数５４】
【００８８】
＜例３．＞ ある骨格系列ｓと系列データｄiの変更操作系列表記を、それぞれ以下の式であるとする。
【００８９】
【数５５】
【００９０】
このときｐｒｏｊｅｃｔ（（ｔｉｄi，ｄi），ｓ）は、以下で表される。
【００９１】
【数５６】
【００９２】
操作オペレータの適用順序ｔが同じ操作オペレータを括弧で括り、ｔを除いて系列（４）を記すと
【数５７】
となり、オペレータをアイテムとする系列パターンマイニングの系列表記と見なすことができる。入力データ集合と骨格パターンｓより
【数５８】
を生成し、系列パターンマイニングの入力とすることで、骨格系列ｓの和グラフを変えない範囲で、パターンを順次拡張することができる。
【００９３】
＜３．３．擬似コード＞
図１０に、頻出変化パターン抽出装置１００により実行される提案手法の擬似コードを示す。入力として、系列データの集合ＤＢと支持度の閾値σ´を与える。７行目で骨格系列を拡張する。９行目で、骨格系列ｓが正準形であるかをチェックする。これはｇＳｐａｎの擬似コードの「ｉｆ ｓ＝ｍｉｎ（ｓ）」に相当する手続きである（例えば、非特許文献１０参照）。列挙された骨格系列を用いて、１５行目で射影データを生成し、系列パターンマイニング手法を用いて、骨格系列の和グラフと同型な和グラフをもつ全パターンを列挙する。図１０は、深さ優先探索でパターンを列挙する手法であるが、同様に深さ優先探索で列挙する手法も設計可能である。
【００９４】
＜４．評価実験、考察＞
前節までに述べた手法をＣ＋＋で実装し、ＣＰＵが Ｃｏｒｅ Ｄｕｏ １．６６ＧＨｚ、メモリが１。５ＧＢのパーソナルコンピュータ（ＰＣ）を用いて評価実験を行った。系列パターンマイニングにはＰｒｅｆｉｘＳｐａｎ（例えば、非特許文献８参照）を用いた。表５は本実験で用いた人工データのパラメータの意味とその基本設定値を要約したものである。はじめに平均｜Ｖavg｜個の頂点をもつラベル付きグラフをＮ個生成する。頂点ラベルはＬv個のラベルから等確率で、２頂点間の辺存在確率はｐeで決められる。これが基本パターンの和グラフとなる。各基本パターンについて、
【数５９】
からはじめて、操作系列の和グラフが先に生成した和グラフと同型になるまで、変更操作オペレータを１つずつ加えていき、基本パターンの操作系列を生成する。オペレータは、頂点、辺の追加、削除のみとし、操作する頂点、辺をランダムに選択し、確率ｐiで追加か、削除を決定する。同様にして、｜ＤＢ｜個のグラフ系列を生成し、各
【数６０】
に対して基本パターンの１つを上書きする。
【００９５】
【表５】
【００９６】
結果の一部を図１１〜図１３に示す。図１１は、｜ＤＢ｜の変化に対する計算時間の変化である。データ数が増加すると計算時間はそれに比例することが分かる。図１２は、ｐ´iを変化させたときの計算時間の変化である。ただし、横軸は、系列中の平均オペレータ数を表している。ｐ´iを減少させると、平均オペレータ数は増加し、計算時間は指数関数的に増加する。図１３は、σ´の変化に対する計算時間の変化である。σ´を減少させると、計算時間は増加する。
【００９７】
以上説明したように、本発明では、ラベル付きグラフ系列に含まれる、可読な頻出変化グラフ系列パターン列挙法を提案した。グラフ変更操作オペレーションを定義し、その適用順序を入れ替えることで、効率良く列挙することを可能となる。また、人工データを用いて提案方法の評価実験を行い、データ特性の違いによる計算時間の変化を示した。
【００９８】
本発明によると、グラフの変化を操作オペレータにより表現することができる。このため、グラフ（ネットワーク構造）の変化をオペレーション系列でとらえることができ、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、頻出する操作オペレータの系列を抽出することができる。操作オペレータの系列は、グラフの変化を表しているため、頻出するグラフの変化パターンを抽出することができる。
【００９９】
また、和グラフに接続されないグラフは、人間にとって理解困難なグラフと解すことができる。このため、和グラフに接続されたにグラフを除外し、和グラフに含まれる操作オペレータの系列のみを処理の対象とすることにより、人間にとって有用な操作オペレータの系列（グラフの変化パターン）のみを抽出することができる。また、抽出部が評価すべき操作オペレータの系列数を減らすことができ、処理を高速に行なうことができる。
【０１００】
また、順序変更部１６がオペレータの操作順序を入れ替えることにより、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用し易くなる。
【０１０１】
なお、上述の実施の形態では、グラフ変化系列記憶部１０には、複数のグラフ系列が記憶されているものとして説明を行なったが、１つのグラフ系列のみが記憶されているものであっても良い。この場合には、頻出変化パターン抽出装置１００によって、１つのグラフ系列を変換した操作オペレータの１つの系列の中に所定回数以上出現する操作オペレータの系列が抽出される。
【０１０２】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味及び範囲内でのすべての変更が含まれることが意図される。
【産業上の利用可能性】
【０１０３】
本発明は、時々刻々変化するネットワーク構造に頻出する変化パターンを抽出する頻出変化パターン抽出装置に適用でき、特に、遺伝子構造の変化に頻出する変化パターンを抽出することにより、創薬を支援する創薬支援装置や、人間関係ネットワークにおいてハブとなる人物に共通する人間関係の変化パターンを抽出することにより、幹部候補を発見することを支援する幹部候補発見支援装置等に適用することができる。
【図面の簡単な説明】
【０１０４】
【図１】本発明の実施の形態に係る頻出変化パターン抽出装置の機能的な構成を示すブロック図である。
【図２】グラフ系列の一例を示す図である。
【図３】不可読なパターンの一例を示す図である。
【図４】入力系列の一部を示す図である。
【図５】グラフ変更操作オペレータによる系列表現の一例を示す図である。
【図６】出力パターンの一例を示す図である。
【図７】表３のグラフ系列表記の一例を示す図である。
【図８】表４のグラフ系列表記の一例を示す図である。
【図９】探索木の一例を示す図である。
【図１０】幅優先探索による手法の擬似コードを示す図である。
【図１１】｜ＤＢ｜の変化に対する計算時間の変化を示す図である。
【図１２】ｐ´iの変化に対する計算時間の変化を示す図である。
【図１３】σ´の変化に対する計算時間の変化を示す図である。
【図１４】データ組の一例を示す図である。
【図１５】探索木と探索木を総当り探索した結果を示す図である。
【図１６】Ａｐｒｉｏｒｉアルゴリズムにより探索を行なった結果を示す図である。
【符号の説明】
【０１０５】
１０ グラフ変化系列記憶部
１２ 変換部
１４ 和グラフ対応系列作成部
１６ 順序変更部
１８ 抽出部
２０ 系列候補作成部
２２ 出現回数算出部
３３、３４、３５ 頂点
１００ 頻出変化パターン抽出装置
【技術分野】
【０００１】
本発明は、グラフで示されたデータのデータマイニング技術に関し、特に、グラフの時間的な変化系列から当該変化系列に頻出する変化のパターンを抽出する頻出変化パターン抽出装置に関する。
【背景技術】
【０００２】
近年、膨大なデータの中から有用な、あるいは興味のあるパターンを知識として発掘しようとするデータマイニングの研究が盛んに行われている。有用性は人それぞれ異なるので定義するのは難しいが、一般に多くの事例を説明できる知識は有用と考えられる（例えば、非特許文献６参照）。１９９４年に複数のアイテム集合からなるデータから頻出アイテム集合を列挙するＡｐｒｉｏｒｉアルゴリズム（例えば、非特許文献１参照）が提案されて以来、様々なデータ構造に対して頻出パターン列挙アルゴリズムが提案されている。近年では、グラフのような複雑な構造に頻出する部分構造パターンを高速列挙する手法が提案されている（例えば、非特許文献９参照）。
【０００３】
図１４〜図１６は、Ａｐｒｉｏｒｉアルゴリズムを用いた頻出アイテム集合の列挙方法の一例について説明するための図である。Ａｐｒｉｏｒｉアルゴリズムを使用することにより、例えば、複数のデータ組に頻出するデータの組み合わせを高速に抽出することができる。
【０００４】
図１４に示すように４つのデータ組｛Ｒ，Ｙ，Ｐ｝、｛Ｂ，Ｙ，Ｇ｝、｛Ｒ，Ｂ，Ｙ，Ｇ｝及び｛Ｂ，Ｇ｝の中から、２回以上出現するデータの組み合わせを抽出する場合について考える。これらのデータ組には、Ｒ、Ｂ、Ｙ、Ｐ及びＧという５種類のデータが存在する。したがって、データの組み合わせとしては、データ数が１つの組み合わせが５（＝5Ｃ1）種類、２つの組み合わせが１０（＝5Ｃ2）種類、３つの組み合わせが１０（＝5Ｃ3）種類、４つの組み合わせが５（＝5Ｃ4）種類、５つの組み合わせが１（＝5Ｃ5）種類それぞれ存在し、計３１種類のデータの組み合わせが存在する。
【０００５】
図１５は、各頂点が１種類のデータの組み合わせに対応する探索木を示す図である。同図に示す頂点ラベルは、データの組み合わせとともに、その組み合わせを含むデータ組の個数を示している。例えば、データの組み合わせ｛Ｒ，Ｙ｝が出現するデータ組は２つ（｛Ｒ，Ｙ，Ｐ｝及び｛Ｒ，Ｂ，Ｙ，Ｇ｝）存在する。このため、頂点ラベルに「ＲＹ2」と記載されている。同図では、根に近づくほどデータ数が少なくなり、葉に近づくほどデータ数が多くなる。また、辺で接続された頂点について着目すると、子の頂点のデータの組み合わせは、親の頂点のデータの組み合わせに１つデータを付加したものになっている。総当りで探索木の探索を行なうためには、３１種類のデータの組み合わせについて出現回数の計算を行なわなければならない。
【０００６】
図１６は、Ａｐｒｉｏｒｉアルゴリズムにより、２回以上出現するデータの組み合わせの抽出方法について説明するための図である。まず、データ数が１つのデータの組み合わせ（｛Ｒ｝、｛Ｂ｝、｛Ｙ｝、｛Ｐ｝及び｛Ｇ｝）について上述の出現回数を計算すると、それぞれ２回、３回、３回、１回及び３回となる。データの組み合わせ｛Ｐ｝の出現回数は１回であるため、組み合わせ｛Ｐ｝を含む他の組み合わせについても出現回数は２回未満である。このため、組み合わせ｛Ｐ｝を含む他の組み合わせ（探索木では頂点ラベルＰ1の子孫の頂点）については、探索を行なう必要がないため、出現回数の計算を打ち切る。同様に、データ数が２つのデータの組み合わせのうち、組み合わせ｛Ｒ，Ｂ｝及び｛Ｒ，Ｇ｝の出現回数は１回であるため、これらの組み合わせを含む他の組み合わせについても出現回数の計算を打ち切る。これにより、高速に出現回数が２回以上のデータの組み合わせを求めることができる。以上説明したように、Ａｐｒｉｏｒｉアルゴリズムでは、目標に到達する見込みがないパターンの探索を途中で打ち切ることにより、高速に頻出パターンを探索することができる。
【０００７】
これまでグラフマイニングが対象としてきたグラフは、主に時間とともに変化しないグラフである。
【非特許文献１】R. Agrawal, R. Srikant. Fast Algorithms for Mining Association Rules in Large Databases. Proc. of Very Large Data Base, pp. 487-499, 1994.
【非特許文献２】A. Inokuchi et. al. An Apriori-based Algorithm for Mining Frequent Substructures from Graph Data. Proc. of European Conf. on Principles of Data Mining and Knowledge Discovery, pp. 13-23, 2000.
【非特許文献３】A. Inokuchi, T. Washio, Y. Nishimura, & H. Motoda. A Fast Algorithm for Mining Frequent Connected Subgraphs. IBM Research Report, RT0448 Feb., 2002.
【非特許文献４】M. Kuramochi & G. Karypis. Frequent Subgraph Discovery. Proc. of Int'l Conf. on Data Mining, pp.313-320, 2001.
【非特許文献５】M. Kuramochi & G. Karypis: Finding Frequent Patterns in a Large Sparse Graph. Proc. of SIAM Data Mining, 2004.
【非特許文献６】元田浩. 明示的理解に魅せられて 人工知能学会学会誌 pp. 615-625, 1999.
【非特許文献７】S. Nijssen & J. Kok. A Quickstart in Frequent Structure Mining can Make a Difference. Proc. of Int'l Conf. on Knowledge Discovery and Data Mining, pp. 647-652, 2004.
【非特許文献８】J. Pei, et. al. PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth. Pro. of Int'l Conf. on Data Engineering, pp. 215-224, 2001.
【非特許文献９】T. Washio & H. Motoda. State of the Art of Graph-based Data Mining. SIGKDD Explorations, Vol. 5, No. 1, pp. 59-68, 2003.
【非特許文献１０】X. Yan & J. Han. gSpan: Graph-Based Substructure Pattern Mining. Proc. of Int'l Conf. on Data Mining, pp. 721-724, 2002.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかし、例えば、グラフが１つの表現法である人間関係ネットワークに於いて将来ハブ（中核、中心）となる人は、ネットワーク参加時からハブの役割を果たしているわけでなく、時間とともにネットワーク構造を変化させながらハブとなりうる位置に変化していく。人間関係ネットワークにおいては、１つのコミュニティをグラフ全体だと考えると、人の参加、脱退が頂点の増減であり、そこで変化する関係の変化が辺の増減である。ホームページによって構成されるネットワーク構造も同様に、発展の過程において、ホームページやハイパーリンクの増減によって、その構造を変化させている。また遺伝子ネットワークにおいても、新規遺伝子の獲得、欠落、突然変異を含む進化の過程においてネットワーク構造が変化している。ディスカッションスレッドに於いては、新たな発言が新たな頂点の発生であり、以前のコメントに対する参照が辺の発生となる木、あるいは有向非巡回グラフの成長だとみなせる。このようなネットワーク構造の変化に関する研究は、今後重要なテーマの１つになると考えられる。
【０００９】
しかしながら、従来の部分構造パターンを高速列挙する手法は、静的なデータ構造を対象としているため、時々刻々変化するネットワーク構造から頻出する変化パターンを抽出することができなかった。
【００１０】
本発明は、上述の課題を解決するためになされたものであり、時々刻々変化するネットワーク構造から頻出する変化パターンを抽出する頻出変化パターン抽出装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、本発明に係る頻出変化パターン抽出装置は、頂点がデータに対応し、辺がデータ間の繋がりに対応するグラフの時間的変化を示す複数のグラフからなるグラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、前記第１のグラフを前記第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、前記グラフ系列を前記操作オペレータの系列に変換する変換部と、前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、前記操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する抽出部とを備えることを特徴とする。
【００１２】
具体的に、前記操作オペレータは、前記頂点の挿入、前記頂点の削除、前記頂点のラベルの変更、前記辺の挿入、前記辺の削除及び前記辺のラベルの変更の少なくとも１つを含むことを特徴とする。
【００１３】
この構成によると、グラフの変化を操作オペレータにより表現している。このため、グラフ（ネットワーク構造）の変化をオペレーション系列でとらえることができ、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、頻出する操作オペレータの系列を抽出することができる。操作オペレータの系列は、グラフの変化を表しているため、頻出するグラフの変化パターンを抽出することができる。
【００１４】
好ましくは、上述の頻出変化パターン抽出装置は、さらに、前記グラフ系列に含まれる前記複数のグラフの頂点の和集合及び辺の和集合からなるグラフから他の頂点と接続されない頂点が除外されたグラフである和グラフに対応する操作オペレータの系列を作成する和グラフ対応系列作成部を備え、前記抽出部は、前記和グラフ対応系列作成部で作成された前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、当該操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出することを特徴とする。
【００１５】
和グラフに接続されないグラフは、人間にとって理解困難なグラフと解すことができる。このため、和グラフに接続されたにグラフを除外し、和グラフに含まれる操作オペレータの系列のみを処理の対象とすることにより、人間にとって有用な操作オペレータの系列（グラフの変化パターン）のみを抽出することができる。また、抽出部が評価すべき操作オペレータの系列数を減らすことができ、処理を高速に行なうことができる。
【００１６】
さらに好ましくは、上述の頻出変化パターン抽出装置は、さらに、前記変換部で変換された前記操作オペレータの系列で示されるグラフの時間的変化が頂点数が増加するような時間的変化となるように、当該系列に含まれる操作オペレータの順序を変更する順序変更部を備え、前記抽出部は、前記順序変更部で変更された後の前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、当該操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出することを特徴とする。
【００１７】
オペレータの操作順序を入れ替えることにより、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用し易くなる。
【００１８】
なお、本発明は、このような特徴的な手段を備える頻出変化パターン抽出装置として実現することができるだけでなく、頻出変化パターン抽出装置に含まれる特徴的な手段をステップとする頻出変化パターン抽出方法として実現したり、頻出変化パターン抽出方法に含まれる特徴的なステップをコンピュータに実行させるプログラムとして実現したりすることもできる。そして、そのようなプログラムは、ＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）等の記録媒体やインターネット等の通信ネットワークを介して流通させることができるのは言うまでもない。
【発明の効果】
【００１９】
本発明によると、時々刻々変化するネットワーク構造から頻出する変化パターンを抽出する頻出変化パターン抽出装置を提供することができる。
【発明を実施するための最良の形態】
【００２０】
本発明では、グラフマイニング手法を基にして、時間とともに変化するグラフ系列からなるデータに埋もれた頻出変化パターンを効率良く列挙する手法を提案する。
【００２１】
本発明が対象とするグラフ変化は、頂点や辺が増減することで起こる構造変化を考慮する。つまり、ネットワーク（グラフ）上を流れる情報や、頂点間の距離なども、構造の変化の原因となりうる重要な要素ではあるが、問題の簡単化のために、本発明では、グラフの構造のみに着目して、議論する。
【００２２】
以下、図面を参照しながら本発明の実施の形態に係る頻出変化パターン抽出装置について説明する。
【００２３】
図１は、本発明の実施の形態に係る頻出変化パターン抽出装置の機能的な構成を示すブロック図である。
【００２４】
頻出変化パターン抽出装置１００は、時間とともに変化するグラフ系列の中から頻出する変化パターンを抽出する装置であり、グラフ変化系列記憶部１０と、変換部１２と、和グラフ対応系列作成部１４と、順序変更部１６と、抽出部１８と、系列候補作成部２０と、出現回数算出部２２とを備えている。頻出変化パターン抽出装置１００は、コンピュータにより構成され、グラフ変化系列記憶部１０は、コンピュータ上のメモリ又はハードディスク等の外部記憶装置から構成される。その他の処理部の処理は、コンピュータのＣＰＵ上でプログラムを実行させることにより実現される。
【００２５】
グラフ変化系列記憶部１０は、頂点がデータに対応し、辺がデータ間の繋がりに対応するグラフの時間的変化を示す複数のグラフからなるグラフ系列を複数記憶している記憶装置である。
【００２６】
変換部１２は、グラフ変化系列記憶部１０に記憶されているグラフ変化系列毎に、当該グラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、第１のグラフを第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、グラフ系列を操作オペレータの系列に変換する処理部である。
【００２７】
和グラフ対応系列作成部１４は、複数の操作オペレータの系列毎に、当該操作オペレータの系列に対応するグラフ系列に含まれる複数のグラフの頂点の和集合及び辺の和集合からなるグラフから他の頂点と接続されない頂点が除外されたグラフである和グラフに対応する操作オペレータの系列を作成する処理部である。
【００２８】
順序変更部１６は、和グラフ対応系列作成部１４で作成された操作オペレータの系列毎に、当該系列で示されるグラフの時間的変化が頂点数が増加するような時間的変化となるように、当該系列に含まれる操作オペレータの順序を変更する処理部である。
【００２９】
抽出部１８は、複数のグラフ系列に対応する複数の操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、複数の操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する処理部であり、系列候補作成部２０と、出現回数算出部２２とを含む。
【００３０】
系列候補作成部２０は、含まれる操作オペレータの数を１つずつ増やしながら操作オペレータの系列候補を作成する処理部である。
【００３１】
出現回数算出部２２は、複数の操作オペレータの系列における操作オペレータの系列候補の出現回数を算出する処理部である。
【００３２】
なお、系列候補作成部２０は、操作オペレータの系列候補のうち、出現回数算出部２２で算出された出現回数が所定回数以上の操作オペレータの系列候補に対してのみ、操作オペレータの数を１つ増やし、操作オペレータの系列候補を更新する。
【００３３】
以上のように構成された頻出変化パターン抽出装置１００の処理について、以下に説明する。
【００３４】
＜１．問題定義＞
図２に、グラフ変化系列記憶部１０に記憶されているグラフ変化系列の例を示す。ｇ(t)は系列の中でｔ番目のグラフであり、各ｇ(t)はラベル付きグラフである。本発明では、このようなグラフ変化系列から、頻出変化パターンを列挙するアルゴリズムを提案することを目的とする。この問題を解決するために、課題として考えられるのは、１点目としてグラフ系列の変化を如何に簡潔に表現し、同時に可能な表現の多様性を小さくすることで探索すべき空間を小さくするかが課題となる。図２のｇ(1)とｇ(2)は３頂点からなる部分構造が共通であるので、各ｔにおいて全ての頂点、辺の情報を保持することは簡潔な表現であるとはいえない。そこで本発明では、ｇ(t)とｇ(t+1)の差分に注目した記述によってグラフ変化系列を表すことを考える。
【００３５】
２点目の課題として、どのような特徴をもつパターンｐ＝＜ｇs(1)…ｇs(m)＞を探索するのかが課題となる。例えば、探索するグラフ系列の各グラフｇs(t)を制約のないグラフとした場合、探索すべきパターン数が膨大になり、さらに出力されたパターンを理解可能であるとは限らない。例えば、ｇs(t)に非連結グラフを認めると図３のようなパターンが出力される可能性がある。図３をホームページのネットワーク構造だとした場合に、頂点のＢとＣは鷲尾研究室のページ、Ａはブラジルのある組織のホームページという構造など、至る所に存在しうる部分系列であるので、頻出パターンとして取り出される可能性が大きいが、ＡとＢには何の関連もないために、このようなパターンの意味を理解することは一般には困難であり、人間の興味から外れる場合がある。一方で、各ｔに於けるグラフが連結であると制約を課すと、図２のようなパターンは探索されない。頂点３３と頂点３４は各ｔに於けるグラフ内では繋がっていないが、それらは頂点３５を介してなんらかの関係があると理解でき、このようなパターンは探索の対象としたい。汎用性の観点からは、探索対象とするパターンはより制約が少ないパターンであるほうがよいと考えられる。このように、本発明のような問題で探索すべきパターンも自明ではないために、パターンの定義についても議論を行う。
【００３６】
ラベル付きグラフｇはｇ＝（Ｖ、Ｅ、Ｌ、ｆ）で定義される。ここでＶ＝｛ｖ1，ｖ2，…，ｖn｝は頂点集合、
【数１】
は辺集合、Ｌはラベル集合であり、
【数２】
である。本発明で提案する手法は無向グラフについて議論するが、有向グラフにも適用可能である。グラフｇとｇs＝（Ｖs，Ｅs，Ｌs，ｆ）が
【数３】
を満たすような関数φが存在するとき、ｇsをｇの部分グラフと呼び、
【数４】
と表す。頂点ｖiからｖjに至る辺の集合をパスという。グラフの任意の２頂点間にパスがあるとき、そのグラフを連結グラフという。グラフ系列をｄ＝＜ｇ(1)ｇ(2)…ｇ(n)＞と表す。本発明の目的は入力としてグラフの系列ｄが与えられたときに、頻出系列ｐ＝＜ｇs(1)ｇs(2)…ｇs(m)＞を探索・発見する手法を提案することである。ここで、１≦ｊ1＜ｊ2…＜ｊm≦ｎに対して、
【数５】
であり、この時、
【数６】
と書く。
【００３７】
＜例１．＞ 例えば、ホームページのネットワークは、各ページが頂点、ハイパーリンクを辺とするグラフ構造である。グラフの構造は、編集されるたびに構造が変化する。例えば、ｇ(t)はあるサイトにおける第ｔ期目のグラフ構造である。また、各ページはラベルを持たない構造として扱ってもよいが、『大学のページ』、『金融系企業ページ』、『製造業企業ページ』などのようなラベルをもつグラフとして扱ってもよい。ラベルは分析の意図に応じて設定されるものであり、本発明では具体的に特定はしない。
【００３８】
どのようなパターンを探索するかについて議論するために和グラフ（Ｕｎｉｏｎ Ｇｒａｐｈ）を定義する。グラフの各頂点ｖiはユニークＩＤ ｉｄ（ｖi）を持ち、ユニークＩＤは時間が経過しても変わらないものとする。前述のホームページの例では、ＵＲＬがユニークＩＤに相当する。グラフ集合｛ｇ1，…，ｇn｝が与えられたとき
【数７】
を
【数８】
と定義する。ここでＶ（ｇi）、Ｅ（ｇi）はそれぞれ、グラフｇiの頂点集合、辺集合である。
【００３９】
【数９】
の頂点数は｛ｇ1，…，ｇn｝の頂点のユニークＩＤの異なり数になる。以上の定義より本発明が対象とするパターンを以下のように定義できる。パターンをｐ＝＜ｇs(1)ｇs(2)…ｇs(m)＞とするとき、
【数１０】
が連結であるグラフ系列ｐを探索する。また、この条件を満たすグラフ系列ｐに含まれる頂点は、“互いに関連している”という。パターンに現れる各グラフｇs(i)は非連結かもしれないが、パターンに現れる任意の２頂点は、対象とする期間で互いに関連しているので、出力されるパターン全てが可読（理解可能）であり、先に述べた目的に反しない。
【００４０】
文献（例えば、非特許文献５参照）では時間変化のない巨大なグラフを対象として頻出部分グラフをマイニングするＳＩＧＲＡＭを提案している。ＳＩＧＲＡＭは頻度集計法を提案しているがパターン列挙法は既存のグラフマイニング手法であるＦＳＧ（例えば、非特許文献４参照）を用いている。すなわちパターン列挙法と頻度集計法は別に定義できるものであり、本発明が対象としている問題でも同様である。従って、本発明ではパターン列挙法に主眼をおき、その効率の良い列挙法について提案する。入力データベースＤＢはグラフ系列ｄiとデータ識別子ｔｉｄiの集合として、ＤＢ＝｛（ｔｉｄi，ｄi）｜ｄi＝＜ｇi(1)ｇi(2)…ｇi(ti)＞｝とする。このようなデータベースに対し、支持度を
【数１１】
と定義する。指定された閾値σ´以上の支持度をもつパターンを頻出パターンと呼ぶ。
【００４１】
次に、１つ目のパターン列挙問題について説明する。
【００４２】
〈パターン列挙問題１（Ｓｉｍｐｌｅ Ｐｒｏｂｌｅｍ）〉
グラフの系列の集合ＤＢ＝｛（ｔｉｄi，ｄi）｜ｄi＝＜ｇi(1)…ｇi(ti)＞｝とσ´が入力として与えられた時、
【数１２】
が連結である頻出パターンｐ＝＜ｇs(1)…ｇs(m)＞を全て列挙することである。
【００４３】
パターンであるグラフの系列を構成する各グラフｇs(t)は必ずしも連結であるとは限らない。パターン列挙アルゴリズムとして最も単純な方法は、非連結グラフも出力する頻出部分グラフ列挙アルゴリズムを動かし、各頻出部分グラフをアイテムとして既存の系列パターンマイニングを動作させ、和グラフが連結でないパターンを後処理で除く手法である。しかし、この方法では後処理の直前の段階で、パターンの和グラフが連結であるという条件を満たさないパターンが大量に得られるので非効率である。
【００４４】
また、従来の系列パターンマイニング（例えば、非特許文献８参照）のように時間順にアイテムｉkを１つずつ追加して拡張する方法を考える。取り出したいパターンがｉ1ｉ2（ｉ2ｉ3）ｉ4だとすると、ｉ1，ｉ1ｉ2，ｉ1ｉ2（ｉ2），ｉ1ｉ2（ｉ2ｉ3），ｉ1ｉ2（ｉ2ｉ3）ｉ4、と順にパターンを拡張していく。新たに追加されるアイテムは時間順にみて、必ず最後に発生したアイテムが追加される。しかし、分析の対象がグラフの場合、頻出パターンの１つとして図２が頻出であると事前に分かっていれば、図２のｇs(1)に赤い頂点を追加してｇs(2)を生成できるが、＜ｇs(1)ｇs(2)＞が頻出で、＜ｇs(1)ｇs(2)ｇs(3)＞が非頻出の場合には、赤色の頂点を加えたことが無駄であり、非効率である。事前にどのようなパターンが頻出であるか分からない状態で探索するので、上記の目的を達成するには効率の良い探索手法が必要となる。
【００４５】
既存の頻出部分グラフマイニング問題との関連を述べると、パターン列挙問題１のｔiが全て１であれば、ＡｃＧＭ（例えば、非特許文献３参照）、ＦＳＧ（例えば、非特許文献４参照）、ｇＳｐａｎ（例えば、非特許文献１０参照）が対象とした問題と同一となる。また、ｔi＝１でかつ、和グラフの制約を除き、取り出されるパターンがデータベース中のグラフに誘導部分グラフとして含まれるという制約を課すとＡＧＭ（例えば、非特許文献２参照）が対象とした問題と同一である。
【００４６】
＜２．グラフ変更操作オペレータ＞
変換部１２は、グラフの変化を表現するために、グラフの編集距離を決める手法の１つを用いてｇ(t)とｇ(t+1)の差分のみを保持する。具体的には、２グラフの類似度は頂点、辺の追加、削除、ラベルの変更を２グラフが同一なるまで繰り返し適用した最短数により決められる。表１の６種の操作を変更操作オペレータと呼ぶ。
【００４７】
【表１】
【００４８】
ｇ(1)とその後の差分を保持するのも１つの手ではあるが、ｇ(0)を頂点数がゼロのグラフだと考え、ｇ(0)とｇ(1)の差分を含め、データを保持することで、データを統一的にあつかう。以後、ｇ(0)を
【数１３】
と表す。各グラフが比較的大きな場合でも、その変更箇所が少なければ、簡潔にデータを保持できる。
【００４９】
＜例２．＞ 例えば、図４のような系列を考える。図４は図５のように、頂点、辺の追加、削除の系列によって表すことができる。各頂点の右肩の数字は頂点のユニークＩＤを表している。このとき、グラフの変化を以下のように表すことができる。
【００５０】
【数１４】
データベース中のデータｄiをｄｉ＝＜ｇi(1)ｇi(2)…ｇi(n)＞で表すことをグラフ系列表記と呼び、
【数１５】
で表すことを変更操作表記、
【数１６】
を変更操作系列表記と呼ぶ。変更操作系列表記ｓに、ある操作オペレータ
【数１７】
が含まれるとき、
【数１８】
と書き、グラフ系列表記ｄに対する変更操作系列表記をｓｅｑ（ｄ）と書く。変更操作系列表記
【数１９】
から幾つかのオペレータを除いて生成される系列ｓ´をｓの部分系列であると呼び、
【数２０】
で表す。ｓ´がｓの部分系列であり、その対応関係をφで表すと、
【数２１】
に対し、
【数２２】
である。
【００５１】
＜仮定１．＞ 変更操作オペレータはｇ(t)とｇ(t+1)の最短の編集距離から生成される。従って、１つの変更操作表記中の
【数２３】
と
【数２４】
に対して、頂点を追加して、即座に削除というようなｔ1＝ｔ2かつｏ1＝ｏ2という値の組み合わせはないものとする。
【００５２】
変更操作系列表記
【数２５】
が与えられたとき、ｓに対する和グラフＧ＝（Ｖ、Ｅ）を
【数２６】
と定義する。また、ＤＢ＝｛（ｔｉｄi，ｄi）｜ｄi＝＜ｇi(1)…ｇi(ti)＞｝に対し、変更操作系列表記のパターンｓの支持度を
【数２７】
とする。和グラフＧは、和グラフ対応系列作成部１４により作成される。
【００５３】
＜パターン列挙問題２．（Ｅｘｔｅｎｄｅｄ Ｐｒｏｂｌｅｍ）＞
グラフ系列の集合ＤＢ＝｛（ｔｉｄi，ｄi）｜ｄi＝＜ｇi(1)…ｇi(ti)＞｝とσ´が入力として与えられた時、和グラフが連結であるグラフ変更操作系列表記の頻出パターン
【数２８】
を全て列挙することである。この処理は、抽出部１８により実行される。
【００５４】
＜定理１＞ 支持度はパターンの系列長に対し、逆単調性の性質を持つ。
【００５５】
＜定理２＞ グラフデータの系列の集合ＤＢ＝｛（ｔｉｄi，ｄi）｜ｄi＝＜ｇi(1)ｇi(2)…ｇi(ti)＞｝とσ´が与えられた時、パターン列挙問題１、および２で出力される全パターンの集合をそれぞれＰ1、Ｐ2とすると、
【数２９】
である。
【００５６】
前述のように、本発明では可読なパターンでかつ、制約が少ない（汎用的な）パターンをマイニングすることを目的としている。変更操作系列表記の和グラフの定義より、変更操作系列表記の和グラフが連結であれば、変更操作系列表記中の２頂点ｖiとｖjは関連しているといえる。従って、パターン列挙問題２で出力されるパターンは可読性がある。紙面の都合上証明は省略するが、定理２より、パターン列挙問題１で出力されるパターンは、パターン列挙問題２で出力されるパターンに制約を課す（増やす）ことで出力可能であると考える。よって、以降ではパターン列挙問題２について議論する。
【００５７】
操作オペレーションＯＰを定義した際、その適用順序の詳細までは議論しなかった。以下では、操作オペレータの可換性について述べる。ラベルの変更を含む性質は紙面の都合上省略するが同様に定義可能である。以下の説明で、ｔ＜ｔ´＜ｔ´´を前提とする。なお、操作オペレータの順序変更は、順序変更部１６により行なわれる。
【００５８】
＜頂点の追加→頂点の追加＞
ユニークＩＤがｉとｊの頂点を追加する場合を考える。グラフｇ（ｔ）にユニークＩＤがｉの頂点を追加し、続いてｊの頂点を追加してグラフｇ(t´´)が生成されるとき、その追加の順序を以下のように入れ替えても同型のグラフｇ(t´´)が生成される。
【００５９】
【数３０】
【００６０】
＜頂点の追加→頂点の削除＞
ユニークＩＤがｉである頂点を追加し、続いてｊである頂点を削除する場合を考える。ｉ≠ｊの場合、この操作でｇ(t´´)が生成されるとき、その追加の順序を以下のように入れ替えても同型のグラフｇ(t´´)が生成される。一方、ｉ＝ｊの場合は、追加した頂点を削除する操作なので、順序を入れ替えることはできない。
【００６１】
【数３１】
【００６２】
＜頂点の削除→頂点の追加＞
ユニークＩＤがｉである頂点を削除し、次にｊである頂点を追加する。削除される頂点はユニークＩＤがｉでない頂点から選ばれるので、順序を入れ替え可能である。
【００６３】
【数３２】
【００６４】
＜頂点の追加→辺の変更＞
辺の追加は
【数３３】
、辺の削除は
【数３４】
で表されるが、ここでは辺の変更を
【数３５】
と表す。
【００６５】
【数３６】
【００６６】
＜辺の変更→頂点の追加＞
【数３７】
【００６７】
＜頂点の削除→頂点の削除＞
【数３８】
【００６８】
＜頂点の削除→辺の変更＞
【数３９】
【００６９】
＜辺の変更→頂点の削除＞
【数４０】
【００７０】
＜辺の変更→辺の変更＞
【数４１】
【００７１】
＜３．パターン列挙アルゴリズム＞
前節で示したようにグラフの変化は操作オペレータによって表すことができる。またそれら操作の可換性について示した。パターン列挙アルゴリズムの詳細を示す前に具体例でイメージを示す。なお、パターンの列挙は、抽出部１８に含まれる系列候補作成部２０及び出現回数算出部２２により行なわれる。図６を出力されるパターンの１つとすると、
【数４２】
で表される。各オペレータの適用毎に分けて表したのが表２である。可換な範囲でこれらのオペレータの順序を入れ替えることを考える。入れ替えの１つとしては表３であり、それを図示したのが図７である。図７を見ると１つの頂点の追加とそれに付随する幾つかの辺を１つのまとまりとしてグラフを徐々に拡張していくのが分かる。各オペレータの適用順に再度並び替えることで、元のグラフ変化系列パターン（１）が得られる。
【００７２】
【表２】
【００７３】
一方、表４、及び図８は１つの辺の追加、あるいは１つの辺の追加を頂点の追加を１つのまとまりとしてグラフを拡張させる方法である。適用順序ｔなどを無視したトポロジーのみの成長のみに着目すると、前者はＡｃＧＭ（例えば、非特許文献３参照）のパターン成長（ＡｃＧＭ、ＦＳＧはＰａｔｔｅｒｎ Ｇｒｏｗｔｈ法ではなく、Ｃａｎｄｉｄａｔｅ ＆ Ｔｅｓｔ法であるが、ここではどちらもパターン成長という言葉を使う。）であり、後者はｇＳｐａｎ（例えば、非特許文献１０参照）のパターン成長法である。また異なるオペレータ順序によってＧａｓｔｏｎ（例えば、非特許文献７参照）のように、パス、根無し木、グラフの順にパターンを成長させることも可能である。以上のように提案手法はオペレータの入れ替えにより様々な既存の頻出グラフマイニング法を統合可能な非常に汎用的な手法である。
【００７４】
変更操作系列表記ｓの骨格（ｓｃａｆｆｏｌｄ）系列ｓ´を
【数４３】
に対し、ｔ1＜ｔ2かつｏ1＝ｏ2であるとき、ｓ´は
【数４４】
によって構成されるｓの部分系列であると定義する。表３のｇ1からｇ8までで形成される操作オペレータ、及び表４のｇ1からｇ8までで形成される操作オペレータが、それぞれの系列の骨格である。
【００７５】
【表３】
【００７６】
＜定理３．＞ 変更操作系列表記パターンｓとその骨格系列をｓ´とし、その対応関係をφとすると、以下が満たされる。
【００７７】
【数４５】
【００７８】
＜定理４．＞ 変更操作系列表記であるパターンｓの和グラフとｓの骨格系列から得られる和グラフは同型である。
【００７９】
以上より、変更操作系列表記で表される頻出パターンｓを得るための１つの手段として、ｓの骨格系列ｓ´を生成し、ｓ´のグラフ和を変えない範囲でｓ´に変更操作オペレータを加えて拡張していく方法が考えられる。実際、表３のｇ9以降、及び表４のｇ9以降の操作オペレータは、骨格の和グラフを変えない範囲でパターンを拡張しているのが分かる。従って、
１．はじめに取り出すべき全パターンの骨格系列を全列挙すること、
２．骨格系列の和グラフを変えない範囲で、骨格系列に含まれない操作オペレータを付け加えてパターンを順次拡張していくこと
の２点からなるアルゴリズムが考えられる。上記のステップ１で骨格系列ｓの拡張操作をｅｘｐａｎｄ（ｓ）と書く。
【００８０】
【表４】
【００８１】
＜３．１．骨格系列の拡張＞
図９は和グラフの頂点数が２までの骨格系列を探索した探索木の一部を表している。図の三角形も探索空間を示しているが、紙面の都合上省略する。骨格系列の探索は、系列候補作成部２０及び出現回数算出部２２により行なわれる。頂点ラベルの種類はＡとＢの２種、辺ラベルの種類は−の１種とし、ラベル変更はないものとする。系列候補作成部２０が１頂点のパターン候補を作成し、出現回数算出部２２が骨格パターンの出現回数を算出することにより、はじめに１頂点のパターンから探索する。このとき、探索木のルートノードの子ノードとして、１頂点で存在可能な全骨格パターン
【数４６】
に相当するノードが生成される。パターン内の頂点のユニークＩＤは１からはじまる整数値とする。続いて、
【数４７】
を拡張して、その子ノードを生成する。パターン拡張は、変更操作オペレータの適用順序ｔが増えるように拡張するのではなく、骨格パターンの和グラフが連結であるように拡張する。拡張法がＡｃＧＭであれば、１つの頂点とそれに付随する辺を追加する。拡張法が、ＦＳＧ、ｇＳｐａｎ、Ｇａｓｔｏｎのいずれかであれば、１つの辺とそれに付随する頂点で拡張する。骨格に既に含まれるｏをもつ変更操作オペレータでは拡張しない。
【００８２】
注意すべきパターンとしては、
【数４８】
である。パターン（２）は、ｔ＝０でラベルがＡ、ユニークＩＤが１である頂点を追加し、同時に頂点対（１，２）に辺を追加する。続いて、ｔ＝１でラベルがＡ、ユニークＩＤが２である頂点を追加するというパターンである。この情報だけをみると、ユニークＩＤが２である頂点を追加する前に、辺（１，２）を追加しているため、辺の追加が不可能のように思える。しかし、
【数４９】
が頻出であれば、支持度の逆単調性より、その部分系列であるパターン（２）も頻出であるので、パターン（２）も列挙する必要がある。
【００８３】
また、パターン（３）は
【数５０】
を拡張することで生成されたパターンであるが、ユニークＩＤが１である頂点の追加順序が変更されている。パターンの操作オペレータ
【数５１】
のｔは、２つの操作オペレータの適用順序の情報を示すものであるので、このようにパターン中の操作オペレータの適用順序はパターンを拡張するに従って変更されうることに注意されたい。
【００８４】
探索木の中で、同型のパターンが唯一現れるとは限らない。例えば、２つの系列
【数５２】
は同型である。同型のパターンであるが表記が異なるパターンが何度も生成されると効率が悪くなる。この場合は、骨格パターンの和グラフとその頂点のユニークＩＤから生成されるグラフコードが正準形（ｃａｎｏｎｉｃａｌ ｃｏｄｅ）であるときに、そのパターンを探索空間に残す。グラフコードは、骨格パターン拡張にＡｃＧＭ、ｇＳｐａｎ、ＦＳＧ、Ｇａｓｔｏｎなどいずれの手法を使うかに依存する。
【００８５】
＜３．２．射影データからのパターン拡張＞
前節で述べた手法を用いて骨格系列ｓを生成し、続いて本節で述べるようにｓの和グラフを変えない範囲で、骨格系列に含まれない操作オペレータを加えて拡張していく。図４のｇ8まで、及び図５のｇ8までがパターンの骨格であり、本節では、ｇ9以降の手続きについて説明する。
【００８６】
ある骨格系列ｓとそれを含むデータ（ｔｉｄi，ｄi）、その対応関係をφとする。このとき、射影関数ｐｒｏｊｅｃｔを
【数５３】
と定義する。ここで、ｄ´iは以下を満たす。
【００８７】
【数５４】
【００８８】
＜例３．＞ ある骨格系列ｓと系列データｄiの変更操作系列表記を、それぞれ以下の式であるとする。
【００８９】
【数５５】
【００９０】
このときｐｒｏｊｅｃｔ（（ｔｉｄi，ｄi），ｓ）は、以下で表される。
【００９１】
【数５６】
【００９２】
操作オペレータの適用順序ｔが同じ操作オペレータを括弧で括り、ｔを除いて系列（４）を記すと
【数５７】
となり、オペレータをアイテムとする系列パターンマイニングの系列表記と見なすことができる。入力データ集合と骨格パターンｓより
【数５８】
を生成し、系列パターンマイニングの入力とすることで、骨格系列ｓの和グラフを変えない範囲で、パターンを順次拡張することができる。
【００９３】
＜３．３．擬似コード＞
図１０に、頻出変化パターン抽出装置１００により実行される提案手法の擬似コードを示す。入力として、系列データの集合ＤＢと支持度の閾値σ´を与える。７行目で骨格系列を拡張する。９行目で、骨格系列ｓが正準形であるかをチェックする。これはｇＳｐａｎの擬似コードの「ｉｆ ｓ＝ｍｉｎ（ｓ）」に相当する手続きである（例えば、非特許文献１０参照）。列挙された骨格系列を用いて、１５行目で射影データを生成し、系列パターンマイニング手法を用いて、骨格系列の和グラフと同型な和グラフをもつ全パターンを列挙する。図１０は、深さ優先探索でパターンを列挙する手法であるが、同様に深さ優先探索で列挙する手法も設計可能である。
【００９４】
＜４．評価実験、考察＞
前節までに述べた手法をＣ＋＋で実装し、ＣＰＵが Ｃｏｒｅ Ｄｕｏ １．６６ＧＨｚ、メモリが１。５ＧＢのパーソナルコンピュータ（ＰＣ）を用いて評価実験を行った。系列パターンマイニングにはＰｒｅｆｉｘＳｐａｎ（例えば、非特許文献８参照）を用いた。表５は本実験で用いた人工データのパラメータの意味とその基本設定値を要約したものである。はじめに平均｜Ｖavg｜個の頂点をもつラベル付きグラフをＮ個生成する。頂点ラベルはＬv個のラベルから等確率で、２頂点間の辺存在確率はｐeで決められる。これが基本パターンの和グラフとなる。各基本パターンについて、
【数５９】
からはじめて、操作系列の和グラフが先に生成した和グラフと同型になるまで、変更操作オペレータを１つずつ加えていき、基本パターンの操作系列を生成する。オペレータは、頂点、辺の追加、削除のみとし、操作する頂点、辺をランダムに選択し、確率ｐiで追加か、削除を決定する。同様にして、｜ＤＢ｜個のグラフ系列を生成し、各
【数６０】
に対して基本パターンの１つを上書きする。
【００９５】
【表５】
【００９６】
結果の一部を図１１〜図１３に示す。図１１は、｜ＤＢ｜の変化に対する計算時間の変化である。データ数が増加すると計算時間はそれに比例することが分かる。図１２は、ｐ´iを変化させたときの計算時間の変化である。ただし、横軸は、系列中の平均オペレータ数を表している。ｐ´iを減少させると、平均オペレータ数は増加し、計算時間は指数関数的に増加する。図１３は、σ´の変化に対する計算時間の変化である。σ´を減少させると、計算時間は増加する。
【００９７】
以上説明したように、本発明では、ラベル付きグラフ系列に含まれる、可読な頻出変化グラフ系列パターン列挙法を提案した。グラフ変更操作オペレーションを定義し、その適用順序を入れ替えることで、効率良く列挙することを可能となる。また、人工データを用いて提案方法の評価実験を行い、データ特性の違いによる計算時間の変化を示した。
【００９８】
本発明によると、グラフの変化を操作オペレータにより表現することができる。このため、グラフ（ネットワーク構造）の変化をオペレーション系列でとらえることができ、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、頻出する操作オペレータの系列を抽出することができる。操作オペレータの系列は、グラフの変化を表しているため、頻出するグラフの変化パターンを抽出することができる。
【００９９】
また、和グラフに接続されないグラフは、人間にとって理解困難なグラフと解すことができる。このため、和グラフに接続されたにグラフを除外し、和グラフに含まれる操作オペレータの系列のみを処理の対象とすることにより、人間にとって有用な操作オペレータの系列（グラフの変化パターン）のみを抽出することができる。また、抽出部が評価すべき操作オペレータの系列数を減らすことができ、処理を高速に行なうことができる。
【０１００】
また、順序変更部１６がオペレータの操作順序を入れ替えることにより、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用し易くなる。
【０１０１】
なお、上述の実施の形態では、グラフ変化系列記憶部１０には、複数のグラフ系列が記憶されているものとして説明を行なったが、１つのグラフ系列のみが記憶されているものであっても良い。この場合には、頻出変化パターン抽出装置１００によって、１つのグラフ系列を変換した操作オペレータの１つの系列の中に所定回数以上出現する操作オペレータの系列が抽出される。
【０１０２】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味及び範囲内でのすべての変更が含まれることが意図される。
【産業上の利用可能性】
【０１０３】
本発明は、時々刻々変化するネットワーク構造に頻出する変化パターンを抽出する頻出変化パターン抽出装置に適用でき、特に、遺伝子構造の変化に頻出する変化パターンを抽出することにより、創薬を支援する創薬支援装置や、人間関係ネットワークにおいてハブとなる人物に共通する人間関係の変化パターンを抽出することにより、幹部候補を発見することを支援する幹部候補発見支援装置等に適用することができる。
【図面の簡単な説明】
【０１０４】
【図１】本発明の実施の形態に係る頻出変化パターン抽出装置の機能的な構成を示すブロック図である。
【図２】グラフ系列の一例を示す図である。
【図３】不可読なパターンの一例を示す図である。
【図４】入力系列の一部を示す図である。
【図５】グラフ変更操作オペレータによる系列表現の一例を示す図である。
【図６】出力パターンの一例を示す図である。
【図７】表３のグラフ系列表記の一例を示す図である。
【図８】表４のグラフ系列表記の一例を示す図である。
【図９】探索木の一例を示す図である。
【図１０】幅優先探索による手法の擬似コードを示す図である。
【図１１】｜ＤＢ｜の変化に対する計算時間の変化を示す図である。
【図１２】ｐ´iの変化に対する計算時間の変化を示す図である。
【図１３】σ´の変化に対する計算時間の変化を示す図である。
【図１４】データ組の一例を示す図である。
【図１５】探索木と探索木を総当り探索した結果を示す図である。
【図１６】Ａｐｒｉｏｒｉアルゴリズムにより探索を行なった結果を示す図である。
【符号の説明】
【０１０５】
１０ グラフ変化系列記憶部
１２ 変換部
１４ 和グラフ対応系列作成部
１６ 順序変更部
１８ 抽出部
２０ 系列候補作成部
２２ 出現回数算出部
３３、３４、３５ 頂点
１００ 頻出変化パターン抽出装置
【特許請求の範囲】
【請求項１】
頂点がデータに対応し、辺がデータ間の繋がりに対応するグラフの時間的変化を示す複数のグラフからなるグラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、前記第１のグラフを前記第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、前記グラフ系列を前記操作オペレータの系列に変換する変換部と、
前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、前記操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する抽出部と
を備えることを特徴とする頻出変化パターン抽出装置。
【請求項２】
前記操作オペレータは、前記頂点の挿入、前記頂点の削除、前記頂点のラベルの変更、前記辺の挿入、前記辺の削除及び前記辺のラベルの変更の少なくとも１つを含む
ことを特徴とする請求項１に記載の頻出変化パターン抽出装置。
【請求項３】
さらに、前記グラフ系列に含まれる前記複数のグラフの頂点の和集合及び辺の和集合からなるグラフから他の頂点と接続されない頂点が除外されたグラフである和グラフに対応する操作オペレータの系列を作成する和グラフ対応系列作成部を備え、
前記抽出部は、前記和グラフ対応系列作成部で作成された前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、当該操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する
ことを特徴とする請求項１又は２に記載の頻出変化パターン抽出装置。
【請求項４】
さらに、前記変換部で変換された前記操作オペレータの系列で示されるグラフの時間的変化が頂点数が増加するような時間的変化となるように、当該系列に含まれる操作オペレータの順序を変更する順序変更部を備え、
前記抽出部は、前記順序変更部で変更された後の前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、当該操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する
ことを特徴とする請求項１〜３のいずれか１項に記載の頻出変化パターン抽出装置。
【請求項５】
前記抽出部は、
含まれる操作オペレータの数を１つずつ増やしながら操作オペレータの系列候補を作成する系列候補作成部と、
前記操作オペレータの系列における前記操作オペレータの系列候補の出現回数を算出する出現回数算出部とを備え、
前記系列候補作成部は、操作オペレータの系列候補のうち、前記出現回数算出部で算出された前記出現回数が前記所定回数以上の前記操作オペレータの系列候補に対してのみ、前記操作オペレータの数を１つ増やし、前記操作オペレータの系列候補を更新する
ことを特徴とする請求項１〜４のいずれか１項に記載の頻出変化パターン抽出装置。
【請求項６】
前記グラフ系列は複数存在し、
前記変換部は、グラフ系列毎に、当該グラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、前記第１のグラフを前記第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、前記グラフ系列を前記操作オペレータの系列に変換し、
前記抽出部は、複数の前記グラフ系列に対応する複数の前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、前記複数の操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する
ことを特徴とする請求項１〜５のいずれか１項に記載の頻出変化パターン抽出装置。
【請求項７】
頂点がデータに対応し、辺がデータ間の繋がりに対応するグラフの時間的変化を示す複数のグラフからなるグラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、前記第１のグラフを前記第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、前記グラフ系列を前記操作オペレータの系列に変換するステップと、
前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、前記操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出するステップと
を含むことを特徴とする頻出変化パターン抽出装置。
【請求項８】
頂点がデータに対応し、辺がデータ間の繋がりに対応するグラフの時間的変化を示す複数のグラフからなるグラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、前記第１のグラフを前記第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、前記グラフ系列を前記操作オペレータの系列に変換するステップと、
前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、前記操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出するステップと
をコンピュータに実行させるためのプログラム。
【請求項１】
頂点がデータに対応し、辺がデータ間の繋がりに対応するグラフの時間的変化を示す複数のグラフからなるグラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、前記第１のグラフを前記第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、前記グラフ系列を前記操作オペレータの系列に変換する変換部と、
前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、前記操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する抽出部と
を備えることを特徴とする頻出変化パターン抽出装置。
【請求項２】
前記操作オペレータは、前記頂点の挿入、前記頂点の削除、前記頂点のラベルの変更、前記辺の挿入、前記辺の削除及び前記辺のラベルの変更の少なくとも１つを含む
ことを特徴とする請求項１に記載の頻出変化パターン抽出装置。
【請求項３】
さらに、前記グラフ系列に含まれる前記複数のグラフの頂点の和集合及び辺の和集合からなるグラフから他の頂点と接続されない頂点が除外されたグラフである和グラフに対応する操作オペレータの系列を作成する和グラフ対応系列作成部を備え、
前記抽出部は、前記和グラフ対応系列作成部で作成された前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、当該操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する
ことを特徴とする請求項１又は２に記載の頻出変化パターン抽出装置。
【請求項４】
さらに、前記変換部で変換された前記操作オペレータの系列で示されるグラフの時間的変化が頂点数が増加するような時間的変化となるように、当該系列に含まれる操作オペレータの順序を変更する順序変更部を備え、
前記抽出部は、前記順序変更部で変更された後の前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、当該操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する
ことを特徴とする請求項１〜３のいずれか１項に記載の頻出変化パターン抽出装置。
【請求項５】
前記抽出部は、
含まれる操作オペレータの数を１つずつ増やしながら操作オペレータの系列候補を作成する系列候補作成部と、
前記操作オペレータの系列における前記操作オペレータの系列候補の出現回数を算出する出現回数算出部とを備え、
前記系列候補作成部は、操作オペレータの系列候補のうち、前記出現回数算出部で算出された前記出現回数が前記所定回数以上の前記操作オペレータの系列候補に対してのみ、前記操作オペレータの数を１つ増やし、前記操作オペレータの系列候補を更新する
ことを特徴とする請求項１〜４のいずれか１項に記載の頻出変化パターン抽出装置。
【請求項６】
前記グラフ系列は複数存在し、
前記変換部は、グラフ系列毎に、当該グラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、前記第１のグラフを前記第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、前記グラフ系列を前記操作オペレータの系列に変換し、
前記抽出部は、複数の前記グラフ系列に対応する複数の前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、前記複数の操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出する
ことを特徴とする請求項１〜５のいずれか１項に記載の頻出変化パターン抽出装置。
【請求項７】
頂点がデータに対応し、辺がデータ間の繋がりに対応するグラフの時間的変化を示す複数のグラフからなるグラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、前記第１のグラフを前記第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、前記グラフ系列を前記操作オペレータの系列に変換するステップと、
前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、前記操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出するステップと
を含むことを特徴とする頻出変化パターン抽出装置。
【請求項８】
頂点がデータに対応し、辺がデータ間の繋がりに対応するグラフの時間的変化を示す複数のグラフからなるグラフ系列に含まれる第１のグラフから当該第１のグラフと時間的に連続する第２のグラフへの変化を、前記第１のグラフを前記第２のグラフに変更するのに必要な操作を示す操作オペレータで表現することにより、前記グラフ系列を前記操作オペレータの系列に変換するステップと、
前記操作オペレータの系列に対して、Ａｐｒｉｏｒｉアルゴリズムで用いられる逆単調性を適用することにより、前記操作オペレータの系列に所定回数以上出現する操作オペレータの系列を抽出するステップと
をコンピュータに実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２００９−２０５２６９（Ｐ２００９−２０５２６９Ａ）
【公開日】平成２１年９月１０日（２００９．９．１０）
【国際特許分類】
【出願番号】特願２００８−４４６０２（Ｐ２００８−４４６０２）
【出願日】平成２０年２月２６日（２００８．２．２６）
【出願人】（５０４１７６９１１）国立大学法人大阪大学 (1,536)
【Ｆターム（参考）】
【公開日】平成２１年９月１０日（２００９．９．１０）
【国際特許分類】
【出願日】平成２０年２月２６日（２００８．２．２６）
【出願人】（５０４１７６９１１）国立大学法人大阪大学 (1,536)
【Ｆターム（参考）】
[ Back to top ]