王 蒙 方 睿 鄒書蓉

（成都信息工程大學(xué)計(jì)算機(jī)學(xué)院 成都 610225）

1 引言

最經(jīng)典的Apriori算法廣泛用于商業(yè)、教育、衛(wèi)生等領(lǐng)域，于 1994 年被 Rakesh Agrawal等提出［1］，2007年Apriori算法被列為數(shù)據(jù)挖掘十大算法之一［2］，最近幾十年里，大量學(xué)者為了改進(jìn)Apriori算法產(chǎn)生大量的候選集頻繁和反復(fù)地掃描數(shù)據(jù)庫的問題提出了很多卓有成效的方法。徐章艷等［3］提出了Apriori算法的三種優(yōu)化方法，對(duì)連接程序中的候選集進(jìn)行優(yōu)化剪枝，刪除在掃描數(shù)據(jù)庫時(shí)不必要比較的事務(wù)等做了改進(jìn)。但是每次還要反復(fù)回掃數(shù)據(jù)庫。一些國(guó)內(nèi)外學(xué)者用把存儲(chǔ)為布爾矩陣，通過項(xiàng)集向量“與”的操作來代替掃描數(shù)據(jù)庫，通過對(duì)矩陣的操作實(shí)現(xiàn)對(duì)候選集的剪枝大大提高了算法效率［4～6］。文獻(xiàn)［7～9］中通過一次性掃描數(shù)據(jù)庫得到的Tid表（項(xiàng)、事務(wù)、支持度），這個(gè)表格維護(hù)在內(nèi)存中，通過直接操作此表，這樣就不用反復(fù)掃描數(shù)據(jù)，在用頻繁項(xiàng)集連接生成候選項(xiàng)集時(shí)，直接把項(xiàng)的事務(wù)向量求交集。但是沒有在算法運(yùn)行中刪除一些不必比較的事務(wù)，有大量的候選集生成頻繁集時(shí)非常耗時(shí)。

Apriori算法就是通過反復(fù)多次掃描事務(wù)數(shù)據(jù)庫來計(jì)算候選集的支持度，這樣得到頻繁項(xiàng)集后產(chǎn)生關(guān)聯(lián)規(guī)則。但是隨著大量學(xué)者的深入研究，Apriori也存在缺點(diǎn)，對(duì)于超長(zhǎng)長(zhǎng)度的候選集集合，每計(jì)算一個(gè)項(xiàng)集的支持度都要掃描數(shù)據(jù)庫，頻繁的掃描使I/O不堪重負(fù)?；谝陨峡梢姸际窃卺槍?duì)Apriori的常見缺點(diǎn)進(jìn)行改進(jìn)。本文不僅針對(duì)Apri?ori算法常見缺點(diǎn)進(jìn)行改進(jìn)還對(duì)事務(wù)集進(jìn)行精簡(jiǎn)刪除和連接步剪枝步過程優(yōu)化。

2 Apriori算法基本性質(zhì)和改進(jìn)算法的定義

2.1 Apriori算法基本性質(zhì)

針對(duì)以上的Apriori算法缺點(diǎn)，下面給出Apriori算法的性質(zhì)并加以證明。

性質(zhì)1［10］：對(duì)于頻繁項(xiàng)集的任何非空子項(xiàng)集都是頻繁項(xiàng)集。

推論1［10］：根據(jù)性質(zhì)1，它的逆否命題也是成立的，如果一個(gè)非空項(xiàng)集不是頻繁的，那么它的超集也不是頻繁的，它的超集不作為候選項(xiàng)集。

性質(zhì) 2［11］：設(shè) Lk為頻繁 k-項(xiàng)項(xiàng)集集合，其中 I1∈Lk，I1的前k-1項(xiàng)與I2的前k-1相同，若I1的第k項(xiàng)與I2的第k項(xiàng)組成的項(xiàng)集是頻繁2-項(xiàng)集，則I1與I2連接成的候選（k+1）-項(xiàng)集的所有非空子集都是頻繁項(xiàng)集，否則根據(jù)推論2得知此候選（k+1）-項(xiàng)集不可能為頻繁項(xiàng)集。

證明：候選（k+1）-項(xiàng)集的子集有三類：I1的子集、I2的子集、I1的第k項(xiàng)與I2的第k項(xiàng)組成的項(xiàng)集的子集，因?yàn)镮1與I2為頻繁項(xiàng)集，又因I1的第k項(xiàng)與I2的第k項(xiàng)組成的項(xiàng)集是頻繁2-項(xiàng)集，根據(jù)性質(zhì)1得知候選（k+1）-項(xiàng)集的非空子集都是頻繁項(xiàng)集。

性質(zhì)3：若事務(wù)集T中含有可連接的頻繁k-項(xiàng)集的數(shù)量小于等于1，則T不可能包含頻繁（k+1）-項(xiàng)集。

證明：反證法，假設(shè)T具有頻繁（k+1）-項(xiàng)集，則按照兩個(gè)頻繁k-項(xiàng)集的連接成頻繁（k+1）-項(xiàng)集的方式，T中至少有兩個(gè)可連接的頻繁k-項(xiàng)集。與題設(shè)矛盾，故原命題成立。

性質(zhì)4：在一個(gè)頻繁項(xiàng)集集合中，若其中的某個(gè)項(xiàng)集不能與其相鄰的頻繁項(xiàng)集連接，則此項(xiàng)集一定不能與此集合中所有的頻繁項(xiàng)集連接。

證明：反證法，假設(shè)此項(xiàng)集I能與不相鄰的項(xiàng)集I'相連接，則I的前k-1項(xiàng)與I'的前k-1相同，又因項(xiàng)集都是按照字典順序排列，所以從I到I'的所有項(xiàng)集的前k-1項(xiàng)相同，也就是說從I到I'的所有項(xiàng)集都可以連接，又因I'與I不相鄰，所以I也能與相鄰的項(xiàng)集連接這與題設(shè)矛盾，故原命題成立。

2.2 改進(jìn)算法的定義

為了更好地說明改進(jìn)的算法，給出改進(jìn)算法的相關(guān)定義。

定義1：相鄰頻繁項(xiàng)集，k=1時(shí)頻繁1-項(xiàng)集都是相鄰的；k≥2時(shí)，設(shè)Lk為頻繁k-項(xiàng)項(xiàng)集集合，p為L(zhǎng)k內(nèi)的項(xiàng)集個(gè)數(shù)，其中 Ii-1∈Lk、Ii∈ Lk、Ii+1∈ Lk，1＜i＜k時(shí)，若 Ii與 Ii-1或者 Ii與 Ii+1的前 k-1 相同，則判定 Ii為相鄰頻繁項(xiàng)集；i=1時(shí)，若I1與I2前k-1相同，則I1為相鄰頻繁項(xiàng)集；i=k時(shí)，若Ik與Ik-1前k-1相同，則Ik為相鄰頻繁項(xiàng)集。

定義2：相鄰頻繁項(xiàng)集事務(wù)矩陣SN，候選項(xiàng)集事務(wù)矩陣SC，候選項(xiàng)集矩陣H，設(shè)l為事物的個(gè)數(shù)，m為相鄰頻繁k-項(xiàng)集的個(gè)數(shù)，n為候選（k+1）-項(xiàng)集的個(gè)數(shù)，設(shè)｛T1，T2，…，Tl｝為數(shù)據(jù)庫事務(wù)集集合T，其中k≥1。

SN為一個(gè)l×m矩陣，設(shè)｛I1，I2，…，Im｝為相鄰頻繁k-項(xiàng)集集合Nk，若事務(wù)Ti中包含項(xiàng)集Ii則snij=1反之snij=0，其中（i≤l，j≤m）。定義數(shù)組X存儲(chǔ)SN的各行之和也就是統(tǒng)計(jì)各事務(wù)所包含項(xiàng)集的個(gè)數(shù)，根據(jù)性質(zhì)3，找到X中小于2的元素所對(duì)應(yīng)的事務(wù)，刪除該事務(wù)所對(duì)應(yīng)的SN矩陣的行，得到的矩陣為SN'。

H為一個(gè)m×n矩陣，設(shè)｛I'1I'1，…，I'n｝為候選（k+1）-項(xiàng)集集合 Ck+1，若候選集 I'j包含 Ii，則 hij=0.5，反之hij=0，其中Ii∈Nk，（i≤m，j≤n）。

SC為一個(gè)l×n矩陣，若事務(wù)Tu中包含項(xiàng)集I'v則scuv=1，反之scuv=0，其中（u≤l，v≤n），Tu∈T，I'v∈Ck+1，本文定義：

即

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

本文對(duì)Apriori算法進(jìn)行這三個(gè)方面的改進(jìn)，反復(fù)掃描數(shù)據(jù)庫；把不必要的事務(wù)集加入下次數(shù)據(jù)庫掃描；連接步剪枝步比較過程復(fù)雜。

改進(jìn)方法，只掃描一次數(shù)據(jù)庫，存儲(chǔ)為布爾矩陣［12］，利用頻繁k-項(xiàng)集的事務(wù)矩陣與候選（k+1）-項(xiàng)集矩陣相乘得到候選（k+1）-項(xiàng)集事務(wù)矩陣，從而求出頻繁（k+1）-項(xiàng)集；根據(jù)性質(zhì)3刪除不必要的事務(wù)；在判斷連接過程中刪除不相鄰頻繁項(xiàng)僅使用可以相連接的頻繁項(xiàng)進(jìn)行連接并優(yōu)化連接過程。根據(jù)性質(zhì)2對(duì)剪枝步進(jìn)行優(yōu)化。其中本文所有事務(wù)或項(xiàng)集中的項(xiàng)都按字典順序排列。

3.1 算法思想

通過掃描一次事務(wù)數(shù)據(jù)庫產(chǎn)生候選項(xiàng)集事務(wù)矩陣SC，計(jì)算支持度得到頻繁項(xiàng)集L，只掃描一次數(shù)據(jù)庫即可，減少I/O時(shí)間。對(duì)SC進(jìn)行壓縮精簡(jiǎn)，得到SN與相鄰頻繁項(xiàng)集集合Nk，對(duì)SN刪除不必要的事務(wù)，減少參加下次運(yùn)算的事務(wù)數(shù)量，得到SN'，然后通過相鄰頻繁項(xiàng)集連接剪枝生成H，減少連接比較次數(shù)進(jìn)一步優(yōu)化算法，分別刪除SN'與H不能組成候選項(xiàng)集的相鄰頻繁項(xiàng)集對(duì)應(yīng)的列與行。矩陣相乘運(yùn)算SN'*H=SC再次得到下一個(gè)候選項(xiàng)集事務(wù)矩陣SC，多次重復(fù)SN'*H=SC直到Nk為空時(shí)結(jié)束。

3.1.1 連接步的優(yōu)化

相鄰頻繁項(xiàng)集集合Nk，頻繁項(xiàng)集集合Lk，改進(jìn)算法使用Nk來進(jìn)行連接，由性質(zhì)4可知，使用Nk或Lk連接得到的候選項(xiàng)集一致，這樣就避免和非相鄰項(xiàng)集進(jìn)行多次比較，加快了連接速度。改進(jìn)算法對(duì)連接過程也進(jìn)行了優(yōu)化，設(shè)I，I'∈Nk，若I與I'不能連接，顯然I不能與I'之后的所有項(xiàng)集連接，這樣就不用比較I'之后的項(xiàng)集，加快了連接速度，從而提高了算法效率。

3.1.2 生成頻繁項(xiàng)集

候選項(xiàng)集事務(wù)矩陣SC，最小支持度min_sup，定義支持度數(shù)組W存儲(chǔ)SC各列之和。

生成頻繁1-項(xiàng)集，掃描數(shù)據(jù)庫生成布爾矩陣，也就是候選1-項(xiàng)集事務(wù)矩陣SC，候選1-項(xiàng)集集合C1，通過步驟通過W對(duì)支持度小于min_sup的SC的列進(jìn)行刪除和對(duì)應(yīng)C1的項(xiàng)集進(jìn)行刪除得到頻繁1-項(xiàng)集L1，由定義1知N1=L1。

k≥1時(shí)，生成頻繁（k+1）-項(xiàng)集，1）對(duì)相鄰頻繁k-項(xiàng)集集合Nk進(jìn)行連接步后得到候選（k+1）-項(xiàng)集集合Ck。2）由性質(zhì)2可對(duì)Ck+1進(jìn)行剪枝，同時(shí)生成候選項(xiàng)集矩陣H。3）分別刪除SN'與H不能組成候選項(xiàng)集的相鄰頻繁項(xiàng)集對(duì)應(yīng)的列與行。然后SN'*H=SC此時(shí)得到的是候選（k+1）-項(xiàng)集事務(wù)矩陣SC。4）通過W對(duì)支持度小于min_sup的SC的列進(jìn)行刪除和對(duì)應(yīng)Ck+1的項(xiàng)集進(jìn)行刪除得到頻繁（k+1）-項(xiàng)集Lk+1。5）由定義1得到Nk+1，對(duì)SC矩陣刪除非相鄰的頻繁項(xiàng)集的列得到SN，SN刪除不必要的事務(wù)后得到 SN'。循環(huán)執(zhí)行1）～5）直到Nk為空，結(jié)束。

3.2 改進(jìn)算法偽代碼描述

輸入：事務(wù)數(shù)據(jù)庫D，最小支持度min_sup。

輸出：頻繁k-項(xiàng)集Lk，和Lk所包含項(xiàng)集的個(gè)數(shù)LCountk。

Begin

掃描數(shù)據(jù)庫D，生成布爾矩陣。生成頻繁1-項(xiàng)集。

打印輸出 LCount1，L1；

While Nk非空

For r=1 to m（m為Nk中項(xiàng)集的個(gè)數(shù)）

For i=r to m-1

If（Nk｛r｝與Nk+1｛i+1｝滿足連接條件）

Then NEW=Nk｛r｝Nk+1｛i+1｝連接的結(jié)果；

If（根據(jù)性質(zhì)2，NEW的子集是頻繁項(xiàng)集）

Then將NEW寫入Ck+1；

將Nk與Ck+1映射值存入生成的矩陣H；

Else Break；EndIf

Else Break；EndIf EndFor EndFor

分別刪除SN'與H不能組成候選項(xiàng)集的相鄰

頻繁項(xiàng)集對(duì)應(yīng)的列與行。

SN'*H=SC；

Lk+1=Ck+1｛W≥min_sup｝；

打印輸出 LCountk+1，Lk+1；

刪除SC中W＜min_sup所對(duì)應(yīng)的列；

k=k+1；

For（s=1 to n）（n為L(zhǎng)k+1中的項(xiàng)集個(gè)數(shù)）

If（Lk+1｛s｝是相鄰的頻繁項(xiàng)集）

Then把Lk+1｛s｝寫入Nk+1中；

生成非相鄰頻繁項(xiàng)集的索引數(shù)組Del；

EndIf EndFor

SN←刪除SC中的Del對(duì)應(yīng)的列；

SN'←刪除SN中數(shù)組X≤1所對(duì)應(yīng)的行；

EndWhile End

4 算法實(shí)例和實(shí)驗(yàn)對(duì)比

4.1 算法實(shí)例分析

通過實(shí)例來說明改進(jìn)算法思想的運(yùn)行流程，表1為數(shù)據(jù)庫的事務(wù)列表。

表1 數(shù)據(jù)庫事務(wù)列表［10］

設(shè)min_sup=2，改進(jìn)的算法運(yùn)行過程如下。其中會(huì)給出關(guān)鍵矩陣內(nèi)容。

掃描數(shù)據(jù)庫D，得到布爾矩陣SC，C1=｛I1，I2，I3，I4，I5｝，支持度數(shù)組W ≥ min_sup則頻繁1-項(xiàng)集集合L1=｛I1，I2，I3，I4，I5｝，由定義1知SN=SC，N1=L1，X≥2由定義2中的SN生成SN'的過程得知SN=SN'。

第1次循環(huán)，N1不為空，對(duì)N1連接步得到C2=｛｛I1，I2｝，｛I1，I3｝，｛I1，I4｝，｛I1，I5｝，｛I2，I3｝，｛I2，I4｝，｛I2，I5｝，｛I3，I4｝，｛I3，I5｝，｛I4，I5｝｝，根據(jù)定義2中的H矩陣定義，組成H矩陣，其中例如12代表｛I1，I2｝。然后SN'*H=SC，此時(shí)的SC是候選2-項(xiàng)集矩陣。

依據(jù)W ≥ min_sup從C2可得L2=｛｛I1，I2｝，｛I1，I3｝，｛I1，I5｝，｛I2，I3｝，｛I2，I4｝，｛I2，I5｝｝，同時(shí)對(duì)W＜min_sup所對(duì)應(yīng)SC的列進(jìn)行刪除，然后通過定義1刪除L2非相鄰頻繁項(xiàng)集得到N2=｛｛I1，I2｝，｛I1，I3｝，｛I1，I5｝，｛I2，I3｝，｛I2，I4｝，｛I2，I5｝｝，同時(shí)把SC 非相鄰的項(xiàng)集的列刪除得到SN，根據(jù)性質(zhì)3，數(shù)組 X≤1所對(duì)應(yīng)的SN的行刪除得到SN'。

第2次循環(huán)，N2不為空，對(duì)N2進(jìn)行連接得到C3=｛｛I1，I2，I3｝，｛I1，I2，I5｝，｛I1，I3，I5｝，｛I2，I3，I4｝，｛I2，I3，I5｝，｛I2，I3，I5｝｝。根據(jù)性質(zhì)2剪枝后的C3=｛｛I1，I2，I3｝，｛I1，I2，I5｝｝同時(shí)生成H，分別刪除SN'與H不能組成候選項(xiàng)集的相鄰頻繁項(xiàng)集集合｛｛I2，I3｝，｛I2，I4｝，｛I2，I5｝｝對(duì)應(yīng)的列與行。然后SN'*H=SC，其中123表示｛I1；I2；I3｝。

此時(shí)的SC是候選3-項(xiàng)集矩陣，依據(jù)W≥min_sup從C3可得 L3=｛｛I1，I2，I3｝，｛I1，I2，I5｝｝，然后得到N3=｛I1，I2，I3｝，｛I1，I2，I5｝｝，同時(shí)把SC非相鄰的項(xiàng)集的列刪除得到SN，根據(jù)性質(zhì)3，數(shù)組X≤1所對(duì)應(yīng)的SN的行刪除得到SN'。

第3次循環(huán)，N3不為空，對(duì)N3進(jìn)行連接得到C3=｛｛I1，I2，I3，I5｝｝。根據(jù)性質(zhì)2剪枝后的C3=空，N4也為空。

第4次循環(huán)，N4為空，算法結(jié)束。

4.2 實(shí)驗(yàn)對(duì)比分析

4.2.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

將Apriori算法和本文的改進(jìn)的算法在MAT?LAB R2015b中實(shí)現(xiàn)，計(jì)算機(jī)實(shí)驗(yàn)環(huán)境為Win7x64操作系統(tǒng)，8GRAM，1T硬盤，Intel Core-i5處理器，數(shù)據(jù)集采用經(jīng)典的MushRoom數(shù)據(jù)集，下載網(wǎng)址：http：//fimi.ua.ac.be/data/，該數(shù)據(jù)集有8124個(gè)事務(wù)，119個(gè)項(xiàng)。

4.2.2 實(shí)驗(yàn)結(jié)果

表 2中 1（0.3）表 示 的 是 Apriori算 法 在min_sup=0.3的情況下，2（0.3）表示的是改進(jìn)后算法在min_sup=0.3的情況下。k的值就是頻繁k-項(xiàng)集。

表2 兩種算法所得到的頻繁項(xiàng)集個(gè)數(shù)對(duì)比

兩種算法在119個(gè)項(xiàng)，8124個(gè)事務(wù)的mushroom數(shù)據(jù)集，最小支持在0.3～0.9之間，同種環(huán)境下運(yùn)行得到頻繁集結(jié)果一致。改進(jìn)算法的準(zhǔn)確性得到驗(yàn)證。

圖1 不同支持度下兩種算法的運(yùn)行時(shí)間對(duì)比

圖2 不同項(xiàng)的兩種算法運(yùn)行時(shí)間對(duì)比

實(shí)驗(yàn)一在mushroom數(shù)據(jù)集下，min_sup在0.3～0.9之間變化，比較兩種算法的運(yùn)行時(shí)間，從圖1中可以看出在支持度逐漸增大過程中兩種算法的運(yùn)行時(shí)間都存在著下降最后趨近于0，但是Apriori算法的時(shí)間在支持度小的時(shí)候運(yùn)行時(shí)間明顯大于改進(jìn)的算法，改進(jìn)的算法的在不同的min_sup情況下運(yùn)行時(shí)間沒有很大的波動(dòng)。

實(shí)驗(yàn)二在不同mushroom數(shù)據(jù)集的項(xiàng)的個(gè)數(shù)，在min_sup=0.3得情況下兩種算法運(yùn)行的時(shí)間比較，從圖2可以看出隨著項(xiàng)的個(gè)數(shù)增長(zhǎng)兩種算法運(yùn)行時(shí)間都有所增長(zhǎng)，開始兩種算法的時(shí)間相差不是太大，后面的時(shí)候Apriori算法的時(shí)間遠(yuǎn)遠(yuǎn)大于改進(jìn)的算法，說明原算法面對(duì)項(xiàng)數(shù)多的數(shù)據(jù)集的情況下嚴(yán)重影響運(yùn)行時(shí)間，改進(jìn)算法時(shí)間增長(zhǎng)平緩。

綜上，改進(jìn)算法在不同支持度下和不同項(xiàng)的情況下表現(xiàn)出更好的性能。

5 結(jié)語

本文提出基于矩陣改進(jìn)的Apriori算法，通過矩陣相乘改進(jìn)了Apriori算法反復(fù)多次掃描數(shù)據(jù)庫巨大的I/O負(fù)載的問題［13］，改進(jìn)了連接剪枝候選集的方式避免產(chǎn)生巨量的候選集大大提高了算法效率，刪除不必要的事務(wù)集減少了不必要的比較，通過實(shí)驗(yàn)可以看出改進(jìn)算法大大的降低了運(yùn)行時(shí)間，改進(jìn)算法的效果明顯。未來的工作是讓算法在大數(shù)據(jù)集的情況中表現(xiàn)很高的性能，通過優(yōu)化矩陣存儲(chǔ)方式減少內(nèi)存負(fù)載［14］，通過并行方法［15～16］優(yōu)化矩陣相乘等方式讓算法具有更好的效率。