田磊，崔廣才，何旭，陳建新

（長春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春 130022）

基于聚類布爾矩陣的Apriori算法的研究

田磊，崔廣才，何旭，陳建新

（長春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春 130022）

針對(duì)聚類布爾矩陣的Apriori算法—CBM_Apriori算法的不足之處，提出了一種基于聚類布爾矩陣的Eclat算法—CBM_Eclat算法。該算法首先對(duì)布爾矩陣使用K-medoids算法，獲得權(quán)值和聚類后的布爾矩陣；然后將聚類后的布爾矩陣轉(zhuǎn)換成Tidset，并采用邏輯“交操作”運(yùn)算，進(jìn)而有效地減少了聚類布爾矩陣存儲(chǔ)和候選項(xiàng)集的生成，提高了該算法的執(zhí)行效率。通過實(shí)例應(yīng)用和算法執(zhí)行結(jié)果都能夠證明CBM_Eclat算法具有可行性和有效性。

CBM_Apriori算法；CBM_Eclat算法；布爾矩陣；K-medoids算法；Tidset

關(guān)聯(lián)規(guī)則最常見的算法是Apriori算法［1］和FP-Growth算法［2］，它們都是水平數(shù)據(jù)表示法［3］挖掘頻繁項(xiàng)集，但是這兩種算法都有著自己的缺陷，Apriori算法的缺陷是反復(fù)掃描事務(wù)數(shù)據(jù)庫和產(chǎn)生大量的候選項(xiàng)集，而FP-Growth算法的缺陷是占用大量的內(nèi)存空間。于是，研究者們對(duì)它們的缺陷進(jìn)行了大量的研究，提出了許多改進(jìn)的方法，從而提高了算法的運(yùn)行效率以及減少了存儲(chǔ)空間。

本文是針對(duì)聚類布爾矩陣的Apriori算法—CBM_Apriori算法［4］，該算法只需要掃描事務(wù)數(shù)據(jù)庫一次，但是，還會(huì)產(chǎn)生大量的候選項(xiàng)集。于是，本文對(duì)該缺點(diǎn)進(jìn)行改進(jìn)，對(duì)事務(wù)數(shù)據(jù)庫使用垂直數(shù)據(jù)表示方法［5-6］，提出了一種基于聚類布爾矩陣的Eclat算法—CBM_Eclat算法，該算法也僅需要掃描事務(wù)數(shù)據(jù)庫一次即可，減少了候選項(xiàng)集的生成，從而提高了算法的執(zhí)行效率。

1 基本概念

1.1 布爾矩陣

布爾矩陣［7］具有矩陣所有的運(yùn)算性質(zhì)，如與/交操作運(yùn)算。其基本思想為：首先對(duì)事務(wù)數(shù)據(jù)庫D進(jìn)行掃描并轉(zhuǎn)換成布爾矩陣形式，即為Dmn=(dij)mn，其中：

事務(wù)數(shù)據(jù)庫D中的項(xiàng)和事務(wù)分別用行向量和列向量表示，即行向量表示成項(xiàng)，列向量表示事務(wù)。如果第j個(gè)事務(wù)中有第i個(gè)項(xiàng)，則矩陣對(duì)應(yīng)第i行和第j列的數(shù)值為1，否則數(shù)值為0。

1.2 水平和垂直數(shù)據(jù)表示

經(jīng)典的Apriori算法和FP-Growth算法都是采用水平數(shù)據(jù)表示方法，其中事務(wù)由事務(wù)標(biāo)識(shí)符［8］（TID）和項(xiàng)目［9］（Item）兩部分組成。每個(gè)事務(wù)交易僅有唯一一個(gè)TID，而一個(gè)TID對(duì)應(yīng)一個(gè)項(xiàng)集（Itemsets）由一個(gè)項(xiàng)目或者多個(gè)項(xiàng)目組成。水平數(shù)據(jù)表示如表1所示。

Eclat算法［5-6］就是采用垂直數(shù)據(jù)表示方法，該方法是由事務(wù)數(shù)據(jù)庫中的Item和事務(wù)交易中每個(gè)項(xiàng)目按唯一的TID的數(shù)字集合表示記為Tidset組成。垂直數(shù)據(jù)表示如表2所示。

1.3 支持度計(jì)數(shù)（sup_count）

關(guān)聯(lián)規(guī)則挖掘頻繁項(xiàng)集過程中，計(jì)算每個(gè)項(xiàng)的sup_count是必不可少的，但是，計(jì)算sup_count有兩種方法［10-11］：一種是計(jì)數(shù)法，該方法應(yīng)用水平數(shù)據(jù)表示的算法中，如Apriori算法。而一種是交集操作法，該方法由于垂直數(shù)據(jù)表示的算法中，如Eclat算法。即支持度閾值support（sup）如公式（2）所示，而“交操作”運(yùn)算sup_count如公式（3）所示。

其中，X和Y是Item，T(X)和T(Y)是對(duì)應(yīng)項(xiàng)的Tidset。

1.4 實(shí)例應(yīng)用

某事務(wù)數(shù)據(jù)庫中有10個(gè)事務(wù)，D={T1,T2,…,T10}，對(duì)應(yīng)的項(xiàng)目集I={I1,I2,I3,I4,I5}，如表1所示。假設(shè)最小支持度min_sup=30%，則最小支持度計(jì)數(shù)值min_sup_count=min_sup×|D|=30%×10=3。

2 CBM_Apriori算法

2.1 CBM_Apriori算法基本思想

首先掃描事務(wù)數(shù)據(jù)庫D，構(gòu)造成布爾矩陣Dmn，且每列的權(quán)值都為1，然后建立AE權(quán)值數(shù)組來存放每列的權(quán)值，即AE[k]。然后采k-medoids聚類算法，將布爾矩陣中含有相同項(xiàng)目的事務(wù)數(shù)進(jìn)行聚類，則該列的權(quán)值數(shù)加1，即權(quán)值含有相同項(xiàng)目的事務(wù)數(shù)，從而壓縮了矩陣，獲得新的聚類布爾矩陣Dmn。

掃描聚類布爾矩陣，并且計(jì)算所有項(xiàng)目的支持度計(jì)數(shù)（sup_count），將每行矩陣中列向量數(shù)值與對(duì)應(yīng)的AE[k]數(shù)組的數(shù)值進(jìn)行相乘，再相加得到每行事務(wù)的sup_count。即項(xiàng)目Ii的支持度計(jì)數(shù)公式為：

如果事務(wù)的sup_count小于最小支持度計(jì)數(shù)值（min_sup_count），則該項(xiàng)無法生成頻繁2-項(xiàng)集，即刪除該項(xiàng)目對(duì)應(yīng)的行向量，得到頻繁1-項(xiàng)集矩陣L1。

對(duì)頻繁1-項(xiàng)集矩陣L1各行按位采用與操作運(yùn)算，得到候選1-項(xiàng)集矩陣C1。然后將候選1-項(xiàng)集矩陣C1采用（2）中的公式，獲得各行的sup_count，如果sup_count大于或者等于min_sup_count，則存儲(chǔ)該行向量，否則刪除該行向量，即為頻繁2-項(xiàng)集矩陣L2。

分別對(duì)頻繁2-項(xiàng)集矩陣中的各列求和，再將各列之和與對(duì)應(yīng)權(quán)值A(chǔ)E[k]相乘，獲得列向量數(shù)值column（Ti）與 min_sup_count進(jìn)行比較，如果大于或者等于min_sup_count，則保留該列向量，否則刪除該列向量。即列向量數(shù)值公式為：

通過列向量數(shù)值公式對(duì)頻繁2-項(xiàng)集矩陣L2進(jìn)行了壓縮，即為壓縮頻繁2-項(xiàng)集矩陣。

表1 水平數(shù)據(jù)表示

表2 垂直數(shù)據(jù)表示

對(duì)壓縮頻繁2-項(xiàng)集矩陣各行按位采用與操作運(yùn)算，重復(fù)進(jìn)行CBM_Apriori算法的基本思想步驟（3）和（4），生成各頻繁K-項(xiàng)集矩陣Lk，即K大于等于3。直到矩陣行數(shù)少于或者等于1行時(shí)，則算法結(jié)束，即所有的頻繁項(xiàng)集為L=L1+L2+…+Lk。

2.2 CBM_Apriori算法描述如下：

CBM_Apriori算法的代碼如下：

2.3 CBM_Apriori算法的實(shí)例應(yīng)用

事務(wù)數(shù)據(jù)庫就是表1。該算法解決步驟如下：

布爾矩陣Dmn進(jìn)行k-medoids聚類算法生成聚類布爾矩陣D如表3所示。

表3 聚類后的布爾矩陣D

因?yàn)槭聞?wù)T1和T10含有相同的項(xiàng)目，則第1列權(quán)值為2，其余的權(quán)值均為1，I1={100110111}，AE={2，1，1，1，1，1，1，1，1}，sup_count（I1）=1×2+0×1+0×1+1×1+1×1+0×1+1×1+1×1+1×1=7，項(xiàng)目{I1}的sup_count大于或者等于min_sup_count，同理，得到頻繁1-項(xiàng)集L1={I1：7，I2：6，I3：7，I4：3，I5：4}。

對(duì)頻繁1-項(xiàng)集L1，對(duì)各行按位采用與操作運(yùn)算，得到候選1-項(xiàng)集C1，如表4所示。

表4 候選1-項(xiàng)集C1

每行矩陣的列向量的數(shù)值乘以對(duì)應(yīng)的權(quán)值A(chǔ)E[k]的數(shù)值，如I1ΛI(xiàn)2=000110011，AE={2，1，1，1，1，1，1，1，1}，sup_count{I1ΛI(xiàn)2}=0×2+0×1+0×1+1×1+1×1+0×1+0×1+1×1+1×1=4，根據(jù)CBM_Apriori算法的基本思想步驟3），項(xiàng)集{I1ΛI(xiàn)2}的sup_count_row大于或者等于min_sup_count，同理，保留各行向量，即得到頻繁2-項(xiàng)集L2={I1ΛI(xiàn)2：4，I1ΛI(xiàn)3：5，I1ΛI(xiàn)5：3，I2ΛI(xiàn)3：5，I3ΛI(xiàn)5：4}，如表5所示。

表5 頻繁2-項(xiàng)集L2

根據(jù)CBM_Apriori算法的基本思想步驟（4），如第一列向量為{01101}，column（T1）=（0+1+1+0+1）×2=6，刪除第2、3、5、6、7列以及對(duì)應(yīng)的權(quán)值2、3、5、6、7列，獲得壓縮頻繁2-項(xiàng)集矩陣，如表6所示。

對(duì)壓縮頻繁2-項(xiàng)集矩陣，重復(fù)進(jìn)行CBM_Apriori算法的基本思想步驟（5），獲得頻繁3-項(xiàng)集矩陣L3={I1ΛI(xiàn)2ΛI(xiàn)3：3，I1ΛI(xiàn)3ΛI(xiàn)5：3}，壓縮頻繁3-項(xiàng)集矩陣，頻繁4-項(xiàng)集矩陣L4，如表7所示。

表7 頻繁3-項(xiàng)集L3、壓縮頻繁3-項(xiàng)集矩陣、頻繁4-項(xiàng)集L4

（6）直到生成的矩陣的行向量小于或者等于1，結(jié)束該算法過程。最后輸出矩陣中所有的行向量，即為所有的頻繁項(xiàng)集L=L1+L2+L3={I1,I2,I3,I4,I5，I1ΛI(xiàn)2，I1ΛI(xiàn)3，I1ΛI(xiàn)5，I2ΛI(xiàn)3，I3ΛI(xiàn)5，I1ΛI(xiàn)2ΛI(xiàn)3，I1ΛI(xiàn)3ΛI(xiàn)5}。

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

為了減少候選項(xiàng)集的生成和存儲(chǔ)空間等問題，對(duì)CBM_Apriori算法進(jìn)行改進(jìn)。本文提出了一種基于聚類布爾矩陣的Eclat算法—CBM_Eclat算法。

3.1 CBM_Eclat算法基本思想

（1）首先掃描事務(wù)數(shù)據(jù)庫，構(gòu)造布爾矩陣D；然后采用k-medoids聚類算法，將布爾矩陣中含有相同項(xiàng)目的事務(wù)數(shù)進(jìn)行聚類，從而壓縮了布爾矩陣，產(chǎn)生了新的布爾矩陣D1和權(quán)值A(chǔ)E[k]；再對(duì)新的布爾矩陣D1增加 Tidset，即為T(N)（N=1，2，…，m）。最終得到標(biāo)記聚類布爾矩陣D2。

（2）對(duì)標(biāo)記聚類布爾矩陣D2進(jìn)行掃描，尋找該矩陣中每個(gè)項(xiàng)目1所對(duì)應(yīng)的T(N)和AE[k]并同時(shí)保存；然后計(jì)算T(N[Ii])對(duì)應(yīng)的權(quán)值A(chǔ)E[k]進(jìn)行相加為該項(xiàng)的sup_count，如果sup_count大于或者等于min_sup_count，則存儲(chǔ)T(N)以及所對(duì)應(yīng)的項(xiàng)和權(quán)值A(chǔ)E[k]，否則刪除，即獲得頻繁1-項(xiàng)集L1。

（3）頻繁1-項(xiàng)集中每項(xiàng)所對(duì)應(yīng)的T(N)兩兩采用交操作運(yùn)算，得到候選項(xiàng)集C1以及對(duì)應(yīng)的T(N)權(quán)值A(chǔ)E[k]；然后重復(fù)步驟（2），即獲得頻繁2-項(xiàng)集

L2。

（4）重復(fù)步驟（3），直到T(N)不能兩兩采用交操作運(yùn)算，則算法結(jié)束，即獲得所有的頻繁項(xiàng)集L。

3.2 CBM_Eclat算法描述

R語言編寫CBM_Eclat算法的主要代碼如下：

輸入：Tidset數(shù)據(jù)庫D，最小支持度計(jì)數(shù)值min_sup_count；

輸出：所有的頻繁項(xiàng)集Lk；

（1）對(duì)事務(wù)數(shù)據(jù)庫進(jìn)行聚類

①D＜-read.csv（“data.csv”，header=TRUE）

#導(dǎo)入數(shù)據(jù)集；

②set.seed（0）

#設(shè)置隨機(jī)種子；

③pamx＜-pam（Data，k）

#構(gòu)造k-medoid聚類模型；

④AE＜-pamx$clusinfo

#獲得聚類后權(quán)值A(chǔ)E；

⑤D＜-pamx$medoids

#獲得聚類后布爾矩陣D；

（2）生成頻繁1-項(xiàng)集L1

①掃描標(biāo)記聚類布爾矩陣D；

②Eclat（D，AE[k]）

③ for each項(xiàng)集i∈I{

④ for each標(biāo)記符T(N)∈D

⑤i.sup_count=AE［1］+...+AE［n］，

其中，n=1，2，...，N；

#計(jì)算項(xiàng)集支持度計(jì)數(shù)；

⑥ }

⑦L1=（i∈項(xiàng)集 I|i.sup_count＞=min_sup_count）

#大于或者等于支持度計(jì)數(shù)的候選項(xiàng)集為頻繁項(xiàng)集L1；

（3）生成候選項(xiàng)集Ck和頻繁項(xiàng)集Lk

3.3 CBM_Eclat算法的實(shí)例應(yīng)用

事務(wù)數(shù)據(jù)庫如表1所示。該算法解決步驟如下：

（1）掃描布爾矩陣D，然后對(duì)布爾矩陣D進(jìn)行k-medoids聚類算法生成聚類布爾矩陣 D1和AE[k]，對(duì)聚類布爾矩陣D1使用標(biāo)記T(N)，于是由AE[k]、標(biāo)記T(N)和聚類布爾矩陣D1構(gòu)成標(biāo)記聚類布爾矩陣D2，如表8所示。

表8 標(biāo)記聚類布爾矩陣D2

（2）根據(jù)CBM_Eclat算法，得出Tidset垂直數(shù)據(jù)庫，如表9所示。

計(jì)算每個(gè)項(xiàng)的T(N)個(gè)數(shù)為sup_count，如T(N[I1])={1，4，5，7，8，9}，則sup_count（I1）=2+1+1+1+1+1=7，保存大于或者等于min_sup_count的項(xiàng)以及對(duì)應(yīng)的T(N)。故得到頻繁1-項(xiàng)集L1={I1:7,I2:6,I3:7,I4:3,I5:4}。

表9 Tidset垂直數(shù)據(jù)庫

（3）對(duì)Tidset垂直數(shù)據(jù)庫兩兩采用交操作運(yùn)算以及對(duì)應(yīng)AE[k]，獲得候選項(xiàng)集C1，如圖1所示。

與步驟（2）計(jì)算sup_count相同，保存大于或者等于min_sup_count的項(xiàng)以及對(duì)應(yīng)的T(N)，刪除{I1I4,I2I4,I2I5,I3I4,I4I5}。故得到頻繁2-項(xiàng)集L2={I1I2:4,I1I3:5,I1I5:3,I2I3:5,I3I5:4}和頻繁3-項(xiàng)集L3={I1I2I3:3,I1I2I3:3}。

（4）最終輸出所有的頻繁項(xiàng)集L=L1+L2+L3={I1,I2,I3,I4,I5,I1I2,I1I3,I2I3,I3I5,I1I2I3,I1I3I5}。

4 算法性能分析與實(shí)驗(yàn)

通過實(shí)驗(yàn)分析Apriori算法、Eclat算法、CBM_Apriori算法和CBM_Eclat算法的性能，它們都在相同的環(huán)境下進(jìn)行比較。實(shí)驗(yàn)環(huán)境為：CPU為i7-4790、3.60GHz、內(nèi)存4GB和Windows7系統(tǒng)，使用R語言編輯的程序。首先從R語言中自帶的Groceries數(shù)據(jù)庫中提取樣本數(shù)據(jù)分別為1000、2000、3000、4000和5000；然后對(duì)Groceries數(shù)據(jù)庫進(jìn)行處理并使用K-medoids聚類算法，獲得不同的樣本布爾矩陣；最后使用CBM_Apriori算法和CBM_Eclat算法運(yùn)行樣本布爾矩陣，找到所有滿足條件的頻繁項(xiàng)集。當(dāng)最小支持度相同時(shí)，則通過上述四種算法運(yùn)行時(shí)間與樣本數(shù)據(jù)之間的變化關(guān)系，如圖2所示。當(dāng)最小支持度不同時(shí)，則比較上述四種算法的性能，如圖3所示。

圖1 候選項(xiàng)集和頻繁項(xiàng)集

圖2 四種算法運(yùn)行時(shí)間與樣本數(shù)據(jù)的變化關(guān)系

如圖2所示，四條曲線變化趨勢明顯看出：經(jīng)典Apriori算法隨著樣本數(shù)據(jù)的增加，其運(yùn)行時(shí)間在快速的增加；Eclat算法、CBM_Apriori算法和CBM_Eclat算法隨著樣本數(shù)據(jù)的增加，其運(yùn)行時(shí)間也在緩慢的增加；CBM_Apriori算法運(yùn)行的速度也比經(jīng)典的Eclat算法要快；本文改進(jìn)的CBM_Eclat算法運(yùn)行的速度比其他三個(gè)算法都要快，其中隨著樣本數(shù)的增加，時(shí)間變化更明顯。

圖3 最小支持度不同時(shí)四種算法的性能比較

如圖3所示，當(dāng)最小支持度越來越小時(shí)，經(jīng)典Apriori算法要比其他三個(gè)算法運(yùn)行的時(shí)間明顯要多；而當(dāng)最小支持度越來越大時(shí)，四個(gè)算法運(yùn)行的時(shí)間也越來越少且基本上相等。

5 結(jié)論

隨著數(shù)據(jù)挖掘技術(shù)的廣泛應(yīng)用，關(guān)聯(lián)規(guī)則挖掘作為數(shù)據(jù)挖掘領(lǐng)域的主要研究課題之一，為了提高關(guān)聯(lián)規(guī)則挖掘算法的運(yùn)算效率，針對(duì)CBM_Apriori算法產(chǎn)生大量的候選項(xiàng)集和占用大量的存儲(chǔ)空間等缺點(diǎn)進(jìn)行改進(jìn)。于是，提出了一種基于聚類布爾矩陣的Eclat算法—CBM_Eclat算法。該算法也只需要掃描事務(wù)數(shù)據(jù)庫一次且采用邏輯“交”操作運(yùn)算，減少候選項(xiàng)集的生成和存儲(chǔ)空間，所以提高了該算法的執(zhí)行效率。

［1］Agrawal R，Imielinaki T，Swami A.Mining association rules between sets of items in large databases［C］.InProc.1993ACM—SIGMOD Int.Conf.Management of Date，Washington，D.C.，1993：207-216.

［2］Jiawei Han，Jian Pei，Yiwen Yin.Mining frequent patterns without candidate generation［C］.In Proc.2000 ACM—SIGMOD Int.Conf.Management of Data，Dallas，Texas，USA，2000：1-12.

［3］Vu L，Alaghband G.A fast algorithm combining FP-tree and TID-list for frequent pattern mining［C］.In Proceedings of IEEE Conference on Information and Knowledge Engineering，2011：472-477.

［4］付沙，宋丹.基于矩陣的Apriori改進(jìn)算法研究［J］.微電子學(xué)與計(jì)算機(jī)，2012，5（5）：156-161.

［5］Mohammed J Zaki.Scalable algorithms for association mining［J］.Knowledge and Data Engineering，2000，12（3）：372-390.

［6］Zaki M.J.Fast vertical mining using diffsets［R］.Technical Report 0-1，Rensselaer Polytechnic Institute，Troy，New York，2001.

［7］方煒煒，楊炳儒，宋威，等.基于布爾矩陣的關(guān)聯(lián)規(guī)則算法研究［J］.計(jì)算機(jī)應(yīng)用，2008，25（7）：1964-1967.

［8］李敏，李春平.頻繁模式挖掘算法分析和比較［J］.計(jì)算機(jī)應(yīng)用，2005，25（1）：166-171.

［9］宋長新，馬克.改進(jìn)的Eclat數(shù)據(jù)挖掘算法的研究［J］.微計(jì)算機(jī)信息，2008，24（8）：92-94.

［10］景永霞，王治和，杜躍.一種新的Apriori改進(jìn)算法［J］，長春理工大學(xué)，2007，30（2）：67-69.

［11］談恒貴，王文杰，李克雙.頻繁項(xiàng)集挖掘算法綜述［J］，計(jì)算機(jī)仿真，2005，22（11）：1-4.

The Research of Apriori Algorithm Based on Cluster Boolean Matrix

TIAN Lei，CUI Guangcai，HE Xu，CHEN Jianxin
（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

For the inadequacy of Apriori algorithm of cluster Boolean matrix —CBM_Apriori algorithm，this paper presents a methods of Eclat algorithm based on cluster Boolean matrix —CBM_Eclat algorithm. To begin with，using K-medoids algorithm deal with Boolean matrix to obtain the weight and new Boolean matrix. Then，new Boolean matrix is transformed into the Tidset that use logical “and” operating，so the cluster Boolean matrix storage and candidate itemsets are reduced effectively. Thus，the efficiency of the algorithm is improved. Meanwhile，the application of example and result of algorithm performance both can prove the feasibility and effectiveness of the CBM_Eclat algorithm.

CBM_Apriori algorithm；CBM_Eclat algorithm；Boolean matrix；K-medoids algorithm；Tidset

TP311

A

1672-9870（2017）05-0109-06

2017-09-18

田磊（1989-），男，碩士研究生，E-mail：tl091138@163.com

崔廣才（1964-），男，博士，教授，E-mail：gccui@cust.edu.cn