http://blog.csdn.net/sealyao/article/details/6460578

Apriori算法和FPTree算法都是數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則挖掘算法，處理的都是最簡單的單層單維布爾關(guān)聯(lián)規(guī)則。

Apriori算法

Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。是基于這樣的事實：算法使用頻繁項集性質(zhì)的先驗知識。Apriori使用一種稱作逐層搜索的迭代方法，k-項集用于探索(k+1)-項集。首先，找出頻繁1-項集的集合。該集合記作L₁。L₁用于找頻繁2-項集的集合L₂，而L₂用于找L₃，如此下去，直到不能找到頻繁k-項集。找每個L_k需要一次數(shù)據(jù)庫掃描。

這個算法的思路，簡單的說就是如果集合I不是頻繁項集，那么所有包含集合I的更大的集合也不可能是頻繁項集。

算法原始數(shù)據(jù)如下：

TID	List of item_ID’s
T100 T200 T300 T400 T500 T600 T700 T800 T900	I1,I2,I5 I2,I4 I2,I3 I1,I2,I4 I1,I3 I2,I3 I1,I3 I1,I2,I3,I5 I1,I2,I3

算法的基本過程如下圖：

首先掃描所有事務(wù)，得到1-項集C1，根據(jù)支持度要求濾去不滿足條件項集，得到頻繁1-項集。

下面進行遞歸運算：

已知頻繁k-項集(頻繁1-項集已知)，根據(jù)頻繁k-項集中的項，連接得到所有可能的K+1_項，并進行剪枝（如果該k+1_項集的所有k項子集不都能滿足支持度條件，那么該k+1_項集被剪掉），得到項集，然后濾去該項集中不滿足支持度條件的項得到頻繁k+1-項集。如果得到的項集為空，則算法結(jié)束。

連接的方法：假設(shè)項集中的所有項都是按照相同的順序排列的，那么如果[i]和[j]中的前k-1項都是完全相同的，而第k項不同，則[i]和[j]是可連接的。比如中的{I1,I2}和{I1,I3}就是可連接的，連接之后得到{I1,I2,I3}，但是{I1,I2}和{I2,I3}是不可連接的，否則將導(dǎo)致項集中出現(xiàn)重復(fù)項。

關(guān)于剪枝再舉例說明一下，如在由生成的過程中，列舉得到的3_項集包括{I1,I2,I3},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}，但是由于{I3,I4}和{I4,I5}沒有出現(xiàn)在中，所以{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}被剪枝掉了。

海量數(shù)據(jù)下，Apriori算法的時空復(fù)雜度都不容忽視。

空間復(fù)雜度：如果數(shù)量達到的量級，那么中的候選項將達到的量級。

時間復(fù)雜度：每計算一次就需要掃描一遍數(shù)據(jù)庫。

FP-Tree算法

FPTree算法：在不生成候選項的情況下，完成Apriori算法的功能。

FPTree算法的基本數(shù)據(jù)結(jié)構(gòu)，包含一個一棵FP樹和一個項頭表，每個項通過一個結(jié)點鏈指向它在樹中出現(xiàn)的位置。基本結(jié)構(gòu)如下所示。需要注意的是項頭表需要按照支持度遞減排序，在FPTree中高支持度的節(jié)點只能是低支持度節(jié)點的祖先節(jié)點。

另外還要交代一下FPTree算法中幾個基本的概念：

FP-Tree：就是上面的那棵樹，是把事務(wù)數(shù)據(jù)表中的各個事務(wù)數(shù)據(jù)項按照支持度排序后，把每個事務(wù)中的數(shù)據(jù)項按降序依次插入到一棵以NULL為根結(jié)點的樹中，同時在每個結(jié)點處記錄該結(jié)點出現(xiàn)的支持度。

條件模式基：包含F(xiàn)P-Tree中與后綴模式一起出現(xiàn)的前綴路徑的集合。也就是同一個頻繁項在PF樹中的所有節(jié)點的祖先路徑的集合。比如I3在FP樹中一共出現(xiàn)了3次，其祖先路徑分別是{I2，I1：2(頻度為2)}，{I2：2}和{I1：2}。這3個祖先路徑的集合就是頻繁項I3的條件模式基。

條件樹：將條件模式基按照FP-Tree的構(gòu)造原則形成的一個新的FP-Tree。比如上圖中I3的條件樹就是：

?

1、 構(gòu)造項頭表：掃描數(shù)據(jù)庫一遍，得到頻繁項的集合F和每個頻繁項的支持度。把F按支持度遞降排序，記為L。

2、 構(gòu)造原始FPTree：把數(shù)據(jù)庫中每個事物的頻繁項按照L中的順序進行重排。并按照重排之后的順序把每個事物的每個頻繁項插入以null為根的FPTree中。如果插入時頻繁項節(jié)點已經(jīng)存在了，則把該頻繁項節(jié)點支持度加1；如果該節(jié)點不存在，則創(chuàng)建支持度為1的節(jié)點，并把該節(jié)點鏈接到項頭表中。

3、 調(diào)用FP-growth(Tree，null)開始進行挖掘。偽代碼如下：

procedure FP_growth(Tree, a)

if Tree 含單個路徑P then{

???????? for 路徑P中結(jié)點的每個組合（記作b）

???????? 產(chǎn)生模式b U a，其支持度support = b 中結(jié)點的最小支持度；

} else {

???????? for each a _i 在Tree的頭部(按照支持度由低到高順序進行掃描){

????????????????? 產(chǎn)生一個模式b = a _i U a，其支持度support = a _i .support；

????????????????? 構(gòu)造b的條件模式基，然后構(gòu)造b的條件FP-樹Treeb；

????????????????? if Treeb 不為空 then

??????????????????????????? 調(diào)用 FP_growth (Treeb, b)；

?????????? }

}

FP-growth是整個算法的核心，再多啰嗦幾句。

FP-growth函數(shù)的輸入：tree是指原始的FPTree或者是某個模式的條件FPTree，a是指模式的后綴（在第一次調(diào)用時a=NULL，在之后的遞歸調(diào)用中a是模式后綴）

FP-growth函數(shù)的輸出：在遞歸調(diào)用過程中輸出所有的模式及其支持度（比如{I1,I2,I3}的支持度為2）。每一次調(diào)用FP_growth輸出結(jié)果的模式中一定包含F(xiàn)P_growth函數(shù)輸入的模式后綴。

我們來模擬一下FP-growth的執(zhí)行過程。

1、 在FP-growth遞歸調(diào)用的第一層，模式前后a=NULL，得到的其實就是頻繁1-項集。

2、 對每一個頻繁1-項，進行遞歸調(diào)用FP-growth()獲得多元頻繁項集。

下面舉兩個例子說明FP-growth的執(zhí)行過程。

1、I5的條件模式基是(I2 I1:1), (I2 I1 I3:1)，I5構(gòu)造得到的條件FP-樹如下。然后遞歸調(diào)用FP-growth，模式后綴為I5。這個條件FP-樹是單路徑的，在FP_growth中直接列舉{I2:2，I1:2，I3:1}的所有組合，之后和模式后綴I5取并集得到支持度>2的所有模式：{ I2 I5:2, I1 I5:2, I2 I1 I5:2}。

2、I5的情況是比較簡單的，因為I5對應(yīng)的條件FP-樹是單路徑的，我們再來看一下稍微復(fù)雜一點的情況I3。I3的條件模式基是(I2 I1:2), (I2:2), (I1:2)，生成的條件FP-樹如左下圖，然后遞歸調(diào)用FP-growth，模式前綴為I3。I3的條件FP-樹仍然是一個多路徑樹，首先把模式后綴I3和條件FP-樹中的項頭表中的每一項取并集，得到一組模式{I2 I3:4, I1 I3:4}，但是這一組模式不是后綴為I3的所有模式。還需要遞歸調(diào)用FP-growth，模式后綴為{I1，I3}，{I1，I3}的條件模式基為{I2：2}，其生成的條件FP-樹如右下圖所示。這是一個單路徑的條件FP-樹，在FP_growth中把I2和模式后綴{I1，I3}取并得到模式{I1 I2 I3：2}。理論上還應(yīng)該計算一下模式后綴為{I2，I3}的模式集，但是{I2，I3}的條件模式基為空，遞歸調(diào)用結(jié)束。最終模式后綴I3的支持度>2的所有模式為：{ I2 I3:4, I1 I3:4, I1 I2 I3:2}

????? ????????

?

根據(jù)FP-growth算法，最終得到的支持度>2頻繁模式如下：

item	條件模式基	條件FP-樹	產(chǎn)生的頻繁模式
I5 I4 I3 I1	{(I2 I1:1),(I2 I1 I3:1) {(I2 I1:1), (I2:1)} {(I2 I1:2), (I2:2), (I1:2)} {(I2:4)}	<I2:2, I1:2> <I2:2> <I2:4, I1:2>, <I1:2> <I2:4>	I2 I5:2, I1 I5:2, I2 I1 I5:2 I2 I4:2 I2 I3:4, I1 I3:4, I2 I1 I3:2 I2 I1:4

FP-growth算法比Apriori算法快一個數(shù)量級，在空間復(fù)雜度方面也比Apriori也有數(shù)量級級別的優(yōu)化。但是對于海量數(shù)據(jù)，FP-growth的時空復(fù)雜度仍然很高，可以采用的改進方法包括數(shù)據(jù)庫劃分，數(shù)據(jù)采樣等等。

?

總結(jié)

以上是生活随笔為你收集整理的关联挖掘算法Apriori和FP-Tree学习的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。