王錚 周國(guó)光

重慶大學(xué)計(jì)算機(jī)學(xué)院 重慶 400044

0 引言

為了方便快速的從事務(wù)數(shù)據(jù)庫(kù)中挖掘出頻繁項(xiàng)集，本文依據(jù)Apriori算法的思路加以改進(jìn)，將事務(wù)數(shù)據(jù)庫(kù)轉(zhuǎn)換成0-1矩陣，通過0-1矩陣可很快計(jì)算出各個(gè)候選集的支持度計(jì)數(shù)，省去了 Apriori算法中的連接步驟和刪除步驟這樣避免了傳統(tǒng)Apriori算法頻繁掃描數(shù)據(jù)庫(kù)的操作，從而提高了算法的效率。

1 關(guān)聯(lián)規(guī)則Apriori算法

Apriori算法是R.Agrawal和R.Srikant于1994年提出的為布爾關(guān)聯(lián)規(guī)則挖掘頻繁項(xiàng)集的原創(chuàng)性算法。Apriori使用一種稱作逐層搜索的迭代方法，k項(xiàng)集用于探索(k+1)項(xiàng)集。首先，通過掃描數(shù)據(jù)庫(kù)，累積每個(gè)項(xiàng)的計(jì)數(shù)，并收集滿足最小支持度的項(xiàng)，找出頻繁1項(xiàng)集的集合。該集合記作L1。然后L1用于找頻繁2項(xiàng)集的集合L2，L2用于找L3，如此下去，直到不能再找到頻繁k項(xiàng)集。找每個(gè)Lk需要一次數(shù)據(jù)庫(kù)掃描。為提高頻繁項(xiàng)集逐層產(chǎn)生的效率，Apriori算法利用了一個(gè)性質(zhì)用于壓縮搜索空間。Apriori性質(zhì):頻繁項(xiàng)集的所有非空子集也必須是頻繁的 Apriori性質(zhì)在挖掘頻繁項(xiàng)集中的應(yīng)用可以用Lk-1產(chǎn)生Lk為例來(lái)說明，用Lk-1產(chǎn)生Lk包含兩步，即連接步和剪枝步。

（1）連接步：由Apriori性質(zhì)，頻繁項(xiàng)集的子集一定頻繁。Lk的任一項(xiàng)集一定是Lk-1某項(xiàng)集的超集。通過Lk-1內(nèi)部項(xiàng)集間的連接，生成候選 k-項(xiàng)集記作Ck。如果兩個(gè)項(xiàng)集有(k-2)個(gè)相同的項(xiàng)，Lk-1的元素是可連接的。

（2）剪枝步：由Apriori性質(zhì)：任何非頻繁的(k-1)項(xiàng)集都不是頻繁k項(xiàng)集的子集。因此如果候選k項(xiàng)集的(k-1)項(xiàng)子集不在Lk-1中，則改候選也不可能是頻繁的，從而從Ck中刪除。

2 改進(jìn)算法

2.1 Apriori算法缺陷

Apriori算法作為關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法，能夠比較有效的產(chǎn)生頻繁項(xiàng)集，但也存在幾個(gè)缺陷：

（1）掃描數(shù)據(jù)庫(kù)的次數(shù)太多，每次尋找k頻繁項(xiàng)目集時(shí)都需要掃描數(shù)據(jù)庫(kù)來(lái)獲得候選集的支持度，共需掃描n次，如果數(shù)據(jù)庫(kù)很大則算法效率太低。

（2）利用k頻繁項(xiàng)集連接產(chǎn)生(k+1)候選項(xiàng)集，判斷連接條件時(shí)重復(fù)次數(shù)太多。

2.2 Apriori算法改進(jìn)

針對(duì)以上情況，產(chǎn)生了一種基于矩陣的改進(jìn) Apriori算法。它將矩陣的思想應(yīng)用到Apriori算法中，將數(shù)據(jù)庫(kù)表示成矩陣的形式。改進(jìn)算法思想可描述為：成員表示行向量，事務(wù)表示列向量，若第i個(gè)成員在第j個(gè)事務(wù)中，則矩陣的第i行，第j列的值為1，否則為0，稱其為數(shù)據(jù)庫(kù)的布爾矩陣。求頻繁k項(xiàng)集之前，先統(tǒng)計(jì)每個(gè)項(xiàng)目Ii在頻繁k-1項(xiàng)集中出現(xiàn)的次數(shù)b，如果b小于 min_sup，則刪除事務(wù)矩陣中的第Ii行。隨著k值的變大，事務(wù)矩陣將變得越來(lái)越小，從而提高了算法的效率。

3 實(shí)例分析

給出的事務(wù)數(shù)據(jù)庫(kù)如圖1所示，設(shè)最小支持度min_sup=2，利用上述改進(jìn)算法，找出頻繁k-項(xiàng)集。

圖1 事務(wù)數(shù)據(jù)庫(kù)

（1）根據(jù)事務(wù)數(shù)據(jù)庫(kù)構(gòu)造出事務(wù)矩陣，如圖2所示。

圖2 將事務(wù)數(shù)據(jù)庫(kù)變換為事務(wù)矩陣

（2）求頻繁1項(xiàng)集。第i行為1的個(gè)數(shù)之和就是Ii的出現(xiàn)次數(shù)。從上面的矩陣可看出只有I6的次數(shù)為1小于min_sup，故矩陣變成如圖3所示，得到頻繁1項(xiàng)集 L1={I1, I2,I3, I4,I5}

圖3 修建后的矩陣

（3）k=2求頻繁2項(xiàng)集。Ii, Ij為1就是分別計(jì)算第i行和第j行同時(shí)為1的個(gè)數(shù)和。從圖2的矩陣可求出{I1,I2}=4,{I1,I3}=3,{I1,I4}=1,{I1,I5}=2,{I2,I3}=4,{I2,I4}=2,{I2,I5}=2,{I3,I4}=0,{I3,I5}=1,{I4,I5}=0。得到頻繁 2項(xiàng)集 L2={{I1,I2 },{I1,I 3},{I1,I5 },{I2 ,I3 },{I2 ,I4 },{I2 ,I5 }}。然后統(tǒng)計(jì)每個(gè)項(xiàng)目在L2中出現(xiàn)的次數(shù)，可看出I4只出現(xiàn)了一次小于min_sup，所有刪除圖3矩陣的I4行(如圖4)。

圖4 再次修建后的矩陣

（4）k=3求頻繁3項(xiàng)集。對(duì)圖4的矩陣4個(gè)行向量取3行任意組合。連接運(yùn)算有{.I1,I2,I3}{ I1,I2,I5,}{,{I1,I3,I5},I2,I3,I5}4個(gè)三項(xiàng)集。從圖 4的矩陣中看出{I1,I2,I3}支持度計(jì)數(shù)為 2{I1,I2,I5}支持度計(jì)數(shù)為2,{I2,I3,I5}支持度計(jì)數(shù)為1，{I1,I3,I5}的支持度計(jì)數(shù)為 1。因此頻繁 3項(xiàng)集 L2={{I1,I2 ,I 3},{I1,I2 ,I5 }，此時(shí)頻繁項(xiàng)集的個(gè)數(shù)小于4，循環(huán)結(jié)束。

4 小結(jié)

關(guān)聯(lián)規(guī)則挖掘是當(dāng)前數(shù)據(jù)挖掘領(lǐng)域的主要研究課題，本文介紹的基于矩陣的關(guān)聯(lián)規(guī)則挖掘算法直接對(duì)布爾矩陣的行向量進(jìn)行按位與運(yùn)算產(chǎn)生頻繁項(xiàng)集，有效的解決了Apriori算法經(jīng)連接和剪枝迭代產(chǎn)生頻繁項(xiàng)集的問題，同時(shí)將事務(wù)數(shù)據(jù)庫(kù)轉(zhuǎn)換成矩陣可減少存儲(chǔ)空間。

[1]馬盈倉(cāng).挖掘關(guān)聯(lián)規(guī)則中 Aproori 算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用與軟件.2004.

[2]Jiawei Han,Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)[M].北京:機(jī)械工業(yè)出版社.2001.

[3]梅成.基于矩陣的 Apriori 算法的優(yōu)化[J].江西:計(jì)算機(jī)與現(xiàn)代化.2008.