アプリオリアルゴリズムとは？仕組みと特徴をわかりやすく解説

Apriori（アプライオリ）アルゴリズムは、R. Agrawal と R. Srikant によって1994年に開発された、データマイニング分野における画期的なアルゴリズムです。ブール型相関ルール（Boolean association rules）のための頻出アイテムセットの抽出を目的としており、頻出アイテムセットが持つ性質に関する事前知識を活用する点が大きな特徴となっています。

レベルワイズ探索による頻出アイテムセットの発見

Aprioriは「レベルワイズ探索（level-wise search）」と呼ばれる反復的な手法を採用しています。これは、k-アイテムセットをもとに(k+1)-アイテムセットを順次探索していくアプローチです。

まず、データベースを走査して各アイテムの出現回数を集計し、最小サポート条件を満たすアイテムのみを抽出することで、頻出1-アイテムセットの集合を発見します。この結果得られる集合は L₁ と表記されます。

続いて、L₁ をもとに頻出2-アイテムセットの集合 L₂ を求め、さらにそこから L₃ を導出するという処理を繰り返します。この反復は、新たな頻出k-アイテムセットが見つからなくなるまで継続されます。なお、各 L_k を求める際には、データベースの完全なスキャンが1回必要となる点に注意してください。

アプリオリ特性（Apriori Property）

レベルワイズな頻出アイテムセット生成の効率を高めるうえで鍵となるのが、「アプリオリ特性」と呼ばれる重要な性質です。この特性を利用することで、探索空間を大幅に削減できます。

アプリオリ特性： 頻出アイテムセットの空でない部分集合は、必ず頻出でもある。

特性の根拠となる観察

この特性は、以下のような観察に基づいています。定義により、あるアイテムセット I が最小サポート閾値 min_sup を満たさない場合、I は頻出ではありません。すなわち、P(I) < min_sup が成立します。

ここで、アイテム A をアイテムセット I に追加することを考えてみましょう。追加によって得られる新しいアイテムセット（I ∪ A）が I よりも頻繁に出現することはありません。したがって、I ∪ A も頻出ではなく、P(I ∪ A) < min_sup が成り立ちます。

反単調性との関係

この性質は「反単調性（antimonotone）」と呼ばれる性質群の一種に分類されます。ある集合がある判定条件を満たさない場合、その上位集合も同じ判定条件を満たさなくなる、という意味での反単調性です。判定に不合格となる方向に対して単調に振る舞うことから、「反単調」と呼ばれています。

候補生成の2段階プロセス：結合と枝刈り

Aprioriにおける候補アイテムセットの生成は、「結合（join）」と「枝刈り（prune）」の2つのステップで構成されるプロセスに従います。

結合ステップ（Join Step）

L_k を求めるために、L_k−1 をそれ自身と結合することで、候補k-アイテムセットの集合が生成されます。この候補の集合は C_k と表記されます。l₁ と l₂ が L_k−1 に含まれるアイテムセットであるとします。表記 l_i[j] は、アイテムセット l_i 内の j 番目のアイテムを意味します（例：l₁[k−2] は l₁ の末尾から2番目のアイテムを指します）。

枝刈りステップ（Prune Step）

C_k は L_k の上位集合です。つまり、C_k のメンバーすべてが頻出であるとは限りませんが、すべての頻出k-アイテムセットは C_k に含まれています。データベースをスキャンして C_k 内の各候補の出現回数を計測することで、L_k を確定できます。出現回数が最小サポートカウント以上の候補は、定義上、頻出アイテムセットとして L_k に属することになります。

ただし、C_k は非常に大きなサイズになり得るため、計算コストが膨大になる可能性がある点には留意が必要です。