アプリオリアルゴリズムとは何ですか？

Aprioriは、1994年にR.AgrawalとR.Srikantによって開発された独創的なアルゴリズムであり、ブール相関ルールの頻繁なアイテムセットを作成します。アルゴリズムは、アルゴリズムが頻繁なアイテムセットのプロパティに関する事前の知識を必要とする場合に依存します。

Aprioriは、レベルワイズ検索と呼ばれる反復法を使用します。この方法では、k個のアイテムセットが（k + 1）個のアイテムセットを探索できます。まず、データベースを参照して各アイテムのカウントを収集し、最小限のサポートを満たすアイテムを受け取ることによって、頻繁な1アイテムセットのセットが検出されます。結果のセットはL₁で示されます 。

次に、L ₁ L ₂を見つけることができます 、L ₃を見つけることができる頻繁な2アイテムセットのセット 、など、より頻繁なkアイテムセットが検出されなくなるまで。各L_kの結果 データベースの完全なスキャンが1回必要でした。

これにより、Aprioriプロパティとして知られる必須プロパティである、頻繁なアイテムセットのレベルごとの生成の有効性を高めることができます。検索スペースを減らすことができます。

アプリオリプロパティ −頻繁なアイテムセットの空でないサブセットも頻繁に使用する必要があります。

Aprioriプロパティは、次の観察に依存します。説明により、アイテムセットIが最小サポートしきい値min supを満たさない場合、Iは頻繁ではありません。つまり、P（I）

アイテムAがアイテムセットIに挿入された場合、結果のアイテムセット（つまり、I∪A）はIよりも定期的に表示されません。したがって、I∪AはP（I∪A）>

このプロパティは、セットがテストを変更できない場合、一部のスーパーセットも同様のテストを拒否するという意味で、アンチモノトーンと呼ばれるプロパティの要素に属します。テストを拒否するという状況ではプロパティが単調であるため、これは反単調として知られています。

次のような参加アクションとプルーニングアクションを含む、2段階のプロセスが続きます-

参加ステップ − L _kを見つけることができます 、候補kアイテムセットのセットは、L _kを結合することによって生成されます。 -1それ自体で。この候補のセットはC_kで示されます 。 L ₁ およびL₂ L _kのアイテムセットである -1。ドキュメントL_i [j]はL_iのj番目のアイテムを定義します （例：L ₁ [k-2]は、L ₁の最後から2番目の項目を定義します 。

プルーンステップ − c _k L _kのスーパーセットです つまり、そのメンバーは頻繁に使用することはできませんが、いくつかの頻繁なkアイテムセットがC _kに含まれています。 。 C _kのすべての候補者の数を決定するためのデータベースのスキャン L _kの決定につながる可能性があります （つまり、最小サポート数以上の数の候補者は、説明によって頻繁に使用されるため、L _kに属します。 ）。 C _k 大きくすることができ、大きな計算を含めることができます。