基于矩陣的apriori算法的改進(jìn)

張衛(wèi)華

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

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

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

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

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

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

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

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

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

1.2 項(xiàng)集的有序性

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

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

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

For each item I Lk-1

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

If iI

I.count++;

For each i K

If i.count

For each item I Lk-1

If iI

Delete I

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

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

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

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

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

偽代碼如下：

For item i Lk-1 {

For j //j是矩陣的行

{

}

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

{

Delete i;

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

For k //k是矩陣的列

{

If A[j][k]==i

i.count++;

If i.count==k-1

Step to next i；

}

}

}

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

2 算法的設(shè)計(jì)和說(shuō)明

2.1 算法的基本思想

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

2.2 算法的主要步驟

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

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

第三步：刪減矩陣。

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

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

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

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

3 算法的示例

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

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

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

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

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

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

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

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

4 算法的分析

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

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

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

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

5 結(jié)論

本文主要的創(chuàng)新點(diǎn)是對(duì)基于矩陣的apriori算法中刪減矩陣前的對(duì)頻繁k-1-項(xiàng)集的查找方法進(jìn)行了改進(jìn)，從而降低了算法的時(shí)間復(fù)雜度，通過(guò)分析對(duì)矩陣的掃描量從而得出此改進(jìn)是有效的。但是此算法在數(shù)據(jù)量比較大的時(shí)候?qū)?，?nèi)存消耗比較大，此問(wèn)題值得進(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ì)算機(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挖掘頻繁項(xiàng)目集算法的改進(jìn)[J].計(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算法的入侵檢測(cè)系統(tǒng)的研究[J].計(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ì)算機(jī)工程和設(shè)計(jì)，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ì)算機(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ì)算機(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]傅慧，鄒海.基于待與項(xiàng)集的頻繁項(xiàng)集挖掘算法的研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，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.