李莎莎

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

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

1 引言

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

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

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

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

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

2.1 RCDI規(guī)則生成

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

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

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

2.2 分類

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

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

3 實(shí)驗(yàn)

我們在10個(gè) UCI數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，每種數(shù)據(jù)的特點(diǎn)如表1所示。

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

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

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

4 總結(jié)

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

參考文獻(xià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é)）