和Apriori算法相比，F(xiàn)P-growth算法只需要對數(shù)據(jù)庫進(jìn)行兩次遍歷，從而高效發(fā)現(xiàn)頻繁項(xiàng)集。對于搜索引擎公司而言，他們需要通過查看互聯(lián)網(wǎng)上的用詞，來找出經(jīng)常在一塊出現(xiàn)的詞。因此就需要能夠高效的發(fā)現(xiàn)頻繁項(xiàng)集的方法，F(xiàn)P-growth算法就可以完成此重任。

FP-growth算法是基于Apriori原理的，通過將數(shù)據(jù)集存儲(chǔ)在FP（Frequent Pattern)樹上發(fā)現(xiàn)頻繁項(xiàng)集。

FP-growth算法只需要對數(shù)據(jù)庫進(jìn)行兩次掃描，而Apriori算法在求每個(gè)潛在的頻繁項(xiàng)集時(shí)都需要掃描一次數(shù)據(jù)集，所以說FP-growth算法是高效的。

[[212909]]

FP算法發(fā)現(xiàn)頻繁項(xiàng)集的過程是：

(1)構(gòu)建FP樹；

(2)從FP樹中挖掘頻繁項(xiàng)集

FP表示的是頻繁模式，其通過鏈接來連接相似元素，被連起來的元素可看成是一個(gè)鏈表

將事務(wù)數(shù)據(jù)表中的各個(gè)事務(wù)對應(yīng)的數(shù)據(jù)項(xiàng)，按照支持度排序后，把每個(gè)事務(wù)中的數(shù)據(jù)項(xiàng)按降序依次插入到一棵以 NULL為根節(jié)點(diǎn)的樹中，同時(shí)在每個(gè)結(jié)點(diǎn)處記錄該結(jié)點(diǎn)出現(xiàn)的支持度。

假設(shè)存在的一個(gè)事務(wù)數(shù)據(jù)樣例為,構(gòu)建FP樹的步驟如下：

結(jié)合Apriori算法中最小支持度的閾值，在此將最小支持度定義為3，結(jié)合上表中的數(shù)據(jù)，那些不滿足最小支持度要求的將不會(huì)出現(xiàn)在***的FP樹中。

據(jù)此構(gòu)建FP樹，并采用一個(gè)頭指針表來指向給定類型的***個(gè)實(shí)例，快速訪問FP樹中的所有元素，構(gòu)建的帶頭指針的FP樹如圖：

結(jié)合繪制的帶頭指針表的FP樹，對表中數(shù)據(jù)進(jìn)行過濾，排序如下：

在對數(shù)據(jù)項(xiàng)過濾排序了之后，就可以構(gòu)建FP樹了，從NULL開始，向其中不斷添加過濾排序后的頻繁項(xiàng)集。過程可表示為：

這樣，F(xiàn)P樹對應(yīng)的數(shù)據(jù)結(jié)構(gòu)就建好了，現(xiàn)在就可以構(gòu)建FP樹了，F(xiàn)P樹的構(gòu)建函數(shù)參見Python源代碼。

在運(yùn)行上例之前還需要一個(gè)真正的數(shù)據(jù)集，結(jié)合之前的數(shù)據(jù)自定義數(shù)據(jù)集。這樣就構(gòu)建了FP樹，接下來就是使用它來進(jìn)行頻繁項(xiàng)集的挖掘。