摘 要: 通過對Apriori算法基本原理和性能的研究分析,，針對算法存在的不足,，提出了一種更高效的基于對頻繁項(xiàng)集分組并行的挖掘算法。該算法把頻繁k-1項(xiàng)集按照一定規(guī)律分組,，每組頻繁k-1子項(xiàng)集直接產(chǎn)生頻繁k子項(xiàng)集,；再把每組產(chǎn)生的頻繁k子項(xiàng)集合起來,這樣每組不僅在自連接時減少了很多判斷連接嘗試，而且可以并行處理連接,、剪枝行為,，減少了等待時間，提高了查找頻繁項(xiàng)集的速度,。經(jīng)過實(shí)驗(yàn)證實(shí),，改進(jìn)后的算法在性能上有很大的提升。

關(guān)鍵詞: 數(shù)據(jù)挖掘,；關(guān)聯(lián)規(guī)則,；Apriori算法；分組,； 并行

       數(shù)據(jù)挖掘是指從數(shù)據(jù)庫的大量數(shù)據(jù)中提取出先前未知的,、具有潛在實(shí)際價值的,、隱含的信息[1]。關(guān)聯(lián)規(guī)則挖掘就是從海量的數(shù)據(jù)中尋找數(shù)據(jù)項(xiàng)間的關(guān)聯(lián)關(guān)系,。 

       關(guān)聯(lián)規(guī)則挖掘是由Agrawal等人于1993年首先提出[2],，之后又提出了著名的基于頻繁項(xiàng)集的Apriori算法[3-4]。關(guān)聯(lián)分析用來發(fā)現(xiàn)購物籃數(shù)據(jù)事務(wù)中各項(xiàng)之間的有趣現(xiàn)象,，目前主要被應(yīng)用于如科學(xué)數(shù)據(jù)分析,、生物信息學(xué)、醫(yī)療診斷和網(wǎng)頁分析等許多領(lǐng)域[5],。因此,，關(guān)聯(lián)規(guī)則挖掘被廣泛地研究。為了提高挖掘的效率,，近幾年國內(nèi)外學(xué)者不斷地對基于Apriori算法進(jìn)行改進(jìn)和創(chuàng)新,，提出了很多優(yōu)化的改進(jìn)算法[6-8]。

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

　     令I(lǐng)={i1,i2,…,id}是所有項(xiàng)的集合,，而T={t1,t2,…,tN}是所有事務(wù)的集合,。每一個事務(wù)ti包含的項(xiàng)集都是I的子集。在關(guān)聯(lián)規(guī)則的分析中,，包含多個項(xiàng)的集合被稱之為項(xiàng)集,。例如一個項(xiàng)集包含了k個項(xiàng)，則此項(xiàng)集被稱為k-項(xiàng)集[9],?？占遣话魏雾?xiàng)的項(xiàng)集。

關(guān)聯(lián)規(guī)則表達(dá)式X→Y,其中X和Y是不相交的項(xiàng)集,，即X∩Y=?準(zhǔn),。支持度(support)是T中同時包含X和Y的事務(wù)占的百分比。置信度(confidence)是T中同時包含X和Y的事務(wù)占包含X的事務(wù)的百分比,。項(xiàng)集的出現(xiàn)頻率是包含項(xiàng)集的事務(wù)數(shù),，稱為項(xiàng)集的支持度計(jì)數(shù)。支持度確定規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度,。如果項(xiàng)集I的支持度計(jì)數(shù)大于等于最小支持度閾值,，可以確定項(xiàng)集I是頻繁項(xiàng)集。支持度(s)度量形式為：

　    　S(X→Y)=N  (1)

       2 Apriori算法分析

　      Apriori算法是一種非常具有影響力的關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法,。它開創(chuàng)性地通過對最小支持度閾值的設(shè)置,，系統(tǒng)地控制了候選項(xiàng)數(shù)量幾何的增長。

　     該算法采用了寬度優(yōu)先且逐層搜索的迭代方法,，即當(dāng)?shù)趉次迭代時,，頻繁k-項(xiàng)集通過頻繁(k-1)-項(xiàng)集 Lk-1來關(guān)聯(lián)查找。第一次運(yùn)行迭代時,掃描事務(wù)數(shù)據(jù)庫所有項(xiàng)目,，找出事務(wù)數(shù)據(jù)庫中的所有項(xiàng)集構(gòu)成的候選1-項(xiàng)集C1,，然后根據(jù)設(shè)定的最小支持度閾值,，在C1中篩選出符合條件的項(xiàng)，構(gòu)成頻繁1-項(xiàng)集L1;第二次運(yùn)行迭代時,，用頻繁1-項(xiàng)集L1自連接產(chǎn)生候選項(xiàng),，并且掃描所有事務(wù)數(shù)據(jù)庫集合，得到C2中每一個項(xiàng)的支持度值,，然后通過最小支持度的閾值進(jìn)一步篩選出符合條件的頻繁2-項(xiàng)集L2,。一直這樣循環(huán)迭代下去，直到不能再產(chǎn)生頻繁項(xiàng)集為止,。

　      該算法核心方法主要通過連接(候選項(xiàng)集的產(chǎn)生)和剪枝兩個步驟來完成,。

       (1)連接。由前一次迭代發(fā)現(xiàn)的頻繁(k-1)-項(xiàng)集Lk-1直接產(chǎn)生新的候選k-項(xiàng)集Ck,。

　     (2)剪枝,。候選k-項(xiàng)集Ck是頻繁k-項(xiàng)集Lk的超集，且Ck中的項(xiàng)集不確定是否都是頻繁集,。剪枝一般分為兩步來進(jìn)行,。首先，根據(jù)Apriori的性質(zhì),，任何的非頻繁(k-1)-項(xiàng)集都不是頻繁k項(xiàng)集的子集,。考慮Ck,，即X={i1,i2,…,ik},。該算法首先需確定它所有的真子集X-{i1}(?坌j=1,2,…,k)必須都是頻繁的。如果其中一個真子集是非頻繁的,，則X將會被立即剪枝。這種方法能非常有效地減少在支持度計(jì)數(shù)過程中所要考慮的候選項(xiàng)集的數(shù)量,。繼而可以得到已經(jīng)被剪枝處理過的候選項(xiàng)集Ck′,。然后，掃描所有事務(wù)數(shù)據(jù)庫集合,，計(jì)算Ck′每一個候選項(xiàng)的支持度計(jì)數(shù),，刪除支持度計(jì)數(shù)小于支持度計(jì)數(shù)閾值的項(xiàng)集，從而得到Lk,。

　     由于Apriori算法主要通過這兩步來實(shí)現(xiàn),，為了能對該算法有更加清楚直觀的認(rèn)識，具體分析這個過程,，Lk-1自連接來產(chǎn)生新的Ck′,。令所有的項(xiàng)集中的項(xiàng)都按照一定的原則來排序。假設(shè)任意l1∈Lk-1,、l2∈Lk-1,、c1∈Ck,，c1′∈Ck。當(dāng)Lk-1進(jìn)行自連接時,，要判斷兩個頻繁項(xiàng)是否能夠連接,，如果l1[i]=l2[i](?坌i=1,2,…,k-2)，則可以連接產(chǎn)生項(xiàng)c1′,。根據(jù)Apriori的性質(zhì),，項(xiàng)c1′可以產(chǎn)生(k-1)個(k-1)-項(xiàng)子集，再判斷所有的(k-1)-項(xiàng)子集是否都在Lk-1中,。若有一個(k-1)-項(xiàng)子集不在Lk-1中,，則項(xiàng)c1′為非頻繁項(xiàng)，可以忽略此項(xiàng),；反之,，項(xiàng)c1′可以被確定為候選項(xiàng)c1。重復(fù)進(jìn)行以上所述的連接過程,，直到篩選產(chǎn)生所有候選k-項(xiàng)集Ck′為止,。然后再分析Ck′，依次對Ck′逐項(xiàng)掃描事務(wù)數(shù)據(jù)庫所有項(xiàng)目進(jìn)行支持度計(jì)算,，進(jìn)一步篩選出頻繁k項(xiàng)集Lk,。

       3 Apriori算法改進(jìn)

　     經(jīng)過對上面的情況深入分析發(fā)現(xiàn)，該算法Lk-1大部分的自連接是無用的,，且基本上絕大多數(shù)的判斷連接是不成立的,。假設(shè)Lk-1項(xiàng)集大小為N，則需要判斷連接的次數(shù)LN為：

        LN=∑n (2)

　      假定N=4,，根據(jù)式(2),，得出LN=3+2+1=6(次)。然后再對Ck′逐項(xiàng)掃描事務(wù)數(shù)據(jù)庫,，計(jì)算支持度,，這個過程需要排隊(duì)掃描，花費(fèi)大量的等待時間,?？紤]以上問題，本文對Lk-1產(chǎn)生Lk的過程提出一種基于對頻繁項(xiàng)集分組并行的改進(jìn)算法P-Apriori,。改進(jìn)算法是在經(jīng)典Apriori算法基礎(chǔ)上修改提出的,，效率上有很大的提升。下面將具體介紹改進(jìn)后算法的這部分改良方法,。

      首先在Lk-1自連接前對Lk-1進(jìn)行掃描,，按照一定規(guī)律分組，把Lk-1每一個頻繁項(xiàng)中的前第一項(xiàng)相同的分為一組。例如當(dāng)l1[1]=l2[1]時,，可以分為一組,。Lk-1自連接時，要判斷它們的前(k-2)個項(xiàng)是否相同,。如果它們的前第一個項(xiàng)都不相同,，那么這個連接肯定就不會成立。由此可以得出,，分組后的每組頻繁(k-1)-子項(xiàng)集都可以獨(dú)自進(jìn)行自連接,，且分組后的最多自連接總次數(shù)為PLN：   PLN=∑n+∑n+…+∑n  (3)

其中i為頻繁(k-1)-項(xiàng)集分組量，ni為每組的頻繁(k-1)-子項(xiàng)集長度,，n1+n2+…+ni=N,。

　     顯然分組后自連接總次數(shù)被壓縮了，即PLN的值要比LN小得多,。假定N=4,， 分為兩組，令兩組的頻繁(k-1)-子項(xiàng)集長度分別為n1=2,、n2=2,，則根據(jù)式(3)得出分組后的PLN=1+1=2(次)，比原來分組前LN=6(次)少了很多無用連接,。當(dāng)N處于一個較大值,，且分組量增加，這種優(yōu)勢將更加明顯,。由于分組后每組頻繁(k-1)-子項(xiàng)集可以并行處理,，或者說同步處理，且互不干擾地進(jìn)行連接,、剪枝行為,，不僅自連接效率可以進(jìn)一步提高，同時,，把原方法需要逐個根據(jù)Apriori性質(zhì)和掃描事務(wù)數(shù)據(jù)庫計(jì)算支持度的過程,，變成了可以并行進(jìn)行。如原來只能排成一個隊(duì),，現(xiàn)在可以排成多個隊(duì),。顯然,，分組后效率的提高是可觀的,。最后把每組頻繁(k-1)-子項(xiàng)集直接產(chǎn)生的頻繁k-子項(xiàng)集組合起來，即頻繁k-項(xiàng)集Lk,。改進(jìn)后的Apriori算法流程如圖1所示,。

       其實(shí)根據(jù)事務(wù)數(shù)據(jù)庫實(shí)際的需求，還可以在Lk-1分組后，把每組的頻繁(k-1)-子項(xiàng)集,，再將頻繁(k-1)-子項(xiàng)集中每一個頻繁項(xiàng)的前第二項(xiàng)相同的分為一組,。通過組內(nèi)再分組的方式，更加細(xì)化了頻繁項(xiàng)集,，使得判斷連接次數(shù)進(jìn)一步減少,，連接速度加快，繼而提高效率,。也可以直接把頻繁(k-1)-項(xiàng)集中每一個頻繁項(xiàng)lk-1中的前第一項(xiàng)和前第二項(xiàng)相同的分為一組,，這樣也能很好地達(dá)到分組的效果。

       4 實(shí)驗(yàn)驗(yàn)證及性能分析

　     通過對兩種算法的分析,，顯然在理論上改進(jìn)后的算法在很多方面效率會更高,。下面將通過具體實(shí)驗(yàn)來驗(yàn)證算法在改進(jìn)前后的性能比較。

　     本文使用Java語言分別來實(shí)現(xiàn)改進(jìn)前后的兩種算法,。在相同的實(shí)驗(yàn)環(huán)境下實(shí)現(xiàn)兩種算法的比較,，實(shí)驗(yàn)所用的具體環(huán)境配置為：處理器Intel(R)Core(TM)2 Duo CPU P8600,主頻2.40 GHz、內(nèi)存4 GB(實(shí)際可用2.96 GB),，操作系統(tǒng)Windows 7 旗艦版,，系統(tǒng)類型32位。利用系統(tǒng)上安裝的Eclipse開發(fā)軟件來進(jìn)行實(shí)驗(yàn)數(shù)據(jù)測試,。本文將提供8 000條事務(wù)數(shù)據(jù)庫,得到在不同最小支持度閾值下兩種算法的運(yùn)行時間,。實(shí)驗(yàn)結(jié)果如表1和圖2所示。

       由圖2可知,，在實(shí)驗(yàn)環(huán)境和事務(wù)數(shù)據(jù)庫所有項(xiàng)目不變的前提下,，得出了在不同閾值支持度下，兩種算法運(yùn)行時間的值,。顯然,，兩種算法在最小支持度閾值變小時，所需要的運(yùn)行時間都會成幾何的增長,。通過相互對比,，改進(jìn)后的P-Apriori算法比經(jīng)典Apriori算法運(yùn)行時間的增加更緩慢、不迅速,。在最小支持度的閾值相同的情況下,，改進(jìn)后的P-Apriori算法運(yùn)行時間更少，更加高效,。當(dāng)最小支持度的閾值較小時,，特別在閾值為0.15時，改進(jìn)后的P-Apriori算法效率的提升更加明顯,。當(dāng)最小支持度的閾值較大時,，由于兩種算法運(yùn)行的時間都比較少，所以在圖中難以辨別出來。但根據(jù)表1可知,，通過實(shí)際運(yùn)行數(shù)據(jù)比較,，還是可以發(fā)現(xiàn)改進(jìn)后的P-Apriori算法運(yùn)行時間比經(jīng)典Apriori算法的運(yùn)行時間要少，只是在圖2中不明顯,。

       本文通過對經(jīng)典Apriori算法理論研究和具體分析,，在該算法的理論基礎(chǔ)上進(jìn)行了一定修改和改進(jìn)，提出了基于對頻繁項(xiàng)集分組并行的挖掘算法P-Apriori,。通過實(shí)驗(yàn)表明,，改進(jìn)優(yōu)化后的P-Apriori算法不僅能并行處理數(shù)據(jù)，而且可以有效減少頻繁項(xiàng)集自連接次數(shù),，大大提高了頻繁項(xiàng)集生成的效率,，其在數(shù)據(jù)挖掘效率上比經(jīng)典Apriori算法更加高效實(shí)用。并且理論上,，隨著實(shí)驗(yàn)機(jī)器性能的提升或者采用分布式計(jì)算,，改進(jìn)優(yōu)化后的P-Apriori算法挖掘效率提升將更加明顯。

參考文獻(xiàn)

[1] 朱明. 數(shù)據(jù)挖掘[M]. 合肥: 中國科學(xué)技術(shù)大學(xué)出版社,2007.

[2] AGRAWAL R, IMIELINSKI T, SWAMI A. Database min-ing: a performance perspective[J]. IEEE Transactions on Knowledge and Data Engineering,1993,5(6):914-925.

[3] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules[C].Santiago, Chile: Proceeding of the 20th International Conference on Very Large Databases, 1994:487-499.

[4] AGARWAL C C, YU P S. Mining large itemsets for asso-ciation rules[J].Data Engineering Bulletin,1998,21(1):22-31.

[5] 吳昊, 李軍國. 基于關(guān)聯(lián)規(guī)則理論的道路交通事故數(shù)據(jù)挖掘模型[J].電子技術(shù)應(yīng)用, 2009,35(2):139-143.

[6] AGARWAL R C, SHAFER J C. Parallel mining of associ-ation rules[J]. IEEE Transactions on Knowledge and Data Engineering,1998,8(6):962-969.

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

[8] 肖冬榮, 楊磊. 基于遺傳算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘[J]. 通信技術(shù),2010,43(01):205-207.

[9] TAN P N, STEINBACH M,KUMAR V. 數(shù)據(jù)挖掘?qū)д?完整版)[M].范明,范宏建,譯.北京:人民郵電出版社,