數據挖掘fp-growth報告

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

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

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

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

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

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

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

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

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

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

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