Skip to content
検索結果に戻る

関連ルールマイニング(Apriori)

提唱者
Rakesh Agrawal & Ramakrishnan Srikant
年
1994
種類
Unsupervised pattern discovery algorithm
系統
Pattern mining

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

関連ルールマイニングは、トランザクションデータセット内のアイテム間の共起パターンを発見する教師なしデータマイニング技術である。1993年にAgrawal、Imieliński、Swamiによって正式に導入され、1994年にAgrawalとSrikantによる画期的なAprioriアルゴリズムによって洗練されたこの手法は、X ⇒ Y の形式のルールを特定する。これは、アイテムセットXを含むトランザクションがアイテムセットYも含む傾向があることを意味し、サポート、信頼度、リフトによって定量化される。

手法の背後にある直感

スーパーマーケットのレシートログを想像してみよう。パンとバターを買う何千人もの顧客が牛乳も買う場合、そのパターンは注目に値する。関連ルールマイニングは、あらゆるレシートを丹念に調べる几帳面な図書館員のように機能し、アイテムの組み合わせが一緒に現れる頻度を数え、最小頻度を超える組み合わせを表面化させる。頻繁なグループが見つかったら、アルゴリズムは次のように尋ねる:これらのアイテムをすでに持っている場合、それが次のアイテムをどれだけ確実に予測できるか?この頻度、次に信頼度という2段階のロジックがAprioriの核心である。

歴史学

Agrawal、Imieliński、Swami(1993)による基礎論文は、スーパーマーケットのトランザクションデータという文脈で関連ルール問題を定義した。AgrawalとSrikantの1994年のVLDB論文は、Aprioriアルゴリズムとその効率的な枝刈り戦略を導入し、大規模マイニングを実用的なものにした。その後の研究では、候補生成を完全に回避するFP-Growth(Hanら、2000)や、垂直データ形式でマイニングするECLATが開発され、現在データマイニングのカリキュラムの中心となっている豊かなアルゴリズムファミリーを確立した。

使うべき場面

関連ルールマイニングは、定義済みのターゲット変数なしで共起パターンを発見することを目的とする大規模なトランザクションデータセットに適している。トランザクションごとにアイテムがバイナリ(存在/不在)であると仮定する。マーケットバスケット分析、レコメンデーションシステム、Webクリックストリーム分析、および医療における共同診断発見に適している。連続データまたは順序データ(事前に離散化されていない場合)、非常に高次元のデータセット(指数関数的な候補空間)、または連想推論ではなく因果推論が必要な場合には不適切である。代替手段としては、より高速な頻繁アイテムセット列挙のためのFP-Growthや、時間的順序が重要な場合のシーケンスマイニングがある。

限界と注意点

  • 指数関数的な候補空間:アイテムの数が異なると、ルールの数は組み合わせ的に増加する。
  • サポート・信頼度フレームワークは、アイテムのベースレートが大きく変動する場合、誤解を招くルールを生成する可能性がある(リフト調整が必要)。
  • バイナリトランザクションモデルは、連続変数の離散化を必要とし、情報損失を導入する。
  • 高い最小サポート閾値は、まれだが価値のあるルールを見逃す;低い閾値は数千の些細なルールを生成する。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 完全に教師なし:ラベル付きデータや定義済みのターゲットは不要。
  • 解釈可能な出力:ルールは、サポートと信頼度が定量化された人間が読める「もし~ならば~」という形式のステートメントである。
  • Aprioriによる枝刈りによるスケーラビリティ;FP-Growthバリアントはデータベーススキャンの繰り返しを完全に排除する。
  • ドメイン非依存:小売、ヘルスケア、Web分析、バイオインフォマティクスに適用可能。

応用

  • 小売:POSトランザクションログからの商品配置とクロスセル推奨。
  • ヘルスケア:電子健康記録における診断、処置、または薬剤の共起分析。
  • Web分析:ページ推奨とナビゲーション最適化のためのクリックストリームパターン発見。
  • バイオインフォマティクス:共発現遺伝子セットとタンパク質相互作用モチーフの同定。
  • サイバーセキュリティ:侵入パターンの兆候となる相関ネットワークイベントの検出。

使い方

使い方

1

アルゴリズムはトランザクションデータベースDをスキャンして、各アイテムセットXの出現頻度を数える。アイテムセットは、そのサポート(それを包含するトランザクションの割合)がユーザー定義の最小サポート閾値σ_min以上である場合にのみ頻繁であると宣言され、L_kに配置される。このプロセスは個々のアイテム(k=1)から始まり、より大きな候補セットを反復的に構築する。

数式
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}
2

サポートの反単調性という性質は、頻繁なアイテムセットの任意のサブセットもまた頻繁でなければならないと述べている。Aprioriはこの性質を利用して、その(k-1)サブセットがすべて検証済みの頻繁セットL_{k-1}に含まれていない候補k-アイテムセットをすべて枝刈りする。これにより、検索空間が劇的に削減され、頻繁になる可能性のないアイテムセットに対する高価なデータベーススキャンが回避される。

数式
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_k
3

各頻繁アイテムセットX ∪ Yから、アルゴリズムはXとYが互いに素なサブセットであるルールX ⇒ Yを生成する。ルールは、その信頼度(YがXを与えられたときの条件付き確率、support(X ∪ Y) / support(X)として計算される)が最小信頼度閾値γ_min以上である場合にのみ保持される。このステップは、生の共起を方向性のある予測ステートメントに変換する。

数式
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}
4

保持されたルールは、リフトによってランク付けおよびフィルタリングされる。リフトは、YがXとともに現れる確率が偶然よりもどれだけ高いかを測定する。リフト > 1 は独立性以上の正の相関を示し、リフト = 1 は独立性を示し、リフト < 1 は負の相関を示す。確信度やレバレッジなどの追加の興味深さ指標は、実用的な展開のためにルールセットをさらに洗練させることができる。

数式
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)} = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}

よくある落とし穴

  • 最小サポートを低すぎると、分析担当者は偽のルールで溢れる;閾値の選択にはドメイン知識またはクロスバリデーションが必要。
  • 統計的関連性と因果関係の混同:高いリフトはXがYの原因であることを意味しない。
  • アイテム頻度分布の無視:一般的なアイテムがルールを支配し、意味のあるまれなアイテムの関連性を圧迫する。
  • 信頼度のみを品質指標として扱う;高い信頼度だが低いリフトのルールは、ランダムなチャンスよりも良く機能しない可能性がある。

よくある質問

サポート、信頼度、リフトの違いは何ですか?

サポートは、アイテムセットがデータセット全体でどれだけ頻繁に出現するかを測定する。信頼度は、後件が前件を与えられたときの条件付き確率を測定する。リフトは、共起が独立性下で期待されるものよりもどれだけ超えているかを示すために、後件の周辺頻度で信頼度を正規化する。堅牢なルール評価のためには、これら3つの指標すべてが一緒に必要である。

Aprioriアルゴリズムはどのように計算コストを削減しますか?

Aprioriは反単調性という性質を利用する:アイテムセットが頻度が低い場合、そのすべての超セットも頻度が低くなければならない。頻繁であることが検証されていないサブセットを持つ候補をすべて破棄することにより、アルゴリズムはカウントの前に検索空間の広大な部分を枝刈りし、総当たり列挙と比較して必要なデータベースパスの数を劇的に削減する。

Aprioriの代わりにFP-Growthを使用すべきなのはいつですか?

FP-Growthは、データセットが大きく、最小サポート閾値が低い場合に推奨される。なぜなら、トランザクションデータベースをコンパクトなFPツリー構造に圧縮し、明示的な候補を生成せずにパターンを直接マイニングするからである。これにより、データベースのスキャンが繰り返されることがなくなり、多くの頻繁なアイテムセットを持つ密なデータセットではAprioriよりも大幅に高速になる。

関連する手法

参考文献

  1. Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.

    DOI 文献を開く
    コピーしました。
  2. Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.

    出版物の文献を開く
    コピーしました。