基于选择度的分类规则学习算法

何田中，周忠眉，黄再祥

(闽南师范大学计算机科学与工程系，福建 漳州 363000)

1 概述

分类技术一直是数据挖掘技术中研究的热点之一，近年来提出了各种不同的分类技术，如:将近似求导引入分类［1］，使用最近邻进行分类［2］等。为了提高不平衡数据集分类准确率，文献［3］使用KNN技术，文献［4］提出基于Boosting 技术。规则式分类一直是分类技术的重要方法之一，近年来也提出了许多规则式分类技术，如:基于DE/QDE 算法技术［5］，具有多标准分类技术［6］，分层模糊化规则分类技术［7］，进化的规则式系统［8］等。规则式分类具有分类速度快特点，因此规则式分类技术也得到了较为广泛的应用，如:肺癌评估［9］，预测蛋白质相互作用类型［10］等。规则式分类技术抽取一条新规则时，使用某种度量获取“最好”属性值添加到当前规则中。如ID3、C4.5［11］算法分别使用信息熵及信息增益来选择“最好”属性，信息熵及信息增益都是单一度量，使用它们度量属性时存在很多度量值相等的“最好”属性，导致上述算法很难选择出真正的“最好”属性。FOIL［12］算法使用FOIL 增益来度量，FOIL增益是支持数与相关度的乘积。当支持数较大时，相关度几乎不起任何作用，使用FOIL 增益也不能选择出“最好”的属性值。

规则式分类技术抽取一条新规则时，不断选择出“好”属性值添加到规则中，直到该规则置信度100%为止，然后抽取下一条规则。这种学习方法容易导致过度学习，规则的支持度小、质量不高，并且使规则抽取更为耗时。如在ID3 算法中，当节点包含的实例为同一类时，分枝结束;此时的规则置信度为100%。FOIL 算法不断地选择“好”属性值添加到当前规则中，直到该规则不包含负实例为止，规则的置信度也是100%。

为了解决上述问题，本文提出了基于选择度的分类规则学习算法LRSM，该算法具有以下特点:

(1)使用一个新的属性值度量方法——属性值的选择度，属性值的选择度是属性值的信息熵、类的支持度及偏离度的综合。由于选择度是3 种度量的综合，用它度量属性值时，度量值相等“最好”属性值的数量将大大减少。另外，选择度包含偏离度，偏离度能够衡量属性值偏向某一类属性值的程度。因此，选择度不但能度量属性值的好坏，而且还能够反映出其偏向某一类属性值的程度。

(2)LRSM 算法使用基于负实例数进行剪枝(NIP)，即当规则覆盖的负实例数小于特定值时，LRSM 算法结束该规则抽取，进行下一条规则抽取过程;这种方法克服了FOIL 等零负实例的学习方法带来的过度拟合的问题，提高规则的支持度及质量，分类准确率得到较大的提高，同时也大大减少抽取规则时间。

2 属性值的选择度

设T 为元组集合，其属性为A1，A2，…，Am及类属性C={c1，c2，…，ck}，每一元组{a1，a2，…，am，c}称谓实例，其中，ai是属性Ai;c 是类属性C 的值。实例{a1，a2，…，am，cp}称为正实例，而实例{a1，a2，…，am，cq}，其中，q≠p 则称谓负实例。

定义1 属性值ai的信息熵:

其中，pj=mj/mai，m为包含属性值的实例数，mj为包含属性值ai，且类值为cj的实例数。

属性值的信息熵能够度量出属性值所包含信息量大小，但不能够反映出该信息量更偏向哪个类属性值。数据集D 如表1 所示。

表1 数据集D

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

表2 属性值(A，1)包含的实例

从表2 可以看出，属性值(A，1)包含的实例中，属于类(C，1)的实例数比类(C，0)要少;但无法从信息熵看出属性值(A，1)更偏向类(C，0)。为了克服信息熵的这种缺点，本文提出了属性值的偏向熵。

定义2 属性值ai对类cj的偏向熵:

其中，m为包含属性值ai的实例数;mcj为包含属性值ai，且类值为cj的实例数。

按照定义2 属性值(A，1)对类(C，0)及类(C，1)的偏向熵分别为:

可以看出，属性值(A，1)更偏向于类(C，0)与实际情况一致。

定义3 属性值ai对类cj的偏离度:

其中，k 为类值个数;mc为包含属性值ai，且类值为c的实例数;Mc为类值为c 的实例数。

定义4 属性值ai对类cj的选择度:

从定义4 可以看出，选择度是偏向熵与偏离度的综合，而偏向熵综合了熵与类的支持度，即选择度是熵、类支持度及偏离度3 种度量的综合;属性值度量值相同的机会较少，更易选择出“好”属性值，实验结果表明，使用选择度来度量属性值具有更高的准确率。

3 基于选择度的分类规则学习算法LRSM

LRSM 算法具有以下特点:(1)使用选择度来度量属性值，具有相同度量值的“最好”属性值的数量大大减少，能更好地选择出“好”属性值;(2)LRSM算法使用基于负实例数进行剪枝，因此抽取的规则的置信度小于100%，从而避免了过度学习，提高规则的支持度。对于训练集的每一个类属性值，LRSM算法依次把属于该类的所有实例作为正实例集，属于其他类的实例作为负实例集，然后抽取属于正实例集类的规则。抽取正实例集类规则时，LRSM 算法不断使用选择度来选择“最好”属性值添加到当前规则中，当该规则覆盖的负实例数小于给域值时，规则抽取结束，删除该规则覆盖的正实例，再进行下一条规则抽取。因此，LRSM 算法具有较高准确率，且规则提取耗时更少的优点。

LRSM 算法具体描述如下:

输入 数据集D

输出 一组规则集RS

(1)对数据集D 中的每一类标c 值循环。

(2)将D 分成正实例集PS 及负实例集NS，其中，PS 为类标值为c 实例，其余的组成NS。

(3)抽取规则rs=mineRule(PS，NS)，并添加到RS 中。

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

1)规则集rs←Φ;

2)正实例数n←|PS|;

3)max_rule_length←属性个数;

4)WHILE n ＞0

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

6) 规则r←Φ;

7) 当前负实例数m←|NS'|;

8) 最小负实例数δ←m×α

9) WHILE(m ＞δ AND 规则r 长度＜max_rule_length)

10) 根据PS' 及NS 计算所有属性值的选择度，并返回选择度最大的属性值av;

11) 将av 添加到规则r 中;

12) 从PS'、NS'移除不满足规则r 的实例;

13)m←|NS'|

14) END

15) 规则r 添加到规则集rs 中;

16) 从PS'移除满足规则r 的实例;

17) n←|PS'|

18)END

19)返回规则集rs

LRSM 使用选择度选择“好”的属性值;由于选择度是3 种度量综合，因此属性值具有相同度量值机会大大减少，更容易选择“好”的属性值;另外，当负实例数小于最小负实例数δ，规则提取提前结束，因此规则抽取耗时更少，支持度更高。

以下通过一个例子说明LRSM 主要思想:数据集如表3 所示，以正实例为类属性值(C，1)，负实例数域值为δ=2 为例进行说明。

表3 数据集

此时，正实例集为:PS={X1，X2，X3，X7}，负实例集为:NS={X4，X5，X6，X8}。

提取第一条规则，PS'=PS，NS'=NS;空规则为:null→(c，1)。

计算属性值的偏向信息熵、偏离度及选择度如表4 所示。

表4 属性值的偏离度、偏向熵及选择度

由表4 可知，属性值(A1，1)选择度最大，将(A1，1)添加到规则中得:(A1，1)→(C，1)。

从PS'、NS'中删除满足规则前件的正、负实例得:PS'={X3，X7}，负实例集为:NS'={X8}。

从PS 中删除满足规则的实例，此时，正实例集为:PS={X1，X2}，负实例集为:NS={X4，X5，X6，X8}。由于正实例数不为零，继续下一条规则抽取，过程同上，正类(C，1)的规则集为:(A1，1)→(C，1)，(A3，2)→(C，1)。

4 分类规则学习算法LRSM 的测试

在进行测试之前，先计算出所有规则强度RS。测试每一实例时，如果该实例匹配的规则集的类属性值相同，且该实例的类属性值与规则集类属性值一致，测试正确;若匹配的规则集类属性值不同，将这些规则集按类属性值分组，计算规则集R 的平均强度ARS(R)，如果该实例的类属性值与最高平均强度的规则集类属性值一致，测试正确。

计算规则强度定义如下:

其中，nc为满足规则实例数;l(r)为规则r 的拉普拉斯值［13］。

规则集R 的平均强度定义如下:

其中，n 为规则集R 中规则数。

5 实验结果与分析

所有的实验都是PC 机上进行，其中，CPU 为3.1 GHz、内存4 GB、操作系统为Windows XP;实验数据来源于UCI 机器学习库。为了验证选择度及LRSM 算法的准确性及耗时，分别设计以下3 组与FOIL 对照的实验。

在第1 组实验中，用实验测试本文中属性值的度量选择度有效性。在FOIL 算法中，分别使用FOIL 增益及选择度来选择“好”属性，表5 实验结果表明，选择度度量平均准确率比FOIL 增益高，尤其在数据集lymph、monks 和breast 有较大的提高。

表5 FOIL 增益及选择度的准确率对比

在第2 组实验中，为验证基于负实例数提前剪枝(NIP)的有效性，在FOIL 算法中使用基于NIP 剪枝与不使用NIP 剪枝，表6 结果表明，使用提前剪枝能使规则的支持度更高，规则质量更好。因此，基于负实例数提前剪枝能较大地提高分类准确率。

表6 使用NIP 剪枝与不剪枝的准确率对比

在第3 组实验中，用实验测试LRSM 算法的准确率及效率，使用LRSM 算法与FOIL 算法进行实验，由于LRSM 算法使用提前剪枝且使用选择度度量，表7 实验结果表明，与FOIL 算法相比，LRSM 算法训练耗时减少近一个数量级，而平均准确率提高了近3 个百分点。

表7 FOIL 算法与LRSM 算法的准确率及耗时对比

从上述3 组实验可以得出如下结论:

(1)三度量结合的选择度比两度量结合FOIL增益，更易选择出“好”属性值，分类准确率更高;

(2)使用基于负实例数提前剪枝(NIP)不但能提高分类准确率，而且能大大缩短提取规则的时间。

6 结束语

通常属性值的度量采用单度量如信息增益，或2 种度量结合如FOIL 增益。不管是单度量还是2 种度量结合，仍然会存在若干不同属性值的度量值相同，从而较难选择出“好”的属性值。本文提出一种三度量结合的度量选择度，使用选择度度量属性值时，不同属性值具有相同的度量值大大减少，因此更容易地找出“好”属性值。此外，本文提出基于选择度的规则学习算法LRSM。在LRSM 算法中，使用选择度，及基于负实例数提前剪枝。用基于负实例数提前剪枝方法能提取到的规则支持度更高、质量更好且耗时更少。实验结果表明，LRSM 算法减少了训练时间，且提高了分类准确率。

［1］刘建伟，李双成，罗雄麟.基于非近似求导过程的加更新和乘更新分类算法［J］.计算机学报，2013，36(2):327-340.

［2］钟 智，朱曼龙，张 晨，等.最近邻分类方法的研究［J］.计算机科学与探索，2011，5(5):467-473.

［3］王超学，潘正茂，马春森，等.改进型加权KNN 算法的不平衡数据集分类［J］.计算机工程，2012，38(20):160-163.

［4］李秋洁，茅耀斌，王执铨.基于Boosting 的不平衡数据分类算法研究［J］.计算机科学，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.