矩陣與前綴樹方法挖掘頻繁項(xiàng)集

丁邦旭，黃永青

銅陵學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，安徽 銅陵 244000

1 引言

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領(lǐng)域中的重要方面，其反映出相關(guān)數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)或相關(guān)聯(lián)系。頻繁項(xiàng)集挖掘是關(guān)聯(lián)規(guī)則挖掘中的主要步驟。作為知識(shí)發(fā)現(xiàn)KDD的一項(xiàng)重要研究課題，頻繁項(xiàng)集挖掘最初是由事務(wù)庫(kù)中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則，由Agrawal等人首先提出[1]。數(shù)據(jù)挖掘應(yīng)用于諸多領(lǐng)域，其主要工作是發(fā)現(xiàn)頻繁項(xiàng)集。近年來(lái)，研究學(xué)者先后提出了Apriori，F(xiàn)P-growth，ECLAT等數(shù)據(jù)挖掘算法及其改進(jìn)算法。（1）Apriori算法采用逐層迭代方式，從候選項(xiàng)集中產(chǎn)生頻繁項(xiàng)集，需多次掃描數(shù)據(jù)庫(kù)，算法的時(shí)間與空間效率都很低，不適用于處理大量數(shù)據(jù)集[1-3]；（2）FP-growth算法只需掃描數(shù)據(jù)庫(kù)2次，采用模式增長(zhǎng)方式，不產(chǎn)生候選項(xiàng)集，但算法的數(shù)據(jù)存儲(chǔ)FP-Tree樹維護(hù)復(fù)雜，挖掘時(shí)需要遞歸創(chuàng)建FP-Tree，時(shí)空效率不高[3-4]；（3）ECLAT算法僅需掃描一遍數(shù)據(jù)庫(kù)，采用矩陣形式存儲(chǔ)TID項(xiàng)集，其計(jì)算項(xiàng)集的支持?jǐn)?shù)較快，但算法遇到TID項(xiàng)集很長(zhǎng)時(shí)，自連接的交運(yùn)算消耗大量時(shí)間，算法占用空間迅速增大，運(yùn)行效率降低[3，5-6]。因而改進(jìn)挖掘算法，提高算法的效率對(duì)數(shù)據(jù)挖掘具有重要意義。

本文提出一種基于矩陣（Matrix）與前綴樹（Prefixtree）的頻繁項(xiàng)集挖掘新算法MPFI。該算法掃描事務(wù)數(shù)據(jù)庫(kù)一次，構(gòu)建二進(jìn)制向量矩陣，得到二進(jìn)制位數(shù)組記錄的頻繁項(xiàng)集信息，并采用新的數(shù)據(jù)結(jié)構(gòu)前綴樹壓縮存儲(chǔ)頻繁項(xiàng)的相關(guān)信息，采用深度優(yōu)先的策略挖掘頻繁模式，不產(chǎn)生候選項(xiàng)集，將有效地提高算法的時(shí)間與空間效率。

2 問題定義和描述

2.1 問題定義

定義1設(shè)I={I1,I2,…,In}是一給定數(shù)據(jù)項(xiàng)全集，Ii為第i個(gè)項(xiàng) (1≤i≤n)。項(xiàng)集X是集合I的子集(X?I)，含有K個(gè)數(shù)據(jù)項(xiàng)的項(xiàng)集X稱為K-項(xiàng)集[1]。

定義2 由表達(dá)式?X,Y:(X?Y)?s(X)≥s(Y)可知：如果一個(gè)項(xiàng)集是頻繁的，那么它的所有非空子集都是頻繁的[1]。

定義3事務(wù)數(shù)據(jù)庫(kù)D中所有包含項(xiàng)集X的事務(wù)個(gè)數(shù)稱為項(xiàng)集X的支持?jǐn)?shù)，記為Sup(X)。設(shè)最小支持度為minsup，對(duì)于項(xiàng)集X，若Sup(X)≥minsup·|D|(|D|為D的事務(wù)數(shù)），則稱項(xiàng)集X是頻繁項(xiàng)集[1]。

定義4事務(wù)數(shù)據(jù)庫(kù)D={T1,T2,…,Tm}，事務(wù)Tj(k=1,2,…,m)中含有若干個(gè)數(shù)據(jù)項(xiàng)，Tj由＜TID,Items＞來(lái)表示。經(jīng)f：T→R轉(zhuǎn)換為布爾型0-1矩陣BR=f(T)=(rij)(i=1,2,…,n;j=1,2,…,m)，rij表示數(shù)據(jù)項(xiàng)Ii在事務(wù)Tj中是否出現(xiàn)，1表示Ii∈Tj，否則表示為0[3，7-8]。

定義6數(shù)據(jù)劃分：對(duì)(K-1)-頻繁項(xiàng)集進(jìn)行分割，在各個(gè)分割上繼續(xù)與其他的項(xiàng)集相并運(yùn)算，得到K-頻繁項(xiàng)集。在BR的二進(jìn)制矩陣中，執(zhí)行布爾向量的“與”運(yùn)算。

定義7前綴樹為哈希樹的一種變種，結(jié)構(gòu)為多叉樹。以字符串公共前綴壓縮存儲(chǔ)空間，并能提高檢索效率，其時(shí)間復(fù)雜度僅為O(n)。按照項(xiàng)集格遍歷的等價(jià)類劃分方式，采用前綴樹數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)形式挖掘并存儲(chǔ)頻繁項(xiàng)集[9-10]。

2.2 數(shù)據(jù)描述

為了實(shí)現(xiàn)算法對(duì)事務(wù)數(shù)據(jù)庫(kù)D的頻繁項(xiàng)集挖掘，把D轉(zhuǎn)換為二進(jìn)制的布爾型矩陣，利用二進(jìn)制向量運(yùn)算提高算法效率，可大幅降低挖掘頻繁項(xiàng)的時(shí)間復(fù)雜度。構(gòu)建事務(wù)二進(jìn)制位矩陣，只需掃描D一次，從該二進(jìn)制矩陣中得到1-頻繁項(xiàng)集，按照相應(yīng)規(guī)則繼續(xù)挖掘高維頻繁項(xiàng)集[11]。在挖掘過(guò)程中只需存儲(chǔ)二進(jìn)制位串?dāng)?shù)據(jù)，空間開銷相對(duì)很小。

數(shù)據(jù)項(xiàng)Ii由包含它的事務(wù)表示，如果該項(xiàng)包含于某個(gè)事務(wù)中，則對(duì)應(yīng)的二進(jìn)制位為1，否則為0，即每個(gè)數(shù)據(jù)項(xiàng)以二進(jìn)制向量表示，最終構(gòu)成一個(gè)二進(jìn)制事務(wù)矩陣，如表1所示[12-14]。

表1 二進(jìn)制事務(wù)矩陣

假設(shè)給定一事務(wù)數(shù)據(jù)庫(kù)D，項(xiàng)集為{A,B,C,D,E}。表1為D按事務(wù)水平方向構(gòu)建二進(jìn)制位向量矩陣，但不便于頻繁項(xiàng)挖掘；對(duì)事務(wù)二進(jìn)制矩陣改進(jìn)，表示為表2的形式：按事務(wù)垂直方向構(gòu)建布爾向量矩陣。運(yùn)算規(guī)則：項(xiàng)Ii和Ij(i≠j)，取出Ii和Ij對(duì)應(yīng)的布爾向量，將該兩數(shù)據(jù)項(xiàng)的布爾向量進(jìn)行“與”運(yùn)算，得到二進(jìn)制位向量，若位的值為1，則事務(wù)中存在項(xiàng)集{Ii,Ij}，否則該事務(wù)中不存在項(xiàng)集{Ii,Ij}[15-17]。

表2 二進(jìn)制項(xiàng)集矩陣

對(duì)表2的矩陣按行向量執(zhí)行布爾向量的“與”運(yùn)算，得到相應(yīng)項(xiàng)集的二進(jìn)制位數(shù)組，其頻度計(jì)數(shù)即為該項(xiàng)集的支持?jǐn)?shù)[18]。

3 算法描述

3.1 算法基本思想

MPFI算法根據(jù)定義3、定義 4、定義 5、定義 6、定義7，進(jìn)行了以下改進(jìn)：

（1）基于定義4，按事務(wù)垂直方向構(gòu)建布爾型向量矩陣，得到以二進(jìn)制位數(shù)組表示的1-頻繁項(xiàng)集，如表3所示。

表3 1-頻繁項(xiàng)集

（2）基于定義6、定義7，按照項(xiàng)集格遍歷的等價(jià)類劃分方式，利用前綴樹實(shí)現(xiàn)存儲(chǔ)頻繁項(xiàng)集，并以深度優(yōu)先的搜索方式進(jìn)行遍歷，得到所有頻繁項(xiàng)集，如圖1所示。

圖1 數(shù)據(jù)劃分

算法結(jié)合前綴樹Prefix-tree結(jié)構(gòu)，以1-頻繁項(xiàng)的二進(jìn)制位向量與(K-1)-頻繁項(xiàng)集的二進(jìn)制位向量按位“與”運(yùn)算，產(chǎn)生K-項(xiàng)集的方法挖掘事務(wù)矩陣中的頻繁項(xiàng)集，如圖2所示。并且在產(chǎn)生K-項(xiàng)集的過(guò)程中對(duì)1-頻繁項(xiàng)集中不在(K-1)-頻繁項(xiàng)集中出現(xiàn)的項(xiàng)集進(jìn)行剪枝，提高了算法效率，降低了算法的空間復(fù)雜度。

圖2 前綴樹Prefix-tree

算法的具體執(zhí)行過(guò)程為：

（1）掃描事務(wù)庫(kù)D，構(gòu)建二進(jìn)制矩陣。

（2）根據(jù)用戶設(shè)定的最小支持度，產(chǎn)生頻繁1-項(xiàng)集L1，即：計(jì)算數(shù)據(jù)項(xiàng)的二進(jìn)制位向量的頻度計(jì)數(shù)，若Frequency(Ii)不小于最小支持?jǐn)?shù)，則該項(xiàng)為頻繁項(xiàng)。

（3）釋放二進(jìn)制矩陣存儲(chǔ)空間，并以1-頻繁項(xiàng)集構(gòu)建Prefix-tree。

（4）按照對(duì)應(yīng)規(guī)則，計(jì)算項(xiàng)集的頻度計(jì)數(shù)，循環(huán)創(chuàng)建Prefix-tree的下一層結(jié)點(diǎn)，從而產(chǎn)生頻繁項(xiàng)集L2,L3,…,Lk。

（5）深度遍歷Prefix-tree，L1∪L2∪…∪Lk，輸出結(jié)果，算法結(jié)束。

設(shè)最小支持度為minsup=40%，按照本算法的基本思想，對(duì)上述事務(wù)數(shù)據(jù)庫(kù)D進(jìn)行運(yùn)算，得到1-頻繁項(xiàng)集；取項(xiàng)“A”的二進(jìn)制位序列01111，“B”的二進(jìn)制位序列10001相“與”運(yùn)算，得項(xiàng)集{A,B}二進(jìn)制位序列00001，F(xiàn)requency({A,B})=1＜2，即該項(xiàng)集不頻繁。

3.2 數(shù)據(jù)存儲(chǔ)

算法程序采用面向?qū)ο蟮某绦蛟O(shè)計(jì)思想，將頻繁項(xiàng)集定義為類的形式，采用Java語(yǔ)言編寫程序，其類的定義如下：

本算法采用二進(jìn)制位序列保存頻繁項(xiàng)挖掘的信息，記錄該頻繁項(xiàng)集在哪些事務(wù)中出現(xiàn)，其二進(jìn)制位的存儲(chǔ)空間為：1/（4×8）字節(jié)，對(duì)系統(tǒng)存儲(chǔ)空間的開銷很小；采用如圖2所示改進(jìn)結(jié)構(gòu)的前綴樹Prefix-tree挖掘并記錄所有的頻繁項(xiàng)集，記錄K-頻繁項(xiàng)集的信息只需要一個(gè)數(shù)據(jù)項(xiàng)的結(jié)點(diǎn)存儲(chǔ)空間，其前k-1個(gè)項(xiàng)集無(wú)需存儲(chǔ)，按照深度遍歷的方式即可得到K-頻繁項(xiàng)集，大大降低了算法的空間存儲(chǔ)代價(jià)。

3.3 MPFI算法

MPFI算法采用二進(jìn)制位向量表示數(shù)據(jù)項(xiàng)，利用前綴樹存儲(chǔ)頻繁項(xiàng)挖掘數(shù)據(jù)，利用項(xiàng)集對(duì)應(yīng)的二進(jìn)制位向量“與”運(yùn)算產(chǎn)生頻繁模式。

算法：MPFI

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

MPFI算法采用java語(yǔ)言實(shí)現(xiàn)，實(shí)驗(yàn)環(huán)境為Windows7操作系統(tǒng)，雙核2.2 GHz處理器，內(nèi)存大小為4 GB，實(shí)驗(yàn)所需的數(shù)據(jù)采用兩個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集：T10I4D100K.dat與mushroom.dat數(shù)據(jù)集（下載自http：//fimi.ua.ac.be/data/）。公式δ=t/(m×n)為事務(wù)矩陣的稀疏因子，數(shù)據(jù)集T10I4D100K.dat的稀疏因子為0.01，比較稀疏；數(shù)據(jù)集mushroom.dat的稀疏因子為0.191，相對(duì)稠密。

為了驗(yàn)證該算法的理論分析及其實(shí)際性能，基于上述實(shí)驗(yàn)環(huán)境，相比較的ECLAT算法、FP-growth算法和MPFI算法均采用Java語(yǔ)言實(shí)現(xiàn)。在不同的最小支持度下，對(duì)上述兩個(gè)數(shù)據(jù)集進(jìn)行挖掘，得到ECLAT算法、FP-growth算法和MPFI算法的運(yùn)行時(shí)間，以圖表的形式對(duì)這幾種算法的運(yùn)行效率進(jìn)行比較。

圖3為挖掘數(shù)據(jù)集T10I4D100K.dat時(shí)隨支持度變化的運(yùn)行時(shí)間比較。T10I4D100K.dat為IBM購(gòu)物籃分析的人工事務(wù)數(shù)據(jù)庫(kù)，其事務(wù)平均長(zhǎng)度為10，事務(wù)模式較短。從實(shí)驗(yàn)數(shù)據(jù)對(duì)比可知，在對(duì)稀疏數(shù)據(jù)挖掘時(shí)，F(xiàn)P-growth算法優(yōu)于ECLAT算法（垂直記錄方式實(shí)現(xiàn)），MPFI算法的時(shí)間性能更好。

圖3 挖掘T10I4D100K.dat運(yùn)行時(shí)間比較

圖4是挖掘數(shù)據(jù)集mushroom.dat時(shí)隨支持度變化的運(yùn)行時(shí)間比較。該數(shù)據(jù)集包含描述的假設(shè)樣本對(duì)應(yīng)于23種雙孢蘑菇的物理特征，對(duì)蘑菇進(jìn)行分類：有毒或食用；其事務(wù)平均長(zhǎng)度為23，數(shù)據(jù)集相對(duì)較稠密。從實(shí)驗(yàn)數(shù)據(jù)對(duì)比可知，對(duì)交稠密的數(shù)據(jù)集挖掘時(shí)FP-growth算法需要花費(fèi)較多時(shí)間建FP-tree樹，ECLAT算法略優(yōu)于FP-growth算法，MPFI算法的執(zhí)行效率最好。

圖4 挖掘mushroom.dat運(yùn)行時(shí)間比較

5 結(jié)束語(yǔ)

本文提出了一種基于矩陣與前綴樹的頻繁項(xiàng)集挖掘MPFI算法，能快速地挖掘事務(wù)數(shù)據(jù)庫(kù)中的頻繁項(xiàng)集。本算法將事務(wù)序列采用垂直方向的二進(jìn)制位向量矩陣表示，以二進(jìn)制位數(shù)組與前綴樹Prefix-tree形式保存挖掘數(shù)據(jù)，降低了算法的空間開銷；MPFI算法先得到1-頻繁項(xiàng)集，再以1-頻繁項(xiàng)集構(gòu)建前綴樹，同時(shí)挖掘出頻繁項(xiàng)集，有效地提高了算法執(zhí)行的效率。實(shí)驗(yàn)證明，MPFI算法具有較好的頻繁項(xiàng)集挖掘執(zhí)行效率。

本算法的數(shù)據(jù)挖掘功能有限，后續(xù)改進(jìn)的研究方向?yàn)椋海?）結(jié)合閉合項(xiàng)集格改進(jìn)算法，挖掘頻繁閉項(xiàng)集（Frequent Closed Itemsets）；（2）挖掘流式數(shù)據(jù)頻繁模式。

[1]Agrawal R.Database mining：a performance perspective[J].IEEE Trans on Knowledge and Data Engineering，1993，5（6）.

[2]Agrawal R，Imielinski T，Swami A.Mining association rules between sets of items in large databases[C]//Proceedings of the ACM SIGMOD International Conference Management of Date，Washington，1993：207-216.

[3]閆珍，皮德常，吳文昊.高維稀疏數(shù)據(jù)頻繁項(xiàng)集挖掘算法的研究[J].計(jì)算機(jī)科學(xué)，2011，38（6）：183-186.

[4]宋余慶，朱玉全，孫志揮，等.基于FP-Tree的最大頻繁項(xiàng)目集挖掘及更新算法[J].軟件學(xué)報(bào)，2003，14（9）：1586-1592.

[5]張毅，楊穎，陸瑞興.一種新的頻繁項(xiàng)集挖掘算法DS_ECLAT[J].廣西科學(xué)院學(xué)報(bào)，2010，26（1）：19-22.

[6]Han J，Pei J，Yin Y.Mining Frequent Patterns Without Candiate Generation[C]//Proc of SIGMOD，Dallas，2000，29（2）：1-12.

[7]張忠平，李巖，楊靜.基于矩陣的頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)工程，2009，35（1）：84-86.

[8]王柏盛，劉寒冰，靳書和.基于矩陣的關(guān)聯(lián)規(guī)則挖掘算法[J].微計(jì)算機(jī)信息，2007，24（5）：143-145.

[9]Liu Guimei，Lu Hongjun，XuYabo，et al.Ascending frequency ordered prefix tree：Efficient mining of frequent patterns[C]//Prco of 8th Database Systems for Advanced Applications（DASFAA’03），2003.

[10]朱光喜，吳偉民，阮幼林，等.一種基于前綴樹的頻繁模式挖掘算法[J].計(jì)算機(jī)科學(xué)，2005，32（4）：34-36.

[11]徐嘉莉，陳佳，胡慶，等.基于向量的數(shù)據(jù)流滑動(dòng)窗口中最大頻繁項(xiàng)集挖掘[J].計(jì)算機(jī)應(yīng)用研究，2012，29（3）：837-840.

[12]Zaki M J.Fast vertical mining using diffsets，Technical Report 01-1[R].Rensselaer Polytechnic Institute，Troy，New York，2001.

[13]熊忠陽(yáng)，耿曉斐，張玉芳.一種新的頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)科學(xué)，2009，36（4a）：42-44.

[14]王磊，黃志球，朱小棟，等.數(shù)據(jù)流中基于矩陣的頻繁項(xiàng)集挖掘[J].計(jì)算機(jī)科學(xué)與探索，2008，2（3）：330-336.

[15]徐建民，郝麗維，王煜.數(shù)據(jù)流頻繁項(xiàng)集的快速挖掘方法[J].計(jì)算機(jī)工程與應(yīng)用，2009，44（34）：142-144.

[16]嚴(yán)海兵，卞福荃.一種基于布爾向量的Apriori改進(jìn)算法[J].蘇州科技學(xué)院學(xué)報(bào)：自然科學(xué)版，2008，25（1）：67-70.

[17]李志林，戴娟，劉以安.基于布爾向量運(yùn)算的Apriori算法[J].江南大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，9（3）：270-273.

[18]張?jiān)虑?滑動(dòng)窗口中數(shù)據(jù)流頻繁項(xiàng)集挖掘方法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（16）：132-134.