アソシエーションルール — データの中の「一緒に買われるもの」を見つける

おむつとビールが一緒に買われる——。このパターンをデータから自動発見するのがアソシエーションルール分析です。 Support・Confidence・Liftという3つの指標と、組み合わせ爆発を回避するAprioriアルゴリズムを、一緒に見ていきましょう。

夜のスーパーで気づいたこと

スーパーのレジで並んでいると気づきます。おむつを買っている人は、なぜかビールも一緒にレジに持ってくる——。

これは冗談のような話ですが、実際に1990年代のアメリカのスーパーチェーンで発見されたパターンです。金曜の夜、育児中のパパたちが子供のおむつを買いに来たついでに、週末のビールも買っていた。このデータパターンを発見したことで、店側はおむつ売り場の近くにビールを置く陳列変更を行いました。

買い物かごの中の共起パターンが浮かび上がるアニメーション — 複数のかごに共通して現れる青と赤のアイテムが浮かび上がる

これが「アソシエーションルール分析」の本質です。

正解ラベルなしに、「一緒に現れるパターン」をデータから自動発見する。

より正式に定義しましょう。私たちのデータは、 $$N$$ 個の取引（トランザクション）で構成されます。各取引 $$i$$ について、変数 $$X_j$$ は：

$x_{ij} = 1$ ：商品 $$j$$ が購入された
$x_{ij} = 0$ ：購入されなかった

このような二値変数が $$p$$ 個あるとき（例：スーパーの全商品が $$p = 10{,}000$$ 品）、どのアイテムセット $$K$$ （商品の集合）が「よく一緒に現れるか」を発見することが目標です。

Confidenceの落とし穴、そしてLift

アソシエーションルールを評価するために、3つの指標を順に定義します。

まずSupport（支持度）。「そのアイテムセットがどれだけの割合の取引に現れるか」です：

T(K) = \frac{1}{N} \sum_{i=1}^{N} \prod_{j \in K} x_{ij}

$\prod_{j \in K} x_{ij}$ は「アイテムセット $$K$$ の全商品が購入されたときだけ 1、一つでも欠けると 0」を意味します。例えば「ビールとおむつ」が全取引の3%に現れるなら $T(\{\text{ビール}, \text{おむつ}\}) = 0.03$ 。

次にConfidence（確信度）。「 $$A$$ があるとき、 $$B$$ もある確率」です：

C(A \Rightarrow B) = \frac{T(A \cup B)}{T(A)}

おむつを買った人の中でビールも買った人が82%なら、 $C(\{\text{おむつ}\} \Rightarrow \{\text{ビール}\}) = 0.82$ 。

しかし、ここで一つの疑問を考えてみてください。

「スーパーで水を買った人は、ビールも買う確率が80%」というルールがあるとします。 Confidence = 0.80 は高い。では、これは有用なルールでしょうか？

——実は、水を買わない人でもビールを買う確率が 75% だったなら、このルールは「ほぼ全員がビールを買う」という現象を言い換えているだけで、「水との特別な関係」を発見していません。

Liftの概念をベン図で比較するアニメーション — 左：lift≈1（Bの出現確率が高く、交差の割合は小さい）　右：lift>1（Bの基本確率が低いが交差が相対的に大きい）

このような「ありふれた商品のありふれた購買」をルールに含めないために、Lift（リフト）が必要です：

L(A \Rightarrow B) = \frac{C(A \Rightarrow B)}{T(B)}

「 $$A$$ があることで $$B$$ の確率が何倍になるか」。水の例では：

L(\{\text{水}\} \Rightarrow \{\text{ビール}\}) = \frac{0.80}{0.75} \approx 1.07 \approx 1

Lift ≈ 1 なので、水とビールはほぼ独立（関連なし）。

一方、おむつとビールの例では：

L(\{\text{おむつ}\} \Rightarrow \{\text{ビール}\}) = \frac{0.82}{0.43} \approx 1.91

Lift > 1 は「正の関連あり（ $$A$$ が $$B$$ の出現を促進する）」、Lift = 1 は「独立」、Lift < 1 は「 $$A$$ が $$B$$ を抑制する」を意味します。

Aprioriアルゴリズム — 組み合わせ爆発を回避する

ここに深刻な問題があります。 $$p = 10{,}000$$ 品目があるスーパーで、すべてのアイテムセットを総当たりで調べると、 $2^{10000}$ 通りの組み合わせが生じます。これは宇宙の原子の数をはるかに超えます。

いかにして高支持度のアイテムセットを効率的に見つけるか？

ここで強力な観察があります。

反単調性（Anti-monotonicity）の原理：アイテムセット $$K$$ の支持度が閾値 $$t$$ を下回るなら、 $$K$$ を含む任意のアイテムセット（ $$K$$ に商品を追加したもの）も必ず閾値を下回る。

考えてみれば当然です。「ビールとおむつと赤ワイン」が一緒に買われる確率は、「ビールとおむつ」が一緒に買われる確率以上にはなりません。より多くの条件を要求するほど、満たす人は減ります。

Aprioriアルゴリズムの刈り込みを木構造で示すアニメーション — Dがlow supportで刈り込まれると、D含む全組み合わせが探索から除外される

これを利用したのがAprioriアルゴリズムです：

第1パス：全商品について、単独で support > t のものだけを残す。以降は残ったものだけを考える
第2パス：残った商品のペアを候補とし、support > t のペアだけを残す
第kパス：前のパスで残った $$(k-1)$$ サイズのセットから $$k$$ サイズの候補を生成し、support > t のものだけを残す

支持度の低いアイテムが一つでも含まれていれば、そのスーパーセット全体を探索から除外できます。これにより、実際の計算量は $$2^p$$ から大幅に削減されます。

Aprioriが解く問題：

\{K \mid T(K) > t\}

出力されるアソシエーションルール（supportとconfidenceの両方で足切り）：

C(A \Rightarrow B) > c \quad \text{かつ} \quad T(A \cup B) > t

実例 — サンフランシスコ・ショッピングモール調査

理論を実際のデータで確認しましょう。

サンフランシスコベイエリアのショッピングモール顧客調査データを使います。 $$N = 6{,}876$$ 件の回答者について、性別、婚姻状態、年齢、教育、職業、収入などの14変数（合計50個のダミー変数）が記録されています。このデータは特定の文化的背景を持ちますが、重要なのは「support・confidence・liftが何を発見するか」の構造的理解です。

Aprioriアルゴリズムを最小支持度 $t = 10\%$ で実行すると、前件が5個以下のルールが6,288個発見されました。

その中から、confidenceは高いがliftは低いルールと、liftが高いルールを比べてみましょう。

ルール1（confidenceは高いがliftが低い）

\text{年齢}=\text{18〜34歳, 独身} \Rightarrow \text{性別}=\text{男性}

Confidence: 99.7%（前件を満たす人のほぼ全員が男性）
Lift: 1.03（→ 男性全体の比率とほぼ同じ。関連なし）

これは「若い独身者の大半が男性」というだけで、有用な発見ではありません。

ルール2（liftが高い）

\text{言語=英語, 職業=専門職・管理職, 世帯主地位=持ち家} \Rightarrow \text{収入} \geq \$40{,}000

Support: 13.4%
Confidence: 80.8%
Lift: 2.13（→ 収入≥$40,000の全体確率より2.13倍高い）

こちらは「英語を話す専門職の持ち家オーナーは高収入の可能性が2.13倍」という、データから初めて発見できる関係性です。

Lift値の高低を棒グラフで比較するアニメーション — 左：lift=1.03（基準線とほぼ同じ高さ）　右：lift=2.13（2倍以上の価値）

アソシエーションルール分析では、高いconfidenceよりも高いliftを重視します。

発展 — 教師なし学習を「教師あり学習」として解く

ここまでのアソシエーションルールの枠組みを、さらに根本から見直す面白い視点があります。

「教師なし学習の問題を、教師あり学習に変換して解けないか？」

実は可能です。アイデアはシンプルです：

実データに $$Y = 1$$ のラベルを付ける：持っている $$N$$ 個の観測を「陽性」とする
参照分布からダミーデータを生成：均一分布など既知の分布 $$g_0(x)$$ から $$N_0$$ 個の「陰性」サンプルを生成し、 $$Y = 0$$ のラベルを付ける
分類器を学習： $$Y = 1$$ vs $$Y = 0$$ の2値分類問題として学習する
密度比を復元：学習した推定値 $\hat{\mu}(x)$ から元の密度推定値を復元： $\hat{g}(x) = g_0(x) \cdot \frac{\hat{\mu}(x)}{1 - \hat{\mu}(x)}$

教師なし問題を教師あり問題に変換する概念を示すアニメーション — 左：実データの点群（教師なし）　右：参照サンプル追加後、分類境界線が密度の高い領域を囲む（教師あり）

この方法の利点は、教師あり学習のツールをそのまま使えることです。ロジスティック回帰、決定木、SVMなど、分類で使えるものが何でも活用できます。

アソシエーションルールの文脈では、参照分布として「変数が独立な場合の分布」 $g_0(x) = \prod_j g_j(x_j)$ を使います。すると $$g(x) / g_0(x) > 1$$ の領域、つまり「独立を仮定した場合より変数が共起しやすい領域」が検出され、これはまさにアソシエーションルールが探したいものと一致します。

まとめ — パターン発見の武器

アソシエーションルール分析を振り返りましょう。

教師なし学習の中でも特に実用的なこの手法は、「一緒に現れるパターン」を自動発見します。3つの指標が重要です：

Support：どれくらいの頻度で現れるか（稀なルールを排除）
Confidence：前件があるとき後件はどれくらい確実か（ルールの強さ）
Lift：ランダムより何倍多く共起するか（真の関連性 — 最重要）

Aprioriアルゴリズムは反単調性の原理を活用し、 $$2^p$$ の組み合わせ空間を効率的に探索します。支持度の低いアイテムセットを早期に刈り込み、大規模なデータベースでも実用的な時間で計算が完了します。

アソシエーションルールをネットワークグラフで表現するアニメーション — 弱いルール（灰色）が消え、強いルール（ゴールド）だけが残る

さらに発展的な視点として、教師なし問題を教師あり問題に変換する方法があります。実データと参照サンプルを混ぜ、分類問題として解くことで、教師あり学習のあらゆるツールが使えるようになります。

アソシエーションルールは、小売業界（購買分析）、医療（症状の共起パターン）、Web行動分析（ページ遷移パターン）など、幅広い分野で活用されています。