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

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

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

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

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

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

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

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

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

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

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

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