張健, 劉韶濤

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

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

張健, 劉韶濤

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

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

關(guān)聯(lián)規(guī)則； 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

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

1 Apriori算法及M-Apriori算法

1.1Apriori算法及其改進

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

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

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

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

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

1) 需要多次掃描數(shù)據(jù)庫.

2) 產(chǎn)生大量中間候選項集.

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

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

1.2M-Apriori算法

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

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

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

2 M-Apriori算法的優(yōu)化

2.1MR-Apriori算法

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

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

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

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

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

2.2MP-Apriori算法

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

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

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

步驟1掃描數(shù)據(jù)庫，構(gòu)造2項集的支持度矩陣.以數(shù)據(jù)庫中的項作為矩陣相應(yīng)的行標(biāo)和列標(biāo)，如果掃描到一條事務(wù)中包含有{Ii,Ij}2項集，則對矩陣進行一次填充.

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

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

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

2.3MRP-Apriori算法

優(yōu)化1，2從兩個不同的方向?qū)-Apriori算法進行優(yōu)化改進，MRP-Apriori算法將優(yōu)化1，2綜合到一起加入到M-Apriori算法中.

3 實驗結(jié)果與分析

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

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

4 結(jié)論

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

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

[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].武漢大學(xué)學(xué)報(信息科學(xué)版),2003,28(1):94-99.

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

[8] 劉維曉,陳俊麗,屈世富,等.一種改進的Apriori算法[J].計算機工程與應(yīng)用,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] 紀(jì)懷猛.基于頻繁2項集支持矩陣的Apriori改進算法[J].計算機工程,2013,39(11):183-186.

[12] 胡吉明,鮮學(xué)豐.挖掘關(guān)聯(lián)規(guī)則中Apriori算法的研究與改進[J].計算機技術(shù)與發(fā)展,2006,16(4):99-101.

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

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-)，男，副教授，主要從事軟件體系結(jié)構(gòu)與軟件復(fù)用的研究.E-mail:shaotaol@hqu.edu.cn.

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

TP 311

A

1000-5013(2017)05-0727-05