李莎莎

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

【關(guān)鍵詞】數(shù)據(jù)挖掘;分類;規(guī)則提取;二次學(xué)習(xí)

1 引言

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

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

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

2 基于規(guī)則的二次學(xué)習(xí)方法

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

2.1 RCDI規(guī)則生成

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

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

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

2.2 分類

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

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

3 實驗

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

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

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

通過以上的實驗結(jié)果，我們可以得出：1）RCDI分類器將關(guān)聯(lián)規(guī)則與基于規(guī)則相結(jié)合的分類算法是十分必要的。2）RCDI采用二次學(xué)習(xí)的方式，不僅可行，而且可以獲得很高的分類準(zhǔn)確率。

4 總結(jié)

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

參考文獻：

[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.

（作者單位：安徽廣播電視大學(xué)）