相関ルール

相関ルール (association rule) †

(バスケットデータの項目の記号を参照)

アイテム集合 \(X\subseteq\mathcal{I}\) が，トランザクション \(T\) を含むとは \(X\subseteq T\) であること．

アイテム集合 \(X\subseteq\mathcal{I}\) について，\(\mathrm{count}(X)\) は，バスケットデータ \(D\)中のトランザクションで，\(X\) を含むものの個数．

\(X,Y\subseteq\mathcal{I}\) が \(X\cap Y=\emptyset\) であるとする．相関ルール(association rule)は\(X\Rightarrow Y\) の形式で，「\(X\) を含むトランザクションは \(Y\) も含む」ことを示す．論理学でいう含意にあたる． \(X\) を前提部(antecedent)，\(Y\) を結論部(consequent) と呼ぶ．

相関ルールの評価指標には次のようなものがある．

• 支持度 (support)：全トランザクション数に対する，\(X\) と \(Y\) とを共に含むトランザクション数の比．\(\Pr[X,Y]\) に相当． \[\mathrm{support}(X)=\frac{\mathrm{count}(X)}{|D|}\] \[\mathrm{support}(X\Rightarrow Y)=\frac{\mathrm{count}(X\cup Y)}{|D|}\]
• 確信度 (confidence)：\(X\) を満たすトランザクション数に対する， \(X\) と \(Y\) を共に含むトランザクション数の比．\(\Pr[Y|X]\) に相当． \[\mathrm{confidence}(X\Rightarrow Y)=\frac{\mathrm{count}(X\cup Y)}{\mathrm{count}(X)}=\frac{\mathrm{support}(X\Rightarrow Y)}{\mathrm{support}(X)}\]
• リフト (lift)：\(\Pr[Y,X]/\Pr[X]\Pr[Y]\) に相当． \[\mathrm{lift}(X\Rightarrow Y)=\frac{\mathrm{confidence}(X\Rightarrow Y)}{\mathrm{support}(Y)}\]

支持度と確信度が一定以上になるような相関ルールを列挙する解析がよく行われる． 例外を含むものや，バスケットデータの時系列を扱うといった拡張もある．

-- しましま

関連項目 †

• association rule
   
• バスケットデータ
• データマイニング
• 頻出パターンマイニング
• Apriori
• おむつとビール
   
• 検索:相関ルール

リンク集 †

• Rakesh Agrawalのホームページ 関連文献がダウンロードできる
   
• Wikipedia:Pattern_mining

Freeware †

• mloss:association-rules
• Weka：Associateの項目にいくつかのアルゴリズムが実装されている．
• MUSASHI：xtasruleコマンドで生成できる．
• Natto：データ視覚化，相関ルール

関連文献 †

• 基本文献
  R. Agrawal, T. Imielinski, A. Swami "Mining Associations between Sets of Items in Massive Databases", Proc. of the ACM-SIGMOD Int'l Conference on Management of Data, (1993)
  GoogleScholarAll:Mining Associations between Sets of Items in Massive Databases
• Book/データマイニング(データサイエンスシリーズ3) 3章, 4章
• Book/Data Mining - Concepts and Techniques 5.1章
• Book/Data Mining - Practical Machine Learning Tools and Techniques 4.5章
• Book/Principles of Data Mining 13.3章
• Book/The Elements of Statistical Learning 14.2章
• Book/人工知能学事典 13-10節
• Book/データマイニングの基礎 2.5節