基于頻繁樹的關聯挖掘算法FP-Growth的研究

摘要:FP-growth算法是當前挖掘頻繁項目集算法中應用最廣，并且不需要候選集的一種挖掘關聯規則的算法。該文研究分析研究了FP-growth的算法思想、算法描述，并舉例分析了FP-growth的執行過程。

關鍵字:關聯規則;頻繁項集;FP-tree;FP-growth

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2009)33-9320-02

The Research of FP-growth Algorithm Based on FP-tree Association Mining

GU Hong-qi， XIONG Fu-shong

(Nanjing Institute of Railway Technology， Department of Information Engineering， Suzhou 2150000， China)

Abstract: FP-growth algorithm is one of the currently most popular algorithms for mining association rules without candidate generation. in this paper， the thinking and description of FP-growth algorithm is introduced. And illustrate the implement process of FP-growth algorithm.

Key words: association rules; frequent itemset; FP-tree; FP-growth

經典的Apriori算法[1]在發現頻繁項集的過程中，當頻繁1-項集的數目很大或需發現的頻繁模式很長時，需要產生的候選項集的數量就會劇增，從而造成算法效率急劇下降。研究不產生候選項集的挖掘算法就變得很理所當然了。

該文著重研究了在挖掘過程中不需要產生候選項集的算法:FP-增長算法[2-3]，它采取分治策略:將提供頻繁項集的數據庫壓縮到一棵頻繁模式樹(或FP-樹)，但仍保留項集關聯信息;然后，將這種壓縮后的數據庫分成一組條件數據庫(一種特殊類型的投影數據庫)，每個關聯一個頻繁項，并分別挖掘每個數據庫。

1 頻繁模式樹FP-tree

頻繁模式樹FP-tree就是這樣的一種的數據結構，用于存儲挖掘頻集所需的事務數據庫的信息。頻繁模式樹是一種樹結構，定義如下:

1) 它由一個標記為<1>的根節點，多個以項目為前綴的子樹作為根節點的子節點，以及一個頻集頭表組成。

2) 子樹的第一個節點由3個字段組成:項目名稱，支持度計數和節點指針，這里項目名稱表明是這個節點代表什么項目，支持度計數表示到達這個節點的事務的數目，節點指針指向該項目在頻繁模式樹中出現的下一個節點，若該項目是頻繁模式樹的最后一個節點，該節點指針為空(用1表示)。

3) 頻集頭表的每一個節點由2個字段組成:項目名稱和頭節點指針。頭節點指針指向該項目在頻繁模式樹中出現的下一個節點。

2 FP-growth的算法描述

算法:FP-Growth。使用FP-樹，通過模式段增長，挖掘頻繁模式。

輸入:事務數據庫D;最小支持度閾值min_sup。

輸出:頻繁模式的完全集。

2.1 按以下步驟構造FP-樹:

1) 掃描事務數據庫D一次。收集頻繁項的集合F和它們的支持度。對F按支持度降序排序，結果為頻繁項表L。

2) 創建FP-樹的根結點，以\"1\"標記它。對于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.2 FP-樹的挖掘通過調用FP_growth(FP_tree， 1)實現

該過程實現如下:

procedure 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β，β);}

3 應用舉例

通過一個實例來說明FP-growth算法的頻繁項集挖掘過程。該實例基于圖1最左側所示的事務數據庫D。該數據庫中共有5個事務。設最小支持度為3，即(min_sup=60%)。

1) 首先對數據庫D進行一次掃描，找出候選1-項集的集合，并得到它們的支持度計數(頻繁性)。然后，按照支持度的大小遞減排列候選1-項集的各項，將候選1-項集中支持度小于最小支持度項刪除，得到頻繁1-項集L(如圖1所示)，然后根據頻繁1-項集重新生成數據庫D如圖2所示。

2) 在掃描完所有的事務以后，生成帶有相應節點鏈的Fp-樹如圖3所示。

FP-Tree挖掘處理如下。由長度為1的頻繁模式(初始后綴模式)開始，構造它的條件模式基(一個“子數據庫”，由FP-樹中與后綴模式一起出現的前綴路徑集組成)。然后，構造它的(條件)FP-樹，并遞歸地在該樹上進行挖掘。模式增長通過后綴模式與由條件FP-樹產生的頻繁模式連接實現。

3) 對每個模式庫用模式庫中的頻繁項建立FP-tree，如圖4所示。

4 算法分析

FP-growth方法將發現長頻繁模式的問題轉換成遞歸地發現一些短模式，然后連接后綴。它使用最不頻繁的項作后綴，提供了好的選擇性。同時，該方法大大降低了搜索開銷。

綜合起來，FP-growth算法具有以下優點:

1) 一個大型數據庫能夠被有效地壓縮成比原數據庫小很多的高密度的數據結構，避免了重復掃描數據庫的開銷。

2) 該算法基于FP-tree的挖掘采取模式增長的遞歸策略，創造性地提出了無候選項目集的挖掘方法，在進行頻繁項目集的挖掘時效率較好。

3) 挖掘過程中采取了分治的策略，將這種壓縮后的數據庫D分成一組條件數據庫D，每個條件數據庫關聯一個頻繁項，并分別挖掘每一個條件數據庫。而這些條件數據庫要遠遠小于數據庫D。

FP-growth算法也存在一些缺點，主要有:在挖掘過程，如果大項集的數量很多，并且如果由原數據庫得到的FP-tree的分支很多，而且分支長度很長時，該算法將需要構造出數量巨大的條件FP-tree，不僅費時而且要占用大量的空間，挖掘效率不好，且遞歸算法本身效率也較低。

參考文獻:

[1] 畢建欣，張岐山.關聯規則挖掘算法綜述[J].中國工程科學，2005，7(4).

[2] 王曙光，施小英.一種改進的相聯規則提取算法[J]，計算機工程與應用，2002(15):173-174.

[3] 包劍.關聯規則挖掘研究[J].計算機系統應用，2005(11).