FP-growth算法將數(shù)據(jù)集存儲在一個特定的稱作FP樹的結(jié)構(gòu)之后發(fā)現(xiàn)頻繁項集或者頻繁項集對椅亚，即常在一起出現(xiàn)的元素項的集合FP樹遇八。這種做法使得算法的執(zhí)行速度要快于Apriori算法雷蹂，性能要好兩個數(shù)量級以上。
FP-growth算法只需要對數(shù)據(jù)集記性兩次掃描就能判定給定模式是否頻繁朵你，當數(shù)據(jù)庫特別大時其優(yōu)勢越明顯崭添。但是這種算法不能用來發(fā)現(xiàn)關(guān)聯(lián)規(guī)則。它發(fā)現(xiàn)頻繁項集的過程：（1）構(gòu)建FP樹（2）從FP樹中挖掘頻繁項集吭历。
12.1? FP樹：用于編碼數(shù)據(jù)集的有效方式
FP-growth算法將數(shù)據(jù)存儲在一種稱為FP樹的緊湊數(shù)據(jù)結(jié)構(gòu)中堕仔。FP代表頻繁模式（Frequent Pattern）。
同搜索樹不同的是晌区，一個元素項可以在一棵FP樹中多次出現(xiàn)摩骨。FP樹會存儲項集的出現(xiàn)頻率，而每個項集會以路徑的方式存儲在樹中朗若。存在相似元素的集合會共享樹的一部分恼五。只有當集合之間完全不同時，樹才會分叉哭懈。樹節(jié)點上給出集合中單個元素及其在序列中出現(xiàn)的次數(shù)灾馒，路徑會給出該序列的出現(xiàn)次數(shù)。相似項之間的鏈接叫做節(jié)點鏈接遣总，用于快速發(fā)現(xiàn)相似項的位置睬罗。
FP-growth算法工作流程如下：首先構(gòu)建FP樹，然后利用它來挖掘頻繁項集旭斥。為構(gòu)建FP樹容达，需要對原始數(shù)據(jù)集掃描兩遍。第一遍對所有元素項的出現(xiàn)次數(shù)進行統(tǒng)計垂券，如果某元素是不頻繁的花盐，那么它的超集也是不頻繁的。數(shù)據(jù)庫第一遍掃描用來統(tǒng)計出現(xiàn)的頻率圆米，第二遍掃描中只考慮那些頻繁的元素卒暂。
12.2? 構(gòu)建FP樹
12.2.1? 創(chuàng)建FP樹的數(shù)據(jù)結(jié)構(gòu)
12.2.2? 構(gòu)建FP樹
這里使用一個字典作為數(shù)據(jù)結(jié)構(gòu)，來保存頭指針表娄帖。除了存放指針外也祠，頭指針表還可以用來保存FP樹中每個元素是總數(shù)。
第一次遍歷數(shù)據(jù)集會獲得每個元素項的出現(xiàn)頻率近速。接下來诈嘿，去掉不滿足最小支持度的元素項。在下一步構(gòu)建FP樹削葱。在構(gòu)建時奖亚，讀入每個項集并將其添加到一條已經(jīng)存在的路徑中。如果該路徑不存在析砸，則創(chuàng)建一條新路徑昔字。每個事務(wù)都是一個無序集合。在將集合添加到樹之前，需要對每個集合排序作郭。排序基于元素項的絕對出現(xiàn)頻率進行陨囊。在對事務(wù)記錄過濾和排序之后，就可以侯建FP樹了夹攒。從空集開始蜘醋，向其中不斷添加頻繁項集。過濾咏尝、排序后的事務(wù)依次添加到樹中压语。如果樹中已存在現(xiàn)有元素，則增加現(xiàn)有元素的值编检。如果現(xiàn)有元素不存在胎食，則向樹添加一個分枝。
上面給的是元素項及其對應的頻率計數(shù)值允懂，其中每個縮進表示所處的樹的深度斥季。
12.3? 從一棵FP樹中挖掘頻繁項集
有了FP樹之后，就可以抽取頻繁項集了累驮。首先從單元素項集合開始，然后在此基礎(chǔ)上逐步構(gòu)建更大的集合舵揭。
從FP樹中抽取頻繁項集的三個基本步驟：（1）從FP樹中獲得條件模式基谤专；（2）利用條件模式基，構(gòu)建一個條件FP樹午绳；（3）迭代重復步驟1和2 置侍，直到樹包含一個元素項為止。
我們重點關(guān)注步驟（1）拦焚，即尋找條件模式基蜡坊。之后，為每一個條件模式基創(chuàng)建對應的條件FP樹赎败。最后構(gòu)造少許代碼封裝上述兩個函數(shù)秕衙，并從FP樹中獲得頻繁項集。
12.3.1? 抽取條件模式基
首先從上一節(jié)發(fā)現(xiàn)的已經(jīng)保存在頭指針表中的單個頻繁元素項開始僵刮。對于每一個元素項据忘，獲得其對應的條件模式基（conditional pattern base）。條件模式基是以所查找元素項為結(jié)尾的路徑集合搞糕。每一條路徑其實都是一條前綴路徑（prefix path）勇吊。簡而言之，一條前綴路徑是介于所查找元素項與根節(jié)點之間的所有內(nèi)容窍仰。
每一條前綴路徑都與一個計數(shù)值關(guān)聯(lián)汉规。前綴路徑將用于構(gòu)建條件FP樹。為了獲得這些前綴路徑驹吮，可以對樹進行窮舉式搜索针史，直到獲得想要的頻繁項為止晶伦，或者使用一個更有效的方法來加速搜索過程∥蛎瘢可以利用先前創(chuàng)建的頭指針表來得到一種更有效的方法坝辫。頭指針表包含相同類型元素鏈表的起始指針。一旦到達了每一個元素項射亏，就可以上溯這棵樹直到根節(jié)點為止近忙。
有了條件模式基，就可以創(chuàng)建條件FP樹智润。
12.3.2? 創(chuàng)建條件FP樹
對每個頻繁項及舍，都要創(chuàng)建一棵條件FP樹。我們可以使用剛才發(fā)現(xiàn)的條件模式基作為輸入數(shù)據(jù)窟绷，并通過相同的建樹代碼來構(gòu)架這些樹锯玛。然后，我們會遞歸地發(fā)現(xiàn)頻繁項兼蜈、發(fā)現(xiàn)條件模式基攘残，以及發(fā)現(xiàn)另外的條件樹。
12.4? 本章小結(jié)
FP-growth算法是一種用于發(fā)現(xiàn)數(shù)據(jù)集中頻繁模式的有效方法为狸。FP-growth算法利用Apriori算法的原則歼郭，但只對數(shù)據(jù)集掃描兩次，執(zhí)行更快辐棒。在FP-growth算法中病曾，數(shù)據(jù)集存儲在一個稱為FP樹的結(jié)構(gòu)中。FP樹構(gòu)建完成后漾根，可以通過查找元素項的條件基及構(gòu)建條件樹來發(fā)現(xiàn)頻繁項集泰涂。該過程不斷以更多元素作為條件重復進行，直到FP樹中只包含一個元素為止辐怕。
使用FP-growth算法可以在多種文本文檔中查找頻繁單詞逼蒙，本文沒有實踐和記錄實例。
