基于矩陣的apriori算法的改進

張衛華

（江蘇大學 計算機科學與通信工程學院，江蘇 鎮江 212013）

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

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

1 改進的查找方法

1.1 刪減矩陣的相關性質

性質1如果某列的1出現的個數小于最小支持度計數，則刪除此列。

性質2如果在產生頻繁k-項集之前，對布爾矩陣掃描發現，某事務行的1出現的個數少于k，則刪除此事務。

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

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

1.2 項集的有序性

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

1.3 改進的查找方法

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

For each item I Lk-1

For each iK //K是出現在所有頻繁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-項集，此外利用矩陣的刪除性質3，并不要得出每一項的在頻繁k-1-項集的計數，而是找出在頻繁k-1-項集中出現次數少于k-1的項Xi即可。

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

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

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

表1 事務集Tab.1 Transaction set

偽代碼如下：

For item i Lk-1 {

For j //j是矩陣的行

{

}

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

{

Delete i;

Step to next i； //進入下一項的掃描；

For k //k是矩陣的列

{

If A[j][k]==i

i.count++;

If i.count==k-1

Step to next i；

}

}

}

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

2 算法的設計和說明

2.1 算法的基本思想

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

2.2 算法的主要步驟

第一步：建立矩陣。將事務映射成矩陣，矩陣一行對應一條事務。其中項出現的為1，不出現的為0。

第二步：產生頻繁1-項集和頻繁2-項集。產生頻繁項集1后，應用性質1，性質2對矩陣進行壓縮。然后在這個基礎上產生頻繁2-項集。

第三步：刪減矩陣。

對行的刪除：應用性質2，如果矩陣行中1出現的次數,少于k，則刪除此事務行。

對列的刪除：應用性質3，用改進的查找方法找出在頻繁k-1-項集中出現的次數小于k-1的項Xi，然后刪掉。

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

第五步：不斷重復第三步，第四步，到無法產生頻繁項集。

3 算法的示例

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

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

表3 事務集tab.3 Transaction set

表4 對應的矩陣Tab.4 The corresponding matrix

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

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

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

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

4 算法的分析

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

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

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

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

5 結論

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

[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]徐章艷,張師超,區玉明,等.挖掘關聯規則中的一種優化的Aprior算法[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].計算機工程與應用，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]崔貫勛,李梁，王柯柯,等.基于改進Apriori算法的入侵檢測系統的研究[J].計算機工程與科學，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]劉敏嫻,馬強,寧以風.基于頻繁矩陣的Apriori算法改進[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優化算法[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].計算機工程與應用，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].計算機工程與設計，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.