1

頻繁に使用するアイテムセットをマイニングするためのアプリオリ アルゴリズムを実装しましたが、サンプル データでは問題なく動作しますが、 http://fimi.ua.ac.be/data/retail.datで入手できる小売データセットに対して実行しようとすると、約 3 MB のデータになります。 88,000 のトランザクションと 1600 のユニークなアイテムで、約 29 時間かかります。パフォーマンス ヒットの原因を調べたところ、候補アイテムセットを生成するアルゴリズムに時間がかかっていることがわかりました。パフォーマンスを改善する方法について誰か助けてもらえますか、それともこれらは通常のアルゴリズムの動作ですか。

4

3 に答える 3

2

使用しているアルゴリズムとしきい値は何ですか?

n最小サポートを満たす 1 項目セットがある場合、Apriori (および他の多くの) は 2 項目セットを検討する必要がありますn*(n-1)/2。もちろん、これはかなり高価になります。Apriori では、多くの場合、2 アイテムセットが最大かつ最もコストのかかるステップです (設定によっては、3 アイテムセットの方が悪い場合もありますが、通常はそこまで到達しません...)。

データの特性によっては、Eclat のパフォーマンスが向上することもあれば、低下することもあります。FP 成長は非常に巧妙ですが、正しく効率的に実装するのは非常に難しいようです。

無数のバリアントも存在し、一部は確率論的であり、大幅に高速になる場合があります。

しかし、本質的には、実装とデータ セット/パラメーターの設定が重要です。同じデータ セットに対して、1 つのアプローチが他のアプローチよりも優れている場合があります。実装によって、10 倍のパフォーマンスの差が簡単に生じる可能性があります。特にアプリオリでは、多くの人が使用される剪定のトリックを完全に理解しておらず、あまりにも多くの作業を行うことになります.

サンプル データ セット (残念ながら、数値を説明する辞書がないとまったく役に立ちません) の場合、私の APRIORI は、minSupport=1000 のローエンド Atom CPU で約 1 分で終了します。見つかった 4 つのアイテムセットは次のとおりです。

32, 38, 39, 48: 1236
32, 39, 41, 48: 1646
36, 38, 39, 48: 1080
38, 39, 41, 48: 1991
38, 39, 48, 110: 1031
38, 39, 48, 170: 1193

しかし、前に述べたように、APRIORI ではパラメーターが非常に重要です。APRIORI は、トランザクション数 (メイン メモリに収まらない場合があります) で適切にスケーリングしますが、多数の候補に悩まされるため、minSupport を十分に高く設定する必要があります。

minSupport=1000 の場合:

1-frequentItemsets (56)
2-frequentItemsets (49)
3-frequentItemsets (24)
4-frequentItemsets (6)
APRIORI runtime: 55401 ms

minSupport=500 の場合:

1-frequentItemsets (185)
2-frequentItemsets (191)
3-frequentItemsets (79)
4-frequentItemsets (13)
5-frequentItemsets (0)
APRIORI runtime: 136594 ms

ご覧のとおり、実行時間は 2 倍以上になりました。その理由は、1 アイテムセットが成長し、さらに多くの 2 アイテムセット候補が生成されたためです。3点セットと4点セットでは、その差はそれほど大きくありません。しかし、全体として、非常にローエンドの CPU での 2 分間の実行時間はまだ悪くありません。

最小サポートを 250 に減らす:

1-frequentItemsets (587)
2-frequentItemsets (640)
3-frequentItemsets (273)
4-frequentItemsets (54)
5-frequentItemsets (4)
APRIORI runtime: 954984 ms

ランタイムが爆発し始めます。5つのアイテムセットを見つけるのに約16分:

32, 38, 39, 41, 48: 448
36, 38, 39, 41, 48: 334
38, 39, 41, 48, 110: 346
38, 39, 41, 48, 170: 413

ご覧38, 39, 41, 48のとおり、このデータ セットでは 4 項目セットが重要な役割を果たしています (ただし、これは最初の実行で既に見つかりました)。また、 の信頼度を与えることもできます38, 39, 41, 48 -> 32。これは、5 つのアイテムを含む最も信頼性の高いルールになります。22.5%最初の 4 つのアイテムも含まれるトランザクションの約32. しかし、このデータセットの数値の意味が AFAICT で不明であることを考えると、このルールが実際に興味深いものなのか、それとも単なるおもちゃの演習なのかはわかりません。

minSupport=100 にすると、ランタイムはさらに大きくなります。

1-frequentItemsets (1857)
2-frequentItemsets (2785)
3-frequentItemsets (1475)
4-frequentItemsets (306)
5-frequentItemsets (28)
6-frequentItemsets (0)
APRIORI runtime: 8256507 ms

つまり2時間以上。この時間のほとんどは 2 つの項目セットに費やされています。170 万の候補があり、そのうち 2785 が頻繁に使用されていました。3 項目セットの場合、候補は数千に過ぎないとおおまかに見積もることができますが、数百万はありません。候補の数に応じて 2 つのコードパスを切り替えることで、実装をさらに改善するいくつかの計画があります。('''更新:''' より単純な修正を加えて、ランタイムをさらに 20 分の 1 に短縮しました。つまり、'''実装が重要です'''、簡単に 100 倍から 1000 倍以上に短縮できます - APRIORI プルーニングが完全に実装されていない場合など)

Eclat アルゴリズムを読んで再実装する時間があれば、これを結果で更新できます。ここでははるかに速くなると信じており、FP の成長も同様です。

于 2014-01-22T09:10:58.713 に答える
0

実装によって異なります。Apriori を実装する際には、多くの最適化を行うことができます。

まず、Agrawal & Srikant による Apriori の元の論文を読むと、候補者の支持を効率的にカウントするために特別なハッシュ ツリーを使用することが提案されていることに気付くでしょう。この実装がどのように機能するかを確認したい場合は、SPMF オープン ソース データ マイニング ライブラリに HashTree を実装した Apriori のバージョンがあります。AprioriHT という名前です。

データベースを複数回スキャンすることを避けるための別の最適化は、AprioriTID と呼ばれます。各項目セットには、それを含むトランザクション (tid セット) の一連の ID が注釈として付けられます。次に、2 つの項目セット A と B を組み合わせて候補が生成されると、データベースをスキャンせずに AUB のサポートを直接カウントするために、A と B の tid セットの交差を実行できます。さらに最適化するために、tid セットを次のように実装できます。ビット ベクトル。APriori のこのバージョンは、AprioriTID と呼ばれます。

Pascal アルゴリズムでは、別の最適化が提案されました。Formal Concept Analysis のジェネレーター項目セットの概念を使用して、データベースをスキャンせずに、ジェネレーターの概念を使用して、いくつかの項目セットのサポートしきい値を推測することです。

もう 1 つの最適化は、Apriori の各レベルのアイテムセットを辞書順でソートし、各アイテムセットのすべてのアイテムを辞書順でソートすることです。次に、候補を生成するときに、この順序付けを使用して、すべてのアイテムセットを互いに比較してより大きな候補を生成することを回避できます。

他の最適化もあります。FIMI Web サイトには、最適化が異なるさまざまな実装があります。

最適化されたバージョンを確認したい場合は、JavaのSPMF データ マイニング ライブラリで私の実装を確認できます。また、同じ Web サイトで、FPGrowth などのより高速なアルゴリズムの実装を入手できます。

于 2014-02-26T15:49:58.553 に答える