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

關鍵詞: 數據挖掘；關聯規則；Apriori算法；分組； 并行

       數據挖掘是指從數據庫的大量數據中提取出先前未知的、具有潛在實際價值的、隱含的信息[1]。關聯規則挖掘就是從海量的數據中尋找數據項間的關聯關系。 

       關聯規則挖掘是由Agrawal等人于1993年首先提出[2]，之后又提出了著名的基于頻繁項集的Apriori算法[3-4]。關聯分析用來發現購物籃數據事務中各項之間的有趣現象，目前主要被應用于如科學數據分析、生物信息學、醫療診斷和網頁分析等許多領域[5]。因此，關聯規則挖掘被廣泛地研究。為了提高挖掘的效率，近幾年國內外學者不斷地對基于Apriori算法進行改進和創新，提出了很多優化的改進算法[6-8]。

       1 關聯規則概念

　     令I={i1,i2,…,id}是所有項的集合，而T={t1,t2,…,tN}是所有事務的集合。每一個事務ti包含的項集都是I的子集。在關聯規則的分析中，包含多個項的集合被稱之為項集。例如一個項集包含了k個項，則此項集被稱為k-項集[9]。空集是不包含任何項的項集。

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

　    　S(X→Y)=N  (1)

       2 Apriori算法分析

　      Apriori算法是一種非常具有影響力的關聯規則頻繁項集的算法。它開創性地通過對最小支持度閾值的設置，系統地控制了候選項數量幾何的增長。

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

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

       (1)連接。由前一次迭代發現的頻繁(k-1)-項集Lk-1直接產生新的候選k-項集Ck。

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

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

       3 Apriori算法改進

　     經過對上面的情況深入分析發現，該算法Lk-1大部分的自連接是無用的，且基本上絕大多數的判斷連接是不成立的。假設Lk-1項集大小為N，則需要判斷連接的次數LN為：

        LN=∑n (2)

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

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

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

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

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

       4 實驗驗證及性能分析

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

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

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

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

參考文獻

[1] 朱明. 數據挖掘[M]. 合肥: 中國科學技術大學出版社,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] 吳昊, 李軍國. 基于關聯規則理論的道路交通事故數據挖掘模型[J].電子技術應用, 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 算法的三種優化方法[J]. 計算機工程與應用,2004,40(36):190-192.

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

[9] TAN P N, STEINBACH M,KUMAR V. 數據挖掘導論(完整版)[M].范明,范宏建,譯.北京:人民郵電出版社,