fpgrowthは、頻繁なパターンマイニングで「最先端」とみなされていますか？

Question

頻繁なパターンマイニング（FPM）問題を解決するためのアルゴリズムの開発を知っている限り、改善の道にはいくつかの主要なチェックポイントがあります。まず、 アプリオリ 1993年にアルゴリズムが提案されました Agrawal et al。, 、問題の形式化とともに。アルゴリズムができました 取り除きます からのいくつかのセット 2^n - 1 格子を使用してデータを維持することにより（PowerSet）セット（PowerSet）。アプローチの欠点は、拡張された各セットの頻度を計算するためにデータベースを読み直す必要性でした。

その後、1997年、 Zaki et al。 アルゴリズムを提案しました エクラット, 、 どれの 挿入 格子内の各セットの結果の周波数。これは、格子の各ノードに、ルートから参照ノードにアイテムを搭載したトランザクションIDのセットを追加することによって行われました。主な貢献は、各セットの頻度を知るためにデータセット全体を読み直す必要がないことですが、そのようなデータ構造を構築するために必要なメモリは、データセット自体のサイズを超えている可能性があります。

2000年、 ハン等。 名前のアルゴリズムを提案しました fpgrowth, 、fptreeという名前のプレフィックスツリーデータ構造とともに。アルゴリズムは、重要なデータ圧縮を提供することができましたが、頻繁なアイテムセットのみが（候補のアイテムセット生成なしで）生成されることも付与されました。これは主に、各トランザクションのアイテムを減少した順序で並べ替えることによって行われたため、最も頻繁なアイテムは、ツリーデータ構造の繰り返しが最も少ないアイテムです。頻度は奥でツリーを横断している間にのみ下降するため、アルゴリズムは 取り除きます 非頻度のアイテムセット。

編集:

私の知る限り、これは最先端のアルゴリズムと見なされるかもしれませんが、他の提案されたソリューションについて知りたいと思います。 FPMの他のどのアルゴリズムが「最先端」と見なされますか？何ですか 直感/主な矛盾 そのようなアルゴリズムの？

fprowthアルゴリズムは、頻繁なパターンマイニングで「最先端」とみなされていますか？そうでない場合、どのアルゴリズムがより効率的に大きなデータセットから頻繁なアイテムセットを抽出する可能性がありますか？

Answer 1

最先端のような最先端：実際に使用されるか、理論で作業しましたか？

Aprioriは、新しい頻繁なアイテムセットアルゴリズムの開発を除き、どこでも使用されます。実装が簡単で、非常に異なるドメインで簡単に再利用できます。さまざまな品質の数百のApriori実装が見つかります。実際、Aprioriを間違えるのは簡単です。

FPGrowthは実装がはるかに困難ですが、もっと興味深いものでもあります。したがって、学問的な観点からは、誰もがFPGROWTHを改善しようとします。

あなたが良い実装を持っているなら、すべてのアルゴリズムはそれが良好であり、私の意見ではそれは悪い状況です。優れたAprioriの実装が行われます それだけ データベースをスキャンする必要があります k 長さのすべての頻繁なアイテムセットを見つける時間 k. 。特に、データがメインメモリに収まる場合、これは安いです。 Aprioriを殺すことができるものは、頻繁に2項目を頻繁に使用することが多すぎます（特に、Trieや同様の加速技術などを使用しない場合）。頻繁なアイテムセットの数が少ない大規模なデータで最適に機能します。

Eclatは列で動作します。ただし、各列をより頻繁に読む必要があります。この作業を減らすためのディフェットにはいくつかの作業があります。データがメインメモリに適合しない場合、EclatはおそらくApriori以上に苦しんでいます。最初に深さを進むことにより、Aprioriよりもはるかに早く最初の興味深い結果を返すことができ、これらの結果を使用してパラメーターを調整することができます。したがって、適切なパラメーターを見つけるには、より少ない反復が必要です。しかし、設計上、Aprioriのようにきちんと剪定を活用することはできません。

fpgrowthは、データセットをツリーに圧縮します。これは、レコードが重複している場合に最適に機能します。おそらく、データを事前に事前にして重み付きベクターに重複を融合させることができれば、AprioriとEclatのかなりの利益を得ることができます。 fpgrowthはこれを極端なレベルで行います。欠点は、実装がはるかに難しいことです。そして、このツリーがもはやメモリに収まらないと、実装する混乱が生じます。

パフォーマンスの結果とベンチマークについては、それらを信頼しないでください。誤って実装するものがたくさんあります。 10の異なる実装を試してみると、10の非常に異なるパフォーマンス結果が得られます。特にAprioriの場合、私はほとんどの実装がAprioriの主な貢献のいくつかを欠いているという意味で破られているという印象を持っています...そして、これらの部分が正しいもののうち、最適化の質は大きく異なります。

実際には、これらのアルゴリズムを効率的に実装する方法に関する論文もあります。

AprioriとEclatの効率的な実装。
クリスチャン・ボルゲルト
頻繁なアイテムセットマイニング実装のワークショップ（FIMI 2003、メルボルン、フロリダ州、米国）。

また、このドメインでこれらの調査を読むこともできます。

• ゲタル、バート。 「頻繁なパターンマイニングに関する調査。」大学。ヘルシンキ（2003）。

• Ferenc Bodon、頻繁なアイテムセットマイニングに関する調査、テクニカルレポート、ブダペスト工科大学経済、2006年

• 頻繁なアイテムセットマイニング
  クリスチャン・ボルゲルト
  ワイリー学際レビュー：データマイニングと知識発見2（6）：437-456。 2012年

Answer 2

私が文献で見た最近の頻繁なパターンアプローチのほとんどは、FPグロースの最適化に基づいています。私は認めなければなりません、私は長年にわたってFPMの文献内で多くの開発を見ていません。

このウィキブック そこにあるFPグロースの多くのバリエーションを強調しています。