基于改進關聯分類的兩次學習方法

黃再祥，周忠眉，何田中

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

1 引言

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

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

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

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

本文提出了基于改進的關聯分類兩次學習方法，創新點如下：

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

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

2 關聯分類的基本概念

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

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

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

(1)

(2)

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

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

(3)

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

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

(4)

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

(5)

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

3 改進的關聯分類算法

改進的關聯分類算法有以下四個特點：

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

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

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

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

該算法的具體過程如下：

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

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

輸出：類關聯規則集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為前件的置信度最大的規則Ri:X→Yi;

9: ifconf(Ri)>s(Yi)

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

11: if 泛化規則的置信度都小于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)，記錄每個項出現的行號，刪除信息熵超過maxEntropy的項，將頻繁的項加入L1中，并抽取相應的規則放入R中。

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

4 新的兩次學習框架

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

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

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

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

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

AlgorithmdoubleLearning(T，minsup,minAllconf,maxEntropy)

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

輸出：兩級規則集RL1和RL2。

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

2.ConflictSet_G(T,RL1,conflictSet);

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

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

沖突實例分離算法如下：

AlgorithmConflictSet_G(T,RL1,conflictSet)

輸入：訓練集T，第一級規則RL1;

輸出：沖突實例集conflictSet。

1. for(each instancetiinT)

2. for(each ruleRiinRL1)

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

4. 將Ri加入匹配規則集MR;

5. end if

6. end for

7. ifMR中規則類別不一致

8. 將ti加入沖突集conflictSet;

9. end if

10. end for

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

5 實驗與分析

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

Table 1 UCI dataset characteristics表1 UCI機器學習庫中的數據集特征

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

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

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

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

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

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

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

6 結束語

針對關聯分類方法中規則沖突問題，本文提出了一種基于改進的關聯分類兩次學習方法。利用All-confidence度量項集中項之間的關聯程度，挖掘頻繁互關聯的項集產生規則，提高規則質量。應用改進的關聯分類算法在訓練集上進行了兩次學習得到兩級規則共同構成分類器。實驗結果表明，在分類沖突實例時，基于改進關聯分類的兩次學習方法相比一次學習算法顯著提高了分類準確率。

[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] 武建華，沈鈞毅，方加沛. 提取有效規則的關聯分類算法[J]. 西安交通大學學報，2009，43(4):22-25.

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