數(shù)據(jù)挖掘FP-Growth算法實驗報告.docx

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