基于規則的二次學習分類方法

李莎莎

【摘 ?要】多數基于規則的分類方法對訓練集學習一次，產生的規則數量較少，在預測未知實例時容易出現不匹配規則的情況，影響分類準確率。文中提出一種基于規則的二次學習方法RCDI（Rule-based classification with double induction），選取長度為1和2的頻繁項建立候選集，頻繁項包含正項以及負項。在候選集上搜索全局以及條件庫最優值來產生規則，增大搜索空間。當測試出現規則不匹配或沖突的情況，則針對符合測試實例特征實例進行二次規則提取。實驗表明，該算法不僅可行，而且提高了分類準確率。

【關鍵詞】數據挖掘;分類;規則提取;二次學習

1 引言

分類是數據挖掘中重要的任務之一。傳統的基于規則的分類算法通常重復搜索當前一個最優值或多個最優值來產生規則，并移除訓練集中被這些規則覆蓋的例子，例如 FOIL[1]，CPAR[2] 和 CMER[3]等。這些分類方法選取生成規則的最優值時候選集中值數量少，搜索范圍較小，導致產生的分類規則較少，在測試未知實例時極易出現規則不匹配的情況，在某些訓練集上的分類準確率不高。Liu等提出了關聯分類方法來產生關聯規則[4]。大多數關聯分類算法主要基于正關聯模式來產生分類規則，如XTY的形式。如果是負相關則產生形如XT﹁Y 或者 ﹁X TY的負關聯，﹁X代表不取x值。研究表明負關聯模式也包含了非常有價值的信息，能更大范圍的增大候選集的搜索空間，因而利用負關聯模式進行分類同樣具有十分重要的意義。 年，Liudgren等提出了二次學習方法，該方法在解決規則沖突方面有著明顯的效果，但采用對沖突規則覆蓋實例進行二次學習，無法解決無匹配規則的測試情況。

針對以上問題，文中提出一種新算法：基于規則的二次學習分類算法RCDI（Rule-based classification with double induction）。RCDI候選集的產生采用頻繁模式，候選集包括滿足支持度和置信度、長度為1的正項和負項，以及長度為2的頻繁項，增大了對訓練集的搜索空間。在規則產生時，充分考慮候選集上全局以及條件庫最優值。規則產生過程中保留高置信度的中間規則。當測試未知實例出現規則不匹配或沖突的情況，根據測試實例的屬性值在訓練集上的覆蓋實例組成新訓練集，進行二次規則提取，二次提取規則與之前保留的高置信度規則結合，預測待分類實例類別。新訓練集符合待測實例的特征，很好的解決待測實例的規則不匹配問題。通過在10個UCI數據上測試結果表明，RCDI不僅可行，而且取得了很高的分類準確率。

本文的安排如下：第2節，我們介紹RCDI，并且討論怎樣用 RCDI對新實例進行分類。實驗結果在第3節進行報告。最終在第4節對我們的工作進行總結。

2 基于規則的二次學習方法

在本節，我們介紹基于規則的二次學習方法RCDI（Rule-based classification with double induction）生成的詳細步驟。

2.1 RCDI規則生成

假設 為一系列元組。每個元組 有m個屬性 。令 作為類標 ，并且 由 種樣本組成。一條規則 包含多個樣本 和一個類標 ，形式為 。從一個分類器中提取的規則組成了一個規則集。如果一個元組 滿足一條規則中 的形式，那么 被規則 匹配， 預測 屬于類別 。當一組屬性值 所在的元組個數與訓練集 的元組個數相等，則稱 被屬性值 覆蓋。

RCDI首先選擇訓練集中的單個類別作為正類P，其余類別作為負類N。正類候選集生成時考慮訓練集中屬性值的正項和負項。度量單個屬性值 以及 在每個類別中的增益值、相關度、支持度以及置信度。當滿足支持度，置信度為100%時加入規則集;若滿足給定支持度和置信度時，相關度大于1保留為頻繁集 ，并在頻繁集 中按照增益值由大至小進行排序，選擇增益大于0的值作為正類的種子集。使用Apriori 算法，滿足支持度、置信度和相關度要求生成頻繁集 。候選集包含長度為1和2的頻繁項集 、 。

候選集中每個項集的規則生成時挑選每個項集所在條件庫中的最優屬性值。項集的條件庫是指訓練集中包含該項集的所有樣本。每個項集 遞歸選擇條件庫中信息增益的最大值 ，并找出條件庫中存在的、種子集中信息增益最大值 ， 連接 與 生成pattern X。若pattern X的置信度為100%，則加入規則集;當置信度不足100%，但比 的置信度有提升，則X保留繼續生成規則;若置信度沒有提升，則拋棄這條pattern。在規則的生成過程中，保留置信度較高但不足100%的pattern作為備選規則。當一組規則生成后，對正例被規則覆蓋的實例進行刪除，若正例中還有實例，則重復規則提取過程。RCDI規則的生成規則如算法1所示。

2.2 分類

當測試未知實例時，RCDI首先度量每個規則的質量Laplace[2]，在每個類別中找出能匹配的規則集，并按照每條規則的 值由大至小進行排序，選取前3條，并計算在這個類別中的平均 值。具有最大平均 值的類別作為最終預測類別。

在測試時，若出現在每個類別都無規則匹配的情況，則要針對該實例進行二次學習。根據測試實例中包含的屬性值 ，在訓練集中找出包含 中任一屬性值的樣本，組成小訓練集 。在小訓練集中同樣運用2.1中所介紹的方法進行提取規則，記為 。聯合 與 共同對未知實例進行測試，測試時按照規則在訓練集上的置信度和支持度由大至小進行排序，選取具有最大置信度和最大支持度的規則對未知實例進行預測。

3 實驗

我們在10個 UCI數據集上進行實驗，每種數據的特點如表1所示。

Att代表每個訓練集的屬性個數，Cla代表訓練集的類別個數，Ins表明每個訓練集所包含的實例數目。每個數據集上的測試采用10-折交叉驗證方法。產生候選集時設置支持度為0.1，置信度為10%。在規則提取的過程中當置信度滿足60%，則保留為中間規則。

在表1，我們給出了CBA、CMAR、CPAR 和 RCDI的分類準確率，最后一行給出了每個算法的平均準確率。RCDI的候選集搜索范圍廣，并選取候選集中每個值條件庫中的最優種子來連接規則，結合了關聯規則和基于規則分類的優點。并且RCDI采用二次學習的方式，在規則不匹配和遇到沖突的情況下，根據未知實例特征所覆蓋的訓練集進行規則的再次提取。從表 可以看出，RCDI的分類準確率不僅高于CBA算法，并且能取得比CMAR和CPAR更高的分類準確率。

通過以上的實驗結果，我們可以得出：1）RCDI分類器將關聯規則與基于規則相結合的分類算法是十分必要的。2）RCDI采用二次學習的方式，不僅可行，而且可以獲得很高的分類準確率。

4 總結

準確率是衡量一個分類器好壞與否的重要指標。傳統的分類算法在預測實例時產生規則不匹配或規則沖突時沒有良好的解決方案。文中提出了一種基于規則的二次學習方法RCDI，選取滿足支持度和置信度、長度為 和 的頻繁項建立候選集，頻繁項包含正項以及負項，增大搜索空間。在候選集上搜索全局以及條件庫最優值來產生規則。當測試出現規則不匹配或沖突的情況，則針對符合測試實例特征實例進行二次規則提取。在大量數據上的實驗表明，該算法不僅可行，而且提高了分類準確率。

參考文獻：

[1]John Ross Quinlan，R.Mike Cameron-Jones.FOIL：A midtern report.In Proc.1993 European Conf.Machine Learning，Vienna，Austria，1993，pp：3-20.

[2]Xiaoxin Yin，Jiawei Han.CPAR：Classification based on Predictive Association Rules.Data Mining，The 2003 SIAM（Society for Industrial and Applied Mathematics）International Conference on，May.2003.

[3]Xuejun Wang，Zhongmei Zhou，Guiying Pan.CMER：Classification Based On Multiple Excellent Rules.Journal of Theoretical and Applied Information Technology，2013，pp.661-665.

[4]Wenmin Li，Jiawei Han，Jian Pei.CMAR：Accurate and efficent classification based on multiple class-assocation rules.In ICDM01，2011，pp.369-376.

（作者單位：安徽廣播電視大學）