基于C#的Apriori算法的實現(xiàn)及其改進策略

董袁泉

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

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

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

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

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

1.2 Apriori算法的基本思想

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

（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算法的缺點

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

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

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

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

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

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

4、生成候選項集

5、用Apriori算法進行迭代

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

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

3 Apriori算法的改進

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

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

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

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

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

其中i=l,2,3…,m，j=l,2,3…,n.具體實例如下：設(shè)有項目I={A,B,C,D,E,F},交易數(shù)據(jù)庫為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來表示項集I的一個項目，每一個行向量表示一個交易記錄.

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

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

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

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

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

由于Apriori算法可能產(chǎn)生大量的候選集以及需要重復(fù)掃描數(shù)據(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ù)庫生成布爾矩陣，布爾矩陣的各個元素的值按照上述定義1和定義3求得，然后通過統(tǒng)計項目的支持數(shù)計算得到頻繁1-項集.

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

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

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

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

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

3.3 MV-Apriori算法的描述

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

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

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

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

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

3.4 MV-Apriori算法的實例說明

假設(shè)有如下事務(wù)數(shù)據(jù)庫（見表1），其中包含事務(wù)標識T以及項目Item.

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

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

3.5 MV-Apriori算法分析

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

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

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

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

圖2 MV-Apriori算法裁剪生成頻繁項集過程

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

圖3 兩種算法找頻繁項集時間對比

4 結(jié)束語

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

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

[2]屈世富、萬旺根、劉維曉.一種改進的關(guān)聯(lián)規(guī)則挖掘算法[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].微計算機信息，2009，25（12）：213-215.

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

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

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

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