IBMのAprioriは、あり得ない候補を枝刈りして、買い物客が一緒に買うものをマイニングした

小売業者はどの商品が一緒に買われるかを知りたがっていたが、可能な商品の組み合わせの数はSKUの数とともに指数関数的に爆発した。

1994年に発表されたAprioriは、ある性質を利用する。すなわち、頻出でない項目集合の任意の上位集合もまた頻出でないはずだ、という性質である。単一項目を数え、頻出するものを残し、それらをペアへと成長させ、これを繰り返すので、親がすでに失敗した候補を数えることは決してない。

この仕掛けにより、すぐに手に負えなくなる探索が、頻出集合という小さな最前線だけに触れる探索へと変わる。それは市場バスケット分析を実用的なデータベースクエリへと変えた。

ある集合がまれであれば、その任意の上位集合もまたまれである

下方閉包性により、探索は成長する前に枝刈りされるので、実行時間はすべての集合ではなく頻出集合に比例する。

レベルごとのデータベーススキャンにより、メモリは候補集合に限定される。

それはヒューリスティックやサンプリングによる近似ではなく、正確な頻出集合を与える。

同じ枝刈りは、バスケットを超えて系列マイニングやパターンマイニングにも一般化される。

巨大な空間を探索する前に、枝全体を一度に捨てられる単調な性質を探せ。ある領域を除外する規則は、探索を指数関数的から線形へと縮小する。

Aprioriは標準的な相関ルールアルゴリズムとなり、データマイニングの標準的な教訓となった。それは推薦、品揃え、クロスセル分析を支える分野の種をまき、後にそのスキャンを削減するfpgrowthやその他の手法を生んだ。