事務約簡和2項集支持度矩陣快速剪枝的Apriori改進算法

張健, 劉韶濤

(華僑大學 計算機科學與技術學院， 福建 廈門 361021)

事務約簡和2項集支持度矩陣快速剪枝的Apriori改進算法

張健, 劉韶濤

(華僑大學 計算機科學與技術學院， 福建 廈門 361021)

在Apriori算法的改進算法M-Apriori基礎上，為了進一步減少不必要的數據庫掃描，引入事務約簡技術，提出一種改進的MR-Apriori算法.考慮到M-Apriori算法會產生大量候選項集，為了實現對候選項集快速剪枝，加入一個自定義的2項集支持度矩陣，提出第2種改進的MP-Apriori算法.將事務約簡和2項集矩陣快速剪枝一起引入到 M-Apriori算法中，提出第3種改進的MRP-Apriori算法.最后，在mushroom數據集上進行實驗.結果表明：加入事務約簡的MR-Apriori算法和加入2項集矩陣快速剪枝的MP-Apriori算法，運行時間相比原M-Apriori算法都有較大縮減，而同時結合兩種優化策略的MRP-Apriori算法運行時間最短，驗證了這兩種優化策略的有效性.

關聯規則； Apriori算法； 頻繁項集； 支持度矩陣

Abstract： Based on the M-Apriori algprithm, an improved version of the Apriori algorithm, a transaction reduction technique is introduced and an improved algorithm, MR-Apriori, is proposed in the paper in order to further reduce unnessary database scans; Meanwhile, considering that the M-Apriori algorithm generates large amount of candidate itemsets during the running process, so as to quickly prune the candidate itemsets, a self-defined two-item set support matrix is added and a second improved algorithm, MP-Aproiri, is proposed in the paper. Then transaction reduction, accompanied by two-item set support matrix which is used to quickly prune the candidate itemsets, are combined together and a third improved algorithm, MRP-Aproiri, is proposed in the paper. Finally, an experiment is conducted on the mushroom dataset, the result shows that the MR-Apriori algorithm which uses the transaction reduction and the MP-Apriori algorithm which uses the two-item set support matrix that can quickly prune the candidate itemsets, is much faster than the M-Apriori algorithm, and the MRP-Apriori algotirhm which combines these two optimization strategies together gets the shortest time, therefore, it proves that these two optimization strategies are efficient.

Keywords： association rule； Apriori algorithm； frequent itemset； support matrix

關聯規則挖掘是數據挖掘任務中一個重要的研究方面，旨在挖掘出數據庫中潛在的關聯關系[1-8].Apriori算法[1]是關聯規則挖掘中最經典的算法，該算法基于“產生測試”框架，采用逐層迭代的方法得到頻繁項集.Apriori算法思想簡單，但也存在算法效率低的缺點.針對算法需要頻繁掃描數據庫的缺點，Al-Maolegi等[9]提出M-Apriori算法.M-Apriori算法采用了一種新的改進思路，大大減少了掃描數據庫次數.但是，這種改進雖然減少了數據庫掃描次數，但卻存在很多不必要的掃描.Singh等[10]則是通過事務約簡改進Apriori算法.紀懷猛[11]提出頻繁2項集支持矩陣對候選項集快速剪枝的方法，對M-Apriori算法進行優化，優化后的算法命名為MP-Apriori算法.本文結合這兩個優化算法，提出MRP-Apriori算法.

1 Apriori算法及M-Apriori算法

1.1Apriori算法及其改進

Apriori算法[1]采用寬度優先搜索的策略，算法有以下2個步驟.

步驟1掃描數據庫，計算得到1項集的支持度，刪去不滿足最小支持度的項集，得到頻繁1項集的集合.

步驟2由頻繁1項集得到頻繁2項集，頻繁2項集得到頻繁3項集，如此循環，直到不能找到頻繁項集為止.

步驟2分為連接和剪枝.連接是頻繁k-1項集Lk-1與自身進行連接，條件是兩者前k-2個項都相同(稱為可連接的)，最后一個元素不同，連接得到的結果是兩者前k-2個項加上按字典順序排列的兩者的最后一個元素，即得到候選k項集Ck.剪枝運用Apriori性質[1]，即頻繁項集的所有非空子集也都是頻繁的，對候選k項集Ck進行剪枝，剪枝后得到頻繁k項集Lk.

Apriori算法簡單，但是它仍比較低效.原因主要有以下3個方面.

1) 需要多次掃描數據庫.

2) 產生大量中間候選項集.

3) 候選項集求支持度時,需要和各條事務進行模式匹配，比較費時.

針對Apriori算法的這3點不足，國內外學者從各個方面來改進它的效率.DHP算法[2]引入Hash技術來減少候選2項集的生成；Partition算法[3]采用劃分的辦法，把數據庫劃分為若干個子庫，在子庫上求出局部頻繁項集，最后再匯總求出全局頻繁項集；Samping算法[4]隨機選擇一部分數據庫樣本，用這部分數據上的頻繁項集代表全局頻繁項集；DIC算法[5]在掃描的不同點添加候選項集，從而可以動態對項集進行評估，進一步減少數據庫掃描次數.陳江平等[6]引入概率的方法對Apriori算法進行改進；黃建明等[7]將數據庫轉換為十字鏈表的方式存儲，使得掃描數據庫的次數減少到了1次；劉維曉等[8]在Apriori中加入用戶興趣項進行改進，從而大范圍縮減數據庫容量.

1.2M-Apriori算法

Apriori算法中，為了產生頻繁k項集，需要保持大量候選項集，特別是當支持度很小的時候.因此，為了減少在掃描數據庫確定頻繁項集上花費的時間，M-Apriori算法[9]提出了一種新的改進的思路.在第1次掃描數據庫時，M-Apriori算法保存頻繁1項集L1中的每個項、對應的支持度及每個項所出現的事務ID號的集合.在計算k項集支持度時，M-Apriori算法先將k項集劃分為k個1項集；接著，根據頻繁1項集L1比較這k個1項集的支持度大小；最后，選擇從其中支持度最小的事務ID集合所對應的事務中掃描計算此k項集的支持度，從而大大減少掃描數據庫次數.改進后MR-Apriori算法示例，如圖1所示.

圖1中：D為原始數據庫；L1為M-Apriori算法得到頻繁1項集結果；實線為刪去事務中單個項；虛線為刪除整條事務.要產生頻繁2項集{I1,I2}，先比較I1和I2的支持度的大小，I1的支持度為5，小于I2的支持度7，掃描從I1所對應的事務ID集合{T1,T3,T7,T9,T10}所對應的事務T1,T3,T7,T9,T10，計算{I1,I2}的支持度，這樣本來需要掃描整個數據庫，現在只用掃描其中的5條，減少了掃描次數.同理，要產生頻繁3項集{I1,I2,I3}時，比較I1,I2和I3的支持度，掃描從支持度最小的即I1所對應的事務ID集合{T1,T3,T7,T9,T10}所對應的事務T1,T3,T7,T9,T10，計算{I1,I2,I3}的支持度.

圖1 改進后MR-Apriori算法示例Fig.1 Example of improved MR-Apriori algorithm

2 M-Apriori算法的優化

2.1MR-Apriori算法

文獻[10]為了改進Apriori算法，用兩點優化(性質1，2)：從數據庫中刪除某個值；刪除某條事務.

性質1當掃描第k(k≥2)次時，從數據庫中刪除在頻繁k-1項集Lk-1，但不刪除在頻繁k項集Lk的項.

性質2如果掃描第k(k≥2)次時，某事務項目數小于k, 則可以將其從數據庫中刪除.

需要注意這兩點優化是在第k(k≥2)次掃描時結合在一起作用的，且有先后順序，先用性質1刪除單個項，再判斷修改后的數據庫中各項事務長度是否小于k(k≥2)，刪除小于k(k≥2)的事務.

將這兩點優化加入到M-Apriori中，提出MR-Apriori算法.MR-Apriori算法在M-Apriori算法的基礎上，加入事務約簡技術.在M-Apriori算法掃描數據庫前，分別判斷性質1，2是否成立，從而對數據庫進行約簡.然后，在約簡后的數據庫上執行M-Apriori算法的后續步驟.為了計算k項集支持度，根據頻繁1項集L1比較k個1項集的支持度大小，掃描支持度最小的事務ID集合所對應的事務中，計算k項集的支持度.保存頻繁1項集L1中的每個項，每個項對應的支持度及每個項所出現的事務ID號的集合，由于MR-Apriori算法對事務進行了約簡，相應的L1的事務ID號集合這一項也要相應修改.

2.2MP-Apriori算法

Apriori算法產生大量候選集，尤其是候選2項集.候選集需要剪枝步驟才能生成頻繁項集，M-Apriori算法采用的還是Apriori算法的剪枝原理，即?c∈Ck，判斷c的k個(k-1)-子集是否都在Lk-1中，若找到一個(k-1)-子集不在Lk-1中就淘汰c.因為這個過程會多次掃描Lk-1，特別是當生成Ck很大時，算法的效率并不理想[12].優化1雖然約簡數據庫，也能一定程度上由于數據庫的減少而使生成的候選集數目減少，但從本質上說仍是基于傳統Apriori算法的剪枝原理產生候選集，并沒有充分改進候選集的剪枝過程.

定義matrix[MaxItemId][MaxItemId]的2項集支持度矩陣是一個三角矩陣(全部元素位于次對角線上方)，其中，MaxItemId為數據庫中所有項的最大值，MaxItemId 為7，矩陣初始元素全部為0.MP-Apriori算法有如下3個步驟.

圖2 填充后2項集支持度矩陣Fig.2 Two item support matrix after being filled

步驟1掃描數據庫，構造2項集的支持度矩陣.以數據庫中的項作為矩陣相應的行標和列標，如果掃描到一條事務中包含有{Ii,Ij}2項集，則對矩陣進行一次填充.

矩陣元素填充規則為：如果行下標i小于列下標j，則matrix[MaxItemId-j][i]+=1；否則，matrix[MaxItemId -1][j]+=1.填充后2項集支持度矩陣，如圖2所示.

步驟2產生頻繁2項集，由于第一步已經用矩陣保存了2項集和其對應的支持度，因此，只需要連接頻繁1項集L1和頻繁1項集L1.然后，從矩陣中得到連接后得到2項集的支持度，若支持度大于等于最小支持度，則加入到頻繁2項集中.獲取元素值的方法為：如果行下標i小于列下標j，則對應元素值為matrix[maxItemId -j][i]位置的值；否則，為matrix[maxItemId-1][j]位置的值.

步驟3產生頻繁k(k≥3)項集,和M-Apriori算法中步驟基本一致，唯一不同的就是在算法的剪枝步.在M-Apriori算法中的剪枝步驟，要不斷掃描數據庫，確定候選k項集Ck的每一個(k-1)項非空真子集是否都是頻繁的，從而確定頻繁k項集Lk，而為了運用2項集支持度矩陣對Ck進行快速剪枝，在原剪枝前面加入了一個預判斷.方法是在進行原Apriori剪枝前，先將要進行連接的兩個項集的各自最后一項進行連接得到二項集；然后，從矩陣中得到該二項集的支持度.如果小于最小支持度，可以把兩個連接的候選項集的連接項剪掉.通過這樣的預先判斷，只有矩陣元素的值大于等于最小支持度時，才需要檢查此連接項的所有(k-1)項子集是否都是頻繁的，從而可以大大提高算法效率.

2.3MRP-Apriori算法

優化1，2從兩個不同的方向對M-Apriori算法進行優化改進，MRP-Apriori算法將優化1，2綜合到一起加入到M-Apriori算法中.

3 實驗結果與分析

圖3 不同支持度下的運行時間對比Fig.3 Comparation of running time in different support

實驗平臺為Intel(R) Core(TM) i5-3470，主頻為3.20 GHz；內存為8 GB，Windows 7 旗艦版 64位 SP1.采用的編程語言為Java，開發環境為Eclipse 4.4.0.實驗數據集為fimi網站([ http:∥fimi.ua.ac.be/ ])上的蘑菇數據集，它共有8 124條事務，119個屬性，事務平均長度為23項.不同支持度下的運行時間對比，如圖3所示.圖3中：t為運行時間；ηmin為最小支持度.由圖3可知：MR-Apriori算法由于對在M-Apriori算法的基礎上加入事務約簡，使得運行效率較M-Apriori算法有所提高.MP-Apriori算法引進了2項集支持度矩陣，雖然需要消耗一定的存儲空間，但是它的效率提高比較明顯，比較顯著地提高算法的效率.MRP-Apriori算法則綜合了以上兩個算法的優點，因此，它的效率是最高的.

4 結論

在改進的M-Apriori算法，加入了事務約簡優化，提出MR-Apriori算法，在算法計算候選項集支持度時減少了原數據庫中記錄的數目，從而進一步減少了數據庫的次數，提高算法的效率.掃描加入了2項集支持度矩陣快速剪枝優化，能快速對候選項目集進行快速剪枝，而不用像原算法那樣需要檢查候選k項集的所有(k-1)項子集是否都是頻繁的，從而提高了效率.最后，結合前兩點優化，把提高效率的這兩方面結合到一起，提出了MRP-Apriori算法，再用實驗驗證了這3種算法的效率.

然而，第1點優化會對數據庫進行修改，需要花費精力對數據庫進行維護，降低算法效率.下一步將考慮使用其他辦法減少數據庫掃描次數，或在編寫代碼時，設置標志位，跳過這些需要被刪除的事務，而不是直接將其刪去，從而提高效率.第2點優化中，當數據庫事務平均長度很大時，矩陣會迅速增大，還可能會存在大量的零元素，從而會對算法效率有所影響.下一步將對此問題的改進方法進行研究.

[1] AGRAWAL R,SRIKANT R.Fast algorithms for mining association rules[C]∥Proc 20th Int Conf Very Large Data Bases.Santiago：VLDB,1994:487-499.

[2] PARK J S, CHEN M S, YU P S.An effective hash-based algorithm for mining association rules[J].ACM,1995：175-186.

[3] SAVASERE A,OMIECINSKI E R,NAVATHE S B.An efficient algorithm for mining association rules in large databases[C]∥ International Conference on Very Large Data Bases.[S.l.]:Morgan Kaufmann Publishers Inc,1995:432-444.

[4] TOIVONEN H.Sampling large databases for association rules[C]∥Proceedings of the 22nd VLDB Conference.Mumbai：[s.n.],1996:134-145.

[5] BRIN S,MOTWANI R,ULLMAN J D,etal.Dynamic itemset counting and implication rules for market basket data[J].ACM SIGMOD Record,1997,26(2):255-264.

[6] 陳江平,傅仲良,徐志紅.一種Apriori的改進算法[J].武漢大學學報(信息科學版),2003,28(1):94-99.

[7] 黃建明,趙文靜,王星星.基于十字鏈表的Apriori改進算法[J].計算機工程,2009,35(2):37-38,40.

[8] 劉維曉,陳俊麗,屈世富,等.一種改進的Apriori算法[J].計算機工程與應用,2011,47(11):149-159.

[9] AL-MAOLEGI M,ARKOK B.An improved apriori algorithm for association rules[J].International Journal on Natural Language Computing,2014,3(1):21-29.

[10] SINGH J,RAM H,SODHI D J S.Improving efficiency of apriori algorithm using transaction reduction[J].International Journal of Scientific and Research Publications,2013,3(1):1-4.

[11] 紀懷猛.基于頻繁2項集支持矩陣的Apriori改進算法[J].計算機工程,2013,39(11):183-186.

[12] 胡吉明,鮮學豐.挖掘關聯規則中Apriori算法的研究與改進[J].計算機技術與發展,2006,16(4):99-101.

(責任編輯： 陳志賢英文審校： 吳逢鐵)

ImprovedAprioriAlgorithmforQuicklyPrunebyCombiningTransactionReductionWithTwo-ItemSetSupportMatrix

ZHANG Jian， LIU Shaotao

(College of Computer Science and Technology, Huaqiao University, Xiamen 361021, China)

10.11830/ISSN.1000-5013.201510043

2015-10-21

劉韶濤(1969-)，男，副教授，主要從事軟件體系結構與軟件復用的研究.E-mail:shaotaol@hqu.edu.cn.

福建省科技計劃重大項目(2011H6016)

TP 311

A

1000-5013(2017)05-0727-05