1、精選優質文檔-傾情為你奉上1.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 => cr

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

5、項表L。(b) 創建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(P, N)。（2）FP-樹的挖掘通過調用FP_gro

6、wth(FP_tree, null)實現。該過程實現如下：FP_growth(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；(7) if Tree then(8) 調用 FP_growth (Tree, )；end1.1.3 FP-

7、Growth算法演示構造FP-樹（1）事務數據庫建立原始事務數據庫如下：TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3掃描事務數據庫得到頻繁1-項目集F。I1I2I3I4I567622定義minsup=20%，即最小支持度為2，重新排列F。I2I1I3I4I576622重新調整事務數據庫。TidItems1I2, I1,I52I2,I43I2,I34I2, I1,I45I1,I36I2,I37I1,I38I2, I1,I3,I59I2, I1,I3（2）創建根結點和頻繁項目表（3）加入第

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

9、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-樹如下圖所示。在FP_g

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

11、ject方法、getTransactions方法、extract方法。/ run 計算頻繁項集 /* * Computes an FP-Growth model that contains frequent itemsets. * param data input data set, each element contains a transaction * return an FPGrowthModel */ def runItem: ClassTag(data: RDDArrayItem): FPGrowthModelItem = if (data.getStorageLevel = St

12、orageLevel.NONE) logWarning("Input data is not cached.") val count = data.count()/計算事務總數 val minCount = math.ceil(minSupport * count).toLong/計算最小支持度 val numParts = if (numPartitions > 0) numPartitions else data.partitions.lengthval partitioner = new HashPartitioner(numParts)/freqItems計算

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

14、upport level. * param minCount minimum count for frequent itemsets * param partitioner partitioner used to distribute items * return array of frequent pattern ordered by their frequencies */ privatedef genFreqItemsItem: ClassTag( data: RDDArrayItem, minCount: Long, partitioner: Partitioner): ArrayIt

15、em = data.flatMap t => val uniq = t.toSet if (t.size != uniq.size) thrownew SparkException(s"Items 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項的頻次，

16、對小于minCount的Items項過濾，返回Items項。/ genFreqItemsets計算頻繁項集：生成FP-Trees，挖掘FP-Trees/* * Generate frequent itemsets by building FP-Trees, the extraction is done on each partition. * param data transactions * param minCount minimum count for frequent itemsets * param freqItems frequent items * param partition

17、er partitioner used to distribute transactions * return an RDD of (frequent itemset, count) */ privatedef genFreqItemsetsItem: ClassTag( data: RDDArrayItem, minCount: Long, freqItems: ArrayItem, partitioner: Partitioner): RDDFreqItemsetItem = val itemToRank = freqItems.zipWithIndex.toMap/表頭 data.fla

18、tMap transaction => genCondTransactions(transaction, itemToRank, partitioner) .aggregateByKey(new FPTreeInt, partitioner.numPartitions)( /生成FP樹 (tree, transaction) => tree.add(transaction, 1L), /FP樹增加一條事務 (tree1, tree2) => tree1.merge(tree2) /FP樹合并 .flatMap case (part, tree) => tree.extr

19、act(minCount, x => partitioner.getPartition(x) = part)/FP樹挖掘頻繁項 .map case (ranks, count) => new FreqItemset(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) var c

20、urr = root curr.count += count t.foreach item => val summary = summaries.getOrElseUpdate(item, new Summary) summary.count += count val child = curr.children.getOrElseUpdate(item, val newNode = new Node(curr) newNode.item = item summary.nodes += newNode newNode ) child.count += count curr = child

21、this/ 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) && summary.count >= minCount) Iterator.single(item : Nil, summary.count) + project(item).extract(minCount).