矩陣與前綴樹方法挖掘頻繁項集

丁邦旭，黃永青

銅陵學院 數(shù)學與計算機學院，安徽 銅陵 244000

1 引言

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

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

2 問題定義和描述

2.1 問題定義

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

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

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

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

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

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

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

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

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

表1 二進制事務矩陣

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

表2 二進制項集矩陣

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

3 算法描述

3.1 算法基本思想

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

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

表3 1-頻繁項集

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

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

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

圖2 前綴樹Prefix-tree

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

（1）掃描事務庫D，構建二進制矩陣。

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

（3）釋放二進制矩陣存儲空間，并以1-頻繁項集構建Prefix-tree。

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

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

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

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

算法程序采用面向對象的程序設計思想，將頻繁項集定義為類的形式，采用Java語言編寫程序，其類的定義如下：

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

3.3 MPFI算法

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

算法：MPFI

4 實驗結果與分析

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

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

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

圖3 挖掘T10I4D100K.dat運行時間比較

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

圖4 挖掘mushroom.dat運行時間比較

5 結束語

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

本算法的數(shù)據(jù)挖掘功能有限，后續(xù)改進的研究方向為：（1）結合閉合項集格改進算法，挖掘頻繁閉項集（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ù)頻繁項集挖掘算法的研究[J].計算機科學，2011，38（6）：183-186.

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

[5]張毅，楊穎，陸瑞興.一種新的頻繁項集挖掘算法DS_ECLAT[J].廣西科學院學報，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]張忠平，李巖，楊靜.基于矩陣的頻繁項集挖掘算法[J].計算機工程，2009，35（1）：84-86.

[8]王柏盛，劉寒冰，靳書和.基于矩陣的關聯(lián)規(guī)則挖掘算法[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].計算機科學，2005，32（4）：34-36.

[11]徐嘉莉，陳佳，胡慶，等.基于向量的數(shù)據(jù)流滑動窗口中最大頻繁項集挖掘[J].計算機應用研究，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]熊忠陽，耿曉斐，張玉芳.一種新的頻繁項集挖掘算法[J].計算機科學，2009，36（4a）：42-44.

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

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

[16]嚴海兵，卞福荃.一種基于布爾向量的Apriori改進算法[J].蘇州科技學院學報：自然科學版，2008，25（1）：67-70.

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

[18]張月琴.滑動窗口中數(shù)據(jù)流頻繁項集挖掘方法[J].計算機工程與應用，2010，46（16）：132-134.