《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 嵌入式技術(shù) > 設(shè)計(jì)應(yīng)用 > 基于垂直分布方法的關(guān)聯(lián)規(guī)則算法及改進(jìn)
基于垂直分布方法的關(guān)聯(lián)規(guī)則算法及改進(jìn)
來源:微型機(jī)與應(yīng)用2011年第8期
楊振華
(西安文理學(xué)院 計(jì)算機(jī)科學(xué)系,, 陜西 西安710065)
摘要: 數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則挖掘近些年一直是人們研究的熱點(diǎn),。但是關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法Apriori存在著挖掘效率低,、系統(tǒng)開銷大等問題。AprioriTid,、DIC等算法,也僅從某一方面進(jìn)行了改進(jìn)。針對(duì)上述問題,,提出了一種新的改進(jìn)算法,新算法從三大方面對(duì)原有的算法進(jìn)行了改進(jìn),,以此提高算法的效率,,降低系統(tǒng)的開銷,。
Abstract:
Key words :

摘  要: 數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則挖掘近些年一直是人們研究的熱點(diǎn)。但是關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法Apriori存在著挖掘效率低,、系統(tǒng)開銷大等問題,。AprioriTidDIC等算法,,也僅從某一方面進(jìn)行了改進(jìn),。針對(duì)上述問題,提出了一種新的改進(jìn)算法,,新算法從三大方面對(duì)原有的算法進(jìn)行了改進(jìn),,以此提高算法的效率,降低系統(tǒng)的開銷,。
關(guān)鍵詞: 數(shù)據(jù)挖掘;關(guān)聯(lián)規(guī)則; Apriori; AprioriTid; DIC

    數(shù)據(jù)庫中大量的數(shù)據(jù)與數(shù)據(jù)之間存在著某種聯(lián)系,,這種數(shù)據(jù)之間的聯(lián)系就屬于一種重要的知識(shí),也是進(jìn)行數(shù)據(jù)挖掘的對(duì)象,,即關(guān)聯(lián)規(guī)則挖掘[1],。在眾多的關(guān)聯(lián)規(guī)則挖掘算法中最著名的是Apriori算法[2]。它的基本思想是使用一種逐層搜索的迭代算法,。但是Apriori算法也有明顯的缺點(diǎn):每次都會(huì)產(chǎn)生大量的候選頻繁項(xiàng)集,,而且候選頻繁項(xiàng)集呈指數(shù)級(jí)增長(zhǎng)。每產(chǎn)生一個(gè)頻繁項(xiàng)目集就需要掃描一次完整的數(shù)據(jù)庫,。這些都需要耗費(fèi)巨大的系統(tǒng)資源而且算法的執(zhí)行速度,、效率也比較低。因此人們提出了許多改進(jìn)的Apriori算法,,本文吸取前人的經(jīng)驗(yàn)提出了一種新的改進(jìn)Apriori算法,,稱為Apriori-Evo算法。
1 Apriori算法分析
     Apriori算法的基本步驟是:首先掃描事務(wù)數(shù)據(jù)庫D中的事務(wù),,統(tǒng)計(jì)各個(gè)項(xiàng)目出現(xiàn)的次數(shù)來產(chǎn)生頻繁項(xiàng)目集L1,然后由L1×L1進(jìn)行連接運(yùn)算生成候選2-項(xiàng)集C2,,掃描數(shù)據(jù)庫統(tǒng)計(jì)各個(gè)候選2-項(xiàng)集出現(xiàn)的次數(shù),確定其中的頻繁2-項(xiàng)集L2。再由L2×L2進(jìn)行連接運(yùn)算產(chǎn)生候選3-項(xiàng)集C3,,一直反復(fù)進(jìn)行這個(gè)過程生成頻繁k-項(xiàng)集Lk,,直到無法再生成頻繁項(xiàng)目集為止。

 



     代碼中apriori_gen( )函數(shù)[3]主要完成兩個(gè)動(dòng)作:連接和剪枝運(yùn)算,。Lk-1與Lk-1進(jìn)行連接生成候選頻繁項(xiàng)集,。然后剪枝部分利用Apriori的性質(zhì)刪除掉包含非頻繁子集的候選。
     Apriori算法的主要缺點(diǎn)是會(huì)產(chǎn)生大量的候選項(xiàng)集,,如果頻繁1-項(xiàng)集有10 000個(gè),,則候選2-項(xiàng)集的個(gè)數(shù)將超過10 000 000個(gè),算法實(shí)現(xiàn)時(shí),,大量的候選2-項(xiàng)集都被存放在哈希樹中,,對(duì)它們的統(tǒng)計(jì)和測(cè)試所需要的開銷會(huì)很大;每產(chǎn)生一個(gè)頻繁項(xiàng)目集就需要將整個(gè)事務(wù)數(shù)據(jù)庫掃描一遍,,大大降低了系統(tǒng)I/O效率。
2 對(duì)Apriori算法的改進(jìn)
 關(guān)聯(lián)規(guī)則具有如下性質(zhì):
 (1)對(duì)于項(xiàng)目集X和它的任意子集Y,,如果X是頻繁的,,則它的子集Y一定也是頻繁的。
   (2)對(duì)于項(xiàng)目集X和它的任意子集Y,,如果Y是非頻繁項(xiàng)目集,,則X也一定不是頻繁項(xiàng)目集。
   (3)X是k維項(xiàng)目集,,如果頻繁項(xiàng)目集Lk-1中包含的X的子集個(gè)數(shù)小于k,則X不可能是頻繁項(xiàng)目集,。
   利用它的性質(zhì)對(duì)Apriori算法從以下三方面進(jìn)行了改進(jìn)。
   (1)在剪枝階段減少掃描Lk-1的次數(shù)
   進(jìn)行剪枝的工作原理是:根據(jù)關(guān)聯(lián)規(guī)則的性質(zhì),,Ck中的一個(gè)項(xiàng)集如果是頻繁項(xiàng)集,那么它一定有K個(gè)k-1項(xiàng)頻繁子集,,且這K個(gè)k-1項(xiàng)頻繁子集一定都在Lk-1當(dāng)中,。因此以往的對(duì)Ck的剪枝過程都是先取出一個(gè)候選k項(xiàng)集,,然后產(chǎn)生它的K個(gè)k-1項(xiàng)子集,,再掃描一次Lk-1查看這K個(gè)k-1項(xiàng)子集是否都在Lk-1中,如果不是則剪掉這個(gè)候選k項(xiàng)集,,如此循環(huán),。如果產(chǎn)生m條候選k項(xiàng)集,就需掃描Lk-1項(xiàng)集m次,。然而頻繁項(xiàng)集具有性質(zhì)3[4],。所以不需要掃描Lk-1次。首先進(jìn)行Lk-1×Lk-1的連接運(yùn)算生成所有的候選項(xiàng)集Ck,然后取出Lk-1中的第一個(gè)頻繁k-1項(xiàng)集,,查看該k-1項(xiàng)集是Ck中哪些k項(xiàng)集的子集,,如果是子集,則對(duì)相應(yīng)的k項(xiàng)集進(jìn)行計(jì)數(shù),。然后再從Lk-1中取出第二個(gè)頻繁k-1項(xiàng)集,,再到Ck中去查看它是哪些k項(xiàng)集的子集,直到Lk-1中的各個(gè)項(xiàng)集都比對(duì)完成,。最后,,查看Ck中的每個(gè)k項(xiàng)集,如果它的計(jì)數(shù)小于k,,則它不可能是頻繁k項(xiàng)集,,需要?jiǎng)h除。因?yàn)轭l繁k項(xiàng)集一定有k個(gè)k-1項(xiàng)子集存放在Lk-1中,。這樣整個(gè)剪枝步驟只需要掃描Lk-1一次,,提高了剪枝步驟的效率和開銷,。

    (3)對(duì)用于連接的頻繁項(xiàng)目集進(jìn)行精簡(jiǎn),減少無用候選的產(chǎn)生,。
    對(duì)于產(chǎn)生的頻繁項(xiàng)目集Lk-1,Apriori算法直接用它連接產(chǎn)生候選頻繁項(xiàng)目集Ck,。但實(shí)際上Lk-1中的有些項(xiàng)目集已經(jīng)對(duì)產(chǎn)生Lk不起作用了,包含這些項(xiàng)目集的候選k-項(xiàng)集一定不是頻繁的,,因此可以對(duì)頻繁項(xiàng)目集Lk-1進(jìn)行精簡(jiǎn),。
    根據(jù)頻繁項(xiàng)集的性質(zhì)[7],當(dāng)要用Lk-1連接產(chǎn)生Ck時(shí),首先統(tǒng)計(jì)Lk-1中各個(gè)項(xiàng)目出現(xiàn)的次數(shù),,如果該項(xiàng)目出現(xiàn)的次數(shù)小于k-1,,則該項(xiàng)目所在的項(xiàng)目集不用來鏈接生成Ck[8]。

   
    實(shí)驗(yàn)結(jié)果表明,,改進(jìn)的Apriori-Evo算法確實(shí)在關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的速度和效率方面有很大的提高,,而且隨著事務(wù)數(shù)據(jù)的增多,提升效果更加明顯,。
    新的算法從三個(gè)方面對(duì)原有的算法進(jìn)行了改進(jìn),,減少了產(chǎn)生的候選頻繁項(xiàng)集Ck中項(xiàng)集的數(shù)據(jù),,也減少了剪枝過程中的運(yùn)算次數(shù),,在統(tǒng)計(jì)支持度階段減少了需要掃描的數(shù)據(jù)庫中的事務(wù)數(shù)。而且計(jì)算機(jī)進(jìn)行向量運(yùn)算和位運(yùn)算速度更快,,程序也會(huì)更容易實(shí)現(xiàn),。實(shí)驗(yàn)證明,,新算法在系統(tǒng)的開銷和時(shí)間效率上都有很大的提高,。
參考文獻(xiàn)
[1] HAN J,KAMBER M.數(shù)據(jù)挖掘:概念與技術(shù)[M]. 范明,孟小峰,譯.北京:機(jī)械工業(yè)出版社,,2001.
[2] AGRAWAL R, IMIEL NSKI T , SWAM I A. Mining association rules between sets of items in large database[A]. In Proc. of the ACM SIGMOD Intl Conf. on Management of Data[C]. Washington D. C. , 1993:207-216.
[3] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules[C].Morgan Kaufmann, San Francisco, CA: Proceedings of the 24th International Conference on Very  Large Databases,1998:478-499.
[4] 李緒成,,王保保. 挖掘關(guān)聯(lián)規(guī)則中Apriori 算法的一種改進(jìn)[J]. 計(jì)算機(jī)工程,2002,,7(28):104-105.
[5] 羅芳,,李志亮.一種基于壓縮矩陣的Apriori改進(jìn)算法[J]. 科技資訊,2010(4):19.
[6] 劉以安,,羊斌.關(guān)聯(lián)規(guī)則挖掘中對(duì)Apriori算法的一種改進(jìn)研究[J].計(jì)算機(jī)應(yīng)用,,2007,27(2):418-420.
[7] 盛立,,劉希玉,,高明.挖掘關(guān)聯(lián)規(guī)則中AprioriTid算法的改進(jìn)[J].山東師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2005,,20(4): 20-22.
[8] 葉福蘭,,施忠興.Apriori算法的改進(jìn)及應(yīng)用[J].現(xiàn)代計(jì)算機(jī),,2009(9):95-126.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載,。