（通俗易懂）關聯規則演算法及FP-growth的使用和原始碼解析

摘要： 原創文章，轉載請表明出處 今天將前段時間學的部分知識做一個總結，之前公司有一個業務為同緯度下，挖掘各個項之間有什麼潛在的關係。經過一頓思考，我發現這個需求很像一個案例，那就是啤酒和紙尿褲。又經過一頓Google，百度。哦！原來完成這個需求的演算法統稱關聯規則，我們下面就先簡單的介紹一下...

原創文章，轉載請表明出處

今天將前段時間學的部分知識做一個總結，之前公司有一個業務為同緯度下，挖掘各個項之間有什麼潛在的關係。經過一頓思考，我發現這個需求很像一個案例，那就是啤酒和紙尿褲。又經過一頓Google，百度。哦！原來完成這個需求的演算法統稱關聯規則，我們下面就先簡單的介紹一下何為關聯規則。

關聯規則：從大規模資料集中，尋找各個項的隱含關係被稱作關聯分析或者關聯規則學習。

再往通俗易懂了說，就是從大規模資料中，我們去找哪些項總是同時出現，頻繁出現。

那頻繁的定義是什麼呢？怎樣才算頻繁呢？度量他們的方法有很多種，這裡我們來簡單介紹一下支援度和置信度，下圖是王者榮耀商店每個顧客買的商品公仔（圖畫的有點糙，哈哈）。

支援度 ：資料集中該項集的記錄數量所佔的比例，例如上圖中，{貂蟬公仔}的支援度為4/10,{貂蟬公仔，呂布公仔}的支援度為2/10。

置信度 ：針對一條如{呂布公仔}-->{貂蟬公仔}這樣的關聯規則來定義的，這條規則的置信度被定義為：支援度({呂布公仔, 貂蟬公仔})/支援度({呂布公仔})。再通俗易懂的講就是使用者買呂布公仔的前提下，有多大機率買貂蟬公仔。從圖中可以看出，支援度({呂布公仔, 貂蟬公仔})=2/10，支援度({呂布公仔})=2/10。所以{呂布公仔}-->{貂蟬公仔}的置信度=2/10/2/10=1。也就是說使用者買了呂布公仔，肯定會買貂蟬公仔。

以上就是對關聯規則本質上的一個介紹。下面我們再從實現上說一下典型的關聯規則演算法Aprioir。還是根據上面那張圖描述一下Aprioir的邏輯步驟。

1.自己規定一個支援度閾值為：0.2，用來過濾不頻繁項集。

2.掃描事物集，尋找1項頻繁集並過濾，如下圖：

3，再次掃描事務集，尋找2項頻繁集再過濾：如下圖：

4，以此類推，推到沒有頻繁項集為止。（我們這裡上圖的資料集也就到2項頻繁集就沒有了）

5，發現關聯規則：以上四步把各個頻繁集的支援度都已經得出，置信度上文也提及過了，這樣就可以得出關聯規則了。

從上述演算法步驟中可以看出，Aprior演算法每輪迭代都要掃描資料集，因此在資料集很大，資料種類很多的時候，演算法效率很低。經過多方瞭解，我又找到了FP-growth演算法。

FP-growth

FP-growth演算法不同於Apriori演算法生成頻繁項集再檢查是否頻繁，不斷掃描事物集。而是使用一種稱為頻繁模式樹（FP-Tree，PF代表頻繁模式，Frequent Pattern）選單緊湊資料結構組織資料，並直接從該結構中提取頻繁項集，不需要產生候選集。每個事務被對映到FP-tree的一條路徑上，不同的事務會有相同的路徑，因此重疊的越多，壓縮效果越好。

FP-growth分為兩大步，一是構建頻繁模式樹，二是從頻繁模式樹中挖掘各個頻繁項集。下面從邏輯上說一下。由於上組資料集有點不滿足現在這個需求，我們換一組資料集。現有如下資料集：

FP-growth演算法需要對原始訓練集掃描兩遍以構建FP樹。第一次掃描，過濾掉所有不滿足最小支援度的項；對於滿足最小支援度的項，按照全域性最小支援度排序，在此基礎上，為了處理方便，也可以按照項的關鍵字再次排序。

第二次掃描，構造FP樹。參與掃描的是過濾後的資料，如果某個資料項是第一次遇到，則建立該節點，並在headTable中新增一個指向該節點的指標；否則按路徑找到該項對應的節點，修改節點資訊。具體過程如下所示：

從上面可以看出，headTable並不是隨著FPTree一起建立，而是在第一次掃描時就已經建立完畢，在建立FPTree時只需要將指標指向相應節點即可。從事務004開始，需要建立節點間的連線，使不同路徑上的相同項連線成連結串列。

下面我們結合spark中的原始碼講一下（只講和演算法相關的部分，講個大概，細節還得自己去看）。

上圖是FP-growth的入口函式，val count = data.count()，得出事物集的總條數。

val minCount = math.ceil(minSupport * count).toLong，根據設定的最小支援度得出最小條數。

val freqItems = genFreqItems(data, minCount, partitioner)，得到1項頻繁集並過濾按照次數排序（在這篇文章裡叫這個順序叫全域性順序）。這是該演算法第一次掃描事物集。

val freqItemsets = genFreqItemsets(data, minCount, freqItems, partitioner)，構建樹，並挖掘樹，得到頻繁項集。這個方法很重要，我們下面跟一下這個方法。

val itemToRank = freqItems.zipWithIndex.toMap，將每條事物加上索引。後續處理每個項拿索引替代。

genCondTransactions(transaction, itemToRank, partitioner)，將事務集的每行按照上面提到的全集順序排好。

(tree, transaction) => tree.add(transaction, 1L),(tree1, tree2) => tree1.merge(tree2))，每個分組內各構建一顆樹。

tree.extract(minCount, x => partitioner.getPartition(x) == part)，對每顆樹進行遞迴挖掘出頻繁項集。

至此，完畢！

以上所述如有不妥，懇請大家指正。

(如果對您有所幫助話，那就點個贊點個關注吧，嘻嘻~~)

安利一個特別熱心的程式設計樂園群：624108656