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

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

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

[[212909]]

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

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

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

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

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

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

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

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

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

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

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

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