【Data Mining】Note 1- Apriori Algorithm

如標題所述，這次我要扯的是 Apriori演算法╮(╯_╰)╭

Introduction

Apriori, a classic algorithm for learning association rules, is designed to operate on databases containing transactions, for instance, collections of items bought by customers or details of a website frequentation, which is different with other algorithms that are designed for finding association rules in data having no transactions, or having no timestamps.

The algorithm aims to find the rules which satisfy both a minimum support threshold and a minimum confidence threshold.

●Item: article in the basket.

●Itemset: a group of items purchased together in a single transaction.

How Apriori Works

1° Find all frequent itemsets

● Get frequent items

○ Items whose occurrence in database is greater than or equal to the min.support threshold.

● Get frequent itemsets

○ Generate candidates from frequent items.

○ Prune the results to find the frequent itemsets.

2° Generate strong association rules from frequent itemsets

● Rules which satisfy the min.support and min.confidence threshold.

Lattice

● Closed Itemset: support of all parents are not equal to the support of the itemset.

● Maximal Itemset: all parents of that itemset must be infrequent.

事實上我的理解就是——

簡單地說（不大嚴謹），這個演算法就是算一個東西出現的頻率/頻次，然後和一個既定的概率比較大小，篩掉一些不符合的集合，接著算一個鏈接集合出現的頻率/頻次，繼續比大小……反覆多次直到不能再重複了，最後得到一個集合。完事。

不要問我為什麼中英文混雜。

因為，上課用的課本/PPT是全英文的，而且寫這個筆記前半段的時候我輸入法壞掉了只能打英文，而我不想翻譯……

順便附上一個疑似誤傳，進而導致誤導/易錯的問題：

假設有頻繁3-項集{A,B,C}{B,C,D}{B,C,E}{B,C,F}{B,D,E}{C,D,E}

則得到候選4-項集的連接步：{B,C,D,E}{B,C,E,F} 剪枝得：{B,C,D,E}（{C,E,F}不是頻繁的，所以劃掉{B,C,E,F}）

易錯！{A,B,C}{B,C,D}是不可連的！我不知道為什麼網上有些介紹apriori舉例子的時候把他們當可連的了。我就不po鏈接了~

連接步的要求是前k-2項相同，否則不可連~因為連了剪枝步也要剪掉啊~也就是這麼連將出現非頻繁子集。比如上面的{A,B,C}{B,C,D}，如果連接則得到{A,B,C,D}可是，{A,C,D}並不是頻繁的。

嚴謹的數學證明我有空再寫……不過我覺得這個還是好理解的吧~