張健, 劉韶濤

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

事務(wù)約簡(jiǎn)和2項(xiàng)集支持度矩陣快速剪枝的Apriori改進(jìn)算法

張健, 劉韶濤

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

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

關(guān)聯(lián)規(guī)則； Apriori算法； 頻繁項(xiàng)集； 支持度矩陣

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

1 Apriori算法及M-Apriori算法

1.1Apriori算法及其改進(jìn)

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

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

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

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

Apriori算法簡(jiǎn)單，但是它仍比較低效.原因主要有以下3個(gè)方面.

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

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

3) 候選項(xiàng)集求支持度時(shí),需要和各條事務(wù)進(jìn)行模式匹配，比較費(fèi)時(shí).

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

1.2M-Apriori算法

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

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

圖1 改進(jìn)后MR-Apriori算法示例Fig.1 Example of improved MR-Apriori algorithm

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

2.1MR-Apriori算法

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

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

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

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

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

2.2MP-Apriori算法

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

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

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

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

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

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

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

2.3MRP-Apriori算法

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

3 實(shí)驗(yàn)結(jié)果與分析

圖3 不同支持度下的運(yùn)行時(shí)間對(duì)比Fig.3 Comparation of running time in different support

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

4 結(jié)論

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

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

[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ìn)算法[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2003,28(1):94-99.

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

[8] 劉維曉,陳俊麗,屈世富,等.一種改進(jìn)的Apriori算法[J].計(jì)算機(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項(xiàng)集支持矩陣的Apriori改進(jìn)算法[J].計(jì)算機(jī)工程,2013,39(11):183-186.

[12] 胡吉明,鮮學(xué)豐.挖掘關(guān)聯(lián)規(guī)則中Apriori算法的研究與改進(jìn)[J].計(jì)算機(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.

福建省科技計(jì)劃重大項(xiàng)目(2011H6016)

TP 311

A

1000-5013(2017)05-0727-05