| layout | title | date | tags | ||
|---|---|---|---|---|---|
post |
[Data Mining] Apriori Algorithm |
2011-12-01 |
|
P.S. 以下內容純為小弟個人研究看法，若有錯誤歡迎來信或留言指正，謝謝 <(__)>
由於這學期有修碩士班的 data mining 課程，這週要 demo 期中 project，加上我們竟然在 ICPC 後才開始寫。時間緊迫，就寫了個最簡單也很經典的 apriori algorihm。可惜執行效率不佳，另外有看到 FP-Tree 的演算法，可惜有點複雜，未來若有接觸到再研究吧。
Apriori 是在資料探勘的領域中，用來找尋關聯式規則 (association rules) 的經典演算法之一。關聯式規則的應用，較常見的例子是在顧客的購物分析上，在其他領域也有相當多的應用。一個比較常被提出的故事為「尿布與啤酒」，這故事就是發現許多顧客買了尿布就會買啤酒。經過研究分析後，發現到：「在美國，許多年輕母親都留在家中照顧嬰兒，而父親匯到超市買尿布，但往往就會順便買啤酒」。在資料探勘的領域中，藉由「尿布與啤酒」的故事，我們發現在生活上，可存在許多表面上看似毫無關連的事物，但其實有著密不可分的關係， apriori 就是被提出用來找出這些關連的演算法之一。
變數與函式
- D：Transaction Database，儲存我們所要分析資料的資料庫
- T：Transaction，資料庫中的一筆資料（交易），T ∈ D
- Support：在 D 中，支持該 itemset 的 T 佔有的比例，Support(X) = Occur(X) / Count(D) = P(X)
- Confidence：Conf(X → Y) = Support(A ∪ B) / Support(A) = P(Y | X)
- Candidate Itemset：通過 apriori 合併操作所得到的 itemset
- Frequent Itemset：support 值大於 min support 之 itemset
- C(k)：含有 k 個元素之 candidate itemset 之集合
- L(k)：含有 k 個元素之 frequent itemset 之集合
演算法流程
- 從 D 中找出 C(1)
- 再掃描 D 找出所有包含 C(1) 的 T，計算其 support，將 C(1) 中不符合 min support 的 itemset 剔除，結果即為 L(1)
- 自 L(k) 來產生其他的 L(k+1)，直到找 L(k+1) 為空集合（k 由 1 開始）
- 產生 L(k+1) 的首要步驟為合併 L(k) 來產生 C(k+1)
- 在 C(k+1) 中，若有某 itemset 其所有含 k 項的 subset 不屬於 L(k)，即可將其自 C(k+1) 剔除
- 掃描 D 找出所有包含 C(k+1) 的 T，計算其 support，將 C(k+1) 中不符合 min support 的 itemset 剔除 ，結果即為 L(k+1)
- 枚舉此 L(k+1) 中的 itemset，將 itemset 分成兩個部份 {A}{B} 的所有可能（其中 A 含有 p 個項目，而 B 含有 (k+1)-p 個項目，1<=p<=(k+1)-1）
- 判斷 P(itemset) / P(A) 是否大於等於 min confidence，若符合我們可以判斷存在 A => B 的 association rule
關於上述第 6 步驟，為什麼可以只判定含有 k 項的 subset？
由於我們每次產生的 L(k) 也都已經過 k-1 項的 subset 篩選過，在此具有向下封閉性。故我們只需要使用其 k 項的 subset 來篩選。
優點
- 簡單易懂
- 實現複雜度低
缺點
- 產生過多的 candidate itemset
- 需重複掃描資料庫
L(1) = Scan database to find {frequent itemset}
do
Gnerate C(k+1) from L(k)
Remove the itemset which has any subset that is not a frequent itemset (detect from L(k))
L(k+1) = candicates in C(k+1) with min_support
for all possible of partition L(k+1) into two parts A,B
if P(L(k+1)) / P(A) >= min_confidence
A => B is one association rule
until L(k+1) is ∅
source code on gist.