何田中，周忠眉，黃再祥

(閩南師范大學(xué)計(jì)算機(jī)科學(xué)與工程系，福建 漳州 363000)

1 概述

分類技術(shù)一直是數(shù)據(jù)挖掘技術(shù)中研究的熱點(diǎn)之一，近年來提出了各種不同的分類技術(shù)，如:將近似求導(dǎo)引入分類［1］，使用最近鄰進(jìn)行分類［2］等。為了提高不平衡數(shù)據(jù)集分類準(zhǔn)確率，文獻(xiàn)［3］使用KNN技術(shù)，文獻(xiàn)［4］提出基于Boosting 技術(shù)。規(guī)則式分類一直是分類技術(shù)的重要方法之一，近年來也提出了許多規(guī)則式分類技術(shù)，如:基于DE/QDE 算法技術(shù)［5］，具有多標(biāo)準(zhǔn)分類技術(shù)［6］，分層模糊化規(guī)則分類技術(shù)［7］，進(jìn)化的規(guī)則式系統(tǒng)［8］等。規(guī)則式分類具有分類速度快特點(diǎn)，因此規(guī)則式分類技術(shù)也得到了較為廣泛的應(yīng)用，如:肺癌評(píng)估［9］，預(yù)測(cè)蛋白質(zhì)相互作用類型［10］等。規(guī)則式分類技術(shù)抽取一條新規(guī)則時(shí)，使用某種度量獲取“最好”屬性值添加到當(dāng)前規(guī)則中。如ID3、C4.5［11］算法分別使用信息熵及信息增益來選擇“最好”屬性，信息熵及信息增益都是單一度量，使用它們度量屬性時(shí)存在很多度量值相等的“最好”屬性，導(dǎo)致上述算法很難選擇出真正的“最好”屬性。FOIL［12］算法使用FOIL 增益來度量，F(xiàn)OIL增益是支持?jǐn)?shù)與相關(guān)度的乘積。當(dāng)支持?jǐn)?shù)較大時(shí)，相關(guān)度幾乎不起任何作用，使用FOIL 增益也不能選擇出“最好”的屬性值。

規(guī)則式分類技術(shù)抽取一條新規(guī)則時(shí)，不斷選擇出“好”屬性值添加到規(guī)則中，直到該規(guī)則置信度100%為止，然后抽取下一條規(guī)則。這種學(xué)習(xí)方法容易導(dǎo)致過度學(xué)習(xí)，規(guī)則的支持度小、質(zhì)量不高，并且使規(guī)則抽取更為耗時(shí)。如在ID3 算法中，當(dāng)節(jié)點(diǎn)包含的實(shí)例為同一類時(shí)，分枝結(jié)束;此時(shí)的規(guī)則置信度為100%。FOIL 算法不斷地選擇“好”屬性值添加到當(dāng)前規(guī)則中，直到該規(guī)則不包含負(fù)實(shí)例為止，規(guī)則的置信度也是100%。

為了解決上述問題，本文提出了基于選擇度的分類規(guī)則學(xué)習(xí)算法LRSM，該算法具有以下特點(diǎn):

(1)使用一個(gè)新的屬性值度量方法——屬性值的選擇度，屬性值的選擇度是屬性值的信息熵、類的支持度及偏離度的綜合。由于選擇度是3 種度量的綜合，用它度量屬性值時(shí)，度量值相等“最好”屬性值的數(shù)量將大大減少。另外，選擇度包含偏離度，偏離度能夠衡量屬性值偏向某一類屬性值的程度。因此，選擇度不但能度量屬性值的好壞，而且還能夠反映出其偏向某一類屬性值的程度。

(2)LRSM 算法使用基于負(fù)實(shí)例數(shù)進(jìn)行剪枝(NIP)，即當(dāng)規(guī)則覆蓋的負(fù)實(shí)例數(shù)小于特定值時(shí)，LRSM 算法結(jié)束該規(guī)則抽取，進(jìn)行下一條規(guī)則抽取過程;這種方法克服了FOIL 等零負(fù)實(shí)例的學(xué)習(xí)方法帶來的過度擬合的問題，提高規(guī)則的支持度及質(zhì)量，分類準(zhǔn)確率得到較大的提高，同時(shí)也大大減少抽取規(guī)則時(shí)間。

2 屬性值的選擇度

設(shè)T 為元組集合，其屬性為A1，A2，…，Am及類屬性C={c1，c2，…，ck}，每一元組{a1，a2，…，am，c}稱謂實(shí)例，其中，ai是屬性Ai;c 是類屬性C 的值。實(shí)例{a1，a2，…，am，cp}稱為正實(shí)例，而實(shí)例{a1，a2，…，am，cq}，其中，q≠p 則稱謂負(fù)實(shí)例。

定義1 屬性值ai的信息熵:

其中，pj=mj/mai，m為包含屬性值的實(shí)例數(shù)，mj為包含屬性值ai，且類值為cj的實(shí)例數(shù)。

屬性值的信息熵能夠度量出屬性值所包含信息量大小，但不能夠反映出該信息量更偏向哪個(gè)類屬性值。數(shù)據(jù)集D 如表1 所示。

表1 數(shù)據(jù)集D

屬性值(A，1)的信息熵E((A，1))=0.918 3，其包含的實(shí)例如表2 所示。

表2 屬性值(A，1)包含的實(shí)例

從表2 可以看出，屬性值(A，1)包含的實(shí)例中，屬于類(C，1)的實(shí)例數(shù)比類(C，0)要少;但無法從信息熵看出屬性值(A，1)更偏向類(C，0)。為了克服信息熵的這種缺點(diǎn)，本文提出了屬性值的偏向熵。

定義2 屬性值ai對(duì)類cj的偏向熵:

其中，m為包含屬性值ai的實(shí)例數(shù);mcj為包含屬性值ai，且類值為cj的實(shí)例數(shù)。

按照定義2 屬性值(A，1)對(duì)類(C，0)及類(C，1)的偏向熵分別為:

可以看出，屬性值(A，1)更偏向于類(C，0)與實(shí)際情況一致。

定義3 屬性值ai對(duì)類cj的偏離度:

其中，k 為類值個(gè)數(shù);mc為包含屬性值ai，且類值為c的實(shí)例數(shù);Mc為類值為c 的實(shí)例數(shù)。

定義4 屬性值ai對(duì)類cj的選擇度:

從定義4 可以看出，選擇度是偏向熵與偏離度的綜合，而偏向熵綜合了熵與類的支持度，即選擇度是熵、類支持度及偏離度3 種度量的綜合;屬性值度量值相同的機(jī)會(huì)較少，更易選擇出“好”屬性值，實(shí)驗(yàn)結(jié)果表明，使用選擇度來度量屬性值具有更高的準(zhǔn)確率。

3 基于選擇度的分類規(guī)則學(xué)習(xí)算法LRSM

LRSM 算法具有以下特點(diǎn):(1)使用選擇度來度量屬性值，具有相同度量值的“最好”屬性值的數(shù)量大大減少，能更好地選擇出“好”屬性值;(2)LRSM算法使用基于負(fù)實(shí)例數(shù)進(jìn)行剪枝，因此抽取的規(guī)則的置信度小于100%，從而避免了過度學(xué)習(xí)，提高規(guī)則的支持度。對(duì)于訓(xùn)練集的每一個(gè)類屬性值，LRSM算法依次把屬于該類的所有實(shí)例作為正實(shí)例集，屬于其他類的實(shí)例作為負(fù)實(shí)例集，然后抽取屬于正實(shí)例集類的規(guī)則。抽取正實(shí)例集類規(guī)則時(shí)，LRSM 算法不斷使用選擇度來選擇“最好”屬性值添加到當(dāng)前規(guī)則中，當(dāng)該規(guī)則覆蓋的負(fù)實(shí)例數(shù)小于給域值時(shí)，規(guī)則抽取結(jié)束，刪除該規(guī)則覆蓋的正實(shí)例，再進(jìn)行下一條規(guī)則抽取。因此，LRSM 算法具有較高準(zhǔn)確率，且規(guī)則提取耗時(shí)更少的優(yōu)點(diǎn)。

LRSM 算法具體描述如下:

輸入 數(shù)據(jù)集D

輸出 一組規(guī)則集RS

(1)對(duì)數(shù)據(jù)集D 中的每一類標(biāo)c 值循環(huán)。

(2)將D 分成正實(shí)例集PS 及負(fù)實(shí)例集NS，其中，PS 為類標(biāo)值為c 實(shí)例，其余的組成NS。

(3)抽取規(guī)則rs=mineRule(PS，NS)，并添加到RS 中。

mineRule(PS，NS)過程描述如下:

1)規(guī)則集rs←Φ;

2)正實(shí)例數(shù)n←|PS|;

3)max_rule_length←屬性個(gè)數(shù);

4)WHILE n ＞0

5) NS'←NS，PS'←PS;

6) 規(guī)則r←Φ;

7) 當(dāng)前負(fù)實(shí)例數(shù)m←|NS'|;

8) 最小負(fù)實(shí)例數(shù)δ←m×α

9) WHILE(m ＞δ AND 規(guī)則r 長(zhǎng)度＜max_rule_length)

10) 根據(jù)PS' 及NS 計(jì)算所有屬性值的選擇度，并返回選擇度最大的屬性值av;

11) 將av 添加到規(guī)則r 中;

12) 從PS'、NS'移除不滿足規(guī)則r 的實(shí)例;

13)m←|NS'|

14) END

15) 規(guī)則r 添加到規(guī)則集rs 中;

16) 從PS'移除滿足規(guī)則r 的實(shí)例;

17) n←|PS'|

18)END

19)返回規(guī)則集rs

LRSM 使用選擇度選擇“好”的屬性值;由于選擇度是3 種度量綜合，因此屬性值具有相同度量值機(jī)會(huì)大大減少，更容易選擇“好”的屬性值;另外，當(dāng)負(fù)實(shí)例數(shù)小于最小負(fù)實(shí)例數(shù)δ，規(guī)則提取提前結(jié)束，因此規(guī)則抽取耗時(shí)更少，支持度更高。

以下通過一個(gè)例子說明LRSM 主要思想:數(shù)據(jù)集如表3 所示，以正實(shí)例為類屬性值(C，1)，負(fù)實(shí)例數(shù)域值為δ=2 為例進(jìn)行說明。

表3 數(shù)據(jù)集

此時(shí)，正實(shí)例集為:PS={X1，X2，X3，X7}，負(fù)實(shí)例集為:NS={X4，X5，X6，X8}。

提取第一條規(guī)則，PS'=PS，NS'=NS;空規(guī)則為:null→(c，1)。

計(jì)算屬性值的偏向信息熵、偏離度及選擇度如表4 所示。

表4 屬性值的偏離度、偏向熵及選擇度

由表4 可知，屬性值(A1，1)選擇度最大，將(A1，1)添加到規(guī)則中得:(A1，1)→(C，1)。

從PS'、NS'中刪除滿足規(guī)則前件的正、負(fù)實(shí)例得:PS'={X3，X7}，負(fù)實(shí)例集為:NS'={X8}。

從PS 中刪除滿足規(guī)則的實(shí)例，此時(shí)，正實(shí)例集為:PS={X1，X2}，負(fù)實(shí)例集為:NS={X4，X5，X6，X8}。由于正實(shí)例數(shù)不為零，繼續(xù)下一條規(guī)則抽取，過程同上，正類(C，1)的規(guī)則集為:(A1，1)→(C，1)，(A3，2)→(C，1)。

4 分類規(guī)則學(xué)習(xí)算法LRSM 的測(cè)試

在進(jìn)行測(cè)試之前，先計(jì)算出所有規(guī)則強(qiáng)度RS。測(cè)試每一實(shí)例時(shí)，如果該實(shí)例匹配的規(guī)則集的類屬性值相同，且該實(shí)例的類屬性值與規(guī)則集類屬性值一致，測(cè)試正確;若匹配的規(guī)則集類屬性值不同，將這些規(guī)則集按類屬性值分組，計(jì)算規(guī)則集R 的平均強(qiáng)度ARS(R)，如果該實(shí)例的類屬性值與最高平均強(qiáng)度的規(guī)則集類屬性值一致，測(cè)試正確。

計(jì)算規(guī)則強(qiáng)度定義如下:

其中，nc為滿足規(guī)則實(shí)例數(shù);l(r)為規(guī)則r 的拉普拉斯值［13］。

規(guī)則集R 的平均強(qiáng)度定義如下:

其中，n 為規(guī)則集R 中規(guī)則數(shù)。

5 實(shí)驗(yàn)結(jié)果與分析

所有的實(shí)驗(yàn)都是PC 機(jī)上進(jìn)行，其中，CPU 為3.1 GHz、內(nèi)存4 GB、操作系統(tǒng)為Windows XP;實(shí)驗(yàn)數(shù)據(jù)來源于UCI 機(jī)器學(xué)習(xí)庫。為了驗(yàn)證選擇度及LRSM 算法的準(zhǔn)確性及耗時(shí)，分別設(shè)計(jì)以下3 組與FOIL 對(duì)照的實(shí)驗(yàn)。

在第1 組實(shí)驗(yàn)中，用實(shí)驗(yàn)測(cè)試本文中屬性值的度量選擇度有效性。在FOIL 算法中，分別使用FOIL 增益及選擇度來選擇“好”屬性，表5 實(shí)驗(yàn)結(jié)果表明，選擇度度量平均準(zhǔn)確率比FOIL 增益高，尤其在數(shù)據(jù)集lymph、monks 和breast 有較大的提高。

表5 FOIL 增益及選擇度的準(zhǔn)確率對(duì)比

在第2 組實(shí)驗(yàn)中，為驗(yàn)證基于負(fù)實(shí)例數(shù)提前剪枝(NIP)的有效性，在FOIL 算法中使用基于NIP 剪枝與不使用NIP 剪枝，表6 結(jié)果表明，使用提前剪枝能使規(guī)則的支持度更高，規(guī)則質(zhì)量更好。因此，基于負(fù)實(shí)例數(shù)提前剪枝能較大地提高分類準(zhǔn)確率。

表6 使用NIP 剪枝與不剪枝的準(zhǔn)確率對(duì)比

在第3 組實(shí)驗(yàn)中，用實(shí)驗(yàn)測(cè)試LRSM 算法的準(zhǔn)確率及效率，使用LRSM 算法與FOIL 算法進(jìn)行實(shí)驗(yàn)，由于LRSM 算法使用提前剪枝且使用選擇度度量，表7 實(shí)驗(yàn)結(jié)果表明，與FOIL 算法相比，LRSM 算法訓(xùn)練耗時(shí)減少近一個(gè)數(shù)量級(jí)，而平均準(zhǔn)確率提高了近3 個(gè)百分點(diǎn)。

表7 FOIL 算法與LRSM 算法的準(zhǔn)確率及耗時(shí)對(duì)比

從上述3 組實(shí)驗(yàn)可以得出如下結(jié)論:

(1)三度量結(jié)合的選擇度比兩度量結(jié)合FOIL增益，更易選擇出“好”屬性值，分類準(zhǔn)確率更高;

(2)使用基于負(fù)實(shí)例數(shù)提前剪枝(NIP)不但能提高分類準(zhǔn)確率，而且能大大縮短提取規(guī)則的時(shí)間。

6 結(jié)束語

通常屬性值的度量采用單度量如信息增益，或2 種度量結(jié)合如FOIL 增益。不管是單度量還是2 種度量結(jié)合，仍然會(huì)存在若干不同屬性值的度量值相同，從而較難選擇出“好”的屬性值。本文提出一種三度量結(jié)合的度量選擇度，使用選擇度度量屬性值時(shí)，不同屬性值具有相同的度量值大大減少，因此更容易地找出“好”屬性值。此外，本文提出基于選擇度的規(guī)則學(xué)習(xí)算法LRSM。在LRSM 算法中，使用選擇度，及基于負(fù)實(shí)例數(shù)提前剪枝。用基于負(fù)實(shí)例數(shù)提前剪枝方法能提取到的規(guī)則支持度更高、質(zhì)量更好且耗時(shí)更少。實(shí)驗(yàn)結(jié)果表明，LRSM 算法減少了訓(xùn)練時(shí)間，且提高了分類準(zhǔn)確率。

［1］劉建偉，李雙成，羅雄麟.基于非近似求導(dǎo)過程的加更新和乘更新分類算法［J］.計(jì)算機(jī)學(xué)報(bào)，2013，36(2):327-340.

［2］鐘 智，朱曼龍，張 晨，等.最近鄰分類方法的研究［J］.計(jì)算機(jī)科學(xué)與探索，2011，5(5):467-473.

［3］王超學(xué)，潘正茂，馬春森，等.改進(jìn)型加權(quán)KNN 算法的不平衡數(shù)據(jù)集分類［J］.計(jì)算機(jī)工程，2012，38(20):160-163.

［4］李秋潔，茅耀斌，王執(zhí)銓.基于Boosting 的不平衡數(shù)據(jù)分類算法研究［J］.計(jì)算機(jī)科學(xué)，2011，38 (12):224-228.

［5］Su Haijun，Yang Yupu，Zhao Liang.Classification Rule Discovery with DE/QDE Algorithm［J］.Expert Systems with Applications，2010，37(2):1216-1222.

［6］Rezaei J，Dowlatshahi S.A Rule-based Multi-criteria Approach to Inventory Classification［J］.International Journal of Production Research，2010，48 (23):7107-7126.

［7］Fernández A，del Jesus M J，Herrera F.Hierarchical Fuzzy Rule Based Classification Systems with Genetic Rule Selection for Imbalanced Data-sets［J］.International Journal of Approximate Reasoning，2009，50 (3):561-577.

［8］Orriols-Puig A，Bernadó-Mansilla E.Evolutionary Rulebased Systems for Imbalanced Data Sets ［J］.Soft Computing，2009，13(3):213-225.

［9］Anthony N N，Michael J L.Symbolic Rule-based Classification of Lung Cancer Stages from Free-text Pathology Reports［J］.Journal of the American Medical Informatics Association，2010，17(4):440-445.

［10］Sung H P，José A R.Prediction ofProtein-protein Interaction Types Using Association Rule Based Classification［J］.BMC Bioinformatics，2009，10(1):36.

［11］Quinlan J R.C4.5:Programs for Machine Learning［M］.Vol.1.San Francisco，USA:Morgan Kaufmann，1993.

［12］Quinlan J R，Cameron-Jones R M.FOIL:A Midterm Report［C］//Proc.of ECML'93.Vienna，Austria:Springer，1993:3-20.

［13］Yin Xiaoxin，Han Jiawei.CPAR:Classification Based on Predictive Association Rules［C］//Proc.of SDM'03.San Francisco，USA:Society for Industrial ＆ Applied Mathematics，2003.