王 盛,董黎剛,李 群

(浙江工商大學(xué)信息與電子工程學(xué)院,浙江杭州310018)

0 引 言

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘一個(gè)重要課題。數(shù)據(jù)預(yù)處理是數(shù)據(jù)挖掘中的一個(gè)重要階段。數(shù)據(jù)預(yù)處理的目的就是找到一種高效的方法來存儲(chǔ)數(shù)據(jù),以使對(duì)數(shù)據(jù)子群的訪問盡可能快。但人們往往忽略它對(duì)數(shù)據(jù)挖掘的重要性,使它經(jīng)常成為整個(gè)數(shù)據(jù)挖掘算法的瓶頸[1]。當(dāng)前的規(guī)則挖掘算法[1-6]主要從3個(gè)方面著手：(1)如何降低規(guī)則挖掘的掃描開銷;(2)如何減少掃描事務(wù)數(shù)據(jù)庫的次數(shù);(3)如何確定頻繁項(xiàng)目集并減少候選項(xiàng)目個(gè)數(shù)和計(jì)算頻繁項(xiàng)目集的支持?jǐn)?shù)。如基于二進(jìn)制序列集挖掘算法[2],B-Apriori算法[1],采用PLT結(jié)構(gòu)的算法[4],采用剪枝技術(shù)的Apriori改進(jìn)算法[5]等,這些算法中有些改進(jìn)了數(shù)據(jù)預(yù)處理技術(shù),而確定繁項(xiàng)目集仍沿用運(yùn)算量大的Apriori算法中的方法。對(duì)于新增加的項(xiàng)目,新老數(shù)據(jù)無法相互兼容,必須整體重新掃描生成數(shù)據(jù),這種特性降低了效率,同時(shí)增加了系統(tǒng)的開銷。因此,針對(duì)以上3個(gè)方面及算法存在的不足,必須尋找一種安全、高效的實(shí)現(xiàn)方式對(duì)數(shù)據(jù)進(jìn)行分析,目前國內(nèi)外并沒有較好的研究報(bào)道。為此,本文提出一種基于二進(jìn)制數(shù)以及項(xiàng)目的支持度分布(概率分布)的Apriori改進(jìn)算法BF-Apriori。

1 主要定義和性質(zhì)

為了實(shí)現(xiàn)BF-Apriori算法,定義1規(guī)定了對(duì)數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行二進(jìn)制數(shù)轉(zhuǎn)換的轉(zhuǎn)換協(xié)議。相關(guān)的性質(zhì)為規(guī)則挖掘算法的相關(guān)運(yùn)算保證了理論依據(jù)和運(yùn)算結(jié)果的可靠性。

定義1 事務(wù)-二進(jìn)制數(shù)逆序轉(zhuǎn)換關(guān)系RTR,給定項(xiàng)目集I={I1,I2,…,Im},其中項(xiàng)目是按照項(xiàng)目支持度從大到小排列。事務(wù)數(shù)據(jù)庫D,其中T∈D,并且T?I,規(guī)定f1：T×I→bk…b3b2b1(k≤m,且為事務(wù)t中包含的項(xiàng)目編號(hào)的最大值),并稱b=bk…b3b2b1事務(wù)T所對(duì)應(yīng)的二進(jìn)制數(shù),記為Bt,其中bj∈{0,1},若事務(wù)中包含Ij則bj=1,否則為0。

性質(zhì)1 行向量逆序轉(zhuǎn)換性質(zhì),給定項(xiàng)目集I={I1,I2,…,Im},若二進(jìn)制Bt的第j1,j2,…,jk(ji＞ji-1,且0＜j≤m,1≤i≤k,其中 jk為b的最高位的序號(hào))位的值為1,則Xb={Ij1,Ij2,…,Ijk},其中jk小于等于Bt的最高位。

證明 根據(jù)RTR轉(zhuǎn)換規(guī)則,性質(zhì)1顯然成立。

性質(zhì)2 給定項(xiàng)目集 I={I1,I2,…,Im},假設(shè)事務(wù)二進(jìn)制數(shù)Bt1、Bt2,如果Bt1and Bt2=Bt1,那么事務(wù)T1?T2。

證明 根據(jù)邏輯與的定義和定義1,性質(zhì)2顯然成立。

性質(zhì)3 若某一元素在產(chǎn)生的所有頻繁項(xiàng)集Xk-1中出現(xiàn)的次數(shù)小于k-1次,那么它就不可能是頻繁項(xiàng)集Xk的元素。

證明 由頻繁項(xiàng)集的定義可知,頻繁項(xiàng)集的任一子集都是大的,根據(jù)排列組合的性質(zhì)可知,頻繁項(xiàng)集Xk的k-1維子集也就是意味著在k個(gè)元素中去掉一個(gè),那么每一個(gè)元素在Xk的k-1維子集中出現(xiàn)的次數(shù)等于k-1次,所以若某一元素在產(chǎn)生的所有頻繁項(xiàng)集Xk-1中出現(xiàn)的次數(shù)小于k-1次,那么它就不可能是頻繁項(xiàng)集Xk的元素。性質(zhì)3得證。

2 數(shù)據(jù)處理和規(guī)則挖掘

假設(shè)I={I1,I2,…,Im}是m個(gè)不同項(xiàng)目的一個(gè)集合,T={t1,t2,t3,…,tn}是事務(wù)數(shù)據(jù)庫D中n條記錄的集合,minsup表示最小支持度,X.sup表示項(xiàng)目集X在事務(wù)數(shù)據(jù)庫D中所對(duì)應(yīng)的支持?jǐn)?shù),Li表示頻繁i項(xiàng)目集,Fre表示上一級(jí)挖掘中每一個(gè)項(xiàng)目成功組合的次數(shù),Cas表示事務(wù)總數(shù),R表示滿足minsup的組合,NFre表示當(dāng)前挖掘中每一個(gè)項(xiàng)目成功組合的次數(shù)。

2.1 以二進(jìn)制數(shù)轉(zhuǎn)換事務(wù)數(shù)據(jù)庫的算法

算法1 基于二進(jìn)制數(shù)的行向量轉(zhuǎn)換事務(wù)的算法(RTR算法)。

對(duì)于海量的數(shù)據(jù),采用內(nèi)存管理當(dāng)中的地址映射中的組相聯(lián)策略,可對(duì)所得到的數(shù)據(jù)進(jìn)行切片運(yùn)算,即事務(wù)經(jīng)過行向量轉(zhuǎn)換得到二進(jìn)制數(shù)過長,則對(duì)其進(jìn)行定長截取并進(jìn)行標(biāo)記,分別進(jìn)行支持度或支持?jǐn)?shù)的統(tǒng)計(jì),得到的結(jié)果再進(jìn)行組合從而得到總的支持度和支持?jǐn)?shù)。

由于項(xiàng)目在事務(wù)當(dāng)中的發(fā)生的不確定性,因而本文對(duì)于事務(wù)-二進(jìn)制數(shù)逆序轉(zhuǎn)換算法在空間上的性能做了如下的理論估計(jì)。

假設(shè)項(xiàng)目集I={I1,I2,…,Im},事務(wù)數(shù)據(jù)庫D,其中T?I且T?D,對(duì)應(yīng)的支持度(也就是概率)分別為P={P1,P2,…,Pm},且項(xiàng)目集中的各項(xiàng)目支持度之間的關(guān)系是P1＞P2＞…＞Pm,則事務(wù)的平均長度的：

根據(jù)定義1,本文給如圖1所示的RTR轉(zhuǎn)換算法流程圖。

2.2 規(guī)則生成頻繁i-項(xiàng)目集算法

算法2 行向量逆序轉(zhuǎn)換后規(guī)則挖掘算法BF-Apriori(RTR)(BF-Apriori based on RTR)如圖2所示：

3 算法實(shí)現(xiàn)和性能比較

為了驗(yàn)證算法的性能,本文用JavaSE-1.6在內(nèi)存2G、CPU為 Intel酷睿 2雙核T7500 2.2GHz、操作系統(tǒng)為Windows7 Ultimate的電腦上實(shí)現(xiàn)算法,本文使用了與文獻(xiàn)6同樣的測試數(shù)據(jù)庫對(duì)算法進(jìn)行實(shí)現(xiàn)和性能分析,該數(shù)據(jù)庫有8124條記錄,記錄了Mushroom的23種屬性119個(gè)屬性分量。

圖1 RTR轉(zhuǎn)換算法流程圖

圖2 BF-Apriori(RTR)算法

圖3 逆序轉(zhuǎn)換長度比較

3.1 算法預(yù)處理的驗(yàn)證實(shí)驗(yàn)

為了驗(yàn)證RTR算法事務(wù)平均長度估計(jì)公式的準(zhǔn)確性、RTR算法的高效性,在實(shí)驗(yàn)的過程中,本文取了7組數(shù)據(jù)集(6,33)、(10,51)、(15,75)、(18,89)、(20,97)、(22,112)、(23,119)。其中(屬性數(shù),分量數(shù)),MaxLen由公式1計(jì)算得到RTR轉(zhuǎn)換的估計(jì)的事務(wù)平均長度的最大值,MinLen為由公式2計(jì)算得到RTR轉(zhuǎn)換的估計(jì)的事務(wù)平均長度的最小值,LenbyLAB為實(shí)驗(yàn)測得事務(wù)的平均長度,ComLen為一般基于二進(jìn)制序列的算法[2]事務(wù)的平均長度,實(shí)驗(yàn)的結(jié)果如圖3所示。

通過圖3可以看到,經(jīng)過RTR轉(zhuǎn)換后事務(wù)的平均長度明顯優(yōu)于其他基于二進(jìn)制序列的數(shù)據(jù)預(yù)處理方法,基于Mushroom數(shù)據(jù)庫的RTR轉(zhuǎn)換節(jié)約了50%左右的存儲(chǔ)空間,可見,RTR算法比一般的基于二進(jìn)制數(shù)據(jù)預(yù)處理方案在存儲(chǔ)開銷上優(yōu)越。此外,從實(shí)驗(yàn)可以得出事務(wù)經(jīng)RTR轉(zhuǎn)換的事務(wù)平均長度LenbyLAB落在了MaxLen,MinLen之間,從而證明在實(shí)踐中式1、2可以用來估計(jì)經(jīng)RTR轉(zhuǎn)換的事務(wù)的平均長度區(qū)間并定性分析RTR算法的性能。

3.2 規(guī)則挖掘算法驗(yàn)證實(shí)驗(yàn)

為了驗(yàn)證算法規(guī)則挖掘的性能,本文在電腦上實(shí)現(xiàn)了BF-Apriori(RTR)算法和B-Apriori算法(該算法與本算法屬于同一類型)[1]生成頻繁項(xiàng)目集并計(jì)算項(xiàng)目集的支持?jǐn)?shù)。分別取了 0.05、0.08、0.11、0.14、0.17、0.20、0.25、0.30、0.35、0.45、0.50、0.60這12組支持度進(jìn)行頻繁2-項(xiàng)目集挖掘(2層關(guān)聯(lián)挖掘),聯(lián)規(guī)則挖掘的算法實(shí)際執(zhí)行時(shí)間如圖4所示。

圖4可以看出,BF-Apriori(RTR)的挖掘效率比一般的B-Apriori算法提高了一個(gè)數(shù)量級(jí)。隨著最小支持度的增大,BF-Apriori(RTR)算法的執(zhí)行效率明顯提高,B-Apriori算法也有提高,但提升幅度沒有BF-Apriori(RTR)算法突出,從而驗(yàn)證了BF-Apriori算法的有效性和高效性。

4 結(jié)束語

本文提出一種基于二進(jìn)制數(shù)以及項(xiàng)目的支持度分布的Apriori改進(jìn)算法BF-Apriori。該算法能夠?qū)⑹聞?wù)信息進(jìn)行大幅度壓縮后存入內(nèi)存,提高規(guī)則挖掘的效率,同時(shí)能夠很好的將二進(jìn)制數(shù)回溯到事務(wù)記錄。在分布式數(shù)據(jù)分析時(shí),只要雙方同步數(shù)據(jù)字典(項(xiàng)目的排序定義),就能夠?qū)崿F(xiàn)基于網(wǎng)絡(luò)的加密的分布式數(shù)據(jù)分析,同時(shí),BF-Apriori(RTR)算法具有數(shù)據(jù)高可壓縮性和可分割性,能大幅降低分布式系統(tǒng)間的通信量,對(duì)于新增加的事件類型,能夠兼容已轉(zhuǎn)換的數(shù)據(jù)而無需重新生成。實(shí)驗(yàn)結(jié)果表明,BF-Apriori算法提高數(shù)據(jù)挖掘算法中項(xiàng)目集的存儲(chǔ)效率,比基于二進(jìn)制序列的處理方法效率提高了將近一倍。而在進(jìn)行2層關(guān)聯(lián)挖掘方面,挖掘效率提升了一個(gè)數(shù)量級(jí)。BF-Apriori算法為海量數(shù)據(jù)庫的知識(shí)發(fā)現(xiàn)提供了一種高效而快速的算法。

圖4 二層關(guān)聯(lián)規(guī)則挖掘的算法執(zhí)行時(shí)間

[1]陳耿,朱玉全,楊鶴標(biāo),等.關(guān)聯(lián)規(guī)則挖掘中若干關(guān)鍵技術(shù)的研究[J].計(jì)算機(jī)研究與發(fā)展,2005,42(10)：1 785-1 789.

[2]孔令富,王晗,練秋生.一種基于關(guān)聯(lián)規(guī)則挖掘的組織數(shù)據(jù)方法[J].計(jì)算機(jī)工程,2006,32(21)：12-14.

[3]顏躍進(jìn),李舟軍,陳火旺.一種挖掘最大頻繁項(xiàng)集的深度優(yōu)先算法[J].計(jì)算機(jī)研究與發(fā)展,2005,42(3)：462-467.

[4]Azzedine Boukerche,Samer Samarah.A Novel Algorithm for Mining Association Rules in WirelessAd Hoc Sensor Networks[J].IEEE Transactions On Parallel And Distributed Systems,2008,19(7)：865-877.

[5]何海濤,呂士勇,田海燕.基于改進(jìn) Apriori算法的數(shù)據(jù)庫入侵檢測[J].計(jì)算機(jī)工程,2009,35(16)：154-158.

[6]宋余慶,朱玉全,孫志揮,等.基于FP-tree的最大頻繁項(xiàng)目集挖掘及更新算法[J].軟件學(xué)報(bào),2003,14(9)：1 586-1 592.