黃再祥，周忠眉，何田中

(漳州師范學(xué)院計(jì)算機(jī)科學(xué)與工程系，福建 漳州 363000)

1 引言

對(duì)于大型數(shù)據(jù)集，構(gòu)建準(zhǔn)確而高效的分類器是數(shù)據(jù)挖掘領(lǐng)域的一項(xiàng)主要任務(wù)。1998年，Liu B等[1]提出了將關(guān)聯(lián)規(guī)則和分類相結(jié)合的關(guān)聯(lián)分類方法。由于關(guān)聯(lián)分類具有分類準(zhǔn)確率高和易理解等特點(diǎn)，一直是分類領(lǐng)域的研究熱點(diǎn)之一[2～7]。

關(guān)聯(lián)分類算法主要包含類關(guān)聯(lián)規(guī)則產(chǎn)生和分類兩個(gè)階段。類關(guān)聯(lián)規(guī)則是后件為類別的特殊關(guān)聯(lián)規(guī)則。通常使用改進(jìn)的關(guān)聯(lián)規(guī)則挖掘算法來產(chǎn)生類關(guān)聯(lián)規(guī)則，如CBA[1]使用類Apriori[8]算法，CMAR[9]使用FPgrowth[10]算法產(chǎn)生類關(guān)聯(lián)規(guī)則。由于產(chǎn)生的類關(guān)聯(lián)規(guī)則數(shù)量眾多，大多數(shù)關(guān)聯(lián)分類算法采用相關(guān)的剪枝技術(shù)，從中選出一小部分高質(zhì)量的規(guī)則來構(gòu)建分類器。

在分類新實(shí)例時(shí)，與待分類實(shí)例匹配的多個(gè)規(guī)則的類別經(jīng)常出現(xiàn)不一致的情況。目前，大多數(shù)關(guān)聯(lián)分類算法解決這種規(guī)則沖突問題主要有三種策略：(1)使用優(yōu)先級(jí)最高的單個(gè)規(guī)則，如CBA等。(2)使用優(yōu)先級(jí)最高的k個(gè)規(guī)則，如CPAR[11]等。(3)使用所有匹配的規(guī)則，如CMAR等。對(duì)于前兩種方法都需要首先確定規(guī)則的優(yōu)先級(jí)，而不同的優(yōu)先級(jí)排序算法對(duì)分類的準(zhǔn)確率有較大影響[12]。對(duì)于后兩種方法都需要對(duì)多個(gè)規(guī)則按類別分組并計(jì)算一組規(guī)則的強(qiáng)度，選擇強(qiáng)度最大的組的類別作為待分類實(shí)例的類別。不同的規(guī)則強(qiáng)度計(jì)算方法對(duì)分類的準(zhǔn)確率也有較大影響。

然而，在分類某些實(shí)例時(shí)，上述處理規(guī)則沖突的策略仍然很難將這些實(shí)例正確分類。文獻(xiàn)[13，14]等提出了一種利用神經(jīng)網(wǎng)絡(luò)解決規(guī)則沖突的方法，這種方法需要額外訓(xùn)練一個(gè)神經(jīng)網(wǎng)絡(luò)模型。Lindgren T等[15]提出了兩次學(xué)習(xí)方法，該方法在分類實(shí)例遇到規(guī)則沖突時(shí)，從沖突規(guī)則覆蓋的實(shí)例中進(jìn)行第二次學(xué)習(xí)得到一組新規(guī)則來分類該實(shí)例。但是，這種方法的缺點(diǎn)是分類每一個(gè)實(shí)例都要進(jìn)行一次學(xué)習(xí)，對(duì)大數(shù)據(jù)集來說時(shí)間開銷非常大。

本文提出了基于改進(jìn)的關(guān)聯(lián)分類兩次學(xué)習(xí)方法，創(chuàng)新點(diǎn)如下：

(1)提出改進(jìn)的關(guān)聯(lián)分類算法。挖掘頻繁且互關(guān)聯(lián)的項(xiàng)集用來產(chǎn)生規(guī)則；利用信息熵和正相關(guān)等進(jìn)行剪枝；在規(guī)則排序時(shí)考慮了項(xiàng)集和類之間的關(guān)聯(lián)程度，這樣能更好地定義規(guī)則之間的優(yōu)先級(jí)。

(2)提出新的兩次學(xué)習(xí)框架。利用改進(jìn)的關(guān)聯(lián)分類算法在訓(xùn)練集上學(xué)習(xí)產(chǎn)生第一級(jí)規(guī)則；然后應(yīng)用第一級(jí)規(guī)則分離出訓(xùn)練集中規(guī)則沖突的實(shí)例；最后，在沖突實(shí)例上應(yīng)用改進(jìn)的關(guān)聯(lián)分類算法進(jìn)行第二次學(xué)習(xí)得到第二級(jí)規(guī)則。

2 關(guān)聯(lián)分類的基本概念

關(guān)聯(lián)分類方法是一種使用一組關(guān)聯(lián)規(guī)則來分類事務(wù)的技術(shù)。它挖掘形如X?Yi的類關(guān)聯(lián)規(guī)則，其中X是項(xiàng)(或?qū)傩?值對(duì))的集合，而Yi是類標(biāo)號(hào)。假設(shè)有兩個(gè)規(guī)則R1：X1?Y1和R2：X2?Y2，如果X1?X2，則稱R1是R2的泛化規(guī)則，R2是R1的特化規(guī)則。

在關(guān)聯(lián)分類中，設(shè)訓(xùn)練集T={t1,t2,…,tn}有m個(gè)不同的特征屬性A1，A2，…,Am和一個(gè)類屬性Y。如果實(shí)例ti?X，稱之為實(shí)例ti匹配規(guī)則X?Yi。假設(shè)有兩個(gè)規(guī)則R1：X1?Y1和R2：X2?Y2，如果ti?X1且ti?X2，Y1≠Y2，則稱ti為沖突實(shí)例。

支持度和置信度是關(guān)聯(lián)規(guī)則的兩個(gè)重要度量。支持度(s)確定項(xiàng)集X可以用于給定數(shù)據(jù)集的頻繁程度，而置信度(c)確定Yi在包含X的事務(wù)中出現(xiàn)的頻繁程度。這兩種度量的形式定義如下:

(1)

(2)

如果對(duì)于規(guī)則R：X?Yi，有c(X?Yi)>s(Yi)，這樣的規(guī)則稱之為正相關(guān)規(guī)則。

Omiecinski E R[16]提出了All-confidence的概念。 項(xiàng)集X=(a1，…,an)的All-confidence定義如下：

(3)

All-confidence代表從一個(gè)項(xiàng)集中抽出的所有關(guān)聯(lián)規(guī)則中的最小置信度。All-confidence是衡量項(xiàng)集中項(xiàng)之間的關(guān)聯(lián)程度的一種很好的度量。如果項(xiàng)集的All-confidence超過用戶指定的閾值，則稱該項(xiàng)集為互關(guān)聯(lián)項(xiàng)集。All-confidence也可以用來定義規(guī)則中項(xiàng)集與類的關(guān)聯(lián)程度，定義如下：

allconf(X?Yi)=s(X∪Yi)/max(s(X),s(Yi))

(4)

信息熵[17]是信息量的一種度量。項(xiàng)集X的信息熵E(X)定義如下：

(5)

其中,k是類標(biāo)的個(gè)數(shù)，p(Yi|X)是匹配X的實(shí)例屬于Yi的概率。項(xiàng)集信息熵越大，分類的信息量越小。因此，可以提前刪除信息熵接近1的項(xiàng)，從而提高挖掘類關(guān)聯(lián)規(guī)則的效率。

3 改進(jìn)的關(guān)聯(lián)分類算法

改進(jìn)的關(guān)聯(lián)分類算法有以下四個(gè)特點(diǎn)：

(1)挖掘頻繁且互關(guān)聯(lián)的項(xiàng)集。項(xiàng)集中項(xiàng)之間關(guān)聯(lián)越緊密，越具有較好的分類能力。

(2)刪除信息熵接近1的項(xiàng)，從而提高挖掘效率。項(xiàng)的信息熵越大，分類的信息量越小。

(3)排序。在規(guī)則排序時(shí)不僅考慮了規(guī)則的置信度和支持度，還考慮了項(xiàng)集和類之間的關(guān)聯(lián)程度，這樣能更好地定義規(guī)則之間的優(yōu)先級(jí)。

(4)通過類分布的交運(yùn)算計(jì)算支持度[18]，避免多次掃描數(shù)據(jù)集。在第一趟掃描過程中，記錄項(xiàng)的類分布情況，結(jié)構(gòu)如〈X,{Yi,{行號(hào)}}〉，其中X是項(xiàng)，Yi是類別。在隨后的迭代過程中通過兩個(gè)項(xiàng)集的類分布交運(yùn)算來計(jì)算項(xiàng)集的支持度和置信度。例如，假設(shè)某數(shù)據(jù)集有兩個(gè)類Y1和Y2，有兩個(gè)項(xiàng)集的類分布如下：〈X1,{(Y1,{1,2,3}),(Y2,{6,7,8,9})}〉，〈X2,{(Y1,{2,3,4}),(Y2,{5,6,7,8,10})}〉。通過求交運(yùn)算可得〈X1∪X2,{(Y1,{2,3}),(Y2,{6,7,8})}〉。從中可抽取規(guī)則X1∪X2?Y2，支持度為3，置信度為60%。

該算法的具體過程如下：

AlgorithmICAR(T,minsup,minAllconf,maxEntropy,R)

輸入：訓(xùn)練集T，支持度閾值minsup，All-confidence閾值minAllconf，信息熵閾值maxEntropy；

輸出：類關(guān)聯(lián)規(guī)則集R。

1.init-pass(T,minsup,maxEntropy,L1,R);

2:for (k=2;Lk-1≠?;k++) do

3:Ck←candidateGen(Lk-1);

4: for allXinCkdo

5: computeallconf(X);

6: ifs(X)≥minsupandallconf(X)≥minAllconfthen

7: pushXintoLk;

8: 抽取以X為前件的置信度最大的規(guī)則Ri:X→Yi;

9: ifconf(Ri)>s(Yi)

10: 在R中找出Ri的所有泛化規(guī)則；

11: if 泛化規(guī)則的置信度都小于Ri的置信度

12: pushRiintoR;

13: end if

14: end if

15: end if

16:end for

17:Sort(R);

18:DatabaseCoverage(T,R, 1);

19:returnR;

在對(duì)訓(xùn)練集第一趟掃描中(行1)，記錄每個(gè)項(xiàng)出現(xiàn)的行號(hào)，刪除信息熵超過maxEntropy的項(xiàng)，將頻繁的項(xiàng)加入L1中，并抽取相應(yīng)的規(guī)則放入R中。

在接下來的迭代中，類似Apriori算法，將Lk-1中的兩個(gè)項(xiàng)集進(jìn)行連接運(yùn)算得到候選項(xiàng)集，并通過相連的兩個(gè)項(xiàng)集的類分布的交運(yùn)算計(jì)算候選項(xiàng)集的支持度(行3)。按公式(3)計(jì)算每個(gè)候選項(xiàng)集的All-confidence，將支持度和All-confidence超出相應(yīng)閾值的項(xiàng)集X加入Lk，并抽取以X為條件的所有規(guī)則中置信度最大的規(guī)則Ri:X→Yi(行5～行8)。利用正相關(guān)性和泛化規(guī)則進(jìn)行剪枝。即該規(guī)則的置信度大于相應(yīng)類的支持度并且規(guī)則的置信度大于其所有泛化規(guī)則的置信度時(shí)才加入規(guī)則集(行9～行12)。候選規(guī)則產(chǎn)生后對(duì)規(guī)則集進(jìn)行排序并利用數(shù)據(jù)庫覆蓋剪枝。規(guī)則按置信度、項(xiàng)集和類的All-confidence、項(xiàng)集的All-confidence、規(guī)則支持度進(jìn)行排序。數(shù)據(jù)庫覆蓋與CMAR算法類似，選取至少能正確分類一個(gè)實(shí)例的規(guī)則，當(dāng)一個(gè)實(shí)例被k個(gè)規(guī)則覆蓋后將其從訓(xùn)練集中刪除。

4 新的兩次學(xué)習(xí)框架

新的兩次學(xué)習(xí)框架主要有以下三個(gè)特點(diǎn)：

(1)利用第一級(jí)規(guī)則將訓(xùn)練集中的所有沖突實(shí)例分離出來。

(2)在沖突實(shí)例上進(jìn)行二次學(xué)習(xí)得到第二級(jí)規(guī)則，與第一級(jí)規(guī)則共同構(gòu)成分類器。

(3)基于兩級(jí)規(guī)則的分類。在對(duì)一個(gè)新實(shí)例分類時(shí)，先從第一級(jí)規(guī)則集中找出與該實(shí)例匹配的優(yōu)先級(jí)最高的兩個(gè)規(guī)則來對(duì)該實(shí)例分類。如果匹配的兩個(gè)規(guī)則預(yù)測(cè)類別不一致，則使用第二級(jí)規(guī)則集中匹配的優(yōu)先級(jí)最高的規(guī)則對(duì)該實(shí)例分類。

基于改進(jìn)的關(guān)聯(lián)分類兩次學(xué)習(xí)具體算法如下：

AlgorithmdoubleLearning(T，minsup,minAllconf,maxEntropy)

輸入：訓(xùn)練集T，支持度閾值minsup，All-confidence閾值minAllconf，熵閾值maxEntropy;

輸出：兩級(jí)規(guī)則集RL1和RL2。

1.ICAR(T,minsup,minAllconf,maxEntropy,RL1);

2.ConflictSet_G(T,RL1,conflictSet);

3.ICAR(conflictSet,minsup,minAllconf,maxEntropy,RL2);

首先在訓(xùn)練集上利用改進(jìn)的關(guān)聯(lián)分類算法ICAR產(chǎn)生第一級(jí)規(guī)則RL1(行1)；然后利用第一級(jí)規(guī)則RL1將訓(xùn)練集中規(guī)則沖突的實(shí)例分離出來(行2)；最后在沖突實(shí)例集上應(yīng)用相同的關(guān)聯(lián)分類算法ICAR進(jìn)行第二次學(xué)習(xí)得到第二級(jí)規(guī)則RL2。

沖突實(shí)例分離算法如下：

AlgorithmConflictSet_G(T,RL1,conflictSet)

輸入：訓(xùn)練集T，第一級(jí)規(guī)則RL1;

輸出：沖突實(shí)例集conflictSet。

1. for(each instancetiinT)

2. for(each ruleRiinRL1)

3. ifRi匹配ti&& (MR[0].conf-Ri.conf)

4. 將Ri加入匹配規(guī)則集MR;

5. end if

6. end for

7. ifMR中規(guī)則類別不一致

8. 將ti加入沖突集conflictSet;

9. end if

10. end for

利用第一級(jí)規(guī)則將沖突實(shí)例分離出來。對(duì)訓(xùn)練集中的每個(gè)實(shí)例從RL1中找出與第一個(gè)匹配規(guī)則置信度相差在Difconf之內(nèi)的所有規(guī)則(行2～行6)，如果這些規(guī)則預(yù)測(cè)的類別不一致則將該實(shí)例加入沖突實(shí)例集(行7～行9)。

5 實(shí)驗(yàn)與分析

采用10-折交叉驗(yàn)證方法，把所有樣本分成10等份，每次將其中的9份作為訓(xùn)練集，剩下的1份作為測(cè)試集，計(jì)算測(cè)試集的分類準(zhǔn)確率，將10次準(zhǔn)確率的平均值作為該數(shù)據(jù)集的準(zhǔn)確率。我們對(duì)UCI機(jī)器學(xué)習(xí)庫中的12個(gè)數(shù)據(jù)集進(jìn)行了測(cè)試。這12個(gè)數(shù)據(jù)集的特征如表1所示。

Table 1 UCI dataset characteristics表1 UCI機(jī)器學(xué)習(xí)庫中的數(shù)據(jù)集特征

首先，我們對(duì)改進(jìn)的關(guān)聯(lián)分類算法(IAC)和基于頻繁的關(guān)聯(lián)分類算法(FAC)的分類性能進(jìn)行了比較。對(duì)于IAC, 我們將支持度、All-confidence、信息熵的閾值分別設(shè)為0.5%、10% 和0.95。對(duì)于FAC, 我們將支持度、All-confidence、信息熵的閾值分別設(shè)為0.5%、0% 和1。也就是說, FAC 近挖掘頻繁項(xiàng)集產(chǎn)生規(guī)則，并且也不刪除信息熵很高的項(xiàng)集。實(shí)驗(yàn)結(jié)果如表2所示。 在12個(gè)數(shù)據(jù)集中的9個(gè)數(shù)據(jù)集上，IAC取得的準(zhǔn)確率比FAC高。此外，IAC得到的規(guī)則數(shù)減少了近一半，運(yùn)行時(shí)間僅為FAC的5%。原因是頻繁且互關(guān)聯(lián)項(xiàng)集比頻繁項(xiàng)集要少得多且這種頻繁互關(guān)聯(lián)項(xiàng)集具有更好的分類能力。

Table 2 Comparison of IAC and FAC表2 改進(jìn)的關(guān)聯(lián)分類與基于頻繁的關(guān)聯(lián)分類的比較

其次，我們對(duì)基于改進(jìn)關(guān)聯(lián)分類的兩次學(xué)習(xí)算法(DLIAC)進(jìn)行了分類性能的實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表3所示。

Table 3 Comparison of DLIAC and IAC表3 基于改進(jìn)關(guān)聯(lián)分類的兩次學(xué)習(xí)算法的分類性能

實(shí)驗(yàn)結(jié)果表明基于改進(jìn)關(guān)聯(lián)分類的兩次學(xué)習(xí)算法比改進(jìn)關(guān)聯(lián)分類算法顯著提高了分類準(zhǔn)確率，其中在Balance、Heart、Lymph、Sonar等數(shù)據(jù)集上提高了2%以上。實(shí)驗(yàn)結(jié)果也顯示了在分類階段一級(jí)規(guī)則沖突的實(shí)例占總的測(cè)試集的平均百分比為9%，而二級(jí)規(guī)則沖突的實(shí)例百分比顯著下降到1.5%。由于兩次學(xué)習(xí)需要從沖突實(shí)例中進(jìn)行第二次學(xué)習(xí)，因此訓(xùn)練時(shí)間要稍微長(zhǎng)一些。從表3中可以看出平均多花費(fèi)大約10%的時(shí)間。

表4進(jìn)一步比較了兩次學(xué)習(xí)和一次學(xué)習(xí)在分類沖突實(shí)例時(shí)的準(zhǔn)確率。沖突實(shí)例是指使用第一級(jí)規(guī)則時(shí)匹配的優(yōu)先級(jí)最高的兩個(gè)規(guī)則類別不一致的測(cè)試實(shí)例。一次學(xué)習(xí)采用匹配的優(yōu)先級(jí)最高的規(guī)則分類沖突實(shí)例，而兩次學(xué)習(xí)采用第二級(jí)規(guī)則對(duì)沖突實(shí)例分類。表3中第3列表示沖突實(shí)例在測(cè)試集中占的比例，第4列顯示一次學(xué)習(xí)對(duì)沖突實(shí)例分類的準(zhǔn)確率，第5列顯示了兩次學(xué)習(xí)分類沖突實(shí)例的準(zhǔn)確率。結(jié)果顯示，兩次學(xué)習(xí)在分類沖突實(shí)例時(shí)顯著地提高了分類準(zhǔn)確率。

Table 4 Comparison of accuracy on conflict instances表4 分類沖突實(shí)例準(zhǔn)確率對(duì)比

6 結(jié)束語

針對(duì)關(guān)聯(lián)分類方法中規(guī)則沖突問題，本文提出了一種基于改進(jìn)的關(guān)聯(lián)分類兩次學(xué)習(xí)方法。利用All-confidence度量項(xiàng)集中項(xiàng)之間的關(guān)聯(lián)程度，挖掘頻繁互關(guān)聯(lián)的項(xiàng)集產(chǎn)生規(guī)則，提高規(guī)則質(zhì)量。應(yīng)用改進(jìn)的關(guān)聯(lián)分類算法在訓(xùn)練集上進(jìn)行了兩次學(xué)習(xí)得到兩級(jí)規(guī)則共同構(gòu)成分類器。實(shí)驗(yàn)結(jié)果表明，在分類沖突實(shí)例時(shí)，基于改進(jìn)關(guān)聯(lián)分類的兩次學(xué)習(xí)方法相比一次學(xué)習(xí)算法顯著提高了分類準(zhǔn)確率。

[1] Liu B, Hsu W, Ma Y. Integrating classification and association rule mining[C]∥Proc of the 4th International Conference on Knowledge Discovery and Data Mining (KDD’98), 1998:80-86.

[2] Cheng H, Yan X, Han J, et al. Direct discriminative pattern mining for effective classification[C]∥Proc of the 20th International Conference on Knowledge Discovery and Data Mining (ICDE’08), 2008:169-178.

[3] Wu Jian-hua,Shen Jun-yi,Fang Jia-pei.An associative classification algorithm by distilling effective rules[J]. Journal of Xi’an Jiaotong University, 2009,43(4):22-25.(in Chinese)

[4] Jiang Yuan-chun, Liu Ye-zheng, Liu Xiao, et al. Integrating classification capability and reliability in associative classification:Aβ-stronger model [J]. Expert Systems with Applications, 2010, 37(5):3953-3961.

[5] Simon G, Kumar V, Li P. A simple statistical model and association rule filtering for classification[C]∥Proc of the 17th International Conference on Knowledge Discovery and Data Mining (KDD’11), 2011:823-831.

[6] Yu K, Wu X, Ding W. Causal associative classification[C]∥Proc of the 11th International Conference on Data Mining (ICDM’11), 2011:914-923.

[7] Li Xue-ming, Yang Yang, Qin Dong-xia, et al. Associative classification based on closed frequent itemsets[J]. Journal of University of Electronic Science and Technology of China,2012，41(1):104-109.(in Chinese)

[8] Agrawal R, Srikant R. Fast algorithms for mining association rules[C]∥Proc of the 20th International Conference on Very Large Data Bases (VLDB’94), 1994:487-499.

[9] Li W, Han J, Pei J. CMAR:Accurate and efficient classification based on multiple class-association rules[C]∥Proc of the 1st International Conference on Data Mining, 2001:369-376.

[10] Han J, Pei J, Yin Y. Mining frequent patterns without candidate generation[C]∥Proc of the 2000 ACM SIGMOD International Conference on Management of Data, 2000:1-12.

[11] Yin X, Han J. CPAR:Classification based on predictive association rules[C]∥Proc of the SIAM International Conference on Data Mining (SDM’03), 2003:331-335.

[12] Thabtah F.A review of associative classification mining [J]. The Knowledge Engineering Review, 2007, 22(1):37-65.

[13] Antonie M,Zaiane O,Holte R.Learning to use a learned model:A two-stage approach to classification[C]∥Proc of the 6th International Conference on Data Mining, 2006:33-42.

[14] Shekhawat P, Dhande S. A classification technique using associative classification[J]. International Journal of Computer Applications, 2011, 20(5):20-28.

[15] Lindgren T,Bostr?m H.Resolving rule conflicts with double induction[C]∥Proc of the 5th International Symposium on Intelligent Data Analysis, 2003:60-67.

[16] Omiecinski E R. Alternative interest measures for mining associations in databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(1):57-69.

[17] Zhao Y, Karypis G. Criterion functions for document clustering:Experiments and analysis[R]. Technical Report #01-40,Ninneapolis:University of Minnesota, 2001.

[18] Thabtah F A, Cowling P, Peng Y. MMAC:A new multi-class, multi-label associative classification approach[C]∥Proc of the 4th International Conference on Data Mining (ICDM’04), 2004:217-224.

附中文參考文獻(xiàn)：

[3] 武建華，沈鈞毅，方加沛. 提取有效規(guī)則的關(guān)聯(lián)分類算法[J]. 西安交通大學(xué)學(xué)報(bào)，2009，43(4):22-25.

[7] 李學(xué)明，楊陽，秦東霞，等. 基于頻繁閉項(xiàng)集的新關(guān)聯(lián)分類算法ACCF[J]. 電子科技大學(xué)學(xué)報(bào)，2012，41(1):104-109.