標籤:數據挖掘

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

1演算法背景

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

  FP-Tree結構圖

條件模式基:包含FP-Tree中與後綴模式一起出現的前綴路徑的集合
條件樹:將條件模式基按照FP-Tree的構造原則形成的一個新的FP-Tree

2演算法思想

基本思路:不斷地迭代FP-tree的構造和投影過程
演算法描述如下:
1、對於每個頻繁項,構造它的條件投影資料庫和投影FP-tree。
2、對每個新構建的FP-tree重複這個過程,直到構造的新FP-tree為空,或者只包含一條路徑。
3、當構造的FP-tree為空時,其前綴即為頻繁模式;當只包含一條路徑時,通過枚舉所有可能組合併與此樹的前綴連接即可得到頻繁模式。

3演算法描述

挖掘頻繁模式
對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)thencall FP-Growth ( TreeB , B )
}
}

4演示圖

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

FP-Growth演算法實例演示圖

FP-Growth演算法實例演示圖
上一篇[交叉銷售]    下一篇 [FP-tree]

相關評論

同義詞:暫無同義詞