应用分类贡献函数的决策树构造方法

谌章义，伍临莉

(洛阳师范学院信息技术学院，河南洛阳471022)

0 前言

在决策树的构建中一个关键问题就是选择合适的分类属性，使最后生成的决策树最小，也就是说决策树的分支最少。目前，已有多种选择属性构造决策树的方法，如ID3(以及其改进算法C4.5)、CART、CHAID、QUEST等，其中最经典的就是Quinlan提出的基于信息熵的方法ID3，C4.5［1］。这种方法已广泛应用于实际的分类问题。但是基于信息熵的方法存在的主要问题是一棵决策树中子树有重复，而且有些属性会在一棵决策树中的某一路径上被多次检验，从而降低了分类的效率和效果。

为此，很多学者在决策树生成算法中引入了粗糙集的概念，以提高分类效率［2－9］。粗糙集理论是波兰数学家Pawlak在1982年提出的一种分析数据的数学理论［10］，主要用来处理不确定和不精确信息。其特点是不需要预先给定某些特征和属性的数量描述，而是直接从给定问题的描述集合出发，找出该问题的内在规律，其基本思想更接近现实情况。该理论已广泛应用于数据挖掘、人工智能、模式识别等认知领域。

本文就是基于粗糙集的基本理论，设计了一个分类贡献函数来选择分类贡献最大的属性作为分类节点，使最后生成的决策树最小。通过在UCI数据集上做实验，与基于信息熵的C4.5算法，以及基于加权平均粗糙度的决策树生成算法［3］进行了比较。实验证明:应用了分类贡献函数后，构造的决策树与传统的基于信息熵方法构造的决策树相比较，其复杂性低，且能有效提高分类效果。

1 相关概念与原理

定义1 决策系统

一个决策系统是一个有序四元组:S=(U，A，V，f)，其中U是全域，是由对象构成的集合，U={x1， x2，…，xm};A是属性集合，A=C∪D，其中C是条件属性集，D是决策属性集;V=Va是属性值的集合，Va是属性a的值域;f:U×A→V是一个信息函数，对每一个a∈A和x∈U，定义了一个信息函数f(x，a)∈Va，即信息函数f指定U中每一个对象x的属性值。当属性集合A不划分为条件属性子集合和决策属性子集合时，该系统又称为信息系统。

定义2核

设P⊆C，若γP=γC，且不存在R⊂P，使得γR=γC，则称P为C的一个(相对于决策属性D的)属性约简。所有C的属性约简的交称为C的核，记为Core(C)。

属性a∈Core(C)当且仅当a是不可缺少的属性。

定义3 不可区分关系

对决策系统S=(U，A，V，f)，∀B⊆A是条件属性集合的一个子集，称二元关系IND(B)为S的不可区分关系:IND(B)={(x，y)∈U×U∀a∈B，f(x，a)=f(y，a)}。它表示对象x和y关于属性集A的子集B是不可区分的。

定义4 区分矩阵

所谓一个区分矩阵S，记作M(S)，是如下定义的一个n×n矩阵:

因此，矩阵元素cij是区分对象xi和xj的所有属性的集合。

很容易看出，若B是A的满足下面条件的一个最小子集，则B⊆A是A的缩减，B∩c≠φ，对于M(S)中任一非空元素c(c≠φ)。

换句话说，缩减是这样的属性最小子集，它能区分用整个属性集可区分的所有对象。

2 属性选择原理和算法

2.1 分类贡献函数的定义和说明

定义5 分类贡献函数

对决策系统S=(U，A，V，f)，xi，xj∈U，A是属性集合，A=C∪D，其中C是条件属性集;D是决策属性集。其对应的区分矩阵是M(S)，ak是核中的一个属性，cij是M(S)的矩阵元素。

这里，cij∩ak≠φ。I(cij∩ak)=1，如果ak是矩阵元素cij的一个属性;否则，I(cij∩ak)=0。n(cij)是矩阵元素cij中的属性个数。

分类贡献函数CCF(ak)的前面一部分的决策属性不同，d(xi)≠d(xj)，这表明属性对象xi，xj不属于同一类，所以ak适合于作分类节点;后面一部分的决策属性相同。d(xi)=d(xj)，表明对象xi，xj属于同一类，所以ak不适合作为分类节点。而则是属性ak在区分矩阵元素cij中所占的比重。这样前后两部分差值就是所希望得到的分类贡献值，该值越大，那么说明该属性越适合作为分类节点。

2.2 基于分类贡献函数的决策树构造算法(CCF)

基本思想是:先使用区分矩阵确定属性的核(如果没有核，则用其缩减)，然后通过分类贡献函数确定核中各个属性的分类贡献值，取值大的属性作为节点。接着用选择的属性去划分决策系统，相应于该属性的每一个取值产生一个子集，再在每一个子集中用同样的方法选择分类属性作为节点。这一算法递归地应用到导出的每一个分支上，直到树中所有分支都到达叶节点为止。

算法归纳如下:

(1)根据决策表生成区分矩阵，确定核，有3种情况:①没有核，则求出其最小缩减。②核中只有一个属性。③核中有多个属性。

(2)节点条件:①计算缩减里面属性的分类贡献函数值，选择值最大的一个属性作为节点。②选择这个核作为节点，不用计算。③计算核中各属性的分类贡献函数值，选择值最大的一个属性作为节点。

(3)根据所选定属性的不同取值，将决策系统分为不同子集，在每一个子集中分别重复步骤(1)和步骤(2)，直到所有的对象都划定到某一类中。

3 实例分析和比较

本算法与经典的基于信息熵算法的主要区别在于选择分类属性的标准不同。下面通过决策表实例对二者构造的决策树进行比较，见表1和表2。

由上述分类贡献函数算法来构造决策树，首先生成相应的区分矩阵:

步骤1:构造表1的区分矩阵，通过表2的区分矩阵可以很容易求得核{a3，a4}，这里核有两个属性，要分别计算它们的分类贡献值以决定取那一个作为根节点。属性a3，a4的分类贡献函数计算如下:

因为CCF(a3)比CCF(a4)大，所以选择属性a3作为根节点。

表1 决策表

表2 决策表对应的区分矩阵

步骤2:根据属性a3的不同取值将决策表系统分为3个子集:a3=1，a3=2和a3=3。

步骤3:应用相同的过程在a3=1，a3=2和a3=3的子集上直到它们满足节点条件。

图1a是在表1上基于信息熵的方法构造的决策树，而图1b就是用该方法在表1的决策表上构造的决策树。从图1的两个决策树中可以看到:图1a中决策树的复杂性(树中所有结点的个数)为12，对应7个叶结点;图1b中决策树的复杂性为10，对应6个叶结点。显然从树的大小来看，前者比后者少2个结点，少1个叶结点。通过这个简单的例子可以看出:本文提出的基于分类贡献值的概念构造的决策树可以降低树的复杂性。这意味着存储同一信息表所对应的决策树，基于分类贡献值的方法比基于信息熵的方法所占用的空间少;又由于前者比后者得到的叶结点少，所以更易于作决策;同时也避免了在决策树的一条路径上多次检验某一属性的问题。

4 实验结果

图1 基于信息熵的决策树和基于分类贡献值的决策树

在UCI［10］提供的数据集上分别运行了分类贡献函数和C4.5，用十倍交叉的方法验证两种方法构造决策树的分类精度。本文的算法用C++语言实现，在PentiumⅣ3.2 GHz处理器、512 M内存、WindowsXP环境下运行。C4.5的源程序来自［11］。表3给出了实验结果。

从表3中可以看出:与基于信息熵的方法C4.5相比较，基于分类贡献值的方法有较好的平均分类精确度，同时构造的决策树有较低的复杂性。与文献［3］基于加权平均粗糙度的决策树生成算法相比，分类效果基本相同。但是基于加权平均粗糙度的决策树生成算法要计算所有属性的平均粗糙度，而本算法只计算核(或其缩减)里面的属性。

表3 两生成算法在UCI数据集上的比较

5 结论

本文利用粗糙集理论中的条件属性相对于决策属性的确定性原理，提出了分类贡献值的概念，分类贡献值越大，说明该属性所包含的确定性因素越多，所以将分类贡献值最大的属性选为分类属性来构造决策树，同时通过分类贡献值来全面地考虑了决策属性每个划分对条件属性选择的影响，使结果更接近真实情况。通过实验与基于信息熵构造决策树的方法相比较，用本文提出的方法所构造的决策树，复杂性低，且有较高的平均分类精确度。

［1］ Quinlan JR.C4.5:Programs for Machine Learning［M］.San Mateo，CA:Morgan Kaufmann，1993.

［2］ Chandra B，Varghese PP.Moving Towards Efficient Decision Tree Construction［J］.Information Sciences，2009，179:1059－1069.

［3］ 蒋芸，李战怀，张强，等.一种基于粗糙集构造决策树的新方法［J］.计算机应用，2004，24(8):21－23.

［4］ 张先荣.粗糙集理论在智能数据分析中的应用［J］.河南科技大学学报:自然科学版，2008，29(5):88－90.

［5］ 程楠，祝彦知.基于模糊积分多元决策模型的电源开发排序［J］.河南科技大学学报:自然科学版，2009，30(2):45－49.

［6］ Chandra B，Kothari R，Paul P.A New Node Splitting Measure for Decision Tree Construction［J］.Pattern Recognition，2010，43(8):2725－2731.

［7］ Geetha S，Ishwarya N，Kamaraj N.Evolving Decision Tree Rule Based System for Audio Stego Anomalies Detection Based on Hausdorff Distance Statistics［J］.Information Sciences，2010，180(13):2540－2559.

［8］ Shi L，Weng M，Ma X M，et al.Rough Set Based Decision Tree Ensemble Algorithm for Text Classification［J］.Journal of Computational Information Systems，2010，6(1):89－95.

［9］ Pawlak ZW.Rough Sets and Intelligent Data Analysis［J］.Information Sciences，2002，147:1－12.

［10］ Murphy P，AhaW.UC Irvine Machine Learning Repository［DB/OL］.http://archive.ics.uci.edu/ml/，2009.

［11］ Zhou ZH.AISoftwares＆Codes［CP/OL］.http://cs.nju.edu.cn/zhouzh/zhouzh.files/ai_resource/software.htm，2009.