高虹雷，门昌骞，王文剑,2

1(山西大学 计算机与信息技术学院，太原 030006)2(山西大学 计算智能与中文信息处理教育部重点实验室，太原 030006)

E-mail：wjwang@sxu.edu.cn

1 引 言

随着大数据时代的来临，合理高效地对海量数据进行分类从而得到隐藏的、有价值的、可理解的知识，将会对日常生活产生重要的影响.分类作为机器学习的一个核心任务，在数据的分析处理上发挥着重要的作用.常见的分类方法有神经网络[1]、朴素贝叶斯法[2]、K最近邻法[3]、决策树[4]和支持向量机[5]、深度神经网络[6]等.决策树与其它分类算法相比，由于容易实现且易于理解，因而得到了广泛地应用.目前决策树的相关研究集中在决策树改进方面.

传统的决策树算法主要有ID3算法[7]，C4.5算法[8]以及分类与回归决策树(classification and regression tree，CART)[9]等.ID3算法通过使用信息增益准则进行特征选择，但不能处理连续特征值.Quinlan随后将ID3算法进行了改进，提出C4.5算法，采用信息增益比来克服ID3算法的不足，但C4.5算法需要对数据集进行多次的顺序扫描和排序，比较耗时.CART决策树本质上是一棵二叉树，使用Gini指数来进行特征选择，既可以处理连续值也可以处理离散值，被称为数据挖掘领域中里程碑式的算法.

Alsabti等人[10]从抽样方法的角度上提出了一种新的决策树分类器用于处理大规模数据集，在确定最优分裂结点上提供了两种新的度量方法，缩小了搜索空间.此外，Mehta和Agrawal等人提出的一种快速可伸缩分类器SLIQ(Supervised Learning In Quest)[11]对C4.5算法进行了改进，该算法在决策树构造过程中采用了预排序及广度优先策略，缩短了学习的时间，提高了决策树构建的效率，但它需将类别列表储存在内存中，从而导致数据集的规模受到了限制.Shafer和Agrawal等人[12]对SLIQ算法进一步改进，提出了一种新的算法，该算法构建了一种可扩展、可并行的决策树，解决了内存限制的问题.这两种决策树均能处理大规模数据集，且能处理连续特征值和离散特征值.Rastogi等人[13]提出了建树和剪枝结合在一起的分类算法，用以提升决策树构建的效率.随着集成学习(Ensemble Learning)[14]在分类问题中的不断推广，越来越多的基于决策树的集成学习方法应用而生.Breiman以决策树为基本单元，运用Bagging方法提出的随机森林RF(Random Forest)[15]可以有效避免过拟合问题，Friedman以决策树为基础，运用Boosting方法提出的GBDT(Gradient Boosting Decision Tree)[16]可以根据损失函数的不同灵活处理各种类型的数据，并在分类速度上得到了很大的提升.之后，华人科学家陈天奇和微软公司分别开发出了GBDT的改进算法Xgboost(extreme Gradient Boosting)[17]和LightGBM(Light Gradient Boosting Machine)[18]，这两种算法在保证分类精度的前提下，速度更快，被广泛应用于工程领域之中.南京大学周志华教授类比深度神经网络提出了一种新的决策树集成方法Deep Forest[19]，使用树集成来构建多层模型，该算法只需少量训练数据以及参数优化就可以得到很好的性能.在2018年，周志华研究团队又提出了多层梯度提升决策树mGBDT(Multi-Layered Gradient Boosting Decision Trees)[20]，首次确认了可以使用决策树来进行分布式表征，并取得了明显的效果.

尽管对决策树的研究已经取得了很多的成果，但仍存在一些问题，如决策树在训练集上的过度分类可能会导致过拟合现象的发生,从而影响分类预测的准确率.另外，在寻找最佳分裂点时需要遍历特征的所有取值，当数据集规模较大时，递归构建决策树所需时间将会很长.文献[21]提出的模型决策树(Model Decision Tree，MDT)相对于传统决策树来说加速了构建过程，在一定程度上具有抗过拟合作用.其主要思想为在分类树叶子规模到达给定阈值时停止树的构建，并在生成的不完全决策树的可辨识结点(非叶结点且包含不同类别的样本)上搭载分类器，通过分类器继续进行分类.由于模型决策树在可辨识结点上已经使用了比较强的分类器，但在选择最优特征划分和最优切分点时仍需要计算全部样本每一特征维度上的所有取值，这样会增加一些没有必要的计算代价.

本文在文献[21]基础上提出一种基于特征值区间划分的模型决策树加速算法，算法根据数据的不同分布给出两种特征值区间的分割方法，通过计算各选定区间的基尼指数，寻找最优特征及最优切分点，最后递归生成模型决策树.所提出的算法可在保证分类精度的前提下加快决策树的构建.

2 基于特征值区间划分的模型决策树加速算法

2.1 特征值区间划分

模型决策树[21]在处理二分类问题时通过对每一特征维度上的所有特征值分别计算其Gini指数并以此逐层构建二叉树，直到树深度或叶子节点满足某一条件时停止，此时构建的二叉决策树可以较好地对数据进行分类，但当数据规模较大时，用全部样本每一特征维度上所有取值来构建决策树会耗费大量的时间及计算资源.本文提出两种面向不同类型特征值分布的特征值区间划分方法，用以加速决策树的构建过程.

2.1.1 等精度特征值区间划分

当数据集中所有样本每一特征维度上取值分布较为均匀时，特征取值差异较小，此时将特征取值划分为多个等精度区间并用每一区间所含特征值的平均值代表各区间的值，之后对每一区间平均值计算其Gini指数进而构建决策树，此时决策树构建所需时间及计算代价将大大降低.等精度特征值区间划分的详细过程如下.

…

之后计算每一区间特征取值平均值：

…

此时等精度特征值区间划分完成.图1是在Magic Gamma Telescope数据集(说明见表1)上进行等精度特征值区间划分的结果，在数据集中随机挑选一个特征，利用等精度特征值区间划分方法将其划分成10个区间，每个区间样本个数为902个，各分裂结点的位置即各区间内包含的所有样本特征值的平均值.

图1 等精度特征值区间划分结果Fig.1 Result of equal-precision feature value interval partition

2.1.2 变精度特征值区间划分

当数据集中所有样本每一特征维度上取值分布波动较大时，特征取值差异较大，此时等精度特征值区间划分无法充分表示特征取值特性，针对这种情况，本文提出变精度特征值区间划分方法.该方法根据每一特征维度上特征取值的上界和下界将特征值取值空间等分为多个区间，之后统计每一区间中样本个数，确定不足给定样本个数阈值的区间，最后根据这些区间中所含样本特征取值的平均值计算其各自Gini指数进而构建决策树.

…

统计每一区间中包含的样本数，对于样本数小于给定阈值N*的区间，计算该区间内所包含特征取值的平均值，此时变精度特征值区间划分完成.图2是在Cod_rna数据集(说明见表1)上进行变精度特征值区间划分的结果.在数据集中随机挑选一个特征，利用变精度特征值区间划分方法将其划分成20个区间，各样本点依据特征值的大小落入不同区间内，如给定阈值N*等于400，各分裂结点的位置就是样本数小于400的区间内所包含的所有样本特征值的平均值.

图2 变精度特征值区间划分结果Fig.2 Result of variable-precision feature value interval partition

2.2 寻找最优特征及最优切分点

特征选择是对特征空间划分及决策树构建非常重要的一步，通过递归选择最优特征并依据此特征计算的最优切分点对训练数据进行划分，从而保证各子数据集可以按照最好的分类标准去分开.一般而言，理论上希望在不断划分的过程中，各结点中所包含的样本纯度会不断提高，不确定性会逐渐变小，即只包含同一类样本.在这个过程中，有些特征并没有分类能力，实际上舍去这些特征并不会影响分类的准确率，并且可以对决策树分类的效率进行提高.因此，通常会使用信息增益、信息增益比、基尼指数等准则作为分类算法属性选择的度量标准，本文选择Gini指数作为最优特征及最优切分点的度量.

在分类问题中，设给定的训练数据集为D，其样本个数为|D|，假设有K个类，Ck表示D中属于第k类的样本子集，k=1，2，…，K，|Ck|表示属于Ck类样本的个数.定义样本点属于第k类的概率为Pk，则该数据集在概率分布P下的Gini指数:

(1)

给定训练数据集D的Gini指数为：

(2)

对于二分类问题，若要在训练集D中根据特征A的某一个取值a来计算基尼指数，则训练集D被划分为D1和D2两部分：

D1={(xi,yi)∈D|A(xi)=a},D2=D-D1

(3)

训练集D在特征A的条件下，Gini指数定义为：

(4)

式(2)表示训练集D抽取样本类别标记不一致的概率，即Gini指数越小，纯度越高，划分越好；式(4)表示训练集D在特征A下按特征值a划分后的Gini指数，根据式(4)在候选属性集合中找到使得划分后Gini指数最小的属性以及切分点，可以得到最优特征及最优切分点.

2.3 模型决策树加速算法

本文提出的等精度特征值区间划分模型决策树算法EPPMDT(Model decision tree based on equal-precision feature value interval partition)的主要步骤总结如下.

EPPMDT算法

输入：训练数据集D，测试数据集S，划分区间数Z，可辨识结点中样本个数阈值V

输出：EPPMDT决策树

Step 1.对于训练数据集D，根据等精度特征值区间划分方法将每维特征下的特征值划分成H0,H1,…,Hz-1个区间，计算各区间特征取值的平均值M0,M1,…,Mz-1，将其作为当前需要分裂结点上每一特征对应的可能取值；

Step 2.对每一特征A及其可能取的值a，根据样本点对A=a将D划分为D1和D2两部分，通过式(4)计算所有可能的特征和所有的切分点对该数据集D的Gini指数，选择Gini指数最小的特征和其对应的切分点进行划分；

Step 3.对划分之后得到的两个子结点递归调用Step 1和Step 2，直至可辨识结点中样本个数小于阈值V，这时中止决策树的生长；

Step 4.在所得到的可辨识结点上搭载分类器，生成等精度特征值区间划分的模型决策树；

Step 5.算法结束.

EPPMDT算法适用于样本每一特征维度上取值分布较为均匀，特征值差异较小的数据集.当数据集中所有样本每一特征维度上取值分布波动较大时，特征取值差异较大时，可采用变精度特征值区间划分模型决策树算法VPPMDT(Model decision tree based on variable-precision feature value interval partition)，其主要步骤如下.

VPPMDT算法

输入：训练数据集D，测试数据集S，划分区间数Z，区间中样本个数阈值N*，可辨识结点中样本个数阈值V

输出：VPPMDT决策树

Step 1.设根结点的训练数据集为D，根据变精度特征值区间划分方法将每维特征下的特征值划分成H0,H1,…,Hz-1个区间，计算样本数小于给定阈值N*的区间内所包含的特征取值的平均值，将其作为当前需要分裂结点上每一特征对应的可能取值；

Step 2.对每一特征A及其可能取的值a，根据样本点对A=a将D划分为D1和D2两部分，通过式(4)计算所有可能的特征和所有的切分点对该数据集D的Gini指数，选择Gini指数最小的特征和其对应的切分点进行划分；

Step 3.对划分之后得到的两个子结点递归调用Step 1和Step 2，直至可辨识结点中样本个数小于阈值V，中止决策树的生长；

Step 4.在所得到的可辨识结点上搭载分类器，生成变精度特征值区间划分的模型决策树；

Step 5.算法结束.

3 实验结果及分析

3.1 实验设置及实验数据集

实验使用UCI数据集中的9个典型二分类数据集进行测试，如表1所示.为消除实验的随机性，每种算法在每个数据集上的实验结果为运行20次结果的均值.

表1 实验数据集Table 1 Datasets used in experiments

本文提出的EPPMDT算法及VPPMDT算法，在生成的不完全决策树中可辨识结点上使用简单的分类器继续进行分类，分类器选用了软件包LIBLINEAR模型和标准SVM模型，形成6种不同的模型，其中使用了LIBLINEAR模型的记为EPPMDT_LIB和VPPMDT_LIB，使用线性核的SVM模型记为EPPMDT_SVM(linear)和VPPMDT_SVM(linear)，使用高斯核的SVM模型记为EPPMDT_SVM(rbf)和VPPMDT_SVM(rbf).因文献[21]中所提的算法已与常见的分类算法SVM、LIBLINEAR、逻辑回归(Logistic Regression，LR)、KNN以及传统决策树DT进行了性能比较，且在分类错误率和运行时间方面均有提升，故本文提出的6种模型将直接与文献[21]中提出的3种模型决策树算法MDT_LIB、MDT_SVM(linear)和MDT_SVM(rbf)进行比较.

本实验首先将训练数据集按4∶1的比例随机均匀抽样得到验证集，通过实验得到对应的最优参数.实验中可辨识结点样本个数阈值V、LIBLINEAR中的类型参数以及SVM中惩罚参数、高斯核参数均为不同实验数据集下在验证集上得到的最优参数.因部分数据集训练样本数较少，为保证合理划分区间，EPPMDT 3种模型算法在Madelon数据集上可辨识结点规模V取训练样本数的20%，VPPMDT 3种模型算法在Germen、Spambase和 Credit Card Cliet数据集上V取训练样本数的30%，其余算法中V均为训练样本数的10%.使用LIBLINEAR模型的算法类型参数S取2，使用线性核SVM模型和高斯核SVM模型算法中的惩罚参数C除在Credit Card Cliet、Magic Gamma Telescope和Cod_rna数据集中为1以外，其余均为50，使用高斯核SVM模型算法中的高斯核参数γ除在Credit Card Cliet、Magic Gamma Telescope和Cod_rna数据集中为0.5，其余均为1.

3.2 EPPMDT和VPPMDT算法的参数实验设置

划分区间数Z这一参数对EPPMDT算法和VPPMDT算法都有影响，除此之外，VPPMDT算法还受区间中样本个数阈值N*的影响.

3.2.1 EPPMDT算法中划分区间数Z的设置

模型的分类错误率及运行时间在不同的划分区间数下会有所不同，因此，在不同数据集下找到最优的划分区间个数至关重要.本文通过实验获得各数据集上划分区间数Z的较优值，对于不同数据集，通过实验设置的参数如表2所示.

表2 EPPMDT算法参数设置Table 2 Parameter setting of EPPMDT

3.2.2 VPPMDT算法中划分区间数Z及样本个数阈值N*的设置

在VPPMDT算法中，划分区间数Z以及区间中样本个数阈值N*均会影响算法的分类错误率及运行时间，因此，本节也是通过实验在不同数据集下设置较优的Z和N*.对于不同数据集，通过实验设置的参数如表3所示.

表3 VPPMDT算法参数设置Table 3 Parameter setting of VPPMDT

3.3 本文算法与MDT算法的比较

本节将本文提出的两种算法模型EPPMDT和VPPMDT分别与文献[21]中的MDT算法进行分类性能及运行时间的比较.MDT算法的实验结果来自于文献[21].

本文提出的EPPMDT算法3种模型的分类性能及运行时间的实验结果见表4和表5.由表4和表5可知，EPPMDT_LIB算法和EPPMDT_SVM(linear)算法在相同数据集下的分类错误率及运行时间均相似，因为其在可辨识结点上使用的均为线性分类器，但EPPMDT_LIB算法在运行时间上还是要比EPPMDT_SVM(linear)算法快，因为LIBLINEAR模型主要还是面向于大规模数据集的，分类速度会更快一些.另外，当数据集规模相对较大时，如数据集Credit Card Cliet、Magic Gamma Telescope，EPPMDT算法提速更为明显.

表4 不同算法下分类性能比较结果Table 4 Comparison results of classification performance under different algorithms

表5 不同算法下运行时间比较结果Table 5 Comparison results of running time under different algorithms

为更加直观地解释实验结果，图3给出EPPMDT算法与MDT算法采用3种不同分类器时分类错误率的大小关系比较.其中，黑点表示所用的9个数据集，横坐标代表MDT算法的错误率，纵坐标代表EPPMDT算法的错误率.对角线上的黑点表示两种算法错误率一致，在对角线上方的黑点表示在此数据集上EPPMDT算法错误率高于MDT算法错误率，对角线下方的黑点代表在此数据集上EPPMDT算法错误率低于MDT算法错误率.黑点到对角线的垂直距离越大，表示在此数据集上算法的分类错误率越大.由图3可知，当采用LIBLINEAR模型时，在6个数据集上EPPMDT的错误率低于/相当MDT算法；当采用SVM(linear)模型时，在7个数据集上EPPMDT算法的错误率低于/相当MDT算法；当采用SVM(rbf)模型时，在8个数据集上EPPMDT算法的错误率低于/相当MDT算法.对于LIBLINEAR模型，EPPMDT算法只在2个数据集上的错误率略高于MDT算法；对于SVM(linear)模型，EPPMDT算法只在1个数据集上的错误率略高于MDT算法.特别地，在Image数据集上EPPMDT_SVM(rbf)算法的分类错误率比MDT_SVM(rbf)算法降低了近13倍.

图4中是采用3种不同分类器时EPPMDT算法与MDT算法相比运行时间加速的结果.由图4可以看出，EPPMDT相关算法在绝大部分数据集上相较MDT算法均有提升，且在部分数据集(Madelon、Spambase、Credit Card Cliet)上加速效果明显，特别地，在Spambase数据集上EPPMDT_SVM(rbf)算法比MDT_SVM(rbf)算法运行时间快了近24倍.

图3 EPPMDT与MDT分类错误率比较Fig.3 Comparison of classification error rate forEPPMDT and MDT

图4 EPPMDT对MDT的加速结果Fig.4 Accelerating results of EPPMDT on MDT

综上，EPPMDT算法可以在保证与MDT算法分类错误率相差不大或更低的条件下，使得分类效率得到有效提升.

对于VPPMDP模型，由表4和表5可知，VPPMDT_LIB算法和VPPMDT_SVM(linear)算法因在可辨识结点上均使用了线性分类器从而使得在相同数据集下的分类错误率及运行时间基本相似.类似地，为更加直观地解释实验结果，图5给出VPPMDT算法与MDT算法采用3种不同分类器时分类错误率的大小关系比较.同样，黑点表示所用的9个数据集，横坐标代表MDT算法的错误率，纵坐标代表VPPMDT算法的错误率.对角线上的黑点表示两种算法错误率一致，在对角线上方的黑点表示在此数据集上VPPMDT算法错误率高于MDT算法错误率，对角线下方的黑点代表在此数据集上VPPMDT算法错误率低于MDT算法错误率.由图5可知，当采用LIBLINEAR模型时，在7个数据集上VPPMDT算法的错误率低于/相当MDT算法；当采用SVM(linear)模型时，在7个数据集上VPPMDT算法的错误率低于/相当MDT算法；当采用SVM(rbf)模型时，在8个数据集上VPPMDT算法的错误率低于/相当MDT算法.另外， 对于LIBLINEAR和SVM(linear)模型VPPMDT算法只在2个数据集上的错误率略高于MDT算法；对于SVM(rbf)模型，VPPMDT算法只在1个数据集的错误率略高于MDT算法.特别地，在Image数据集下VPPMDT_SVM(rbf)算法的分类错误率比MDT_SVM(rbf)算法降低了近8倍.

图5 VPPMDT与MDT分类错误率比较Fig.5 Comparison of classification error rate forVPPMDT and MDT

图6中是采用3种不同分类器时VPPMDT算法与MDT算法相比运行时间加速的结果.由图6可以看出，除采用SVM(linear)模型时在Germen数据集上VPPMDT算法的运行时间高于MDT算法，VPPMDT相关算法在其它数据集上相较MDT算法均有提升，且在5个数据集上加速效果明显(Madelon、Spambase、Image、Credit Card Cliet、Magic Gamma Telescope)，特别在Credit Card Cliet数据集上，VPPMDT_SVM(rbf)算法比MDT_SVM(rbf)算法运行时间快了近10倍.

图6 VPPMDT对MDT的加速结果Fig.6 Accelerating results of VPPMDT on MDT

综上，VPPMDT算法可以在保证与MDT算法分类错误率相差不大或更低的条件下，分类效率不同程度得到有效提升.

3.4 EPPMDT算法与VPPMDT算法结果比较

由3.3节实验可知，本文提出的EPPMDT算法与VPPMDT算法，在保证与MDT算法分类错误率相差不大或更低的条件下，分类时间均得到了大幅度降低.图7是EPPMDT与VPPMDT分类性能的比较，从图中可以看出，两种算法在大部分数据集上的性能也大体相同.通过实验可以看出，EPPMDT算法更适用于每一特征维度上取值分布较为均匀，特征值差异较小的数据集，比如在Madelon数据集上EPPMDT算法的分类性能比VPPMDT算法要好.当数据集中所有样本每一特征维度上取值分布波动较大时，特征取值差异较大，如Credit Card Cliet数据集，这时VPPMDT算法分类性能要比EPPMDT算法好.

3.5 算法抗过拟合性分析

在传统决策树算法中，过拟合现象一直都是普遍存在的一个问题.由于决策树过度生长，导致叶节点样本基本都是“纯”的，虽然对于训练集分类效果很好但在测试集上的分类效果并不理想.本文提出的EPPMDT算法及VPPMDT算法，在区间划分的过程和生成一颗不完全决策树的终止条件时考虑了这一问题，因而算法会在一定程度上避免过拟合现象的发生.

一般训练数据越多训练出的模型越复杂，后期出现过拟合的可能性越大.本节实验通过对比EPPMDT算法、VPPMDT算法和传统决策树算法DT在不同规模训练集下的训练误差和测试误差，进一步分析本文提出算法的抗过拟合能力.训练集大小设定为初始训练集的10%到100%，各算法均在最优参数下运行.

图7 EPPMDT与VPPMDT分类错误率比较Fig.7 Comparison of classification error rate for EPPMDT and VPPMDT

因为在所使用的实验数据集上可以得出类似结论，所以本节以Credit Card Cliet数据集为例，比较几种算法的抗过拟合性能.图8给出了不同训练集规模下，几种比较算法的训练误差和测试误差比较.从图中可以看出，两种误差相差最大的是DT算法，EPPMDT相关算法的训练误差及测试误差相差相对较小，EPPMDT_SVM(linear)算法表现最好，其次为EPPMDT_LIB，EPPMDT_SVM(rbf)算法虽然表现不如以上两种模型，但远好于DT算法，且测试误差与以上两种算法相差不多.总体来看，EPPMDT算法在基本保证分类错误率的基础上，均有一定的抗过拟合的能力.

图8 Credit Card Cliet数据集上EPPMDT和DT抗过拟合性能比较Fig.8 Anti-overfitting performance comparison of EPPMDT and DT on Credit Card Cliet dataset

图9为在Credit Card Cliet数据集上，VPPMDT相关算法与DT算法抗过拟合性能的比较.结合图8来看，VPPMDT相关算法的抗过拟合能力比EPPMDT相关算法要更好一些，在VPPMDT相关算法中，抗过拟合能力最强的是VPPMDT_SVM(linear)算法， VPPMDT_LIB算法在训练集规模小于30%时，训练误差和测试误差较大，但训练集规模大于30%后，性能很稳定，与VPPMDT_SVM(linear)算法相差不大.类似地，VPPMDT_SVM(rbf)算法的训练误差和测试误差虽然相差较多，但其测试误差与上述两种模型相差不多，比DT算法要好得多.另外，模型的抗过拟合能力与可辨识结点使用的简单分类器有关，本文实验中，无论是EPPMDT还是VPPMDT，采用SVM(linear)作为分类器性能最好，而且更为稳定.

图9 Credit Card Cliet数据集上VPPMDT和DT抗过拟合性能比较Fig.9 Anti-overfitting performance comparison of VPPMDT and DT on Credit Card Cliet dataset

4 结 语

本文提出两种面向不同类型特征值分布的特征值区间划分方法EPPMDT和VPPMDT，以加速决策树的构建过程.与MDT算法相比，本文提出的两种算法可以保证在分类错误率相当或更低的前提下加速构建决策树.另外，本文提出的算法抗过拟合能力表现良好，性能也比较稳定.未来将会重点考虑分布情况比较复杂的数据集，研究更加快速有效的决策树分类算法.