FP-growth算法，fpgrowth算法詳解

下面使用的最小支持度是2，也就是說最小等于2算達標，對應代碼中則是>minSup=1

使用FP-growth算法來高效發(fā)現(xiàn)頻繁項集

前言

你用過搜索引擎揮發(fā)現(xiàn)這樣一個功能：輸入一個單詞或者單詞的一部分，搜索引擎酒會自動補全查詢詞項，用戶甚至實現(xiàn)都不知道搜索引擎推薦的東西是否存在，反而會去查找推薦詞項，比如在百度輸入“為什么”開始查詢時，會出現(xiàn)諸如“為什么我有了變身器卻不能變身奧特曼”之類滑稽的推薦結果，為了給出這些推薦查詢慈祥，搜索引擎公司的研究人員使用了本文要介紹的一個算法，他們通過查看互聯(lián)網(wǎng)上的用詞來找出經(jīng)常在一塊出現(xiàn)的詞對，這需要一種高效發(fā)現(xiàn)頻繁集的方法。該算法稱作FP-growth,又稱為FP-增長算法，它比Apriori算法要快，它基于Apriori構建，但在完成相同任務時采用了一些不同的技術。不同于Apriori算法的”產(chǎn)生－測試”，這里的任務是將數(shù)據(jù)集存儲在一個特定的稱做FP樹的結構之后發(fā)現(xiàn)頻繁項集或者頻繁項對，即常在一塊出現(xiàn)的元素項的集合FP樹,這種做法是的算法的執(zhí)行速度要快于apriori，通常性能要好兩個數(shù)量級以上。

FP樹表示法

FP樹時一種輸入數(shù)據(jù)的壓縮表示，它通過逐個讀入事務，并把事務映射到FP樹中的一條路徑來構造，由于不同的事務可能會有若干個相同的項，因此它們的路徑可能部分重疊。路徑相互重疊越多，使用FP樹結構獲得的壓縮效果越好，如果FP樹足夠小，能夠存放在內(nèi)存中，就可以直接從這個內(nèi)存中的結構提取頻繁項集，而不必重復地掃描存放在硬盤上的數(shù)據(jù)。

下圖顯示了一個數(shù)據(jù)集，它包含10個事務和5個項。(可以把一條事務都直觀理解為超市的顧客購物記錄，我們利用算法來發(fā)掘那些物品或物品組合頻繁的被顧客所購買。)

下圖繪制了讀入三個事務之后的FP樹的結構以及最終完成構建的FP樹，初始，FP樹僅包含一個根節(jié)點，用符號null標記，隨后，用如下方法擴充FP樹：

通常，FP樹的大小比未壓縮的數(shù)據(jù)小，因為購物籃數(shù)據(jù)的事務常常共享一些共同項，在最好的情況下，所有的事務都具有相同的項集，FP樹只包含一條節(jié)點路徑，當每個事務都具有唯一項集時，導致最壞情況發(fā)生，由于事務不包含任何共同項，FP樹的大小實際上與原數(shù)據(jù)的大小一樣，然而，由于需要附加的空間為每個項存放節(jié)點間的指針和技術，FP樹的存儲需求增大。

FP樹還包含一個連接具有相同項的節(jié)點的指針列表，這些指針再上圖中用虛線表示，有助于快速訪問樹中的項。

FP增長算法的頻繁項集產(chǎn)生

FP-growth是一種以自底向上方式探索樹，由FP樹產(chǎn)生頻繁項集的算法，給定上面構建的FP樹，算法首先查找以e結尾的頻繁項集，接下來是b,c,d，最后是a，由于每一個事務都映射到FP樹中的一條路徑，因為通過僅考察包含特定節(jié)點（例如e）的路徑，就可以發(fā)現(xiàn)以e結尾的頻繁項集，使用與節(jié)點e相關聯(lián)的指針，可以快速訪問這些路徑，下圖顯示了所提取的路徑，后面詳細解釋如何處理這些路徑，以得到頻繁項集。

上面的圖演示了講頻繁項集產(chǎn)生的問題分解成多個子問題，其中每個子問題分別涉及發(fā)現(xiàn)以e,d,c,b和a結尾的頻繁項集

發(fā)現(xiàn)以e結尾的頻繁項集之后，算法通過處理與節(jié)點d相關聯(lián)的路徑，進一步尋找以d為結尾的頻繁項集，繼續(xù)該過程，直到處理了所有與節(jié)點c,b和a相關聯(lián)的路徑為止，上面的圖分別顯示了這些項的路徑，而他們對應的頻繁項集匯總在下表中

FP增長采用分治策略將一個問題分解為較小的子問題，從而發(fā)現(xiàn)以某個特定后綴結尾的所有頻繁項集。例如，假設對發(fā)現(xiàn)所有以e結尾的頻繁項集感興趣，為了實現(xiàn)這個目的，必須首先檢查項集{e}本身是否頻繁，如果它是平凡的，則考慮發(fā)現(xiàn)以de結尾的頻繁項集子問題，接下來是ce和ae,依次，每一個子問題可以進一步劃分為更小的子問題，通過合并這些子問題的結果，就可以找到所有以e結尾的頻繁項集，這種分治策略是FP增長算法采用的關鍵策略。

為了更具體地說明如何解決這些子問題，考慮發(fā)現(xiàn)所有以e結尾的頻繁項集的任務。

?

這個例子解釋了FP增長算法中使用的分治方法，每一次遞歸，都要通過更新前綴路徑中的支持度計數(shù)和刪除非頻繁的項來構建條件FP樹，由于子問題時不相交的，因此FP增長不會產(chǎn)生任何重復的項集，此外，與節(jié)點相關聯(lián)的支持度計數(shù)允許算法在產(chǎn)生相同的后綴項時進行支持度計數(shù)。

FP增長是一個有趣的算法，它展示了如何使用事務數(shù)據(jù)集的壓縮表示來有效的產(chǎn)生頻繁項集，此外對于某些事務數(shù)據(jù)集，FP增長算法比標準的Apriori算法要快幾個數(shù)量級，FP增長算法的運行性能取決于數(shù)據(jù)集的“壓縮因子”。如果生成的FP樹非常茂盛（在最壞的情況下，是一顆完全二叉樹）則算法的性能顯著下降，因為算法必須產(chǎn)生大量的子問題，并且需要合并每個子問題返回的結果

?

總結

以上是生活随笔為你收集整理的FPgrwoth详解(转载+修改一处图片问题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。