李雪迪，鄭 彥

(南京郵電大學 計算機學院，江蘇 南京 210003)

基于分布式倒排索引的頻繁項集挖掘

李雪迪，鄭 彥

(南京郵電大學 計算機學院，江蘇 南京 210003)

頻繁項集挖掘是關(guān)聯(lián)規(guī)則挖掘中的核心，其直接影響了頻繁項集的產(chǎn)生效率。針對Eclat算法在挖掘海量數(shù)據(jù)中的頻繁項集時存在的內(nèi)存和計算資源不足等問題，文中設(shè)計了通過分布式倒排索引實現(xiàn)頻繁項集挖掘的DiiEclat算法。倒排索引等同于將數(shù)據(jù)垂直分布，按事務(wù)編號的不同將倒排索引分布式地存儲在不同的索引節(jié)點上，每個節(jié)點上的事務(wù)分別做交集，最后由檢索代理合并交集結(jié)果。在chess、mushroom、T40I10D100K和T10I4D100K數(shù)據(jù)集上，對DiiEclat、Eclat、Diffset等算法進行了實驗對比。結(jié)果表明，給出的DiiEclat算法通過事務(wù)集合垂直劃分和并行計算，解決了數(shù)據(jù)挖掘過程中求交集運算效率低下和內(nèi)存不足等問題，算法高效、可擴展。

Eclat算法；頻繁項集；倒排索引；并行計算

0 引 言

挖掘頻繁項集是生成關(guān)聯(lián)規(guī)則的關(guān)鍵。Apriori算法[1]是最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法，但該算法需要多次重復掃描數(shù)據(jù)庫，候選項集的生成效率較低并占用大量內(nèi)存。對此,J.Han等[2]提出了不產(chǎn)生候選頻繁項集的方法—FP-growth算法。盡管FP-growth算法有很多優(yōu)點，但是它也有不足，動態(tài)地生成和釋放數(shù)以萬計的條件FP-樹，將耗費大量的時間和空間。

上述兩種挖掘算法基于水平數(shù)據(jù)格式進行挖掘，相比之下Zaki等[3]提出的Eclat算法的數(shù)據(jù)集采用垂直數(shù)據(jù)的表示形式。Eclat算法由2個項集的Tidset求交集快速得到候選集的支持度，當頻繁項集龐大，進行交操作時會消耗系統(tǒng)大量的內(nèi)存，影響算法效率。宋長新等[4]提出Eclat+算法，充分利用Apriori的先驗性質(zhì)防止大量的時間消耗在額外候選集的產(chǎn)生及支持度的計算上。Zaki等[5]提出用Diffset垂直數(shù)據(jù)來減少交集的數(shù)據(jù)規(guī)模，降低內(nèi)存消耗。為改進頻繁項集產(chǎn)生的效率，傅向華等[6]提出基于倒排索引位運算的DF-FIMBII。該算法采取二進制數(shù)組位運算可以實現(xiàn)快速求交集，在數(shù)據(jù)規(guī)模非常大，建立倒排索引時，需為每個項目分配一個數(shù)組，導致性能下降。張玉芳等[7]結(jié)合劃分思想和突出基于概率的先驗約束方法，通過將事務(wù)劃分為多個非重疊部分，并對每一部分分別采用Eclat算法，以減少比較次數(shù)。馮培恩等[8]提出基于雙層哈希表的Eclat_opt算法，提高了剪枝的效率，但雙層哈希表需要額外的內(nèi)存開銷。

文中提出了一種基于分布式倒排索引挖掘頻繁項集的算法。垂直數(shù)據(jù)格式的實質(zhì)就是倒排索引[9]，按事務(wù)TID的不同將倒排索引分布式地存儲在不同的索引節(jié)點上，每個索引節(jié)點負責一個TID區(qū)間，因此每個索引節(jié)點上倒排索引中的TID互不相同。在交叉計數(shù)時，將檢索請求廣播到每個節(jié)點，節(jié)點并行計算，最后由檢索代理合并結(jié)果。該算法降低了交集的規(guī)模，實現(xiàn)了并行計算，從而提高了挖掘效率。

1 Eclat關(guān)聯(lián)規(guī)則挖掘

1.1 關(guān)聯(lián)規(guī)則相關(guān)概念

假設(shè)I={I1,I2,…,In}是項的集合。給定一個交易數(shù)據(jù)庫D，其中每個事務(wù)(Transaction)T是I的非空子集，即每一個交易都與一個唯一的標識符TID(TransactionID)對應(yīng)。關(guān)聯(lián)規(guī)則是形如X→Y的蘊涵式，其中X?I,Y?I且X∩Y=?。X和Y分別稱為關(guān)聯(lián)規(guī)則的先導和后繼。

對于關(guān)聯(lián)規(guī)則X?Y的可信度是指包含X和Y的事務(wù)數(shù)與包含X的事務(wù)數(shù)之比，即：confidence(X?Y)=support(X?Y)/support(X)?？尚哦确从沉巳绻灰字邪琗，則交易包含Y的概率。

1.2 Eclat算法

Eclat算法是一種深度優(yōu)先算法，采用垂直數(shù)據(jù)表示形式，在概念格理論的基礎(chǔ)上利用基于前綴的等價關(guān)系將搜索空間(概念格[10])劃分為較小的子空間(子概念格)。各子概念格采用自底向上的搜索方法獨立產(chǎn)生頻繁項集。

與FP-growth和Apriori算法不同，Eclat算法加入了倒排的思想，具體就是將事務(wù)數(shù)據(jù)中的項作為key，每個項對應(yīng)的Tidset作為value。項集X和Y可以組成一個新的項集Z，則Z的支持度計數(shù)為(X，value)∩(Y，value)。Eclat算法采用此方法計算支持度，對候選k項集進行支持度計算時，不需再次掃描數(shù)據(jù)庫，僅在一次掃描數(shù)據(jù)庫后得到每個1項集的支持度，而候選k項集的支持度就是在對k-1項集進行交集操作后得到該k項集Tidset中元素的個數(shù)[11]。

2 基于分布式倒排索引的頻繁項集挖掘

倒排索引源于實際應(yīng)用中需要根據(jù)屬性的值來查找記錄，Eclat算法查找頻繁項集是根據(jù)項目Item的值來查找事務(wù)Tidset求交集的過程，所以文中的索引對象是事務(wù)和事務(wù)包含的項目。倒排索引包括兩個部分：詞項詞典和倒排記錄表。詞項是可以被檢索的基本單位，索引中為每個詞項維護一個倒排記錄表。倒排記錄表中僅需要采用單鏈表記錄每個項目Item出現(xiàn)的事務(wù)TID。當?shù)古潘饕加脙?nèi)存達到一定大小時，才將詞典和倒排記錄表寫入磁盤中。

文中采用分布式倒排索引提高了頻繁項集挖掘的效率，將倒排索引按照事務(wù)編號垂直劃分的shard分布到不同的服務(wù)器上，服務(wù)器對不同shard并行計算交集，最后合并結(jié)果。

2.1 分布式倒排索引

掃描事務(wù)數(shù)據(jù)庫，根據(jù)TID值作Hash操作去查找Hash值所屬的范圍，找到對應(yīng)的shard。每個shard內(nèi)保存部分索引片段，從而實現(xiàn)分布式的倒排索引。

例如：設(shè)項目集I有兩個項目I1和I2，I1和I2的事務(wù)列表分別為TID(I1)={1,2,4,6,8,9,11,14,15}和TID(I2)={1,3,4,6,7,9,12,13,15}。預(yù)設(shè)三個shard，分別是shard1、shard2、shard3，其對應(yīng)的TID范圍分別是1～5、6～10、11～15。通過上述條件建立的分布式倒排索引如圖1所示。I1,I2對應(yīng)倒排索引的詞項詞典，shard1、shard2、shard3對應(yīng)倒排記錄表，里面的記錄以單鏈表形式存儲在內(nèi)存空間。

圖1 分布式倒排索引(I1,I2)

當求項目I1和I2的交集運算時，shard1、shard2、shard3并行地在每個分片上求和。shard1上交集為{1,4}，shard2上交集為{6,9}，shard3上交集為{15}，最后合并的結(jié)果為：{I1,I2}={1,4,6,9,15}，支持度計數(shù)為5。雖然倒排索引和Hash結(jié)構(gòu)很相似，但倒排索引不允許存在碰撞，而Hash存在碰撞，因此索引左側(cè)的I1,I2采用Bitmap表示，每個Ii對應(yīng)一個位置，并且是一一對應(yīng)的，從而Ii可以被快速定位。索引右側(cè)鏈表長度由9變?yōu)?，降低了內(nèi)存空間的要求和交集規(guī)模，加快了交集運算的速度，同時shard1、shard2、shard3并行計算，進一步提高了交集運算的速度。

根據(jù)數(shù)據(jù)庫中事務(wù)集T的規(guī)模，將事務(wù)集T按升序劃分，分片范圍為shard1(1～Tn1)，shard2(1～Tn2)，…，shardn(1～Tnn)。

2.2 基于分布式倒排索引的頻繁項集挖掘算法

建立事務(wù)集的分布式倒排索引后，查詢統(tǒng)計的效率是非常高的，可以快速得到1-頻繁項集。然后采用深度優(yōu)先搜索策略遞歸挖掘k-頻繁項集，并將得到的k-頻繁項集建立新的分布式倒排索引。根據(jù)Apriori算法中定義的?? 運算，在挖掘k-項集時利用頻繁(k-1)-項集對候選k-項集進行剪枝[12]。?? 運算定義如下：

lk-1中的兩個元素l1和l2可以執(zhí)行連接操作的條件是：

(l1[1]=l2[1]∧l1[2]=l2[2]∧…∧l1[k-2]=l2[k-2]∧l1[k-1]=l2[k-1])

l1和l2連接的結(jié)果為：

{l1[1],l1[2],…,l1[k-1],l2[k-1]}

基于分布式倒排索引的頻繁項集挖掘算法描述如下：

輸入：數(shù)據(jù)庫D，最小支持度閾值minsup；

輸出：所有頻繁項集L。

(1)第一次掃描數(shù)據(jù)庫，建立分布式倒排索引index1，同時得到頻繁1-項集L1，L=L∪L1；

(2)Eclat(Lk)：

forallXi∈Lkdo

forallXj∈Lk，i

若R=Xi∪Xj為k-項集且它的(k-1)-項集在index的Item中可搜索到，則R=Xi∪Xj成為一個新的候選項集。

Tidset(R)=Query(XiANDXj)

若|Tidset(R)|≥minsup，則L=L∪R，indexk=indexk∪R，其中indexk初始為空。

(3)若indexk≠?，調(diào)用函數(shù)Eclat(indexk)。

上述基于分布式倒排索引的頻繁項集挖掘算法關(guān)鍵是Query(XiANDXj)，數(shù)據(jù)分片并行求交集后合并。假設(shè)一個分片上Xi的鏈表長度為n，Xj的鏈表長度為m，則Query(XiANDXj)的時間復雜度為O(m+n)。

每個分片上(XiANDXj)是兩個鏈表求交集的過程，將兩個鏈表求交集后得到的鏈表直接保存在該分片的內(nèi)存形成新的倒排索引。例如：I1和I2在shard1上交集得到的鏈表為1->4，1和4仍然屬于shard1，所以直接將其以倒排索引保存在內(nèi)存中。算法中indexk=indexk∪R是保存新產(chǎn)生的頻繁項集的倒排索引。該操作都在各自shard上完成，不需要網(wǎng)絡(luò)傳輸開銷。

R=Xi∪Xj為k-項集且它的(k-1)-項集在index的Item中可搜索到，則R=Xi∪Xj成為一個新的候選項集。由于倒排索引的詞項詞典(Item)可以快速定位，因此提高了對候選項集剪枝的效率。比如：由2-項集{I1,I3}和{I2,I3}生成項集3-項集{I1,I2,I3}時，項集{I1,I2}是否頻繁在Item中可以快速查詢，從而可以對候選集{I1,I2,I3}進行剪枝。

3 實 驗

3.1 實驗環(huán)境和實驗數(shù)據(jù)

使用編號1～5的虛擬機搭建基于Solr[13]和Zookeeper[14]的分布式搜索方案SolrCloud實現(xiàn)分布式倒排系統(tǒng)，每臺機器上的SolrCore管理一個索引分片shard。所有的事務(wù)TID分配到四個shard數(shù)據(jù)區(qū)間上，每個shard的Tidset鏈表相互獨立。每臺機器運行的操作系統(tǒng)為CentOS6.3，內(nèi)存2 G，采用Java語言編程實現(xiàn)文中提出的DiiEclat算法。算法Eclat、Diffset和Eclat_opt用VC++2008實現(xiàn)，運行的平臺環(huán)境為Win7旗艦版，內(nèi)存2 G。

實驗數(shù)據(jù)集分為兩類：一類是稀疏型合成數(shù)據(jù)集T40I10D100K和T10I4D100K；另一類是密集型實際數(shù)據(jù)集chess和mushroom。

3.2 實驗結(jié)果與分析

實驗過程分為兩步：第一步，單機DiiEclat算法與算法Eclat、Diffset、Eclat_opt，針對不同數(shù)據(jù)集選擇不同的minsupport運行時間對比；第二步，DiiEclat算法在minsupport相同時，不斷增加shard節(jié)點個數(shù)，得到四種數(shù)據(jù)集運行時間的變化趨勢。

第一步的實驗結(jié)果如圖2～5所示。

圖2 chess上四種算法的運行時間結(jié)果

圖3 mushroom上四種算法的運行時間結(jié)果

chess和mushroom同為事務(wù)數(shù)較少的密集數(shù)據(jù)集，Diffset算法由于采用差集操作在數(shù)據(jù)集稠密時效率比Eclat算法高。而對事務(wù)數(shù)目較大的稀疏數(shù)據(jù)集T10I4D100K和T40I10D100K，Diffset算法明顯效率降低，不如Eclat算法。文中提出的DiiEclat算法通過Apriori算法的性質(zhì)和倒排表的快速定位Item大大提高了剪枝效率，無論數(shù)據(jù)集的稠密程度如何，效率明顯優(yōu)于算法Diffset和Eclat。Eclat_opt算法在四個數(shù)據(jù)集上都有較高的效率，但其通過雙層哈希表以空間換取時間，當數(shù)據(jù)集或者項目數(shù)變大時，額外的內(nèi)存開銷是比較大的，以至于單機內(nèi)存條件無法承受。而DiiEclat算法通過將索引段分布式存儲，既能并行計算交集、減少鏈表長度，又降低了每個節(jié)點的內(nèi)存需求。

圖4 T40I10D100K上四種算法的運行時間結(jié)果

圖5 T10I4D100K上四種算法的運行時間結(jié)果

第二步的實驗結(jié)果如圖6所示。DiiEclat算法針對四種數(shù)據(jù)集選取不同的minsupport，同時根據(jù)第一步的實驗結(jié)果選取運行時間較長的minsupport，即chess(60)、mushroom(10)、T40I10D100K(0.4)和T10I4 D100K(0.05)。

隨著節(jié)點個數(shù)由1增加到5，DiiEclat算法在數(shù)據(jù)集chess(60)、mushroom(10)、T40I10D100K(0.4)和T10I4D100K(0.05)的運行時間均明顯減少。隨著節(jié)點個數(shù)N的增加，使得求交集的鏈表長度L平均降到L/N，兩個鏈表求交集的時間和每個節(jié)點上的內(nèi)存需求明顯降低。同時，由于幾個節(jié)點并行求交集，進一步加快了算法的效率。

4 結(jié)束語

文中提出了一種基于分布式倒排索引的深度優(yōu)先頻繁項集挖掘算法。垂直數(shù)據(jù)格式的實質(zhì)是倒排索引，基于分布式倒排索引的DiiEclat算法挖掘頻繁項集時，通過將索引垂直劃分后分配到不同的節(jié)點上并行計算，解決了內(nèi)存和計算資源不足等問題。DiiEclat算法通過節(jié)點擴展能夠有效挖掘大數(shù)據(jù)集的頻繁項集。在下一步工作中，將考慮調(diào)整分布式倒排索引的存儲結(jié)構(gòu)，進一步提高所提方法的性能。

[1]AgrawalR,ImielinakiT,SwamiA.Miningassociationrulesbetweensetsofitemsinlargedatabases[C]//ProcoftheACMSIGMODconferenceonmanagementofdata.Washington,D.C.:ACM,1993:207-216.

[2]HanJ,PeiJ,YinY.Mingfrequentpatternswithoutcandidategeneration[C]//Procofthe2000ACMdata.Dallas,UnitedStates:ACM,2000:1-12.

[3]ZakiMJ.Scalablealgorithmsforassociationmining[J].IEEETransactionsonKnowledgeandDataEngineering,2000,12(3):372-390.

[4] 宋長新,馬 克.改進的Eclat數(shù)據(jù)挖掘算法的研究[J].微計算機信息,2008,24(24):92-94.

[5]ZakiMJ.Fastverticalminingusingdiffsets[R].NewYork,USA:RensselaerPolytechnicInstitute,2001.

[6] 傅向華,陳冬劍,王志強.基于倒排索引位運算的深度優(yōu)先頻繁項集挖掘[J].小型微型計算機系統(tǒng),2012,33(8):1747-1751.

[7] 張玉芳,熊忠陽,耿曉斐,等.Eclat算法的分析及改進[J].計算機工程,2010,36(23):28-30.

[8] 馮培恩,劉 嶼,丘清盈,等.提高Eclat算法效率的策略[J].浙江大學學報:工學版,2013,47(2):223-230.

[9] 鄭榕增,林世平.基于Lucene的中文倒排索引技術(shù)的研究[J].計算機技術(shù)與發(fā)展,2010,20(3):80-83.

[10]DaveyBA,PriestleyHA.Introductiontolatticesandorder[M].Cambridge,UK:CambridgeUniversityPress,1990.

[11] 陸 楠.關(guān)聯(lián)規(guī)則的挖掘及其算法的研究[D].長春:吉林大學,2007.

[12] 徐章艷,劉美玲,張師超,等.Apriori算法的三種優(yōu)化方法[J].計算機工程與應(yīng)用,2004,40(36):190-192.

[13]KucR.ApacheSolr3.1cookbook[M].[s.l.]:PacktPublishing,2001.

[14] 黃毅斐.基于ZooKeeper的分布式同步框架設(shè)計與實現(xiàn)[D].杭州:浙江大學,2012.

Frequent Itemset Mining Based on Distributed Inverted Index

LI Xue-di，ZHENG Yan

(College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Mining frequent itemsets is the core of mining association rules,which directly affects the efficiency of generating frequent itemsets.Eclat algorithm exists issues of insufficient memory and computing resource when mining frequent itemset of massive data.The DiiEclat algorithm is proposed for mining frequent itemsets through distributed inverted index.Inverted index is equal to the vertical distribution of the data,and according to the number of different transactions inverted index will be distributed on different index nodes,each node calculates the intersection of transactions on itself,the results of the intersection merged by the retrieval agent.The execution time of DiiEclat,Eclat,Diffset and Eclat_opt is compared in four datasets such as chess,mushroom,T40I10D100K and T10I4D100K.The experimental results show that DiiEclat is given to improve efficiency of intersection operation through the vertical division of the transaction sets and parallel computing,and it is efficient and scalable.

Eclat algorithm;frequent itemset;inverted index;parallel computing

2015-01-16

2015-04-20

時間：2016-02-18

國家“863”高技術(shù)發(fā)展計劃項目(2006AA01Z201)

李雪迪(1989-)，男，碩士研究生,研究方向為數(shù)據(jù)挖掘、大數(shù)據(jù)、云計算；鄭 彥，教授，碩士生導師，研究方向為數(shù)據(jù)挖掘、信息安全。

http://www.cnki.net/kcms/detail/61.1450.TP.20160218.1619.002.html

TP311

A

1673-629X(2016)03-0101-04

10.3969/j.issn.1673-629X.2016.03.024