共計 3439 個字符，預計需要花費 9 分鐘才能閱讀完成。

本篇內容主要講解“關聯挖掘算法 Apriori 和 FP-Tree 怎么使用”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓丸趣 TV 小編來帶大家學習“關聯挖掘算法 Apriori 和 FP-Tree 怎么使用”吧!

Apriori 算法和 FPTree 算法都是數據挖掘中的關聯規則挖掘算法，處理的都是最簡單的單層單維布爾關聯規則。

Apriori 算法

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

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

算法原始數據如下：

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

算法的基本過程如下圖：

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

下面進行遞歸運算：

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

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

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

海量數據下，Apriori 算法的時空復雜度都不容忽視。

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

時間復雜度：每計算一次 就需要掃描一遍數據庫。

FP-Tree 算法

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

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

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

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

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

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

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

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

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

procedure FP_growth(Tree, a)

if Tree 含單個路徑 P then{

  for 路徑 P 中結點的每個組合（記作 b）

  產生模式 b U a，其支持度 support = b 中結點的最小支持度；

} else {

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

  產生一個模式 b = a i U a，其支持度 support = a i .support；

  構造 b 的條件模式基，然后構造 b 的條件 FP- 樹 Treeb；

  if Treeb 不為空 then

  調用 FP_growth (Treeb, b)；

  }

}

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

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

FP-growth 函數的輸出：在遞歸調用過程中輸出所有的模式及其支持度（比如 {I1,I2,I3} 的支持度為 2）。每一次調用 FP_growth 輸出結果的模式中一定包含 FP_growth 函數輸入的模式后綴。

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

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

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

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

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

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

item

條件模式基

條件 FP- 樹

產生的頻繁模式

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 算法快一個數量級，在空間復雜度方面也比 Apriori 也有數量級級別的優化。但是對于海量數據，FP-growth 的時空復雜度仍然很高，可以采用的改進方法包括數據庫劃分，數據采樣等等。

到此，相信大家對“關聯挖掘算法 Apriori 和 FP-Tree 怎么使用”有了更深的了解，不妨來實際操作一番吧！這里是丸趣 TV 網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！