數據挖掘演算法揭秘篇——關聯規則方法
"首席"工程師
小昶
關聯規則方法
關聯規則挖掘的目標是發現數據項集之間的關聯關係或相關關係，是數據挖掘中的一個重要的課題。
關聯規則挖掘的一個典型例子是購物籃分析，關聯規則挖掘有助於發現交易資料庫中不同商品項之間的關係，找出顧客購買行為模式，如購買了某一商品對購物對其他商品的影響。分析結果可以應用於商品貨架布局、貨存安排以及根據購買模式對用戶進行分類。
先簡單介紹一下關聯規則挖掘中涉及的幾個基本概念：
定義1：項與項集
資料庫中不可分割的最小單位信息，稱為項目，用符號i表示。項的集合稱為項集。設集合I=是項集，I中項目的個數為k，則集合I稱為k-項集。
定義2：事務
設I=是由資料庫中所有項目構成的集合，一次處理所含項目的集合用T表示，T=。每一個包含ti子項的項集都是I子集。
定義3：項集的頻數（支持度計數）
包括項集的事務數稱為項集的頻數（支持度計數）。
定義4：關聯規則
關聯規則是形如X=>Y的蘊含式，其中X、Y分別是I的真子集，並且X∩Y=?。X稱為規則的前提，Y稱為規則的結果。關聯規則反映X中的項目出現時，Y中的項目也跟著出現的規律。
定義5：關聯規則的支持度（Support）
關聯規則的支持度是交易集中同時包含的X和Y的交易數與所有交易數之比，記為support(X=>Y)，即support(X=>Y)=supportX∪Y=P(XY)。支持度反映了X和Y中所含的項在事務集中同時出現的概率。
定義6：關聯規則的置信度（Confidence）
關聯規則的置信度是交易集中包含X和Y的交易數與所有包含X的交易數之比，記為confidence(X=>Y)，即：confidence(X=>Y)==P(Y|X)。置信度反映了包含X的事務中，出現Y的條件概率。
定義7：最小支持度與最小置信度
通常用戶為了達到一定的要求，需要指定規則必須滿足的支持度和置信度閾限，當support(X=>Y)、confidence(X=>Y)分別大於等於各自的閾限值時，認為X=>Y是有趣的，此兩個值稱為最小支持閾值(min_sup)和最小置信閾值(min_conf)。其中，min_sup描述了關聯規則的最低重要程度，min_conf規定了關聯規則必須滿足的最低可靠性。
定義8：頻繁項集
設U=為項目的集合，且UI，U≠?，對於給定的最小支持度min_sup，如果項集U的支持度support(U)≧min_sup，則稱U為頻繁項集，否則，U為非頻繁項集。
定義9：強關聯規則
support(X=>Y)≧min_sup且confidence(X=>Y)≧min_conf，稱關聯規則X=>Y為強關聯規則，否則為若關聯規則。
關聯規則挖掘演算法是關聯規則挖掘研究的主要內容，迄今為止已提出了許多高效的關聯規則挖掘演算法。最著名的關聯規則發現方法是R.Agrawal提出的Apriori演算法。Apriori演算法主要包含兩個步驟：第一步是找出事務資料庫中所有大於等於用戶指定的最小支持度的數據項集；第二步是利用頻繁項集生成所需要的關聯規則，根據用戶設定的最小置信度進行取捨，最後得到強關聯規則。識別或發現所有頻繁項目集是關聯規則發現演算法的核心。
另一個比較著名的演算法是J.Han等提出的FP-tree。該方法採用分治的策略，在經過第一遍掃描之後，把資料庫中的頻集壓縮進一棵頻繁模式樹(FP-tree)，同時依然保留其中的關聯信息，隨後再將FP-tree分化成一些條件庫，每個庫和一個長度為1 的頻集相關然後再對這些條件庫分別進行挖掘。當原始數據量很大時，也可以結合劃分的方法，使得一個FP-tree可以放入主存中。實驗表明FP-Growth對不同長度的規則都有很好的適應性，同時在效率上較之Apriori演算法有巨大的提高。
下面對這兩個演算法進行介紹：
Apriori演算法
Apriori演算法核心思想中有兩個關鍵步驟——連接步和剪枝步。連接步：為找出Lk(頻繁k項集)，通過Lk-1與自身連接，產生候選k項集，該候選項集記作Ck；其中Lk-1的元素是可連接的。剪枝步：Ck是Lk的超集，即它的成員可以是也可以不是頻繁的，但所有的頻繁項集都包含在Ck中。掃描資料庫確定Ck中每一個候選的計數，從而確定Lk(計數值不小於最小支持度計數的所有候選是頻繁的，從而屬於Lk)。然而，Ck可能很大，這樣所設計的計算量就很大。為壓縮Ck，使用Apriori性質：任何非頻繁的(k-1)項集都不可能是頻繁k項集的子集。因此，如果一個候選k項集的(k-1)項集不在Lk中，則該候選項也不可能是頻繁的，從而可以由Ck中刪除。這種子集測試可以使用所有頻繁項集的散列樹快速完成。
Apriori演算法的主要步驟如下：
1. 掃描全部數據，產生候選集1-項集的集合C1；
2. 根據最小支持度，由候選1-項集的集合C1產生頻繁項集1-項集的集合L1；
3. 對k>1，重複執行步驟4、5、6；
4. 由Lk執行連接和剪枝操作，產生候選(k+1)-項集的集合Ck+1；
5. 根據最小支持度，由候選(k+1)-項集的集合Ck+1，產生頻繁項集(k+1)-項集的集合Lk+1；
6. 若L≠?，則k=k+1，跳往步驟4；否則跳往步驟7；
7. 根據最小置信度，由頻繁項集產生強關聯規則，結束。
給個簡單的例子作說明吧。
下面這個表格是代表一個事務資料庫D，其中最小支持度為50%，最小置信度??為70%，求事務資料庫中的頻繁關聯規則。
Apriori演算法的步驟如下所示:??
(1)生成候選頻繁1-項目集C1={，，，，}。
(2)掃描事務資料庫D，計算C1中每個項目集在D中的支持度。從事務資料庫D中可以得出每個項目集的支持數分別為3,3,3,1,2，事務資料庫D的項目集總數為4，因此可得出C1中每個項目集的支持度分別為75%，75%，75%，25%，50%。根據最小支持度為50%，可以得出頻繁1-項目集L1={，，，}。
(3)根據L1生成候選頻繁2-項目集C2={，，，，，}。
(4)掃描事務資料庫D，計算C2中每個項目集在D中的支持度。從事務資料庫D中可以得出每個項目集的支持數分別為3,2,1,2,1,2，事務資料庫D的項目集總數為4，因此可得出C2中每個項目集的支持度分別為75%，50%，25%，50%，25%，50%。根據最小支持度為50%，可以得出頻繁2-項目集L2={，，，}。
(5)根據L2生成候選頻繁3-項目集C3={，，，}，由於C3中項目集中的一個子集是L2中不存在的，因此可以去除。同理項目集、也可去除。因此C3=。
(6)掃描事務資料庫D，計算C3中每個項目集在D中的支持度。從事務資料庫D中可以得出每個項目集的支持數分別為2，事務資料庫D的項目集總數為4，因此可得出C2中每個項目集的支持度分別為50%。根據最小支持度為50%，可以得出頻繁3-項目集L3={}。
(7)L=L1UL2UL3={，，，，，，，，}。
(8)我們只考慮項目集長度大於1的項目集，例如，它的所有非真子集，，，，，，分別計算關聯規則—>，—>，—>，—>，—>，—>的置信度，其值分別為67%，67%，67%，67%，100%，100%。由於最小置信度為70%，可得}，—>，—>為頻繁關聯規則。也就是說買麵包和啤酒的同時肯定會買牛奶，買牛奶和啤酒的同時也是會買麵包。
Apriori演算法最大的優點是演算法思路比較簡單，它以遞歸統計為基礎，生成頻繁項集，易於實現。Apriori演算法作為經典的頻繁項目集生成演算法，在數據挖掘技術中佔有很重要的地位。但通過上面的分析發現，為了生成Ck，在連接步驟需要大量的比較，而且由連接生成的項集即使後來由Apriori性質確定了它不是候選項集，但在確定之前仍需對它生成子項集，並對子項集進行確定是否都在Lk-1中。這些步驟都浪費了大量的時間，如果可以保證由連接步生成的項集都是候選項集，那麼可以省掉不必要的連接比較和剪枝步驟。
FP-Growth演算法
FP-Growth(頻繁模式增長)演算法是韓家煒老師在2000年提出的關聯分析演算法，它採取將提供頻繁項集的資料庫壓縮到一棵頻繁模式樹但仍保留項集關聯信息的分治策略。這個演算法與Apriori演算法有兩個最大的不同：第一，不產生候選集；第二隻需要兩次遍歷資料庫，大大提高了效率。
演算法的具體描述如下：
輸入：事務資料庫D；最小支持閾值min_sup。
輸出：頻繁模式的完全集。
第一步：按下述步驟構造FP-Tree：
1. 掃描事務資料庫D一次。收集頻繁項的集合F和它們的支持度。對F按支持度降序排序，結果為頻繁項表L。
2. 創建FP-Tree的根節點，以」null」標記它。對於D中的每一個事務Trans，執行：選擇Trans中的頻繁項，並按L中的次序排序。設排序後的頻繁項表為[p|P]，其中，p是第一個元素，而P是剩餘元素的表。調用insert_tree([p|P], T)。該過程執行情況如下：如果T有子女N使得N.item-name = p.item-name，則N的計數加1；否則創建一個新結點N，將其計數設置為1，鏈接到它的父節點T，並且通過節點鏈將其鏈接到具有相同item-name的節點。如果P非空，遞歸調用insert_tree(P, N)。
第二步：根據FP-Tree挖掘頻繁項集，過程實現偽代碼如下：
1. if Tree含單個路徑P then
2. for 路徑P中節點的每個組合(記作β)
3. 產生模式β∪α，其支持度support=β中節點的最小支持度
4. else for each ai在Tree頭部 {
5. 產生一個模式β=ai∪α，其支持度support=ai.support
6. 構造β的條件模式基，然後構造β的條件FP-Tree Treeβ
7. If Treeβ≠? then
8. 調用FP-growth(Treeβ, β)}
FP-Growth演算法的優點：
1. 一個大資料庫能夠被有效的壓縮成比原資料庫小很多的高密度結構，避免了重複掃描的開銷；
2. 演算法基於FP-tree的挖掘採取模式增長的遞歸策略，創造性的提出了無候選項集的挖掘方法，在進行長頻繁項集的挖掘時效率較好；
3. 挖掘過程中採取了分治策略，將這種壓縮後的資料庫DB分成一組條件資料庫Dn，每個條件資料庫關聯一個頻繁項，並分別挖掘每一個條件資料庫。而這些條件資料庫Dn要遠遠小於資料庫DB。
FP-Growth演算法的缺點：
1. 演算法採取增長模式的遞歸策略，雖避免了候選項集的產生，但在挖掘過程中，如果大項集的數量很多，並且由於原資料庫得到的FP-Tree的分支很多，而且分支又很長時，該演算法需要構造出數量巨大的conditional FP-Tree，不僅費時而且需要大量空間，挖掘效率不高，而且採用遞歸演算法本身的效率也較低；
2. 由於海量的事務集合存放在大型資料庫中，經典的FP-Growth演算法在生成新的FP-tree時每次都要遍歷調減模式基兩次，導致系統需要反覆申請本地及資料庫資源查詢相同的海量資源，一方面降低了演算法效率，另一方面使得資料庫產生高負荷，不利於資料庫伺服器正常運作。
關於關聯規則方法就先介紹到這裡，如果想要了解更多內容，歡迎關注微信公眾號：落餅楓林，並與我們聯繫。
本文參閱了周英的《大數據挖掘系統方法與實例分析》，在此表示感謝！
本文由小昶提供，請勿未經作者本人許可用於商業行為，謝謝！
關注我們
TAG:落餅楓林 |