基于Ap riori算法的改進關(guān)聯(lián)規(guī)則的算法研究

謝美萍，芮廷先

(上海財經(jīng)大學信息管理與工程學院，上海 200433)

1 引言

關(guān)聯(lián)規(guī)則的最經(jīng)典算法就是Apriori算法，但是該算法在實際應(yīng)用時，存在著很多缺陷，比如需要多次掃描事務(wù)數(shù)據(jù)庫，需要很大的I/O負載，而且可能產(chǎn)生龐大的候選集.針對這些缺陷，許多學者提出了改進的算法，王培吉等［1］提出一種基于分辨矩陣的含負屬性項的關(guān)聯(lián)規(guī)則挖掘算法;王娟琴等［2］在研究ApriorTid算法的基礎(chǔ)上提出了一種高效的關(guān)聯(lián)規(guī)則挖掘算法AprioriTidD，在計算數(shù)據(jù)庫中的頻繁項集時依靠有效的裁剪減少無效項集的產(chǎn)生，同時可以減少候選項集，從而提高算法效率;方煒煒等［3］針對可快速在大型交易事務(wù)數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則的問題，提出了一種基于布爾矩陣的挖掘算法，該算法通過僅需存儲布爾位節(jié)約了內(nèi)存，提高求解頻繁項集的效率.針對關(guān)聯(lián)規(guī)則的特點，本文也提出了一種基于Apriori算法的改進算法，通過內(nèi)存矩陣，將事務(wù)數(shù)據(jù)庫的相關(guān)信息存放到內(nèi)存矩陣中，同時在找頻繁項目集的時候采用數(shù)組分組的方法來減少對內(nèi)存矩陣的掃描.為了減少候選集，采用從大到小篩選頻繁項目集的方法，同時把相應(yīng)的事務(wù)從矩陣中刪除以減少掃描范圍.

2 關(guān)聯(lián)規(guī)則的定義

設(shè)I={i1，i2，…，im}為項目集，事務(wù)數(shù)據(jù)庫D={t1，t2，…，tn}是由一系列具有唯一標識TID的事務(wù)組成，每個事務(wù)ti(i=1，2，…，n)都對應(yīng)項目集I上的一個子集.關(guān)聯(lián)規(guī)則就是一個蘊涵式，形如X?Y，其中X∈I，Y∈I，并且滿足X∩Y=?.其中X是關(guān)聯(lián)規(guī)則的條件，Y是關(guān)聯(lián)規(guī)則的結(jié)果.在使用關(guān)聯(lián)規(guī)則前，需設(shè)定最小支持度(Minsupport)與最小置信度(Minconfidence)，最小支持度的定義是事務(wù)集合D中包含有X和Y的百分比.最小置信度的定義是事務(wù)集合D中同時包含X和Y的事務(wù)占X的百分比.因此使用關(guān)聯(lián)規(guī)則的關(guān)鍵問題就轉(zhuǎn)換為如下兩個問題:

(1)發(fā)現(xiàn)頻繁項目集:通過用戶給定Minsupport，尋找所有頻繁項目集或者最大頻繁項目集.

(2)生成關(guān)聯(lián)規(guī)則:通過用戶給定Minconfidence，在頻繁項目集中，尋找關(guān)聯(lián)規(guī)則.

發(fā)現(xiàn)頻繁項目集的典型算法就是前面提及的Apriori算法，本文針對該算法提出一些改進，可以減少掃描數(shù)據(jù)庫的次數(shù)，很快找到最大頻繁項目集.

3 模型介紹

利用Apriori算法的頻繁項目集的兩個性質(zhì)，即任何強項集的子集必定是強項集;任何弱項集的超集必定是弱項集.這樣就可以解決Apriori算法要多次掃描事務(wù)數(shù)據(jù)庫的問題，采用掃描一次事務(wù)數(shù)據(jù)庫把信息存放到內(nèi)存矩陣中來實現(xiàn)，同時在找頻繁項目集的時候采用數(shù)組分組法來減少對矩陣的掃描.為了減少候選集，采用從大到小的篩選頻繁項目集的方法，同時把相應(yīng)的事務(wù)從矩陣中刪除以減少掃描范圍.

具體算法描述如下:

設(shè)有n個事務(wù)，k個項目.

(1)把事務(wù)數(shù)據(jù)庫存入矩陣.項目為行，事務(wù)為列;事務(wù)中有對應(yīng)項目則在矩陣相應(yīng)位置填1，否則填0.

(2)掃描矩陣，記下所有項目均存在的事物，并把矩陣中相應(yīng)的行刪掉，形成新的矩陣.

(3)L－(k－m)的生成:掃描矩陣，對每行中為1的元素作排列組合，得出的項目集存入相應(yīng)的數(shù)組中，數(shù)組第一個數(shù)為項目個數(shù).找出大于規(guī)定的最小支持度的項目集，把矩陣中的包含這個項目集所有元素且元素數(shù)等于k－m的行刪除.

(4)重復(3)，直到矩陣中行數(shù)小于給定的minsupport_count時停止.

此時，很容易找出事務(wù)數(shù)據(jù)庫的最大頻繁項目集，各個不同維度的頻繁項目集即是已求出的頻繁項目集的子集的并集.

4 模型仿真

設(shè)有如下事務(wù)數(shù)據(jù)庫(表1)，共含有5件商品，6條事務(wù)，項目分別用ABCDE表示:設(shè)定最小支持度為50%，即minsupport_count=3，用三中描述的算法尋找各個不同維度的頻繁項目集，步驟如下:

第一步，生成L5.因為沒有同時含有ABCDE的事務(wù)，所以，候選集C5為空集.

第二步，生成L4.掃描矩陣，生成以下數(shù)組，如表2所示:

表2 4－項目集的數(shù)組分配實例

因為最小支持度為50%，即minsupport_count=3，則L4={A，B，D，E}

同時刪除矩陣的第二行、第四行與第五行，得到新矩陣如下.

第三步，生成L3.掃描矩陣，生成以下數(shù)組，如表3所示:

表3 3－項目集的數(shù)組分配實例

因為最小支持度為50%，即minsupport_count=3，以上各3項集均不滿足，則保留原矩陣.第四步，生成L2.

表4 2－項目集的數(shù)組分配實例

因為最小支持度為50%，即minsupport_count=3，則{B，C}滿足最小支持度，而{B，C}所對應(yīng)的行為第一行、第二行與第三行，這樣刪除矩陣中的這三行，剩下一個空矩陣，不必再繼續(xù)找下去了.算法終止，見表4.

從上面的計算可以很容易的看出，該事務(wù)數(shù)據(jù)庫最大頻繁項目集為{ABDE}，與{BC}，并且可一次求出其他各維項目集可由{ABDE}，{BC}的子集的并集求出:

1－項目集{A}，{B}，{C}，{D}，{E};

2－項目集{AB}，{AD}，{AE}，{BD}，{BE}，{DE}，{BC};

3－項目集{ABD}，{BDE}，{ADE}，{ABE};

4－項目集{ABDE}.

5 結(jié)論

從算法的運行過程可以看出該算法與傳統(tǒng)的Apriori算法相比，計算量大大減少，只需要掃描數(shù)據(jù)庫一次，從而也減少了I/O的次數(shù).在生成頻繁項目集中用矩陣保存數(shù)據(jù)，并將生成的頻繁項目集所在矩陣的行刪除，減少了候選集的數(shù)目，從而減少了訪問數(shù)據(jù)庫的次數(shù)，提高了運行的速度.

［1］王培吉，趙玉琳，呂劍峰.基于Apriori算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘研究［J］.統(tǒng)計與決策，2011(23):19－21.

［2］王娟勤，李書琴.一種高效關(guān)聯(lián)規(guī)則挖掘算法［J］.湖南科技大學學報(自然科學版)，2011，26(4):60－63.

［3］方煒煒，楊炳儒，宋威.基于布爾矩陣的關(guān)聯(lián)規(guī)則算法研究［J］.計算機應(yīng)用研究，2008，25(7):1964－1966.