FP的全稱是Frequent Pattern，在算法中使用了一種稱為頻繁模式樹（Frequent Pattern Tree）的數據結構。
基本介紹
- 中文名：FP增長算法
- 外文名：Frequent Pattern
- 運用：頻繁模式樹
- 說明：a.FP-Tree
背景,算法說明,
背景
Apriori算法在產生頻繁模式完全集前需要對資料庫進行多次掃描，同時產生大量的候選頻繁集，這就使Apriori算法時間和空間複雜度較大。但是Apriori算法中有一個很重要的性質：頻繁項集的所有非空子集都必須也是頻繁的。由此性質，引出了FP增長算法。
算法說明
首先介紹FP增長算法中的幾個概念
b.條件模式基：包含FP-Tree中與後綴模式一起出現的前綴路徑的集合
c.條件樹：將條件模式基按照FP-Tree的構造原則形成的一個新的FP-Tree
步驟：
挖掘頻繁模式前首先要構造FP-Tree，
輸入:一個事物資料庫D和一個最小支持度threshold.
輸出:對應的FP-tree.
算法流程
1.掃描資料庫T一遍.得到頻繁項的集合F和每個頻繁項的支持度.把F按支持度遞降排序,結果記為L.
2.創建FP-tree的根節點,記為T,並且標記為"null".然後對D中的每個事務t,
根據L中的順序,選出並排序t中的事務項.把t中排好序的事務項列表記為[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進行挖掘，算法如下：
輸入:一棵用算法一建立的樹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 )
}
}
