張衛(wèi)華

（江蘇大學(xué) 計算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013）

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中的一個重要的問題。而apriori算法是挖掘關(guān)聯(lián)規(guī)則的經(jīng)典算法。主要步驟是：通過掃描數(shù)據(jù)庫得到頻繁1-項集，然后頻繁1-項集組合候選2-項集，然后對候選項2-項集剪枝，通過掃描數(shù)據(jù)庫得到支持度計數(shù)來生成頻繁2-項集。以此類推，直到?jīng)]有頻繁項集產(chǎn)生，然后將頻繁項集生成關(guān)聯(lián)規(guī)則[1]。這樣一來，這個算法中有兩個重要的問題：大量的候選項集產(chǎn)生和多次掃描數(shù)據(jù)庫。

針對以上兩個問題，文獻(xiàn) [6]中使用的是基于矩陣的apriori算法,此算法將事務(wù)集以矩陣的形式保存到內(nèi)存中，通過計算矩陣列向量中1出現(xiàn)的個數(shù)然后與最小支持度計數(shù)比較從而得到頻繁1-項集，在產(chǎn)生頻繁k-項集的時候(k>1),首先對頻繁k-1-項集進(jìn)行連接后得到候選k-項集，將對應(yīng)的k個矩陣列進(jìn)行位與運算生成列向量，計算列向量中1出現(xiàn)的個數(shù)，與最小支持度計數(shù)比較判斷而產(chǎn)生頻繁項集，此算法只需要掃描一次數(shù)據(jù)庫，而且通過減少無用連接而減少了候選項集的產(chǎn)生。文獻(xiàn)[2]、[7]采取的是直接產(chǎn)生頻繁項集,從而減少了連接和剪枝時間，即直接按順序?qū)仃噆個列進(jìn)行位與運算得到列向量，對列向量1出現(xiàn)的個數(shù)進(jìn)行計數(shù)然后和最小支持度計數(shù)比較產(chǎn)生頻繁k-項集，此算法通過刪減矩陣的列來減少位與運算的次數(shù)，而刪減列前需要對頻繁k-1-項集的查找，即判斷頻繁項集中的項Ij在所有頻繁k-1-項集中出現(xiàn)的次數(shù)是否小于k-1，然后再刪除此項對應(yīng)對應(yīng)的矩陣列。文獻(xiàn)[3]、[4]、[5]采取的方法是通過查找每一個頻繁k-1-項集而得出此項在所有的頻繁k-1-項集中出現(xiàn)次數(shù)，然后再判斷是否需要刪除此項所對應(yīng)的矩陣列，這樣會導(dǎo)致多余的掃描。因此本文針對此問題提出一種新的查找方法，利用頻繁項集的有序性，不一定要查找所有的頻繁k-1-項集，利用矩陣的刪除性質(zhì)，并不要得出每一項的在頻繁k-1-項集的計數(shù),而是一旦發(fā)現(xiàn)在頻繁k-1的計數(shù)等于k-1則進(jìn)入下一個項的計數(shù)，從而節(jié)約了時間。將這種查找方法應(yīng)用到的基于矩陣的apriori算法[2，7]中,從而降低了整個算法的時間復(fù)雜度。

1 改進(jìn)的查找方法

1.1 刪減矩陣的相關(guān)性質(zhì)

性質(zhì)1如果某列的1出現(xiàn)的個數(shù)小于最小支持度計數(shù)，則刪除此列。

性質(zhì)2如果在產(chǎn)生頻繁k-項集之前，對布爾矩陣掃描發(fā)現(xiàn)，某事務(wù)行的1出現(xiàn)的個數(shù)少于k，則刪除此事務(wù)。

性質(zhì)3在布爾矩陣中，在產(chǎn)生頻繁k-項集之前，如果某數(shù)據(jù)項Xi在所有的頻繁k-1-項集中出現(xiàn)的次數(shù)少于k-1次，那么此數(shù)據(jù)項Xi參與組合成的所有候選k-項集如{X1,X2,X3,Xi,....Xk}必不是頻繁項集，則可以刪除此數(shù)據(jù)項[9]。

證明：反證法。如果候選k-項集{X1,X2,X3,Xi,....Xk}是頻繁項集，則元素Xi參與組成的k-1子集的個數(shù)就是 ，即k-1，那么元素Xi在頻繁k-1-項集中出現(xiàn)的次數(shù)大于等于k-1，與條件矛盾，證明完畢。

1.2 項集的有序性

apriori算法中產(chǎn)生的頻繁項集的項是按字典序存儲的，即頻繁k-1-項集的前面一項的字典序不得大于后一項的字典序。如項A、B、C、D、E按字典序依次排列。那么在項集ABCD是允許的，而ABDC是不允許的，因為C的字典序比D小。

1.3 改進(jìn)的查找方法

在性質(zhì)3中，需要對頻繁k-1-項集進(jìn)行查找。常見的方法，使用for循環(huán)按行查找項在所有的頻繁k-1-項集[3-5，7]出現(xiàn)的次數(shù)，通過判斷次數(shù)是否小于k-1來決定是否刪除項，偽代碼如下。

For each item I Lk-1

For each iK //K是出現(xiàn)在所有頻繁k-1-項集中項的集合

If iI

I.count++;

For each i K

If i.count

For each item I Lk-1

If iI

Delete I

這樣忽略了項集的有序性，不一定要查找每一個頻繁k-1-項集，此外利用矩陣的刪除性質(zhì)3，并不要得出每一項的在頻繁k-1-項集的計數(shù)，而是找出在頻繁k-1-項集中出現(xiàn)次數(shù)少于k-1的項Xi即可。

針對以上問題，提出一種改進(jìn)的查找方法即，將頻繁k-1-項集的下標(biāo)組合按行存儲在二維數(shù)組中[8]，最后一列是它的計數(shù)。

第一，按行對頻繁k-1-項集進(jìn)行搜索，如果發(fā)現(xiàn)某一項Xi在頻繁k-1-項集中出現(xiàn)的次數(shù)已經(jīng)等于k-1，立即放棄掃描，跳到下一個項的計數(shù)。如在掃描B時候，發(fā)現(xiàn)掃描第三行就發(fā)現(xiàn)B的計數(shù)就為3，則停止掃描，進(jìn)入對C的計數(shù)。

第二，利用頻繁項集的有序性[2]，減少掃描量。即按行搜索項Xi在頻繁k-1-項集的次數(shù)的時候，若是第一列出現(xiàn)的項的字典序大于Xi的字典序，則停止搜索，因為接下來的矩陣行中不可能還出現(xiàn)Xi，由于第一種改進(jìn)的存在，所以這項在頻繁k-1-項集出現(xiàn)的次數(shù)就是小于k-1，刪除此項。如下面表1，表2。搜索A時候，在第三行中第一列出現(xiàn)了B，則停止搜索，后面的頻繁3-項集不可能還出現(xiàn)A，A項在頻繁k-1-項集中出現(xiàn)的次數(shù)必然是小于3，所以刪除此項。

表1 事務(wù)集Tab.1 Transaction set

偽代碼如下：

For item i Lk-1 {

For j //j是矩陣的行

{

}

If A[j][0]]>L[i]; //如果行的第一列的字典序大于搜索項的字典序

{

Delete i;

Step to next i； //進(jìn)入下一項的掃描；

For k //k是矩陣的列

{

If A[j][k]==i

i.count++;

If i.count==k-1

Step to next i；

}

}

}

表2 存入數(shù)組中煩人頻繁3-項集Tab.2 Frequent 3-set stored in array

2 算法的設(shè)計和說明

2.1 算法的基本思想

算法通過將事務(wù)映射成一個矩陣，然后通過矩陣中的數(shù)據(jù)項列向量進(jìn)行位與運算，然后對其計數(shù)向量中的1出現(xiàn)的總和，然后與最小支持度計數(shù)比較直接產(chǎn)生頻繁項集[7]。這個過程中不產(chǎn)生候選項集，但是會通過改進(jìn)的查找方法進(jìn)行刪減矩陣列來減少矩陣列參與位與運算的次數(shù)，此外會通過刪減矩陣行減少對矩陣的掃描量和內(nèi)存消耗。

2.2 算法的主要步驟

第一步：建立矩陣。將事務(wù)映射成矩陣，矩陣一行對應(yīng)一條事務(wù)。其中項出現(xiàn)的為1，不出現(xiàn)的為0。

第二步：產(chǎn)生頻繁1-項集和頻繁2-項集。產(chǎn)生頻繁項集1后，應(yīng)用性質(zhì)1，性質(zhì)2對矩陣進(jìn)行壓縮。然后在這個基礎(chǔ)上產(chǎn)生頻繁2-項集。

第三步：刪減矩陣。

對行的刪除：應(yīng)用性質(zhì)2，如果矩陣行中1出現(xiàn)的次數(shù),少于k，則刪除此事務(wù)行。

對列的刪除：應(yīng)用性質(zhì)3，用改進(jìn)的查找方法找出在頻繁k-1-項集中出現(xiàn)的次數(shù)小于k-1的項Xi，然后刪掉。

第四步：產(chǎn)生頻繁k項集（k>3）。將矩陣行k（k>1）個行向量相與，計算行中各個1的和,然后將這個和與最小支持度計數(shù)相比較，如果大于等于，則這幾個數(shù)據(jù)項的組合就是頻繁項集。然后將組合的數(shù)據(jù)項列號和頻數(shù)用二維數(shù)組存儲起來，便于第三步中進(jìn)行查找。

第五步：不斷重復(fù)第三步，第四步，到無法產(chǎn)生頻繁項集。

3 算法的示例

第一步：將矩陣映射為矩陣，如表4。

第二步：產(chǎn)生頻繁1-項集和頻繁2-項集。假定最小支持度計數(shù)為2，A的向量形式為{A：101110}，對出現(xiàn)的 1個數(shù)求和，支持度計數(shù)為4，所以A保留，依此得到頻繁1-項集為：{A}，{B}，{C}，{D}，{E}。 將矩陣列 A 和 B 進(jìn)行位相與，得到{AB：101010}，支持度計數(shù)為3，所以為頻繁項集。這樣得到頻繁2-項集為：

表3 事務(wù)集tab.3 Transaction set

表4 對應(yīng)的矩陣Tab.4 The corresponding matrix

{AB},{AC},{AD},{AE},{BC},{BD},{BE},{CD},{CE},{DE}。

第三步：刪減矩陣。對行掃描，發(fā)現(xiàn)所有的行1出現(xiàn)的個數(shù)都是大于3的，所以沒有必要刪除。在對項在頻繁2-項集中出現(xiàn)的次數(shù)進(jìn)行計數(shù)，都是大于2的。如A在頻繁2-項集中出現(xiàn)的次數(shù)就是4。所以沒有必要刪除矩陣。

第四步：生成頻繁3-項集為：{ABC},{ABD},{BCD},{BCE},{CDE},利用性質(zhì)3，發(fā)現(xiàn)A在頻繁3-項集中出現(xiàn)的次數(shù)為2，所以刪掉A列。得到矩陣如表5。

第五步：生成頻繁4-項集為{BCDE}，整個算法結(jié)束。

4 算法的分析

本算法較之文獻(xiàn)[7]的算法的不同之處主要在是對頻繁k-1-項集的查找的方法上，所以分析主要在查找方法上的分析上。

假設(shè)頻繁k-1-項集的個數(shù)即矩陣的行數(shù)為m，頻繁k-1-項集的集合的項的個數(shù)是p，之前的查找方法需要掃描頻繁k-1-項集的次數(shù)是p，所以總的掃描行數(shù)為pm。使用改進(jìn)的算法，在計算項在頻繁k-1-項集中出現(xiàn)的次數(shù)時候，只需要掃描矩陣部分行。如表5中A、B、C項都是需要掃描部分行，所以總的掃描行數(shù)是，所以這樣一來會較之原來的查找方法節(jié)約時間。此外,由表2可知,當(dāng)事務(wù)集的項越多,那么矩陣第一列的字典序不同的項會比較多,由于這種查找方法中根據(jù)有序性查找的,則一旦發(fā)現(xiàn)掃描的行的第一列的的字典序大于所搜索項的字典序,則停在搜索,那么所掃描的行數(shù)與之前的查找方法相比較會大大減少,這種查找方法的優(yōu)勢會更加明顯。而整個算法中這種查找會用到k次左右，節(jié)約的時間會比較多。用在整個算法上也就降低了時間復(fù)雜度。

表5 刪減后的矩陣Tab5 The reduced matrix

與apriori算法比較,整個算法由于把事務(wù)以矩陣的形式存入內(nèi)存所以對數(shù)據(jù)庫只是需要掃描一次,而且不需要產(chǎn)生候選項集,節(jié)省了內(nèi)存空間,而且省略了連接和剪枝的時間。

5 結(jié)論

本文主要的創(chuàng)新點是對基于矩陣的apriori算法中刪減矩陣前的對頻繁k-1-項集的查找方法進(jìn)行了改進(jìn)，從而降低了算法的時間復(fù)雜度，通過分析對矩陣的掃描量從而得出此改進(jìn)是有效的。但是此算法在數(shù)據(jù)量比較大的時候?qū)?，?nèi)存消耗比較大，此問題值得進(jìn)一步研究。

[1]TANGPang-ning,Steinbach V，Kumar V.Introduction to data mining[M].北京：人民郵電出版社，2006.

[2]BAI Si-xue,DAI Xin-xi.An efficiency apriori algorithm：P_Matrix algorithm[C].ISDPE,2007:101-103.

[3]徐章艷,張師超,區(qū)玉明,等.挖掘關(guān)聯(lián)規(guī)則中的一種優(yōu)化的Aprior算法[J].計算機(jī)工程,2003(19):83-87.XU Zhang-yan,ZHANG Shi-chao,QU Yu-ming,et al.An optimized apriori algorithm for mining assoeiation rules[J].Compute Engineering,2003(19):83-87.

[4]柴華昕,王勇.Apriori挖掘頻繁項目集算法的改進(jìn)[J].計算機(jī)工程與應(yīng)用，2007,43(24):158-161.CHAI Hua-xin,WANG Yong.Improvement of apriori algorithm[J].Computer Engineering and Applications,2007,43(24):158-161.

[5]崔貫勛,李梁，王柯柯,等.基于改進(jìn)Apriori算法的入侵檢測系統(tǒng)的研究[J].計算機(jī)工程與科學(xué)，2011(4):40-44.CUI Guan-xun,LI Liang,WANG Ke-ke,et al.Research on an intrusion detection system based on the improved apriori algorithm[J].Computer Engineering and Science,2011(4):40-44.

[6]劉敏嫻,馬強(qiáng),寧以風(fēng).基于頻繁矩陣的Apriori算法改進(jìn)[J].計算機(jī)工程和設(shè)計，2012,33(11):4235-4239.LIU Min-xian,MA Qiang,NING Yi-feng.Improved apriori algorithm based on frequent matrix[J].Computer Engineering and Design,2012,33(11):4235-4239.

[7]徐嘉莉.一種基于矩陣壓縮的Apriori優(yōu)化算法[J].微計算機(jī)信息，2009,4(3):213-215.XU Jia-li.A high efficiency algorithm based on reducing matrix for apriori[J].Microcomputer Information,2009,4(3):213-215.

[8]苗苗苗,王玉英.基于矩陣壓縮的Apriori算法的研究[J].計算機(jī)工程與應(yīng)用，2013,49(1):159-162.MIAO Miao-miao,WANG Yu-ying.Research on improvement of Apriori algorithm based on matrix compression.Computer Engineering and Applications,2013,49（1）：159-162.

[9]傅慧，鄒海.基于待與項集的頻繁項集挖掘算法的研究[J].計算機(jī)工程與設(shè)計，2009,30(1):129-131.FU Hui，ZOU Hai.Algorithm of mining frequent itemsets based on pending items [J].Computer Engineering and Design，2009,30(1):129-131.