Aprioriアルゴリズムのマイニング効率をさらに高める4つの改善手法とは？

Aprioriアルゴリズムには、元のアルゴリズムの効率向上を目的としたさまざまな改良版が提案されています。本記事では、代表的な最適化手法である「ハッシュベース手法」「トランザクション削減」「分割法」「サンプリング」の4つについて詳しく解説します。

ハッシュベース手法（アイテムセットのバケットへのハッシュ）

ハッシュベースの手法を用いることで、k > 1 における候補k-アイテムセット C_k のサイズを削減できます。例えば、データベース内の各トランザクションを走査し、候補1-アイテムセット C₁ から頻出1-アイテムセット L₁ を生成する過程で、各トランザクションから2-アイテムセットを作成し、それらをハッシュテーブル構造の複数のバケットへマッピング（ハッシュ）して、対応するバケットのカウントを増加させることが可能です。

トランザクション削減（Transaction Reduction）

頻出k-アイテムセットを含まないトランザクションは、頻出(k+1)-アイテムセットを含むこともできません。したがって、そのようなトランザクションは以降の検討対象から除外（マークまたは削除）できます。なぜなら、j > k を満たす j-アイテムセットを求めるためのその後のデータベース走査では、このトランザクションが必要なくなるためです。

分割法（Partitioning）

分割法では、わずか2回のデータベース走査で頻出アイテムセットをマイニングできます。この手法は次の2つのフェーズで構成されます。

フェーズI：ローカル頻出アイテムセットの発見

まず、アルゴリズムはデータベースDのトランザクションをn個の重複しないパーティションに分割します。Dにおける最小サポート閾値が min_sup であれば、各パーティションの最小サポートカウントは「min_sup × そのパーティション内のトランザクション数」として計算されます。

続いて、各パーティションごとに、そのパーティション内で頻出となるアイテムセット（ローカル頻出アイテムセット）をすべて発見します。この処理では、各アイテムセットに対して、該当するアイテムを含むトランザクションのTID（トランザクションID）を記録する特殊なデータ構造を使用します。これにより、データベースを1回走査するだけで、k = 1, 2, ... に対応するすべてのローカル頻出k-アイテムセットを見つけられます。

フェーズII：グローバル頻出アイテムセットの決定

ローカル頻出アイテムセットは、データベース全体Dに対しても頻出であるとは限りません。しかし、D全体で真に頻出である可能性のあるアイテムセットは、必ず少なくとも1つのパーティションにおいて頻出アイテムセットとして現れます。したがって、すべてのローカル頻出アイテムセットがDのグローバルな候補アイテムセットとなり、各パーティションから得られた頻出アイテムセットの集合がDに対する全世界の候補アイテムセットを形成します。フェーズIIでは、Dの2回目の走査を実施し、各候補の実際のサポート度を評価することで、グローバルな頻出アイテムセットを最終的に確定します。

サンプリング（Sampling）

サンプリング手法の基本的な考え方は、与えられたデータDから無作為標本Sを選択し、DそのものではなくSの中から頻出アイテムセットを探索するというものです。この方法では、ある程度の正確性と引き換えに処理効率を高めるトレードオフが可能になります。標本Sのサイズは、S内での頻出アイテムセット探索をメインメモリ上で完結できるように設定されるため、全体としてはSのトランザクションを1回走査するだけで済むという大きな利点があります。