改進(jìn)的Eclat算法研究與應(yīng)用

崔馨月，孫靜宇

(太原理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，山西 太原 030024)

0　引　言

傳統(tǒng)的頻繁項集挖掘算法在處理較大規(guī)模數(shù)據(jù)時，存在效率低、內(nèi)存消耗大等問題，無法滿足應(yīng)用需求[1]。因此，提高頻繁項集挖掘算法處理較大規(guī)模數(shù)據(jù)的效率是一個重要的研究課題。

經(jīng)典的頻繁項集算法——Apriori算法在算法實現(xiàn)過程中，需多次訪問數(shù)據(jù)記錄，若源數(shù)據(jù)中的記錄條數(shù)較多，將使得算法的運行時間延長，并且系統(tǒng)的內(nèi)存消耗增加，有可能出現(xiàn)內(nèi)存不足等問題[2]。Eclat算法由Zaki等提出，“讀取”數(shù)據(jù)的次數(shù)為一次，是一種基于列存儲的頻繁項集挖掘算法，相比較基于行存儲的Apriori算法效率較高[3]。

Eclat算法沒有對產(chǎn)生的候選集進(jìn)行刪減操作，若數(shù)據(jù)中項出現(xiàn)頻率十分高時，交集運算消耗大量存儲空間，最終產(chǎn)生的頻繁項集數(shù)量巨大，影響算法效率。

許多學(xué)者從不同角度對Eclat算法進(jìn)行了改進(jìn)研究，其中馮培恩等[4]從剪枝、項集連接、交叉計數(shù)等方面提出改進(jìn)Eclat算法的方法，引入雙層哈希表，鏈表等數(shù)據(jù)結(jié)構(gòu)，提高了算法的運行效率，實驗結(jié)果表明，算法在處理稀疏數(shù)據(jù)集時效率更高。劉彩萍等[5]將等價類思想融入到FP-growth算法中，通過子空間迭代產(chǎn)生頻繁項集，使得改進(jìn)算法的效率優(yōu)于FP-growth，但是與Eclat算法相比并未做進(jìn)一步研究。王紅梅等[6]使用Eclat算法格的思想將數(shù)據(jù)劃分等價類，分段求頻繁項集，該算法對于長模式的稀疏數(shù)據(jù)集的挖掘效果較好。徐衛(wèi)等[7]將命題邏輯思想引入到Eclat算法中，減少了實際應(yīng)用中領(lǐng)域知識和支持度設(shè)置的局限,提高了算法的效率。李海峰等[8]提出針對流數(shù)據(jù)的頻繁項集挖掘算法，通過變化數(shù)據(jù)類型對挖掘的項集進(jìn)行動態(tài)分類，算法對流數(shù)據(jù)的處理效率較高。

本文通過分析Eclat算法的優(yōu)點和不足，使用候選集優(yōu)化、剪枝方法改進(jìn)算法，縮小候選集數(shù)量，從而減少了算法的運行時間；空間消耗方面，采用相關(guān)數(shù)據(jù)結(jié)構(gòu)減少空間消耗。在實際數(shù)據(jù)集上進(jìn)行驗證性實驗，最后在真實數(shù)據(jù)集上進(jìn)行算法的應(yīng)用研究。

1　Eclat算法

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

關(guān)聯(lián)規(guī)則挖掘通過分析數(shù)據(jù)，發(fā)現(xiàn)數(shù)據(jù)中可能存在的關(guān)聯(lián)或者聯(lián)系，其相關(guān)定義如下：

設(shè)I={i1,i2,…,im}是項目集，T={t1,t2,…,tn}是事務(wù)集，其中tj是項的集合，即ti?I，i∈[1,2,…,n]。設(shè)Z是一個項集，事務(wù)tj包含Z的充要條件是：Z?tj。當(dāng)A?I，B?I并且A∩B=?時，形式如“A?B”的規(guī)則蘊含式稱為關(guān)聯(lián)規(guī)則。規(guī)則A?B在T中成立的條件是Sup≥minsup，其中Sup是T中包含A∪B的百分比，minsup是最小支持度閾值。

1.2　Eclat算法

Zaki等基于概念格理論提出Eclat算法，利用等價類將整體數(shù)據(jù)劃分成較小的等價類，采用深度優(yōu)先搜索策略產(chǎn)生頻繁項集[9]。

Eclat算法由兩個頻繁k項集求并集得到候選k+1項集，對候選k+1項集的事務(wù)集做交集操作，生成頻繁k+1項集，以此迭代直到項集歸一，算法結(jié)束。

Eclat算法使用垂直數(shù)據(jù)格式來表示數(shù)據(jù)，即數(shù)據(jù)的每一條記錄由項標(biāo)記和該項出現(xiàn)的事務(wù)標(biāo)號構(gòu)成Tidset垂直數(shù)據(jù)庫，具體數(shù)據(jù)形式見表1。這樣表示的數(shù)據(jù)通過交集操作得到項集的支持度，而不用多次掃描數(shù)據(jù)。

表1　Tidset垂直數(shù)據(jù)庫

Eclat算法由事務(wù)的交集操作計算出候選集的支持度，當(dāng)數(shù)據(jù)表中事務(wù)集或項目集的規(guī)模較大時將出現(xiàn)[10]：① 由交集操作求支持度消耗大量時間；② 數(shù)據(jù)表較大時，消耗大量系統(tǒng)內(nèi)存。

2　改進(jìn)的Eclat算法

針對1.2節(jié)中分析的Eclat算法的不足，本節(jié)結(jié)合頻繁項集挖自身的性質(zhì)，在2.1節(jié)，2.2節(jié)提出2種優(yōu)化策略，構(gòu)成了改進(jìn)算法的理論依據(jù)。本文用到的符號說明見表2。

2.1　候選集優(yōu)化

性質(zhì)1：k-1項集Lk-1并集生成k項集時，若兩個項集的前k-2項不相同，則由這兩個項集產(chǎn)生的新項集是和之前產(chǎn)生的項集重復(fù)的或為非頻繁的項集。

表2　本文用到的符號

證明：設(shè)I1={i1,i2…ik-1}、I2={j1,j2…jk-1}是經(jīng)升序排列的兩個k-1項集，滿足前k-2項不同，則I1,I2的并集是頻繁項集。

假設(shè)項集I1,I2的前k-2項中有相同項的數(shù)目為x項，則不相同項有(k-2)-x項，2個k-2項集的并集中元素的個數(shù)為：|Uk-2|=x+2[(k-2)-x]即|Uk-2|=2(k-2)-x，若可以產(chǎn)生候選集，那么可以得到：|Uk-1|=k。分兩種情況討論：

(1) 第k-1項相同：

第k-1項相同，即滿足jk-1=ik-1，并集中的元素個數(shù)為：|Uk-1|=2(k-2)-x+1，即|Uk-1|=2k-3-x，則前k-2項中相同項有k-3項，即前k-3項都相同，而第k-2項不相同：jk-2≠ik-2，因此，項的組合(ik-2,jk-2)是否為頻繁項對分析起關(guān)鍵作用：

若(ik-2,jk-2)不是頻繁項集，根據(jù)Apriori算法的性質(zhì)(參見文獻(xiàn)[11]性質(zhì)2)，那么I1,I2的并集也不是頻繁項集。

(2) 第k-1項不同：

第k-1項不同，即jk-1≠ik-1，并集中的元素個數(shù)為：|Uk-1|=2(k-2)-x+2，即|Uk-1|=2(k-1)-x，若產(chǎn)生候選集，則前k-2項中相同的項有k-2項，也就是前k-2項都相同，與假設(shè)條件矛盾。

該性質(zhì)通過比較兩個k-1項集的前k-2項是否相同，二者相同時并集操作產(chǎn)生新項；否則，略過對這兩個項的操作，判斷其它項。對表1中的數(shù)據(jù)進(jìn)行頻繁項集挖掘，設(shè)置最小支持度為3，使用性質(zhì)1的情況是：對于2-項集{u,z}，{v,z}產(chǎn)生3-項集時，{u,v}是頻繁2-項集，故這兩項構(gòu)成的3-項集與前面的2-項集{u,v}，{u,z}產(chǎn)生的3-項集{u,v,z}重復(fù)。對于2-項集{u,z}和{w,z}產(chǎn)生3-項集時，由于子集{u,w}是非頻繁項，因此不能產(chǎn)生候選集{u,w,z}。

2.2　剪 枝

性質(zhì)2：若k項集I={i1,i2,…,ik}中，存在一個j∈I使得|Lk-l(j)|

證明：設(shè)I是k項頻繁項目集，則I的k個k-1項子集均在Lk-1中。在由I生成的k個k-1項子集中每一個項目i∈I共出現(xiàn)k-1次，故j∈I均有|Lk-l(j)|≥k-1，與假設(shè)矛盾，故I不是頻繁項集。

性質(zhì)2的延伸性質(zhì)是：Lk-1并集產(chǎn)生的候選k-項集的集合中存在一個k-維項集I={i1,i2,…,ik}，并存在i(1≤i≤k)，使得|Lk-l(i)|

證明：設(shè)I為k維頻繁項集。

因此，在固定了前i個項后，由I生成的k-1頻繁項集個數(shù)為k-i個，即|Lk-l(i)|=k-i，這與初始條件矛盾。

因此I不是頻繁k-項集。

從該性質(zhì)可知：如果Lk-1中任一頻繁集的前i個項在Lk-1中出現(xiàn)的次數(shù)小于k-i，那么該項為非頻繁項。

2.3　Eclat’算法

Eclat’算法是使用2.1節(jié)和2.2節(jié)的性質(zhì)得到的改進(jìn)算法，算法的具體實現(xiàn)過程如算法1所示。

算法1：Eclat’算法

輸入：垂直型數(shù)據(jù)庫Tidset，最小支持度minsup

輸出：所有的頻繁項集L

(1)首先掃描數(shù)據(jù)庫得到1-項集T1

(2)forallXi∈Tido

(3)forXj∈Tj，j>ido

(4)if前k-1項相同then

(5)產(chǎn)生候選集R=Xi∪Xj

(6)ifR中任意一項在k-1項集中出現(xiàn)的次數(shù)≥k-ithen

(7)則R=Xi∪Xj是一個新的候選集

(8)T(R)=T(Xi)∩T(Xj)

(9)ifT(R)≥minsupthen

(10)Tk+1=Tk+1∪R,L=L∪R，Tk+1初始為空

(11)ifTi≠?then

(12) 調(diào)用函數(shù)Eclat(Tk+1)

3　實驗設(shè)計及結(jié)果分析

3.1　實驗設(shè)計

使用公開的數(shù)據(jù)集對Eclat算法，Eclat’算法，改進(jìn)算法(僅使用性質(zhì)1)設(shè)計對比實驗，驗證本文提出的Eclat’算法的有效性，實驗平臺為PC(Intel i7，CPU 3.6 GHz，內(nèi)存4 GB)，操作系統(tǒng)為Win7旗艦版。實驗中采用的數(shù)據(jù)集包括密集型數(shù)據(jù)集：chess數(shù)據(jù)集和mushroom數(shù)據(jù)集；稀疏型數(shù)據(jù)集：IBM數(shù)據(jù)生成器產(chǎn)生的數(shù)據(jù)集T10I4D100k。關(guān)于實驗數(shù)據(jù)集的具體信息參見文獻(xiàn)[4]。

在實驗運行過程中，為避免其它進(jìn)程對實驗結(jié)果的干擾，使實驗結(jié)果出現(xiàn)一定偏差，本實驗中通過多次實驗取平均值得到實驗的運行時間，本實驗的運行時間由兩部分組成：產(chǎn)生頻繁項集的時間、將結(jié)果寫入文件的時間。

由于數(shù)據(jù)集稠密情況不同，故選取相應(yīng)的支持度閾值進(jìn)行實驗，比較實驗運行情況。由圖1可知：最小支持度設(shè)置得越小，產(chǎn)生的項集數(shù)越多，算法的運行時間也相應(yīng)增加[12]。實驗結(jié)果如圖2，圖3，圖4所示。

圖1　mushroom數(shù)據(jù)集上最小支持度與頻繁項集數(shù)之間的關(guān)系

圖2是在mushroom數(shù)據(jù)集上支持度閾值從6%到50%時三者運行時間。由圖2可知，最小支持度較大時，3條折線基本重合；最小支持度較小時，Eclat’算法相較于其它兩個算法運行時間更短，如最小支持度為0.3時算法運行時間比改進(jìn)算法減少19.63%，比原算法減少29.51%。在chess數(shù)據(jù)集上進(jìn)行實驗的實驗結(jié)果如圖3所示，實驗中選取支持度閾值為50%到90%的運行情況，通過比較算法的運行時間可以發(fā)現(xiàn)：Eclat’算法的效率較高，如在支持度閾值為80%時，Eclat’算法相比僅使用候選集優(yōu)化的改進(jìn)算法運行時間減少了38.15%。

圖2　mushroom數(shù)據(jù)集上算法的運行時間

圖3　chess數(shù)據(jù)集上算法的運行時間

圖4　T10I4D100k數(shù)據(jù)集上算法的運行時間

圖4是在數(shù)據(jù)集T10I4D100k上支持度閾值從0.1%增加到1%時算法消耗時間的比較情況，由圖中可以看出Eclat’算法運行更快，例如在最小支持度為0.4%時Eclat’算法效率與原算法相比提高接近16.5%，與改進(jìn)算法相比效率提高了6.62%。

通過對比實驗可以發(fā)現(xiàn)：相比Eclat算法、僅使用候選集優(yōu)化的改進(jìn)算法，Eclat’算法的效率更高，與Eclat算法相比，運行時間減少了20.37%以上，與僅使用候選集優(yōu)化策略的改進(jìn)算法相比，Eclat’算法的效率提高了9.522%。對于公開數(shù)據(jù)集，特別是稀疏型數(shù)據(jù)，當(dāng)設(shè)置較小的支持度時，改進(jìn)算法的性能更加明顯。

3.2　結(jié)果分析

通過分析Eclat算法，結(jié)合頻繁項集自身的性質(zhì)，基于候選集優(yōu)化、剪枝策略提出Eclat’算法。

候選集優(yōu)化主要是通過判斷有序排列的兩個k-1項集的前k-2項是否相同，滿足時，通過并集產(chǎn)生候選集，這樣可以減少部分無用項和略過對多余項的判斷，從而提高生成候選集的效率；剪枝策略則是篩選產(chǎn)生的Lk-1，使自連接的頻繁項集數(shù)減少，算法運行產(chǎn)生的中間多余項減少，計算支持度的交集操作次數(shù)也相應(yīng)地減少，減少了整體的時間和空間消耗，從而提高了算法效率。

為減少實驗的空間消耗，在編程實現(xiàn)算法時采用了適用于海量數(shù)據(jù)的位操作對象BitSet，減少了存放進(jìn)行交集操作的項目所占空間。

4　應(yīng)用研究

據(jù)IDC監(jiān)測顯示，全球數(shù)據(jù)以每年40%的速度增加，預(yù)計到2020年數(shù)據(jù)總量將達(dá)到40ZB[13]。各行各業(yè)產(chǎn)生的數(shù)據(jù)呈指數(shù)型增長，因此從大量數(shù)據(jù)中高效挖掘價值，有效利用數(shù)據(jù)成為當(dāng)前的研究熱點[14]。

隨著移動通信技術(shù)的迅速發(fā)展，智能手機更加人性化的設(shè)計，強大的綜合處理能力和無線接入力，開放的操作系統(tǒng)等特點使其通過安裝APP即可實現(xiàn)多功能擴展和應(yīng)用，智能手機逐漸成為我們生活密不可分的一部分。本文通過對用戶使用APP情況和用戶信息的分析，為用戶推薦相關(guān)APP。

應(yīng)用研究的數(shù)據(jù)來自某市的兩個通信運營商，數(shù)據(jù)的屬性包括IMEI、年齡、性別、手機品牌、流量使用情況、消費水平、訪問文娛類APP的頁面瀏覽量(page view，PV)、訪問購物類APP的PV數(shù)……訪問健康類APP的PV數(shù)等共29項信息。

上述數(shù)據(jù)信息存儲于MySQL中，首先預(yù)處理原始數(shù)據(jù)，主要包括3方面的內(nèi)容。數(shù)據(jù)清理：處理缺失值，如某記錄的屬性值缺省，則為該屬性值賦值為0；刪除與實驗研究無關(guān)的屬性，如IMEI屬性。數(shù)據(jù)集成：將兩個通信運營商的數(shù)據(jù)整合為一個數(shù)據(jù)集進(jìn)行分析。數(shù)據(jù)交換：合并所屬類別相近的屬性，或合并之后新命名屬性名。經(jīng)預(yù)處理之后的數(shù)據(jù)格式見表3，最終實驗的數(shù)據(jù)包括22個相關(guān)屬性。

表3　經(jīng)預(yù)處理的數(shù)據(jù)集樣例

通過頻繁項集挖掘找到出現(xiàn)頻率較高的項集，為進(jìn)一步分析研究奠定基礎(chǔ)。使用Eclat’算法輸出不同支持度下的頻繁項集，分析各屬性之間的關(guān)聯(lián)關(guān)系。實驗的結(jié)果在表4中有列出，從表中可以發(fā)現(xiàn)：購物類與IT類、時事類和網(wǎng)游類、女性與購物類等的關(guān)聯(lián)性較強。

表4　頻繁2項集

對一條規(guī)則A=>B，支持度(support)是指所有事務(wù)中同時出現(xiàn)A和B的概率。置信度(confidence)是所有事務(wù)中在出現(xiàn)A的情況下出現(xiàn)B的概率。A對于B的提升度(lift)為conf(A=>B)/conf(B)。lift<1，說明這兩個條件沒有關(guān)聯(lián)，lift≥1，表明A和B正相關(guān)，提升度越大規(guī)則越有價值。

從表5可以看出規(guī)則：{購物類，網(wǎng)游類}=>{IT類}的置信度為95.2%，{購物類，網(wǎng)游類}=>{IT類}和{IT類}=>{網(wǎng)游類}的提升度分別為2.265和2.190，均大于2，說明這兩條規(guī)則的關(guān)聯(lián)程度較高。最后一條規(guī)則的概率為72.5%，說明該條規(guī)則的可信度較高。

表5　產(chǎn)生的關(guān)聯(lián)規(guī)則

實驗結(jié)果可作為向用戶推薦APP的重要依據(jù)，讓相關(guān)企業(yè)和通信運營商獲取更大的利益，從而為用戶提供更周到、滿意的服務(wù)，為用戶的日常生活提供便利。

5　結(jié)束語

本文通過分析Eclat算法，結(jié)合頻繁項集自身特有的性質(zhì)，基于候選集優(yōu)化、剪枝策略提出了Eclat’算法，在公開數(shù)據(jù)集上對Eclat算法、僅使用候選集優(yōu)化的算法以及Eclat’算法設(shè)計了對比實驗，實驗結(jié)果表明較前兩者Eclat’算法的效率更高。此外本文還對算法的應(yīng)用作了進(jìn)一步的研究，在某市的通信運營商數(shù)據(jù)集上使用Eclat’算法進(jìn)行了頻繁項集挖掘，得到了出現(xiàn)頻率較高的項集，進(jìn)一步產(chǎn)生對指導(dǎo)實際有價值的關(guān)聯(lián)規(guī)則?；诒疚牡难芯?，后續(xù)將考慮采用MapReduce并行實現(xiàn)Eclat’算法，并對其作進(jìn)一步的應(yīng)用探索，以及平臺實現(xiàn)研究。

參考文獻(xiàn)：

[1]Riondato Matteo,Debrabant Justin A,Fonseca Rodrigo,et al.PARMA:A parallel randomized algorithm for approximate association rules mining in MapReduce[C]//ACM International Conference on Information and Knowledge Management.Maui: IEEE,2012:85-94.

[2]Shedge R,Ragha L.Hybrid approach for database intrusion detection with reactive policies[C]//4th International Confe-rence on Computational Intelligence and Communication Networks.Mathura: IEEE,2012:724-729.

[3]DING Bangxu, HUANG Yongqing.Algorithm of matrix and prefix-tree for mining frequent itemsets[J]. Computer Engineering and Applications,2015, 51(22):154-157(in Chinese).[丁邦旭,黃永青.矩陣與前綴樹方法挖掘頻繁項集[J].計算機工程與應(yīng)用,2015,51(22):154-157.]

[4]FENG Pei’en,LIU Yu,QIU Qingying,et al.Strategies of efficiency improvement for Eclat algorithm[J]. Journal of Zhejiang University(Engineering Science),2013,47(2):223-230(in Chinese).[馮培恩,劉嶼,邱清盈,等.提高Eclat算法效率的策略[J].浙江大學(xué)學(xué)報(工學(xué)版),2013,47(2):223-230.]

[5]LIU Caiping,MAO Jianpin,MAO Jianxu, et al. Lattice-based algorithm for fast mining frequent itemsets[J].Journal of Hunan University(Natural Sciences),2013,40(10):52-57(in Chinese).[劉彩蘋,毛建頻,毛建旭,等.基于格的快速頻繁項集挖掘算法[J].湖南大學(xué)學(xué)報(自科版),2013,40(10):52-57.]

[6]WANG Hongmei,HU Ming,ZHAO Shoufeng. Frequent itemsets mining segmentation algorithm based on vertical format[J]. Journal of Jilin University(Science Edition),2016,54(3):553-560(in Chinese).[王紅梅,胡明,趙守峰.基于垂直格式的頻繁項集挖掘分段算法[J].吉林大學(xué)學(xué)報理學(xué)版,2016,54(3):553-560.]

[7]XU Wei,LI Xiaofen,LIU Duanyang.Propositional logic-based association-rule mining algorithm L-Eclat[J].Computer Science, 2017, 44(12):211- 215(in Chinese).[徐衛(wèi), 李曉粉, 劉端陽. 基于命題邏輯的關(guān)聯(lián)規(guī)則挖掘算法L-Eclat[J]. 計算機科學(xué), 2017, 44(12):211-215.]

[8]LI Haifeng,ZHANG Ning,ZHU Jianming,et al.Frequent itemset mining over time-sensitive streams[J].Chinese Journal of Computers,2012, 35(11):2283-2293(in Chinese).[李海峰,章寧,朱建明,等.時間敏感數(shù)據(jù)流上的頻繁項集挖掘算法[J].計算機學(xué)報,2012,35(11):2283-2293.]

[9]Kotiyal B,Kumar A,Pant B,et al.User behavior analysis in web log through comparative study of Eclat and apriori[C]//International Conference on Intelligent Systems and Control.Coimbatore:IEEE, 2013:421-426.

[10]CHEN Fengjuan.ECLAT algorithm of association rules[J].Consumer Electronics,2014(16):149-149(in Chinese).[陳鳳娟.關(guān)聯(lián)規(guī)則的ECLAT算法[J].消費電子,2014(16):149-149.]

[11]LUO Dan,LI Taoshen.Research on improved Apriori algorithm based on compressed matrix[J].Computer Science,2013,40(12):75-80(in Chinese).[羅丹,李陶深.一種基于壓縮矩陣的Apriori算法改進(jìn)研究[J].計算機科學(xué),2013,40(12):75-80.]

[12]XU Jiali,YANG Hongjun,ZHAO Maojuan,et al.Algorithm based on bit operation forming frequent closed itemset[J].Application Research of Computer, 2013,30(11):3280-3282(in Chinese).[徐嘉莉,楊洪軍,趙茂娟,等.一種基于位運算的頻繁閉項集挖掘算法[J].計算機應(yīng)用研究,2013,30(11):3280-3282.]

[13]The 7 mainstreams of global data in 2018 reached MYM80 billion in 2020[EB/OL].[2018-02-27].http:// www.elecfans.com/iot/630774.html.

[14]Digital universe in China[EB/OL].[2016-08-25]. http://finance.sina.com.cn/roll/doc-ifxvixsh6641009.shtml.