基于Ap riori算法的改進關聯規則的算法研究

謝美萍，芮廷先

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

1 引言

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

2 關聯規則的定義

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

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

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

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

3 模型介紹

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

具體算法描述如下:

設有n個事務，k個項目.

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

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

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

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

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

4 模型仿真

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

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

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

表2 4－項目集的數組分配實例

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

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

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

表3 3－項目集的數組分配實例

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

表4 2－項目集的數組分配實例

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

從上面的計算可以很容易的看出，該事務數據庫最大頻繁項目集為{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 結論

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

［1］王培吉，趙玉琳，呂劍峰.基于Apriori算法的關聯規則數據挖掘研究［J］.統計與決策，2011(23):19－21.

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

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