[ ML 文章收集 ] Apriori Algorithm Introduction

來源自 這裡
Preface:
apriori 是在資料探勘的領域中，用來找尋關聯式規則（association rules）的經典演算法之一。關聯式規則的應用，較常見的例子是在顧客的購物分析上，在其他領域也有相當多的應用。一個比較常被提出的故事為「尿布與啤酒」，這故事就是發現許多顧客買了尿布就會買啤酒。經過研究分析後，發現到：「在美國，許多年輕母親都留在家中照顧嬰兒，而父親匯到超市買尿布，但往往就會順便買啤酒」。在資料探勘的領域中，藉由「尿布與啤酒」的故事，我們發現在生活上，可存在許多表面上看似毫無關連的事物，但其實有著密不可分的關係。apriori 就是被提出用來找出這些關連的演算法之一.

Algorithm:
首先來看看這個演算法會用到的符號：

* D:Transaction Database，儲存我們所要分析資料的資料庫
* T：Transaction，資料庫中的一筆資料（交易），T ∈ D
* Support：在 D 中，支持該 itemset 的 T 佔有的比例，Support( X ) = Occur( X ) / Count( D ) = P( X )
* Confidence：Conf( X → Y) = Support( X ∩ Y ) / Support( X ) = P( Y | X )
* Candidate Itemset：通過 apriori 合併操作所得到的 itemset
* Frequent Itemset：support 值大於 min support 之 itemset
* C(k)：含有 k 個元素之 candicate itemset 之集合
* L(k)：含有 k 個元素之 frequent itemset 之集合

底下是演算法的文字說明:

1. 從 D 中找出 C(1)
2. 再掃描 D 找出所有包含 C(1) 的 T，計算其 support，將 C(1) 中不符合 min support 的 itemset 剔除，結果即為 L(1)
3. 自 L(k) 來產生其他的 L(k+1)，直到找 L(k+1) 為空集合（k 由 1 開始）
4. 產生 L(k+1) 的首要步驟為合併 L(k) 來產生 C(k+1)
5. 在 C(k+1) 中，若有某 itemset 其所有含 k 項的 subset 不屬於 L(k)，即可將其自 C(k+1) 剔除
6. 掃描 D 找出所有包含 C(k+1) 的 T，計算其 support，將 C(k+1) 中不符合 min support 的 itemset 剔除 ，結果即為 L(k+1)
7. 枚舉此 L(k+1) 中的 itemset，將 itemset 分成兩個部份 {A}{B} 的所有可能（其中 A 含有 p 個項目，而 B 含有 (k+1)-p 個項目，1<=p<=(k+1)-1）
8. 判斷 P(itemset) / P(A) 是否大於等於 min confidence，若符合我們可以判斷存在 A => B 的 association rule

而 Pseudo code 如下:

view plaincopy to clipboardprint?

1. L(1) = Scan database to find {frequent itemset}  
2.       
3. do  
4.     Gnerate C(k+1) from L(k)  
5.     Remove the itemset which has any subset that is not a frequent itemset (detect from L(k))  
6.     L(k+1) = candicates in C(k+1) with min_support  
7.       
8.     for all possible of partition L(k+1) into two parts A,B  
9.         if P(L(k+1)) / P(A) >= min_confidence  
10.             A => B is one association rule  
11.       
12. until L(k+1) is ∅  

上面演算法的優點是 1) 簡單易懂, 2)實現複雜度低. 而缺點是 1)產生過多的 candicate itemset, 2)需重複掃描資料庫.

Implementation:
如果是 C 語言, 則你可以參考原文中的鏈結 Gist, 而下面是我使用 Java 實作的代碼. 完整的代碼可以在 這裡 下載.

- 定義訓練資料
要使用我撰寫的 Apriori 實作, 首先要定義訓練資料的類別, 而資料類別都需要實作介面 IDataBean. 這邊我定義資料類別 RichData:

view plaincopy to clipboardprint?

1. package ml.alg.apriori;  
2.   
3. public class RichData implements IDataBean{  
4.     public String outlook=null;  
5.     public String age=null;  
6.     public String height=null;  
7.     public Boolean hasCar=null;  
8.     @Target  
9.     public Boolean rich=null;  
10.       
11.     public RichData()  
12.     {  
13.           
14.     }  
15.       
16.     public RichData(String outlook, String age, String height, boolean hasCar, boolean rich)  
17.     {  
18.         this.outlook = outlook;  
19.         this.age = age;  
20.         this.height = height;  
21.         this.hasCar = hasCar;  
22.         this.rich = rich;  
23.     }  
24. }  

上面定義了我們的資料包含了欄位 "outlook", "age", "height", "hasCar" 與 "rich", 這邊我們藉由 annotation @Target 告訴工具說欄位 "rich" 為目標欄位, 也就是說產生的規則 condition->result 格式中欄位 "rich" 會是 result!

有了訓練資料後, 我們便可以如下進行 Apriori algorithm 的運行並列印出產生的 association rules:

view plaincopy to clipboardprint?

1. Apriori apriori = new Apriori(Level.ALL);  
2. // Add training data set  
3. apriori.addT(AddRichData("ugly", "m", "m", true, true));  
4. apriori.addT(AddRichData("normal", "y", "m", false, false));  
5. apriori.addT(AddRichData("handsome", "m", "h", false, false));  
6. apriori.addT(AddRichData("ugly", "o", "l", false, false));  
7. apriori.addT(AddRichData("normal", "m", "m", true, true));  
8. apriori.addT(AddRichData("normal", "y", "m", false, false));  
9. apriori.addT(AddRichData("normal", "m", "m", true, true));  
10. apriori.addT(AddRichData("ugly", "o", "h", false, true));  
11. apriori.addT(AddRichData("handsome", "y", "h", true, true));  
12. apriori.addT(AddRichData("handsome", "y", "l", false, true));  
13. apriori.addT(AddRichData("ugly", "y", "l", true, true));  
14. apriori.addT(AddRichData("ugly", "m", "l", false, false));  
15. apriori.addT(AddRichData("ugly", "y", "l", false, true));  
16. apriori.addT(AddRichData("normal", "m", "m", true, true));  
17. apriori.addT(AddRichData("ugly", "o", "m", true, true));  
18. apriori.addT(AddRichData("handsome", "m", "m", false, false));  
19. apriori.addT(AddRichData("handsome", "y", "m", false, false));  
20. apriori.addT(AddRichData("handsome", "y", "m", false, true));  
21. apriori.addT(AddRichData("handsome", "y", "l", false, false));  
22. apriori.addT(AddRichData("handsome", "m", "m", true, true));  
23. apriori.addT(AddRichData("ugly", "o", "l", true, true));  
24. apriori.addT(AddRichData("normal", "m", "h", true, false));  
25. apriori.addT(AddRichData("normal", "m", "h", false, false));  
26. apriori.addT(AddRichData("normal", "m", "h", true, true));  
27. apriori.addT(AddRichData("normal", "m", "m", true, true));  
28.   
29. // Run association learning  
30. List ruleList = apriori.run();  
31.   
32. // Output result  
33. for(Rule r:ruleList) System.out.printf("%s\n", r);  

執行結果如下:

hasCar=true->rich=true (0.44, 0.92) # 說明只要有車 (hasCar=true) 就是有錢, 其 support=0.44; confidence=0.92
age=m,height=m->rich=true (0.24, 0.86)
hasCar=false,height=m->rich=false (0.16, 0.80)
hasCar=true,height=m->rich=true (0.28, 1.00)
hasCar=false,outlook=normal->rich=false (0.12, 1.00)
hasCar=true,outlook=normal->rich=true (0.20, 0.83)
hasCar=true,outlook=ugly->rich=true (0.16, 1.00)
age=m,hasCar=false->rich=false (0.16, 1.00)
age=m,hasCar=true->rich=true (0.28, 0.88)
age=m,height=m,outlook=normal->rich=true (0.16, 1.00)
hasCar=true,height=m,outlook=normal->rich=true (0.16, 1.00)
age=m,hasCar=true,height=m->rich=true (0.24, 1.00)
age=m,hasCar=true,outlook=normal->rich=true (0.20, 0.83)

Supplement:
* Apriori - Association Rule Induction / Frequent Item Set Mining

Christian Borgelt's Web Pages - A program to find association rules and frequent item sets (also closed and maximal as well as generators) with the Apriori algorithm (Agrawal et al. 1993), which carries out a breadth first search on the subset lattice and determines the support of item sets by subset tests...

* CODE PROJECT - Apriori Algorithm

In data mining, Apriori is a classic algorithm for learning association rules. Apriori is designed to operate on databases containing transactions (for example, collections of items bought by customers, or details of a website frequentation)...

This message was edited 16 times. Last update was at 30/05/2013 13:37:02