1、FPGrowth 算法1.1.1基本概念關聯規則挖掘的一個典型例子是購物籃分析。關聯規則研究有助于發現交易數據庫中不 同商品（項）之間的聯系，找出顧客購買行為模式，如購買了某一商品對購買其他商品的影 響，分析結果可以應用于商品貨架布局、貨存安排以及根據購買模式對用戶進行分類。關聯規則的相關術語如下：（1）項與項集這是一個集合的概念，在一籃子商品中的一件消費品即為一項（Item），則若干項的集 合為項集，如啤酒，尿布構成一個二元項集。（2）關聯規則一般記為的形式，X為先決條件，Y為相應的關聯結果，用于表示數據內隱含的關聯性。 如：表示購買了尿布的消費者往往也會購買啤酒。關聯性強度如何，由三個概念

2、一一支持度、 置信度、提升度來控制和評價。例：有10000個消費者購買了商品，其中購買尿布1000個，購買啤酒2000個，購買面包 500個，同時購買尿布和面包800個，同時購買尿布和面包100個。（3）支持度（Support）支持度是指在所有項集中X, Y出現的可能性，即項集中同時含有X和Y的概率。該指 標作為建立強關聯規則的第一個門檻，衡量了所考察關聯規則在“量”上的多少。通過設定最 小閾值（minsup），剔除出鏡率”較低的無意義規則，保留出現較為頻繁的項集所隱含的規 則。設定最小閾值為5%，由于尿布，啤酒的支持度為800/10000=8%，滿足基本輸了要求， 成為頻繁項集，保留規則；而

3、尿布，面包的支持度為100/10000=1%，被剔除。（4）置信度（Confidence）置信度表示在先決條件X發生的條件下，關聯結果Y發生的概率。這是生成強關聯規則 的第二個門檻，衡量了所考察的關聯規則在質”上的可靠性。相似的，我們需要對置信度設 定最小閾值（mincon）來實現進一步篩選。具體的，當設定置信度的最小閾值為70%時，置 信度為800/1000=80%，而的置信度為800/2000=40%，被剔除。（5）提升度（lift）提升度表示在含有X的條件下同時含有Y的可能性與沒有X這個條件下項集中含有Y 的可能性之比：公式為 confidence（artichok = cracker）

4、/support（cracker） = 80%/50% = 1.6。該 指標與置信度同樣衡量規則的可靠性，可以看作是置信度的一種互補指標。FP-Growth 算法FP-Growth（頻繁模式增長）算法是韓家煒老師在2000年提出的關聯分析算法，它采取如 下分治策略：將提供頻繁項集的數據庫壓縮到一棵頻繁模式樹（FP-Tree），但仍保留項集關 聯信息；該算法和Apriori算法最大的不同有兩點：第一，不產生候選集；第二，只需要兩 次遍歷數據庫，大大提高了效率。（1）按以下步驟構造FP-樹（a）掃描事務數據庫D 一次。收集頻繁項的集合F和它們的支持度。對F按支持度降序排序， 結果為頻繁項表L。(b

5、)創建FP-樹的根結點，以“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(F, N)。(2)FP-樹的挖掘通過調用FP_growth(FP_tr

6、ee, null)實現。該過程實現如下：FP_growth(Tree, a)(1) if Tree含單個路徑P thenfor路徑P中結點的每個組合(記作6) 產生模式6 Ua，其支持度support = 6中結點的最小支持度；else for each ai在Tree的頭部(按照支持度由低到高順序進行掃描) 產生一個模式6 = aiUa，其支持度support = ai .support；構造6的條件模式基，然后構造6的條件FP-樹Tree6；if Tree6 壬 then調用 FP_growth (Tree6, 6)； endFP-Growth算法演示一構造FP-樹(1)事務數據庫建立原始

7、事務數據庫如下：TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3掃描事務數據庫得到頻繁1-項目集F。I1I2I3I4I567622定義minsup=20%，即取小支持度為2，重新排列F。I2I1I3I4I576622重新調整事務數據庫。Tid1I2, I1,I52I2,I43I2,I34I2, I1,I45I1,I36I2,I37I1,I38I2, I1,I3,I59I2, I1,I3ItemsNull(2)創建根結點和頻繁項目表Item-nameNode-head12NullIINull

8、13Null14Null15Null(3)加入第一個事務(I2,I1,I5)(4)加入第二個事務(I2,I4)(5)加入第三個事務(I2,I3)以此類推加入第5、6、7、8、9個事務。(6)加入第九個事務(I2,I1,I3)FP-Growth算法演示FP-樹挖掘FP-樹建好后，就可以進行頻繁項集的挖掘，挖掘算法稱為FpGrowth (Frequent Pattern Growth)算法，挖掘從表頭header的最后一個項開始，以此類推。本文以15、I3為例進行 挖掘。(1)挖掘15：對于 15，得到條件模式基：(I2,I1:1)、I2,I1,I3:1構造條件FP-tree：得到 I5 頻繁項集

9、：I2,I5:2,I1,I5:2,I2,I1,I5:2I4、I1的挖掘與I5類似，條件FP-樹都是單路徑。(1)挖掘I3：I5的情況是比較簡單的，因為I5對應的條件FP-樹是單路徑的，I3稍微復雜一點。I3的條件模式基是(I2 I1:2), (I2:2), (I1:2)，生成的條件FP-樹如下圖：I3的條件FP-樹仍然是一個多路徑樹，首先把模式后綴I3和條件FP-樹中的項頭表中的每項取并集，得到一組模式I2 I3:4, I1 I3:4，但是這一組模式不是后綴為I3的所有模式。還需要遞歸調用FP-growth，模式后綴為I1，I3，I1，I3的條件模式基為I2： 2，其生成的條件FP-樹如下圖所

10、示。Item-nameNode-head12在FP_growth中把I2和模式后綴I1，I3取并得到模式I1 I2 I3： 2。理論上還應該計算一下模式后綴為I2, I3的模式集，但是I2, I3的條件模式基為空，遞歸 調用結束。最終模式后綴I3的支持度2的所有模式為： I2 I3:4, I1 I3:4, I1 I2 I3:2。Spark MllibFPGrowth 源碼分析FPGrowth 源碼包括：FPGrowth、FPTree 兩部分。其中 FPGrowth 中包括：run 方法、genFreqItems 方法、genFreqItemsets 方法、genCondTransactions

11、 方法；FPTree 中包括：add 方法、merge 方法、project 方法、getTransactions方法、extract 方法。/ run計算頻繁項集/*Computes an FP-Growth model that contains frequent itemsets.param data input data set, each element contains a transactionreturn an FPGrowthModel*/def runItem: ClassTag(data: RDDArrayItem): FPGrowthModelItem = if (da

12、ta.getStorageLevel = StorageLevel.NONE) logWarning(Input data is not cached.)val count = data.count()/計算事務總數valminCount = math.ceil(minSupport * count).toLong/計算最小支持度valnumParts = if (numPartitions 0) numPartitions else data.partitions.lengthvalpartitioner = new HashPartitioner(numParts)/freqItems計算

13、滿足最小支持度的Items項valfreqItems = genFreqItems(data, minCount, partitioner)/freqItemsets計算頻繁項集valfreqItemsets = genFreqItemsets(data, minCount, freqItems, partitioner)newFPGrowthModel(freqItemsets)/ genFreqItems計算滿足最小支持度的Items項/*Generates frequent items by filtering the input data using minimal support l

14、evel.paramminCount minimum count for frequent itemsetsparampartitionerpartitioner used to distribute itemsreturn array of frequent pattern ordered by their frequencies*/ privatedefgenFreqItemsItem: ClassTag( data: RDDArrayItem, minCount: Long, partitioner: Partitioner): ArrayItem = data.flatMap t =v

15、aluniq = t.toSetif (t.size != uniq.size) (thrownewSparkException(sItems in a transaction must be unique but got $t.toSeq.) t.map(v = (v, 1L).reduceByKey(partitioner, _ + _).filter(_._2 = minCount).collect().sortBy(-_._2).map(_._1)統計每個Items項的頻次，對小于minCount的Items項過濾，返回Items項。/ genFreqItemsets 計算頻繁項集：生

16、成 FP-Trees，挖掘 FP-Trees/*Generate frequent itemsets by building FP-Trees, the extraction is done on each partition.param data transactionsparamminCount minimum count for frequent itemsetsparamfreqItems frequent itemsparampartitionerpartitioner used to distribute transactionsreturn an RDD of (frequent

17、 itemset, count)*/ privatedefgenFreqItemsetsItem: ClassTag(data: RDDArrayItem,minCount: Long,freqItems: ArrayItem,partitioner: Partitioner): RDDFreqItemsetItem = valitemToRank = freqItems.zipWithIndex.toMap/表頭data.flatMap transaction =genCondTransactions(transaction, itemToRank, partitioner).aggrega

18、teByKey(new FPTreeInt, partitioner.numPartitions)( /生成 FP 樹 (tree, transaction) =tree.add(transaction, 1L), /FP 樹增加一條事務 (tree1, tree2) = tree1.merge(tree2) /FP 樹合并.flatMap case (part, tree)=tree.extract(minCount, x =partitioner.getPartition(x) = part)/FP 樹挖掘頻繁項 .map case (ranks, count) =newFreqItems

19、et(ranks.map(i =freqItems(i).toArray, count)/ add FP-Trees增加一條事務數據 /* Adds a transaction with count. */ def add(t: IterableT, count: Long = 1L): this.type = require(count 0) varcurr = rootcurr.count += countt.foreach item =val summary = summaries.getOrElseUpdate(item, new Summary) summary.count += c

20、ountval child = curr.children.getOrElseUpdate(item, valnewNode = new Node(curr) newNode.item = itemsummary.nodes += newNode newNode)child.count += countcurr = childthis/ merge FP-Trees 合并/* Merges another FP-Tree. */def merge(other: FPTreeT): this.type = other.transactions.foreach case (t, c)= add(t, c)this/ extract FP-Trees挖掘，返回所有頻繁項集/* Extracts all patterns with valid suffix and minimum count. */ def extract(minCount: Long, validateSuffix: T = Boolean = _ = true): Iterator(ListT, Long) = summaries.iterator.flatMap case (item, summary)=if (validateSuffix(item) &s