關聯規則挖掘演算法

關聯規則挖掘是一種基於規則的機器學習演算法，該演算法可以在大資料庫中發現感興趣的關係。它的目的是利用一些度量指標來分辨資料庫中存在的強規則。也即是說關聯規則挖掘是用於知識發現，而非預測，所以是屬於無監督的機器學習方法。

「尿布與啤酒」是一個典型的關聯規則挖掘的例子，沃爾瑪為了能夠準確了解顧客在其門店的購買習慣，對其顧客的購物行為進行購物籃分析，想知道顧客經常一起購買的商品有哪些。沃爾瑪利用所有用戶的歷史購物信息來進行挖掘分析，一個意外的發現是："跟尿布一起購買最多的商品竟是啤酒！

關聯規則挖掘演算法不僅被應用於購物籃分析，還被廣泛的應用於網頁瀏覽偏好挖掘，入侵檢測，連續生產和生物信息學領域。

與序列挖掘演算法不同的是，傳統的關聯規則挖掘演算法通常不考慮事務內或者事件之間的順序。

支持度和置信度

那麼我們如何能夠從所有可能規則的集合中選擇感興趣的規則呢？需要利用一些度量方法來篩選和過濾，比較有名的度量方法是最小支持度（minimum support）和最小置信度（minimum confidence）。

假定我們一個資料庫包含5條事務，每行表示一個購物記錄，1 表示購買，0 表示沒有購買，如下圖表格所示：

讓 X，Y 各表示為一個 item-set, X ? Y 表示為一條規則（尿布 ? 啤酒 就是一條規則），用 T 表示為事務資料庫（並不是說只局限於事務資料庫）。

支持度

支持度表示 item-set 在整個 T 中出現的頻率。假定 T 中含有 N 條數據，那麼支持度的計算公式為：

譬如在上面的示例資料庫中，{beer, diaper} 的支持度為 1/5 = 0.2。5 條事務中只有一條事務同事包含 beer和 diaper ，實際使用中我們會設置一個最低的支持度（minimum support），那些大於或等於最低支持度的 X 稱之為頻繁的 item-set 。

置信度

置信度表示為規則 X ? Y 在整個 T 中出現的頻率。而置信度的值表示的意思是在包含了 X 的條件下，還含有 Y 的事務佔總事務的比例。同樣假定 T 中含有 N 條數據，那麼置信度的計算公式為：

譬如再上面的示例資料庫中，{beer, diaper} 的置信度為 0.2/0.2 = 1。表面在所有包含 beer 的事務中都會一定包含 diaper。同樣的，在實際使用中我們會設置一個最低置信度，那些大於或等於最小置信度的規則我們稱之為是有意義的規則。

相關性變數

有時候使用支持度和置信度挖掘到的規則可能是無效的。

舉個例子：

10000 個事務中, 6000 個事務包含計算機遊戲, 7500 個包含遊戲機遊戲, 4000 個事務同時包含兩者。關聯規則（計算機遊戲 ? 遊戲機遊戲） 支持度為 0.4 ，看似很高，但其實這個關聯規則是一個誤導。在用戶購買了計算機遊戲後有 (4000÷6000) = 0.667 的概率的去購買遊戲機遊戲，而在沒有任何前提條件時，用戶反而有 (7500÷10000) = 0.75的概率去購買遊戲機遊戲，也就是說設置了購買計算機遊戲這樣的前置條件反而會降低用戶去購買遊戲機遊戲的概率，所以計算機遊戲和遊戲機遊戲是相斥的，也即表明是獨立的。

因此我們可以通過下面的一些相關性度量方法來篩選挖掘到的規則。

提升度

提升度可以用來判斷規則 X ? Y 中的 X 和 Y 是否獨立，如果獨立，那麼這個規則是無效的。

計算提升度的公式如下：

如果該值等於 1 ,說明兩個條件沒有任何關聯。如果小於 1 ,說明 X 與 Y 是負相關的關係，意味著一個出現可能導致另外一個不出現。大於 1 才表示具有正相關的關係。一般在數據挖掘中當提升度大於 3 時,我們才承認挖掘出的關聯規則是有價值的。

他可以用來評估一個出現提升另外一個出現的程度。

提升度是一種比較簡單的判斷手法，實際中受零事務（也即不包含 X 也不包含 Y 的事務）的影響比較大。所以如果數據中含有的零事務數量較大，該度量則不合適使用。

全置信度和最大置信度

給定兩個項集 X 和 Y ，其全置信度為

不難知道，最大置信度為

全置信度和最大置信度的取值都是從 0 ~ 1 ，值越大，聯繫越大。

該度量是不受零事務影響的。

KULC 度量 + 不平衡比（IR）

給定兩個項集 X 和 Y，其 Kulczynski(Kulc) 度量定義為：

可以看做是兩個置信度的平均值，同樣取值也是從 0 ~ 1，值越大，聯繫越大，關係越大。

該度量同樣也是不受零事務影響的。

Apriori 演算法

在執行演算法之前，用戶需要先給定最小的支持度和最小的置信度。

生成關聯規則一般被劃分為如下兩個步驟：

1、利用最小支持度從資料庫中找到頻繁項集。

給定一個資料庫 D ，尋找頻繁項集流程如下圖所示

C1 中 {1} 的支持度為 2/4 = 0.5 表示在 D 中的 4 條事務中，{1} 出現在其中的兩條事務中，以後幾個步驟的支持度計算方式也是類似的。假定給定的最小支持度為 0.5，那麼最後我們可以得到一個包含 3 個項的頻繁項集 {2 3 5}。

另外，從圖中我們可以看到 itemset 中所包含的 item 是從 1 增長到 3 的。並且每次增長都是利用上一個 itemset 中滿足支持度的 item 來生成的，這個過程稱之為候選集生成（candidate generation）。譬如說 C2 里就不包含 C1 中的 4 。

2、利用最小置信度從頻繁項集中找到關聯規則。

同樣假定最小的置信度為 0.5 ，從頻繁項集 {2 3 5} 中我們可以發現規則 {2 3} ? {5} 的置信度為 1 > 0.5 ，所以我們可以說 {2 3} ? {5} 是一個可能感興趣的規則。

從第一步中我們看出每次計算支持度都需要掃描資料庫，這會造成很大的 I/O 開銷，所以有很多變種的演算法都會在該問題上進行優化（FP-Growth）。此外如何有效的生成候選集也是很多變種演算法優化的問題之一(Apriori-all)。

總結

1、關聯規則是無監督的學習演算法，能夠很好的用於知識的發現。

2、缺點是很難嚴重演算法的有效性，一般只能夠通過肉眼觀察結果是否合理。

參考資料

1、Association Rule Learning

2、Data mining: Concepts and Technique

3、Fast Algorithm For Mining Association Rule (Apriori-all 演算法)

4、Mining frequent patterns without candidate generation: a frequent-pattern tree approach (FP-Growth演算法)

歡迎關注我們微信公眾號：人工智慧LeadAI，ID：atleadai

推薦閱讀：