FP-growth

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

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

基本介紹

• 中文名：FP-Growth
• 外文名：FP-Growth
• 全稱：Frequent Pattern
• 屬性：數據結構
• 基本思路：不斷地疊代FP-tree的構造和投影
• 好處：比Apriori算法簡單

算法背景

提出背景

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

預備知識

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

FP-Tree結構圖

條件模式基：包含FP-Tree中與後綴模式一起出現的前綴路徑的集合

條件樹：將條件模式基按照FP-Tree的構造原則形成的一個新的FP-Tree

算法思想

基本思路：不斷地疊代FP-tree的構造和投影過程

算法描述如下：

1、對於每個頻繁項，構造它的條件投影資料庫和投影FP-tree。

2、對每個新構建的FP-tree重複這個過程，直到構造的新FP-tree為空，或者只包含一條路徑。

3、當構造的FP-tree為空時，其前綴即為頻繁模式；當只包含一條路徑時，通過枚舉所有可能組合併與此樹的前綴連線即可得到頻繁模式。

算法描述

構造FP-Tree

挖掘頻繁模式前首先要構造FP-Tree，算法偽碼如下：

輸入:一個交易資料庫DB和一個最小支持度threshold.

輸出:它的FP-tree.

步驟:

1.掃描資料庫DB一遍.得到頻繁項的集合F和每個頻繁項的支持度.把F按支持度遞降排序,結果記為L.

2.創建FP-tree的根節點,記為T,並且標記為’null’.然後對DB中的每個事務Trans做如下的步驟.

根據L中的順序,選出並排序Trans中的事務項.把Trans中排好序的事務項列表記為[p|P],其中p是第一個元素,P是列表的剩餘部分.調用insert_tree([p|P],T).

函式insert_tree([p|P],T)的運行如下.

如果T有一個子結點N,其中N.item-name=p.item-name,則將N的count域值增加1;否則,創建一個新節點N,使它的count為1,使它的父節點為T,並且使它的node_link和那些具有相同item_name域串起來.如果P非空,則遞歸調用insert_tree(P,N).

FP-Tree創建的算法流程圖

註：構造FP-Tree的算法理解上相對簡單，所以不過多描述

挖掘頻繁模式

對FP-Tree進行挖掘，算法如下：

輸入:一棵用算法一建立的樹Tree

輸出:所有的頻繁集

步驟:

調用FP-growth(Tree,null).

procedure FP-Growth ( Tree, x)

{

(1)if (Tree只包含單路徑P) then

(2) 對路徑P中節點的每個組合（記為B）

(3) 生成模式B並x，支持數=B中所有節點的最小支持度

(4) else 對Tree頭上的每個ai，do

{

(5) 生成模式B= ai 並 x，支持度=ai.support；

(6) 構造B的條件模式庫和B的條件FP樹TreeB；

(7)if TreeB != 空集

(8)then call FP-Growth ( TreeB , B )

}

}

演示圖

下圖給出了整個算法的演示過程：