基于矩陣的Apriori算法改進

宋文慧，高建瓴

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

基于矩陣的Apriori算法改進

宋文慧，高建瓴

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

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

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

1 概 述

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

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

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

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

2 經典的Apriori算法

2.1 Apriori算法的基本思想

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

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

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

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

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

2.2 Apriori算法的關鍵步驟

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

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

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

2.3 Apriori算法的不足

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

(1)每當挖掘K頻繁項集時，都要對事務數(shù)據(jù)庫進行多次掃描以得到相應的支持度計數(shù)，不可避免地將導致時間消耗太長。

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

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

3 基于矩陣的Apriori算法

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

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

(1)構建m×n階0-1矩陣。其中，m是事務的個數(shù)，n是項集的個數(shù)。

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

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

(2)對Ii中1的個數(shù)記數(shù)。

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

(4)對記數(shù)大于等于minsup的項做交運算。

(5)用上述的結果項構建矩陣。

·aij=1，結果項存在于Tj中；

·aij=0，結果項不存在于Tj中。

(6)對以結果項構建的矩陣中1的個數(shù)記數(shù)。

(7)將記數(shù)小于minsup的結果項都刪除。

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

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

從上述過程可知，0-1矩陣改進算法有兩個優(yōu)點：

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

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

4 改進的基于矩陣Apriori算法

上述基于矩陣的算法需要產生多個矩陣，并且隨著支持度的改變，矩陣需要不斷更改。而經典的算法會生成很多的候選項集，主要集中在二項集上，并且需要多次掃描事務數(shù)據(jù)庫。鑒于這些情況，文中采用新的方法來構建相關矩陣。

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

4.1 矩陣的構成

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

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

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

4.2 頻繁1項集和頻繁2項集

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

頻繁1-項集：因為上三角矩陣的主對角線的元素代表項集I的項在事務數(shù)據(jù)里出現(xiàn)的次數(shù)，通過與最小支持度相比較，可以得出L1={I1:6;I2:7;I3:6;I4:2;I5:2}。

4.3 頻繁3項集及頻繁K項集

L3再自連接得到{I1,I2,I3,I5},因為不符合算法的先驗性質，所以C4=?，因此算法終止。

4.4 算法描述

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

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

輸出：頻繁1-項集，頻繁2-項集……

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

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

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

5 實驗與分析

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

參數(shù)設置：minsup=0.3。實驗采用的數(shù)據(jù)是超市的購物清單。

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

針對中小型事務數(shù)據(jù)庫來說，只要得到目標矩陣就可以很直觀地得出頻繁1-項集L1和頻繁2-項集L2。

6 結束語

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

[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àn)研究[J].計算機技術與發(fā)展,2006,16(3):58-60.

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

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

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

[8] 包震宇.基于粗糙集對Apriori算法的改進[D].上海：上海師范大學，2010.

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

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

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

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

[13] 顧 琳,黎敬濤,張興濤.對Apriori算法的一種改進—基于0-1矩陣處理算法[J].電腦知識與技術，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

時間：2016-05-25

貴州省科學技術基金項目(黔科合J字[2015]2045)

宋文慧(1992-)，女，碩士研究生，研究方向為數(shù)據(jù)挖掘、聚類分析；高建瓴，碩士研究生導師，研究方向為數(shù)據(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