一種基于裁剪FP-Tree 的頻繁項(xiàng)集挖掘算法

羅 芳

(寧德師范學(xué)院 計(jì)算機(jī)系，福建 寧德 352100)

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘技術(shù)的重要內(nèi)容之一，在金融、教育、銷售等行業(yè)得到了越來越廣泛的應(yīng)用。在Apriori 算法［1，2］被AgrawalR 等人提出以后，許多學(xué)者對(duì)其進(jìn)行了改進(jìn)，如FP－Growth［3］，它比Apriori 算法快一個(gè)數(shù)量級(jí)。FP－Growth 算法通過建立FP 樹來挖掘數(shù)據(jù)庫中頻繁項(xiàng)集。首先掃描一次數(shù)據(jù)庫，算出各項(xiàng)集的支持度計(jì)數(shù)，通過與用戶設(shè)定的最小支持度計(jì)數(shù)相比，得出頻繁1－項(xiàng)集，對(duì)頻繁1－項(xiàng)集按支持度計(jì)數(shù)進(jìn)行從大到小排序插入頻繁項(xiàng)頭表中;其次，再掃描一次數(shù)據(jù)庫，刪除數(shù)據(jù)庫中非頻繁1－項(xiàng)集的元素，構(gòu)造FP 樹，并挖掘出頻繁k(k ＞1)－項(xiàng)集。FP－Growth 算法在挖掘過程中，需要產(chǎn)生條件FP 樹，當(dāng)最小支持度較小時(shí)，將產(chǎn)生大量的條件FP 樹，占用的存儲(chǔ)空間會(huì)非常龐大。由于FP 樹和條件FP 樹都需要自頂向下、自底向上兩次遍歷，遍歷占用時(shí)間也大大增加。

針對(duì)FP－Growth 算法的不足之處，吳倩等提出了壓縮FP－tree 的改進(jìn)搜索算法，［4］張中平等提出了基于矩陣的頻繁項(xiàng)集挖掘算法，［5］王利鋼等提出了基于FP－tree 的項(xiàng)約束關(guān)聯(lián)規(guī)則挖掘算法，［6］宋威等提出了基于動(dòng)態(tài)裁剪頻繁模式樹的頻繁項(xiàng)集并發(fā)挖掘算法，［7］郭偉等提出了基于數(shù)組的FP－tree 頻繁項(xiàng)集挖掘算法，［8］付冬梅等提出了基于FP－tree 和約束概念格的關(guān)聯(lián)規(guī)則挖掘算法及應(yīng)用研究。［9］其中文獻(xiàn)［7］裁剪FP 樹的方法存在缺陷，可能會(huì)誤刪樹中結(jié)點(diǎn)，導(dǎo)致挖掘出的頻繁項(xiàng)集不正確。為此本文提出了一種新的基于數(shù)組的頻繁模式樹裁剪算法PruneFP－tree(簡(jiǎn)稱F_ FP)，利用數(shù)組存儲(chǔ)所有的2－項(xiàng)集的支持度計(jì)數(shù)，對(duì)FP 樹中的葉子結(jié)點(diǎn)進(jìn)行有效裁剪，減少條件FP 樹的生成，減少算法的遞歸次數(shù)。

1 理論基礎(chǔ)

數(shù)據(jù)庫D 是事務(wù)T 的集合，事務(wù)T 項(xiàng)目I 的集合，T I。若X T，則X 為一個(gè)項(xiàng)集，X 的支持度計(jì)數(shù)為包含X 的事務(wù)總數(shù)，如果X 的支持度計(jì)數(shù)大于用戶給定的最小支持度計(jì)數(shù)，則X 為頻繁項(xiàng)集。

(1)FP－tree 的樹結(jié)構(gòu):

FP－tree 包含一個(gè)值為null 的根結(jié)點(diǎn)、一棵項(xiàng)前綴子樹和一個(gè)頻繁項(xiàng)頭表HTable。樹中每個(gè)結(jié)點(diǎn)包括5 個(gè)域:item_ name、count、node_ link、child_ link、parent_ link，count 為支持度計(jì)數(shù)，node_ link 指向下一個(gè)具有相同item_ name 的結(jié)點(diǎn)，child_ link 指向子結(jié)點(diǎn)，parent_ link 指向父結(jié)點(diǎn)。頻繁項(xiàng)頭表表示為Head_ table，其中每個(gè)表項(xiàng) 包 括 2 個(gè) 域: item_ name、 node_ link，item_ name 的指針node_ link 指向FP－tree 中與之同名的第1 個(gè)結(jié)點(diǎn)。

(2)數(shù)組A 的定義如下:

I = {I1，I2，…，In}是HTable 頻繁項(xiàng)表頭中項(xiàng)的集合，A 是一個(gè)長(zhǎng)度不大于n－1 的結(jié)構(gòu)數(shù)組，用于存放2－項(xiàng)集的支持度計(jì)數(shù)，數(shù)組元素的值可表示為:count(Ii，Ij)，其中count(Ii，Ij)是2－項(xiàng)集的支持度計(jì)數(shù)。如果2－項(xiàng)集{Ii，Ij}的支持度計(jì)數(shù)為2 則A［i，j］= 2 、A［i，j］= 2 ，只取前一項(xiàng)來記錄即可，因此可知(i ＜j)。

定理1 當(dāng)一棵FP－tree 構(gòu)造完成以后，樹中i 結(jié)點(diǎn)的分布不會(huì)發(fā)生任何變化，i 條件模式不變。

證明:設(shè)FP 樹中i 結(jié)點(diǎn)的集合為{N1，N2，…，Nm}。當(dāng)FP 構(gòu)造完以后不會(huì)有新節(jié)點(diǎn)加入，則其節(jié)點(diǎn)條件模式不變。

定理2 若一個(gè)項(xiàng)集X 的子集不是頻繁項(xiàng)集，那么項(xiàng)集X 也不是頻繁項(xiàng)集。

證明:設(shè)k－項(xiàng)集X 為{I1，I2，…，Ik}，如果存在它的任意子集{I1，I2，…，Ip}(1 ＜p ＜k)不是頻繁項(xiàng)集，則它的支持度計(jì)數(shù)(同時(shí)出現(xiàn)的次數(shù))小于最小支持度計(jì)數(shù)，顯然{I1，I2，…，Ik}同時(shí)的支持度計(jì)數(shù)也小于最小支持度計(jì)數(shù)，則項(xiàng)集X 也不是頻繁項(xiàng)集。

定理3 設(shè)FP 樹中結(jié)點(diǎn)i 為葉子結(jié)點(diǎn)，存在前綴路徑B = {B1，B2，…，Bk}，如果包含結(jié)點(diǎn)i 的項(xiàng)集X 在FP 樹中Bk上是非頻繁的，且(B1∪i)∪(B1∪i)，…，(Bk∪i)中也找不到包含i 的頻繁項(xiàng)集X，則可以在樹中刪除該路徑上的結(jié)點(diǎn)i。

證明:如果項(xiàng)集X 在某條路徑上是非頻繁的，說明在該路徑上找不到頻繁項(xiàng)集X，若在(B1∪i)∪(B1∪i)，…，(Bk∪i)中也找不到頻繁項(xiàng)集X，則說明在FP 樹中找不到包含i 的頻繁項(xiàng)集X。說明可以從樹中刪除該路徑的葉子結(jié)點(diǎn)i。根據(jù)定理2 結(jié)合FP 樹的特點(diǎn)(FP 樹是由頻繁1－項(xiàng)集構(gòu)建的)，只需要求出結(jié)點(diǎn)i 的前綴路徑上的各結(jié)點(diǎn)與結(jié)點(diǎn)i 組合成的2－項(xiàng)集在該FP 樹中是不是頻繁的，如果不是，則說明以該2－項(xiàng)集為子集的項(xiàng)集都不是頻繁的。

定理4 若在某路徑上，結(jié)點(diǎn)i 的父親結(jié)點(diǎn)為根結(jié)點(diǎn)NULL，且孩子結(jié)點(diǎn)為空，則可刪除該路徑的結(jié)點(diǎn)i。

證明:若結(jié)點(diǎn)i 的父親結(jié)點(diǎn)為根結(jié)點(diǎn)NULL，且孩子結(jié)點(diǎn)為空，不可能找到包含i 頻繁k(k ＞1)－ 項(xiàng)集，所以可以刪除該路徑的結(jié)點(diǎn)i。

2 F_ FP 算法

(1)首先掃描數(shù)據(jù)庫，算出各1－項(xiàng)集的支持度計(jì)數(shù)，過濾非頻繁1－項(xiàng)集，將HTable 中的結(jié)點(diǎn)順序按支持度計(jì)數(shù)從大到小排序。對(duì)HTable 表中的事務(wù)進(jìn)行排序。

(2)再掃描數(shù)據(jù)庫，構(gòu)造存放2－項(xiàng)集的數(shù)組A，并構(gòu)造FP 樹(與FP－Growth 算法一致，因此不詳細(xì)展開描述)，裁剪FP 樹。

(3)裁剪FP 樹的過程:①若樹中某路徑上結(jié)點(diǎn)i 的父結(jié)點(diǎn)和孩子結(jié)點(diǎn)都為空，則刪除該結(jié)點(diǎn);②若樹中某路徑上的結(jié)點(diǎn)i 的孩子結(jié)點(diǎn)為空，且在該路徑上沒有包含i 的頻繁2－項(xiàng)集，則要再尋找整棵樹種是否存在包含i 的頻繁2－項(xiàng)集，如果未找到，那么刪除該結(jié)點(diǎn)。

輸入為數(shù)據(jù)庫DB，最小支持度計(jì)數(shù)min_ sup，輸出FP 樹。

(1)count(n)←0;

(2)foreachTiinDB //計(jì)算1－項(xiàng)集支持度計(jì)數(shù)

(3)foreachIiinTi

(4) {生成HTable 表，將事務(wù)Ii按支持度計(jì)數(shù)從大到小排列;

(5)［p/P］= sort(Ti，Item_ sets);}

(6)A［n－1，n－1］←0;//初始二維化數(shù)組

(7)T ←null;//根結(jié)點(diǎn)為null

(8)foreachIiinFrequent_ Items

(9)foreachIjinTi

(10){A［i，j］++;//構(gòu)造數(shù)組(i ＜j)

(11)insert_ tree(［p/P］，T);}//構(gòu)造FP 樹

(12)prune_ tree(T);//裁剪FP 樹

prune_ tree(T)函數(shù)如下:

(1)foreachiinHTable

(2){if(i 的孩子為空且父親為根結(jié)點(diǎn)null)then 刪除結(jié)點(diǎn)i;

(3)if(i 的孩子為空且i 的前綴路徑上找不到包含i 的頻繁2－項(xiàng)集)then

(4){foreachj ∈Bj

if(A［i，j］＜min_ sup)then 刪除結(jié)點(diǎn)i;}}

3 算法示例

事務(wù)數(shù)據(jù)庫列表如表1 所示，設(shè)最小支持度計(jì)數(shù)為3。

表1 事務(wù)數(shù)據(jù)庫表

(1)掃描數(shù)據(jù)庫，找出1－項(xiàng)集{a，b，c，d，e，f}的支持度計(jì)數(shù)為:{5，6，6，5，3，2}。由于f 支持度計(jì)數(shù)為2 則1－項(xiàng)集{f}是非頻繁的，將頻繁1－項(xiàng)集按支持度計(jì)數(shù)從大到小排:{b，c，a，d，e}，將數(shù)據(jù)庫事務(wù)也按該順序調(diào)整，如表1 的Frequent_ Items。

(2)再次掃描已排序的數(shù)據(jù)庫，構(gòu)造數(shù)組A。首先讀取Frequent_ Items 中排好序的T1，得到A［b，c］= 1、A［b，d］= 1、A［c，d］= 1;讀取T2:A［b，a］= 1;讀取T3:A［c，a］= 1、A［c，e］= 1、A［a，e］=1;讀取T4:A［b，c］=1+1 =2、A［b，d］= 1 +1 = 2、A［b，e］= 1、A［c，d］= 1 + 1 = 2、A［c，e］= 1 +1 = 2、A［d，e］= 1;依次掃描剩余事務(wù)可得到如下數(shù)組A 如圖1 所示:

圖1 數(shù)組A

(3)首先創(chuàng)建FP 樹的根結(jié)點(diǎn)，對(duì)排序的事務(wù)按順序調(diào)用insert_ tree(［p/P］，T)，如果i 是p 的孩子，則樹中p 結(jié)點(diǎn)數(shù)加1，否則把i 作為新的結(jié)點(diǎn)加入樹中，遞歸調(diào)用insert_ tree(［p/P］，T)，構(gòu)造FP 樹如圖2 所示。

圖2 構(gòu)造FP 樹

(4)對(duì)樹FP 進(jìn)行裁剪。

首先求出e 的模式基:(c，a:1)、(b，c，d:1)、(b，a:1)，這三條前綴路徑上都不包含e 的頻繁項(xiàng)集，再查找數(shù)組可知:A［e，b］ = 2 、A［e，c］ = 2 、A［e，a］= 2 、A［e，d］= 2 ，說明在整棵樹種找不到含e 的頻繁2－項(xiàng)集，根據(jù)定理3 則可刪除如圖1 所示①處的所有e 結(jié)點(diǎn);求出d 的模式基:(b，c，a:1)、(b，c:2)、(a:1)、(c:1)，這四條前綴路徑上都不包含d 的頻繁2－項(xiàng)集，查找數(shù)組可知:A［d，b］= 3 、A［d，c］= 4 、A［d，a］= 2 ，說明在整棵樹中找到包含d 頻繁2－項(xiàng)集{{b，d}，{c，d}}，則前綴路徑(b，c，a:1)、(b，c:2)、(c:1)上的結(jié)點(diǎn)d 不能刪除，前綴路徑(a:1)上的結(jié)點(diǎn)d 可以刪除，如圖1 的②處所示;求出a 的模式基:(b，c:1)、(b:2)、(c:1)，這四條前綴路徑上都不包含a 的頻繁2－項(xiàng)集，查找數(shù)組可知:A［a，b］=3 、A［a，c］= 2 ，說明在整棵樹中找到包含a 頻繁2－項(xiàng)集{a，b}，則將前綴路徑(c:1)上的結(jié)點(diǎn)a刪除，在尋找模式基的時(shí)候發(fā)現(xiàn)如圖1 中左③所示的結(jié)點(diǎn)a 的父親結(jié)點(diǎn)為根結(jié)點(diǎn)，且a 又是個(gè)葉子結(jié)點(diǎn)，根據(jù)定理4 可刪除該結(jié)點(diǎn);c、b 都不是葉子結(jié)點(diǎn)，則裁剪結(jié)束。裁剪后的FP 樹如圖3 所示:

圖3 裁剪后的FP 樹

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)采用數(shù)據(jù)集Connect 進(jìn)行實(shí)驗(yàn)，分析數(shù)據(jù)源的大小為16.0MB，事務(wù)數(shù)為240112 條，項(xiàng)數(shù)為232 個(gè)。算法編程語言采用C+ +，實(shí)驗(yàn)環(huán)境為:處理器為Intel (R)Core (TM)i7－5500，運(yùn)算速度是2.40GHz，內(nèi)存(RAM)為8GB，64 位WIN7 操作系統(tǒng)。兩種算法在最小支持度為0.1、0.25、0.5、1、1.5 時(shí)，最小支持度與執(zhí)行時(shí)間的關(guān)系如圖4 所示，隨著最小支持度的升高兩種算法的執(zhí)行時(shí)間大幅度減少，顯然，在相同的條件下，由于對(duì)FP 樹進(jìn)行有效裁剪，生成的條件FP 樹也大大減少，減少了遞歸調(diào)用條件FP 樹的時(shí)間，相比FP－Growth算法，改進(jìn)后的算法執(zhí)行時(shí)間效率優(yōu)勢(shì)明顯。

圖4 P_ FP 算法和FP－Growth 算法執(zhí)行時(shí)效比較

在輸入數(shù)據(jù)集相同的情況下，P_ FP 算法和FP－Growth 算法中與FP 樹的結(jié)點(diǎn)個(gè)數(shù)與事務(wù)數(shù)之間的關(guān)系如圖5 所示，可以看出:輸入事務(wù)數(shù)越多，改進(jìn)后的P_ FP 算法生成的結(jié)點(diǎn)個(gè)數(shù)和FP－Growth 算法相比，差距越大，說明生成的條件FP樹越少，算法執(zhí)行效率越高。隨著事務(wù)數(shù)的增多，改進(jìn)后的P_ FP 算法和FP－Growth 算法相比生成的結(jié)點(diǎn)個(gè)數(shù)減少了1 倍以上。

圖5 P_ FP 算法和FP－Growth 算法的結(jié)點(diǎn)數(shù)比較

5 結(jié)束語

FP－Growth 算法在執(zhí)行過程中生成大量的條件FP 樹，遍歷這些條件FP 樹的時(shí)空消耗的過大，為了解決這個(gè)問題，本文提出了一種基于數(shù)組的FP 樹裁剪方法，利用“若某一項(xiàng)集的子集是非頻繁的，那么該項(xiàng)集一定不是頻繁項(xiàng)集”這一性質(zhì)來對(duì)要裁剪的結(jié)點(diǎn)進(jìn)行篩選，有效減少了條件FP樹的生成，提高算法挖掘效率，實(shí)驗(yàn)結(jié)果證明P_FP 算法的可行性和有效性。

［1］ Agrawal R，Imielinski T，Swami A.Mining Association Rules between Sets of Items in Large Databases［C］.In:Proc of the ACM SIGMOD International conference on Management of Data，Washington DC，1993:207－216.

［2］Agrawal R，Srikant R.Fast algorithms for mining association rules［A］.Proc.1994 Int’l Conf.Very LargeData Bases (VLDB’94)［C］.Santiago，1994:487－499.

［3］HAN J，PEI J，YIN Y，etal.Mining frequent patterns without candidate generation a frequent_pattern tree approach［J］.Data Mining and Knowledge Discovery，2004，8(1):53－87.

［4］吳倩，羅健旭. 壓縮FP－tree 的改進(jìn)搜索算法［J］. 計(jì)算機(jī)工程與設(shè)計(jì)，2015，36(7):1771－1777.

［5］張中平，李巖，楊靜. 基于矩陣的頻繁項(xiàng)集挖掘算法［J］. 計(jì)算機(jī)工程，2009，35(1):84－86.

［6］王利鋼，陳平，胡松. 基于FP－tree 的項(xiàng)約束關(guān)聯(lián)規(guī)則挖掘算法［J］. 信息化研究，2014，40(6):11－15.

［7］宋威，劉文博，李晉宏. 基于動(dòng)態(tài)裁剪頻繁模式樹的頻繁項(xiàng)集并發(fā)挖掘算法［J］，山東大學(xué)學(xué)報(bào)，2011，41(4):49－55.

［8］郭偉，葉德謙. 改進(jìn)的基于FP－tree 頻繁項(xiàng)集挖掘算法［J］. 計(jì)算機(jī)工程與應(yīng)用，2007，43(19):174－176.

［9］付冬梅，王志強(qiáng). 基于FP－tree 和約束概念格的關(guān)聯(lián)規(guī)則挖掘算法及應(yīng)用研究［J］. 計(jì)算機(jī)應(yīng)用研究，2014，31(4):1013－1016.