基于改進(jìn)關(guān)聯(lián)分類的兩次學(xué)習(xí)方法

黃再祥，周忠眉，何田中

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

1 引言

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

關(guān)聯(lián)分類算法主要包含類關(guān)聯(lián)規(guī)則產(chǎn)生和分類兩個階段。類關(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)建分類器。

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

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

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

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

(2)提出新的兩次學(xué)習(xí)框架。利用改進(jìn)的關(guān)聯(lián)分類算法在訓(xùn)練集上學(xué)習(xí)產(chǎn)生第一級規(guī)則；然后應(yīng)用第一級規(guī)則分離出訓(xùn)練集中規(guī)則沖突的實例；最后，在沖突實例上應(yīng)用改進(jìn)的關(guān)聯(lián)分類算法進(jìn)行第二次學(xué)習(xí)得到第二級規(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是項(或?qū)傩?值對)的集合，而Yi是類標(biāo)號。假設(shè)有兩個規(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個不同的特征屬性A1，A2，…,Am和一個類屬性Y。如果實例ti?X，稱之為實例ti匹配規(guī)則X?Yi。假設(shè)有兩個規(guī)則R1：X1?Y1和R2：X2?Y2，如果ti?X1且ti?X2，Y1≠Y2，則稱ti為沖突實例。

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

(1)

(2)

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

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

(3)

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

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

(4)

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

(5)

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

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

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

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

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

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

(4)通過類分布的交運算計算支持度[18]，避免多次掃描數(shù)據(jù)集。在第一趟掃描過程中，記錄項的類分布情況，結(jié)構(gòu)如〈X,{Yi,{行號}}〉，其中X是項，Yi是類別。在隨后的迭代過程中通過兩個項集的類分布交運算來計算項集的支持度和置信度。例如，假設(shè)某數(shù)據(jù)集有兩個類Y1和Y2，有兩個項集的類分布如下：〈X1,{(Y1,{1,2,3}),(Y2,{6,7,8,9})}〉，〈X2,{(Y1,{2,3,4}),(Y2,{5,6,7,8,10})}〉。通過求交運算可得〈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;

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

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

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

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

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

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

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

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

AlgorithmdoubleLearning(T，minsup,minAllconf,maxEntropy)

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

輸出：兩級規(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)生第一級規(guī)則RL1(行1)；然后利用第一級規(guī)則RL1將訓(xùn)練集中規(guī)則沖突的實例分離出來(行2)；最后在沖突實例集上應(yīng)用相同的關(guān)聯(lián)分類算法ICAR進(jìn)行第二次學(xué)習(xí)得到第二級規(guī)則RL2。

沖突實例分離算法如下：

AlgorithmConflictSet_G(T,RL1,conflictSet)

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

輸出：沖突實例集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

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

5 實驗與分析

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

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

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

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

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

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

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

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

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

6 結(jié)束語

針對關(guān)聯(lián)分類方法中規(guī)則沖突問題，本文提出了一種基于改進(jìn)的關(guān)聯(lián)分類兩次學(xué)習(xí)方法。利用All-confidence度量項集中項之間的關(guān)聯(lián)程度，挖掘頻繁互關(guān)聯(lián)的項集產(chǎn)生規(guī)則，提高規(guī)則質(zhì)量。應(yīng)用改進(jìn)的關(guān)聯(lián)分類算法在訓(xùn)練集上進(jìn)行了兩次學(xué)習(xí)得到兩級規(guī)則共同構(gòu)成分類器。實驗結(jié)果表明，在分類沖突實例時，基于改進(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é)報，2009，43(4):22-25.

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