《機器學習實戰》使用Apriori算法和FP-growth算法進行關聯分析（Python版）一：關聯分析二：Apriori算法和FP-growth算法原理三：使用Apriori算法發現頻繁項集和挖掘相關規則四：使用FP-growth高效發現頻繁項集五：執行個體：從新聞站點點選流中挖掘新聞報道

=====================================================================

《機器學習實戰》系列部落格是部落客閱讀《機器學習實戰》這本書的筆記也包含一些其他python實作的機器學習算法

算法實作均采用python

1：關聯分析

2：Apriori算法和FP-growth算法原理

3：使用Apriori算法發現頻繁項集

4：使用FP-growth高效發現頻繁項集

5：執行個體：從新聞站點點選流中挖掘新聞報道

關聯分析（association analysis）：從大規模資料集中尋找商品的隐含關系

項集（itemset）：包含0個或者多個項的集合稱為項集

頻繁項集：那些經常一起出現的物品集合

支援度計數（support count）：一個項集出現的次數也就是整個交易資料集中包含該項集的事物數

關聯規則是形如A->B的表達式，規則A->B的度量包括支援度和置信度

項集支援度：一個項集出現的次數與資料集所有事物數的百分比稱為項集的支援度

eg：support(A->B)=support_count(A并B) / N

項集置信度（confidence）：資料集中同時包含A，B的百分比

eg：confidence(A->B) = support_count(A并B) / support_count(A)

(1)：購物籃分析，通過檢視那些商品經常在一起出售，可以幫助商店了解使用者的購物行為，這種從資料的海洋中抽取隻是可以用于商品定價、市場促銷、存貨管理等環節

(2)：在Twitter源中發現一些公共詞。對于給定的搜尋詞，發現推文中頻繁出現的單詞集合

(3)：從新聞網站點選流中挖掘新聞流行趨勢，挖掘哪些新聞廣泛被使用者浏覽到

(4)：搜尋引擎推薦，在使用者輸入查詢時推薦同時相關的查詢詞項

(5)：發現毒蘑菇的相似特征。這裡隻對包含某個特征元素（有毒素）的項集感興趣，從中尋找毒蘑菇中的一些公共特征，利用這些特征來避免遲到哪些有毒的蘑菇

交易号碼

商品

100

Cola，Egg，Ham

200

Cola，Diaper，Beer

300

Cola，Diaper，Beer，Ham

400

Diaper，Beer

找出所有可能是頻繁項集的項集，即候選項集，然後根據最小支援度計數删選出頻繁項集，最簡單的辦法是窮舉法，即把每個項集都作為候選項集，統計他在資料集中出現的次數，如果出現次數大于最小支援度計數，則為頻繁項集。

《機器學習實戰》使用Apriori算法和FP-growth算法進行關聯分析（Python版）一：關聯分析二：Apriori算法和FP-growth算法原理三：使用Apriori算法發現頻繁項集和挖掘相關規則四：使用FP-growth高效發現頻繁項集五：執行個體：從新聞站點點選流中挖掘新聞報道

所有的可能的項集（E：Egg C：Cola D：Diaper B：Beer H：Ham）

頻繁項集的發現過程如下（假定給定的最小支援度為2）：

頻繁項集的發現過程

經過剪枝後的圖為（紅色圓圈内即為剪枝去掉的部分）：

剪枝後的候選集為（E：Egg C：Cola D：Diaper B：Beer H：Ham）

那麼CD，CB，CH，DB，DH，BH，DBH即為所求的候選集

FP-growth算法不同于Apriori算法生成候選項集再檢查是否頻繁的”産生-測試“方法，而是使用一種稱為頻繁模式樹（FP-Tree，PF代表頻繁模式，Frequent Pattern）菜單緊湊資料結構組織資料，并直接從該結構中提取頻繁項集，下面針對

FP-growth算法分為兩個過程，一是根據原始資料構造FP-Tree，二是在FP-Tree上挖掘頻繁模式

做出FP-Tree，頻繁模式樹的挖掘形成過程

首先掃描一遍資料集，找出頻繁項的清單L，按照他們的支援度計數遞減排序，即 L = <（Cola：3），（Diaper：3），（Beer：3），（Ham：2）>

再次掃描資料庫，利用每個事物中的頻繁項構造FP-Tree，FP-Tree的根節點為null，處理每個事物時按照L中的順序将事物中出現的頻繁項添加到中的一個分支

例如，第一個事物建立一個分支<（Cola：1），（Ham：1）>，第二個事物中包含頻繁項排序後為<（Cola，Diaper，Beer）>，與樹中的分支共享字首（Cola），是以将樹中的節點Cola的計數分别加一，在Cola節點建立分支<（Diaper：1），（Beer：1）>，依次類推，将資料集中的事物都添加到FP-Tree中，為便于周遊樹，建立一個頭節點表，使得每個項通過一個節點鍊指向他在樹中的出現，相同的鍊在一個連結清單中，構造好的FP-Tree樹如下圖：

根據上表構造的FP-Tree

在FP-Tree上挖掘頻繁模式：

挖掘FP-Tree采用自低向上的疊代模式，首先查找以”Ham“為字尾的頻繁項集，然後依次是”Beer“，”Diaper“，”Cola“

查找以”Ham“為字尾的頻繁項集，首先在FP-Tree中找出所有包含”Ham“的記錄，利用頭節點表和樹節點的連結，找出包含”Ham“的兩個分支，<Cola：3，Ham：1>和<（Cola：3，Diaper：2，Beer：1，Ham：1）>，說明在該FP-Tree所代表的資料集中記錄（Cola，Ham）和（Cola，Diaper，Beer，Ham）各出現了一次，利用這兩個分支所代表的記錄構造”Ham“的條件模式基。條件模式基可以看作是一個“子資料集”，由FP-Tree中與字尾模式一起出現的字首路徑組成，Ham作為字尾模式時，”Ham“的兩個字首路徑{（Cola：1），（Cola

Diaper Beer：1）}構成了”Ham“的條件模式基。利用”Ham“的條件模式基構造FP-TRee，即“Ham”的條件FP樹。“Ham ”的條件模式基中，Cola出現了2次，Diaper，Beer隻出現了1次，是以Diaper，Beer是非頻繁項，不包含在“Ham”的條件模式樹中，“Ham”的條件模式樹隻有一個分支<Cola：2>，得到條件頻繁項集{Cola：2}，條件頻繁項集與字尾模式“Ham“合并，得到頻繁項集{Cola

Ham ：2}

同理查找”Beer“為字尾的頻繁項集，得到{ {Diaper Beer ：3} ， {Cola Diaper Beer：2}， {Cola Beer：2} }

查找”Diaper“為結尾的頻繁項集，得到 {Cola Diaper ：2}

Apriori算法是發現頻繁項集的一種方法。Apriori算法的兩個輸入參數分别是最小支援度和資料集。該算法首先會生成所有單個元素的項集清單。接着掃描資料集來檢視哪些項集滿足最小支援度要求，那些不滿足最小支援度的集合會被去掉。然後，對剩下來的集合進行組合以生成包含兩個元素的項集。接下來，再重新掃描交易記錄，去掉不滿足最小支援度的項集。該過程重複進行直到所有項集都被去掉，建立

Apriori.py檔案，加入以下代碼

#-*-coding:utf-8-*-

'''

Created on 2016年5月8日

@author: Gamer Think

from pydoc import apropos

#========================= 準備函數（下） ==========================================

#加載資料集

def loadDataSet():

return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]

def createC1(dataSet):

C1 = [] #C1為大小為1的項的集合

for transaction in dataSet: #周遊資料集中的每一條交易

for item in transaction: #周遊每一條交易中的每個商品

if not [item] in C1:

C1.append([item])

C1.sort()

#map函數表示周遊C1中的每一個元素執行forzenset，frozenset表示“冰凍”的集合，即不可改變

return map(frozenset,C1)

#Ck表示資料集，D表示候選集合的清單，minSupport表示最小支援度

#該函數用于從C1生成L1，L1表示滿足最低支援度的元素集合

def scanD(D,Ck,minSupport):

ssCnt = {}

for tid in D:

for can in Ck:

#issubset：表示如果集合can中的每一進制素都在tid中則傳回true

if can.issubset(tid):

#統計各個集合scan出現的次數，存入ssCnt字典中，字典的key是集合，value是統計出現的次數

if not ssCnt.has_key(can):

ssCnt[can] = 1

else:

ssCnt[can] += 1

numItems = float(len(D))

retList = []

supportData = {}

for key in ssCnt:

#計算每個項集的支援度，如果滿足條件則把該項集加入到retList清單中

support = ssCnt[key]/numItems

if support >= minSupport:

retList.insert(0, key)

#建構支援的項集的字典

supportData[key] = support

return retList,supportData

#==================== 準備函數（上） =============================

#====================== Apriori算法（下） =================================

#Create Ck,CaprioriGen ()的輸人參數為頻繁項集清單Lk與項集元素個數k，輸出為Ck

def aprioriGen(Lk,k):

lenLk = len(Lk)

for i in range(lenLk):

for j in range(i+1,lenLk):

#前k-2項相同時合并兩個集合

L1 = list(Lk[i])[:k-2]

L2 = list(Lk[j])[:k-2]

L1.sort()

L2.sort()

if L1 == L2:

retList.append(Lk[i] | Lk[j])

return retList

def apriori(dataSet, minSupport=0.5):

C1 = createC1(dataSet) #建立C1

#D: [set([1, 3, 4]), set([2, 3, 5]), set([1, 2, 3, 5]), set([2, 5])]

D = map(set,dataSet)

L1,supportData = scanD(D, C1, minSupport)

L = [L1]

#若兩個項集的長度為k - 1,則必須前k-2項相同才可連接配接，即求并集，是以[:k-2]的實際作用為取清單的前k-1個元素

k = 2

while(len(L[k-2]) > 0):

Ck = aprioriGen(L[k-2], k)

Lk,supK = scanD(D,Ck, minSupport)

supportData.update(supK)

L.append(Lk)

k +=1

return L,supportData

#====================== Apriori算法(上) =================================

if __name__=="__main__":

dataSet = loadDataSet()

L,suppData = apriori(dataSet)

i = 0

for one in L:

print "項數為 %s 的頻繁項集：" % (i + 1), one,"\n"

i +=1

運作上邊代碼的輸出結果是：

要找到關聯規則，我們首先從一個頻繁項集開始。從文章開始說的那個交易資料表的例子可以得到，如果有一個頻繁項集{Diaper，Beer}，那麼就可能有一條關聯規則“DiaperBeer”。這意味着如果有人購買了Diaper，那麼在統計上他會購買Beer的機率較大。注意這一條反過來并不總是成立，也就是說，可信度(“DiaperBeer”)并不等于可信度(“BeerDiaper”)。

前文也提到過，一條規則PH的可信度定義為support(P 并 H)/support(P)。可見可信度的計算是基于項集的支援度的。

下圖給出了從項集{0,1,2,3}産生的所有關聯規則，其中陰影區域給出的是低可信度的規則。可以發現如果{0,1,2}{3}是一條低可信度規則，那麼所有其他以3作為後件（箭頭右部包含3）的規則均為低可信度的。

頻繁項集{0,1,2,3}的關聯規則網格示意圖

可以觀察到，如果某條規則并不滿足最小可信度要求，那麼該規則的所有子集也不會滿足最小可信度要求。以圖4為例，假設規則{0,1,2} {3}并不滿足最小可信度要求，那麼就知道任何左部為{0,1,2}子集的規則也不會滿足最小可信度要求。可以利用關聯規則的上述性質屬性來減少需要測試的規則數目，類似于Apriori算法求解頻繁項集。

下面我們看一下書中的源代碼是怎麼寫

關聯規則生成函數：

<code>def generateRules(L, supportData, minConf=0.7):</code>

<code> </code><code>bigRuleList = []</code>

<code> </code><code>for</code> <code>i </code><code>in</code> <code>range(1, len(L)):</code>

<code> </code><code>for</code> <code>freqSet </code><code>in</code> <code>L[i]:</code>

<code> </code><code>H1 = [frozenset([item]) </code><code>for</code> <code>item </code><code>in</code> <code>freqSet]</code>

<code> </code><code># 三個及以上元素的集合</code>

<code> </code><code>rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)</code>

<code> </code><code># 兩個元素的集合</code>

<code> </code><code>calcConf(freqSet, H1, supportData, bigRuleList, minConf)</code>

<code> </code><code>return</code> <code>bigRuleList</code>

這個函數是主函數，調用其他兩個函數。其他兩個函數是rulesFromConseq()和calcConf()，分别用于生成候選規則集合以及對規則進行評估（計算支援度）。

函數generateRules()有3個參數：頻繁項集清單L、包含那些頻繁項集支援資料的字典supportData、最小可信度門檻值minConf。函數最後要生成一個包含可信度的規則清單bigRuleList，後面可以基于可信度對它們進行排序。L和supportData正好為函數apriori()的輸出。該函數周遊L中的每一個頻繁項集，并對每個頻繁項集建構隻包含單個元素集合的清單H1。代碼中的i訓示目前周遊的頻繁項集包含的元素個數，freqSet為目前周遊的頻繁項集（回憶L的組織結構是先把具有相同元素個數的頻繁項集組織成清單，再将各個清單組成一個大清單，是以為周遊L中的頻繁項集，需要使用兩層for循環）。

輔助函數——計算規則的可信度，并過濾出滿足最小可信度要求的規則

<code>def</code> <code>calcConf(freqSet, H, supportData, brl, minConf</code><code>=</code><code>0.7</code><code>):</code>

<code> </code><code>''' 對候選規則集進行評估 '''</code>

<code> </code><code>prunedH </code><code>=</code> <code>[]</code>

<code> </code><code>for</code> <code>conseq </code><code>in</code> <code>H:</code>

<code> </code><code>conf </code><code>=</code> <code>supportData[freqSet] </code><code>/</code> <code>supportData[freqSet </code><code>-</code> <code>conseq]</code>

<code> </code><code>if</code> <code>conf ></code><code>=</code> <code>minConf:</code>

<code> </code><code>print</code> <code>freqSet </code><code>-</code> <code>conseq, </code><code>'-->'</code><code>, conseq, </code><code>'conf:'</code><code>, conf</code>

<code> </code><code>brl.append((freqSet </code><code>-</code> <code>conseq, conseq, conf))</code>

<code> </code><code>prunedH.append(conseq)</code>

<code> </code><code>return</code> <code>prunedH</code>

計算規則的可信度以及找出滿足最小可信度要求的規則。函數傳回一個滿足最小可信度要求的規則清單，并将這個規則清單添加到主函數的bigRuleList中（通過參數brl）。傳回值prunedH儲存規則清單的右部，這個值将在下一個函數rulesFromConseq()中用到。

輔助函數——根據目前候選規則集H生成下一層候選規則集

<code>def</code> <code>rulesFromConseq(freqSet, H, supportData, brl, minConf</code><code>=</code><code>0.7</code><code>):</code>

<code> </code><code>''' 生成候選規則集 '''</code>

<code> </code><code>if</code> <code>(</code><code>len</code><code>(freqSet) > (m </code><code>+</code> <code>1</code><code>)):</code>

<code> </code><code>Hmpl </code><code>=</code> <code>aprioriGen(H, m </code><code>+</code> <code>1</code><code>)</code>

<code> </code><code>Hmpl </code><code>=</code> <code>calcConf(freqSet, Hmpl, supportData, brl, minConf)</code>

<code> </code><code>rulesFromConseq(freqSet, Hmpl, supportData, brl, minConf)</code>

從最初的項集中生成更多的關聯規則。該函數有兩個參數：頻繁項集freqSet，可以出現在規則右部的元素清單H。其餘參數：supportData儲存項集的支援度，brl儲存生成的關聯規則，minConf同主函數。函數先計算H中的頻繁項集大小m。接下來檢視該頻繁項集是否大到可以移除大小為m的子集。如果可以的話，則将其移除。使用函數aprioriGen()來生成H中元素的無重複組合，結果儲存在Hmp1中，這也是下一次疊代的H清單。

将上邊的三個函數加入 Apriori.py中

main函數修改為：

print "minConf=0.7時："

rules = generateRules(L,suppData, minConf=0.7)

print "\nminConf=0.5時："

rules = generateRules(L,suppData, minConf=0.5)

運作結果如下：

關于rulesFromConseq()函數的問題

如果仔細看下上述代碼和輸出，會發現這裡面是一些問題的。

頻繁項集L的值前面提到過。我們在其中計算通過{2, 3, 5}生成的關聯規則，可以發現關聯規則{3, 5}{2}和{2, 3}{5}的可信度都應該為1.0的，因而也應該包括在當minConf = 0.7時的rules中——但是這在前面的運作結果中并沒有展現出來。minConf = 0.5時也是一樣，{3, 5}{2}的可信度為1.0，{2,

5}{3}的可信度為2/3，{2, 3}{5}的可信度為1.0，也沒有展現在rules中。

通過分析程式代碼，我們可以發現：

當i = 1時，generateRules()函數直接調用了calcConf()函數直接計算其可信度，因為這時L[1]中的頻繁項集均包含兩個元素，可以直接生成和判斷候選關聯規則。比如L[1]中的{2, 3}，生成的候選關聯規則為{2}{3}、{3}{2}，這樣就可以了。

當i > 1時，generateRules()函數調用了rulesFromConseq()函數，這時L[i]中至少包含3個元素，如{2, 3, 5}，對候選關聯規則的生成和判斷的過程需要分層進行（圖4）。這裡，将初始的H1（表示初始關聯規則的右部，即箭頭右邊的部分）作為參數傳遞給了rulesFromConseq()函數。

例如，對于頻繁項集{a, b, c, …}，H1的值為[a, b, c, …]（代碼中實際為frozenset類型）。如果将H1帶入計算可信度的calcConf()函數，在函數中會依次計算關聯規則{b, c, d, …}{a}、{a, c, d, …}{b}、{a, b, d, …}{c}……的支援度，并儲存支援度大于最小支援度的關聯規則，并儲存這些規則的右部（prunedH，即對H的過濾，删除支援度過小的關聯規則）。

當i > 1時沒有直接調用calcConf()函數計算通過H1生成的規則集。在rulesFromConseq()函數中，首先獲得目前H的元素數m = len(H[0])（記目前的H為Hm ）。當Hm可以進一步合并為m+1元素數的集合Hm+1時（判斷條件：len(freqSet)

> (m + 1)），依次：

生成Hm+1：Hmpl

= aprioriGen(H, m + 1)

計算Hm+1的可信度：Hmpl

= calcConf(freqSet, Hmpl, …)

遞歸計算由Hm+1生成的關聯規則：rulesFromConseq(freqSet,

Hmpl, …)

是以這裡的問題是，在i>1時，rulesFromConseq()函數中并沒有調用calcConf()函數計算H1的可信度，而是直接由H1生成H2，從H2開始計算關聯規則——于是由元素數>3的頻繁項集生成的{a, b, c, …}{x}形式的關聯規則（圖4中的第2層）均缺失了。由于代碼示例資料中的對H1的剪枝prunedH沒有删除任何元素，結果隻是“巧合”地缺失了一層。正常情況下如果沒有對H1進行過濾，直接生成H2，将給下一層帶入錯誤的結果（如圖4中的0123會被錯誤得留下來）。

在i>1時，将對H1調用calcConf()的過程加上就可以了。比如可以這樣：

<code>def</code> <code>generateRules2(L, supportData, minConf</code><code>=</code><code>0.7</code><code>):</code>

<code> </code><code>bigRuleList </code><code>=</code> <code>[]</code>

<code> </code><code>for</code> <code>i </code><code>in</code> <code>range</code><code>(</code><code>1</code><code>, </code><code>len</code><code>(L)):</code>

<code> </code><code>H1 </code><code>=</code> <code>[</code><code>frozenset</code><code>([item]) </code><code>for</code> <code>item </code><code>in</code> <code>freqSet]</code>

<code> </code><code>H1 </code><code>=</code> <code>calcConf(freqSet, H1, supportData, bigRuleList, minConf)</code>

這裡就隻需要修改generateRules()函數。這樣實際運作效果中，剛才丢失的那幾個關聯規則就都出來了。

進一步修改：當i=1時的else部分并沒有獨特的邏輯，這個if語句可以合并，然後再修改rulesFromConseq()函數，保證其會調用calcConf(freqSet, H1, …)：

<code>def</code> <code>generateRules3(L, supportData, minConf</code><code>=</code><code>0.7</code><code>):</code>

<code> </code><code>rulesFromConseq2(freqSet, H1, supportData, bigRuleList, minConf)</code>

<code>def</code> <code>rulesFromConseq2(freqSet, H, supportData, brl, minConf</code><code>=</code><code>0.7</code><code>):</code>

<code> </code><code>if</code> <code>(</code><code>len</code><code>(freqSet) > m): </code><code># 判斷長度改為 > m，這時即可以求H的可信度</code>

<code> </code><code>Hmpl </code><code>=</code> <code>calcConf(freqSet, H, supportData, brl, minConf)</code>

<code> </code><code>if</code> <code>(</code><code>len</code><code>(Hmpl) > </code><code>1</code><code>): </code><code># 判斷求完可信度後是否還有可信度大于門檻值的項用來生成下一層H</code>

<code> </code><code>Hmpl </code><code>=</code> <code>aprioriGen(Hmpl, m </code><code>+</code> <code>1</code><code>)</code>

<code> </code><code>rulesFromConseq2(freqSet, Hmpl, supportData, brl, minConf) </code><code># 遞歸計算，不變</code>

運作結果和generateRules2相同。

進一步修改：消除rulesFromConseq2()函數中的遞歸項。這個遞歸純粹是偷懶的結果，沒有簡化任何邏輯和增加任何可讀性，可以直接用一個循環代替：

<code>def</code> <code>rulesFromConseq3(freqSet, H, supportData, brl, minConf</code><code>=</code><code>0.7</code><code>):</code>

<code> </code><code>while</code> <code>(</code><code>len</code><code>(freqSet) > m): </code><code># 判斷長度 > m，這時即可求H的可信度</code>

<code> </code><code>H </code><code>=</code> <code>calcConf(freqSet, H, supportData, brl, minConf)</code>

<code> </code><code>if</code> <code>(</code><code>len</code><code>(H) > </code><code>1</code><code>): </code><code># 判斷求完可信度後是否還有可信度大于門檻值的項用來生成下一層H</code>

<code> </code><code>H </code><code>=</code> <code>aprioriGen(H, m </code><code>+</code> <code>1</code><code>)</code>

<code> </code><code>else</code><code>: </code><code># 不能繼續生成下一層候選關聯規則，提前退出循環</code>

<code> </code><code>break</code>

另一個主要的差別是去掉了多餘的Hmpl變量。運作的結果和generateRules2相同。

此為修改後的運作結果：

至此，一個完整的Apriori算法就完成了。

關聯分析是用于發現大資料集中元素間有趣關系的一個工具集，可以采用兩種方式來量化這些有趣的關系。第一種方式是使用頻繁項集，它會給出經常在一起出現的元素項。第二種方式是關聯規則，每條關聯規則意味着元素項之間的“如果……那麼”關系。

發現元素項間不同的組合是個十分耗時的任務，不可避免需要大量昂貴的計算資源，這就需要一些更智能的方法在合理的時間範圍内找到頻繁項集。能夠實作這一目标的一個方法是Apriori算法，它使用Apriori原理來減少在資料庫上進行檢查的集合的數目。Apriori原理是說如果一個元素項是不頻繁的，那麼那些包含該元素的超集也是不頻繁的。Apriori算法從單元素項集開始，通過組合滿足最小支援度要求的項集來形成更大的集合。支援度用來度量一個集合在原始資料中出現的頻率。

關聯分析可以用在許多不同物品上。商店中的商品以及網站的通路頁面是其中比較常見的例子。

每次增加頻繁項集的大小，Apriori算法都會重新掃描整個資料集。當資料集很大時，這會顯著降低頻繁項集發現的速度。下面會介紹FP-growth算法，和Apriori算法相比，該算法隻需要對資料庫進行兩次周遊，能夠顯著加快發現頻繁項集的速度。

（拿書中的資料舉例）FP-growth算法将資料存儲在一種稱為FP樹的緊湊資料結構中。FP代表頻繁模式（Frequent Pattern）。一棵FP樹看上去與計算機科學中的其他樹結構類似，但是它通過連結（link）來連接配接相似元素，被連起來的元素項可以看成一個連結清單。圖5給出了FP樹的一個例子。

上圖為一棵FP樹，和一般的樹結構類似，包含着連接配接相似節點（值相同的節點）的連接配接

與搜尋樹不同的是，一個元素項可以在一棵FP樹種出現多次。FP樹輝存儲項集的出現頻率，而每個項集會以路徑的方式存儲在數中。存在相似元素的集合會共享樹的一部分。隻有當集合之間完全不同時，樹才會分叉。樹節點上給出集合中的單個元素及其在序列中的出現次數，路徑會給出該序列的出現次數。

相似項之間的連結稱為節點連結（node link），用于快速發現相似項的位置。

舉例說明，下表用來産生圖5的FP樹：

用于生成圖5中FP樹的事務資料樣例

事務ID

事務中的元素項

001

r, z, h, j, p

002

z, y, x, w, v, u, t, s

003

004

r, x, n, o, s

005

y, r, x, z, q, t, p

006

y, z, x, e, q, s, t, m

對FP樹的解讀：

圖5中，元素項z出現了5次，集合{r, z}出現了1次。于是可以得出結論：z一定是自己本身或者和其他符号一起出現了4次。集合{t, s, y, x, z}出現了2次，集合{t, r, y, x, z}出現了1次，z本身單獨出現1次。就像這樣，FP樹的解讀方式是讀取某個節點開始到根節點的路徑。路徑上的元素構成一個頻繁項集，開始節點的值表示這個項集的支援度。根據圖5，我們可以快速讀出項集{z}的支援度為5、項集{t,

s, y, x, z}的支援度為2、項集{r, y, x, z}的支援度為1、項集{r, s, x}的支援度為1。FP樹中會多次出現相同的元素項，也是因為同一個元素項會存在于多條路徑，構成多個頻繁項集。但是頻繁項集的共享路徑是會合并的，如圖中的{t, s, y, x, z}和{t, r, y, x, z}

和之前一樣，我們取一個最小門檻值，出現次數低于最小門檻值的元素項将被直接忽略。圖5中将最小支援度設為3，是以q和p沒有在FP中出現。

FP-growth算法的工作流程如下。首先建構FP樹，然後利用它來挖掘頻繁項集。為建構FP樹，需要對原始資料集掃描兩遍。第一遍對所有元素項的出現次數進行計數。資料庫的第一遍掃描用來統計出現的頻率，而第二遍掃描中隻考慮那些頻繁元素。

由于樹節點的結構比較複雜，我們使用一個類表示。建立檔案fpGrowth.py并加入下列代碼：

<code>class</code> <code>treeNode:</code>

<code> </code><code>def</code> <code>__init__(</code><code>self</code><code>, nameValue, numOccur, parentNode):</code>

<code> </code><code>self</code><code>.name </code><code>=</code> <code>nameValue</code>

<code> </code><code>self</code><code>.count </code><code>=</code> <code>numOccur</code>

<code> </code><code>self</code><code>.nodeLink </code><code>=</code> <code>None</code>

<code> </code><code>self</code><code>.parent </code><code>=</code> <code>parentNode</code>

<code> </code><code>self</code><code>.children </code><code>=</code> <code>{}</code>

<code> </code><code>def</code> <code>inc(</code><code>self</code><code>, numOccur):</code>

<code> </code><code>self</code><code>.count </code><code>+</code><code>=</code> <code>numOccur</code>

<code> </code><code>print</code> <code>' '</code> <code>*</code> <code>ind, </code><code>self</code><code>.name, </code><code>' '</code><code>, </code><code>self</code><code>.count</code>

<code> </code><code>for</code> <code>child </code><code>in</code> <code>self</code><code>.children.values():</code>

<code> </code><code>child.disp(ind </code><code>+</code> <code>1</code><code>)</code>

每個樹節點由五個資料項組成：

name：節點元素名稱，在構造時初始化為給定值

count：出現次數，在構造時初始化為給定值

nodeLink：指向下一個相似節點的指針，預設為None

parent：指向父節點的指針，在構造時初始化為給定值

children：指向子節點的字典，以子節點的元素名稱為鍵，指向子節點的指針為值，初始化為空字典

成員函數：

inc()：增加節點的出現次數值

disp()：輸出節點和子節點的FP樹結構

測試代碼：

<code>>>></code><code>import</code> <code>fpGrowth</code>

<code>>>> rootNode </code><code>=</code> <code>fpGrowth.treeNode(</code><code>'pyramid'</code><code>, </code><code>9</code><code>, </code><code>None</code><code>)</code>

<code>>>> rootNode.children[</code><code>'eye'</code><code>] </code><code>=</code> <code>fpGrowth.treeNode(</code><code>'eye'</code><code>, </code><code>13</code><code>, </code><code>None</code><code>)</code>

<code>>>> rootNode.children[</code><code>'phoenix'</code><code>] </code><code>=</code> <code>fpGrowth.treeNode(</code><code>'phoenix'</code><code>, </code><code>3</code><code>, </code><code>None</code><code>)</code>

<code>>>> rootNode.disp()</code>

頭指針表

FP-growth算法還需要一個稱為頭指針表的資料結構，其實很簡單，就是用來記錄各個元素項的總出現次數的數組，再附帶一個指針指向FP樹中該元素項的第一個節點。這樣每個元素項都構成一條單連結清單。圖示說明：

帶頭指針表的FP樹，頭指針表作為一個起始指針來發現相似元素項

這裡使用Python字典作為資料結構，來儲存頭指針表。以元素項名稱為鍵，儲存出現的總次數和一個指向第一個相似元素項的指針。

第一次周遊資料集會獲得每個元素項的出現頻率，去掉不滿足最小支援度的元素項，生成這個頭指針表。

元素項排序

上文提到過，FP樹會合并相同的頻繁項集（或相同的部分）。是以為判斷兩個項集的相似程度需要對項集中的元素進行排序（不過原因也不僅如此，還有其它好處）。排序基于元素項的絕對出現頻率（總的出現次數）來進行。在第二次周遊資料集時，會讀入每個項集（讀取），去掉不滿足最小支援度的元素項（過濾），然後對元素進行排序（重排序）。

對示例資料集進行過濾和重排序的結果如下：

過濾及重排序後的事務

z, r

z, x, y, s, t

x, s, r

z, x, y, r, t

建構FP樹

在對事務記錄過濾和排序之後，就可以建構FP樹了。從空集開始，将過濾和重排序後的頻繁項集一次添加到樹中。如果樹中已存在現有元素，則增加現有元素的值；如果現有元素不存在，則向樹添加一個分支。對前兩條事務進行添加的過程：

FP樹建構過程示意（添加前兩條事務）

算法：建構FP樹

輸入：資料集、最小值尺度輸出：FP樹、頭指針表 1. 周遊資料集，統計各元素項出現次數，建立頭指針表 2. 移除頭指針表中不滿足最小值尺度的元素項 3. 第二次周遊資料集，建立FP樹。對每個資料集中的項集： 3.1 初始化空FP樹 3.2 對每個項集進行過濾和重排序 3.3 使用這個項集更新FP樹，從FP樹的根節點開始： 3.3.1 如果目前項集的第一個元素項存在于FP樹目前節點的子節點中，則更新這個子節點的計數值 3.3.2 否則，建立新的子節點，更新頭指針表 3.3.3 對目前項集的其餘元素項和目前元素項的對應子節點遞歸3.3的過程

代碼（在fpGrowth.py中加入下面的代碼）：

1：總函數：createTree

<code>def</code> <code>createTree(dataSet, minSup</code><code>=</code><code>1</code><code>):</code>

<code> </code><code>''' 建立FP樹 '''</code>

<code> </code><code># 第一次周遊資料集，建立頭指針表</code>

<code> </code><code>headerTable </code><code>=</code> <code>{}</code>

<code> </code><code>for</code> <code>trans </code><code>in</code> <code>dataSet:</code>

<code> </code><code>for</code> <code>item </code><code>in</code> <code>trans:</code>

<code> </code><code>headerTable[item] </code><code>=</code> <code>headerTable.get(item, </code><code>0</code><code>) </code><code>+</code> <code>dataSet[trans]</code>

<code> </code><code># 移除不滿足最小支援度的元素項</code>

<code> </code><code>for</code> <code>k </code><code>in</code> <code>headerTable.keys():</code>

<code> </code><code>if</code> <code>headerTable[k] < minSup:</code>

<code> </code><code>del</code><code>(headerTable[k])</code>

<code> </code><code>freqItemSet </code><code>=</code> <code>set</code><code>(headerTable.keys())</code>

<code> </code><code>if</code> <code>len</code><code>(freqItemSet) </code><code>=</code><code>=</code> <code>0</code><code>:</code>

<code> </code><code>return</code> <code>None</code><code>, </code><code>None</code>

<code> </code><code># 增加一個資料項，用于存放指向相似元素項指針</code>

<code> </code><code>for</code> <code>k </code><code>in</code> <code>headerTable:</code>

<code> </code><code>headerTable[k] </code><code>=</code> <code>[headerTable[k], </code><code>None</code><code>]</code>

<code> </code><code>retTree </code><code>=</code> <code>treeNode(</code><code>'Null Set'</code><code>, </code><code>1</code><code>, </code><code>None</code><code>) </code><code># 根節點</code>

<code> </code><code># 第二次周遊資料集，建立FP樹</code>

<code> </code><code>for</code> <code>tranSet, count </code><code>in</code> <code>dataSet.items():</code>

<code> </code><code>localD </code><code>=</code> <code>{} </code><code># 對一個項集tranSet，記錄其中每個元素項的全局頻率，用于排序</code>

<code> </code><code>for</code> <code>item </code><code>in</code> <code>tranSet:</code>

<code> </code><code>if</code> <code>item </code><code>in</code> <code>freqItemSet:</code>

<code> </code><code>localD[item] </code><code>=</code> <code>headerTable[item][</code><code>0</code><code>] </code><code># 注意這個[0]，因為之前加過一個資料項</code>

<code> </code><code>if</code> <code>len</code><code>(localD) > </code><code>0</code><code>:</code>

<code> </code><code>orderedItems </code><code>=</code> <code>[v[</code><code>0</code><code>] </code><code>for</code> <code>v </code><code>in</code> <code>sorted</code><code>(localD.items(), key</code><code>=</code><code>lambda</code> <code>p: p[</code><code>1</code><code>], reverse</code><code>=</code><code>True</code><code>)] </code><code># 排序</code>

<code> </code><code>updateTree(orderedItems, retTree, headerTable, count) </code><code># 更新FP樹</code>

<code> </code><code>return</code> <code>retTree, headerTable</code>

（代碼比較寬，大家的顯示器都那麼大，應該沒關系吧……）

需要注意的是，參數中的dataSet的格式比較奇特，不是直覺上得集合的list，而是一個集合的字典，以這個集合為鍵，值部分記錄的是這個集合出現的次數。于是要生成這個dataSet還需要後面的createInitSet()函數輔助。是以代碼中第7行中的dataSet[trans]實際獲得了這個trans集合的出現次數（在本例中均為1），同樣第21行的“for

tranSet, count in dataSet.items():”獲得了tranSet和count分别表示一個項集和該項集的出現次數。——這樣做是為了适應後面在挖掘頻繁項集時生成的條件FP樹。

2：輔助函數：updateTree

<code>def</code> <code>updateTree(items, inTree, headerTable, count):</code>

<code> </code><code>if</code> <code>items[</code><code>0</code><code>] </code><code>in</code> <code>inTree.children:</code>

<code> </code><code># 有該元素項時計數值+1</code>

<code> </code><code>inTree.children[items[</code><code>0</code><code>]].inc(count)</code>

<code> </code><code># 沒有這個元素項時建立一個新節點</code>

<code> </code><code>inTree.children[items[</code><code>0</code><code>]] </code><code>=</code> <code>treeNode(items[</code><code>0</code><code>], count, inTree)</code>

<code> </code><code># 更新頭指針表或前一個相似元素項節點的指針指向新節點</code>

<code> </code><code>if</code> <code>headerTable[items[</code><code>0</code><code>]][</code><code>1</code><code>] </code><code>=</code><code>=</code> <code>None</code><code>:</code>

<code> </code><code>headerTable[items[</code><code>0</code><code>]][</code><code>1</code><code>] </code><code>=</code> <code>inTree.children[items[</code><code>0</code><code>]]</code>

<code> </code><code>updateHeader(headerTable[items[</code><code>0</code><code>]][</code><code>1</code><code>], inTree.children[items[</code><code>0</code><code>]])</code>

<code> </code><code>if</code> <code>len</code><code>(items) > </code><code>1</code><code>:</code>

<code> </code><code># 對剩下的元素項疊代調用updateTree函數</code>

<code> </code><code>updateTree(items[</code><code>1</code><code>::], inTree.children[items[</code><code>0</code><code>]], headerTable, count)</code>

3：輔助函數：updateHeader

<code>def</code> <code>updateHeader(nodeToTest, targetNode):</code>

<code> </code><code>while</code> <code>(nodeToTest.nodeLink !</code><code>=</code> <code>None</code><code>):</code>

<code> </code><code>nodeToTest </code><code>=</code> <code>nodeToTest.nodeLink</code>

<code> </code><code>nodeToTest.nodeLink </code><code>=</code> <code>targetNode</code>

這個函數其實隻做了一件事，就是擷取頭指針表中該元素項對應的單連結清單的尾節點，然後将其指向新節點targetNode。

生成資料集

<code>def</code> <code>loadSimpDat():</code>

<code> </code><code>simpDat </code><code>=</code> <code>[[</code><code>'r'</code><code>, </code><code>'z'</code><code>, </code><code>'h'</code><code>, </code><code>'j'</code><code>, </code><code>'p'</code><code>],</code>

<code> </code><code>return</code> <code>simpDat</code>

<code>def</code> <code>createInitSet(dataSet):</code>

<code> </code><code>retDict </code><code>=</code> <code>{}</code>

<code> </code><code>retDict[</code><code>frozenset</code><code>(trans)] </code><code>=</code> <code>1</code>

<code> </code><code>return</code> <code>retDict</code>

生成的樣例資料同文中用得一樣。這個詭異的輸入格式就是createInitSet()函數中這樣來得。

測試代碼

<code>>>> </code><code>import</code> <code>fpGrowth</code>

<code>>>> simpDat </code><code>=</code> <code>fpGrowth.loadSimpDat()</code>

<code>>>> initSet </code><code>=</code> <code>fpGrowth.createInitSet(simpDat)</code>

<code>>>> myFPtree, myHeaderTab </code><code>=</code> <code>fpGrowth.createTree(initSet, </code><code>3</code><code>)</code>

<code>>>> myFPtree.disp()</code>

結果是這樣的（連字都懶得打了，直接截圖……）：

得到的FP樹也和圖5中的一樣。

從FP樹中抽取頻繁項集的三個基本步驟如下：

從FP樹中獲得條件模式基；

利用條件模式基，建構一個條件FP樹；

疊代重複步驟1步驟2，直到樹包含一個元素項為止。

（什麼鬼……）

首先從頭指針表中的每個頻繁元素項開始，對每個元素項，獲得其對應的條件模式基（conditional pattern base）。條件模式基是以所查找元素項為結尾的路徑集合。每一條路徑其實都是一條字首路徑（prefix

path）。簡而言之，一條字首路徑是介于所查找元素項與樹根節點之間的所有内容。

将圖5重新貼在這裡：

則每一個頻繁元素項的所有字首路徑（條件模式基）為：

頻繁項

字首路徑

{}: 5

{x, s}: 1, {z, x, y}: 1, {z}: 1

{z}: 3, {}: 1

{z, x}: 3

{z, x, y}: 2, {x}: 1

{z, x, y, s}: 2, {z, x, y, r}: 1

發現規律了嗎，z存在于路徑{z}中，是以字首路徑為空，另添加一項該路徑中z節點的計數值5構成其條件模式基；r存在于路徑{r, z}、{r, y, x, z}、{r, s, x}中，分别獲得字首路徑{z}、{y, x, z}、{s, x}，另添加對應路徑中r節點的計數值（均為1）構成r的條件模式基；以此類推。

字首路徑将在下一步中用于建構條件FP樹，暫時先不考慮。如何發現某個頻繁元素項的所在的路徑？利用先前建立的頭指針表和FP樹中的相似元素節點指針，我們已經有了每個元素對應的單連結清單，因而可以直接擷取。

下面的程式給出了建立字首路徑的代碼：

1 主函數：findPrefixPath

<code>def</code> <code>findPrefixPath(basePat, treeNode):</code>

<code> </code><code>''' 建立字首路徑 '''</code>

<code> </code><code>condPats </code><code>=</code> <code>{}</code>

<code> </code><code>while</code> <code>treeNode !</code><code>=</code> <code>None</code><code>:</code>

<code> </code><code>prefixPath </code><code>=</code> <code>[]</code>

<code> </code><code>ascendTree(treeNode, prefixPath)</code>

<code> </code><code>if</code> <code>len</code><code>(prefixPath) > </code><code>1</code><code>:</code>

<code> </code><code>condPats[</code><code>frozenset</code><code>(prefixPath[</code><code>1</code><code>:])] </code><code>=</code> <code>treeNode.count</code>

<code> </code><code>treeNode </code><code>=</code> <code>treeNode.nodeLink</code>

<code> </code><code>return</code> <code>condPats</code>

該函數代碼用于為給定元素項生成一個條件模式基（字首路徑），這通過通路樹中所有包含給定元素項的節點來完成。參數basePet表示輸入的頻繁項，treeNode為目前FP樹種對應的第一個節點（可在函數外部通過headerTable[basePat][1]擷取）。函數傳回值即為條件模式基condPats，用一個字典表示，鍵為字首路徑，值為計數值。

2 輔助函數：ascendTree

<code>def</code> <code>ascendTree(leafNode, prefixPath):</code>

<code> </code><code>if</code> <code>leafNode.parent !</code><code>=</code> <code>None</code><code>:</code>

<code> </code><code>prefixPath.append(leafNode.name)</code>

<code> </code><code>ascendTree(leafNode.parent, prefixPath)</code>

這個函數直接修改prefixPath的值，将目前節點leafNode添加到prefixPath的末尾，然後遞歸添加其父節點。最終結果，prefixPath就是一條從treeNode（包括treeNode）到根節點（不包括根節點）的路徑。在主函數findPrefixPath()中再取prefixPath[1:]，即為treeNode的字首路徑。

<code>>>> fpGrowth.findPrefixPath(</code><code>'x'</code><code>, myHeaderTab[</code><code>'x'</code><code>][</code><code>1</code><code>])</code>

<code>>>> fpGrowth.findPrefixPath(</code><code>'z'</code><code>, myHeaderTab[</code><code>'z'</code><code>][</code><code>1</code><code>])</code>

<code>>>> fpGrowth.findPrefixPath(</code><code>'r'</code><code>, myHeaderTab[</code><code>'r'</code><code>][</code><code>1</code><code>])</code>

輸出結果：

（又是什麼鬼……）

對于每一個頻繁項，都要建立一棵條件FP樹。可以使用剛才發現的條件模式基作為輸入資料，并通過相同的建樹代碼來建構這些樹。例如，對于r，即以“{x, s}: 1, {z, x, y}: 1, {z}: 1”為輸入，調用函數createTree()獲得r的條件FP樹；對于t，輸入是對應的條件模式基“{z, x, y, s}: 2, {z, x,

y, r}: 1”。

代碼（直接調用createTree()函數）：

<code>condPattBases </code><code>=</code> <code>findPrefixPath(basePat, headerTable[basePat][</code><code>1</code><code>])</code>

<code>myCondTree, myHead </code><code>=</code> <code>createTree(condPattBases, minSup)</code>

示例：t的條件FP樹

t的條件FP樹的建立過程

在圖8中，注意到元素項s以及r是條件模式基的一部分，但是它們并不屬于條件FP樹。因為在目前的輸入中，s和r不滿足最小支援度的條件。

有了FP樹和條件FP樹，我們就可以在前兩步的基礎上遞歸得查找頻繁項集。

遞歸的過程是這樣的：

輸入：我們有目前資料集的FP樹（inTree，headerTable） 1. 初始化一個空清單preFix表示字首 2. 初始化一個空清單freqItemList接收生成的頻繁項集（作為輸出） 3. 對headerTable中的每個元素basePat（按計數值由小到大），遞歸： 3.1 記basePat + preFix為目前頻繁項集newFreqSet 3.2 将newFreqSet添加到freqItemList中 3.3 計算t的條件FP樹（myCondTree、myHead） 3.4 當條件FP樹不為空時，繼續下一步；否則退出遞歸 3.4 以myCondTree、myHead為新的輸入，以newFreqSet為新的preFix，外加freqItemList，遞歸這個過程

函數如下：

<code>def</code> <code>mineTree(inTree, headerTable, minSup, preFix, freqItemList):</code>

<code> </code><code>bigL </code><code>=</code> <code>[v[</code><code>0</code><code>] </code><code>for</code> <code>v </code><code>in</code> <code>sorted</code><code>(headerTable.items(), key</code><code>=</code><code>lambda</code> <code>p: p[</code><code>1</code><code>])]</code>

<code> </code><code>for</code> <code>basePat </code><code>in</code> <code>bigL:</code>

<code> </code><code>newFreqSet </code><code>=</code> <code>preFix.copy()</code>

<code> </code><code>newFreqSet.add(basePat)</code>

<code> </code><code>freqItemList.append(newFreqSet)</code>

<code> </code><code>condPattBases </code><code>=</code> <code>findPrefixPath(basePat, headerTable[basePat][</code><code>1</code><code>])</code>

<code> </code><code>myCondTree, myHead </code><code>=</code> <code>createTree(condPattBases, minSup)</code>

<code> </code><code>if</code> <code>myHead !</code><code>=</code> <code>None</code><code>:</code>

<code> </code><code>print</code> <code>'conditional tree for:'</code><code>, newFreqSet</code>

<code> </code><code>myCondTree.disp()</code>

<code> </code><code>mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)</code>

輸入參數：

inTree和headerTable是由createTree()函數生成的資料集的FP樹

minSup表示最小支援度

preFix請傳入一個空集合（set([])），将在函數中用于儲存目前字首

freqItemList請傳入一個空清單（[]），将用來儲存生成的頻繁項集

<code>>>> freqItems </code><code>=</code> <code>[]</code>

<code>>>> fpGrowth.mineTree(myFPtree, myHeaderTab, </code><code>3</code><code>, </code><code>set</code><code>([]), freqItems)</code>

<code>>>> freqItems</code>

[set(['y']), set(['y', 'x']), set(['y', 'z']), set(['y', 'x', 'z']), set(['s']), set(['x', 's']), set(['t']), set(['z', 't']), set(['x', 'z', 't']), set(['y', 'x', 'z', 't']), set(['y', 'z', 't']), set(['x', 't']), set(['y', 'x', 't']), set(['y', 't']), set(['r']), set(['x']), set(['x', 'z']), set(['z'])]

想這一段代碼解釋清楚比較難，因為中間涉及到很多遞歸。直接舉例說明，我們在這裡分解輸入myFPtree和myHeaderTab後，“for basePat in bigL:”一行當basePat為’t’時的過程：

圖9 mineTree函數解構圖（basePat = ‘t’）

圖中紅色加粗的部分即實際添加到freqItemList中的頻繁項集。

至此，完整的FP-growth算法已經可以運作。封裝整個過程如下：

<code>def</code> <code>fpGrowth(dataSet, minSup</code><code>=</code><code>3</code><code>):</code>

<code> </code><code>initSet </code><code>=</code> <code>createInitSet(dataSet)</code>

<code> </code><code>myFPtree, myHeaderTab </code><code>=</code> <code>createTree(initSet, minSup)</code>

<code> </code><code>freqItems </code><code>=</code> <code>[]</code>

<code> </code><code>mineTree(myFPtree, myHeaderTab, minSup, </code><code>set</code><code>([]), freqItems)</code>

<code> </code><code>return</code> <code>freqItems</code>

<code>>>> dataSet </code><code>=</code> <code>fpGrowth.loadSimpDat()</code>

<code>>>> freqItems </code><code>=</code> <code>fpGrowth.fpGrowth(dataSet)</code>

和之前的輸出相同。

FP-growth算法是一種用于發現資料集中頻繁模式的有效方法。FP-growth算法利用Apriori原則，執行更快。Apriori算法産生候選項集，然後掃描資料集來檢查它們是否頻繁。由于隻對資料集掃描兩次，是以FP-growth算法執行更快。在FP-growth算法中，資料集存儲在一個稱為FP樹的結構中。FP樹建構完成後，可以通過查找元素項的條件基及建構條件FP樹來發現頻繁項集。該過程不斷以更多元素作為條件重複進行，直到FP樹隻包含一個元素為止。

FP-growth算法還有一個map-reduce版本的實作，它也很不錯，可以擴充到多台機器上運作。Google使用該算法通過周遊大量文本來發現頻繁共現詞，其做法和我們剛才介紹的例子非常類似（參見擴充閱讀：FP-growth算法）。

首先，将資料集導入到清單：

<code>>>> parsedDat </code><code>=</code> <code>[line.split() </code><code>for</code> <code>line </code><code>in</code> <code>open</code><code>(</code><code>'kosarak.dat'</code><code>).readlines()]</code>

接下來需要對初始集合格式化：

<code>>>> initSet </code><code>=</code> <code>fpGrowth.createInitSet(parsedDat)</code>

然後建構FP樹，并從中尋找那些至少被10萬人浏覽過的新聞報道。

<code>>>> myFPtree, myHeaderTab </code><code>=</code> <code>fpGrowth.createTree(initSet, </code><code>100000</code><code>)</code>

下面建立一個空清單來儲存這些頻繁項集：

<code>>>> myFreqList </code><code>=</code> <code>[]</code>

<code>>>> fpGrowth.mineTree(myFPtree, myHeaderTab, </code><code>100000</code><code>, </code><code>set</code><code>([]), myFreqList)</code>

接下來看下有多少新聞報道或報道集合曾經被10萬或者更多的人浏覽過：

<code>>>> </code><code>len</code><code>(myFreqList)</code>

9

總共有9個。下面看看都是那些：

<code>>>> myFreqList</code>

[set(['1']), set(['1', '6']), set(['3']), set(['11', '3']), set(['11', '3', '6']), set(['3', '6']), set(['11']), set(['11', '6']), set(['6'])]

至此Apriori算法和FP-Tree算法已經講解分析完畢，當然我這裡講的有很多不足的地方，希望大家指正。

繼續閱讀

無元件上傳圖檔到資料庫中，最完整解決方案

【MySQL資料庫】資料庫索引事務1.索引2.事務

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Cloud Studio初體驗

使用 ctypes 進行 Python 和 C 的混合程式設計

【python】【資料處理】畫多元資料分布圖

NOSQL安全攻擊

mybatis_入門程式Mybatis入門

登入plsql 報錯 the account is locked --使用者被鎖

SequoiaDB巨杉資料庫C++驅動概述

【python】netconf協定對接管理裝置

「Python 網絡自動化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 網絡裝置

在python中建立excel并寫入

hdu7108哈希