楊振華

（西安文理學(xué)院 計(jì)算機(jī)科學(xué)系，陜西 西安710065）

數(shù)據(jù)庫(kù)中大量的數(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ù)庫(kù)。這些都需要耗費(fèi)巨大的系統(tǒng)資源而且算法的執(zhí)行速度、效率也比較低。因此人們提出了許多改進(jìn)的Apriori算法，本文吸取前人的經(jīng)驗(yàn)提出了一種新的改進(jìn)Apriori算法，稱(chēng)為Apriori-Evo算法。

1 Apriori算法分析

Apriori算法的基本步驟是：首先掃描事務(wù)數(shù)據(jù)庫(kù)D中的事務(wù)，統(tǒng)計(jì)各個(gè)項(xiàng)目出現(xiàn)的次數(shù)來(lái)產(chǎn)生頻繁項(xiàng)目集L1,然后由 L1×L1進(jìn)行連接運(yùn)算生成候選 2-項(xiàng)集 C2，掃描數(shù)據(jù)庫(kù)統(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è)過(guò)程生成頻繁k-項(xiàng)集Lk，直到無(wú)法再生成頻繁項(xiàng)目集為止。

Apriori的算法描述如下：

主算法逐層迭代產(chǎn)生 L1→C2→L2→C3→L3…直到Lk=φ為止。到此所有的頻繁項(xiàng)目集都找到了。

procedure aproiri_gen(Lk-1:frequent(k-1)-itemset;min_sup:support)

代碼中 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ù)將超過(guò)10 000 000個(gè)，算法實(shí)現(xiàn)時(shí)，大量的候選2-項(xiàng)集都被存放在哈希樹(shù)中，對(duì)它們的統(tǒng)計(jì)和測(cè)試所需要的開(kāi)銷(xiāo)會(huì)很大;每產(chǎn)生一個(gè)頻繁項(xiàng)目集就需要將整個(gè)事務(wù)數(shù)據(jù)庫(kù)掃描一遍，大大降低了系統(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的剪枝過(guò)程都是先取出一個(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ù)。然后再?gòu)腖k-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一次，提高了剪枝步驟的效率和開(kāi)銷(xiāo)。

(2)統(tǒng)計(jì)階段減少掃描的工作量

對(duì)于數(shù)據(jù)庫(kù)D中的事務(wù)數(shù)據(jù)先把它轉(zhuǎn)換成一個(gè)矩陣。矩陣結(jié)構(gòu)[5]如下,其中T為事務(wù)，I為項(xiàng)目集：

矩陣的一列對(duì)應(yīng)數(shù)據(jù)庫(kù)D中的一條事務(wù)記錄，例如記錄 T1：I1，I2，I5和 T2：I2，I3，I5對(duì)應(yīng)的矩陣。

向量 Di與向量 Dj的內(nèi)積運(yùn)算記為：[Di,Dj]=di1×dj1+di2×dj2+…+din×djn。

對(duì)于Apriori算法過(guò)程中產(chǎn)生的候選2-項(xiàng)集C2中的一個(gè)項(xiàng)目集（I2,I3）,以往需要掃描數(shù)據(jù)庫(kù) D中每一條事務(wù)來(lái)統(tǒng)計(jì)（I2,I3）的支持度?，F(xiàn)在只需要對(duì)行向量D2與D3做內(nèi)積運(yùn)算就可以了。 它們內(nèi)積[6]的和就是（I2,I3）的支持度。 對(duì)于項(xiàng)目集（I1，I2，I5，I7）只需要對(duì) D1、D2、D5、D7這四個(gè)行向量相應(yīng)的列元素做與運(yùn)算，然后各個(gè)列的運(yùn)算結(jié)果相加，就得到了該項(xiàng)目集的支持度。

(3)對(duì)用于連接的頻繁項(xiàng)目集進(jìn)行精簡(jiǎn)，減少無(wú)用候選的產(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)目集不用來(lái)鏈接生成Ck[8]。

例如：有頻繁 3-項(xiàng)目集{I1,I2,I3}，{I1,I2,I5}，{I1,I3,I4}，{I1,I3,I5}，{I1,I3,I6}，{I1,I4,I5}，{I1,I4,I6}。 如果直接用它們進(jìn)行連接產(chǎn)生的候選 4-項(xiàng)集為：{I1,I2,I3,I5}，{I1,I3,I4,I5}，{I1,I3,I4,I6}，{I1,I3,I5,I6}，{I1,I4,I5,I6}共 5 個(gè)。

按照統(tǒng)計(jì)頻繁 3-項(xiàng)集中 I1出現(xiàn) 7次，I22次，I34次，I43次，I53次，I62次。在頻繁4-項(xiàng)集中的每一個(gè)項(xiàng)目在頻繁3-項(xiàng)目集中應(yīng)該出現(xiàn)3次，所以應(yīng)該從頻繁 3-項(xiàng)目集中去除掉：包含 I2、I6(出現(xiàn)次數(shù)小于 3)的項(xiàng)目集，只保留{I1,I3,I4}，{I1,I3,I5}，{I1,I4,I5}。 而它們產(chǎn)生的Ck為{I1,I3,I4，I5}只有1個(gè)。這樣新產(chǎn)生的候選頻繁項(xiàng)集的數(shù)據(jù)將大幅減少。

綜上所述，從三個(gè)方面改進(jìn)了Apriori算法，以此大幅度提高了數(shù)據(jù)挖掘的效率。新算法的描述如下：

3 實(shí)驗(yàn)結(jié)果分析

在由Lk-1連接產(chǎn)生Ck階段Apriori算法,每產(chǎn)生一個(gè)Ck的項(xiàng)目集就掃描一次Lk-1，一共需要進(jìn)行|Ck||Lk-1|k次運(yùn)算，而Apriori-Evo算法只需要掃描 Lk-1一次，只需要進(jìn)行|Lk-1||Ck|次運(yùn)算。在掃描事務(wù)數(shù)據(jù)庫(kù)D統(tǒng)計(jì)各個(gè)候選頻繁項(xiàng)集的支持度階段，Apriori算法每產(chǎn)生一個(gè)頻繁項(xiàng)集{I1,I2…}就需掃描整個(gè)數(shù)據(jù)庫(kù)一次。Apriori-Evo算法每產(chǎn)生一個(gè)頻繁項(xiàng)集{I1,I2…}只需要 I1、I2所在的行做運(yùn)算即可。最后，由Lk連接產(chǎn)生Ck+1階段，Apriori算法直接用Lk進(jìn)行連接。而Apriori-Evo算法先刪除掉Lk中對(duì)產(chǎn)生Lk+1沒(méi)有作用的項(xiàng)目，縮小了產(chǎn)生的Ck體積。本文從三個(gè)方面對(duì)原有算法進(jìn)行了改進(jìn)。最后，通過(guò)實(shí)驗(yàn)將改進(jìn)的Apriori算法與原來(lái)的算法進(jìn)行了比較，從數(shù)據(jù)庫(kù)中分別提取 1 000、2 000、3 000、4 000條記錄進(jìn)行數(shù)據(jù)挖掘，最小支持度設(shè)為25%，運(yùn)行時(shí)間如圖1所示。

實(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ù)，也減少了剪枝過(guò)程中的運(yùn)算次數(shù)，在統(tǒng)計(jì)支持度階段減少了需要掃描的數(shù)據(jù)庫(kù)中的事務(wù)數(shù)。而且計(jì)算機(jī)進(jìn)行向量運(yùn)算和位運(yùn)算速度更快，程序也會(huì)更容易實(shí)現(xiàn)。實(shí)驗(yàn)證明，新算法在系統(tǒng)的開(kāi)銷(xiāo)和時(shí)間效率上都有很大的提高。

[1]HAN J,KAMBER M.數(shù)據(jù)挖掘:概念與技術(shù)[M].范明，孟小峰,譯.北京:機(jī)械工業(yè)出版社，2001.

[2]AGRAWAL R,IMIEL NSKI T,SWAM I A.Mining asso-ciation 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.