Apriori算法改進(jìn)研究及實(shí)現(xiàn)-

1、Apriori算法改進(jìn)研究及實(shí)現(xiàn)摘要: 通過對Apriori算法基本原理和性能的研究分析,針對算法存在的不足,提出了一種更高效的基于對頻繁項(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ī)則挖

2、掘就是從海量的數(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ù)的集合。每一個(gè)事務(wù)ti包含的項(xiàng)集都是I的子集。在關(guān)聯(lián)規(guī)則的分析中,包含多個(gè)項(xiàng)的

3、集合被稱之為項(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á)式XY,其中X和Y是不相交的項(xiàng)集,即XY=?準(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(XY=N (12 Apriori算法分析Apriori算法是一種非常具有影響力的關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。它開

4、創(chuàng)性地通過對最小支持度閾值的設(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)集為止。該算法核心方法主要

5、通過連接(候選項(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將會被立即剪枝。這種方法能非常有效地減少在支持度計(jì)數(shù)過程中所要考慮的候選項(xiàng)集的數(shù)量。繼而可以得到已經(jīng)被剪枝處理過的候選項(xiàng)集Ck。然后,

6、掃描所有事務(wù)數(shù)據(jù)庫集合,計(jì)算Ck每一個(gè)候選項(xiàng)的支持度計(jì)數(shù),刪除支持度計(jì)數(shù)小于支持度計(jì)數(shù)閾值的項(xiàng)集,從而得到Lk。由于Apriori算法主要通過這兩步來實(shí)現(xiàn),為了能對該算法有更加清楚直觀的認(rèn)識,具體分析這個(gè)過程,Lk-1自連接來產(chǎn)生新的Ck。令所有的項(xiàng)集中的項(xiàng)都按照一定的原則來排序。假設(shè)任意l1Lk-1、l2Lk-1、c1Ck,c1Ck。當(dāng)Lk-1進(jìn)行自連接時(shí),要判斷兩個(gè)頻繁項(xiàng)是否能夠連接,如果l1i=l2i(?坌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)子集不

7、在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ì)算支持度,這個(gè)過程需要排隊(duì)掃描,花費(fèi)大量的等待時(shí)間?？紤]以上問題

8、,本文對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每一個(gè)頻繁項(xiàng)中的前第一項(xiàng)相同的分為一組。例如當(dāng)l11=l21時(shí),可以分為一組。Lk-1自連接時(shí),要判斷它們的前(k-2個(gè)項(xiàng)是否相同。如果它們的前第一個(gè)項(xiàng)都不相同,那么這個(gè)連接肯定就不會成立。由此可以得出,分組后的每組頻繁(k-1-子項(xiàng)集都可以獨(dú)自進(jìn)行自連接,且分組后的最多自連接總次數(shù)為PLN:PLN=n+n+n (3其中i為

9、頻繁(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)勢將更加明顯。由于分組后每組頻繁(k-1-子項(xiàng)集可以并行處理,或者說同步處理,且互不干擾地進(jìn)行連接、剪枝行為,不僅自連接效率可以進(jìn)一步提高,同時(shí),把原方法需要逐個(gè)根據(jù)Apriori性質(zhì)和掃描事務(wù)數(shù)據(jù)庫計(jì)算支持度的過程,變成了可以并行進(jìn)行。如原來

10、只能排成一個(gè)隊(duì),現(xiàn)在可以排成多個(gè)隊(duì)。顯然,分組后效率的提高是可觀的。最后把每組頻繁(k-1-子項(xiàng)集直接產(chǎn)生的頻繁k-子項(xiàng)集組合起來,即頻繁k-項(xiàng)集Lk。改進(jìn)后的Apriori算法流程。其實(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)證及性能分析通過對兩種算法的分析,顯然在

11、理論上改進(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(RCore(TM2 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í)間。實(shí)驗(yàn)結(jié)果如表1和圖2所示。由圖2可知,在實(shí)驗(yàn)環(huán)境和事務(wù)數(shù)據(jù)庫所有項(xiàng)目不變的前提下

12、,得出了在不同閾值支持度下,兩種算法運(yùn)行時(shí)間的值。顯然,兩種算法在最小支持度閾值變小時(shí),所需要的運(yùn)行時(shí)間都會成幾何的增長。通過相互對比,改進(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中不明顯。本文通過對經(jīng)典Apriori算法理論研究和具體分析,在該算法的理論基礎(chǔ)