頻出部分構造の発見方法とは？主要なマイニング手法をわかりやすく解説

データマイニングやグラフマイニングの分野において、頻出部分構造（frequent substructure）の発見は重要なタスクの一つです。本記事では、頻出部分構造発見の基本的な流れと、代表的な2つのマイニング手法である「アプライオリ型アプローチ」と「パターングロース型アプローチ」について詳しく解説します。

頻出部分構造発見の基本的な2つのステップ

頻出部分構造の発見は、通常以下の2つのステップで構成されます。

第1ステップでは、頻出部分構造の候補を生成します。続く第2ステップでは、生成された各候補の頻度を検証します。

第2ステップには部分グラフ同型性判定（subgraph isomorphism test）が含まれますが、この処理の計算量は非常に高く、NP完全問題として知られています。そのため、頻出部分構造発見に関する研究の多くは、計算コストの低い第1ステップの最適化に焦点を当てています。

手法1：アプライオリ型アプローチ（Apriori-based Approach）

アプライオリ型の頻出部分構造マイニングアルゴリズムは、頻出項目集合マイニングで用いられるアプライオリ（Apriori）アルゴリズムと同じ特徴を持っています。

頻出グラフの探索は「サイズ」の小さいグラフから開始され、候補に対して頂点・辺・パスを1つずつ追加しながら、ボトムアップ方式で進められます。なお、グラフの「サイズ」の定義は、採用するアルゴリズムによって異なります。

候補生成の難しさ

アプライオリ型部分構造マイニングアルゴリズムにおける最大の設計上の課題は、候補生成ステップです。

頻出項目集合マイニングの場合、候補生成は非常に単純です。例えば、サイズ3の頻出項目集合として (abc) と (bcd) が存在する場合、これらを結合（join）することで、サイズ4の候補 (abcd) が容易に導き出せます。

しかし、頻出部分構造マイニングでは、2つの部分構造を結合する方法が多数存在するため、候補生成は頻出項目集合マイニングよりもはるかに困難になります。

手法2：パターングロース型アプローチ（Pattern-Growth Approach）

アプライオリ型アプローチは、レベルごとの候補生成を行う仕組み上、幅優先探索（BFS）戦略を採用する必要があります。サイズ(k+1)のグラフが頻出であるかどうかを判定するには、対応するすべてのサイズkの部分グラフを確認し、頻度の上限値を求めなければなりません。

そのため、アプライオリ型アプローチでは、サイズ(k+1)の部分グラフをマイニングする前に、サイズkの部分グラフのマイニングを完了しておく必要があります。

一方、パターングロース法は探索方法においてより柔軟性が高いのが特徴です。幅優先探索（BFS）だけでなく、深さ優先探索（DFS）も利用できます。特にDFSはメモリ消費量が少ないという実用上の大きなメリットがあります。

重複グラフ問題というボトルネック

パターングロースによるグラフ成長はシンプルな手法ですが、必ずしも効率的とは言えません。そのボトルネックはグラフ拡張の非効率性にあります。

同じグラフが何度も発見される可能性があるのです。例えば、n個の異なる(n−1)辺グラフが存在し、それらがすべて同一のn辺グラフへと拡張されるケースが考えられます。このように2回目以降に再発見されたグラフは重複グラフ（duplicate graph）と呼ばれ、その重複検出は計算資源の無駄につながります。

重複グラフへの対策

重複グラフの生成を抑えるには、各頻出グラフをできるだけ保守的に拡張することが有効です。この原則に基づいて、いくつかの新しいアルゴリズムが設計されました。

その代表格がスパニングアルゴリズムです。このアルゴリズムは、重複検出のために過去に発見済みの頻出グラフを検索する必要がなく、重複グラフを一切拡張しないにもかかわらず、頻出グラフの完全な集合を漏れなく発見できることを保証しています。