關聯規則挖掘頻繁項算法的應用

（徐州醫藥高等職業學校，江蘇徐州，221116）

關聯規則挖掘頻繁項算法的應用

呂淑玲

（徐州醫藥高等職業學校，江蘇徐州，221116）

關聯規則在數據挖掘中是一種簡單但很實用的規則，Apriori算法和FP-Growth算法是關聯規則中的典型算法，本文介紹了關聯規則和兩種典型算法的概念，利用實例對比兩種算法在挖掘頻繁項集中的區別，分析算法的優劣，從而確定算法的應用。

關聯規則；頻繁項；Aprior算法；FP-Growth算法

關聯規則挖掘是在海量數據上進行的。頻繁項集的產生需要訪問數據庫中所存儲的大量數據，用什么算法迅速高效地在數據集中找出所有的頻繁項集是數據挖掘的核心問題。現給定一個任務用兩種算法舉例對比：

例：事務數據庫中，包含有十個事務，已知最小支持度為30%，根據支持度的定義得到，最小支持數=事務數×最小支持度=10×30%=3。

1 Apriori法舉例，過程如下

（1）對數據庫進行瀏覽，計算每個1-項集的支持數，得到候選1-項集C1，將候選1-項集的支持數與最小支持數3比較，將大于或等于3的項集保留，得到頻繁1-項集F1

（2）對頻繁1-項集進行自連接和剪枝運算，得到候選2-項集。

①連接：項集{A}分別與{B}、{C}、{D}、{E}連接后組成新的項集；項集{B}分別與{C}、{D}、{E}連接后組成新的項集；項集{C}分別與{D}、{E}連接后組成新的項集；項集{D}與{E}連接后組成新的項集。

②剪枝：依據頻繁項集的所有子集都是頻繁的，對產生的每個項集進行判斷，本例中所得到的所有項集都滿足此要求。

（3）瀏覽事務數據庫，得出每個候選2-項集的支持數。

（4）與最小支持數3比較，保留支持數大于或等于3的頻繁項集，去掉支持數小于3的非頻繁項集，得到頻繁2-項集F2。

（5）對頻繁2-項集F2進行自連接和剪枝運算，得到候選3-項集。

自連接：為了避免重復，將項集中的內容按字典順序排序，當兩個項集中前面的項都相同，而只有最后一項不同時，才進行連接。例如，項集{A,B}和項集{A,C}，第一項相同（都是A），而第二項卻不同，這時將兩項連接后組成一個新的3-項集{A,B,C}。但是項集{A,B}和{B,C}的第一項不同，就不進行連接，這樣可以避免產生重復項集{A,B,C}。對頻繁2-項集進行自連接后，得到結果。

2 FP-Growth算法舉例，過程如下

（1）掃描事務數據庫，得到頻繁1-項集，并將頻繁1-項集按支持數從大到小排序，對于支持數相同的按字典順序排序。

（2）構造FP樹

①建立樹的根結點，用null代表。

②讀入第一個事分T01,按DBCAE的次序對事務中所包含的項進行排序，得到{D,B,C,A},創建標記為D、B、C、A的結點，形成路徑null→D→B→C→A,將路徑上結點的計數值設為1。

③讀入第二個事務T02，對各項進行排序，得到{D,B,C},由于路徑null→D→B→C與第一個事務的路徑前部分相同，所以，這里不再增加新結點，而是將D、B、C各個結點的計數值自動加1進行更新。

依次讀入第十個事務T10，得到與事務數據庫對應的FP樹。

（3）利用FP樹得到全部的頻繁項集

對構造的FP樹，采用分而治之的策略，根據項集支持數從小到大的順序，依次對E、A、C、B、D構造條件FP樹，從而找到全部的頻繁項集。

①首先，發現以E結尾的頻繁項集。

a.收集包含E的所有路徑，這些路徑稱為前綴路徑。

b.遍歷E結點，對支持數進行累加，得到E的支持數5，5大于等于最小支持數3成立，所以{E}是頻繁項集。

c.構造E的條件FP樹。

更新前綴路徑上的支持數，因為某些計數中包含有那些不含項E的事務，因此，必須將該路徑上的結點D、B、C的計數信息進行修改，以反映真實的事務數。給出了修改了支持數之后包含E的前綴路徑。

②刪除結點E，修剪前綴路徑，因為發現以AE、CE、BE、DE結尾的頻繁項集的問題不再需要E的信息。

③結點C只出現2次，它的支持數為2，說明只有2個事物包含CE。由于最小支持數為3，因此{C、E}是非頻繁的。因為以CE結尾的項集一定也是非頻繁的，所在以其后的分析中可以忽略C。這樣得到E的條件FP樹。

（4）利用E的條件FP樹，得到以E結尾的頻繁項集。

為了發現以AE結尾的頻繁項集，從E的條件FP樹中得到結點A的所有前綴路徑，此時與E的條件FP樹相同，通過把與結點A相關聯的計數值累加求和，得到{A、E}的支持數3，該值大于等于最小支持數3的要求，所以{A、E}是頻繁項集。按照前面介紹的方法，更新支持度計數，去掉結點A，并刪除非頻繁項B之后，得到AE的條件FP樹。在AE的條件FP樹中，只包含一個結點D，且支持數3滿足最小支持數的要求，所以{D、A、E}是頻繁項集。

先從E的條件FP樹中得到B的所有前綴路徑，得到頻繁項集{B、E}，再構造BE的條件FP樹，得到頻繁項集{D、B、E}。最后，發現以DE結尾的頻繁項集{D、E}。

至此，我們已經得到了以E結尾的所有頻繁項集。同樣，我們可以得到A、C、B、D的頻繁項集。

為了避免重復，Apriori采用了自連接和剪枝技術；為了提高訪問數據庫的效率，又采用了Hash樹求解候選項集的支持數。盡管如此對海量數據庫來說，這個算法還存在不盡人意的地方。

FP-Growth算法即頻繁模式樹增長算法（frequent pattern tree growth），是一種新的挖掘頻繁項集的算法。該算法中引入FP樹和條件FP樹的概念，利用FP樹將事務數據庫中的所有事物實現壓縮存儲，利用條件FP樹得到頻繁項集。在FP-Growth算法中只需要對數據庫進行兩次掃描，一次是為了得到頻繁1-項集，一次是為了建立FP樹。掃描數據庫的次數要遠遠小于Apriori算法。與Apriori算法通過候選項集來產生頻繁項集不同，FP算法并不產生候選項集，而是利用了條件FP樹直接生成頻繁項集，在大數據挖掘中，大大提高了工作效率。

Association rule mining algorithm for frequent item Applications

Lv Shuling
（Xuzhou pharmaceutical higher vocational schools，Xuzhou，Jiangsu，221116）

The association rule in data mining is a simple but very practical rule,Apriori algorithm and FP-Growth algorithm is a typical association rules algorithm, this paper introduces the concept of association rules and two typical algorithms,use two examples contrast algorithms in mining frequent item set difference, the pros and cons analysis algorithm to determine the application of the algorithm.

association rule；frequent item；Aprior algorithm；FP-Growth algorithm

呂淑玲（1974-），女，碩士，講師，研究方向關聯規則算法的應用。