FPツリーとは？データマイニングにおける頻出パターンツリーの構造と構築方法を徹底解説

FPツリーとは何か

FPツリー（Frequent Pattern Tree：頻出パターンツリー）は、入力データセットをコンパクトに表現した木構造のデータ構造です。トランザクション（取引レコード）を1件ずつ読み込みながら構築され、各トランザクションに含まれる項目（アイテム）が、ツリー上の一つの経路（パス）としてマッピングされます。

複数のトランザクションが同じ項目を持っている場合、それらの経路は部分的に重なり合います。この経路の重複度が高いほど、FPツリーによるデータ圧縮率は高くなります。FPツリー全体がメインメモリに収まるサイズであれば、ディスク上のデータに対して繰り返しスキャンを行うことなく、メモリ内のツリー構造から直接頻出項目集合を抽出できるという大きな利点があります。

FPツリーのノード構造

FPツリーの各ノードには、以下の情報が格納されます。

・項目名（アイテムラベル）
・カウンタ：その項目を含むトランザクションが、当該経路に何件マッピングされたかを示す頻度数

初期状態では、FPツリーには「null」記号で表されるルートノードのみが存在します。そこへトランザクションを読み込むごとに、新しいノードや経路が追加されていきます。

FPツリーの構築手順

FPツリーは、主に以下の手順で段階的に構築されます。

ステップ1：第1回目のデータベーススキャン

まずデータセット全体を一度走査し、各項目の出現回数（サポートカウント）を集計します。この時点で頻出しない項目は削除され、頻出する項目のみがサポート数の降順に並べ替えられます。これにより、後続の処理対象となる項目を絞り込むことができます。

ステップ2：第2回目のスキャンによるツリー構築

次に、再度データセットを読み込みながらFPツリーを構築していきます。具体的な例を見てみましょう。

最初のトランザクション {a, b} の場合

項目「a」と「b」に対応するノードが新たに生成され、「null → a → b」という経路が形成されます。この経路上の各ノードの頻度カウントは1となります。

2番目のトランザクション {b, c, d} の場合

項目「b」「c」「d」に対応するノードが作成され、「null → b → c → d」という経路が定義されます。こちらも各ノードの頻度カウントは1です。注目すべきは、最初の2つのトランザクションは共通して項目「b」を含んでいるものの、共通する頻出プレフィックス（先頭部分）を持たないため、両者の経路は完全に分離した状態になるという点です。

3番目のトランザクション {a, c, d, e} の場合

このトランザクションは、最初のトランザクションと共通の頻出プレフィックス（項目「a」）を持っています。そのため、「null → a → c → d → e」という3番目の経路は、最初のトランザクションの経路「null → a → b」と一部が重なります。この共有部分により、ノード「a」の頻度カウントは2に増加し、新しく作成されたノード「c」「d」「e」の頻度カウントはそれぞれ1となります。

圧縮効果とFPツリーの利点

このプロセスは、すべてのトランザクションがFPツリー内のいずれかの経路にマッピングされるまで繰り返されます。完成したFPツリーのサイズは、元の非圧縮データよりも大幅に小さくなります。これは特にマーケットバスケット分析のような分野では、多くのトランザクションが共通の項目を多数持つためです。

このようにFPツリーは、頻繁に共起する項目の組み合わせを効率的に保持しながらデータを圧縮できるため、FP-Growthアルゴリズムなどによる高速な頻出パターンマイニングの基盤として広く活用されています。