Python の基礎: FP 成長アルゴリズムの構築

Apriori アルゴリズムと比較すると、FP-growth アルゴリズムではデータベースを 2 回走査するだけで済むため、頻繁に出現するアイテムセットを効率的に検出できます。検索エンジン会社にとっては、インターネット上で使用されている単語を調べて、どの単語が頻繁に一緒に出現するかを調べる必要があります。したがって、頻繁に出現するアイテムセットを効率的に発見できる方法が必要であり、FP 成長アルゴリズムはこのタスクを達成できます。

FP 成長アルゴリズムは、アプリオリ原理に基づいており、データ セットを FP (頻繁パターン) ツリーに格納することで頻繁なアイテム セットを検出します。

FP-growth アルゴリズムではデータベースを 2 回スキャンするだけで済みますが、Apriori アルゴリズムでは各潜在的頻出アイテム セットを見つけるときにデータ セットを 1 回スキャンするだけで済むため、FP-growth アルゴリズムの方が効率的です。

[[212909]]

頻繁なアイテムセットを発見する FP アルゴリズムのプロセスは次のとおりです。

（１）FPツリーを構築する。

（２）FP木からの頻出アイテムセットのマイニング

FP は頻繁なパターンの略で、類似の要素をリンクで接続します。接続された要素は、リンクされたリストと見なすことができます。

トランザクションデータテーブル内の各トランザクションに対応するデータ項目をサポートに従ってソートした後、各トランザクション内のデータ項目をNULLをルートノードとするツリーに降順で挿入し、各ノードにノードのサポートを記録します。

トランザクション データ サンプルがあると仮定すると、FP ツリーを構築する手順は次のようになります。

Apriori アルゴリズムの最小サポートしきい値と組み合わせて、ここでは最小サポートを 3 と定義します。上記の表のデータと組み合わせて、最小サポート要件を満たさないものは、最適な FP ツリーには表示されません。

これに基づいて FP ツリーが構築され、ヘッド ポインター テーブルを使用して特定の型の最初のインスタンスを指すことで、FP ツリー内のすべての要素にすばやくアクセスできるようになります。ヘッド ポインターを使用して構築された FP ツリーを図に示します。

描画された FP ツリーとヘッド ポインタ テーブルを組み合わせると、テーブル内のデータは次のようにフィルタリングされ、並べ替えられます。

データ項目をフィルタリングおよびソートした後、NULL から開始して、フィルタリングおよびソートされた頻繁な項目セットを継続的に追加して、FP ツリーを構築できます。このプロセスは次のように表現できます。

このようにして、FP ツリーに対応するデータ構造が構築されます。これで、FP ツリーを構築できます。FP ツリーの構築関数については、Python ソース コードを参照してください。

上記の例を実行する前に、実際のデータセットが必要であり、以前のデータを組み合わせてデータセットをカスタマイズする必要があります。このようにして FP ツリーが構築され、次のステップではそれを使用して頻繁なアイテム セットをマイニングします。