(57)【要約】【課題】複数のオブジェクトに共通して含まれる多頻度部分グラフを、上位概念化を考慮しつつ効率良く抽出する。【解決手段】複数のオブジェクトに含まれる多頻度部分グラフの組を抽出する多頻度パターン抽出装置であって、複数種類の構成要素とこれらの上位概念要素との対応を格納する概念階層データベースと、既に抽出された多頻度部分グラフから抽出候補部分グラフの組を生成する抽出候補部分グラフ生成部と、抽出候補部分グラフの重み付き支持度を算出する重み付き支持度算出部と、第１の抽出候補部分グラフの上位概念パターンとなる第２の抽出候補部分グラフを選択する上位概念候補選択部と、第１抽出候補部分グラフ及び第２抽出候補部分グラフの重み付き支持度が同一でないことを条件として、第２抽出候補部分グラフを多頻度部分グラフの組に追加する多頻度部分グラフ追加部とを備える多頻度パターン抽出装置を提供する。【選択図】図１
2005063277.tif 000002
【特許請求の範囲】
【請求項１】
グラフ構造によりそれぞれ表現された複数の前記オブジェクトのうち、予め定められた最小割合以上の前記オブジェクトにそれぞれ含まれる多頻度部分グラフの組を抽出する多頻度パターン抽出装置であって、
前記複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる複数の頂点及び複数の辺のそれぞれを構成要素とするグラフ構造により表現され、
予め定められた複数種類の前記構成要素と、前記複数種類の構成要素のいずれにもマッチングされる上位概念要素との対応を格納する概念階層データベースと、
既に抽出された前記多頻度部分グラフに前記構成要素又は前記上位概念要素を付加した抽出候補部分グラフの組を生成する抽出候補部分グラフ生成部と、
前記複数のオブジェクトのそれぞれにおける前記抽出候補部分グラフにマッチングされる部分グラフの個数を合計した重み付き支持度を算出する重み付き支持度算出部と、
第１の前記抽出候補部分グラフに含まれる前記構成要素を、当該構成要素にマッチングされる前記上位概念要素に置き換えた場合に前記第１抽出候補部分グラフと同一の部分グラフとなる第２の抽出候補部分グラフを選択する上位概念候補選択部と、
前記第１抽出候補部分グラフの前記重み付き支持度である第１重み付き支持度及び前記第２抽出候補部分グラフの前記重み付き支持度である第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加する多頻度部分グラフ追加部と
を備える多頻度パターン抽出装置。
【請求項２】
前記多頻度部分グラフ追加部は、前記第１抽出候補部分グラフを前記多頻度部分グラフの組に追加すること、及び、前記第１重み付き支持度及び前記第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加する請求項１記載の多頻度パターン抽出装置。
【請求項３】
前記抽出候補部分グラフ生成部は、前記抽出候補部分グラフとして、当該抽出候補部分グラフにマッチングされる部分グラフを含む前記オブジェクトの割合を示す支持度が前記最小割合以上を示す前記抽出候補部分グラフを生成する請求項２記載の多頻度パターン抽出装置。
【請求項４】
前記抽出候補部分グラフ生成部は、
既に抽出された一の前記多頻度部分グラフに一の前記構成要素を付加した前記多頻度グラフ候補を生成する構成要素付加部と、
前記一の構成要素を検索キーとして、前記一の構成要素にマッチングされる一の前記上位概念要素を前記概念階層データベースから検索する上位概念要素検索部と、
前記一の多頻度部分グラフに前記一の上位概念要素を付加した前記抽出候補部分グラフを生成する上位概念要素付加部と
を有する請求項１記載の多頻度パターン抽出装置。
【請求項５】
前記多頻度部分グラフを、前記構成要素の数に基づき定められた当該多頻度部分グラフの大きさに対応付けて格納する多頻度部分グラフデータベースを更に備え、
前記抽出候補部分グラフ生成部は、
第１の大きさを有する前記多頻度部分グラフを前記多頻度部分グラフデータベースから検索する多頻度部分グラフ検索部と、
検索された前記多頻度部分グラフに前記構成要素又は前記上位概念要素を付加して前記第１の大きさより大きい第２の大きさとした部分グラフを、当該部分グラフにマッチングされる部分グラフを含む前記オブジェクトの割合を示す支持度が前記最小割合以上を示すことを条件として前記抽出候補部分グラフとして選択する抽出候補部分グラフ選択部と、
を有し、
前記重み付き支持度算出部は、前記第２の大きさの前記抽出候補部分グラフの前記重み付き支持度を算出し、
前記多頻度部分グラフ追加部は、前記第１重み付き支持度及び前記第２重み付き支持度が同一でないことを条件として、前記第２の大きさに対応付けて前記第２抽出候補部分グラフを前記多頻度部分グラフデータベースに格納する
請求項１記載の多頻度パターン抽出装置。
【請求項６】
前記概念階層データベースは、一の前記構成要素と、当該一の構成要素にマッチングされる第１の前記上位概念要素及び第２の前記上位概念要素との対応を更に格納し、
前記上位概念候補選択部は、前記第１抽出候補部分グラフに含まれる前記構成要素を、当該構成要素にマッチングされる前記上位概念要素に置き換えた場合に前記第１抽出候補部分グラフと同一の部分グラフとなる第３の抽出候補部分グラフを更に選択し、
前記多頻度部分グラフ追加部は、前記第２重み付き支持度及び前記第３抽出候補部分グラフの前記重み付き支持度である第３重み付き支持度が同一、かつ、前記複数のオブジェクトのそれぞれについて、当該オブジェクトにおける前記第２抽出候補部分グラフにマッチングされる部分グラフの組と当該オブジェクトにおける前記第３抽出候補部分グラフにマッチングされる部分グラフの組とが同一である場合に、前記第１重み付き支持度及び前記第２重み付き支持度が同一でないことを条件として前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加し、前記第３抽出候補部分グラフを前記多頻度部分グラフの組に追加しない
請求項１記載の多頻度パターン抽出装置。
【請求項７】
前記複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる前記複数の頂点が当該オブジェクトに含まれる複数の原子に対応し、当該オブジェクトに含まれる前記複数の辺が前記複数の原子間の結合に対応する化学物質を示し、
複数の前記化学物質のそれぞれは、当該化学物質が薬品として所定の効用を有することを実験により分析した分析結果に基づいて選択されており、
前記概念階層データベースは、予め定められた複数種類の原子と、前記複数種類の原子のいずれにもマッチングされる上位概念原子との対応を、前記複数種類の構成要素と、前記複数種類の構成要素のいずれにもマッチングされる前記上位概念要素との対応として格納し、
前記抽出候補部分グラフ生成部は、前記所定の効用を有する化学物質の部分構造として既に抽出された前記多頻度部分グラフに前記原子又は前記上位概念原子を付加した前記抽出候補部分グラフの組を生成し、
前記重み付き支持度算出部は、前記複数のオブジェクトのそれぞれにおける前記抽出候補部分グラフにマッチングされる部分グラフの個数を合計した前記重み付き支持度を算出し、
前記上位概念候補選択部は、前記第１抽出候補部分グラフに含まれる原子を当該原子にマッチングされる前記上位概念原子に置き換えた場合に前記第１抽出候補部分グラフと同一の部分構造を示す部分グラフとなる前記第２抽出候補部分グラフを選択し、
前記多頻度部分グラフ追加部は、前記第１重み付き支持度及び前記第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加することにより、前記所定の効用を有する化学物質に共通して含まれる部分構造の組を生成する
請求項１記載の多頻度パターン抽出装置。
【請求項８】
前記複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる前記複数の頂点が閲覧されたウェブページに対応し、当該オブジェクトに含まれる前記複数の辺が前記ウェブページの閲覧順序を示すワールド・ワイド・ウェブサイトの閲覧履歴であり、
前記概念階層データベースは、予め定められた複数種類のウェブページと、前記複数種類のウェブページのいずれにもマッチングされる上位概念ウェブページとの対応を、前記複数種類の構成要素と、前記複数種類の構成要素のいずれにもマッチングされる前記上位概念要素との対応として格納し、
前記抽出候補部分グラフ生成部は、前記所定の特性を有する前記閲覧履歴の部分構造として既に抽出された前記多頻度部分グラフに前記ウェブページ又は前記上位概念ウェブページを付加した前記抽出候補部分グラフの組を生成し、
前記重み付き支持度算出部は、前記複数のオブジェクトのそれぞれにおける前記抽出候補部分グラフにマッチングされる部分グラフの個数を合計した前記重み付き支持度を算出し、
前記上位概念候補選択部は、前記第１抽出候補部分グラフに含まれるウェブページを当該ウェブページにマッチングされる前記上位概念ウェブページに置き換えた場合に前記第１抽出候補部分グラフと同一の部分構造を示す部分グラフとなる前記第２抽出候補部分グラフを選択し、
前記多頻度部分グラフ追加部は、前記第１重み付き支持度及び前記第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加することにより、前記所定の特性を有する前記閲覧履歴に共通して含まれる部分構造の組を生成する
請求項１記載の多頻度パターン抽出装置。
【請求項９】
前記複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる前記複数の頂点が当該オブジェクトに含まれる複数の語句に対応し、当該オブジェクトに含まれる前記複数の辺が前記複数の語句間の順序に対応する文章を示し、
複数の前記文章のそれぞれは、当該文章が所定のジャンルに分類されるべきことを分析した分析結果に基づいて選択されており、
前記概念階層データベースは、予め定められた複数種類の語句と、前記複数種類の語句のいずれにもマッチングされる上位概念語句との対応を、前記複数種類の構成要素と、前記複数種類の構成要素のいずれにもマッチングされる前記上位概念要素との対応として格納し、
前記抽出候補部分グラフ生成部は、前記所定のジャンルに分類される前記文章の部分構造として既に抽出された前記多頻度部分グラフに前記語句又は前記上位概念語句を付加した前記抽出候補部分グラフの組を生成し、
前記重み付き支持度算出部は、前記複数のオブジェクトのそれぞれにおける前記抽出候補部分グラフにマッチングされる部分グラフの個数を合計した前記重み付き支持度を算出し、
前記上位概念候補選択部は、前記第１抽出候補部分グラフに含まれる語句を当該語句にマッチングされる前記上位概念語句に置き換えた場合に前記第１抽出候補部分グラフと同一の部分構造を示す部分グラフとなる前記第２抽出候補部分グラフを選択し、
前記多頻度部分グラフ追加部は、前記第１重み付き支持度及び前記第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加することにより、前記所定のジャンルの前記文章に共通して含まれる部分構造の組を生成する
請求項１記載の多頻度パターン抽出装置。
【請求項１０】
グラフ構造によりそれぞれ表現された複数の前記オブジェクトのうち、予め定められた最小割合以上の前記オブジェクトにそれぞれ含まれる多頻度部分グラフの組をコンピュータにより抽出する多頻度パターン抽出方法であって、
前記複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる複数の頂点及び複数の辺のそれぞれを構成要素とするグラフ構造により表現され、
予め定められた複数種類の前記構成要素と、前記複数種類の構成要素のいずれにもマッチングされる上位概念要素との対応を格納する概念階層データベースを前記コンピュータにより管理する概念階層データベース管理段階と、
既に抽出された前記多頻度部分グラフに前記構成要素又は前記上位概念要素を付加した抽出候補部分グラフの組を前記コンピュータにより生成する抽出候補部分グラフ生成段階と、
前記複数のオブジェクトのそれぞれにおける前記抽出候補部分グラフにマッチングされる部分グラフの個数を合計した重み付き支持度を前記コンピュータにより算出する重み付き支持度算出段階と、
第１の前記抽出候補部分グラフに含まれる前記構成要素を、当該構成要素にマッチングされる前記上位概念要素に置き換えた場合に前記第１抽出候補部分グラフと同一の部分グラフとなる第２の抽出候補部分グラフを前記コンピュータにより選択する上位概念候補選択段階と、
前記第１抽出候補部分グラフの前記重み付き支持度である第１重み付き支持度及び前記第２抽出候補部分グラフの前記重み付き支持度である第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に前記コンピュータにより追加する多頻度部分グラフ追加段階と
を備える多頻度パターン抽出方法。
【請求項１１】
コンピュータを、グラフ構造によりそれぞれ表現された複数の前記オブジェクトのうち、予め定められた最小割合以上の前記オブジェクトにそれぞれ含まれる多頻度部分グラフの組を抽出する多頻度パターン抽出装置として機能させるプログラムであって、
前記複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる複数の頂点及び複数の辺のそれぞれを構成要素とするグラフ構造により表現され、
当該プログラムは、前記コンピュータを、
予め定められた複数種類の前記構成要素と、前記複数種類の構成要素のいずれにもマッチングされる上位概念要素との対応を格納する概念階層データベースを管理する概念階層データベース管理部と、
既に抽出された前記多頻度部分グラフに前記構成要素又は前記上位概念要素を付加した抽出候補部分グラフの組を生成する抽出候補部分グラフ生成部と、
前記複数のオブジェクトのそれぞれにおける前記抽出候補部分グラフにマッチングされる部分グラフの個数を合計した重み付き支持度を算出する重み付き支持度算出部と、
第１の前記抽出候補部分グラフに含まれる前記構成要素を、当該構成要素にマッチングされる前記上位概念要素に置き換えた場合に前記第１抽出候補部分グラフと同一の部分グラフとなる第２の抽出候補部分グラフを選択する上位概念候補選択部と、
前記第１抽出候補部分グラフの前記重み付き支持度である第１重み付き支持度及び前記第２抽出候補部分グラフの前記重み付き支持度である第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加する多頻度部分グラフ追加部と
して機能させるプログラム。
【請求項１２】
請求項１１記載のプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多頻度パターン抽出装置、多頻度パターン抽出方法、及びそのプログラムと記録媒体に関する。特に本発明は、グラフ構造により表現される分析対象のオブジェクトが所定の特性を有するか否かを分析した分析結果に基づいて、所定の特性を有する複数のオブジェクトの多くに含まれる多頻度部分グラフを抽出する多頻度パターン抽出装置、多頻度パターン抽出方法、及びそのプログラムと記録媒体に関する。
【背景技術】
【０００２】
近年、様々な分野でIT（Information Technology）が導入されるのに伴い、自然界の物質、社会の現象、及び人間の行動等のデータが電子化されつつある。このような背景の中で、大量に蓄積されたデータの中から頻繁に出現するパターンを検出して、検出された当該パターンをビジネス及び科学に有効利用するデータマイニング技術が注目されている。従来、リレーショナルテーブルに格納された関連性（リレーション）又はＰＯＳトランザクション等の定型的なログの中から、頻繁に出現するパターンを検出する方法が提案されている（非特許文献１０参照。）。このような多頻度パターンの検出方法の一例としては、バスケット分析が挙げられる（非特許文献２参照。）バスケット分析においては、トランザクションに含まれる各アイテムが概念階層を持つ場合に、データベースから相関ルールあるいは多頻度アイテム集合を抽出する方法が提案されている（非特許文献５、１１参照。）。
【０００３】
一方、定型的なログのみならず、グラフ又は木構造のデータの中から、頻出するパターンを検出する方法が提案されている。グラフ構造のデータに対するデータマイニング技術としては、ＷＡＭＡＲ（非特許文献３参照。）、ＡＧＭ（非特許文献６、７参照。）、ＦＳＧ（非特許文献８参照。）、ＭｏｌＦｅａ（非特許文献４参照。）等が提案されている。また、木構造のデータに対するデータマイニング技術としては、非特許文献９、ＦＲＥＱＴ（非特許文献１参照。）、ＴｒｅｅＭｉｎｅｒ（非特許文献１２参照。）等が提案されている。また、順序列を有するデータにおいて、各頂点の概念階層が与えられた場合に多頻度パターンを抽出する方法として、非特許文献１３が提案されている。
【０００４】
木構造又はグラフ構造のデータから頻出パターンを検出するデータマイニング技術は、化学物質の分子構造、自然言語における構文解析結果、又は自然言語における語の係り受け構造等、様々な分野に応用可能である。
【非特許文献１】Tatsuya Asai, Kenji Abe, Shinji Kawasoe, Hiroki Arimura, Hiroshi Sakamoto, Setsuo Arikawa, Efficient Substructure Discovery from Large Semi-structured Data, the Proc. of the Second SIAM International Conference on Data Mining(SDM2002), pp.158-174, 2002.
【非特許文献２】Agrawal, R., & Srikant, R.: Fast Algorithm for Mining Association Rules in Large Databases. Proc. of the 20th VLDB, pp. 487-499, 1994.
【非特許文献３】Dehaspe,L.,Toivonen,H.,& King,R.D. Finding frequent substructures in chemical compounds. Proc.of the 4th KDD,  pp.30-36, 1998.
【非特許文献４】De Raedt,L.,& Kramer,S.: The Levelwise Version Space Algorithm and its Application to Molecular Fragment Finding. Proc.of the 17th IJCAI, pp.853-859, 2001.
【非特許文献５】Han, J., & Fu, Y.: Discovery of Multiple-Level Association Rules from Large Databases. Proc. of VLDB conference, pp. 420-431, 1995.
【非特許文献６】Inokuchi,I.,Washio,T.,& Motoda,H.: An Apriori-based Algorithm for Mining Frequent Substructures from Graph Data. Proc.of the 4th PKDD,pp.12-23, 2000.
【非特許文献７】Inokuchi,A.,Washio,T.,Nishimura,Y.,& Motoda,H.: A Fast Algorithm for Mining Frequent Connected Subgraphs.IBM Research Report,RT0448, February,2002.
【非特許文献８】Kuramochi,M.,& Karypis,G.: Frequent Subgraph Discovery. Proc.of the 1st ICDM, 2001.
【非特許文献９】Matsuzawa, H., & Fukuda, T.: Mining Structured Association Patterns from Databases. Proc.of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining.
【非特許文献１０】森本  康彦。空間データベースからの頻出集合数え上げアルゴリズム。第２回データマイニングワークショップ、ｐｐ．１−１０。
【非特許文献１１】Srikant, R., and Agrawal, R.: Mining Generalized Association Rules, Proc. of VLDB conference, pp.407-419, 1995.
【非特許文献１２】Zaki, M.: Efficiently Mining Frequent Trees in a Forest. Proc. of the 8th International Conference on KDD.
【非特許文献１３】Ramakrishnan Srikant, Rakesh Agrawal, Mining Sequential Patterns: Generalizations And Performance Improvements, Proc. 5th Int. Conf. Extending Database Technology, pp.3-17, 1996.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上記に示したグラフマイニング及び木構造マイニングは、バスケット分析の対象をグラフ構造データに拡張した手法である。すなわち、グラフの頂点、辺を各アイテムに対応させ、グラフの頂点ラベル、辺ラベルを各アイテムの種類に対応させたものである。ここでラベル間に階層概念を取り入れて多頻度パターンを抽出する場合、次に示す問題が生じる。
【０００６】
グラフデータの場合には、同じラベルを持つ頂点、辺がグラフの中に複数存在するため、アイテム集合の場合と比較した多頻度パターンの数及び候補の数が膨大となる。更に、ラベルを下位概念及び上位概念でそれぞれ表現したパターンを多頻度パターンの候補として生成していくと、同一の部分グラフにマッチングされる多頻度パターンの候補として、それぞれ異なる頂点ラベル又は辺ラベルが上位概念に置換されたパターンが生成される。このようにして生成された多頻度パターンの候補は膨大な数となり、実現困難である。
【０００７】
そこで本発明は、上記の課題を解決することのできる多頻度パターン抽出装置、多頻度パターン抽出方法、及びそのプログラムと記録媒体を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【０００８】
本発明の第１の形態によると、グラフ構造によりそれぞれ表現された複数の前記オブジェクトのうち、予め定められた最小割合以上の前記オブジェクトにそれぞれ含まれる多頻度部分グラフの組を抽出する多頻度パターン抽出装置であって、前記複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる複数の頂点及び複数の辺のそれぞれを構成要素とするグラフ構造により表現され、予め定められた複数種類の前記構成要素と、前記複数種類の構成要素のいずれにもマッチングされる上位概念要素との対応を格納する概念階層データベースと、既に抽出された前記多頻度部分グラフに前記構成要素又は前記上位概念要素を付加した抽出候補部分グラフの組を生成する抽出候補部分グラフ生成部と、前記複数のオブジェクトのそれぞれにおける前記抽出候補部分グラフにマッチングされる部分グラフの個数を合計した重み付き支持度を算出する重み付き支持度算出部と、第１の前記抽出候補部分グラフに含まれる前記構成要素を、当該構成要素にマッチングされる前記上位概念要素に置き換えた場合に前記第１抽出候補部分グラフと同一の部分グラフとなる第２の抽出候補部分グラフを選択する上位概念候補選択部と、前記第１抽出候補部分グラフの前記重み付き支持度である第１重み付き支持度及び前記第２抽出候補部分グラフの前記重み付き支持度である第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加する多頻度部分グラフ追加部とを備える多頻度パターン抽出装置、多頻度パターン抽出方法、及びそのプログラムと記録媒体を提供する。
【０００９】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明の効果】
【００１０】
本発明によれば、グラフ構造により表現される複数のオブジェクトに共通して含まれる多頻度部分グラフを、頂点又は辺の一部の上位概念化を考慮しつつ効率良く抽出することができる。
【発明を実施するための最良の形態】
【００１１】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００１２】
図１は、本実施形態に係る多頻度パターン抽出装置１０の構成を示す。本実施形態に係る多頻度パターン抽出装置１０は、それぞれがグラフ構造により表現される分析対象の複数のオブジェクトのうち、予め定められた最小割合以上のオブジェクトにそれぞれ含まれる多頻度部分グラフの組を抽出する。これらの複数のオブジェクトのそれぞれは、所定の特性を有するか否かを分析した分析結果に基づいて選択された所定の特性を有するオブジェクトであり、当該オブジェクトに含まれる複数の頂点及び複数の辺のそれぞれを構成要素とする、木構造を含むグラフ構造により表現される。
【００１３】
これらのオブジェクトは、例えば分子構造等の自然物をグラフ構造により表現したものであってよく、これに代えて、例えばインターネットをアクセスするユーザが閲覧したウェブページの閲覧順序や自然言語の構文解析木等のデータ構造をグラフ構造により表現したものであってもよい。
【００１４】
オブジェクトＤＢ１００は、グラフ構造により表現された、所定の特性を有する複数のオブジェクトを格納する。オブジェクトＤＢ管理部１０２は、オブジェクトＤＢ１００を管理し、抽出候補部分グラフ生成部１２０内の支持度算出部１４７又は重み付き支持度算出部１５０からの要求を受けてオブジェクトＤＢ１００に格納されたオブジェクトのグラフデータを返信する。
概念階層ＤＢ１０５は、予め定められた複数種類の構成要素と、複数種類の構成要素のいずれにもマッチングされる上位概念要素との対応を格納する。
【００１５】
多頻度部分グラフＤＢ１１０は、オブジェクトＤＢ１００に格納された複数のオブジェクトのうち、予め定められた最小割合以上のオブジェクトにそれぞれ含まれる多頻度部分グラフの組を、当該多頻度部分グラフに含まれる構成要素の数に基づいて定められた大きさの値に対応付けて格納する。ここで、上記の予め定められた最小割合を示す指標を最小支持度と呼び、補足説明の定義６に記載した支持度の最小値としてユーザ等により指定される。多頻度部分グラフＤＢ管理部１１５は、多頻度部分グラフＤＢ１１０を管理し、抽出候補部分グラフ生成部１２０からの要求を受けて多頻度部分グラフＤＢ１１０に格納された多頻度部分グラフを抽出候補部分グラフ生成部１２０へ供給する。また、多頻度部分グラフＤＢ管理部１１５は、多頻度部分グラフ追加部１７０からの要求を受けて、新たに生成された多頻度部分グラフを多頻度部分グラフＤＢ１１０へ格納する。
【００１６】
抽出候補部分グラフ生成部１２０は、多頻度部分グラフが抽出されていない初期状態の場合、構成要素又は上位概念要素を抽出候補部分グラフの組として生成する。また抽出候補部分グラフ生成部１２０は、初期状態でない場合、既に抽出された多頻度部分グラフを多頻度部分グラフＤＢ１１０から取得し、当該多頻度部分グラフに構成要素又は上位概念要素を付加した抽出候補部分グラフの組を生成する。抽出候補部分グラフ生成部１２０は、多頻度部分グラフ検索部１２５及び抽出候補部分グラフ選択部１３０を有する。
【００１７】
多頻度部分グラフ検索部１２５は、第１の大きさを検索キーとして多頻度部分グラフＤＢ管理部１１５を介して多頻度部分グラフＤＢ１１０を検索し、第１の大きさを有する多頻度部分グラフを多頻度部分グラフＤＢ１１０から取得する。抽出候補部分グラフ選択部１３０は、検索された多頻度部分グラフに構成要素又は上位概念要素を付加して第１の大きさより大きい第２の大きさとした部分グラフを、抽出候補部分グラフとして選択する。本実施形態に係る抽出候補部分グラフ選択部１３０は、支持度が最小支持度以上であることを条件として抽出候補部分グラフとして選択する。ここで支持度とは、当該部分グラフにマッチングされる部分グラフを含むオブジェクトの割合を示す指標であり、例えば後述する補足説明の定義６により規定される。
【００１８】
抽出候補部分グラフ選択部１３０は、既に抽出された一の多頻度部分グラフに一の構成要素を付加した多頻度グラフ候補を生成する構成要素付加部１３５と、当該一の構成要素を検索キーとして、当該一の構成要素にマッチングされる一の上位概念要素を概念階層ＤＢ１０５から検索する上位概念要素検索部１４０と、当該一の多頻度部分グラフに当該一の上位概念要素を付加した抽出候補部分グラフを生成する上位概念要素付加部１４５と、生成した抽出候補部分グラフの支持度を算出する支持度算出部１４７とを含む。ここで、抽出候補部分グラフ選択部１３０は、既に抽出された一の多頻度部分グラフに、構成要素付加部１３５により構成要素を付加し、又は、上位概念要素付加部１４５により上位概念要素を付加した部分グラフを生成し、支持度算出部１４７により算出した当該部分グラフの支持度が最小支持度以上であることを条件として抽出候補部分グラフとして選択する。
【００１９】
重み付き支持度算出部１５０は、抽出候補部分グラフ生成部１２０により生成された抽出候補部分グラフのそれぞれの重み付き支持度を算出する。より具体的には、重み付き支持度算出部１５０は、オブジェクトＤＢ管理部１０２を介してオブジェクトＤＢ１００から複数のオブジェクトを順次取得し、それぞれのオブジェクトに含まれる、抽出候補部分グラフにマッチングされる部分グラフの個数を計数する。そして重み付き支持度算出部１５０は、計数した個数を全てのオブジェクトについて合計して重み付き支持度を算出する。ここで重み付き支持度とは、複数のオブジェクトのそれぞれにおける抽出候補部分グラフにマッチングされる部分グラフの個数を合計した値であり、例えば後述する補足説明の定義７により規定される。
【００２０】
抽出候補部分グラフＤＢ１５５は、重み付き支持度算出部１５０から受け取った抽出候補部分グラフと、支持度算出部１４７により算出された当該抽出候補部分グラフの支持度と、重み付き支持度算出部１５０により算出された当該抽出候補部分グラフの重み付き支持度とを対応付けて格納する。抽出候補部分グラフＤＢ管理部１６０は、抽出候補部分グラフＤＢ１５５を管理し、抽出候補部分グラフと、当該抽出候補部分グラフの支持度及び重み付き支持度とを重み付き支持度算出部１５０から取得して抽出候補部分グラフＤＢ１５５に格納させる。
【００２１】
上位概念候補選択部１６５は、抽出候補部分グラフＤＢ管理部１６０を介して抽出候補部分グラフＤＢ１５５から抽出候補部分グラフを取得し、当該抽出候補部分グラフに対応付けて格納された支持度及び重み付け支持度と共に多頻度部分グラフ追加部１７０へ供給する。この際に上位概念候補選択部１６５は、ある第１の抽出候補部分グラフの重み付き支持度と第２の抽出候補部分グラフの重み付き支持度とが同一であり、かつ、第２抽出候補部分グラフが第１抽出候補部分グラフの上位概念パターンとなる場合に、第２抽出候補部分グラフを過度に上位概念化された抽出候補部分グラフとして選択し、過度に上位概念化されたことを示す情報と共に多頻度部分グラフ追加部１７０へ供給する。
【００２２】
多頻度部分グラフ追加部１７０は、上位概念候補選択部１６５から供給された抽出候補部分グラフを、多頻度部分グラフＤＢ管理部１１５を介して多頻度部分グラフＤＢ１１０へ格納することにより、多頻度部分グラフの組に追加する。ここで、上位概念候補選択部１６５により過度に上位概念化されたものとして選択された第２抽出候補部分グラフについては、多頻度部分グラフＤＢ１１０へ格納せずに多頻度部分グラフの組から取り除く。これにより多頻度部分グラフ追加部１７０は、対応する第１抽出候補部分グラフの重み付き支持度である第１重み付き支持度及び第２抽出候補部分グラフの重み付き支持度である第２重み付き支持度が同一でないことを条件として、第２抽出候補部分グラフを多頻度部分グラフの組に追加する。一方、第１抽出候補部分グラフは支持度が最小支持度以上のものが抽出候補部分グラフ生成部１２０により選択されているため、多頻度部分グラフ追加部１７０は、第１抽出候補部分グラフを多頻度部分グラフの組に追加する。
【００２３】
入出力部１８０は、多頻度部分グラフを抽出する対象である複数のオブジェクト、及び、構成要素と上位概念要素の対応付けを多頻度パターン抽出装置１０の利用者又は他の情報処理装置等から入力し、オブジェクトＤＢ１００、及び概念階層ＤＢ１０５に格納する。また入出力部１８０は、抽出すべき多頻度部分グラフの最小支持度を多頻度パターン抽出装置１０の利用者又は他の情報処理装置等から入力し、抽出候補部分グラフ生成部１２０内の構成要素付加部１３５及び上位概念要素付加部１４５へ供給する。そして多頻度パターン抽出装置１０による多頻度部分グラフの抽出が完了すると、入出力部１８０は、抽出した多頻度部分グラフを多頻度部分グラフＤＢ管理部１１５を介してオブジェクトＤＢ１００から取得し、多頻度パターン抽出装置１０の利用者又は他の情報処理装置等に出力する。
【００２４】
以上に示した多頻度パターン抽出装置１０によれば、多頻度部分グラフ追加部１７０は、第１抽出候補部分グラフを多頻度部分グラフの組に追加すること、及び、第１重み付き支持度及び第２重み付き支持度が同一でないことを条件として、第２抽出候補部分グラフを多頻度部分グラフの組に追加する。この結果、多頻度部分グラフ追加部１７０は、第１抽出候補部分グラフの上位概念パターンで、かつ支持度が同一となる第２抽出候補部分グラフを多頻度部分グラフＤＢ１１０に格納しない。ここで後述する補足説明の定理３から、第２抽出候補部分グラフが第１抽出候補部分グラフの上位概念パターンで、かつ、第１重み付き支持度及び第２重み付き支持度が同一である場合、第１抽出候補部分グラフ及び第２抽出候補部分グラフを同型拡張して生成された全ての部分グラフ同士の支持度が等しくなる。したがって多頻度部分グラフ追加部１７０は、このような条件を満たす第２抽出候補部分グラフを探索の途中で取り除くことで、後述する補足説明の定義９に示した、過度に上位概念化された多頻度部分グラフを取り除き、探索空間の大きな範囲を枝刈りすることができる。これにより多頻度パターン抽出装置１０は、多頻度部分グラフを効率良く抽出することができる。
【００２５】
図２は、本実施形態に係るオブジェクトＤＢ１００に格納される情報の一例を示す。オブジェクトＤＢ１００は、複数のオブジェクトのそれぞれのグラフデータを、当該オブジェクトを識別するオブジェクトＩＤ（Identifier：識別情報）に対応付けて格納する。
【００２６】
本実施形態において、複数のオブジェクトのそれぞれは、所定の特性の一例として薬品としての所定の効用を有することを実験により分析した分析結果に基づいて選択された化学物質である。複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる複数の頂点が当該オブジェクトに含まれる複数の原子に対応し、当該オブジェクトに含まれる複数の辺が複数の原子間の結合に対応する。
【００２７】
本実施形態に係るオブジェクトＤＢ１００は、抗ＨＩＶ（Human Immunodeficiency Virus）性を有することを実験により分析した分析結果に基づいて、薬品としての効用として抗ＨＩＶ性を有する複数のオブジェクトを、当該オブジェクトの分子構造がグラフ構造により表現されたグラフデータとして格納する。例えばオブジェクトＤＢ１００は、抗ＨＩＶ性を有する化学物質として、抗ＨＩＶ性を有することが分析の結果確認されたアジドチミジンをオブジェクトＩＤ１に対応付けて格納する。
【００２８】
図３は、本実施形態に係る概念階層ＤＢ１０５に格納される情報の一例を示す。本実施形態に係る概念階層ＤＢ１０５は、複数種類の構成要素と上位概念要素との対応の一例として、予め定められた複数種類の原子と、複数種類の原子のいずれにもマッチングされる上位概念原子との対応を格納する。
【００２９】
例えば概念階層ＤＢ１０５は、複数のオブジェクトの構成要素である、芳香環における炭素原子（芳香環Ｃ）及び非芳香環における炭素原子（非芳香環Ｃ）と、上位概念要素である炭素原子（Ｃ）との対応を格納する。ここで、ある抽出候補部分グラフが上位概念要素である炭素原子Ｃを含む場合、この抽出候補部分グラフは、当該上位概念要素を芳香環Ｃとした部分グラフを含むオブジェクトと、当該上位概念要素を非芳香環Ｃとした部分グラフを含むオブジェクトの両方にマッチングされる。
【００３０】
また概念階層ＤＢ１０５は、複数種類の上位概念要素のそれぞれを構成要素とし、これらの複数種類の構成要素と、複数種類の構成要素のいずれにもマッチングされる更なる上位概念要素との対応を格納してもよい。例えば概念階層ＤＢ１０５は、上位概念要素である炭素原子Ｃ、窒素原子Ｎ、及び酸素原子Ｏを構成要素とし、これらの複数種類の構成要素と、これらの複数種類の構成要素のいずれにもマッチングされる上位概念要素Ｘとの対応を格納する。
【００３１】
また概念階層ＤＢ１０５は、一の構成要素と、当該一の構成要素にマッチングされる第１の上位概念要素及び第２の上位概念要素との対応を更に格納してよい。例えば概念階層ＤＢ１０５は、芳香環Ｃと、芳香環Ｃにマッチングされる第１の上位概念要素である炭素原子Ｃとの対応と、芳香環Ｃと、芳香環Ｃにマッチングされる第２の上位概念要素である芳香環原子との対応とを更に格納する。
【００３２】
以上に示した通り、本実施形態に係る概念階層ＤＢ１０５は、複数種類の頂点と、複数種類の頂点のいずれにもマッチングされる上位概念要素との対応を格納するが、他の例においては、これに代えて複数種類の辺と、複数種類の辺のいずれにもマッチングされる上位概念要素との対応を格納してもよい。
【００３３】
図４は、本実施形態に係る多頻度部分グラフＤＢ１１０に格納される情報の一例を示す。本実施形態において多頻度部分グラフＤＢ１１０は、オブジェクトＤＢ１００に格納された複数のオブジェクトに最小支持度以上の支持度で含まれる多頻度部分グラフを、当該多頻度部分グラフを識別する多頻度部分グラフＩＤ、当該多頻度部分グラフの大きさ、支持度、及び重み付き支持度に対応付けて格納する。
【００３４】
多頻度部分グラフの大きさフィールドは、例えば後述する補足説明の定義１に記載したように、構成要素の数に基づき定められた値である。例えば多頻度部分グラフＩＤｘに対応付けて格納された多頻度部分グラフ４００は、多頻度部分グラフ４００の構成要素である原子の数が１７個であることから、当該多頻度部分グラフの大きさとして１７が格納される。これに代えて、多頻度部分グラフの大きさは、辺の数や、頂点及び辺の合計数等に基づいて定められてよい。
【００３５】
多頻度部分グラフの支持度フィールドは、対応する多頻度部分グラフについて支持度算出部１４７により算出された支持度sup(Gsx)を格納する。多頻度部分グラフの重み付き支持度フィールドは、対応する多頻度部分グラフについて重み付き支持度算出部１５０により算出された重み付き支持度supw(Gsx)を格納する。
【００３６】
本実施形態に係る多頻度パターン抽出装置１０において、多頻度部分グラフ追加部１７０は、抽出候補部分グラフ生成部１２０により生成された抽出候補部分グラフを多頻度部分グラフＤＢ１１０に格納する。ここで、多頻度部分グラフ追加部１７０は、ある第１抽出候補部分グラフの上位概念パターンとなる第２抽出候補部分グラフについては、第１抽出候補部分グラフの重み付き支持度及び第２抽出候補部分グラフの重み付き支持度が同一でないことを条件として、多頻度部分グラフの組に追加する。これにより多頻度部分グラフ追加部１７０は、過度に上位概念化された抽出候補部分グラフを探索の途中で取り除くことができ、効率良く所定の効用を有する化学物質に共通して含まれる部分構造の組を生成することができる。
【００３７】
図５は、本実施形態に係る抽出候補部分グラフＤＢ１５５に格納される情報の一例を示す。本実施形態において抽出候補部分グラフＤＢ１５５は、抽出候補部分グラフ生成部１２０により生成された抽出候補部分グラフを、支持度算出部１４７により算出された当該抽出候補部分グラフの支持度及び重み付き支持度算出部１５０により算出された当該多頻度部分グラフの重み付き支持度に対応付けて格納する。
【００３８】
抽出候補部分グラフの大きさフィールド、支持度フィールド、及び重み付き支持度フィールドは、図４に示した多頻度部分グラフの大きさ、支持度、及び重み付き支持度とそれぞれ同様に定められる抽出候補部分グラフの大きさ、支持度、及び重み付き支持度を格納する。
【００３９】
抽出候補部分グラフ５００及び抽出候補部分グラフ５２０は、抽出候補部分グラフ生成部１２０により生成され、抽出候補部分グラフＤＢ１５５に格納される多頻度部分候補の一例である。すなわち、本実施形態において抽出候補部分グラフ生成部１２０は、所定の効用を有する化学物質の部分構造として既に抽出された多頻度部分グラフに原子又は上位概念原子を付加した抽出候補部分グラフ５００及び抽出候補部分グラフ５２０等の抽出候補部分グラフの組を生成する。
【００４０】
より具体的には、多頻度部分グラフ検索部１２５は、第１の大きさの一例である大きさ１７の多頻度部分グラフ４００を多頻度部分グラフＤＢ１１０から検索し、構成要素付加部１３５は、検索された多頻度部分グラフ４００に構成要素５１０を付加して抽出候補部分グラフ５００を生成する。上位概念要素検索部１４０は、構成要素５１０にマッチングされる上位概念要素５３０を概念階層ＤＢ１０５から検索し、上位概念要素付加部１４５は、検索された多頻度部分グラフ４００に上位概念要素５３０を付加して抽出候補部分グラフ５２０を生成する。この結果抽出候補部分グラフ５２０は、抽出候補部分グラフ５００の上位概念パターンとなる。以上の処理の結果抽出候補部分グラフ選択部１３０は、第１の大きさ１７より大きい第２の大きさ１８とした部分グラフである抽出候補部分グラフ５００及び抽出候補部分グラフ５２０を抽出候補部分グラフとして選択することができる。
【００４１】
図６は、本実施形態に係る多頻度パターン抽出装置１０の動作フローを示す。
多頻度部分グラフの抽出を開始する前に、入出力部１８０は、複数のオブジェクトを入力し、オブジェクトＤＢ管理部１０２を介してオブジェクトＤＢ１００に格納する。また、入出力部１８０は、構成要素と上位概念要素の対応付けを入力し、概念階層ＤＢ１０５に格納する。更に、入出力部１８０は、抽出すべき多頻度部分グラフの最小支持度を入力し、支持度算出部１４７に供給する。そして、多頻度パターン抽出装置１０は、多頻度部分グラフＤＢ１１０に多頻度部分グラフが格納されていない状態として、多頻度部分グラフの抽出を開始する。
【００４２】
多頻度部分グラフの抽出を開始すると、抽出候補部分グラフ生成部１２０は、大きさ１の抽出候補部分グラフを１又は複数生成し、重み付き支持度算出部１５０を介して抽出候補部分グラフＤＢ管理部１６０により抽出候補部分グラフＤＢ１５５に格納させる（ステップＳ６００）。
より具体的には、多頻度部分グラフＤＢ１１０に多頻度部分グラフが格納されていないため、構成要素付加部１３５は、１又は複数の構成要素のそれぞれを、大きさ１の抽出候補部分グラフとして生成する。構成要素付加部１３５が生成した１又は複数の抽出候補部分グラフのそれぞれについて、上位概念要素検索部１４０は、当該抽出候補部分グラフとなった構成要素にマッチングされる上位概念要素を概念階層ＤＢ１０５から検索する。上位概念要素付加部１４５は、上位概念要素検索部１４０により検索された１又は複数の上位概念要素のそれぞれを、大きさ１の抽出候補部分グラフとして生成する。
【００４３】
次に、多頻度パターン抽出装置１０は、大きさk=1の抽出候補部分グラフの組C1から順に（Ｓ６０５）、大きさkを有する抽出候補部分グラフの組Ckから大きさkを有する多頻度部分グラフの組Fkを生成し、多頻度部分グラフの組Fkから大きさk+1を有する抽出候補部分グラフの組Ck+1を生成していく繰り返し処理を行う（Ｓ６１０、Ｓ６６０）。
【００４４】
支持度算出部１４７は、第１の大きさk-1を有する多頻度部分グラフの組Fk-1から構成要素付加部１３５又は上位概念要素付加部１４５により生成された抽出候補部分グラフの組Ckに含まれる各抽出候補部分グラフckの支持度sup(G(ck))を算出する（Ｓ６１５）。そして支持度算出部１４７は、支持度sup(G(ck))が最小支持度minsup以上であることを条件として抽出候補部分グラフとして残し、支持度sup(G(ck))が最小支持度minsup未満のものについては抽出候補部分グラフから除外して、抽出候補部分グラフＤＢ１５５に格納すべき抽出候補部分グラフの組Fkを出力する（Ｓ６２０）。
【００４５】
次に、重み付き支持度算出部１５０は、支持度算出部１４７から出力された、第２の大きさkを有する各抽出候補部分グラフの重み付き支持度を算出する（Ｓ６２３）。そして重み付き支持度算出部１５０は、抽出候補部分グラフを、当該抽出候補部分グラフの支持度及び重み付き支持度に対応付けて抽出候補部分グラフＤＢ１５５に格納する。これに代えて、重み付き支持度算出部１５０は、Ｓ６１５において、構成要素付加部１３５又は上位概念要素付加部１４５により生成された抽出候補部分グラフの組Ckに含まれる各抽出候補部分グラフckの全てについて重み付き支持度を算出し、その後Ｓ６２０の処理を行って抽出候補部分グラフＤＢ１５５に格納すべき抽出候補部分グラフの組Fkを出力してもよい。
【００４６】
次に、上位概念候補選択部１６５及び多頻度部分グラフ追加部１７０は、抽出候補部分グラフＤＢ１５５に格納された大きさkの抽出候補部分グラフの組Fkに含まれる２つの抽出候補部分グラフP1及びP2の組み合わせのそれぞれについて、次の処理を行う（Ｓ６２５、Ｓ６４３）。
まず、上位概念候補選択部１６５は、第１抽出候補部分グラフP1の重み付き支持度である第１重み付き支持度supw(P1)と第２抽出候補部分グラフP2の重み付き支持度である第２重み付き支持度supw(P2)が同一でない場合に、当該第１抽出候補部分グラフP1及び当該第２抽出候補部分グラフP2についての処理を終え、次の組み合わせに処理を進める（Ｓ６３０：Ｎｏ）。
また、第１重み付き支持度supw(P1)及び第２重み付き支持度supw(P2)が同一である場合であって（Ｓ６３０：Ｙｅｓ）、上位概念候補選択部１６５は、第２抽出候補部分グラフP2が第１抽出候補部分グラフP1の上位概念パターンでない場合に、当該第１抽出候補部分グラフP1及び当該第２抽出候補部分グラフP2についての処理を終え、次の組み合わせに処理を進める（Ｓ６３５：Ｎｏ）。
【００４７】
一方、第２抽出候補部分グラフP2が第１抽出候補部分グラフP1の上位概念パターンである場合に（Ｓ６３５：Ｙｅｓ）、上位概念候補選択部１６５は、第２抽出候補部分グラフP2を、過度に上位概念化された抽出候補部分グラフとして選択する。ここで、第２抽出候補部分グラフP2が第１抽出候補部分グラフP1の上位概念パターンであるとは、第１抽出候補部分グラフP1に含まれる構成要素を、当該構成要素にマッチングされる上位概念要素に置き換えた場合に第１抽出候補部分グラフP1と同一の部分グラフとなっていることを示す。
【００４８】
次に、多頻度部分グラフ追加部１７０は、抽出候補部分グラフＤＢ管理部１６０及び上位概念候補選択部１６５を介して第２の大きさの抽出候補部分グラフの組Fkを取得する。そして多頻度部分グラフ追加部１７０は、上位概念候補選択部１６５によりある第１抽出候補部分グラフP1が過度に上位概念化された抽出候補部分グラフとして選択された第２抽出候補部分グラフP2を、抽出候補部分グラフの組Fkから取り除く（Ｓ６４０）。この結果多頻度部分グラフ追加部１７０は、第１抽出候補部分グラフP1の第１重み付き支持度supw(P1)及び第２抽出候補部分グラフP2の第２重み付き支持度supw(P2)が同一であり、かつ、第１抽出候補部分グラフP1の上位概念パターンである第２抽出候補部分グラフP2を抽出候補部分グラフの組Fkから取り除く。
【００４９】
そして、多頻度部分グラフ追加部１７０は、Ｓ６２５からＳ６４３の処理の結果得られた、抽出候補部分グラフの組Fkのうち第２抽出候補部分グラフP2を除く抽出候補部分グラフを、当該抽出候補部分グラフの大きさk、支持度sup(P1)及び／又はsup(P2)、及び重み付き支持度supw(P1)及び／又はsupw(P2)に対応付けて多頻度部分グラフＤＢ１１０に格納する（Ｓ６４５）。この様にして多頻度部分グラフ追加部１７０は、第１抽出候補部分グラフP1の上位概念パターンである第２抽出候補部分グラフP2については、第１抽出候補部分グラフP1の第１重み付き支持度supw(P1)及び第２抽出候補部分グラフP2の第２重み付き支持度supw(P2)が同一でないことを条件として多頻度部分グラフの組に追加する。
【００５０】
次に、抽出候補部分グラフ生成部１２０は、第１の大きさkの多頻度部分グラフから、第１の大きさより大きい第２の大きさk+1の抽出候補部分グラフを生成し、重み付き支持度算出部１５０を介して抽出候補部分グラフＤＢ管理部１６０により抽出候補部分グラフＤＢ１５５に格納させる（Ｓ６５０）。
より具体的には、構成要素付加部１３５は、第１の大きさkを有する１又は複数の多頻度部分グラフを多頻度部分グラフＤＢ１１０から検索する。次に、構成要素付加部１３５は、検索された一の多頻度部分グラフに一の構成要素を付加した多頻度グラフ候補を生成する。次に、上位概念要素検索部１４０は、当該一の構成要素を検索キーとして、当該一の構成要素にマッチングされる一の上位概念要素を概念階層ＤＢ１０５から検索する。次に、上位概念要素付加部１４５は、当該一の多頻度部分グラフに、上位概念要素検索部１４０が検索した一の上位概念要素を付加した抽出候補部分グラフを生成する。これにより、抽出候補部分グラフ生成部１２０は、第２の大きさk+1の抽出候補部分グラフの組Ck+1を生成する。
【００５１】
次に、多頻度パターン抽出装置１０は、処理対象となる抽出候補部分グラフの大きさをインクリメントし（Ｓ６５５）、新たな多頻度部分グラフが生成されなくなるまでＳ６１０からＳ６６０を繰り返し処理する（Ｓ６６０）。Ｓ６１０からＳ６６０までの繰り返し処理を終えると、多頻度パターン抽出装置１０は後処理を行い、過度に上位概念化された多頻度部分グラフであって探索途中で枝刈りできなかったものを多頻度部分グラフＤＢ１１０から削除する（Ｓ６６５）。
【００５２】
以上に示した多頻度パターン抽出装置１０によれば、多頻度部分グラフ追加部１７０は、第１抽出候補部分グラフを多頻度部分グラフの組に追加すること、及び、第１重み付き支持度及び第２重み付き支持度が同一でないことを条件として、第２抽出候補部分グラフを多頻度部分グラフの組に追加する。この結果、多頻度パターン抽出装置１０は、探索の途中で以後同型拡張した場合において第１抽出候補部分グラフが過度に上位概念化された上位概念パターンである第２抽出候補部分グラフを枝刈りすることができる。
【００５３】
以上に示したＳ６４３において、多頻度パターン抽出装置１０は、上記の第２抽出候補部分グラフの枝刈りに加え、次に示す枝刈りを行ってもよい。すなわち、上記のＳ６４３の処理に加え、上位概念候補選択部１６５は、第１抽出候補部分グラフに含まれる構成要素を当該構成要素にマッチングされる上位概念要素に置き換えた場合に第１抽出候補部分グラフと同一の部分グラフとなる、第２抽出候補部分グラフと異なる第３の抽出候補部分グラフを更に選択する。そして、多頻度部分グラフ追加部１７０は、第２重み付き支持度及び第３抽出候補部分グラフの重み付き支持度である第３重み付き支持度が同一、かつ、複数のオブジェクトのそれぞれについて、当該オブジェクトにおける第２抽出候補部分グラフにマッチングされる部分グラフの組と当該オブジェクトにおける第３抽出候補部分グラフにマッチングされる部分グラフの組とが同一である場合に、第１重み付き支持度及び第２重み付き支持度が同一でないことを条件として第２抽出候補部分グラフを多頻度部分グラフの組に追加し、第３抽出候補部分グラフを多頻度部分グラフの組に追加しない。
【００５４】
以上に示した処理を更に加えることにより、第１抽出候補部分グラフの複数の上位概念パターン同士が重複する場合に、重複する上位概念パターンを探索途中で取り除くことができ、多頻度部分グラフを更に効率良く抽出することができる。
【００５５】
図７は、本実施形態の第１変形例に係るオブジェクトＤＢ１００に格納される情報の一例を示す。本変形例における多頻度パターン抽出装置１０の構成及び動作は、図１に示す多頻度パターン抽出装置１０の構成及び動作とほぼ同様であるため、以下相違点を除き説明を省略する。
【００５６】
第１変形例に係るオブジェクトＤＢ１００は、所定の特性を有する複数のオブジェクトのそれぞれとして、当該オブジェクトに含まれる複数の頂点が閲覧されたウェブページに対応し、当該オブジェクトに含まれる複数の辺がウェブページの閲覧順序を示すワールド・ワイド・ウェブサイトの閲覧履歴を格納する。また、概念階層ＤＢ１０５は、複数種類の構成要素と、複数種類の構成要素のいずれにもマッチングされる上位概念要素との対応として、予め定められた複数種類のウェブページと、複数種類のウェブページのいずれにもマッチングされる上位概念ウェブページとの対応を格納する。
【００５７】
ここでオブジェクトＤＢ１００は、例えば利用者が１以上のウェブページを順に閲覧した結果、所定の行動を行った場合に、所定の特性を有するものとして閲覧履歴をオブジェクトＤＢ１００に格納してよい。ここで、所定の行動とは、例えば利用者があるウェブページをアクセスしたことや、利用者があるウェブページを介して商品又はサービス等を購入したこと等であってよい。
【００５８】
抽出候補部分グラフ生成部１２０は、所定の特性を有する閲覧履歴の部分構造として既に抽出された多頻度部分グラフに、構成要素であるウェブページ又は上位概念要素である上位概念ウェブページを付加した抽出候補部分グラフの組を生成する。多頻度部分グラフ検索部１２５及び抽出候補部分グラフ選択部１３０は、ウェブページを構成要素とし、上位概念ウェブページを上位概念要素として、図１から図６に示した処理を行う。
【００５９】
重み付き支持度算出部１５０は、複数のオブジェクトのそれぞれにおける抽出候補部分グラフにマッチングされる部分グラフの個数を合計した重み付き支持度を算出する。上位概念候補選択部１６５は、ある第１抽出候補部分グラフに含まれる構成要素であるウェブページを当該ウェブページにマッチングされる上位概念要素である上位概念ウェブページに置き換えた場合に、第１抽出候補部分グラフと同一の部分構造を示す部分グラフとなる第２抽出候補部分グラフ、すなわち第１抽出候補部分グラフの上位概念パターンとなる第２抽出候補部分グラフを選択する。多頻度部分グラフ追加部１７０は、第１抽出候補部分グラフの重み付き支持度及び第２多頻度部分グラフの重み付き支持度が同一でないことを条件として、第２抽出候補部分グラフを多頻度部分グラフの組に追加することにより、所定の特性を有する閲覧履歴に共通して含まれる部分構造である多頻度部分グラフの組を生成する。
【００６０】
以上に示した第１変形例に係る多頻度パターン抽出装置１０によれば、所定の特性を有する複数のウェブページの閲覧履歴を対象として、複数の閲覧履歴のうち、最小支持度以上の閲覧履歴に含まれる閲覧順序の部分グラフである多頻度部分グラフの組を抽出することができる。これにより、多頻度パターン抽出装置１０は、利用者の特定の行動に結びつきやすい閲覧順序を抽出することができ、ワールド・ワイド・ウェブサイトを用いたマーケティング等を支援することができる。
【００６１】
図８は、本実施形態の第２変形例に係るオブジェクトＤＢ１００に格納される情報の一例を示す。本変形例における多頻度パターン抽出装置１０の構成及び動作は、図１に示す多頻度パターン抽出装置１０の構成及び動作とほぼ同様であるため、以下相違点を除き説明を省略する。
【００６２】
第２変形例に係るオブジェクトＤＢ１００は、所定の特性を有する複数のオブジェクトのそれぞれとして、当該オブジェクトに含まれる複数の頂点が当該オブジェクトに含まれる複数の語句に対応し、当該オブジェクトに含まれる複数の辺が複数の語句間の順序に対応する文章を示すオブジェクトを格納する。ここで、これらの複数の文章のそれぞれは、複数の文章のそれぞれは、当該文章が所定のジャンル、すなわち例えば政治、経済、文芸、又はスポーツ等、に分類されるべきことを分析した分析結果に基づいて選択される。概念階層ＤＢ１０５は、予め定められた複数種類の語句と、複数種類の語句のいずれにもマッチングされる上位概念語句との対応を、複数種類の構成要素と、複数種類の構成要素のいずれにもマッチングされる上位概念要素との対応として格納する。
【００６３】
抽出候補部分グラフ生成部１２０は、所定のジャンルに分類される文章の部分構造として既に抽出された多頻度部分グラフに、構成要素である語句又は上位概念要素である上位概念語句を付加した抽出候補部分グラフの組を生成する。多頻度部分グラフ検索部１２５及び抽出候補部分グラフ選択部１３０は、語句を構成要素とし、上位概念語句を上位概念要素として、図１から図６に示した処理を行う。
【００６４】
重み付き支持度算出部１５０は、複数のオブジェクトのそれぞれにおける抽出候補部分グラフにマッチングされる部分グラフの個数を合計した重み付き支持度を算出する。上位概念候補選択部１６５は、第１抽出候補部分グラフと、第１抽出候補部分グラフに含まれる語句を当該語句にマッチングされる上位概念語句に置き換えた場合に第１抽出候補部分グラフと同一の部分構造を示す部分グラフとなる第２抽出候補部分グラフ、すなわち第１抽出候補部分グラフの上位概念パターンとなる第２抽出候補部分グラフとを選択する。多頻度部分グラフ追加部１７０は、第１多頻度部分グラフの重み付き支持度及び第２多頻度部分グラフの重み付き支持度が同一でないことを条件として、第２抽出候補部分グラフを多頻度部分グラフの組に追加することにより、所定のジャンルの文章に共通して含まれる部分構造の組を生成する。
【００６５】
以上に示した第２変形例に係る多頻度パターン抽出装置１０によれば、所定の特性を有する複数の文章を対象として、複数の文章のうち、最小支持度以上の文章に含まれる語句の組を示す部分グラフである多頻度部分グラフを抽出することができる。これにより、多頻度パターン抽出装置１０は、所定のジャンルに分類される複数の文章に多く含まれる語句の組を抽出することができ、ニュース記事の分類等を支援することができる。
【００６６】
図９は、本実施形態に係るコンピュータ１０００のハードウェア構成の一例を示す。本実施形態に係るコンピュータ１０００は、ホスト・コントローラ９８２により相互に接続されるＣＰＵ９００、ＲＡＭ９２０、グラフィック・コントローラ９７５、及び表示装置９８０を有するＣＰＵ周辺部と、入出力コントローラ９８４によりホスト・コントローラ９８２に接続される通信インターフェイス９３０、記憶装置９４０、及びＣＤ−ＲＯＭドライブ９６０を有する入出力部と、入出力コントローラ９８４に接続されるＲＯＭ９１０、フレキシブルディスク・ドライブ９５０、及び入出力チップ９７０を有するレガシー入出力部とを備える。
【００６７】
ホスト・コントローラ９８２は、ＲＡＭ９２０と、高い転送レートでＲＡＭ９２０をアクセスするＣＰＵ９００及びグラフィック・コントローラ９７５とを接続する。ＣＰＵ９００は、ＲＯＭ９１０及びＲＡＭ９２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ９７５は、ＣＰＵ９００等がＲＡＭ９２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置９８０上に表示させる。これに代えて、グラフィック・コントローラ９７５は、ＣＰＵ９００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。
【００６８】
入出力コントローラ９８４は、ホスト・コントローラ９８２と、比較的高速な入出力装置である通信インターフェイス９３０、記憶装置９４０、ＣＤ−ＲＯＭドライブ９６０を接続する。通信インターフェイス９３０は、ネットワークを介して他の装置と通信する。記憶装置９４０は、コンピュータ１０００内のＣＰＵ９００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ９６０は、ＣＤ−ＲＯＭ９９５からプログラム又はデータを読み取り、ＲＡＭ９２０を介して記憶装置９４０に提供する。
【００６９】
また、入出力コントローラ９８４には、ＲＯＭ９１０と、フレキシブルディスク・ドライブ９５０や入出力チップ９７０等の比較的低速な入出力装置とが接続される。ＲＯＭ９１０は、コンピュータ１０００が起動時に実行するブート・プログラムや、コンピュータ１０００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ９５０は、フレキシブルディスク９９０からプログラム又はデータを読み取り、ＲＡＭ９２０を介して記憶装置９４０に提供する。入出力チップ９７０は、フレキシブルディスク・ドライブ９５０や、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を接続する。
【００７０】
ＲＡＭ９２０を介して記憶装置９４０に提供されるプログラムは、フレキシブルディスク９９０、ＣＤ−ＲＯＭ９９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ９２０を介してコンピュータ１０００内の記憶装置９４０にインストールされ、ＣＰＵ９００において実行される。
【００７１】
コンピュータ１０００にインストールされてコンピュータ１０００を多頻度パターン抽出装置１０として機能させるプログラムは、オブジェクトＤＢ管理モジュールと、多頻度部分グラフＤＢ管理モジュールと、抽出候補部分グラフ生成モジュールと、重み付き支持度算出モジュールと、抽出候補部分グラフＤＢ管理モジュールと、上位概念候補選択モジュールと、多頻度部分グラフ追加モジュールと、入出力モジュールとを備える。これらのプログラム及びモジュールは、コンピュータ１０００を、オブジェクトＤＢ管理部１０２、多頻度部分グラフＤＢ管理部１１５、抽出候補部分グラフ生成部１２０、重み付き支持度算出部１５０、抽出候補部分グラフＤＢ管理部１６０、上位概念候補選択部１６５、及び多頻度部分グラフ追加部１７０としてそれぞれ機能させる。抽出候補部分グラフ生成モジュールは、多頻度部分グラフ検索モジュールと、構成要素付加モジュール、上位概念要素検索モジュール、上位概念要素付加モジュール、及び支持度算出モジュールとを含む抽出候補部分グラフ選択モジュールとを有する。これらのプログラム又はモジュールは、コンピュータ１０００を、多頻度部分グラフ検索部１２５と、構成要素付加部１３５、上位概念要素検索部１４０、上位概念要素付加部１４５、及び支持度算出部１４７を含む抽出候補部分グラフ選択部１３０としてそれぞれ機能させる。
また、記憶装置９４０は、オブジェクトＤＢ１００、概念階層ＤＢ１０５、多頻度部分グラフＤＢ１１０、及び抽出候補部分グラフＤＢ１５５としてそれぞれ機能する。
【００７２】
以上に示したプログラム又はモジュールは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク９９０、ＣＤ−ＲＯＭ９９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ１０００に提供してもよい。
【００７３】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【００７４】
以下に、多頻度パターン抽出装置１０を実現する前提となる定義及び定理について説明する。
【００７５】
（補足説明）
（定義１）ラベル付きグラフの定義
頂点の集合V、辺の集合E、頂点の種類を示す頂点ラベルの集合LV、辺の種類を示す辺ラベルの集合LEが以下の式（１）により与えられたとき、グラフGは、以下の式（２）と表される。そして、頂点の数｜V｜をグラフGの大きさと呼ぶ。
【００７６】
【数１】
2005063277.tif 000003
【００７７】
【数２】
2005063277.tif 000004
【００７８】
（定義２）トポロジー
グラフの頂点及び辺からラベルの情報を取り除いた頂点の連結の情報のみからなるグラフをトポロジーと呼ぶ。
【００７９】
（定義３）概念階層
概念階層は、ループを含まない有効グラフで表される。概念aの上位概念はf(a)で表される。概念階層の一例としては、図３に示すものが挙げられる。
【００８０】
（定義４）グラフの包含関係
グラフG=(V(G),E(G),LV(G),LE(G))、Gs=(V(Gs),E(Gs),LV(Gs),LE(Gs))が与えられ、以下の式（３）の条件を満たすような関数φが存在するとき、グラフGはグラフGsを含むといい、G⊇Gsと示す。ここで、lb(vi)、lb(vi,vj)は、それぞれ頂点vi、辺(vi,vj)のラベルを示す。
【００８１】
【数３】
2005063277.tif 000005
【００８２】
（定義５）グラフパターン
多頻度部分グラフとして抽出される多頻度のパターンは、オブジェクトに含まれるグラフであり、必ずしも連結グラフに限定されない。
【００８３】
（定義６）支持度
複数のオブジェクトを表す複数のグラフデータの集合GDが与えられたとき、部分グラフGsの支持度sup(Gs)は、以下の式（４）に示すように、GDの全データのうち、グラフGsを含むグラフの割合である。
【００８４】
【数４】
2005063277.tif 000006
【００８５】
ユーザにより指定された最小支持度以上の支持度を有するグラフ構造を多頻度部分グラフと呼ぶ。ここで、多頻度部分グラフは、必ずしもGsを含むグラフGの一部分に限定されるものではなく、グラフG全体に対応してもよい。
【００８６】
（定義７）重み付き支持度
グラフデータGにおけるパターンPの出現回数を#(P,G)とする。ただし、頂点の組が重複するものは１回と数える。このとき、パターンPの重み付き支持度は、以下の式（５）により表させる。
【００８７】
【数５】
2005063277.tif 000007
【００８８】
また、式（４）に示した支持度は、式（６）により表すことができる。
【００８９】
【数６】
2005063277.tif 000008
【００９０】
（定義８）上位概念パターン
パターンP1、パターンP2の頂点数が等しく、P1とP2のトポロジーが等しく、かつ、P2がP1を含むとき、P2をP1の上位概念パターンと呼ぶ。
【００９１】
（定義９）多頻度パターン抽出問題
多頻度パターン抽出問題とは、グラフ構造の集合と最小支持度が入力として与えられたとき、グラフ構造の集合に多頻度グラフとして含まれる部分グラフ構造を全て抽出することである。ただし、P2がP1の上位概念パターンで、かつsup(P1)=sup(P2)であるP2は、過度に上位概念化されており、与えられたグラフ構造の集合に対して実質的にP1と同一の部分グラフ構造と見なすことができるため出力しないものとする。
【００９２】
（定理１）支持度の関係
P2がP1の上位概念パターンで、かつsupw(P1)=supw(P2)ならば、sup(P1)=sup(P2)である。
【００９３】
証明：
sup(P1)=sup(P2)でないと仮定する。P2がP1の上位概念パターンであることから、以下の式（７）が成立する。
【００９４】
【数７】
2005063277.tif 000009
【００９５】
P1をGiにおけるP1に対応する部分グラフに対応付ける関数をφi、P2をGiにおけるP2に対応する部分グラフに対応付ける関数をψiとすると、式（７）よりsupw(P2)≧supw(P1)である。ここで等式が成立するのは、全てのiに対して｜φi｜=｜ψi｜が成立する場合であるが、sup(P1)≠sup(P2)よりP2を含むがP1を含まないグラフデータが存在するため等式が成立しない。したがって、supw(P1)=supw(P2)に矛盾する。
【００９６】
（定義１０）同型拡張
P2がP1の上位概念パターンのとき、P1に頂点を１つ加えてパターンを拡張し、このパターンをP'1とする。トポロジーが等しくなるように、P2も同じ頂点ラベル、辺ラベルを持つ頂点、辺で拡張したパターンをP'2とする。このような拡張を同型拡張と呼ぶ。このとき、P'2はP'1の上位概念パターンとなる。
【００９７】
（定理２）P2がP1の上位概念パターンで、かつsupw(P1)=supw(P2)であれば、P1及びP2を同型拡張したパターンP'1及びP'2の支持度は、sup(P'1)=sup(P'2)を満たす。
【００９８】
証明：
P'2がP'1の上位概念パターンであるので、P'1を含むグラフデータは、P'2も含む。すなわち、Gi⊇P'1→Gi⊇P'2であり、sup(P'2)≧sup(P'1)である。従って、以下の式（８）が成立することを示せば、sup(P'1)=sup(P'2)を証明することができる。
【００９９】
【数８】
2005063277.tif 000010
【０１００】
P'2を含むGiは、P2を含む。さらにsupw(P1)=supw(P2)であることから、GiはP1を含む。P1からGiへの関数をφi、P2からGiへの関数をψiとすると、supw(P1) = supw(P2)よりφi =ψiである。ここでP'2からGiへの関数をψ'iとすると、拡張されて増えた頂点及び辺に関する遷移情報をψ'iから除くとψiとなる関係が成り立つ。P'1、P'2は、同型拡張の定義より、同じラベルを持つ頂点又は辺でP1、P2を同型拡張したものであるので、グラフGiに対し、P'1からGiへの関数φ'iが必ず存在する。したがって、P'2を含むGiはP'1も含み、式（８）が成立する。
【０１０１】
（定理３）  P2がP1の上位概念パターンで、かつsupw(P1)=supw(P2)である場合、P1及びP2に同型拡張を１回以上適用して生成されたパターンの支持度は常に等しい。
【０１０２】
証明：定理２より明らか。
【０１０３】
以上に説明した実施形態によれば、以下の各項目に示す多頻度パターン抽出装置、多頻度パターン抽出方法、及びそのプログラムと記録媒体が実現される。
【０１０４】
（項目１）グラフ構造によりそれぞれ表現された複数の前記オブジェクトのうち、予め定められた最小割合以上の前記オブジェクトにそれぞれ含まれる多頻度部分グラフの組を抽出する多頻度パターン抽出装置であって、前記複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる複数の頂点及び複数の辺のそれぞれを構成要素とするグラフ構造により表現され、予め定められた複数種類の前記構成要素と、前記複数種類の構成要素のいずれにもマッチングされる上位概念要素との対応を格納する概念階層データベースと、既に抽出された前記多頻度部分グラフに前記構成要素又は前記上位概念要素を付加した抽出候補部分グラフの組を生成する抽出候補部分グラフ生成部と、前記複数のオブジェクトのそれぞれにおける前記抽出候補部分グラフにマッチングされる部分グラフの個数を合計した重み付き支持度を算出する重み付き支持度算出部と、第１の前記抽出候補部分グラフに含まれる前記構成要素を、当該構成要素にマッチングされる前記上位概念要素に置き換えた場合に前記第１抽出候補部分グラフと同一の部分グラフとなる第２の抽出候補部分グラフを選択する上位概念候補選択部と、前記第１抽出候補部分グラフの前記重み付き支持度である第１重み付き支持度及び前記第２抽出候補部分グラフの前記重み付き支持度である第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加する多頻度部分グラフ追加部とを備える多頻度パターン抽出装置。
【０１０５】
（項目２）前記多頻度部分グラフ追加部は、前記第１抽出候補部分グラフを前記多頻度部分グラフの組に追加すること、及び、前記第１重み付き支持度及び前記第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加する項目１記載の多頻度パターン抽出装置。
【０１０６】
（項目３）前記抽出候補部分グラフ生成部は、前記抽出候補部分グラフとして、当該抽出候補部分グラフにマッチングされる部分グラフを含む前記オブジェクトの割合を示す支持度が前記最小割合以上を示す前記抽出候補部分グラフを生成する項目２記載の多頻度パターン抽出装置。
【０１０７】
（項目４）前記抽出候補部分グラフ生成部は、既に抽出された一の前記多頻度部分グラフに一の前記構成要素を付加した前記多頻度グラフ候補を生成する構成要素付加部と、前記一の構成要素を検索キーとして、前記一の構成要素にマッチングされる一の前記上位概念要素を前記概念階層データベースから検索する上位概念要素検索部と、前記一の多頻度部分グラフに前記一の上位概念要素を付加した前記抽出候補部分グラフを生成する上位概念要素付加部とを有する項目１記載の多頻度パターン抽出装置。
【０１０８】
（項目５）前記多頻度部分グラフを、前記構成要素の数に基づき定められた当該多頻度部分グラフの大きさに対応付けて格納する多頻度部分グラフデータベースを更に備え、前記抽出候補部分グラフ生成部は、第１の大きさを有する前記多頻度部分グラフを前記多頻度部分グラフデータベースから検索する多頻度部分グラフ検索部と、検索された前記多頻度部分グラフに前記構成要素又は前記上位概念要素を付加して前記第１の大きさより大きい第２の大きさとした部分グラフを、当該部分グラフにマッチングされる部分グラフを含む前記オブジェクトの割合を示す支持度が前記最小割合以上を示すことを条件として前記抽出候補部分グラフとして選択する抽出候補部分グラフ選択部とを有し、前記重み付き支持度算出部は、前記第２の大きさの前記抽出候補部分グラフの前記重み付き支持度を算出し、前記多頻度部分グラフ追加部は、前記第１重み付き支持度及び前記第２重み付き支持度が同一でないことを条件として、前記第２の大きさに対応付けて前記第２抽出候補部分グラフを前記多頻度部分グラフデータベースに格納する項目１記載の多頻度パターン抽出装置。
【０１０９】
（項目６）前記概念階層データベースは、一の前記構成要素と、当該一の構成要素にマッチングされる第１の前記上位概念要素及び第２の前記上位概念要素との対応を更に格納し、前記上位概念候補選択部は、前記第１抽出候補部分グラフに含まれる前記構成要素を、当該構成要素にマッチングされる前記上位概念要素に置き換えた場合に前記第１抽出候補部分グラフと同一の部分グラフとなる第３の抽出候補部分グラフを更に選択し、前記多頻度部分グラフ追加部は、前記第２重み付き支持度及び前記第３抽出候補部分グラフの前記重み付き支持度である第３重み付き支持度が同一、かつ、前記複数のオブジェクトのそれぞれについて、当該オブジェクトにおける前記第２抽出候補部分グラフにマッチングされる部分グラフの組と当該オブジェクトにおける前記第３抽出候補部分グラフにマッチングされる部分グラフの組とが同一である場合に、前記第１重み付き支持度及び前記第２重み付き支持度が同一でないことを条件として前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加し、前記第３抽出候補部分グラフを前記多頻度部分グラフの組に追加しない項目１記載の多頻度パターン抽出装置。
【０１１０】
（項目７）前記複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる前記複数の頂点が当該オブジェクトに含まれる複数の原子に対応し、当該オブジェクトに含まれる前記複数の辺が前記複数の原子間の結合に対応する化学物質を示し、複数の前記化学物質のそれぞれは、当該化学物質が薬品として所定の効用を有することを実験により分析した分析結果に基づいて選択されており、前記概念階層データベースは、予め定められた複数種類の原子と、前記複数種類の原子のいずれにもマッチングされる上位概念原子との対応を、前記複数種類の構成要素と、前記複数種類の構成要素のいずれにもマッチングされる前記上位概念要素との対応として格納し、前記抽出候補部分グラフ生成部は、前記所定の効用を有する化学物質の部分構造として既に抽出された前記多頻度部分グラフに前記原子又は前記上位概念原子を付加した前記抽出候補部分グラフの組を生成し、前記重み付き支持度算出部は、前記複数のオブジェクトのそれぞれにおける前記抽出候補部分グラフにマッチングされる部分グラフの個数を合計した前記重み付き支持度を算出し、前記上位概念候補選択部は、前記第１抽出候補部分グラフに含まれる原子を当該原子にマッチングされる前記上位概念原子に置き換えた場合に前記第１抽出候補部分グラフと同一の部分構造を示す部分グラフとなる前記第２抽出候補部分グラフを選択し、前記多頻度部分グラフ追加部は、前記第１重み付き支持度及び前記第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加することにより、前記所定の効用を有する化学物質に共通して含まれる部分構造の組を生成する項目１記載の多頻度パターン抽出装置。
【０１１１】
（項目８）前記複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる前記複数の頂点が閲覧されたウェブページに対応し、当該オブジェクトに含まれる前記複数の辺が前記ウェブページの閲覧順序を示すワールド・ワイド・ウェブサイトの閲覧履歴であり、前記概念階層データベースは、予め定められた複数種類のウェブページと、前記複数種類のウェブページのいずれにもマッチングされる上位概念ウェブページとの対応を、前記複数種類の構成要素と、前記複数種類の構成要素のいずれにもマッチングされる前記上位概念要素との対応として格納し、前記抽出候補部分グラフ生成部は、前記所定の特性を有する前記閲覧履歴の部分構造として既に抽出された前記多頻度部分グラフに前記ウェブページ又は前記上位概念ウェブページを付加した前記抽出候補部分グラフの組を生成し、前記重み付き支持度算出部は、前記複数のオブジェクトのそれぞれにおける前記抽出候補部分グラフにマッチングされる部分グラフの個数を合計した前記重み付き支持度を算出し、前記上位概念候補選択部は、前記第１抽出候補部分グラフに含まれるウェブページを当該ウェブページにマッチングされる前記上位概念ウェブページに置き換えた場合に前記第１抽出候補部分グラフと同一の部分構造を示す部分グラフとなる前記第２抽出候補部分グラフを選択し、前記多頻度部分グラフ追加部は、前記第１重み付き支持度及び前記第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加することにより、前記所定の特性を有する前記閲覧履歴に共通して含まれる部分構造の組を生成する項目１記載の多頻度パターン抽出装置。
【０１１２】
（項目９）前記複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる前記複数の頂点が当該オブジェクトに含まれる複数の語句に対応し、当該オブジェクトに含まれる前記複数の辺が前記複数の語句間の順序に対応する文章を示し、複数の前記文章のそれぞれは、当該文章が所定のジャンルに分類されるべきことを分析した分析結果に基づいて選択されており、前記概念階層データベースは、予め定められた複数種類の語句と、前記複数種類の語句のいずれにもマッチングされる上位概念語句との対応を、前記複数種類の構成要素と、前記複数種類の構成要素のいずれにもマッチングされる前記上位概念要素との対応として格納し、前記抽出候補部分グラフ生成部は、前記所定のジャンルに分類される前記文章の部分構造として既に抽出された前記多頻度部分グラフに前記語句又は前記上位概念語句を付加した前記抽出候補部分グラフの組を生成し、前記重み付き支持度算出部は、前記複数のオブジェクトのそれぞれにおける前記抽出候補部分グラフにマッチングされる部分グラフの個数を合計した前記重み付き支持度を算出し、前記上位概念候補選択部は、前記第１抽出候補部分グラフに含まれる語句を当該語句にマッチングされる前記上位概念語句に置き換えた場合に前記第１抽出候補部分グラフと同一の部分構造を示す部分グラフとなる前記第２抽出候補部分グラフを選択し、前記多頻度部分グラフ追加部は、前記第１重み付き支持度及び前記第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加することにより、前記所定のジャンルの前記文章に共通して含まれる部分構造の組を生成する項目１記載の多頻度パターン抽出装置。
【０１１３】
（項目１０）グラフ構造によりそれぞれ表現された複数の前記オブジェクトのうち、予め定められた最小割合以上の前記オブジェクトにそれぞれ含まれる多頻度部分グラフの組をコンピュータにより抽出する多頻度パターン抽出方法であって、前記複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる複数の頂点及び複数の辺のそれぞれを構成要素とするグラフ構造により表現され、予め定められた複数種類の前記構成要素と、前記複数種類の構成要素のいずれにもマッチングされる上位概念要素との対応を格納する概念階層データベースを前記コンピュータにより管理する概念階層データベース管理段階と、既に抽出された前記多頻度部分グラフに前記構成要素又は前記上位概念要素を付加した抽出候補部分グラフの組を前記コンピュータにより生成する抽出候補部分グラフ生成段階と、前記複数のオブジェクトのそれぞれにおける前記抽出候補部分グラフにマッチングされる部分グラフの個数を合計した重み付き支持度を前記コンピュータにより算出する重み付き支持度算出段階と、第１の前記抽出候補部分グラフに含まれる前記構成要素を、当該構成要素にマッチングされる前記上位概念要素に置き換えた場合に前記第１抽出候補部分グラフと同一の部分グラフとなる第２の抽出候補部分グラフを前記コンピュータにより選択する上位概念候補選択段階と、前記第１抽出候補部分グラフの前記重み付き支持度である第１重み付き支持度及び前記第２抽出候補部分グラフの前記重み付き支持度である第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に前記コンピュータにより追加する多頻度部分グラフ追加段階とを備える多頻度パターン抽出方法。
【０１１４】
（項目１１）コンピュータを、グラフ構造によりそれぞれ表現された複数の前記オブジェクトのうち、予め定められた最小割合以上の前記オブジェクトにそれぞれ含まれる多頻度部分グラフの組を抽出する多頻度パターン抽出装置として機能させるプログラムであって、前記複数のオブジェクトのそれぞれは、当該オブジェクトに含まれる複数の頂点及び複数の辺のそれぞれを構成要素とするグラフ構造により表現され、当該プログラムは、前記コンピュータを、予め定められた複数種類の前記構成要素と、前記複数種類の構成要素のいずれにもマッチングされる上位概念要素との対応を格納する概念階層データベースを管理する概念階層データベース管理部と、既に抽出された前記多頻度部分グラフに前記構成要素又は前記上位概念要素を付加した抽出候補部分グラフの組を生成する抽出候補部分グラフ生成部と、前記複数のオブジェクトのそれぞれにおける前記抽出候補部分グラフにマッチングされる部分グラフの個数を合計した重み付き支持度を算出する重み付き支持度算出部と、第１の前記抽出候補部分グラフに含まれる前記構成要素を、当該構成要素にマッチングされる前記上位概念要素に置き換えた場合に前記第１抽出候補部分グラフと同一の部分グラフとなる第２の抽出候補部分グラフを選択する上位概念候補選択部と、前記第１抽出候補部分グラフの前記重み付き支持度である第１重み付き支持度及び前記第２抽出候補部分グラフの前記重み付き支持度である第２重み付き支持度が同一でないことを条件として、前記第２抽出候補部分グラフを前記多頻度部分グラフの組に追加する多頻度部分グラフ追加部として機能させるプログラム。
【０１１５】
（項目１２）項目１１記載のプログラムを記録した記録媒体。
【図面の簡単な説明】
【０１１６】
【図１】本発明の実施形態に係る多頻度パターン抽出装置１０の構成を示す。
【図２】本発明の実施形態に係るオブジェクトＤＢ１００に格納される情報の一例を示す。
【図３】本発明の実施形態に係る概念階層ＤＢ１０５に格納される情報の一例を示す。
【図４】本発明の実施形態に係る多頻度部分グラフＤＢ１１０に格納される情報の一例を示す。
【図５】本発明の実施形態に係る抽出候補部分グラフＤＢ１５５に格納される情報の一例を示す。
【図６】本発明の実施形態に係る多頻度パターン抽出装置１０の動作フローを示す。
【図７】本発明の実施形態の第１変形例に係るオブジェクトＤＢ１００に格納される情報の一例を示す。
【図８】本発明の実施形態の第２変形例に係るオブジェクトＤＢ１００に格納される情報の一例を示す。
【図９】本発明の実施形態に係るコンピュータ１０００のハードウェア構成の一例を示す。
【符号の説明】
【０１１７】
１０  多頻度パターン抽出装置
１００  オブジェクトＤＢ
１０２  オブジェクトＤＢ管理部
１０５  概念階層ＤＢ
１１０  多頻度部分グラフＤＢ
１１５  多頻度部分グラフＤＢ管理部
１２０  抽出候補部分グラフ生成部
１２５  多頻度部分グラフ検索部
１３０  抽出候補部分グラフ選択部
１３５  構成要素付加部
１４０  上位概念要素検索部
１４５  上位概念要素付加部
１４７  支持度算出部
１５０  重み付き支持度算出部
１５５  抽出候補部分グラフＤＢ
１６０  抽出候補部分グラフＤＢ管理部
１６５  上位概念候補選択部
１７０  多頻度部分グラフ追加部
１８０  入出力部
４００  多頻度部分グラフ
５００  抽出候補部分グラフ
５１０  構成要素
５２０  抽出候補部分グラフ
５３０  上位概念要素
９００  ＣＰＵ
９１０  ＲＯＭ
９２０  ＲＡＭ
９３０  通信インターフェイス
９４０  記憶装置
９５０  フレキシブルディスク・ドライブ
９６０  ＣＤ−ＲＯＭドライブ
９７０  入出力チップ
９７５  グラフィック・コントローラ
９８０  表示装置
９８２  ホスト・コントローラ
９８４  入出力コントローラ
９９０  フレキシブルディスク
９９５  ＣＤ−ＲＯＭ
１０００  コンピュータ
【図１】
2005063277.tif 000011
【図２】
2005063277.tif 000012
【図３】
2005063277.tif 000013
【図４】
2005063277.tif 000014
【図５】
2005063277.tif 000015
【図６】
2005063277.tif 000016
【図７】
2005063277.tif 000017
【図８】
2005063277.tif 000018
【図９】
2005063277.tif 000019