Aprioriアルゴリズムの計算量とは？影響する要因と計算コストを徹底解説

Aprioriアルゴリズムは、大量のトランザクションデータから頻出項目集合を抽出する代表的な手法ですが、その計算複雑性（計算量）は複数の要因によって大きく変動します。本記事では、実行時間に影響を与える主な要因と、各処理ステップにおける計算コストをわかりやすく解説します。

計算量に影響を与える4つの主要因

1. 支持度閾値（Support Threshold）

支持度閾値を低く設定すると、「頻出」と判定される項目集合の数が増加します。その結果、生成・カウントすべき候補項目集合が膨大になり、計算負荷が大幅に上昇します。

さらに、閾値が低いほど頻出項目集合の最大サイズも大きくなる傾向があります。最大サイズが大きくなると、データセットに対する走査（パス）の回数が増え、処理時間がさらに延びてしまいます。

2. 項目数（次元数）

扱う項目の種類が増えると、各項目の支持度カウントを保存するためのメモリ領域も拡張が必要です。また、データの次元数が上がると頻出項目の数も増加し、それに伴って生成される候補項目集合が多くなるため、計算量とI/Oコストの両方が増大します。

3. トランザクション数

Aprioriアルゴリズムはデータセットを繰り返し走査する仕組みのため、トランザクション数が多いほど実行時間は長くなります。

4. 平均トランザクション幅

密度の高いデータセットでは、1件あたりの平均項目数（平均トランザクション幅）が大きくなります。これは以下の2つの側面から計算量に影響します。

• 平均トランザクション幅が大きいほど、頻出項目集合の最大サイズが大きくなる傾向がある。
• トランザクション幅が広がると、1件のトランザクションに含まれる項目集合の数が増え、支持度カウント時に行われるハッシュツリー探索の回数が増加する。

各処理ステップの計算コスト詳細

頻出1項目集合の生成

各トランザクションに含まれるすべての項目について、支持度カウントを更新する必要があります。平均トランザクション幅を w、トランザクション総数を N とすると、この処理に必要な時間は O(Nw) です。

候補生成（Candidate Generation）

候補となる k 項目集合を生成する際には、頻出 (k−1) 項目集合のペアを組み合わせ、両者が共通して持つ項目が k−2 個であるかを判定します。各結合操作には最大で k−2 回の等価比較が必要です。

最良ケース： 各結合ステップごとに有効な候補 k 項目集合が1つ生成されるため、効率的に処理が進みます。

最悪ケース： 前回の反復で発見された頻出 (k−1) 項目集合のすべてのペアを組み合わせる必要があります。この場合、頻出項目集合のマージにかかる総コストは次の範囲に収まります。

Σ_k=2^w (k−2)|C_k| ＜ マージコスト ＜ Σ_k=2^w (k−2)|F_k−1|²

ハッシュツリーの構築

候補生成の過程では、候補項目集合を格納するためのハッシュツリーも構築されます。ツリーの最大深度が k であることから、候補項目集合を挿入するコストは O(Σ_k=2^w k|C_k|) となります。

候補刈り込み（Candidate Pruning）

候補刈り込みのステップでは、各候補 k 項目集合の (k−2) 個の部分集合がすべて頻出であるかを検証する必要があります。ハッシュツリー内での1件の候補検索コストが O(k) であるため、このステップ全体に必要な時間は O(Σ_k=2^w k|C_k|) です。

まとめ

Aprioriアルゴリズムの計算量は、支持度閾値、項目数、トランザクション数、平均トランザクション幅といったデータ特性に強く依存します。特に候補生成と候補刈り込みの段階では、候補項目集合の数 |C_k| が計算コストを左右する重要な要素となります。大規模データを扱う場合は、これらの要因を踏まえたパラメータ設計や、FP-Growthなどの代替アルゴリズムの検討も有効です。