FP-Growth算法實驗報告一、算法介紹數據挖掘是從數據庫中提取隱含的、未知的和潛在的有用信息的過程,是數據庫及相關領域研究中的一個極其重要而又具有廣闊應用前景的新領域. 目前,對數據挖掘的研究主要集中在分類、聚類、關聯規則挖掘、序列模式發現、異常和趨勢發現等方面,其中關聯規則挖掘在商業等領域中的成功應用使它成為數據挖掘中最重要、最活躍和最成熟的研究方向. 現有的大多數算法均是以Apriori 先驗算法為基礎的,產生關聯規則時需要生成大量的候選項目集. 為了避免生成候選項目集,Han等提出了基于FP 樹頻繁增長模式（Frequent-Pattern Growth，FP-Growth）算法。FP 樹的構造過程可描述為: 首先創建樹的根結點, 用“null”標記. 掃描交易數據集DB ,每個事務中的項目按照支持度遞減排序,并對每個事務創建一個分枝. 一般地,當為一個事務考慮增加分枝時,沿共同前綴上的每個結點的計數值增加1 ,為跟隨在前綴之后的項目創建結點并鏈接. 為方便樹的遍歷,創建一個頻繁項目列表,使得每個項目通過一個結點頭指針指向它在樹中的位置. FP 樹挖掘過程可描述為:由長度為1 的頻繁項目開始,構造它的條件項目基和條件FP樹,并遞歸地在該樹上進行挖掘. 項目增長通過后綴項目與條件FP 樹產生的頻繁項目連接實現. FP-Growth 算法將發現大頻繁項目集的問題轉換成遞歸地發現一些小頻繁項目,然后連接后綴.它使用最不頻繁的項目后綴,提供了好的選擇性。算法：FP-Growth。使用FP樹，通過模式增長挖掘頻繁模式。輸入：n D：事物數據庫n min_sup：最小支持度閾值輸出：頻繁模式的完全集。方法：1. 按一下步驟構造FP樹：（a）掃描數據庫D一次。手機頻繁項的集合F和它們的支持度計數。對F按支持度計數降序排序，結果為頻繁項列表L。（b）創建FP樹的根節點，以“null”標記它。對于D中每個事物Trans，執行：選擇Trans中的頻繁項，并按L中的次序排序。設Trans排序后的頻繁項列表為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. FP樹的挖掘通過調用FP-growth（FP_tree,null）實現。該過程實現如下。Procedure FP_growth(Tree,)（1）if Tree包含單個路徑P then（2）for 路徑P中結點的每個組合（記作）（3）產生模式，其中支持度計數support_count等于中結點的最小支持度計數；（4）else for Tree的表頭中的每一個i（5）產生一個模式=i,其中支持度計數support_count=i.support_count;（6）構造的調減模式基然后構造的條件FP樹Tree；（7）if Tree then（8）調用FP_growth(Tree,)；二、算法實現及實驗結果 本實驗有兩個測試集合：小數據集A：50條事物集，10個不同的項大數據集合B：5670事物集，100個不同項1.對數據集合A進行min_sup=8%計數產生的頻繁項集結果如下：表1. 頻繁一項集項集支持度計數支持度1I3 3570%2I9 612%3I6 510%4I1 )1734%5I4 1428%6I71122%7I2 3468%8I8 1122%9I5 1632%表2. 頻繁二項集項集支持度計數支持度1I2 I6510%2I3 I9 48%3I2 I9 48%4I1 I7 48%5I2 I7 714%6I3 I7 816%7I2 I8 612%8I3 I8 816%9I2 I4 1122%10I2 I5 1122%11I3 I5 1326%12I3 I1 1020%13I2 I1 1122%14I3 I2 2142%表3. 頻繁三項集項集支持度計數支持度1I2 I5 I7510%2I3 I5 I7612%3I3 I2 I7510%4I3 I2 I8510%5I2 I5 I8510%6I3 I5 I8 612%7I2 I1 I4510%8I3 I1 I5510%9I2 I1 I5 612%10I3 I2 I5 816%11I3 I2 I148%表4. 頻繁四項集項集支持度計數支持度1I3 I2 I5 I7510%2I3 I2 I5 I8510%3I3 I2 I1 I548%2對數據集B進行不同支持度實驗時間消耗結果如下：圖1.數據集B消耗時間三、算法的優缺點分析1. FP-Growth算法的優點：(1)一個大數據庫能夠被有效地壓縮成比原數據庫小很多的高密度結構，避免了重復掃描數據庫的開銷(2)該算法基于FP-Tree的挖掘采取模式增長的遞歸策略，創造性地提出了無候選項目集的挖掘方法，在進行長頻繁項集的挖掘時效率較好。(3)挖掘過程中采取了分治策略，將這種壓縮后的數據庫DB分成一組條件數據庫Dn，每個條件數據庫關聯一個頻繁項，并分別挖掘每一個條件數據庫。而這些條件數據庫Dn要遠遠小于數據庫DB。2. FP-Growth算法的缺點及改進方法(1)該算法采取增長模式的遞歸策略，雖然避免了候選項目集的產生。但在挖掘過程，如果一項大項集的數量很多，并且由原數據庫得到的FP-Tree的分枝很多，而且分枝長度又很長時，該算法需要構造出數量巨大的conditional FP-Tree，不僅費時而且要占用大量的空間，挖掘效率不好，而且采用遞歸算法本身效率也較低。改進策略：FA算法-FP-Growth算法與Apriori算法的結合在原數據庫得到的FP-Tree的基礎上,采用Apriori算法的方法進行挖掘,挖掘過程中不構造conditional FP-Tree。挖掘過程仍然采用分治的策略,即將壓縮后的數據庫D分成一組條件數據庫,每個條件數據庫關聯一個頻繁項。假設有n個一項大項集,則數據庫D可被分割成n個條件數據庫Di(i=1,n),而數據庫Di是關聯一項大項集Ii的條件數據庫。然后分別采用Apriori算法挖掘每一個條件數據庫Di,得到所有以Ii為尾的大項集。實現方法是,仍然采用FP-Growth算法的方法構造一棵FP-Tree,不過在每個項前綴子樹的節點中增加一個域:con-count。在對條件數據庫Di進行挖掘時,該域記錄了所在路徑代表的交易(transaction)中達到此節點的并且包括Ii的交易個數。而為了找出所有包含Ii的大項集,首先沿著頻繁項頭表中項Ii的鏈域找到item-name為Ii的每個項前綴子樹的節點Pi,再沿著每個Pi的父指針往上走直到根節點,使該路徑上經過的每個項前綴子樹節點的con-count域都增加Pi.count,根節點不增加。同時增加一個臨時頻繁項頭表lTable,每個表項(entry)由三個域組成：（1）item-name；（2）node-link；（3） con-count。若某個項前綴子樹節點的con-count域增加了Pi.count,另外假如lTable中沒有一個表項的item-name與Pi.item-name相同,則在lTable中增加一個表項,使它的item-name,與con-count都與Pi的相同,同時node-link指向該項前綴子樹節點的Pi的地址。如果lTable中存在一個表項,它的item-name與Pi.item-name相同,則只要對該表項的con-count域增加Pi. count就行了。然后再對lTable中的每一個表項的con-count域進行統計,若它的con-count域大于預先給定的最小支持度,則保留該表項,否則刪除該表項1。(2)由于海量的事物集合存放在大型數據庫中，經典的FP-Growth算法在生成新的FP-Tree時每次都要遍歷調減模式基兩次，導致系統需要反復申請本地以及數據庫服務器的資源查詢相同內容的海量數據，一方面降低了算法的效率，另一方面給數據庫服務器產生高負荷，不利于數據庫服務器正常運作。改進策略：針對 FP-Growth 算法的缺點，對經典算法進行改進，提出使用支持度計數二維表的方法，從而省去經典算法對條件模式基的第一次遍歷，具體算法描述為：在第一次遍歷事務集合 T 的同時創建二維向量，記錄每個事務中各個項兩兩組合出現的支持度計數。如有事務 “A，B，C，D”，則二維向量表中(A,B)、(A,C)、(A,D)、(B,C)、(B,D)、 (C,D)項都需要加 1。其中向量(C,B)和(B,C)是兩個不同的向量。 利用遞歸方式創建 條件下(Null)的條件 FP 子樹時，無需兩次遍歷條件模式基(其中第一次遍歷條件模式基可得到支持度計數列表，第二次遍歷條件模式基可插入樹節點從而創建 FP 樹)。支持度計數列表可以從支持度計數二維向量列表中獲得。抽取二維向量表中的與 Ei 相