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

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

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

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

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

針對聚類布爾矩陣的Apriori算法—CBM_Apriori算法的不足之處，提出了一種基于聚類布爾矩陣的Eclat算法—CBM_Eclat算法。該算法首先對布爾矩陣使用K-medoids算法，獲得權(quán)值和聚類后的布爾矩陣；然后將聚類后的布爾矩陣轉(zhuǎn)換成Tidset，并采用邏輯“交操作”運算，進而有效地減少了聚類布爾矩陣存儲和候選項集的生成，提高了該算法的執(zhí)行效率。通過實例應(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］挖掘頻繁項集，但是這兩種算法都有著自己的缺陷，Apriori算法的缺陷是反復(fù)掃描事務(wù)數(shù)據(jù)庫和產(chǎn)生大量的候選項集，而FP-Growth算法的缺陷是占用大量的內(nèi)存空間。于是，研究者們對它們的缺陷進行了大量的研究，提出了許多改進的方法，從而提高了算法的運行效率以及減少了存儲空間。

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

1 基本概念

1.1 布爾矩陣

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

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

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

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

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

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

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

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

1.4 實例應(yīng)用

某事務(wù)數(shù)據(jù)庫中有10個事務(wù)，D={T1,T2,…,T10}，對應(yīng)的項目集I={I1,I2,I3,I4,I5}，如表1所示。假設(shè)最小支持度min_sup=30%，則最小支持度計數(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聚類算法，將布爾矩陣中含有相同項目的事務(wù)數(shù)進行聚類，則該列的權(quán)值數(shù)加1，即權(quán)值含有相同項目的事務(wù)數(shù)，從而壓縮了矩陣，獲得新的聚類布爾矩陣Dmn。

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

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

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

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

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

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

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

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

2.2 CBM_Apriori算法描述如下：

CBM_Apriori算法的代碼如下：

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

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

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

表3 聚類后的布爾矩陣D

因為事務(wù)T1和T10含有相同的項目，則第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，項目{I1}的sup_count大于或者等于min_sup_count，同理，得到頻繁1-項集L1={I1：7，I2：6，I3：7，I4：3，I5：4}。

對頻繁1-項集L1，對各行按位采用與操作運算，得到候選1-項集C1，如表4所示。

表4 候選1-項集C1

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

表5 頻繁2-項集L2

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

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

表7 頻繁3-項集L3、壓縮頻繁3-項集矩陣、頻繁4-項集L4

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

3 CBM_Apriori算法的改進

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

3.1 CBM_Eclat算法基本思想

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

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

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

L2。

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

3.2 CBM_Eclat算法描述

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

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

輸出：所有的頻繁項集Lk；

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

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

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

②set.seed（0）

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

③pamx＜-pam（Data，k）

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

④AE＜-pamx$clusinfo

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

⑤D＜-pamx$medoids

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

（2）生成頻繁1-項集L1

①掃描標記聚類布爾矩陣D；

②Eclat（D，AE[k]）

③ for each項集i∈I{

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

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

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

#計算項集支持度計數(shù)；

⑥ }

⑦L1=（i∈項集 I|i.sup_count＞=min_sup_count）

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

（3）生成候選項集Ck和頻繁項集Lk

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

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

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

表8 標記聚類布爾矩陣D2

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

計算每個項的T(N)個數(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的項以及對應(yīng)的T(N)。故得到頻繁1-項集L1={I1:7,I2:6,I3:7,I4:3,I5:4}。

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

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

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

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

4 算法性能分析與實驗

通過實驗分析Apriori算法、Eclat算法、CBM_Apriori算法和CBM_Eclat算法的性能，它們都在相同的環(huá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；然后對Groceries數(shù)據(jù)庫進行處理并使用K-medoids聚類算法，獲得不同的樣本布爾矩陣；最后使用CBM_Apriori算法和CBM_Eclat算法運行樣本布爾矩陣，找到所有滿足條件的頻繁項集。當最小支持度相同時，則通過上述四種算法運行時間與樣本數(shù)據(jù)之間的變化關(guān)系，如圖2所示。當最小支持度不同時，則比較上述四種算法的性能，如圖3所示。

圖1 候選項集和頻繁項集

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

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

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

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

5 結(jié)論

隨著數(shù)據(jù)挖掘技術(shù)的廣泛應(yīng)用，關(guān)聯(lián)規(guī)則挖掘作為數(shù)據(jù)挖掘領(lǐng)域的主要研究課題之一，為了提高關(guān)聯(lián)規(guī)則挖掘算法的運算效率，針對CBM_Apriori算法產(chǎn)生大量的候選項集和占用大量的存儲空間等缺點進行改進。于是，提出了一種基于聚類布爾矩陣的Eclat算法—CBM_Eclat算法。該算法也只需要掃描事務(wù)數(shù)據(jù)庫一次且采用邏輯“交”操作運算，減少候選項集的生成和存儲空間，所以提高了該算法的執(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］.微電子學(xué)與計算機，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］.計算機應(yīng)用，2008，25（7）：1964-1967.

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

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

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

［11］談恒貴，王文杰，李克雙.頻繁項集挖掘算法綜述［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