在我們?nèi)粘Ｉ钪校褂盟阉饕鏁r(shí)，輸入一個(gè)單詞或者單詞的一部分，就會(huì)自動(dòng)補(bǔ)全查詢?cè)~項(xiàng)

FP-growth算法，不同于Apriori算法生成候選項(xiàng)集再檢查是否頻繁的”產(chǎn)生-測(cè)試“方法，但是基于Apriori構(gòu)建，但在完成相同任務(wù)時(shí)采用了一些不同的技術(shù).這里的任務(wù)是將數(shù)據(jù)集存儲(chǔ)在一個(gè)特定的稱作FP樹的結(jié)構(gòu)之后發(fā)現(xiàn)頻繁項(xiàng)集或頻繁項(xiàng)對(duì)，即常在一塊出現(xiàn)的元素項(xiàng)的集合FP樹.這種做法是的算法的執(zhí)行速度要快于Apriori,通常性能要好兩個(gè)數(shù)量級(jí)以上.

FP-growth 算法是一種用于發(fā)現(xiàn)數(shù)據(jù)集中頻繁模式的有效方法，利用Apriori 原理，只對(duì)數(shù)據(jù)集掃描兩次，運(yùn)行更快。在算法中，數(shù)據(jù)集存儲(chǔ)在 FP 樹中，構(gòu)建完樹后，通過查找元素項(xiàng)的條件基及構(gòu)建條件 FP 樹來發(fā)現(xiàn)頻繁項(xiàng)集。重復(fù)進(jìn)行直到FP樹只包含一個(gè)元素為止。

優(yōu)點(diǎn)：一般要快于 Apriori 算法。

缺點(diǎn)：實(shí)現(xiàn)比較困難，在某些數(shù)據(jù)集上性能會(huì)下降。

適用數(shù)據(jù)類型：離散型數(shù)據(jù)。

應(yīng)用領(lǐng)域：在多種文本文檔中查找頻繁單詞；購物交易；醫(yī)學(xué)診斷；大氣研究等。

一、FpTree
FP代表頻繁模式（Frequent Pattern）。一棵FP樹看上去與[計(jì)算機(jī)科學(xué)中的其他樹結(jié)構(gòu)類似，但是它通過鏈接（link）來連接相似元素，被連起來的元素項(xiàng)可以看成一個(gè)鏈表。

FP樹看上去就是一棵前綴樹，根節(jié)點(diǎn)是空集，結(jié)點(diǎn)上是單個(gè)元素，保存了它在數(shù)據(jù)集中的出現(xiàn)次數(shù)，出現(xiàn)次數(shù)越多的元素越接近根。此外，結(jié)點(diǎn)之間通過鏈接（link）相連，只有相似元素會(huì)被連起來，連起來的元素又可以看成鏈表。同一個(gè)元素可以在FP樹中多次出現(xiàn)，根據(jù)位置不同，對(duì)應(yīng)著不同的頻繁項(xiàng)集?？梢詾镕P樹設(shè)置最小支持度，過濾掉出現(xiàn)次數(shù)太少的元素。
下面這個(gè)數(shù)據(jù)集構(gòu)造FP樹如下圖所示。

假設(shè)最下支持度為3，即低于3的元素項(xiàng)被認(rèn)為是不頻繁的，不會(huì)出現(xiàn)在樹中，例如p,q

這棵樹每個(gè)結(jié)點(diǎn)上都是一個(gè)單獨(dú)的元素，及其在路徑中的出現(xiàn)次數(shù)，例如"z:5"表示集合{z}出現(xiàn)了5次，而"x:3"表示集合{z,x}出現(xiàn)了3次，這是路徑相關(guān)的。

FP-growth算法的工作流程：首先構(gòu)建FP樹，然后利用它來挖掘頻繁項(xiàng)集。為構(gòu)建FP樹，需要對(duì)原始數(shù)據(jù)集掃描兩遍。第一遍對(duì)所有元素項(xiàng)的出現(xiàn)次數(shù)進(jìn)行計(jì)數(shù)。數(shù)據(jù)庫的第一遍掃描用來統(tǒng)計(jì)出現(xiàn)的頻率，而第二遍掃描中只考慮那些頻繁元素。

FP-growth算法還需要一個(gè)稱為頭指針表的數(shù)據(jù)結(jié)構(gòu)，其實(shí)很簡(jiǎn)單，就是用來記錄各個(gè)元素項(xiàng)的總出現(xiàn)次數(shù)的數(shù)組，再附帶一個(gè)指針指向FP樹中該元素項(xiàng)的第一個(gè)節(jié)點(diǎn)。這樣每個(gè)元素項(xiàng)都構(gòu)成一條單鏈表。這個(gè)header除了指向指定元素的第一個(gè)結(jié)點(diǎn)外，還可以保存該元素在數(shù)據(jù)集中的總出現(xiàn)次數(shù)。

這里使用Python字典作為數(shù)據(jù)結(jié)構(gòu)，來保存頭指針表。以元素項(xiàng)名稱為鍵，保存出現(xiàn)的總次數(shù)和一個(gè)指向第一個(gè)相似元素項(xiàng)的指針。

首先，遍歷一次數(shù)據(jù)集，統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，然后把出現(xiàn)次數(shù)較小的濾掉（例如選取最小支持度3，將出現(xiàn)次數(shù)小于3的元素濾除），然后對(duì)每個(gè)樣本按照元素出現(xiàn)次數(shù)重排序。上面給出的數(shù)據(jù)集樣例中，出現(xiàn)次數(shù)不小于3的元素有：z、r、x、y、s、t，濾除并重排后的樣本如下所示。

元素項(xiàng)排序：FP樹會(huì)合并相同的頻繁項(xiàng)集（或相同的部分）。因此為判斷兩個(gè)項(xiàng)集的相似程度需要對(duì)項(xiàng)集中的元素進(jìn)行排序（不過原因也不僅如此，還有其它好處）。排序基于元素項(xiàng)的絕對(duì)出現(xiàn)頻率（總的出現(xiàn)次數(shù)）來進(jìn)行。在第二次遍歷數(shù)據(jù)集時(shí)，會(huì)讀入每個(gè)項(xiàng)集（讀取），去掉不滿足最小支持度的元素項(xiàng)（過濾），然后對(duì)元素進(jìn)行排序（重排序）。

對(duì)示例數(shù)據(jù)集進(jìn)行過濾和重排序的結(jié)果如下：

二、構(gòu)造fp樹
在對(duì)事務(wù)記錄過濾和排序之后，就可以構(gòu)建FP樹了。從根節(jié)點(diǎn)?開始，將過濾并排序后的樣本一個(gè)個(gè)加入樹中，若FP樹不存在現(xiàn)有元素則添加分支，若存在則增加相應(yīng)的值。如果現(xiàn)有元素不存在，則向樹添加一個(gè)分支。下圖給出了從根節(jié)點(diǎn)?開始依次添加三個(gè)樣本（過濾且排序）后FP的情況。

那么對(duì)于單個(gè)樣本，F(xiàn)P樹應(yīng)該怎么生長(zhǎng)呢？自然而然地想到遞歸。因?yàn)槊總€(gè)樣本都是排序過的，頻數(shù)高的頻繁項(xiàng)集在前面，它總是更接近根結(jié)點(diǎn)，所以也可以把每個(gè)樣本看成一棵子樹，而我們要做的就是把子樹添加到FP樹里。因此每次只需判斷第一個(gè)結(jié)點(diǎn)是否是根的兒子，若是則增加計(jì)數(shù)，若不是則增加分枝，然后遞歸調(diào)用構(gòu)造FP樹，傳入第二個(gè)元素開始的子樹即可。比如上例中往根節(jié)點(diǎn)?增加樣本(z,r)時(shí)，根沒有z這個(gè)兒子，因此增加分支z。接著，只需遞歸地構(gòu)造FP樹，傳入(r)，發(fā)現(xiàn)當(dāng)前FP樹?-z也沒有r這個(gè)兒子，因此增加分支r。最終遞歸返回，引入樣本(z,r)后構(gòu)造的FP樹就是?-z-r。

下圖詳細(xì)地描述了這個(gè)過程，代碼中updateFPtree()函數(shù)實(shí)現(xiàn)了這個(gè)功能。

三、從FP樹提取條件模式基
條件模式基（conditional pattern base）定義為以所查找元素為結(jié)尾的所有前綴路徑（prefix path）的集合。我們要做的就是從header列表開始，針對(duì)每一個(gè)頻繁項(xiàng)，都查找其對(duì)應(yīng)的條件模式基。舉個(gè)例子，如下圖所示，元素"r"的前綴路徑是{z}、{z,x,y}和{x,s}。同時(shí)，每一個(gè)路徑要與起始元素的計(jì)數(shù)值關(guān)聯(lián)，該計(jì)數(shù)值等于起始元素項(xiàng)的計(jì)數(shù)值，該計(jì)數(shù)值給了每條路徑上r的數(shù)目。

四、創(chuàng)建條件FP樹
對(duì)每一個(gè)頻繁項(xiàng)，都建立一棵條件FP樹。上面我們對(duì)每一個(gè)頻繁項(xiàng)提取了條件模式基，現(xiàn)在就用它作為輸入數(shù)據(jù)，即把每一個(gè)前綴路徑當(dāng)成一個(gè)樣本，調(diào)用createFPtree()構(gòu)造一棵FP樹，即條件FP樹。然后，對(duì)這個(gè)條件FP樹，遞歸地挖掘。由于createFPtree()中含有過濾的功能，因此最終總能獲得所有滿足最小支持度的頻繁項(xiàng)，即我們所需要的頻繁項(xiàng)集。

重復(fù)進(jìn)行，直到條件數(shù)中沒有元素為止。

五、實(shí)例(上述的Python實(shí)現(xiàn)）
導(dǎo)入數(shù)據(jù)庫中的數(shù)據(jù)

import fpGrowth
simpDat=fpGrowth.loadSimpDat()
simpDat

為了createTree函數(shù)，對(duì)上面數(shù)據(jù)進(jìn)行格式化處理

initSet = fpGrowth.createInitSet(simDat)
initSet

創(chuàng)建FP樹

myFPtree, myHeaderTab = fpGrowth.createTree(initSet, 3)

給出樹的文本表示結(jié)果

myFPtree.disp()

提取條件模式基

fpGrowth.findPrefixPath('z', myHeaderTab['z'][1]),fpGrowth.findPrefixPath('r', myHeaderTab['r'][1]),fpGrowth.findPrefixPath('x', myHeaderTab['x'][1])

生成條件樹

freqItems = [] #建立空列表，存儲(chǔ)所有頻繁項(xiàng)集
fpGrowth.mineTree(myFPtree, myHeaderTab, 3, set([]), freqItems)

檢查一下返回的項(xiàng)集是否與條件樹相匹配

freqItems

顯示相匹配