Association rule mining (2)

[***以下為個人理解，如有錯誤歡迎指證***]

[***This article may contain mistakes and thus any correction is greatly appreciated***]

這裡補充一下關於 association rule mining 的一些知識。association rule mining (以下簡稱ARM)，又叫關聯規則挖掘，目的為發現當某個 item A 的出現，也會引發另一個 item B 的出現，我們稱為 A => B 為一個 association rule。

ARM 中定義了幾個條件：
(1) Support：該 AR 在 databases中涵蓋的資料數目。
(2) Confidence：該AR的預測強度。
(3) Frequent itemsets：又稱作 large itemsets，為T中涵蓋的資料數目大於minimum support 

的 itemsets。
任何滿足 minimum support 與 minimum confidence 的 rule，才能稱作 AR。

[--- AR 又可以分為三類 --- ]
(1) 根據 attribute 分類：item 有無、item數量。

• Boolean AR: 關注item是否出現，如『bear =>biscuits (support=15%, confidence=80%)』中找到的 bear 與 biscuits。
• Quantitative AR: 關注 item 某個範圍下的結果，如 『age(t, "40...45") ^ income(t, "7w...10w") => insurance(x, cancer insurance)』中，從age 20~30且購買bear 3~8瓶的消費者中找到 member 的 rule。

(2) 根據 dimension 分類：

• Single dimension AR: 如 『bear => biscuits』，皆為購買行為。
• multi-dimensional AR: 『age(t, "40...45") ^ income(t, "7w...10w") => insurance(x, cancer insurance)』則包含 age，income 與 insurance。

(3) 根據 abstract layer 分類：

• single-level AR: 『income(t, "7w...10w") => Computer』。
• multi-level AR:『income(t, "7w...10w") => IPad』。

針對 Boolean ARM 及 single dimension ARM 的演算法

• 採用 candidate-generate 找出frequent itemsets的 Apriori, DHP(direct hashing and pruning), Partition
• 非使用 candidate-generate 的 FP-Tree

針對 multi-level AR: 
   在每個 LEVEL 使用相同最小的 support 值，且越往下使用較小的 support 值。這裡有bottom-up 跟 top-down 的搜尋法。

針對 multi-dimension AR：(待補充)

這裡先下個結論：ARM有兩個常見的問題

• (A) 無論是哪一類的ARM，在做 frequent itemsets 搜尋時的 time cost 相當高，因此對於經常變動的 database 做 AR 的維護是很重要的。也就是說，透過增量 (incremental)的方式調整 frequent itemsets，而非針對 database 重新進行 ARM。
• (B) 如何在線上即時取得AR。frequent itemsets的計算，需要給定 user 一個 minimum support 後才以離線或批次的方法進行。但 user 一般都不知道如何選擇 minsup，導致花費太多時間卻得到無用的AR。這方面的研究多採用 Lattice 所提及的 lower/upper bound 或 sampling 的方式進行。

[Reference]
 1.  Bing Liu, UIC 
 2.  Wiki