(57)【特許請求の範囲】
【請求項１】
離散構造データ集合Dを入力として、その離散構造データ集合Dを予め定められた第１の分割数P1個に分割した部分離散構造データ集合Diと、予め設定された閾値Tを上記第１の分割数P1個に分割した局所閾値Tiとを生成するデータ前処理部と、
上記部分離散構造データ集合Diのそれぞれにおいて、上記局所閾値Tiを上回る頻度で現れる局所的な部分構造パターンを分散並列処理して抽出し、その部分構造パターンをハッシュにより第２の分割数Q1個の部分集合に振り分けて出力する局所頻出パターン抽出部と、
上記第２の分割数Q1個に振り分けて出力される上記部分集合の全てに共通する部分構造パターンを頻出パターンとして判別して頻出パターン集合Fqを生成し、それ以外の部分構造パターンを未完パターンと判別して未完パターン集合Sqを生成する局所頻出パターン集計部と、
上記頻出パターン集合Fqを外部に出力する頻出パターン出力部と、
を具備する準頻出構造パターンマイニング装置。
【請求項２】
請求項１に記載した準頻出構造パターンマイニング装置と、
上記離散構造データ集合Dを予め定められた第３の分割数P2個に分割した部分離散構造データ集合Dk′に出現する上記未完パターン集合Sqに含まれる部分構造パターンと、その部分構造パターンに対する頻度情報とを、上記部分離散構造データDk′の数で分散並列処理して再抽出し、その部分構造パターンをハッシュにより第４の分割数Q2個の集合に振り分けて出力する未完パターン再抽出部と、
上記第４の分割数Q2個に振り分けて出力される集合を取得し、その取得した集合Sm={S1,m,…,SP2,m}に含まれる部分構造パターンとその出現頻度を集計し、その出現頻度が上記閾値Tを上回る部分構造パターンを新たな頻出パターン集合Fm′とする未完パターン再集計部と、
上記準頻出構造パターンマイニング装置が出力する頻出パターン集合Fqと、上記頻出パターン集合Fm′を合わせたものを頻出パターン集合として出力する頻出パターン出力部と、
を具備する頻出構造パターンマイニング装置。
【請求項３】
請求項１又は２に記載した準頻出構造パターンマイニング装置又は頻出構造パターンマイニング装置において、
上記局所頻出パターン集計部は上記第２の分割数Q1個の部分集合ごとに、また、上記未完パターン再集計部は上記第４の分割数Q2個の集合ごとに並列に処理を実行するものであることを特徴とする準頻出構造パターンマイニング装置又は頻出構造パターンマイニング装置。
【請求項４】
請求項１乃至３の何れかに記載した準頻出構造パターンマイニング装置又は頻出構造パターンマイニング装置において、
上記局所閾値Tiは、上記閾値Tを上記離散構造データDのデータ数で除した値に、上記部分離散構造データ集合Diのデータ数を乗じた値の小数点以下を切り捨てた整数に１を加えた値を超えないように設定されることを特徴とする準頻出構造パターンマイニング装置又は頻出構造パターンマイニング装置。
【請求項５】
離散構造データ集合Dを入力として、その離散構造データ集合Dを予め定められた第１の分割数P1個に分割した部分離散構造データDiと、予め設定された閾値Tを上記分割数P1個に分割した局所閾値Tiとを生成するデータ前処理過程と、
上記部分離散構造データ集合Diのそれぞれにおいて、上記局所閾値Tiを上回る頻度で現れる局所的な部分構造パターンを分散並列処理して抽出し、その部分構造パターンをハッシュにより第２の分割数Q1個の部分集合に振り分けて出力する局所頻出パターン抽出過程と、
上記第２の分割数Q1個に振り分けて出力される上記部分集合の全てに共通する部分構造パターンを頻出パターンとして判別して頻出パターン集合Fqを生成し、それ以外の部分構造パターンを未完パターンと判別して未完パターン集合Sqを生成する局所頻出パターン集計過程と、
上記頻出パターン集合Fqを外部に出力する頻出パターン出力過程と、
を備える準頻出構造パターンマイニング方法。
【請求項６】
請求項５に記載した準頻出構造パターンマイニング方法と、
上記離散構造データ集合Dを予め定められた第３の分割数P2個に分割した部分離散構造データ集合Dk′に出現する上記未完パターン集合Sqに含まれる部分構造パターンと、その部分構造パターンに対する頻度情報とを、上記部分離散構造データDk′の数で分散並列処理して再抽出し、その部分構造パターンをハッシュにより第４の分割数Q2個の集合に振り分けて出力する未完パターン再抽出過程と、
上記第４の分割数Q2個に振り分けて出力される集合を取得し、その取得した集合Sm={S1,m,…,SP2,m}に含まれる部分構造パターンとその出現頻度を集計し、その出現頻度が上記閾値Tを上回る部分構造パターンを新たな頻出パターン集合Fm′とする未完パターン再集計過程と、
上記準頻出構造パターンマイニング方法が生成する頻出パターン集合Fqと、上記頻出パターン集合Fm′をあわせたものを頻出パターン集合として出力する頻出パターン出力過程と、
を備える頻出構造パターンマイニング方法。
【請求項７】
請求項５又は６に記載した準頻出構造パターンマイニング方法又は頻出構造パターンマイニング方法において、
上記局所頻出パターン集計過程は上記第２の分割数Q1個の部分構造集合ごとに、また、上記未完パターン再集計過程は上記第４の分割数Q2個の集合ごとに並列に処理を実行する過程であることを特徴とする準頻出構造パターンマイニング方法又は頻出構造パターンマイニング方法。
【請求項８】
請求項５乃至７の何れかに記載した準頻出構造パターンマイニング方法又は頻出構造パターンマイニング方法において、
上記局所閾値Tiは、上記閾値Tを上記離散構造データDのデータ数で除した値に、上記部分離散構造データ集合Diのデータ数を乗じた値の小数点以下を切り捨てた整数に１を加えた値を超えないように設定されることを特徴とする準頻出構造パターンマイニング方法又は頻出構造パターンマイニング方法。
【請求項９】
請求項１乃至４の何れかに記載した準頻出構造パターンマイニング装置又は頻出構造パターンマイニング装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データの集合、主に大規模なデータの集合（データベース）から、有用な規則を抽出する技術であるデータマイニングの分野に属し、特に処理速度を高め、メモリ容量を削減した準頻出構造パターンマイニング装置と頻出構造パターンマイニング装置とそれらの方法、及びプログラムに関する。
【背景技術】
【０００２】
計算機上で扱われる実データのいくつかは、計算機で扱い易い形式に変換する段階で、離散構造データ、つまり、ラベル付きグラフにより表現される。図６に、これらのラベル付きグラフにより記述できる離散構造データの実例を示す。例えば、テキストの文法・意味的な構造（図６（a）,(b)）、遺伝子配列に対する蛋白質の構造、人や物の関係を記述するソーシャルネットワーク（図６(d)）等である。
【０００３】
データマイニングは、このような離散構造データがいくつか集った離散構造データベースから意味のある有用な規則を抽出する。データベース中に繰り返し頻出するパターンは、統計的な意味で何か有益な情報である可能性が高い。よってここでは、意味のある有用な規則として、データ中に繰り返し現れるパターンを想定する。
【０００４】
図７に構造パターンマイニングの典型例を示す。図７は、商品購買履歴のデータベースを入力として、出現頻度２回を閾値として抽出した頻出パターンの例を示す。このように大量のデータの中から有益な情報を抽出する技術は、様々な情報処理の基盤技術としての価値が高い。特に、データ量が大規模になればなるほど人手による抽出は困難となるため、計算機により自動的に有益な情報を抽出する技術の有益性が高まる。
【０００５】
計算機による構造パターンマイニングでは、大規模なデータから頻出する構造パターンを抽出することが一般的な前提条件である。これは、上記したように、データ規模が小さい場合は人手による抽出が比較的容易に実現できる場合があり、自動で行うことの意義を発揮するには人手ではコストや時間的に困難であるような状況を想定しているためである。
【０００６】
対規模性がそれなりに高い構造パターンマイニング方法として、gSpan（非特許文献１）、FREQT(非特許文献２)、PrexSpan（非特許文献３）などが知られている。
【０００７】
また、情報処理分野の一般論として、複数プロセッサを用いて分散並列処理を行うことで、処理時間を大幅に縮減する方法論が従来から存在していた。近年では、（非特許文献４）といった情報処理分野で幅広く適用することが可能な汎用的な分散並列処理の計算モデルが提案され、情報検索といった実問題で活用されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Xifeng Yan and Jiawei Han. 2002. gSpan: Graph-Based Substructure Patten Mining. Proc. of ICDM, pp. 721-724.
【非特許文献２】Mohammed J. Zaki. 2002. Efficiently Mining Frequent Trees in a Forest. Proc. Of SIG-KDD.
【非特許文献３】Lian Pei, Jiawei Han, Behzad M. Asl, Helen Pinto, Qiming Chen, Umeshwar Dayal, Mei C. Hsu. 2001. PrefixSpan: Mining Sequential PatternsEfficiently by Prefix-Projected Pattern Growth. Proc. of ICDE.
【非特許文献４】J. Dean and S. Ghemawat. 2008. MapReduce: Simplified Data Processing on Large Clusters. Commun. ACM, 51(1):107-113.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従来の構造パターンマイニング方法は、例えば、非特許文献１，２，３等は、単一のプロセッサ上で動くことを前提にしたものであり、再帰処理の逐次実行で構成されている。つまり、従来の構造パターンマイニング装置に関しては、再帰処理の逐次実行という構成であるが故に分散並列処理に好適な方法が存在していなかった。従来の逐次処理では、近年のデータの大規模化に対応するには難しい状況であり、分散並列処理といった別の方法論で処理時間を大幅に縮減する方法が求められている。
【００１０】
この発明は、このような課題に鑑みてなされたものであり、複数プロセッサの並列処理に好適な準頻出構造パターンマイニング装置と頻出構造パターンマイニング装置とそれらの方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
この発明の準頻出構造パターンマイニング装置は、データ前処理部と、局所頻出パターン抽出部と、局所頻出パターン集計部と、頻出パターン出力部、とを具備する。データ前処理部は、離散構造データ集合Dを入力として、その離散構造データ集合Dを予め定められた第１の分割数P1個に分割した部分離散構造データDiと、予め設定された閾値Tを上記分割数P1個に分割した局所閾値Tiとを生成する。局所頻出パターン抽出部は、部分離散構造データ集合Diのそれぞれにおいて、局所閾値Tiを上回る頻度で現れる局所的な部分構造パターンを分散並列処理して抽出し、その部分構造パターンをハッシュにより第２の分割数Q1個の部分集合に振り分けて出力する。局所頻出パターン集計部は、第２の分割数Q1個に振り分けて出力される部分集合の全てに共通する部分構造パターンを頻出パターンとして判別して頻出パターン集合Fqを生成し、それ以外の部分構造パターンを未完パターンと判別して未完パターン集合Sqを生成する。頻出パターン出力部は、頻出パターン集合Fqを外部に出力する。
【００１２】
また、この発明の頻出構造パターンマイニング装置は、上記した準頻出構造パターンマイニング装置に加え、未完パターン再抽出部と、未完パターン再集計部と、頻出パターン出力部と、を具備する。未完パターン再抽出部は、離散構造データ集合Dを予め定められた第３の分割数P2個に分割した部分離散構造データ集合Dk′に出現する上記未完パターン集合Sqに含まれる部分構造パターンと、その部分構造パターンに対する頻度情報とを、部分離散構造データDk′の数で分散並列処理して再抽出し、その部分構造パターンをハッシュにより第４の分割数Q2個の集合に振り分けて出力する。未完パターン再集計部は、第４の分割数Q2個に振り分けて出力される集合を取得し、その取得した集合Sm={S1,m,…,SP2,m}に含まれる部分構造パターンとその出現頻度を集計し、その出現頻度が閾値Tを上回る部分構造パターンを新たな頻出パターン集合Fm′とする。頻出パターン出力部は、準頻出構造パターンマイニング装置が出力する頻出パターン集合Fqと、頻出パターン集合Fm′を合わせたものを頻出パターン集合として出力する。
【発明の効果】
【００１３】
この発明の準頻出構造パターンマイニング装置は、処理する対象の離散構造データ集合をほぼ等しい固定サイズに分割すると共に、頻出パターンを抽出する閾値も同様に分割する。そして、分割した部分集合の全てに共通する部分構造パターンを頻出パターンとして出力する。従って、離散構造データ集合を分割した部分集合の単位の処理を複数のプロセッサで分担することが可能であり、効率的にデータマイニングを行うことが出来る。また、プロセッサ１個当たりのメモリ容量も小さくすることが出来る。
【００１４】
また、この発明の頻出構造パターンマイニング装置は、準頻出構造パターンマイニング装置で未完パターンと判別された部分構造パターンを、部分離散構造データごとに再抽出するので、頻出パターンを過不足なく抽出することが出来る。
【図面の簡単な説明】
【００１５】
【図１】この発明の準頻出構造パターンマイニング装置１００の機能構成例を示す図。
【図２】準頻出構造パターンマイニング装置１００の動作フローを示す図。
【図３】この発明の頻出構造パターンマイニング装置２００の機能構成例を示す図。
【図４】頻出構造パターンマイニング装置２００の動作フローを示す図。
【図５】この発明の頻出構造パターンマイニング方法のデータマイニングの実行時間と従来の方法の実行時間を比較した結果を示す図。
【図６】ラベル付きグラフにより記述できる離散構造データの実例を示す図である。
【図７】従来の構造パターンマイニングの典型例を示す図。
【図８】従来の典型的なMap-Reduce計算モデルを示す図。
【発明を実施するための形態】
【００１６】
以下、この発明の実施の形態を図面を参照して説明する。複数の図面中同一のものには同じ参照符号を付し、説明は繰り返さない。実施例の説明の前に、この発明の考えを説明する。
【００１７】
〔この発明の考え〕
この発明は、分散並列計算モデルであるMap-Reduceの枠組みに則って動作する構造パターンマイニングの方法を提案し、分散並列計算を利用することで大規模データから効率的に構造パターンを抽出するデータマイニングを行うものである。
【００１８】
図８に、従来の典型的なMap-Reduceモデルを、入力データを文書とした例で示す。入力データの四角は一文を意味する。Map-Reduceモデルによる分散並列計算は、入力データをほぼ均等に分割することで、分割された各データに対する計算量を均等化することにより、各データを処理する際に必要な最大メモリ料をほぼ一定に保つことができる。
【００１９】
但し、単純にMap-Reduceの枠組みで入力データを分割して処理すると、データ全体に対する各パターンの合計頻度情報の収集が難しくなる問題が発生する。そこでこの発明では、入力データを分割して処理する際に、「事前に設定された閾値を分割する。」、また、「頻出パターンかどうか判定するには頻度情報が不足している状態のパターン（未完パターン集合）を保持する。」こと、の２つの処理を行うことでMap-Reduce計算モデルに基づく分散計算環境でも、得られる頻出パターンとその頻度情報を正確に獲得することを可能にする。
【実施例１】
【００２０】
図１に、この発明の準頻出構造パターンマイニング装置１００の機能構成例を示す。ここで準頻出構造パターンとは、本装置の出力となる頻出構造パターンと未完パターンを合わせたパターンの集合を指すものとする。その動作フローを図２に示す。準頻出構造パターンマイニング装置１００は、データ前処理部１０と、局所頻出パターン抽出部２０と、局所頻出パターン集計部３０と、を具備する。局所頻出パターン抽出部２０は、P1個の局所頻出パターン抽出部２０1〜２０P1で構成され、分散並列処理を行う。その各部の機能は、例えばＲＯＭ、ＲＡＭ、ＣＰＵ等で構成されるコンピュータに所定のプログラムが読み込まれて、ＣＰＵがそのプログラムを実行することで実現されるものである。
【００２１】
データ前処理部１０は、離散構造データ集合Dを入力として、その離散構造データ集合Dを予め定められた第１の分割数P1個に分割した部分離散構造データ集合Diと、予め設定された閾値Tを上記分割数P1個に分割した局所閾値Tiとを生成する（ステップＳ１０）。
【００２２】
局所頻出パターン抽出部２０は、部分離散構造データ集合Diのそれぞれにおいて、局所閾値Tiを上回る頻度で現れる局所的な部分構造パターンを分散並列処理して抽出し、その部分構造パターンをハッシュにより第２の分割数Q1個の部分集合Li,1,…,Li,Q1に振り分けて出力する（ステップＳ２０）。
【００２３】
局所頻出パターン集計部３０は、第２の分割数Q１個に振り分けて出力される部分集合Li,1,…,Li,Q1の全てに共通する部分構造パターンを頻出パターンとして判別して頻出パターン集合Fqを生成し、それ以外の部分構造パターンを未完パターンと判別して未完パターン集合Sqを生成する（ステップＳ３０）。
【００２４】
頻出パターン出力部４０は、頻出パターン集合Fｑを外部に出力する（ステップＳ４０）。
【００２５】
準頻出構造パターンマイニング装置１００は、処理する対象の離散構造データ集合をほぼ等しい固定サイズに分割すると共に、頻出パターンを抽出する閾値も同様に分割するので、離散構造データ集合Dを分割した部分離散構造データ集合Diの単位の処理を複数のプロセッサで分担することが可能であり、高速にデータマイニングを行うことが出来る。また、プロセッサ１個当たりのメモリ容量も小さくすることが出来る。
【００２６】
以降、各機能部の動作を更に詳しく説明する。まず、準頻出構造パターンマイニング装置１００が処理する対象と、入力データについて説明する。
【００２７】
準頻出構造パターンマイニング装置１００は、グラフで記述される離散構造データの集合である離散構造データベースに対して、頻出する部分構造パターン（頻出パターン）を列挙するものである。具体的には、図６に示したように例えば、商品購買履歴のデータベースから頻出する購買パターンを頻出パターンとして抽出する。
【００２８】
入力されるデータは、全てラベル付きグラフに変換されており、変換したデータの集合をDとし、N個のグラフで構成されるものとする。また、頻出パターンとする頻度の閾値をTとし、予め設定されているものとする。但し、閾値Tは１以上の正の整数とする。
【００２９】
離散構造データ集合Dを部分離散構造データ集合Diに分割する第１のデータ分割数P1と第３のデータ分割数P2と、その部分離散構造データ集合Diにおいて局所閾値Tiを上回る頻度で現れる局所的な部分構造パターンを抽出してその部分構造パターンをハッシュにより振り分ける数を決める第２のパターン分割数Q1と第４のパターン分割数Q２とは、予め設定されているものとする。P1とP2、Q1とQ２とは分散並列処理の並列数を決める値である。これらの値は同じ値であっても良いし、異なる値であっても良い。
【００３０】
データ分割数P1とP2は、データ数が分割の上限であるため、必然的に１<P1,P2≦Nとなる。P1,P2=1は並列処理を行わないことを意味するので、この発明の対象外である。P1,P2は、一般的にはデータ数Nを適度な大きさに分割する値に設定する。一方、パターン分割数Q1とQ２は事前に上限値を知ることはできないので、適当な値を設定すれば良い。
【００３１】
〔データ前処理部〕
データ前処理部１０は、入力された離散構造データDを、第１のデータ分割数P1に基づいて分割する。分割されたi番目の部分離散構造データの集合をDiと書く。離散構造データ集合Dを分割する方法は、各グラフのノード数やエッジ数がほぼ一定の場合にはデータ数を均等にするように分割する。逆に、グラフに含まれるノード数やエッジ数が個々のグラフで比較的違う場合には、グラフのノードやエッジ数が均等になるように離散構造データ集合Dを分割した方が、リソースの分散につながる場合が多い。基本的には、この何れかの方法で離散構造データ集合Dを分割すれば良い。
【００３２】
次に、予め設定された閾値Tを第１のデータ分割数P1で分割したP1個の局所閾値Tiを決定する。局所閾値Tiは、部分離散構造データ集合Diで、局所的な頻出パターンの抽出に用いる閾値である。i番目の局所閾値をTiと書き、その値は正の整数とする。
【００３３】
閾値Tと局所閾値Tiには式（１）の関係が成り立つ。
【００３４】
【数１】
0005506629.tif 000002
【００３５】
つまり、局所閾値Ti（i＝１,…,P1）の総和が閾値Tを越えないようにP1個の局所閾値Tiを設定する。具体的には、各分割された部分離散構造データ集合Diに含まれるサンプル数に偏りがある場合には各分割された部分離散構造データ集合Diに含まれるデータ数|Di|個に基づいて式（２）に示すように設定するのが最も簡単である。|D|は、離散構造データ集合Dに含まれるデータ数（|D|=N）を表す。
【００３６】
【数２】
0005506629.tif 000003
【００３７】
但し、できるだけ左辺と右辺が近い値をとる方が理想的である。つまり、等号が成り立つことが望ましい。よって式（３）とした時、
【００３８】
【数３】
0005506629.tif 000004
【００３９】
１からrまでのiに対しては式（４）とする拡張も考えられる。
【００４０】
【数４】
0005506629.tif 000005
【００４１】
つまり、局所閾値Tiは、閾値Tを離散構造データ集合Dのデータ数|D|で除した値に、上記部分離散構造データ集合Diのデータ数|Di|を乗じた値の小数点以下を切り捨てた整数に１を加えた値を超えないように設定される。
【００４２】
例えば、サンプル数N=100でデータ分割数P1=8とする。このとき、データの分割はiが1から4までを|Di|=13、iが5から8までを|Di|=12とすれば式（５）が成り立つ。
【００４３】
【数５】
0005506629.tif 000006
【００４４】
以上の処理によって、データ分割数P1個に分割された部分離散構造データ集合Diと局所閾値Tiのペア{D1,T1},…,(DP1,TP1)}が生成される。なお、P1≠P2の場合には、データ分割数P2についても、上記と同様の方法で離散構造データ集合DをP2個に分割した部分離散構造データ集合Dk′(k=1, …,P2)を一緒に生成しても良い。
【００４５】
〔局所頻出パターン抽出部〕
局所頻出パターン抽出部２０は、データ前処理部１０が生成したP1個の部分離散構造データ集合Diと局所閾値Tiのペア{D1,T1},…,(DP1,TP1)}が、それぞれ入力されるP1個の局所頻出パターン抽出部２０1〜２０P1を備える。
【００４６】
i番目の局所頻出パターン抽出部２０iは、分割された部分離散構造データ集合Diと局所閾値Tiのペア{Di,Ti}を取得し、周知の構造パターンマイニング法を用いて局所頻出パターンを獲得する。ここでの「局所頻出パターンの抽出」とは、部分離散構造データ集合Di内で局所閾値Tiを越える頻度をもつ部分構造パターンを抽出することである。
【００４７】
この部分構造パターンを抽出する処理は、各局所パターン抽出部２０iの間で情報の共有が不要であるため、部分離散構造データ集合Diの単位で完全に分散並列処理が可能である。この処理は、Map-Reduce計算モデルのMap処理（図８のMap関数）に相当する。
【００４８】
局所頻出パターンの抽出には、単一の計算機で処理する従来の構造パターンマイニング技術を適用することができる。例えば、この実施例ではgSpan（非特許文献１）を用いる。扱うデータベース内のグラフ構造が、依存構造解析やXML文書等の木構造に限定されている場合は、木構造の効率的な構造パターンマイニング方法であるFREQT（非特許文献２）を利用することも考えられる。
【００４９】
また、データが、例えば文書や商品購買履歴のように時系列構造に限定されている場合には、系列構造に特化して効率的に頻出パターンを抽出するPrexSpan（非特許文献３）を利用することもできる。上記した３種類の方法は、全て深さ優先探索による効率的な構造パターンマイニング方法であり、基本的にはgSpanが他の二つの枠組みを含んだグラフ構造を効率的に列挙することができるアルゴリズムになっている。
【００５０】
局所頻出パターン抽出部２０iは、入力された部分離散構造データ集合Diから局所閾値Tiを上回る頻度で出現した局所頻出パターンを部分構造パターンとして出力する。このとき、予め設定した第２の分割数Q1に基づいて、ハッシュ関数によりQ1個の部分構造パターンの部分集合Li,1,…,Li,Q1に振り分ける。これを全てのi=1,…,Q1に対して同じ処理を行う。この振り分けの処理は、MapReduce計算モデルに基づいた処理である。ハッシュ関数は、各パターンに対して１からQ1の間の整数を返す任意の関数である。この振り分けにより、別の局所頻出パターン集計部から得られた同一のパターンは、必ず同じ局所頻出パターン集計部に代入される。つまり、i番目の局所頻出パターン抽出部２０iとj番目の局所頻出パターン抽出部２０j（iとjは別番号とする）で得られた同一のパターン、例えば”ABC”は、ABCのハッシュ値がkなら部分集合Li,kとLj,kに振り分けられ、最終的に、それぞれ同じ局所パターン集計部３０kに代入される。部分構造パターンには、各部分構造パターンに対応する頻度情報も対応付けて出力されるものとする。
【００５１】
〔局所頻出パターン集計部〕
局所頻出パターン集計部３０は、局所頻出パターン抽出部２０iが振り分けた数に対応した数の局所頻出パターン集計部３０jと、頻出パターン集合生成部３１と、未完パターン集合生成部３２と、を備える。図１の例では、1個目の局所頻出パターン集計部３０1とQ1個目の局所頻出パターン集計部３０Q１のみを表記し、２個目からQ１−１個目の局所頻出パターン集計部を省略している。
【００５２】
j番目（j=1,…,Q1）の局所頻出パターン集計部３０jは、各局所頻出パターン抽出部２０iから出力されるj番目の部分構造パターンの部分集合L1,j,…,LP1,jを取得し、取得した部分集合に含まれる部分構造パターンが頻出パターンになるかどうかを判定する。この処理は、Map-Reduce計算モデルのReduce処理（図８のreduce関数）に相当する。
【００５３】
各局所頻出パターン集計部３０jに入力される部分集合L1,j,…,LP1,jはパターン単位で完全に独立な処理なので、部分集合の単位で分散並列処理が可能である。
【００５４】
局所頻出パターン集計部３０iは、取得した部分集合L1,j,…,LP1,jに含まれる部分構造パターンを、頻出パターンと未完パターンの２種類に判別する。なお、１個の局所頻出パターン集計部３０1で、局所頻出パターン集計部３０を構成しても良い。その場合は、第２の分割数Q1が１であり、局所頻出パターン集計部３０は分散並列処理を行わないので、準頻出構造パターンマイニング装置１００の構成を簡単にすることができる。
【００５５】
〔頻出パターン〕
頻出パターンは、準頻出構造パターンマイニング装置１００の出力である。頻出パターンは、データ分割数P1個で独立に処理された局所頻出パターン抽出部２０iの全てにおいて、局所閾値Ti（i=1, …,P1）を上回った部分構造パターンである。つまり、取得した部分構造集合L1,j,…,LP1,jの全てに含まれる部分構造パターンを頻出パターンとして判定する。
【００５６】
局所頻出パターン集計部３０iで判別されて頻出パターンFjは、頻出パターン集合生成部３１に入力され頻出パターン集合Fqとなる。
【００５７】
〔未完パターン〕
未完パターンは、部分集合L1,j,…,LP1,jの一部において局所閾値Tiを上回る部分構造パターンであっても、全ての部分集合に含まれないパターンである。
【００５８】
ここで重要なことは、P1個の独立に処理された局所頻出パターン抽出部２０において、局所閾値Tiを一つも上回れなかった部分構造パターンは、絶対に頻出パターンに成り得ない点である。これは、式（１）から簡単に証明することが可能である。
【００５９】
ある部分構造パターンCの部分離散構造データDiにおける出現頻度をCiとした場合、Ciが全ての部分離散構造データで局所閾値Tiを上回らなかったということはCi< Tiであり式（６）が成り立つ。
【００６０】
【数６】
0005506629.tif 000007
【００６１】
よって、このような部分構造パターンCは閾値Tを上回ることがないので頻出パターンにならない。P1個の局所頻出パターン抽出部２０iは、絶対に頻出パターンにならない部分構造パターンを除外していることになる。
【００６２】
未完パターンと判定された部分構造パターンは、未完パターン集合生成部３２で、未完パターンとその頻度情報の組の集合である未完パターン集合とされる。
【００６３】
〔頻出パターン出力部〕
頻出パターン出力部４０は、頻出パターン集合生成部３１が生成した頻出パターン集合Fqを外部に出力する。
【実施例２】
【００６４】
図３に、この発明の頻出構造パターンマイニング装置２００の機能構成例を示す。その動作フローを図４に示す。頻出構造パターンマイニング装置２００は、実施例１で説明した準頻出構造パターンマイニング装置１００と、未完パターン再抽出部５０と、未完パターン再集計部６０と、頻出パターン出力部４０′と、を具備する。
【００６５】
頻出構造パターンマイニング装置２００は、準頻出構造パターンマイニング装置１００で未完パターンと判別された部分構造パターンを、部分離散構造データごとに再抽出することで頻出パターンを過不足なく抽出できるようにしたものである。
【００６６】
以降、準頻出構造パターンマイニング装置１００と異なる部分のみを説明する。
【００６７】
〔未完パターン再抽出部〕
未完パターン再抽出部５０は、離散構造データ集合Dを第３のデータ分割数P2個に分割した部分離散構造データDk′と、準頻出構造パターンマイニング装置１００の未完パターン集合生成部３２が生成した未完パターン集合Sq={S1, …,SQ1}が、それぞれ入力されるP2個の未完パターン再抽出部２０1〜２０P2を備える。
【００６８】
P2=P1であっても良い。離散構造データDをP2個に分割する処理は、準頻出構造パターンマイニング装置１００のデータ前処理部１０の内部で行っても良いし、頻出構造パターンマイニング装置２００側で行っても良い。
【００６９】
k番目（k=1,…,P2）の未完パターン再抽出部５０kは、k番目の部分離散構造データDk′と未完パターン集合Sq={S1, …,SQ1}を入力として、未完パターン集合Sq中で、頻出パターンとなる可能性のある部分構造パターンを再抽出する。
【００７０】
未完パターン再抽出部５０の処理は、上記した局所頻出パターン抽出部２０と同様に分散並列処理が可能である。この処理は、Map-Reduce計算モデルのMap処理（図８のMap関数）に相当する。
【００７１】
未完パターン再抽出部５０は、上記した局所頻出パターン抽出部２０とほぼ同等の処理を行うので、上記した既存の構造パターンマイニング手法が利用できる。処理が異なる点は、「未完パターン集合Sqに含まれる部分構造パターンであるか否か」のマイニングに基づいて枝刈りを行う点である。
【００７２】
未完パターン再抽出部５０は、部分離散構造データ集合Dk′に出現する部分構造パターンでかつ、未完パターン集合Sqに含まれる部分構造パターンと、その部分構造パターンに対する頻度情報とを、再抽出した未完パターンとして出力する。したがって、未完パターン再抽出部５０から出力される部分構造パターンは、必ず未完パターンの部分集合となる。
【００７３】
再抽出した未完パターンは、ハッシュにより事前に設定した第４の分割数Q２個の集合Sk,1,…,SkQ2に振り分けて未完パターン再集計部６０に出力する。この振り分けの処理は、Map-Reduce計算モデルに基づいた処理である。
【００７４】
〔未完パターン再集計部〕
未完パターン再集計部６０は、未完パターン再抽出部５０が振り分けた数に対応した数の未完パターン再集計部６０と、新頻出パターン集合生成部６１と、を備える。図３の例では、1個目の未完パターン再集計部６０1とQ2個目の未完パターン再集計部６０Q2のみを表記し、２個目からQ2−１個目の未完パターン再集計部を省略している。また、作図の都合により、未完パターン再集計部から新頻出パターン集合生成部６１に入力される部分構造パターンのF2とFQ2-1の表記を省略している。
【００７５】
m番目（m=1,…,Q2）の未完パターン再集計部６０mは、P2個の未完パターン再抽出部５０からそれぞれm番目の再抽出した部分構造パターンである未完パターンを取得する。新頻出パターン集合生成部６１は、取得した集合Sm={S1,m,…,SP2,m}に含まれる部分構造パターンについてその頻度情報が閾値Tを越えるものを、新たな頻出パターンの集合Fm′として生成する。
【００７６】
頻出パターン出力部４０′は、準頻出構造パターンマイニング装置１００が出力する頻出パターン集合Fq={F1,…,FQ1}と、新頻出パターン集合生成部６１が出力する新頻出パターン集合Fm′={F1′,…,FQ2′}を合わせたものを最終的な頻出パターン集合Fとして出力する。なお、この発明の処理上、集合FqとFm′には重複するパターンは含まれないことが保証されている。
【００７７】
〔評価結果〕
この発明の頻出構造パターンマイニング装置の有効性を確認する目的で、シングルプロセッサでパターンマイニングを行った場合と、この発明の方法で行った場合の実行時間を比較した。その結果を図５に示す。
【００７８】
図５の横軸は文の数を（Million）で表す。縦軸は実行時間を（秒）で表す。シングルプロセッサ（破線）は１ＣＰＵ、本発明の並列分散処理（実線）では同じＣＰＵを２００個用いた。ＣＰＵにはインテルXEON2.96GHzを用いた。
【００７９】
文の数が３（Million）つまり、３百万個の文を対象にしたパターンマイニングの処理時間は本発明が約１００秒であり、シングルプロセッサが約１３００秒である。本発明の方が１０分の１以上も実行時間が短くて済む。また、本発明はデータをほぼ固定サイズに分割することにより、分割された各データの処理に必要な計算コストの上限を一定に保つことができる。よって、計算時間はデータの分割数に依存する。図５によれば、用いるデータの総量に対してほぼ線形の実行時間であることが分かる。
【００８０】
このように、この発明の頻出構造パターンマイニング装置は、高速にデータマイニングを行うことが出来る。
【００８１】
上記装置における処理手段をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各装置における処理手段がコンピュータ上で実現される。
【００８２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、DVD（Digital Versatile Disc）、DVD-RAM（Random Access Memory）、CD-ROM（Compact Disc Read Only Memory）、CD-R（Recordable）/RW（ReWritable）等を、光磁気記録媒体として、MO（Magneto Optical disc）等を、半導体メモリとしてEEP-ROM（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００８３】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記録装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００８４】
また、各手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0005506629.tif 000008
【図２】
0005506629.tif 000009
【図３】
0005506629.tif 000010
【図４】
0005506629.tif 000011
【図５】
0005506629.tif 000012
【図６】
0005506629.tif 000013
【図７】
0005506629.tif 000014
【図８】
0005506629.tif 000015