簡介

FP-Growth算法是韓嘉煒等人在2000年提出的關聯分析算法，它采取如下分治策略：將提供頻繁項集的數據庫壓縮到一棵頻繁模式樹(FP-tree)，但仍保留項集關聯信息。

在算法中使用了一種稱為頻繁模式樹(Frequent Pattern Tree)的數據結構。FP-tree是一種特殊的前綴樹，由頻繁項頭表和項前綴樹構成。FP-Growth算法基于以上的結構加快整個挖掘過程。

眾所周知，Apriori算法在產生頻繁模式完全集前需要對數據庫進行多次掃描，同時產生大量的候選頻繁集，這就使Apriori算法時間和空間復雜度較大。但是Apriori算法中有一個很重要的性質：頻繁項集的所有非空子集都必須也是頻繁的。但是Apriori算法在挖掘額長頻繁模式的時候性能往往低下，Jiawei Han提出了FP-Growth算法。

FP-Tree：將事務數據表中的各個事務數據項按照支持度排序后，把每個事務中的數據項按降序依次插入到一棵以 NULL為根結點的樹中，同時在每個結點處記錄該結點出現的支持度。

1、FPGrowth使用場景

FPGrowth關聯規則算法主要用于發現頻繁項集。如：沃爾瑪啤酒加尿布。

2、FPGrowth基本概念

FPGrowth算法通過構造一個FPTree樹結構來壓縮數據記錄，使得挖掘頻繁項集只需要掃描兩次數據記錄，而且該算法不需要生成候選集合，所以效率會比較高。

那么，如何從購物籃里面發現尿布+啤酒這樣的最佳組合呢？

我們以以下數據集為例，假設有如下的一張購物清單表，每條記錄代表一次購物記錄：

|TID|Items|

|-|-|

| T1 | { 面包 ， 牛奶 } |

| T2 | { 面包 , 尿布 , 啤酒 , 雞蛋 }|

| T3 | { 牛奶 , 尿布 , 啤酒 , 可樂 }|

| T4 | { 面包 , 牛奶 , 尿布 , 啤酒 }|

| T5 | { 面包 , 牛奶 , 尿布 , 可樂 }|

其中：

牛奶、面包叫做項；

{ 牛奶、面包}叫做項集；

項集出現的次數叫做支持度。

T* 表示用戶每次的購物清單。

3、算法思想

該算法的核心就是生成一棵FPTree。前面提到過，FPTree是一種樹結構。

構建的過程需要將表中的數據以及關系進行保存，我們先來看構建過程：

假設我們的最小支持度是3，這相當于是一個閾值。接下來我們開始按如下的步驟處理數據。

3.1、step1

掃描數據記錄，生成一級頻繁項集，并按出現次數由多到少排序，如下所示：

ItemCount

牛奶4

面包4

尿布4

啤酒3

可樂2(<3,刪除)

雞蛋1(<3,刪除)

可以看到，雞蛋和可樂在上表中要刪除，因為可樂只出現2次，雞蛋只出現1次，小于最小支持度，因此不是頻繁項集，非頻繁項集的超集一定不是頻繁項集，所以可樂和雞蛋不需要再考慮。

3.2、step2

再次掃描數據記錄，對每條記錄中出現在Step 1產生的表中的項，按表中的順序排序。初始時，新建一個根結點，標記為null。然后依次掃描每條記錄，構建FPTree。

1、第一條記錄：{面包，牛奶}需要根據Step1中結果轉換成：{牛奶,面包}，新建一個結點，name為{牛奶}，將其插入到根節點下，并設置count為1，然后新建一個{面包}結點，插入到{牛奶}結點下面，插入后如下所示：

2、第二條記錄：{面包,尿布,啤酒,雞蛋}，過濾并排序后為：{面包,尿布,啤酒}，發現根結點沒有包含{面包}的兒子(有一個{面包}孫子但不是兒子)，因此新建一個{面包}結點，插在根結點下面，這樣根結點就有了兩個孩子，隨后新建{尿布}結點插在{面包}結點下面，新建{啤酒}結點插在{尿布}下面，插入后如下所示：

3、第三條記錄：{牛奶,尿布,啤酒,可樂}，過濾并排序后為：{牛奶,尿布,啤酒}，這時候發現根結點有兒子{牛奶}，因此不需要新建結點，只需將原來的{牛奶}結點的count加1即可，往下發現{牛奶}結點有一個兒子{尿布}，于是新建{尿布}結點，并插入到{牛奶}結點下面，隨后新建{啤酒}結點插入到{尿布}結點后面。插入后如下圖所示：

4、第四條記錄：{面包,牛奶,尿布,啤酒}，過濾并排序后為：{牛奶，面包,尿布,啤酒}，這時候發現根結點有兒子{牛奶}，因此不需要新建結點，只需將原來的{牛奶}結點的count加1即可，往下發現{牛奶}結點有一個兒子{面包}，于是也不需要新建{面包}結點，只需將原來{面包}結點的count加1，由于這個{面包}結點沒有兒子，此時需新建{尿布}結點，插在{面包}結點下面，隨后新建{啤酒}結點，插在{尿布}結點下面，插入后如下圖所示：

5、按照1-4這樣的方式迭代所有的記錄，最終會生成一棵樹，即FPTree。按上表中生成的最終的FPTree如下圖所示：

樹中每個路徑代表一個項集，因為許多項集有公共項，而且出現次數越多的項越可能是公共項，因此按出現次數由多到少的順序排序可以節省空間，實現壓縮存儲。

另外我們需要一個表頭和對每一個name相同的結點做一個線索，方便后面使用，線索的構造也是在建樹過程形成的(下圖虛線)。

至此，整個FpTree就構造好了。

4、利用FPTree挖掘頻繁項集

FPTree建好后，就可以進行頻繁項集的挖掘，挖掘算法稱為FPGrowth(Frequent Pattern Growth)算法，挖掘從表頭header的最后一個項開始。

此處即從{啤酒}開始，根據{啤酒}的線索鏈找到所有{啤酒}結點，然后找出每個{啤酒}結點的分支：{牛奶，面包，尿布，啤酒：1}，{牛奶，尿布，啤酒:1}，{面包，尿布，啤酒:1}，其中的“1”表示出現1次。

注意，雖然{牛奶}出現4次，但{牛奶，面包，尿布，啤酒}只同時出現1次，因此分支的count是由后綴結點{啤酒}的count決定的，除去{啤酒}，我們得到對應的前綴路徑{牛奶，面包，尿布：1}，{牛奶，尿布:1}，{面包，尿布:1}，根據前綴路徑我們可以生成一棵條件FPTree，構造方式跟之前一樣，此處的數據記錄變為：

T1{牛奶，面包，尿布 ： 1}

T2{牛奶，尿布： 1}

T3{面包，尿布： 1}

絕對支持度依然是3，我們發現此時，牛奶的支持度為2、面包的支持度為2、尿布的支持度為3，由于我們的支持度為3，所以刪除牛奶和面包。按照相同的算法構造得到的FPTree為：

構造好條件樹后，對條件樹進行遞歸挖掘，當條件樹只有一條路徑時，路徑的所有組合即為條件頻繁集，假設{啤酒}的條件頻繁集為{S1,S2}，則{啤酒}的頻繁集為{S1+{啤酒},S2+{啤酒},S1+S2+{啤酒}}，即{啤酒}的頻繁集一定有相同的后綴{啤酒}，此處的條件頻繁集為：{{}，{尿布}}，于是{啤酒}的頻繁集為{{啤酒}{尿布，啤酒}}。

接下來找header表頭的倒數第二個項{尿布}的頻繁集，同上可以得到{尿布}的前綴路徑為：{面包：1}，{牛奶：1}，{牛奶，面包：2}，條件FPTree的數據集為：

T1{面包 ：1 }

T2{牛奶 ：1}

T3{牛奶，面包 ：2}

構造的條件FpTree為：

這顆條件樹路徑上的所有組合即為條件頻繁集：

{{}，{牛奶}，{面包}，{牛奶，面包}}

加上{尿布}后，又得到一組頻繁項集

{{尿布}，{牛奶，尿布}，{面包，尿布}，{牛奶，面包，尿布}}

同樣，這組頻繁項集一定包含一個相同的后綴：{尿布}，也就是我們一開始分析的對象，并且不包含{啤酒}，因此這一組頻繁項集與上一組不會重復。

重復以上步驟，對header表頭的每個項進行挖掘，即可得到整個頻繁項集，頻繁項集即不重復也不遺漏。

最終，我們可以得到多個集合列表，每一個集合代表一個頻繁項集。

總結下來，FPTree的開發流程為2個：

1、生成樹過程

2、挖掘樹過程：挖掘樹的過程也是一個生成樹的過程，每次挖掘一個節點的目的，都是為了發現該節點的頻繁項集，將最終生成的結果取所有子集然后將每一項與挖掘的節點組合，作為我們最后得到的結果。

Spark Mlib實現

訓練集如下：

面包 牛奶

面包 尿布 啤酒 雞蛋

牛奶 尿布 啤酒 可樂

面包 牛奶 尿布 啤酒

面包 牛奶 尿布 可樂

存儲在路徑data/sample_fpgrowth.txt中。

接下來調用FPGrouwth算法訓練數據集。

package com.zhaoyi;// $example on$

import java.util.Arrays;

import java.util.List;

import org.apache.spark.api.java.JavaRDD;

import org.apache.spark.api.java.JavaSparkContext;

import org.apache.spark.mllib.fpm.AssociationRules;

import org.apache.spark.mllib.fpm.FPGrowth;

import org.apache.spark.mllib.fpm.FPGrowthModel;

// $example off$

import org.apache.spark.SparkConf;

public class JavaSimpleFPGrowth {

public static void main(String[] args) {

SparkConf conf = new SparkConf().setMaster("local[*]").set("spark.testing.memory","2140000000")

.setAppName("JavaLinearRegressionWithSGDExample");

JavaSparkContext sc = new JavaSparkContext(conf);

// $example on$

JavaRDD data = sc.textFile("data/sample_fpgrowth.txt");

JavaRDD> transactions = data.map(line -> Arrays.asList(line.split(" ")));

// 最小支持度為0.5

FPGrowth fpg = new FPGrowth()

.setMinSupport(0.5)

.setNumPartitions(10);

FPGrowthModel model = fpg.run(transactions);

for (FPGrowth.FreqItemset itemset: model.freqItemsets().toJavaRDD().collect()) {

System.out.println("[" + itemset.javaItems() + "], " + itemset.freq());

}

double minConfidence = 0.8;

for (AssociationRules.Rule rule

: model.generateAssociationRules(minConfidence).toJavaRDD().collect()) {

System.out.println(

rule.javaAntecedent() + " => " + rule.javaConsequent() + ", " + rule.confidence());

}

// $example off$

sc.stop();

}

}

面包 牛奶

面包 尿布 啤酒 雞蛋

牛奶 尿布 啤酒 可樂

面包 牛奶 尿布 啤酒

面包 牛奶 尿布 可樂

可以看到，我們設置的最小支持度為0.5，也就是說，過濾過程中，會將低于出現次數小于3/5>0.5>2/5次的話，顯然可樂(出現一次，支持度為2/5=0.4)以及雞蛋(出現1次，支持度為1/5=0.2)都不會納入頻繁項集之中，在step1中就會被T除。

最終的輸出結果

[[尿布]], 4

[[牛奶]], 4

[[牛奶, 尿布]], 3

[[面包]], 4

[[面包, 牛奶]], 3

[[面包, 尿布]], 3

[[啤酒]], 3

[[啤酒, 尿布]], 3

[啤酒] => [尿布], 1.0

可以看到，該輸出結果完美的實現了牛奶尿布實例中的預測結果。即{啤酒，尿布}這樣的組合頻繁項集。

那么，我們可以考慮將這兩種商品擺放到一起，從而起到一定的增加銷售業績的作用(事實上沃爾瑪的確這么做了)。

總結

以上是生活随笔為你收集整理的fpgrowth算法实战 mlib_【spark】41.Spark Mlib：FPGrowth算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。