黃再祥，周忠眉，何田中

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

1 引言

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

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

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

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

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

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

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

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

關聯(lián)分類方法是一種使用一組關聯(lián)規(guī)則來分類事務的技術。它挖掘形如X?Yi的類關聯(lián)規(guī)則，其中X是項(或屬性-值對)的集合，而Yi是類標號。假設有兩個規(guī)則R1：X1?Y1和R2：X2?Y2，如果X1?X2，則稱R1是R2的泛化規(guī)則，R2是R1的特化規(guī)則。

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

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

(1)

(2)

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

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

(3)

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

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

(4)

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

(5)

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

3 改進的關聯(lián)分類算法

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

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

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

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

(4)通過類分布的交運算計算支持度[18]，避免多次掃描數(shù)據(jù)集。在第一趟掃描過程中，記錄項的類分布情況，結構如〈X,{Yi,{行號}}〉，其中X是項，Yi是類別。在隨后的迭代過程中通過兩個項集的類分布交運算來計算項集的支持度和置信度。例如，假設某數(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)

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

輸出：類關聯(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;

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

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

4 新的兩次學習框架

新的兩次學習框架主要有以下三個特點：

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

(2)在沖突實例上進行二次學習得到第二級規(guī)則，與第一級規(guī)則共同構成分類器。

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

基于改進的關聯(lián)分類兩次學習具體算法如下：

AlgorithmdoubleLearning(T，minsup,minAllconf,maxEntropy)

輸入：訓練集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);

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

沖突實例分離算法如下：

AlgorithmConflictSet_G(T,RL1,conflictSet)

輸入：訓練集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ī)則將沖突實例分離出來。對訓練集中的每個實例從RL1中找出與第一個匹配規(guī)則置信度相差在Difconf之內的所有規(guī)則(行2～行6)，如果這些規(guī)則預測的類別不一致則將該實例加入沖突實例集(行7～行9)。

5 實驗與分析

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

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

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

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

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

Table 3 Comparison of DLIAC and IAC表3 基于改進關聯(lián)分類的兩次學習算法的分類性能

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

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

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

6 結束語

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

附中文參考文獻：

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

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