アソシエーションルール/分析(支持度、確信度、リフト値)

協調フィルタリング推薦やバスケット分析で使われるアソシエーションルール/分析について調べました。主に著書[「推薦システム実践入門」](推薦システム実践入門)から学習しました。
<a href="https://www.amazon.co.jp/%E6%8E%A8%E8%96%A6%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0%E5%AE%9F%E8%B7%B5%E5%85%A5%E9%96%80-%E2%80%95%E4%BB%95%E4%BA%8B%E3%81%A7%E4%BD%BF%E3%81%88%E3%82%8B%E5%B0%8E%E5%85%A5%E3%82%AC%E3%82%A4%E3%83%89-%E9%A2%A8%E9%96%93-%E6%AD%A3%E5%BC%98/dp/4873119669?&linkCode=li1&tag=yoheifukuha06-22&linkId=df9399fc72b551b3cc54854cc1eb7f29&language=ja_JP&ref_=as_li_ss_il" target="_blank"><img border="0" src="//ws-fe.amazon-adsystem.com/widgets/q?_encoding=UTF8&ASIN=4873119669&Format=_SL110_&ID=AsinImage&MarketPlace=JP&ServiceVersion=20070822&WS=1&tag=yoheifukuha06-22&language=ja_JP" ></a><img src="https://ir-jp.amazon-adsystem.com/e/ir?t=yoheifukuha06-22&language=ja_JP&l=li1&o=9&a=4873119669" width="1" height="1" border="0" alt="" style="border:none !important; margin:0px !important;" />

**購買履歴データから同時購入される商品組み合わせのルールを探索**します。「おむつとビール」の話が有名ですが、真偽疑わしいようです。

https://www.itmedia.co.jp/im/articles/0504/18/news086.html

また、真偽はともかく「おむつとビール症候群」という単語もあるようで注意が必要みたいです。

https://a2i.jp/column/post-17510/

# 3つの指標
以下の3つの指標を使用します。

|指標|内容|計算式|補足|
|:-:|:-:|:-:|:--|
|支持度(support)|アイテム出現割合|$\cfrac{アイテム出現頻度}{全データ数}$||
|確信度(confidence)|アイテム同時出現割合|$\cfrac{複数アイテム同時出現頻度}{アイテム出現頻度}$||
|リフト値(lift)|アイテム間出現相関|$\cfrac{複数アイテム支持度}{支持度 \times 支持度}$|１だと相関ゼロ|

サンプルとして以下の購買履歴例で計算。

|ユーザ/トランザクション|アイテムA|アイテムB|アイテムC|
|:-:|:-:|:-:|:-:|
|1|購入|購入||
|2||購入||
|3|購入||購入|
|4|購入||購入|

## 支持度(support)
支持度(support)は**全データでの出現頻度割合**で以下の式です。

```math
\cfrac{アイテム出現頻度}{全データ数}
```

サンプルデータでの例。簡単なので一部のみ。

|対象|値|
|:-:|:-:|
|A|$\frac{3}{4}$|
|B|$\frac{2}{4}$|
|A and B|$\frac{1}{4}$|
|B and C|$\frac{0}{4}$|

## 確信度(confidence)
確信度(confidence)は**アイテム同時出現割合**で、**方向性があります**。アイテムA出現時のアイテムB出現割合だと、以下の式です。分母のAを**条件部(antecedents)**、Bを**帰結部(consequents)** と呼びます。条件部を購入した場合、帰結部をどれかけ購入するかの割合がわかります(プリンタ=>インクは高いけど逆)。

```math
確信度(A => B) = \cfrac{アイテムA・B同時出現頻度}{アイテムA出現頻度}
```

サンプルデータでの例。0の場合は、条件部と帰結部入れ替えても当然0ですね。

|対象|値|
|:-:|:-:|
|A => B|$\frac{1}{3}$|
|B => A|$\frac{1}{2}$|
|C => A|$\frac{2}{2}$|
|A => C|$\frac{2}{3}$|
|B => C|$\frac{0}{2}$|
|C => B|$\frac{0}{2}$|


## リフト値(lift)
リフト値(lift)は**アイテム間の相関**です。アイテムAとBのリフト値は以下の式です。支持度の式から支持度と確信度の式に変形できます。
※A=>BとしていますがB=>Aも同じ値です(確信度と対称性の点で異なる)。

```math
リフト(A=>B)=\cfrac{支持度A・B}{支持度A \times 支持度B}=
\cfrac{\frac{アイテムA・B同時出現頻度}{全データ数}}{\frac{アイテムA出現頻度}{全データ数} \times \frac{アイテムB出現頻度}{全データ数}} \\
= \cfrac{\frac{アイテムA・B同時出現頻度}{アイテムA出現頻度}}{\frac{アイテムB出現頻度}{全データ数}} = \cfrac{確信度(A => B)}{支持度B} \\
= \cfrac{\frac{アイテムA・B同時出現頻度}{アイテムB出現頻度}}{\frac{アイテムA出現頻度}{全データ数}} = \cfrac{確信度(B => A)}{支持度A} \\
```

値は以下の解釈です。支持度A・Bを同時購入率と考えます。

|値|解釈|説明|
|:-:|:-:|:--|
|1以下|負の相関|$支持度A \times 支持度B > 支持度A・B$で、同時購入されにくい|
|1|独立|$支持度A \times 支持度B = 支持度A・B$で、同時購入が偶然|
|1以上|正の相関|$支持度A \times 支持度B < 支持度A・B$で、同時購入されやすい|

アイテムが3つ以上の場合は以下の式です。

```math
リフト((A・B)=>C)=\cfrac{支持度A・B・C}{支持度A・B \times 支持度C}
```

サンプルデータで計算すると以下の値です。AとCは正の相関、BとCは負の相関です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/134273/fe02f2cf-5834-007a-7c57-f85e5d48b2ef.png)

# 計算処理
## アプリオリ
全件を計算すると計算量が多いので、**アプリオリアルゴリズムにより高速化**をします。一定以上の支持率のアイテム/アイテム組み合わせのみを計算対象とします(あまり調べていないので少し理解が怪しい)。
このリンク資料を起点に読み解けば効率的に理解できそうな気がしています。

https://www.kamishima.net/archive/freqpat.pdf

## Pythonとmlxtend
Pythonでは[mlxtend](http://rasbt.github.io/mlxtend/user_guide/frequent_patterns/apriori/)パッケージで計算できるようです。
サンプルを実行して理解しようとも思いましたが力尽きました。リンクを載せるだけにしておきます。

http://rasbt.github.io/mlxtend/user_guide/frequent_patterns/apriori/

http://rasbt.github.io/mlxtend/user_guide/frequent_patterns/association_rules/