董袁泉

（沙洲職業(yè)工學(xué)院，江蘇 張家港 215600）

數(shù)據(jù)挖掘是從大量數(shù)據(jù)中提取或“挖掘”知識(shí).它是根據(jù)人們的特定要求，從大量的數(shù)據(jù)中找出所需的信息.關(guān)聯(lián)規(guī)則挖掘就是發(fā)現(xiàn)信息存儲(chǔ)中的大量數(shù)據(jù)項(xiàng)之間隱藏的、有趣的規(guī)律[1].Apriori算法是最經(jīng)典的關(guān)聯(lián)規(guī)則算法，該算法的主要思想是采用逐層迭代的方法通過(guò)低維頻繁項(xiàng)集得到高維頻繁項(xiàng)集.但是Apri?ori算法在實(shí)際應(yīng)用中，還存在不令人滿意的地方，可能產(chǎn)生大量的候選集以及需要重復(fù)掃描數(shù)據(jù)庫(kù).因此，本文提出了一種基于矩陣的關(guān)聯(lián)規(guī)則挖掘算法，通過(guò)掃描一次數(shù)據(jù)庫(kù)得到所有數(shù)據(jù)信息，利用布爾矩陣的相關(guān)性質(zhì)對(duì)候選項(xiàng)集的支持度進(jìn)行計(jì)數(shù)并引入了向量?jī)?nèi)積的思想，在自然連接以前先進(jìn)行一個(gè)修剪過(guò)程，減少參加連接的項(xiàng)集數(shù)量，減小生成的候選項(xiàng)集規(guī)模，減少了循環(huán)迭代次數(shù)和運(yùn)行時(shí)間，同時(shí)在連接判斷步驟中減少多余的判斷次數(shù)，從而大大提高了算法的性能.

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

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

假設(shè)I是項(xiàng)的集合.給定一個(gè)交易數(shù)據(jù)庫(kù)D，其中每個(gè)事務(wù)（Transaction）t是I的非空子集，每一個(gè)交易都與一個(gè)唯一的標(biāo)識(shí)符TID[2]（Transaction ID）對(duì)應(yīng).關(guān)聯(lián)規(guī)則在D中的支持度（support）是D中事務(wù)同時(shí)包含X、Y的百分比，即概率；置信度（confidence）是包含X的事務(wù)中同時(shí)又包含Y的百分比，即條件概率.如果滿足最小支持度閾值和最小置信度閾值.這些閾值根據(jù)挖掘需要人為設(shè)定.

1.2 Apriori算法的基本思想

Apriori算法[3]是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法.在該算法中，所有支持度大于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集，簡(jiǎn)稱頻集.該算法的核心思想描述如下：

（1）L1=find_frequent_1-itemsets(D);

（2）for(k=2;Lk-1≠?;k++){

（3）Ck=apriori-gen(Lk-1,min_sup);

（4）for each transaction t?D{

（5）Ct=subset(Ck,t);

（6）for each candidate c?Ct

（7）c.count++;

（8）}

（9）Lk={c?Ck|c.count≥min_sup}

（10）}

（11）return L=ULk;

1.3 Apriori算法的缺點(diǎn)

Apriori算法利用逐層搜索的迭代方法來(lái)尋找頻繁項(xiàng)集，用k-項(xiàng)集探索（k+1）-項(xiàng)集.首先產(chǎn)生頻繁1-項(xiàng)集L1，然后是頻繁2-項(xiàng)集L2，如此下去，直到不能找到頻繁k-項(xiàng)集[4].可能產(chǎn)生大量的候選集以及需要重復(fù)掃描數(shù)據(jù)庫(kù)，是Apriori算法的兩大缺點(diǎn).

2 Apriori算法的C#實(shí)現(xiàn)

Apriori算法可以有多種實(shí)現(xiàn)方式，比較常見(jiàn)的有C語(yǔ)言和Java實(shí)現(xiàn)的方式，本文利用C#語(yǔ)言實(shí)現(xiàn)Aprio?ri算法.在主程序中主要實(shí)現(xiàn)了以下5個(gè)步驟，分別完成如下功能：

1、由指定的CommandString從數(shù)據(jù)庫(kù)中獲得數(shù)據(jù)

2、從數(shù)據(jù)庫(kù)中獲得事務(wù)集

3、從數(shù)據(jù)庫(kù)中得到候選一項(xiàng)集

4、生成候選項(xiàng)集

5、用Apriori算法進(jìn)行迭代

具體測(cè)試時(shí)采用SQL Server 2008中的Adventure?WorksDW數(shù)據(jù)庫(kù)中的視圖vAssocSeqOrders和vAssocSe?qLineItems來(lái)生成事務(wù)集，包含2個(gè)字段OrderNumber(訂單號(hào))和Model(購(gòu)買產(chǎn)品型號(hào))，共有21255條記錄；測(cè)試時(shí)最小支持度sup設(shè)定為0.05即最小支持?jǐn)?shù)為21255*0.05=1063，程序運(yùn)行結(jié)果見(jiàn)圖1，結(jié)果中輸出了頻繁項(xiàng)集和支持?jǐn)?shù).其中支持?jǐn)?shù)最小的1083，大于程序中設(shè)定的1063，證明了程序的正確性.

圖1 程序運(yùn)行結(jié)果

3 Apriori算法的改進(jìn)

3.1 相關(guān)定義和推論

設(shè)I={i1,i2,i3…,in}是項(xiàng)的集合，數(shù)據(jù)庫(kù)D是數(shù)據(jù)庫(kù)事務(wù)的交易集合，每個(gè)事務(wù)T是相關(guān)項(xiàng)的集合，T?I，用Tm表示其中的每個(gè)事務(wù)[5].

定義1一個(gè)矩陣中的所有元素均為0或者1.

定義2[5]每個(gè)項(xiàng)Ij的向量定義為其中Ti為第i個(gè)事務(wù)，

定義3D轉(zhuǎn)換為矩陣G的每一個(gè)元素{Aij}定義為

其中i=l,2,3…,m，j=l,2,3…,n.具體實(shí)例如下：設(shè)有項(xiàng)目I={A,B,C,D,E,F},交易數(shù)據(jù)庫(kù)為t1={A,B,C}，t2={A,C,E}，t3={A,C,E,F}，t4={A,B,C,D,E}，t5={B,C,D,F}. 生成的布爾矩陣為：

并且使用列向量Ri來(lái)表示項(xiàng)集I的一個(gè)項(xiàng)目，每一個(gè)行向量表示一個(gè)交易記錄.

定義4[6]：布爾矩陣中，每一項(xiàng)Ri的向量定義[7]為=Ri(t1i，t2i…，tni)，supp(Ri)表示算法中該向量的支持度：supp(Ri)=t1i+t2+…+tni.例如上例中項(xiàng)目B的支持?jǐn)?shù)為supp(B)=1+0+0+1+1=3.

定義5：向量?jī)?nèi)積＜Ri，Rj，>表示為布爾矩陣中項(xiàng)集{Ri，Rj}的向量?jī)?nèi)積，＜Ri，Rj>=supp(Rij)=t1i×t1j+t2i×t2j+…+tni×tnj.supp(Rij)代表布爾矩陣中項(xiàng)集{Ri，Rj}的支持度，表示所有事務(wù)同時(shí)出現(xiàn)Ri和Rj的事務(wù)記錄的個(gè)數(shù).

性質(zhì)1[5]：定義Lk表示為L(zhǎng)k中包含j的頻繁項(xiàng)集的個(gè)數(shù)，如果＜k，若k-項(xiàng)集X={i1，i2，…ik}中存在一個(gè)項(xiàng)j?X，則在頻繁k-項(xiàng)集產(chǎn)生(k+1)-項(xiàng)候選集時(shí)，可以把該數(shù)據(jù)裁剪掉.

證明設(shè)X是(k+1)-項(xiàng)頻繁集，則它的k+1個(gè)k-子集均在Lk中.則在生成的k+1個(gè)k-子集中，每一個(gè)項(xiàng)目j∈X共出現(xiàn)k次，?j∈X，均有>k.因此，如果出現(xiàn)＜k，不可能產(chǎn)生(k+1)-項(xiàng)集.

3.2 基于布爾矩陣和向量?jī)?nèi)積的MV-Apriori算法

由于Apriori算法可能產(chǎn)生大量的候選集以及需要重復(fù)掃描數(shù)據(jù)庫(kù)，本文提出了一種基于布爾矩陣和向量?jī)?nèi)積的關(guān)聯(lián)規(guī)則挖掘算法MV-Apriori（Association Rule Mining Algorithm Based on Boolean-matrix and Vector-inner-product），該算法步驟如下：

（1）掃描事務(wù)數(shù)據(jù)庫(kù)生成布爾矩陣，布爾矩陣的各個(gè)元素的值按照上述定義1和定義3求得，然后通過(guò)統(tǒng)計(jì)項(xiàng)目的支持?jǐn)?shù)計(jì)算得到頻繁1-項(xiàng)集.

（2）利用頻繁1-項(xiàng)集連接生成候選2-項(xiàng)集，構(gòu)造一個(gè)2維布爾行向量S2，S2中所有元素均為1，然后將候選2-項(xiàng)集組成的向量集與S2進(jìn)行內(nèi)積運(yùn)算，得到候選項(xiàng)集支持?jǐn)?shù).

下面以實(shí)例說(shuō)明說(shuō)明具體的運(yùn)算方法，首先將一個(gè)2-項(xiàng)候選集所代表的2個(gè)列向量根據(jù)定義2表示為m行2列的向量：，（其中 k＜j）.

S2與該向量的每一行(記為Hi)與進(jìn)行內(nèi)積運(yùn)算，根據(jù)前面的思想選取布爾向量S2=(1 1)，Hi=(1 1)表示兩個(gè)項(xiàng)目均在同一事務(wù)i中出現(xiàn)，表示該2-項(xiàng)候選集有一項(xiàng)支持計(jì)數(shù)，引入一個(gè)算式int來(lái)得到這次計(jì)數(shù)，其中int[]表示取整數(shù)，＜，>表示內(nèi)積運(yùn)算.由于Hk，j是m行2列的向量，所以需要它進(jìn)行m次內(nèi)積運(yùn)算，引入公式表示該2-項(xiàng)候選集與2維布爾行向量?jī)?nèi)積運(yùn)算得到的2-項(xiàng)集的支持計(jì)數(shù).通過(guò)與最小支持度比較，得到頻繁2-項(xiàng)集.

（3）對(duì)項(xiàng)集中出現(xiàn)的其他項(xiàng)目同樣進(jìn)行計(jì)數(shù)，然后對(duì)頻繁2-項(xiàng)集進(jìn)行一次裁剪，根據(jù)性質(zhì)1，如果某個(gè)項(xiàng)目在2-項(xiàng)集的支持計(jì)數(shù)小于2，則裁剪掉包含該項(xiàng)目的所有頻繁2-項(xiàng)集，從而得到新的頻繁2-項(xiàng)集，這樣就可以大大減少3-候選集的數(shù)目，因?yàn)?-項(xiàng)候選集是由頻繁2-項(xiàng)集連接生成的.

（4）構(gòu)造三維布爾行向量與候選3-項(xiàng)集進(jìn)行內(nèi)積，計(jì)算得到3-項(xiàng)集的計(jì)數(shù)，如果某個(gè)項(xiàng)目在3-項(xiàng)集的支持計(jì)數(shù)小于3，則進(jìn)行裁剪生成頻繁3-項(xiàng)集；如果要生成k項(xiàng)候選集，則首先對(duì)k-1頻繁項(xiàng)集進(jìn)行裁剪，然后構(gòu)造k維行向量Sk，k-項(xiàng)候選集的支持計(jì)數(shù)為：然后裁剪得到k-項(xiàng)頻繁集.

3.3 MV-Apriori算法的描述

假設(shè)最小支持度記為min_supp，事務(wù)交易數(shù)據(jù)庫(kù)記為D；那么最小支持?jǐn)?shù)minsupp_count=|D|*min_supp)，.根據(jù)上面的分析，MV-Apriori算法和Apriori算法相比，增加了如下過(guò)程：

（1）把交易數(shù)據(jù)庫(kù)D轉(zhuǎn)換為布爾矩陣G.

（2）構(gòu)造K維布爾向量，與候選K-項(xiàng)集進(jìn)行內(nèi)積運(yùn)算，并求得支持計(jì)數(shù).

（3）把支持計(jì)數(shù)與最小支持度相比進(jìn)行裁剪，求出K-項(xiàng)頻繁集.

具體算法過(guò)程及其偽代碼描述如下：

3.4 MV-Apriori算法的實(shí)例說(shuō)明

假設(shè)有如下事務(wù)數(shù)據(jù)庫(kù)（見(jiàn)表1），其中包含事務(wù)標(biāo)識(shí)T以及項(xiàng)目Item.

該事務(wù)數(shù)據(jù)庫(kù) D包含共10個(gè)事務(wù)(T1，T2，…，T10)，6個(gè)項(xiàng)目(A，B，C，D，E，F(xiàn))，假設(shè)最小支持度為30%，那么最小支持?jǐn)?shù)為0.3*10=3.根據(jù)MV-Apriori算法，得到如圖2所示的圖例說(shuō)明.最后輸出頻繁項(xiàng)集為L(zhǎng)={B，C，D，E，F(xiàn)，BC，BE，BF，CE，CF，DE，EF，BEF，CEF}.

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

3.5 MV-Apriori算法分析

MV-Apriori算法的主要優(yōu)點(diǎn)在于：

1.在生成k-候選項(xiàng)集之前，對(duì)Lk-1頻繁項(xiàng)集中參與組合的元素進(jìn)行計(jì)數(shù)處理，然后進(jìn)行優(yōu)化裁剪，這就降低了組合的可能性.如果對(duì)大型的數(shù)據(jù)庫(kù)而言，這種時(shí)間開(kāi)銷的降低對(duì)數(shù)據(jù)挖掘效率來(lái)說(shuō)是顯而易見(jiàn)的，MV-Apriori算法只掃描數(shù)據(jù)庫(kù)一次，時(shí)間復(fù)雜度為O(mkn)[8]，其中mxn對(duì)應(yīng)于矩陣的行數(shù)和列數(shù)，k為頻集的階數(shù).而Apriori算法掃描數(shù)據(jù)庫(kù)的時(shí)間復(fù)雜度為O(|D|k+1)，|D|>>m.

2.MV-Apriori算法對(duì)數(shù)據(jù)庫(kù)進(jìn)行了掃描后的重新生成“刪除”一些不支持頻繁項(xiàng)集的記錄，這里所謂的刪除實(shí)際上是把不符合再次掃描比較條件的記錄與數(shù)據(jù)庫(kù)末端的記錄進(jìn)行交換，這會(huì)增加一些時(shí)間和I/O的開(kāi)銷，但是隨著循環(huán)次數(shù)的增加，本算法對(duì)以后通過(guò)掃描“新的數(shù)據(jù)庫(kù)”中產(chǎn)生頻繁項(xiàng)集的優(yōu)勢(shì)將體現(xiàn)出來(lái)，因?yàn)椤靶碌臄?shù)據(jù)庫(kù)”記錄將呈現(xiàn)幾何級(jí)數(shù)的降低.

本文采用SQL Server 2008中的AdventureWorksDW數(shù)據(jù)庫(kù)中的視圖vAssocSeqOrders和vAssocSeqLin?eItems來(lái)生成模擬數(shù)據(jù)，在Windows7(Intel(R)Core(TM)i3-2330M CPU2.2GHZ、內(nèi)存為2GB)平臺(tái)、SQL Serv?er2008和VS2010的環(huán)境下進(jìn)行仿真.MV-Apriori算法與Apriori算法在不同的支持度下找出所有的頻繁項(xiàng)集所用時(shí)間的對(duì)比如圖3所示.其中橫坐標(biāo)表示支持度的閾值(100%)，縱坐標(biāo)表示所用的時(shí)間(s).

圖2 MV-Apriori算法裁剪生成頻繁項(xiàng)集過(guò)程

從圖3可以看到在支持度不同時(shí)兩種算法的執(zhí)行時(shí)間差別，優(yōu)化后的MV-Aprior算法在執(zhí)行時(shí)間上優(yōu)于Apriori算法，MV-Aprior在對(duì)Lk-1連接生成CK之前進(jìn)行了修剪，通過(guò)計(jì)數(shù)刪除掉了包含出現(xiàn)次數(shù)小于k-1的項(xiàng)目集，這樣排除了不可能成為k項(xiàng)集的元素，減少了下一步CK中侯選項(xiàng)集的數(shù)量；在支持度越小的情況下，這種優(yōu)勢(shì)更加明顯，這表明了MV-Aprior算法比Apriori算法有更好的效率.在支持度變大的情況下，該數(shù)據(jù)集的項(xiàng)集規(guī)模將逐漸變小，但MV-Aprior的效率仍然優(yōu)于Apriori算法.

圖3 兩種算法找頻繁項(xiàng)集時(shí)間對(duì)比

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

Apriori算法是關(guān)聯(lián)規(guī)則中的經(jīng)典算法，文中主要對(duì)Apriori算法進(jìn)行研究分析之后，采用C#語(yǔ)言對(duì)算法進(jìn)行了實(shí)現(xiàn).在分析了Apriori算法的基礎(chǔ)上，指出了Apriori算法的局限性，提出了新的MV-Apriori改進(jìn)算法.改進(jìn)的算法在每次生成候選項(xiàng)集之后，刪除其中沒(méi)有用的項(xiàng)集，可以大大減少下一步接連生成的項(xiàng)集數(shù)量，從而減少數(shù)據(jù)庫(kù)掃描次數(shù)，節(jié)省算法過(guò)程所需的存儲(chǔ)空間，減少運(yùn)算時(shí)間.仿真結(jié)果也表明，采用改進(jìn)后的Apriori算法可以使掃描次數(shù)減少大概一半，當(dāng)數(shù)據(jù)庫(kù)規(guī)模非常大時(shí)，掃描和比較時(shí)間的縮減將更加明顯，這將對(duì)提高關(guān)聯(lián)規(guī)則挖掘的效率起到積極作用.

[1]邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法[M].北京：科學(xué)出版社，2009：12.

[2]屈世富、萬(wàn)旺根、劉維曉.一種改進(jìn)的關(guān)聯(lián)規(guī)則挖掘算法[J].計(jì)算機(jī)科學(xué)，2010，37（7A）：199-202.

[3]AGRWALR,SRIKANR.Fast algorithms for mining association rules in large databases[C].Chile:Santiago,1994:487-499.

[4]徐嘉莉.一種基于矩陣壓縮的Apriori優(yōu)化算法[J].微計(jì)算機(jī)信息，2009，25（12）：213-215.

[5]李唐平.基于矩陣的關(guān)聯(lián)規(guī)則算法與Apr1ori算法的研究及改進(jìn)[D].成都：西南交通大學(xué)，2009.

[6]李超，余昭平.基于矩陣的Apriori算法改進(jìn)[J].計(jì)算機(jī)工程，2006，32（23）：68-69.

[7]王培吉，王培靜，白金牛.關(guān)聯(lián)規(guī)則挖掘的一種改進(jìn)算法[J].包頭鋼鐵學(xué)院學(xué)報(bào)，2003，22（1）：86-89.

[8]苗苗苗，王玉英.基于矩陣壓縮的Apriori算法改進(jìn)的研究[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（1）：159-162.