宋文慧，高建瓴

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院,貴州 貴陽(yáng) 550025)

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

宋文慧，高建瓴

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院,貴州 貴陽(yáng) 550025)

文中介紹了經(jīng)典Apriori算法的原理、思想和步驟，以及基于矩陣的Apriori算法。針對(duì)Apriori算法需要多次掃描數(shù)據(jù)庫(kù)和產(chǎn)生大量候選項(xiàng)集的缺點(diǎn)，提出了一種基于矩陣的Apriori算法的改進(jìn)方法。該方法的不同之處在于矩陣的構(gòu)建方法，通過(guò)對(duì)事務(wù)數(shù)據(jù)庫(kù)的一次整體掃描，把事務(wù)數(shù)據(jù)庫(kù)中的數(shù)據(jù)轉(zhuǎn)換成一個(gè)上三角矩陣，然后通過(guò)訪問(wèn)上三角矩陣中的元素就可直接得到頻繁1項(xiàng)集和頻繁2項(xiàng)集，再根據(jù)經(jīng)典的Apriori算法，利用頻繁2項(xiàng)集得到頻繁3項(xiàng)集，依此進(jìn)行下去。該算法因?yàn)橛猩先蔷仃嚨囊?，故可以適當(dāng)?shù)販p少訪問(wèn)事務(wù)數(shù)據(jù)庫(kù)的次數(shù)，同時(shí)還減少了大量候選項(xiàng)集的產(chǎn)生，尤其是二次候選項(xiàng)集，節(jié)約了存儲(chǔ)空間。實(shí)驗(yàn)結(jié)果表明，該改進(jìn)算法是有效的，減少了使用掃描數(shù)據(jù)庫(kù)的函數(shù)的次數(shù)，并且保證了頻繁項(xiàng)集的準(zhǔn)確性。

關(guān)聯(lián)規(guī)則；Apriori算法；矩陣；M-Apriori算法

1 概 述

數(shù)據(jù)挖掘，通俗來(lái)說(shuō)，是從大型的數(shù)據(jù)中找出其內(nèi)在隱含的信息，而內(nèi)在的信息可以用關(guān)聯(lián)規(guī)則或頻繁項(xiàng)集來(lái)表示。其中，頻繁模式挖掘是關(guān)聯(lián)規(guī)則、相關(guān)性分析、序列模式、因果關(guān)系、情節(jié)片段、局部周期性、顯露模式等許多重要數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)[1]。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的眾多模式中最重要的一種，通過(guò)對(duì)數(shù)據(jù)項(xiàng)集間的關(guān)聯(lián)性進(jìn)行分析和挖掘，挖掘出在決策制定過(guò)程中具有重要參考價(jià)值的信息。關(guān)聯(lián)規(guī)則經(jīng)常被用于市場(chǎng)營(yíng)銷中,從交易數(shù)據(jù)庫(kù)中可挖掘出不同商品(項(xiàng))之間的聯(lián)系，找出顧客的購(gòu)買行為模式，再將這些購(gòu)買行為模式用在營(yíng)銷策略上，從而提高商品銷售量，故又稱為購(gòu)物籃分析[2]。

Apriori算法[3]是在1994年由Agrawal和R.Srikant共同提出的，是第一個(gè)關(guān)聯(lián)規(guī)則挖掘算法，具有很大的影響力,但算法也存在一些不足之處[4-6]。Apriori算法是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法，利用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)，通過(guò)逐層搜索的迭代方法，即將k項(xiàng)集用于探察(k+1)項(xiàng)集，來(lái)窮盡數(shù)據(jù)集中的所有頻繁項(xiàng)集。算法過(guò)程是[7]：連接→剪枝→生成Ck→掃描計(jì)數(shù)→比較→生成Lk。Apriori算法采用兩階段挖掘的思想，并且基于多次掃描事務(wù)數(shù)據(jù)庫(kù)來(lái)執(zhí)行。面對(duì)存儲(chǔ)了海量數(shù)據(jù)的事務(wù)數(shù)據(jù)庫(kù)，這無(wú)疑將消耗大量的時(shí)間和內(nèi)存空間，也導(dǎo)致了效率較低，這也是Apriori算法的瓶頸所在。

文獻(xiàn)[8]提出基于粗糙集對(duì)Apriori算法進(jìn)行改進(jìn)。該方法是利用項(xiàng)集分類預(yù)處理來(lái)對(duì)事務(wù)數(shù)據(jù)庫(kù)中的所有項(xiàng)集進(jìn)行預(yù)處理。文獻(xiàn)[9]提出一種0-1矩陣的改進(jìn)算法，改變由低維頻繁項(xiàng)目集到高維頻繁項(xiàng)目集的多次連接運(yùn)算。文獻(xiàn)[10]改變了頻繁1項(xiàng)集的排列方式，進(jìn)而減少了候選項(xiàng)集的產(chǎn)生。文獻(xiàn)[11]則消除大量冗余的非頻繁項(xiàng)集。

文中在對(duì)上述幾種算法的研究基礎(chǔ)上，通過(guò)對(duì)矩陣的不同定義，提出了一種新的基于矩陣的Apriori改進(jìn)算法。與文獻(xiàn)[9]提到的矩陣的不同之處在于，該改進(jìn)算法的矩陣是以項(xiàng)集中的項(xiàng)作為矩陣相應(yīng)的行標(biāo)和列標(biāo)，通過(guò)一次遍歷矩陣即可直接得到頻繁1項(xiàng)集和頻繁2項(xiàng)集，從而減少了掃描數(shù)據(jù)庫(kù)的次數(shù)以及大量候選項(xiàng)集的產(chǎn)生，在時(shí)間和內(nèi)存空間方面有一定的改善。

2 經(jīng)典的Apriori算法

2.1 Apriori算法的基本思想

Apriori算法作為一種經(jīng)典算法，無(wú)疑占據(jù)重要地位。其基本思想如下：

(1)通過(guò)掃描事務(wù)數(shù)據(jù)庫(kù)中的所有數(shù)據(jù)項(xiàng)集，得到候選1-項(xiàng)集，記為C1，并統(tǒng)計(jì)出相應(yīng)數(shù)據(jù)項(xiàng)出現(xiàn)的頻數(shù)。按照預(yù)先定義的最小支持度，從C1中篩選出符合要求的頻繁1-項(xiàng)集，記為L(zhǎng)1。

(2)通過(guò)頻繁1-項(xiàng)集L1的自連接得到候選2-項(xiàng)集C2，接著再掃描事務(wù)數(shù)據(jù)庫(kù)，統(tǒng)計(jì)出對(duì)應(yīng)的頻數(shù)，使之和最小支持度相比較，得到L2。

(3)重復(fù)上述步驟，直到不再存在滿足要求的頻繁K-項(xiàng)集為止。

從上述可知，Apriori算法使用逐層搜索的迭代方法，通過(guò)低維頻繁項(xiàng)目集產(chǎn)生高維頻繁項(xiàng)目集[3]。每次挖掘一層頻繁項(xiàng)集Lk，就需要掃描一次整個(gè)事務(wù)數(shù)據(jù)庫(kù)。在此過(guò)程中，還要生成大量的候選項(xiàng)集，因此Apriori算法的效率低。

2.2 Apriori算法的關(guān)鍵步驟

Apriori算法是通過(guò)迭代的方法，由Lk-1找Lk，關(guān)鍵步驟為：連接、剪枝。

(1)連接步：為得到Lk，需要將Lk-1與自身連接生成候選-K項(xiàng)集，執(zhí)行的前提是Lk-1的元素是可以連接的[12]。

(2)剪枝步：Ck的成員可以是也可以不是頻繁的，但所有頻繁K-項(xiàng)集都包含在Ck中，通過(guò)掃描數(shù)據(jù)庫(kù)，確定Ck中每個(gè)候選的頻數(shù)，從而確定Lk[12]。

2.3 Apriori算法的不足

Apriori算法能夠較有效地得到頻繁項(xiàng)集，但也存在一些不足之處。

(1)每當(dāng)挖掘K頻繁項(xiàng)集時(shí)，都要對(duì)事務(wù)數(shù)據(jù)庫(kù)進(jìn)行多次掃描以得到相應(yīng)的支持度計(jì)數(shù)，不可避免地將導(dǎo)致時(shí)間消耗太長(zhǎng)。

(2)將會(huì)生成很多的候選項(xiàng)集，在Lk-1通過(guò)自連接得到Lk時(shí)，可能會(huì)生成大量的候選項(xiàng)集，特別是C2。

鑒于以上的缺陷，提出了基于矩陣的Apriori算法，其核心方法是用矩陣來(lái)表示事務(wù)數(shù)據(jù)庫(kù)中的數(shù)據(jù)項(xiàng)集。

3 基于矩陣的Apriori算法

該算法是把0-1矩陣作為輔助元素，只要掃描一次事務(wù)數(shù)據(jù)庫(kù)，就能得到所有符合條件的頻繁項(xiàng)集。

算法過(guò)程為[13](T代表事務(wù)數(shù)據(jù)庫(kù))：

(1)構(gòu)建m×n階0-1矩陣。其中，m是事務(wù)的個(gè)數(shù)，n是項(xiàng)集的個(gè)數(shù)。

·aij=1，I項(xiàng)出現(xiàn)在Tj中；

·aij=0，I項(xiàng)沒(méi)有出現(xiàn)在Tj中。

(2)對(duì)Ii中1的個(gè)數(shù)記數(shù)。

(3)將記數(shù)小于minsup的Ii項(xiàng)(矩陣的行)都刪除。

(4)對(duì)記數(shù)大于等于minsup的項(xiàng)做交運(yùn)算。

(5)用上述的結(jié)果項(xiàng)構(gòu)建矩陣。

·aij=1，結(jié)果項(xiàng)存在于Tj中；

·aij=0，結(jié)果項(xiàng)不存在于Tj中。

(6)對(duì)以結(jié)果項(xiàng)構(gòu)建的矩陣中1的個(gè)數(shù)記數(shù)。

(7)將記數(shù)小于minsup的結(jié)果項(xiàng)都刪除。

(8)返回(4),否則轉(zhuǎn)到(9)。

(9)最終的結(jié)果項(xiàng)就是所要求的關(guān)聯(lián)規(guī)則。

從上述過(guò)程可知，0-1矩陣改進(jìn)算法有兩個(gè)優(yōu)點(diǎn)：

(1)頻繁項(xiàng)集的搜索工作可以僅通過(guò)一次掃描數(shù)據(jù)庫(kù)完成，減少了訪問(wèn)數(shù)據(jù)庫(kù)的次數(shù)。

(2)減少大量的候選集的產(chǎn)生，節(jié)約存儲(chǔ)空間。

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

上述基于矩陣的算法需要產(chǎn)生多個(gè)矩陣，并且隨著支持度的改變，矩陣需要不斷更改。而經(jīng)典的算法會(huì)生成很多的候選項(xiàng)集，主要集中在二項(xiàng)集上，并且需要多次掃描事務(wù)數(shù)據(jù)庫(kù)。鑒于這些情況，文中采用新的方法來(lái)構(gòu)建相關(guān)矩陣。

通過(guò)掃描一次事務(wù)數(shù)據(jù)庫(kù)就可以得到一個(gè)上三角矩陣，通過(guò)此矩陣，不需要進(jìn)行自連接便可直接得出符合條件的頻繁1-項(xiàng)集和頻繁2-項(xiàng)集。然后再按照經(jīng)典的Apriori算法由L2自連接得到C3，再和minsup相比較，得到L3……依次進(jìn)行下去，直至不存在滿足條件的頻繁項(xiàng)集。

4.1 矩陣的構(gòu)成

為方便說(shuō)明，設(shè)存在下面的數(shù)據(jù)庫(kù)，如表1所示。

表1 某分店的事務(wù)數(shù)據(jù)

按照上述方法可以得到如下所示的上三角矩陣：

4.2 頻繁1項(xiàng)集和頻繁2項(xiàng)集

設(shè)最小支持度計(jì)數(shù)為2。

頻繁1-項(xiàng)集：因?yàn)樯先蔷仃嚨闹鲗?duì)角線的元素代表項(xiàng)集I的項(xiàng)在事務(wù)數(shù)據(jù)里出現(xiàn)的次數(shù)，通過(guò)與最小支持度相比較，可以得出L1={I1:6;I2:7;I3:6;I4:2;I5:2}。

4.3 頻繁3項(xiàng)集及頻繁K項(xiàng)集

L3再自連接得到{I1,I2,I3,I5},因?yàn)椴环纤惴ǖ南闰?yàn)性質(zhì)，所以C4=?，因此算法終止。

4.4 算法描述

對(duì)于上述提出的改進(jìn)的基于矩陣的Apriori算法的(M-Apriori)描述如下：

輸入：事務(wù)數(shù)據(jù)庫(kù)D，最小支持度min-sup；

輸出：頻繁1-項(xiàng)集，頻繁2-項(xiàng)集……

Step1:首先按照事務(wù)數(shù)據(jù)庫(kù)構(gòu)建上三角矩陣。

Step2:按照上三角矩陣直接得出L1和L2。

Step3:根據(jù)經(jīng)典Apriori算法，利用L2找到C3，進(jìn)而得到L3。按照此方法一直迭代，直到?jīng)]有符合minsup的頻繁項(xiàng)集，從而找到所有的滿足要求的頻繁項(xiàng)集。

5 實(shí)驗(yàn)與分析

實(shí)驗(yàn)環(huán)境：操作系統(tǒng)Windows7，CPU為3.20GHzIntel(R)Core(TM)i5-3470,編譯軟件為Matalab2014a。

參數(shù)設(shè)置：minsup=0.3。實(shí)驗(yàn)采用的數(shù)據(jù)是超市的購(gòu)物清單。

實(shí)驗(yàn)將經(jīng)典的Apriori算法和文中的M-Apriori算法進(jìn)行比較，可以發(fā)現(xiàn)M-Apriori算法比經(jīng)典的Apriori算法使用count_support函數(shù)的次數(shù)減少了2次。而count_support函數(shù)的功能就是通過(guò)掃描數(shù)據(jù)庫(kù)從大量的候選項(xiàng)集中篩選出符合minsup的頻繁項(xiàng)集，從而得到相應(yīng)的關(guān)聯(lián)規(guī)則。另外，M-Apriori算法首先就需要通過(guò)掃描一次數(shù)據(jù)庫(kù)生成目標(biāo)矩陣，即上三角矩陣。所以，整體來(lái)說(shuō)M-Apriori算法要比經(jīng)典的Apriori算法少掃描一次數(shù)據(jù)庫(kù)。此外，M-Apriori算法減少了候選項(xiàng)集的數(shù)目。

針對(duì)中小型事務(wù)數(shù)據(jù)庫(kù)來(lái)說(shuō)，只要得到目標(biāo)矩陣就可以很直觀地得出頻繁1-項(xiàng)集L1和頻繁2-項(xiàng)集L2。

6 結(jié)束語(yǔ)

針對(duì)Apriori算法需要多次掃描事務(wù)數(shù)據(jù)庫(kù)這一缺點(diǎn)，文中在矩陣的基礎(chǔ)上改進(jìn)了Apriori算法，提出了M-Apriori算法。實(shí)驗(yàn)結(jié)果表明，提出的新算法可以適當(dāng)減少掃描事務(wù)數(shù)據(jù)庫(kù)的總次數(shù)，并且保證了頻繁項(xiàng)集結(jié)果的準(zhǔn)確性。但由于在生成目標(biāo)矩陣時(shí)，需要統(tǒng)計(jì)出所有的項(xiàng)和二次項(xiàng)集在事務(wù)數(shù)據(jù)庫(kù)中出現(xiàn)的次數(shù)，從而增大了統(tǒng)計(jì)量，所以在時(shí)間方面沒(méi)有得到優(yōu)化。如何保證在減少掃描事務(wù)數(shù)據(jù)庫(kù)次數(shù)的基礎(chǔ)上提高算法的運(yùn)行速度，是筆者下一步需要研究的工作。

[1]Za?aneOR,El-HajjM.Advancesandissuesinfrequentpatternmining[C]//ProcofeighthPacific-Asiaconferenceonknowledgediscoveryanddatamining.Sydney,Australia:[s.n.],2004.

[2]AgrawalR,ImielinskiT,SwamiA.Miningassociationrulesbetweensetsofitemsinlargedatabases[C]//ProceedingsoftheACMSIGMODconferenceonmanagementofdata.Washington,DC:ACM,1993:207-216.

[3]AgrawalR,SrikantR.Fastalgorithmsforminingassociationrules[C]//BoccaJB,JarkeM,ZanioloC,etal.Proceedingof20thinternationalconferenceonverylargedatabases.Santiago,CA,USA:MorganKaufmannPublishersInc,1994:487-499.

[4] 程玉勝,鄧小光,江效堯.Apriori算法中頻繁項(xiàng)集挖掘挖掘?qū)崿F(xiàn)研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2006,16(3):58-60.

[5] 郭福亮,左凱伶.關(guān)聯(lián)規(guī)則挖掘中Apriori算法的一種改進(jìn)[J].計(jì)算機(jī)與數(shù)字工程,2007,35(5):3-4.

[6]HanJiawei,KamberM.Datamining:conceptsandtechniques[M].3thed.Beijing:ChinaMachinePress,2012.

[7] 李小兵,吳錦林,薛永生,等.關(guān)聯(lián)規(guī)則挖掘算法的改進(jìn)與優(yōu)化研究[J].廈門大學(xué)學(xué)報(bào):自然科學(xué)版,2005,44(4):468-471.

[8] 包震宇.基于粗糙集對(duì)Apriori算法的改進(jìn)[D].上海：上海師范大學(xué)，2010.

[9] 馬曉輝.一種基于關(guān)聯(lián)規(guī)則Apriori算法的改進(jìn)研究[J].現(xiàn)代計(jì)算機(jī)，2011(6):6-8.

[10] 呂桃霞,劉培玉.一種基于矩陣的強(qiáng)關(guān)聯(lián)規(guī)則生成算法[J].計(jì)算機(jī)應(yīng)用研究,2011,28(4):1301-1303.

[11] 張笑達(dá),徐立臻.一種改進(jìn)的基于矩陣的頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2010,20(4):93-96.

[12] 蘆 潔,劉志鏡.挖掘關(guān)聯(lián)規(guī)則中對(duì)Apriori算法的一個(gè)改進(jìn)[J].微電子學(xué)與計(jì)算機(jī),2006,23(2):10-12.

[13] 顧 琳,黎敬濤,張興濤.對(duì)Apriori算法的一種改進(jìn)—基于0-1矩陣處理算法[J].電腦知識(shí)與技術(shù)，2007,4(21)：814-816.

Improved Apriori Algorithm Based on Matrix

SONG Wen-hui,GAO Jian-ling

(College of Big Data and Information Engineering，Guizhou University，Guiyang 550025，China)

It introduces the principles,ideas and steps of the classical Apriori algorithm,as well as the Apriori algorithm based on matrix in this paper.In view of the shortcomings for traditional Apriori algorithm of requiring multiple scanning database and producing a large number of candidate itemsets,an improved Apriori algorithm based on matrix is proposed.The difference of this method is the method to construct a matrix,through a whole scan of the transaction database,the transaction data in the database into a upper triangular matrix,and then by accessing the elements in the upper triangular matrix can obtain frequent itemsets 1 and frequent itemsets 2 directly.According to the classical Apriori algorithm,using the frequent itemsets 2 get frequent itemsets 3,proceeding accordingly.Because of the introduction of upper triangular matrix,the improved algorithm can reduce the number of accessing database and the incidence of a large number of candidate itemsets,especially the candidate itemsets 2,saving storage space.The experiment shows that the improved algorithm is effective to reduce the number of functions used to scan the database and to ensure the accuracy of the frequent itemsets.

association rule;Apriori algorithm;matrix;M-Apriori algorithm

2015-09-16

2015-12-18

時(shí)間：2016-05-25

貴州省科學(xué)技術(shù)基金項(xiàng)目(黔科合J字[2015]2045)

宋文慧(1992-)，女，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘、聚類分析；高建瓴，碩士研究生導(dǎo)師，研究方向?yàn)閿?shù)據(jù)挖掘、云計(jì)算。

http://www.cnki.net/kcms/detail/61.1450.TP.20160525.1709.050.html

TP301.6

A

1673-629X(2016)06-0062-03

10.3969/j.issn.1673-629X.2016.06.013