基于约简属性和阈值分割的决策树构建方法

谭正华，戴立平，文 阳，李国泰

湘潭大学 信息工程学院，湖南 湘潭411105

1 引言

决策树是由贪心算法发展而来，由Hunt 等人于1966 年提出的[1]。它是数据挖掘分类算法里的关键分支，广泛运用于诸多领域。主要的决策树算法模型有ID3、C4.5、CART等[2]。其中C4.5算法分类精度高，对于小数据集处理速度快，且分类规则易理解，是最为经典的决策树算法。

文献[3]针对C4.5 算法需要多次扫描、运行效率低的问题，提出了信息增益率的对数优化，提高了算法的运行效率；Mantas等[4]提出了一种改进的C4.5算法——Credal-C4.5算法，通过使用新的不精确信息增益率分类标准，来估计特征和类别变量的概率，有效地解决了噪声数据分类中过度拟合的问题；Ngoc等[5]提出了利用决策树对英文情感词典进行分类，并在该基础上扩展出新的正极性与负极性关联规则，为决策树与关联规则的结合提供了新的方法；文献[6]提出了一种新的VFC4.5 算法，通过使用算术平均值和中值来减少候选阈值分割点的数量，改进了连续值属性分割的方式；Sergio等[7]提出了基于C4.5 分类器的进化分割点选择多元离散化分类，使用适应度函数来定义数据集的最佳离散化方案，提高了数据离散精度。

本文在C4.5 分类算法的基础上，提出了一种新的基于约简属性和阈值分割优化的决策树构建方法。该方法在离散化连续值特征属性过程中优化了最佳阈值分割点的选择，修正了信息增益率的计算方式，解决了分类数据集中特征属性冗余造成分类准确率降低的问题，提高了算法的运行效率与准确率。

2 C4.5算法原理

C4.5算法是对ID3算法的改进，由Quinlan[8]于1993年提出，其基本原理为：

首先采用熵值H(X,a)表示数据集分类为获取属性字段a 的代价，定义为：

其中，k 为属性a 的取值个数，n 为样本总数。然后用信息增益比表示单位代价获取到的信息量，定义为：

其中，I(X,a)为信息增益，将每一个属性的信息增益比作一个计算，来确定测试属性字段。

C4.5算法与ID3算法的不同主要有：

（1）在分支属性的选取上，C4.5 算法采用的是单位代价内获取到的信息量；

（2）C4.5能够完成连续值属性的离散化；

（3）选用常值或者均值，取代数据样本集的未知字段，能够完成缺省字段值的处理；

（4）对于模型优劣程度的评估，采用了K 次迭代交叉验证；

（5）该算法产生的是if-then 的规则集合，该规则集合会形成一条路径，由根节点到叶节点的规则生成。

虽然C4.5算法相对于ID3算法有所改进，提高了识别效果，但还是没能够脱离信息熵的范畴，树的分化仍旧是一个多叉树；同时需要将数据集中的属性做一个扫描排序，增加了时间复杂度[9]。

3 基于属性相关性的约简方法

如何解决决策树属性冗余约简问题，采用概率论中的Pearson系数[10]来对属性间的相关性进行度量。属性约简的目标为：对于决策属性和特征属性，两者之间的相关性越大越好，以保证特征属性子集中没有其他无关属性；对于特征属性，每个属性间的相关性越小越好，使得属性子集中没有冗余属性[11]。

Pearson系数有如下定义：

定义1 对于随机变量X 的概率分布为P{X=Xk}=Pk(k=1,2,…)，当绝对收敛时，则称该级数的和为X 的数学期望E(X)：

定义2 若随机变量X 存在E{[X-E(X)]2}，则称其为X 的方差，用D(X)表示：

定义3 随机变量Y 的数学期望为E(Y)，与随机变量X 的协方差用Cov(X,Y)表示，其中：

那么随机变量X、Y 之间的相关系数（Pearson）表示为：

在两个任意随机变量之间，如下等式成立：

在决策树模型中，X、Y 表示数据集中的两个特征属性集合，数据样本总数为num，其属性值分别为X={X1,X2,…,Xm},包含了m 个属性值；Y={Y1,Y2,…,Yn},包含了n 个属性值。其中Xi表示特征属性X 中的第i个值，Yj表示特征属性Y 中的第j 个值，nai表示满足条件X=Xi的样本个数，用nbj表示Y=Yj的样本个数，当存在X=Xi且Y=Yj的样本数时，用naibj表示，其结果如图1所示。

图1 结果覆盖示意图

特征属性X、Y 的相关系数ρxy取绝对值，由式（4）、式（8）可推导得出：

结合式（3）可得：

对于数据集中存在的特征属性，两者间的相关性越大则p 值越大，反之越小。当属性间相关性较大时，比较属性间的信息增益率，那么可以通过去除信息增益率较小的冗余属性，达到约简数据集特征属性，提高决策树模型准确率的目的。

一般情况下，当0.8 ≤ρxy≤1 时，表示两个特征属性极强相关；0.6 ≤ρxy＜0.8 时，强相关；0.4 ≤ρxy＜0.6 时，中等程度相关；0.2 ≤ρxy＜0.4 时，弱相关；0 ≤ρxy＜0.2时，极弱或者无相关。

4 基于阈值分割点的边界判定优化

传统C4.5算法对连续值的处理如下[12]：

（1）对数据样本子集中的变量统一排序，以升序的排列方式得到属性序列{A1,A2,…,An}；

（2）根据属性值划分，得到n-1 个候选分割阈值点，对于第i 个分割阈值点，分割取值设置为Si=middle{Ai,Ai+1}={Ai,Ai+1}/2，将样本集划分为两个子集；

（3）产生的候选阈值分割点共有n-1 个，并对阈值分割点的信息增益率系数进行计算，最佳的阈值分割点为计算系数最大的点。

在上述计算中，需要计算n-1 个阈值分割点的信息增益率，当数据总量较大时，容易出现时间复杂度较高的问题。针对以上问题，在C4.5 决策树对连续变量分裂属性的处理上，提出了一种优化阈值分割点的方法，减少了分割阈值点的划分，降低了算法的时间复杂度。当数据集样本较大时，能够较好地提高运行效率。

4.1 阈值分割点的边界判定定义

定义4 边界点：对于训练集T,T 中有连续字段A，当将A 字段中的连续字段属性值按照从小到大排列后，有一个点S 将T 划为两个子集T1和T2，能够使得T1＜S ＜T2，其中T1中所有的A 属性值都小于T,T2中所有的A 字段值都会比T 大，那么就可以将T 定义为一个边界点。

定理1 关于边界点判定定理：定义T 为样本数据集，A 为字段属性，E 为在属性A 上划分样本数据集T 所得到的平均类熵，S 为字段A 的阈值点。如果存在S，使得E(A,S;T)最小，则S 是一个边界点。

通过上述判定定理，离散化阈值分割点存在边界点中，最佳划分点总是在边界处，如果把同一个类分成了不同的类，那么这样的分割点是不会有信息增益的。因此并不需要测试所有的分割阈值点，只需要测试边界点[13]。

4.2 分割点的优化判定方法

基于边界点判定定理，通过边界点的划分，降低算法的时间复杂度，减少处理连续属性的计算量，其步骤如下：

步骤1 对连续属性进行升序排序，得到序列；

步骤2 划分阈值分割点，对每个阈值分割点是否属于边界点进行判定；

步骤3 计算边界点的信息增益，选择信息增益最大的边界点进行离散化；

步骤4 将连续属性值离散为两部分，构造决策树节点。

优化的C4.5决策树构造伪代码如下：

输入：节点N ，训练样本集S，分类属性集A；

输出：一棵决策树；

算法流程如图2所示。

图2 阈值分割流程图

在对最佳阈值分割点进行判定时，为避免特征属性分化选择偏连续值属性，对处理连续值特征属性的方法进行了修正[14]。其中最佳分割点为信息增益最大的点，而不是信息增益率最大的点。离散化后再计算该特征属性的信息增益率。修正步骤为：

步骤1 将该节点上的连续属性值进行升序排序，得到属性序列为{A1,A2,…,An,…,Atotal}；

步骤2 按照升序序列产生total-1 个阈值分割点，其中第n 个分割点的取值为(An+An+1)/2，将样本数据集分成两个子集，通过边界点优化方法划分边界点，减少阈值分割点的计算；

步骤3 计算边界点的信息增益，选择信息增益最大的边界点作为该特征属性的最佳分割点；

步骤4 离散化该连续值特征属性，计算该最佳边界分割点的信息增益率，并对其减去lb(N-1)/||D 进行修正，修正方法为：

其中，N 为连续特征的取值个数，D 为训练数据集data_set 的样本量，GainRatioX为该节点属性X 离散化后的信息增益率。

5 实验结果及分析

本文实验在Pycharm 平台上进行，算法实现采用python 语言。实验环境如下：Windows10、CPU-Intel®CoreTMi5-4200U@1.60 GHz，8 GB RAM。实验分为两部分：（1）采用传统的C4.5算法；（2）采用改进的C4.5算法。首先对数据集特征属性进行约简，去掉冗余属性，然后对连续值特征属性离散化进行优化处理，并对信息增益率计算进行修正。本文采用的数据集来自于UCI机器学习平台，实验以CPU 运行时长和准确率作为衡量算法时间复杂度和准确率高低的评判标准，测试案例为生成分类决策树。

本文采用的数据集共三个，具体内容参见表1。

表1 数据集具体内容

上述数据集中，iris数据集样本量较少，属性较少且特征属性全为连续值属性；wine数据集属性较多且特征属性全为连续值属性；abalone数据集样本量较多，特征属性包含了连续值属性和离散值属性。

5.1 数据集处理

计算数据集中特征属性间的相关系数ρ，结果如表2、表3、表4所示。

iris、wine、abalone数据集每个特征属性的信息增益率如表5、表6、表7所示。

当特征属性个数numfeature＜10，选取ρ ≥0.9 的特征属性；当numfeature≥10 时，选取ρ ≥0.85 的特征属性。通过比较特征属性的信息增益率，三个数据集的冗余属性分别为iris{Petal.Length}、wine{Totalphenols}、abalone{Length,Wholeweight,Visceraweight,Shellweight},去除该数据集中的冗余属性，新数据集用于改进的C4.5算法。

表2 iris数据集特征属性相关系数

表3 wine数据集特征属性相关系数

表4 abalone数据集特征属性相关系数

表5 iris特征属性的信息增益率

表6 wine特征属性的信息增益率

表7 abalone特征属性的信息增益率

5.2 实验结果

实验采用多次验证的方法[15]，从数据集随机抽取70%作为训练集，30%作为测试集，进行10次实验，取实验的平均值作为实验结果。实验结果如表8、表9、表10所示。

表8 iris数据集实验结果

表9 wine数据集实验结果

传统C4.5算法和改进C4.5算法的实验结果如图3、图4所示。

表10 abalone数据集实验结果

图3 CPU耗时对比图

图4 准确率对比图

实验结果表明：改进的C4.5 算法在时间运行效率和模型准确率上有了一定的提高。利用基于阈值分割点的边界判定优化可以减少连续值属性离散化的计算量，有效提高决策树的生成效率。当样本数据量较少时，运行效率约提升了50%，随着样本数量的增加，运行效率提升更为明显。同时针对数据集中冗余属性的约简和信息增益率的修正，有效地提高了模型分类的准确率。

6 结束语

本文采用约简属性和阈值分割优化方法，可以有效地提高决策树模型的生成效率和准确率。该方法在具有多个连续值属性的数据集中效果较为明显，如本文中小样本数据集iris和wine，改进前后的差别明显，具有较好的应用前景和价值。本文主要针对多特征属性和多连续值属性的数据样本进行改进。当数据样本量较大时，如abalone 样本集，运行时间较长且模型准确率较低，这是C4.5算法本身的缺陷，也是下一步研究和改进的方向。