P.S. 以下內容純為小弟個人研究看法，若有錯誤歡迎來信或留言指正，謝謝 <(__)>

由於這學期有修碩士班的 data mining 課程，這週要 demo 期中 project，加上我們竟然在 ICPC 後才開始寫。時間緊迫，就寫了個最簡單也很經典的 apriori algorihm。可惜執行效率不佳，另外有看到 FP-Tree 的演算法，可惜有點複雜，未來若有接觸到再研究吧。

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(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 之集合

演算法流程

  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

關於上述第 6 步驟，為什麼可以只判定含有 k 項的 subset？

由於我們每次產生的 L(k) 也都已經過 k-1 項的 subset 篩選過，在此具有向下封閉性。故我們只需要使用其 k 項的 subset 來篩選。

優點

  • 簡單易懂
  • 實現複雜度低

缺點

  • 產生過多的 candidate itemset
  • 需重複掃描資料庫

Pseudo Code

1
2
3
4
5
6
7
8
9
10
11
12
13

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 ∅

C++ Implementation

source code on gist.

Reference