Skip to content
検索結果に戻る

FP成長 (頻出パターン成長)

提唱者
Jiawei Han, Jian Pei & Yiwen Yin
年
2000
種類
Frequent-itemset mining algorithm
系統
Pattern mining

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

2000年にJiawei Han、Jian Pei、Yiwen Yinによって導入されたFP成長は、候補セットを生成することなくトランザクションデータから頻出アイテムセットをマイニングします。これは、古典的なAprioriアルゴリズムを遅くするコストのかかるステップです。データベースを2回のスキャンで頻出パターンツリー(FP-tree)に圧縮し、その構造から再帰的に頻出パターンを成長させることで、大規模で密なデータセットではAprioriよりも劇的に高速になります。

手法の背後にある直感

Aprioriは、候補の組み合わせを繰り返し生成およびテストすることで頻出アイテムセットを見つけます。これは、密なデータでは爆発的にコストがかかる、スキャン負荷の高いプロセスです。FP成長は異なるルートを取ります。トランザクションデータベース全体をコンパクトなツリーに圧縮し、共通のプレフィックスは一度だけ保存されるため、共通のパターンは重複して圧縮されます。次に、候補を生成する代わりに、各アイテムにつながるパスをたどり、より小さな「条件付き」ツリーを再帰的にマイニングすることで、ツリーから直接頻出パターンを読み取ります。データに対する2回のパスと巧妙なデータ構造が、Aprioriの多数のパスと組み合わせ候補の爆発に取って代わります。

歴史学

Han、Pei、Yinは、2000年のSIGMODでAprioriの候補生成フリー代替としてFP成長を発表し、2004年のData Mining and Knowledge Discoveryの記事で詳細に扱いました。頻出パターンツリーのアイデア — トランザクションを共通プレフィックス構造に圧縮し、それを再帰的にマイニングすること — は、Apriori(候補ベース)およびECLAT(垂直フォーマット)とともに、パターンマイニングの基礎的な技術となりました。データマイニングライブラリでは、標準的で高性能なアイテムセットマイナーとして依然として利用されています。

使うべき場面

トランザクションデータ(市場バスケット分析、ウェブ利用およびクリックストリームマイニング、レコメンデーション、バイオインフォマティクス共起など)から頻出アイテムセット(および下流の関連ルール)をマイニングするためにFP成長を使用します。特に、Aprioriの候補生成が遅すぎる大規模または密なデータセットで有効です。データベーススキャンは2回だけで済み、通常はAprioriをはるかに上回るパフォーマンスを発揮します。そのコスト:FP-treeはメモリに収まる必要があります(非常に大規模または極端にスパースなデータでは、ツリーの圧縮がうまくいかないため制限となります)。再帰は実装が複雑になる可能性があり、すべてのサポートベースのマイニングと同様に、最小サポートしきい値に敏感です(低すぎると出力が爆発し、高すぎるとパターンが見逃されます)。ECLAT(垂直tidset交差)が代替手段です。ルール自体については、関連ルール生成と組み合わせてください。

限界と注意点

  • FP-treeはメモリに収まる必要があります。非常に大規模なデータセットでは収まらない場合があります。
  • スパースなデータではツリーの圧縮が悪く、利点が損なわれます。
  • 条件付きツリーの再帰的構築は、実装が比較的複雑です。
  • 頻出アイテムセットマイニングと同様に、最小サポートしきい値に敏感です。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 候補生成なし — 大規模/密なデータではAprioriよりはるかに高速。
  • パターン長に関係なく、データベーススキャンは2回のみ。
  • FP-treeは共通構造を圧縮し、密なデータではメモリと時間を節約します。
  • 候補ベースの方法を圧倒する長い頻出パターンにスケールします。

応用

  • 市場バスケット分析および小売関連マイニング。
  • ウェブ利用およびクリックストリームパターンマイニング。
  • 頻繁に共起するアイテムによるレコメンデーション。
  • バイオインフォマティクス共起およびモチーフ発見。
  • Aprioriが遅すぎる大規模な頻出アイテムセットタスク。

使い方

使い方

1

最初のデータベーススキャンで各アイテムのサポートをカウントし、最小サポートしきい値を下回るものは破棄します。生き残った頻出アイテムは、頻度順に降順にソートされます。この順序により、トランザクションはツリーのプレフィックスを共有でき、FP-treeはコンパクトに保たれます。

数式
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}
2

2回目のスキャンで、各トランザクション(ソートされた順序での頻出アイテム)をFP-treeに挿入し、共通のプレフィックスパスに沿ってカウントをインクリメントし、必要に応じて新しいブランチを追加します。ヘッダーテーブルは各アイテムのすべての出現をリンクするため、ツリーはデータセット全体の頻出構造をコンパクトに表現します。

数式
\text{second scan: insert each transaction's frequent items into the FP-tree}
3

各頻出アイテム(最も頻度の低いものから処理)について、アルゴリズムはその条件付きパターンベースを収集します。これは、そのアイテムと共起するツリー内のプレフィックスパスのセットであり、各パスはそのカウントで重み付けされます。これにより、アイテムが頻繁に出現するコンテキストが捉えられます。

数式
\text{for each item: collect its conditional pattern base (prefix paths)}
4

各条件付きパターンベースから、より小さな条件付きFP-treeが構築され、再帰的にマイニングされます。これにより、アイテムをその条件付きツリーで見つかったパターンに追加することで、より長い頻出アイテムセットが成長します。再帰は単一パスツリーで底を打ち、そのアイテムセットの組み合わせは直接列挙されます。これにより、候補生成なしで全ての頻出アイテムセットが得られます。

数式
\text{build conditional FP-trees recursively to grow frequent patterns}

よくある落とし穴

  • 最小サポートを低く設定しすぎると、アイテムセットの爆発が発生します。
  • 常にAprioriに勝つと仮定すること — 小規模またはスパースなデータでは、その利点はわずかです。
  • 頻出アイテムセットはルールではないことを忘れること。ルール生成は別のステップです。
  • FP-treeがRAMに保持できない場合のメモリ制限を見落とすこと。

よくある質問

FP成長はAprioriよりどのように高速なのですか?

Aprioriは候補アイテムセットを繰り返し生成およびテストし、データベースを何度もスキャンします。FP成長は候補生成を完全に回避します。2回のスキャンでデータをFP-treeに圧縮し、そこからパターンを再帰的にマイニングします。これにより、組み合わせ候補の爆発が排除され、密なデータで大幅な高速化が得られます。

FP-treeとは何ですか?

データベースの頻出アイテムの圧縮プレフィックスツリーです。プレフィックスを共有するトランザクションはパスを共有し、ノードカウントはサポートを記録し、ヘッダーテーブルは各アイテムの出現をリンクします。データセットの頻出構造をコンパクトに格納するため、データを再スキャンせずにパターンを読み取ることができます。

FP成長はECLATおよび関連ルールとどのように関係していますか?

FP成長、ECLAT、Aprioriはすべて頻出アイテムセットを見つけます。ECLATはツリーの代わりに垂直tidset交差アプローチを使用します。頻出アイテムセットを見つけることは最初の段階にすぎません。関連ルール(信頼度/リフト付き)は、別のステップでそれらのアイテムセットから生成されます。

関連する手法

参考文献

  1. Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.

    DOI 文献を開く
    コピーしました。
  2. Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.

    DOI 文献を開く
    コピーしました。