アプリオリ・アルゴリズム

Rで学ぶマーケットバスケット分析

Christopher Bruffaerts

Statistician

アソシエーションルールマイニング

アソシエーションルールマイニングは、大規模な取引データでアイテム間の関係を発見します。

このタスクは2つに分かれます。

頻出アイテム集合の生成: 取引データからすべての頻出アイテム集合を抽出。最小サポートしきい値を満たせば頻出とみなします。
ルール生成: 上の頻出集合から、最小信頼度しきい値以上のルールを生成。

アプリオリ・アルゴリズムは、この分野の古典的かつ高速な手法です。

アプリオリ・アルゴリズムの考え方

アプリオリ・アルゴリズムの要点:

ボトムアップ方式
アプリオリ原理を用いて候補集合を生成

アプリオリ原理:

あるアイテム集合が頻出なら、そのすべての部分集合も頻出。
- 例: {A,B} が頻出なら {A} と {B} も頻出
逆に、非頻出集合のすべての上位集合は非頻出。
- 例: {A} が非頻出なら {A,B}, {A,C}, {A,B,C} は非頻出

¹ Agrawal and Srikant (1994)

例: 1-アイテム集合

アイテム集合ラティス2

TID	取引
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ 最小サポートしきい値 = 3/7 = 0.42

例: 2-アイテム集合

アイテム集合ラティス3

TID	取引
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ 最小サポートしきい値 = 3/7 = 0.42

例: 3-アイテム集合

全アイテム集合

TID	取引
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ 最小サポートしきい値 = 3/7 = 0.42

例: 頻出アイテム集合

アイテム集合ラティス3

アイテム集合	個数	サポート
{A}	3	0.42
{B}	6	0.85
{C}	4	0.57
{D}	5	0.71
{A,B}	3	0.42
{B,C}	3	0.42
{B,D}	4	0.57
{C,D}	3	0.42

¹ 最小サポートしきい値 = 3/7 = 0.42

Apriori: ルール生成

計算コストの高い頻出集合の抽出後、apriori はルールを生成します:

まず単一前件で高信頼度のルールから開始
- 例: {A,C} $\rightarrow$ {B}
右辺のアイテム数を増やし、より複雑なルールへ拡張
- 例: {A,C} $\rightarrow$ {B, D}

コツ: ルールの枝刈り

例: ルール {B,C,D} $\rightarrow$ {A} の信頼度が低ければ、結論に A を含むすべてのルールを破棄できます（{B,D} $\rightarrow$ {A, C} や {D} $\rightarrow$ {A,B, C} など）。

apriori を試す（初回）

取引データ

inspect(head(trans,2))

    items     transactionID
[1] {A,B,C,D} 1            
[2] {A,B,D}   2

apriori の初回呼び出し - 頻出アイテム集合

support.all = apriori(trans, 
                      parameter = list(supp = 3/7, target="frequent itemsets"))

apriori の出力 - 頻出アイテム集合

頻出アイテム集合

inspect(support.all)

    items support   count
[1] {A}   0.4285714 3    
[2] {C}   0.5714286 4    
[3] {D}   0.7142857 5    
[4] {B}   0.8571429 6    
[5] {A,B} 0.4285714 3    
[6] {C,D} 0.4285714 3    
[7] {B,C} 0.4285714 3    
[8] {B,D} 0.5714286 4

アイテム集合ラティス3

apriori 関数でルール抽出

パラメータ: マイニングの設定で抽出される集合やルールが変わります。

サポート = 3/7
信頼度 = 60%
ルールの最小長 = 2

ルール抽出のための apriori 呼び出し（引数指定）

rules.all = apriori(trans,
                parameter = list(supp=3/7, conf=0.6, minlen=2),
                control = list(verbose=F)
                   )

ルール抽出: 出力

ルールの確認

inspect(rules.all)

    lhs    rhs support   confidence lift      count
[1] {A} => {B} 0.4285714 1.0000000  1.1666667 3    
[2] {C} => {D} 0.4285714 0.7500000  1.0500000 3    
[3] {D} => {C} 0.4285714 0.6000000  1.0500000 3    
[4] {C} => {B} 0.4285714 0.7500000  0.8750000 3    
[5] {D} => {B} 0.5714286 0.8000000  0.9333333 4    
[6] {B} => {D} 0.5714286 0.6666667  0.9333333 4

演習に進みましょう！

Rで学ぶマーケットバスケット分析