摘 要: 通過對(duì)Apriori算法基本原理和性能的研究分析，針對(duì)算法存在的不足，提出了一種更高效的基于對(duì)頻繁項(xiàng)集分組并行的挖掘算法。該算法把頻繁k-1項(xiàng)集按照一定規(guī)律分組，每組頻繁k-1子項(xiàng)集直接產(chǎn)生頻繁k子項(xiàng)集；再把每組產(chǎn)生的頻繁k子項(xiàng)集合起來,這樣每組不僅在自連接時(shí)減少了很多判斷連接嘗試，而且可以并行處理連接、剪枝行為，減少了等待時(shí)間，提高了查找頻繁項(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í)際價(jià)值的、隱含的信息[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é)者不斷地對(duì)基于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ù)的集合。每一個(gè)事務(wù)ti包含的項(xiàng)集都是I的子集。在關(guān)聯(lián)規(guī)則的分析中，包含多個(gè)項(xiàng)的集合被稱之為項(xiàng)集。例如一個(gè)項(xiàng)集包含了k個(gè)項(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中同時(shí)包含X和Y的事務(wù)占的百分比。置信度(confidence)是T中同時(shí)包含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)性地通過對(duì)最小支持度閾值的設(shè)置，系統(tǒng)地控制了候選項(xiàng)數(shù)量幾何的增長。

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

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

       (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)必須都是頻繁的。如果其中一個(gè)真子集是非頻繁的，則X將會(huì)被立即剪枝。這種方法能非常有效地減少在支持度計(jì)數(shù)過程中所要考慮的候選項(xiàng)集的數(shù)量。繼而可以得到已經(jīng)被剪枝處理過的候選項(xiàng)集Ck′。然后，掃描所有事務(wù)數(shù)據(jù)庫集合，計(jì)算Ck′每一個(gè)候選項(xiàng)的支持度計(jì)數(shù)，刪除支持度計(jì)數(shù)小于支持度計(jì)數(shù)閾值的項(xiàng)集，從而得到Lk。

　     由于Apriori算法主要通過這兩步來實(shí)現(xiàn)，為了能對(duì)該算法有更加清楚直觀的認(rèn)識(shí)，具體分析這個(gè)過程，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)行自連接時(shí)，要判斷兩個(gè)頻繁項(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)個(gè)(k-1)-項(xiàng)子集，再判斷所有的(k-1)-項(xiàng)子集是否都在Lk-1中。若有一個(gè)(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′，依次對(duì)Ck′逐項(xiàng)掃描事務(wù)數(shù)據(jù)庫所有項(xiàng)目進(jìn)行支持度計(jì)算，進(jìn)一步篩選出頻繁k項(xiàng)集Lk。

       3 Apriori算法改進(jìn)

　     經(jīng)過對(duì)上面的情況深入分析發(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(次)。然后再對(duì)Ck′逐項(xiàng)掃描事務(wù)數(shù)據(jù)庫，計(jì)算支持度，這個(gè)過程需要排隊(duì)掃描，花費(fèi)大量的等待時(shí)間。考慮以上問題，本文對(duì)Lk-1產(chǎn)生Lk的過程提出一種基于對(duì)頻繁項(xiàng)集分組并行的改進(jìn)算法P-Apriori。改進(jìn)算法是在經(jīng)典Apriori算法基礎(chǔ)上修改提出的，效率上有很大的提升。下面將具體介紹改進(jìn)后算法的這部分改良方法。

      首先在Lk-1自連接前對(duì)Lk-1進(jìn)行掃描，按照一定規(guī)律分組，把Lk-1每一個(gè)頻繁項(xiàng)中的前第一項(xiàng)相同的分為一組。例如當(dāng)l1[1]=l2[1]時(shí)，可以分為一組。Lk-1自連接時(shí)，要判斷它們的前(k-2)個(gè)項(xiàng)是否相同。如果它們的前第一個(gè)項(xiàng)都不相同，那么這個(gè)連接肯定就不會(huì)成立。由此可以得出，分組后的每組頻繁(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處于一個(gè)較大值，且分組量增加，這種優(yōu)勢(shì)將更加明顯。由于分組后每組頻繁(k-1)-子項(xiàng)集可以并行處理，或者說同步處理，且互不干擾地進(jìn)行連接、剪枝行為，不僅自連接效率可以進(jìn)一步提高，同時(shí)，把原方法需要逐個(gè)根據(jù)Apriori性質(zhì)和掃描事務(wù)數(shù)據(jù)庫計(jì)算支持度的過程，變成了可以并行進(jìn)行。如原來只能排成一個(gè)隊(duì)，現(xiàn)在可以排成多個(gè)隊(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)集中每一個(gè)頻繁項(xiàng)的前第二項(xiàng)相同的分為一組。通過組內(nèi)再分組的方式，更加細(xì)化了頻繁項(xiàng)集，使得判斷連接次數(shù)進(jìn)一步減少，連接速度加快，繼而提高效率。也可以直接把頻繁(k-1)-項(xiàng)集中每一個(gè)頻繁項(xiàng)lk-1中的前第一項(xiàng)和前第二項(xiàng)相同的分為一組，這樣也能很好地達(dá)到分組的效果。

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

　     通過對(duì)兩種算法的分析，顯然在理論上改進(jìn)后的算法在很多方面效率會(huì)更高。下面將通過具體實(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ù)測(cè)試。本文將提供8 000條事務(wù)數(shù)據(jù)庫,得到在不同最小支持度閾值下兩種算法的運(yùn)行時(shí)間。實(shí)驗(yàn)結(jié)果如表1和圖2所示。

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

       本文通過對(duì)經(jīng)典Apriori算法理論研究和具體分析，在該算法的理論基礎(chǔ)上進(jìn)行了一定修改和改進(jìn)，提出了基于對(duì)頻繁項(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].范明,范宏建,譯.北京:人民郵電出版社,