數(shù)據(jù)挖掘fp-growth報告

1、英文標題：英文標題：MiningFrequentPatternswithoutCidateGeneration中文標題：不產(chǎn)生候選項集的頻繁模式挖掘中文標題：不產(chǎn)生候選項集的頻繁模式挖掘文獻來源：文獻來源：SpecialInterestGroupOnManagementOfData2000一、主要內(nèi)容：一、主要內(nèi)容：（1）論文研究的問題概述）論文研究的問題概述關(guān)聯(lián)規(guī)則在數(shù)據(jù)挖掘是一個重要的研究內(nèi)容。而產(chǎn)生頻繁集則是產(chǎn)生關(guān)聯(lián)規(guī)則的第一步。

2、在大多數(shù)以前的實現(xiàn)中，人們普遍采用了類似于Aprii的算法。這種算法受兩種非平凡開銷的影響：一是需要產(chǎn)生指數(shù)級的候選項集，二是需要重復(fù)地掃描整個數(shù)據(jù)庫，通過模式匹配檢查一個很大的候選集合。檢查數(shù)據(jù)庫中每個事務(wù)來確定候選項集支持度的開銷是非?？捎^的。針對Aprii算法的缺陷JiaweiHan提出FPgrowth算法該算法僅須掃描數(shù)據(jù)庫兩遍且無須生成候選項目集避免了產(chǎn)生“知識的組合爆炸”，提高了頻繁模式集的挖掘效率。（2）論文研究的理論意義

3、及其應(yīng)用前景論文研究的理論意義及其應(yīng)用前景之前的由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)算法都基于Aprii算法框架，在高密度數(shù)據(jù)庫上的執(zhí)行性能不佳。FPgrowth算法提出利用了高效的數(shù)據(jù)結(jié)構(gòu)FPtree，直觀并且容易實現(xiàn)，它只需要兩次掃描數(shù)據(jù)庫，極大地減小了IO操作次數(shù)，并且無須生成候選項目集，因而在時間和空間上都提高了處理效率。此算法執(zhí)行效率比基于Aprii的算法高一個數(shù)量級。FPgrowth算法將發(fā)現(xiàn)長頻繁模式的問題轉(zhuǎn)換成在較小的條件數(shù)據(jù)庫

4、中遞歸地搜索一些較短頻繁模式，然后連接后綴。它使用最不頻繁的模式后綴，提供了好的選擇性，顯著的降低了搜索開銷。（3）論文所述系統(tǒng)或算法的過程描述）論文所述系統(tǒng)或算法的過程描述FPgrowth采用如下分治策略：首先，將代表頻繁項集的數(shù)據(jù)庫壓縮到一棵頻繁模式樹（FP樹），該樹仍保留項集的關(guān)聯(lián)信息。然后，把這種壓縮的數(shù)據(jù)庫劃分成一組條件數(shù)據(jù)庫（一種特殊類型的投影數(shù)據(jù)庫），每個數(shù)據(jù)庫關(guān)聯(lián)一個頻繁項或“模式段”，并分別挖掘每個條件數(shù)據(jù)庫。對每個“

5、模式片段”，只需要考察與它相關(guān)聯(lián)數(shù)據(jù)集。因此，隨著被考察模式的“增長”，這種方法可以顯著的壓縮被搜索的數(shù)據(jù)集的大小。算法的具體過程描述如下：數(shù)據(jù)庫的第一次掃描導(dǎo)出頻繁項（1項集）的集合，并得到它們的支持度計數(shù)。頻繁項的集合按支持度計數(shù)的遞減排序，結(jié)果集或表記為L。然后，F(xiàn)P樹的構(gòu)造過程可描述為：首先創(chuàng)建樹的根結(jié)點，用“null”標記。第二次掃描數(shù)據(jù)庫D，每個事務(wù)中的項目按照支持度遞減排序，并對每個事務(wù)創(chuàng)建一個分枝。一般地，當(dāng)為一個事務(wù)考

6、慮增加分枝時，沿共同前綴上的每個結(jié)點的計數(shù)值增加1，為跟隨在前綴之后的項目創(chuàng)建結(jié)點并鏈接。為了方便樹的遍歷，創(chuàng)建一個頻繁項目頭表，使得每個項目通過一個結(jié)點頭指針指向它在樹中的位置。這樣，數(shù)據(jù)庫頻繁模式的挖掘問題就轉(zhuǎn)換成挖掘FP樹的問題。FP樹挖掘過程可描述為：從項頭表開始挖掘，由頻率低的節(jié)點開始，因此選取長度為1的頻繁模式（初始后綴模式）開始，沿循每個頻繁項的鏈接來遍歷FP樹，通過積累該采用基于劃分的分而治之的方法，大大降低了后續(xù)條件模

7、式基和條件FP樹的大小。它使用最不頻繁的模式后綴，提供了好的選擇性，顯著的降低了搜索開銷。二、實驗評價：二、實驗評價：（1）實驗數(shù)據(jù)集）實驗數(shù)據(jù)集論文中報告了兩個合成數(shù)據(jù)集上的實驗結(jié)果。第一個是包括1000個物品的合成數(shù)據(jù)集。在這組數(shù)據(jù)中，平均交易規(guī)模和平均最大潛在的頻繁項集的大小分別設(shè)置為10和4，而在數(shù)據(jù)集中交易的數(shù)量設(shè)置為100K。這是一個短頻繁項集的稀疏數(shù)據(jù)集。第二合成數(shù)據(jù)集，包括10000項的物品。平均交易規(guī)模和平均最大潛在的

8、頻繁項集的大小分別設(shè)置為25和20。它是一個長頻繁項集和短頻繁模式混合的稠密數(shù)據(jù)集。在長模式數(shù)據(jù)集的FPgrowth算法的性能測試中，使用的是從Connect4游戲狀態(tài)信息編譯的真實數(shù)據(jù)集。它包含67557筆交易，是一個長頻繁項集的稠密數(shù)據(jù)集。（2）評價指標和性能分析）評價指標和性能分析FPgrowth在密集的數(shù)據(jù)集上，一個大數(shù)據(jù)庫能夠被有效地壓縮成比原數(shù)據(jù)庫小很多的高密度結(jié)構(gòu)。在FP樹的分支共享程度較高，對交易頻繁的預(yù)測之間共享收益大

9、大超過開銷，從而使FP樹的空間在很多情況下更高效。對于稀疏數(shù)據(jù)集，F(xiàn)P樹的分支共享程度較低，大大降低了FPgrowth的性能，因此我們應(yīng)該構(gòu)建投影數(shù)據(jù)庫來提高性能。（3）本文方法的優(yōu)點總結(jié)）本文方法的優(yōu)點總結(jié)1、緊湊性，非頻繁的項被刪除，減少了不相關(guān)的信息；按頻率遞減排列，使得更頻繁地項更容易在樹結(jié)構(gòu)中被共享；數(shù)據(jù)量比原數(shù)據(jù)庫要小，一個大數(shù)據(jù)庫能夠被有效地壓縮成比原數(shù)據(jù)庫小很多的高密度結(jié)構(gòu)。只需要兩次掃描數(shù)據(jù)庫，減少大量掃描數(shù)據(jù)庫的IO

10、時間。2、該算法基于FPTree的挖掘采取模式增長的遞歸策略，創(chuàng)造性地提出了無候選項目集的挖掘方法，在進行長頻繁項集的挖掘時效率較好。3、挖掘過程中采取了分治策略，將這種壓縮后的數(shù)據(jù)庫DB分成一組條件數(shù)據(jù)庫Dn，每個條件數(shù)據(jù)庫關(guān)聯(lián)一個頻繁項，并分別挖掘每一個條件數(shù)據(jù)庫。而這些條件數(shù)據(jù)庫Dn要遠遠小于數(shù)據(jù)庫DB。4、完整性，不會打破任何事務(wù)數(shù)據(jù)中的長模式，為頻繁模式的挖掘保留了完整信息。（4）本文方法的缺點和局限性）本文方法的缺點和局限性

11、1、該算法采取增長模式的遞歸策略，雖然避免了候選項目集的產(chǎn)生。但在挖掘過程，如果一項大項集的數(shù)量很多，并且由原數(shù)據(jù)庫得到的FPTree的分枝很多，而且分枝長度又很長時，該算法需要構(gòu)造出數(shù)量巨大的條件FPTree，不僅費時而且要占用大量的空間，挖掘效率不好，而且采用遞歸算法本身效率也較低。2、由于海量的事物集合存放在大型數(shù)據(jù)庫中，經(jīng)典的FPGrowth算法在生成新的FPTree時每次都要遍歷調(diào)減模式基兩次，導(dǎo)致系統(tǒng)需要反復(fù)申請本地以及數(shù)據(jù)