文章來源：加米谷大數據

本節主要描述了基于 Apriori 算法的關聯分析方法。為了克服 Apriori 算法在複雜度和效率方面的缺陷，本節還進一步的介紹了基于 FP-Tree 的頻繁模式挖掘方法。

Apriori關聯分析算法

Apriori 算法是挖掘産生關聯規則所需頻繁項集的基本算法，也是最著名的關聯分析算法之一。

1. Apriori 算法

Apriori 算法使用了逐層搜索的疊代方法，即用 k-項集探索（k 1）-項集。為提高按層次搜索并産生相應頻繁項集的處理效率，Apriori 算法利用了一個重要性質，該性質還能有效縮小頻繁項集的搜索空間。Apriori 性質：一個頻繁項集的所有非空子集也必須是頻繁項集。即假如項集 A 不滿足最小支持度阈值，即 A 不是頻繁的，則如果将項集 B 添加到項集 A 中，那麼新項集（AUB）也不可能是頻繁的。Apriori 算法簡單來說主要有以下幾個步驟。1）通過單遍掃描數據集，确定每個項的支持度。一旦完成這一步，就可得到所有頻繁 1-項集的集合 F1。2）使用上一次疊代發現的頻繁（k-1）-項集，産生新的候選k-項集。3）為了對候選項集的支持度計數，再次掃描一遍數據庫，使用子集函數确定包含在每一個交易 t 中的所有候選 k-項集。4）計算候選項集的支持度計數後，算法将删除支持度計數小于支持度阈值的所有候選項集。5）重複步驟（2）、（3）、（4），當沒有新的頻繁項集産生時，算法結束。Apriori 算法是個逐層算法，它使用“産生——測試”策略來發現頻繁項集。在由（k-1）-項集産生 k-項集的過程中“新産生的 k-項集先要确定它的所有的（k-1）-項真子集都是頻繁的，如果有一個不是頻繁的，那麼它可以從當前的候選項集中去掉。産生候選項集的方法有以下幾種。

1）蠻力法

從 2-項集開始以後所有的項集都是從 1-項集完全拼出來的。例如，3- 項集由 3 個 1-項集拼出，要列出所有的可能性。然後再按照剪枝算法剪枝，即确定當前的項集的所有（k-1）-項集是否都是頻繁的。

2） 法

由 1-項集和（k-1）-項集生成 k-項集，然後再剪枝。這種方法是完全的，因為每一個頻繁 k-項集都是由一個頻繁（k-1）-項集和一個頻繁 1-項集産生的。由于順序的關系，這種方法會産生大量重複的頻繁 k-項集。

3）法

由兩個頻繁（k-1 ）-項集生成候選 k-項集，但是兩個頻繁（k-1）-項集的前 k-2 項必須相同，最後一項必須相異。由于每個候選項集都是由一對頻繁（k-1）-項集合并而成的，所以需要附加的候選剪枝步驟來确保該候選的其餘 k-2 個子集是頻繁的。

2. 由頻繁項集産生關聯規則

一旦從事務數據集中找出頻繁項集，就可以直接由它們産生強關聯規則，即滿足最小支持度和最小置信度的規則。計算關聯規則的置信度并不需要再次掃描事物數據集，因為這兩個項集的支持度計數已經在頻繁項集産生時得到。假設有頻繁項集 Y，X 是 Y 的一個子集，那麼如果規則 X→Y→X 不滿足置信度阈值，則形如 X1→Y1→X1 的規則一定也不滿足置信度阈值，其中，X1 是 X 的子集。根據該性質，假設由頻繁項集 {a,b,c,d｝産生關聯規則，關聯規則｛b,c,d}→{a} 具有低置信度，則可以丢棄後件包含 a 的所有關聯規則，如{c,d}→{a,b}，{b,d}→{a,c} 等。

3. 算法優缺點

Apriori 算法作為經典的頻繁項集産生算法，使用先驗性質，大大提高了頻繁項集逐層産生的效率，它簡單易理解，數據集要求低。但是随着應用的深入，它的缺點也逐漸暴露出來，主要的性能瓶頸有以下兩點。

• 多次掃描事務數據集，需要很大的 I/O 負載。對每次 k 循環，對候選集 ck 中的每個元素都必須通過掃描數據集一次來驗證其是否加入 lk。
• 可能産生龐大的候選集。候選項集的數量是呈指數級增長的，如此龐大的候選項集對時間和空間都是一種挑戰。

FP-Tree關聯分析算法

2000 年，Han Jiawei 等人提出了基于頻繁模式樹（Frequent Pattern Tree, FP—Tree）的發現頻繁模式的算法 FP-Growth。其思想是構造一棵 FP-Tree，把數據集中的數據映射到樹上，再根據這棵 FP-Tree 找出所有頻繁項集。FP-Growth 算法是指，通過兩次掃描事務數據集，把每個事務所包含的頻繁項目按其支持度降序壓縮存儲到 FP-Tree 中。在以後發現頻繁模式的過程中，不需要再掃描事務數據集，而僅在 FP-Tree 中進行查找即可。通過遞歸調用 FP-Growth 的方法可直接産生頻繁模式，因此在整個發現過程中也不需産生候選模式。由于隻對數據集掃描兩次，因此 FP-Growth 算法克服了 Apriori 算法中存在的問題，在執行效率上也明顯好于 Apriori 算法。

1. FP—Tree 的構造

為了減少 I/O 次數，FP-Tree 算法引入了一些數據結構來臨時存儲數據。這個數據結構包括 3 部分：項頭表、FP-Tree 和結點鍊接，如圖 1 所示。

圖 1 FP-Tree數據結構

第一部分是一個項頭表，記錄了所有的頻繁 1-項集出現的次數，按照次數降序排列。例如, 在圖 1 中，A 在所有 10 組數據中出現了 8 次，因此排在第一位。第二部分是 FP-Tree，它将原始數據集映射到了內存中的一顆 FP-Tree。第三部分是結點鍊表。所有項頭表裡的頻繁 1—項集都是一個結點鍊表的頭，它依次指向 FP-Tree 中該頻繁 1-項集出現的位置。這樣做主要是方便項頭表和 FP-Tree 之間的聯系查找和更新。

1）項頭表的建立

建立 FP-Tree 需要首先建立項頭表。第一次掃描數據集，得到所有頻繁 1-項集的計數。然後删除支持度低于阈值的項，将頻繁 1—項集放入項頭表，并按照支持度降序排列。第二次掃描數據集，将讀到的原始數據剔除非頻繁 1-項集，并按照支持度降序排列。在這個例子中有 10 條數據，首先第一次掃描數據并對 1-項集計數，發現 F、O、I、L、J、P、M、N 都隻出現一次，支持度低于阈值(20%)，因此它們不會出現在項頭表中。将剩下的 A、C、E、G、B、D、F 按照支持度的大小降序排列，組成了項頭表。接着第二次，掃描數據，對每條數據剔除非頻繁 1—項集，并按照支持度降序排列。例如，數據項 A、B, C、E、F、O 中的 O 是非頻繁 1-項集，因此被剔除，隻剩下了 A、B、C、E、F。 按照支持度的順序排序，它變成了 A、C、E、B、F，其他的數據項以此類推。将原始數據集裡的頻繁 1-項集進行排序是為了在後面的 FP-Tree 的建立時，可以盡可能地共用祖先結點。經過兩次掃描，項頭集已經建立，排序後的數據集也已經得到了，如圖 2 所示。

圖 2 FP-Tree項頭表示意

2）FP-Tree 的建立

有了項頭表和排序後的數據集，就可以開始 FP-Tree 的建立了。開始時 FP-Tree 沒有數據，建立 FP-Tree 時要一條條地讀入排序後的數據集，并将其插入 FP-Tree。插入時，排序靠前的結點是祖先結點，而靠後的是子孫結點。如果有共用的祖先，則對應的公用祖先結點計數加 1。插入後，如果有新結點出現，則項頭表對應的結點會通過結點鍊表鍊接上新結點。直到所有的數據都插入到 FP-Tree 後，FP-Tree 的建立完成。下面來舉例描述 FP-Tree 的建立過程。首先，插入第一條數據 A、C、E、E、F，如圖 3 所示。此時 FP-Tree 沒有結點，因此 A、C、E、B、F 是一個獨立的路徑，所有結點的計數都為 1，項頭表通過結點鍊表鍊接上對應的新增結點。

圖 3 FP-Tree的構造示意1

接着插入數據 A、C、G，如圖 4 所示。由于 A、C、G 和現有的 FP-Tree 可以有共有的祖先結點序列 A、C，因此隻需要增加一個新結點 G，将新結點 G 的計數記為 1，同時 A 和 C 的計數加 1 成為 2。當然，對應的 G 結點的結點鍊表要更新。

圖 4 FP-Tree的構造示意2

用同樣的辦法可以更新後面 8 條數據，最後構成的 FP-Tree，如圖 1 所示。由于原理類似，就不再逐步描述。

2. FP-Tree 的挖掘

下面講解如何從 FP-Tree 挖掘頻繁項集。基于 FP-Tree、項頭表及結點鍊表，首先要從項頭表的底部項依次向上挖掘。對于項頭表對應于 FP-Tree 的每一項，要找到它的條件模式基。條件模式基是指以要挖掘的結點作為葉子結點所對應的 FP 子樹。得到這個 FP 子樹，将子樹中每個結點的計數設置為葉子結點的計數，并删除計數低于支持度的結點。基于這個條件模式基,就可以遞歸挖掘得到頻繁項集了。還是以上面的例子來進行講解。先從最底部的 F 結點開始，尋找 F 結點的條件模式基，由于 F 在 FP-Tree 中隻有一個結點，因此候選就隻有圖 5 左邊所示的一條路徑，對應 {A:8,C:8,E:6,B:2,F:2}。接着将所有的祖先結點計數設置為葉子結點的計數，即 FP 子樹變成 {A:2,C:2,E:2,B:2,F:2}。條件模式基可以不寫葉子結點，因此最終的 F 的條件模式基如圖 5 右邊所示。基于條件模式基，很容易得到 F 的頻繁 2-項集為 {A:2,F:2},{C:2,F:2},{E:2,F:2}, {B:2,F:2}。遞歸合并 2—項集，可得到頻繁 3—項集為{A:2,C:2,F:2}, {A:2,E:2,F:2}, {A:2,B:2,F:2}, {C:2,E:2, F:2}, {C:2,B2, F:2}, {E:2,B2, F:2}。遞歸合并 3-項集，可得到頻繁 4—項集為{A:2,C:2,E:2,F:2}，{A:2,C:2,B2,F:2}, {C:2,E:2,B2,F:2}。一直遞歸下去，得到最大的頻繁項集為頻繁 5-項集，為 {A:2,C:2,E:2,B2,F:2}。

圖 3 FP-Tree的挖掘示意1

F 結點挖掘完後，可以開始挖掘 D 結點。D 結點比 F 結點複雜一些，因為它有兩個葉子結點，因此首先得到的 FP 子樹如圖 5左邊所示。接着将所有的祖先結點計數設置為葉子結點的計數，即變成 {A:2,C:2,E:1 G:1,D:1,D:1}。此時，E 結點和 G 結點由于在條件模式基裡面的支持度低于阈值，所以被删除，最終，去除了低支持度結點和葉子結點後的 D 結點的條件模式基為 {A:2,C:2}。通過它，可以很容易得到 D 結點的頻繁 2-項集為 {A:2,D:2}，{C:2,D:2}。遞歸合并 2-項集，可得到頻繁 3-項集為 {A:2,C:2,D:2}。D 結點對應的最大的頻繁項集為頻繁 3_項集。用同樣的方法可以遞歸挖掘到 B 的最大頻繁項集為頻繁 4-項集 {A:2,C:2,E:2,B2}。繼續挖掘，可以遞歸挖掘到 G 的最大頻繁項集為頻繁 4-項集 {A:5,C:5,E:4,G:4}，E 的最大頻繁項集為頻繁 3-項集 {A:6,C:6,E:6},C 的最大頻繁項集為頻繁 2-項集{A:8,C:8}。由于 A 的條件模式基為空，因此可以不用去挖掘了。

圖 4 FP-Tree的挖掘示意2

至此得到了所有的頻繁項集，如果隻是要最大的頻繁 k-項集，則從上面的分析可以看到，最大的頻繁項集為 5-項集，包括｛A:2,C:2,E:2,B:2,F:2｝。

3. MLlib 的 FP-Growth 算法實例

Spark MLlib 中 FP-Growth 算法的實現類 FPGrowth 具有以下參數。

class FPGrowth private ( private var minSupport: Double, private var numPartitions: Int) extends Logging with Serializable

變量的含義如下。

• minSupport 為頻繁項集的支持度阈值，默認值為0.3。
• numPartitions 為數據的分區個數，也就是并發計算的個數。

首先，通過調用 FPGrowth.run 方法構建 FP-Growth 樹，樹中将會存儲頻繁項集的數據信息，該方法會返回 FPGrowthModel；然後，調用 FPGrowthModel.generateAssociationRules 方法生成置信度高于阈值的關聯規則，以及每個關聯規則的置信度。實例：導入訓練數據集，使用 FP-Growth 算法挖掘出關聯規則。該實例使用的數據存放在 fpg.data 文檔中，提供了 6 個交易樣本數據集。樣本數據如下所示。

r z h k p z y x w v u t s s x o n r x z y m t s q e z x z y r q t p

數據文件的每一行是一個交易記錄，包括了該次交易的所有物品代碼，每個字母表示一個物品，字母之間用空格分隔。實現的代碼如下所示。

import org.apache.spark.mllib.fpm.FPGrowth import org.apache.spark.{SparkConf,SparkContext} object FP_GrowthTest { def main(args:Array[String]){ val conf = new SparkConf().setAppName("FPGrowthTest").setMaster("local[4]") val sc = new SparkContext(conf) //設置參數 val minSupport = 0.2 //最小支持度 val minConfidence = 0.8 //最小置信度 val numPartitions = 2 //數據分區數 //取出數據 val data = sc.textFile("data/mllib/fpg.data") //把數據通過空格分割 val transactions = data.map (x=>x.split ("")) transactions.cache() //創建一個 FPGrowth 的算法實列 val fpg = new FPGrowth() fpg.setMinSupport(minSupport) fpg.setNumPartitions(numPartitions) //使用樣本數據建立模型 val model = fpg.run(transactions) //查看所有的頻繁項集，并且列出它出現的次數 model.freqItemsets.collect().foreach(itemset=>{ printIn (itemset.items.mkString("[",",","]") itemset.freq) }) //通過置信度篩選出推薦規則 //antecedent 表示前項，consequent 表示後項 //confidence 表示規則的置信度 model.generateAssociationRules(minConfidence).collect().foreach(rule=>{printIn(rule.antecedent.mkString(",") "-->" rule.consequent.mkString("") "-->" rule.confidence) }) //查看規則生成的數量 printIn(model.generateAssociationRules (minConfidence).collect().length)

運行結果會打印頻繁項集和關聯規則。部分頻繁項集如下。

[t] , 3 [t, x] ,3 [t, x, z] , 3 [t, z] , 3 [s] , 3 [s, t] , 2 [s, t, x] , 2 [s, t, x, z] , 2 [s, t, z], 2 [s, x] , 2 [s, x, z] , 2

部分關聯規則如下。

s, t, x --> z --> 1.0 s, t, x --> y --> 1.0 q, x --> t --> 1.0 q, x --> y --> 1.0 q, x --> z --> 1.0 q, y, z --> t --> 1.0 q, y, z --> x --> 1.0 t, x, z --> y --> 1.0 q, x, z --> t --> 1.0 q, x, z --> y --> 1.0

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!