2020, Vol. 41
2. 大连东软信息学院 网络安全与计算技术重点实验室，辽宁 大连 116023
2. Key Laboratory of Network Security and Computing Technology, Dalian Neusoft University of Information, Dalian 116023, China
决策树是一种常见的归纳式学习方法，可用于分类和回归问题.与其他机器学习模型相比，决策树具有泛化错误率低、可解释性强、参数少、生成速度快、能够应对冗余属性以及具有相当不错的抗噪能力等优点.虽然决策树算法出现比较早，但至今仍然是研究热点之一[1-2]，并在知识发现、模式识别等领域有着广泛的应用[3-4].
在分类问题中，用于预测的属性可能分属于不同的数据类型，例如，实数型、整型、布尔型、枚举型、字符串型等.按照其是否存在有序性，这些属性可归为数值型属性和分类型属性两个大类.像“身高”、“年龄”一样的属性可采用实数或整数表示，属于数值型属性.像“学生专业”、“兴趣爱好”等属性，虽然可以使用整数枚举或字符串等表示，但由于其属性值之间的无序性，这些属性属于分类型属性.特别地，布尔型的属性既可视为数值型又可以视为分类型.
经典的决策树算法，例如C4.5[5]，属于单变量决策树.算法划分一个结点时，采用穷举的方式搜索能够使当前结点不纯度下降最大的属性.如果被选中的是分类型属性，当前结点按照分类型属性的属性值个数分成多个子结点，当前结点中的样本依据其属性值进入相应子结点.如果被选中的是数值型属性，还需要搜索一个合适的划分点进行2路划分，当前结点中每个样本按照式(1)划分到左右两个子结点之中.
|
(1) |
式中：xl表示待划分样本在属性Al上的取值；θl为划分点.在这种划分方式下，数值属性空间中的划分超平面与坐标轴平行.为此，单变量决策树也称轴平行决策树.
另一经典单变量决策树算法CART[6]生成二叉树，主要为数值型数据的分类和回归问题而设计.当面对具备三个或以上属性值的分类型属性时，CART算法需要依据GINI指数下降程度，将多个属性值聚合为两组.甚至有些机器学习框架中提供的CART组件根本不支持分类型属性.
与单变量决策树相对应的是多变量决策树，这些决策树在划分结点时需要联合多个预测属性.如果联合多个预测属性的方式是线性组合，结点中的样本将依据式(2)划分到左右两个子结点之中.
|
(2) |
式中，al和p分别表示第l个属性的系数和预测属性的个数.在确定了连同θ在内的p+1个系数后，就唯一确定了划分超平面，这个超平面不一定平行于某个坐标轴.因此，这种多变量决策树也称为斜决策树.由于斜划分的备选超平面范围远远大于轴平行划分，因此，普遍认为，面对同样的数据集合，斜划分往往能够产生更小的决策树，从而得到更好的泛化性能，但需要付出较大的计算代价.
在近几十年中大量的斜划分方法被提出.CART-LC[6]是CART的斜划分版本，它采用爬山法，随机扰动各个属性在空间中的系数，以确定分割超平面.SADT[7]使用模拟退火算法搜索超平面，以避免陷入局部最优解.OC1[8]结合了CART-LC和SADT的思想.FDT[9]是使用线性判别分析方法构建的斜决策树，受FDA(Fisher ’s discriminant analysis)方法限制，FDT仅能应用于二分类问题.在文献[10]中，作者分别尝试DFA、稀疏线性判别分析以及岭回归三种方法确定结点划分的超平面.文献[11]中的HHCART，首先求得原始数据的特征向量，然后将数据映射至新的坐标空间，最后在新空间中搜索最佳轴平行划分超平面(相当于原始空间的斜超平面).文献[12]中的分类器结合了神经网络和决策森林，其中决策森林中的树采用MPSVM方法产生斜划分超平面.
在以上回顾的多变量决策树算法中，所采用的方法均不支持分类型属性.这使得处理带有分类型属性的数据时，要通过CRIMCOORD[13]，OneHot Encoder等方法将分类型属性转换为一个或多个数值型属性.这种转换可能为分类问题带来新的偏差，从而降低模型的泛化能力.
为解决分类型属性之间以及分类型属性与数值型属性之间无法联合在一起进行决策树结点划分的问题，本文提出一种基于距离尺度的、加权聚类的结点划分方法.通过定义样本集合在分类型属性上的中心以及样本到中心的距离，能够使分类型属性像数值型属性一样参与聚类过程.实验结果表明，该划分方法产生的决策树在分类型数据以及混合型数据上，均具备很好的泛化能力.
1 相关算法本文提出的算法需要使用Relief-F算法为属性加权，使用改进后的k-means算法划分结点.
1.1 Relief-F算法Relief-F算法是著名的特征(属性)选择算法Relief在多分类问题上的改进，算法根据各个属性与类别的相关性赋予每个属性不同的权重.计算属性A的权重时，从训练集中随机选择一个样本R，然后从和R同类的样本中寻找最近邻样本H，称为猜中近邻，从和R不同类的样本中寻找最近邻样本M，称为猜错近邻.如果R和H在属性A上的距离小于R和M的距离，则说明该属性对区分同类和不同类的最近邻是有益的，应该增加该属性的权重；反之，说明该属性对区分同类和不同类的最近邻起负面作用，应该降低该属性的权重.
Relief-F算法需要进行m次抽样，为每个抽取的样本，在每个类中寻找knn个最近邻，按照公式(3)计算属性A的权重:
|
(3) |
式中:p(C)表示类别C样本在全体样本中占的比例; Mj(C)表示类别C中与R距离最近的第j个邻居; diff(A, R1, R2)表示样本R1和R2在属性A上的距离，该距离通过式(4)计算得出.在寻找最近邻和计算权重的步骤中都需要使用这个距离.
|
(4) |
k-means算法是一种基于样本到原型距离评价尺度的聚类算法，其思想为:设p个数值属性的样本集D包含n个样本，需要被聚成k簇C1, C2, …，Ck，首先随机选择一些样本作为初始的k个簇的中心μ1, μ2, …，μk；然后对于每个样本xi，使用式(5)计算该样本的簇标签:
|
(5) |
式中，‖xi- μj‖为欧氏距离.所有样本得到簇标签后，使用式(6)更新每个簇中心:
|
(6) |
重复计算式(5)和式(6)，直到达到预设的循环次数或者式(7)表示的平方误差收敛至局部最优解.
|
(7) |
k-means算法仅能应用在数值属性数据集，文献[14]中的k-modes和k-prototypes算法分别是k-means算法在分类型属性数据集和混合型数据集上的变体.k-modes处理分类型属性数据集时，每个簇的中心由相应簇内样本在分类属性上的众数来表示，计算样本与簇中心在某个分类型属性上的距离时，使用公式(4)相应的部分.k-prototypes处理混合型属性数据集时，相当于使用k-means算法中的方式处理数值属性子集，使用k-modes算法中的方式处理分类型属性子集.样本xi与簇心μj的距离dis(xi, μj)采用公式(8)计算:
|
(8) |
式中:dis_n(xi, μj)和dis_c(xi, μj)分别代表数值属性子集和分类属性子集的距离; γ是一个0到1之间的实数，用于调整公式中两项的占比.
2 本文算法(CMDT) 2.1 加权聚类划分方法本文提出的结点划分方法不仅要联合多个变量，而且要对结点进行多路划分，这种多路划分可以看作是多次2路划分的组合.本文采用聚类算法k-means作为基本的划分方法.这样做是由于以下四个方面的原因:其一，多路划分生成的树模型较浅，容易被解释；其二，直接面向k分类问题使用k路划分，不必纠结于多分类问题到二分类问题的转换；其三，由于属性空间中距离相近的点(样本)有很大的几率属于同一类别，使得在不使用穷尽搜索的情况下，仍能使得结点划分后不纯度得到很大的下降；其四，k-means算法简单高效，使得结点划分的速度接近轴平行划分方法，而明显优于大部分斜划分方法.
简单地应用k-means算法进行结点划分也存在一些问题，毕竟k-means算法是一种无监督学习算法，它不会考虑分类问题中各个预测属性与分类目标属性的相关性.在计算样本到簇中心距离时，平等地看待全部预测属性，即使聚类结果在某个聚类效果评价指标上得到了较高的分数(例如式(7)收敛到了最小值)，但这不等于得到了一个好的结点划分结果.特别是在面对存在大量不相关属性的数据集时，平等看待全部预测属性的做法，会减弱“样本到簇心距离”与“分类目标属性”的相关性，进而产生与目标偏离的结点划分结果，最终导致生成的决策树泛化能力差、结构复杂(结点多).解决这一问题的一个方法就是对属性加权.如果能够给予与分类目标强相关的预测属性较大的权重，放大该属性对距离的贡献，反之，则给予较小的权重，减小弱相关和不相关属性对距离的贡献，这样便使k-means算法的优化目标与结点划分的目标趋向一致.
为了说明属性加权对于分类问题的作用，使用数据集iris进行了简单的实验，iris数据集的150个样本来自三个类别，每个类别50个样本.直接使用k-means算法聚类，错分样本10个，具体的结果如表 1所示.
|
表 1 iris属性未加权的聚类结果 Table 1 Clustering results of unweighted iris attributes |
然后，调用Relief-F算法得到4个属性的权重，分别为0.09，0.14，0.34和0.39.k-means聚类过程中，按照式(9)计算样本与簇心的加权欧氏距离.错分样本6个，具体结果如表 2所示.
|
(9) |
|
|
表 2 iris属性加权的聚类结果 Table 2 Clustering results of weighted iris attributes |
综上，提出的结点划分方法可简单描述为属性加权和聚类两个步骤，具体流程如算法1所示.本文提出的决策树算法CMDT与大部分决策树算法一样，采用自顶向下、递归的方式生长决策树，split用于结点划分，待树停止生长后，使用悲观剪枝算法对树进行后剪枝操作，以避免过拟合现象的出现.
算法1:split
输入:当前结点的数据集合D.
输出:将D划分C1, C2, …, Ck，各簇的中心μ1，μ2，μk，以及各属性的权重w.
1.使用D中样本类别数量作为分簇的数量k.
2.将D作为输入，调用Relief-F得到w.
3.在w中找到最大权重存入变量wmax，剔除权值小于β · wmax的属性，β∈[0, 1]，默认值为0.2.
4.使用D中各类别样本的中心初始μ1，μ2，…，μk.
5.For 1 to Imax Do
6. 依照距离最近原则划分样本，形成C1, C2, …, Ck.
7. 重新计算μ1，μ2, …, μk.
8. If各簇中心μ1，μ2, …，μk与前一轮迭代时无明显变化Then Break For
9.End For
10. Return C1, C2, …, Ck，μ1，μ2, …，μk以及w.
2.2 分类属性2.1节所阐述的结点划分方法可以直接应用在数值属性上.对于分类型属性来说，在属性加权部分仍然可以使用Relief-F算法，在聚类步骤需要定义簇心的表示方法以及样本到簇心距离的计算方法.1.2节提及的k-modes算法满足这样的要求.k-modes算法是k-means在分类型属性的变体，它使用分类型属性的众数mode代替数值型属性的均值mean，计算样本到簇中心距离时，分类属性上采用相同值取0，不同值取1的方式.然而，这种方式计算出的距离不够精确, 并且当某个属性出现多个众数时, 不同的众数选择可能得到完全相反的结论[15].
下面使用一个例子来说明这个问题:假设由A和B两个分类型属性描述的两个簇C1和C2都包含10个样本，样本的统计分布如表 3所示.
|
|
表 3 属性值分布 Table 3 Attribute values distribution |
簇C1中，90 %的样本在A上的值为a1，而C2中，只有40 %的样本在A上的值为a1，a1在两个簇中都是众数，这使得在判断某个样本距离C1和C2谁更近时，属性A没有任何作用.属性B在C1和C2中分别存在2个众数.假设存在样本q =(a1, b1)，如果为C1选择簇心μ1=(a1, b1)，为C2选择簇心μ2=(a1, b3)，得到q与μ1的距离为0，q与μ2的距离为1，得到q属于C1的结论；如果为C1选择簇心μ1=(a1, b2)，为C2选择簇心μ2=(a1, b1)，得到q与μ1的距离为1，q与μ2的距离为0，则得到q属于C2的结论.
针对使用各个属性的众数表示簇中心带来的计算距离不够精确、存在二义性等问题，受到文献[15]中k-summary算法的启发，本文使用每个分类属性值的概率分布估计来定义簇心的表示方法及样本到簇心距离的计算方法，供结点划分时使用.
定义1 设包含p个分类型属性，n个样本的数据集D分为k簇，簇Cj中第l个属性Al有d个不同取值ω1, ω2, …，ωd，令Cj, xl表示第l个属性上取值为xl的样本子集，xl∈{ω1, ω2, …, ωd}, 条件概率被估计为
|
(10) |
定义Sj, l为Cj中关于Al的各个属性值的汇总:
|
(11) |
定义2 使用Sj, l代替众数，定义簇Cj的中心μj为由各个属性的Sj, l组成的向量:
|
(12) |
定义3 定义diff(Al, ω, Sj, l)为属性值ω与Sj, l的距离:
|
(13) |
定义4 在已知属性权重向量w的情况下，样本xi与簇心μj的加权距离为
|
(14) |
在之前的例子中，假设所有属性的权重均为1，依据式(14)，样本q=(a1, b1)与表 3中C1和C2中心距离分别为0.7=0.1+0.6和1.2=0.6+0.6，说明q与簇C1更接近，这符合人们的直观感觉.
对于只包括分类型属性的数据集，仅仅是将split的第4, 7步骤中计算簇心的公式由计算均值改为计算式(12)，第6步骤中计算样本到簇心距离的计算公式由式(14)代替式(9).对于混合类型的数据集，簇心向量由两部分构成：一部分是数值属性的均值；一部分如式(12)所示的汇总信息.计算样本到簇心距离时，使用加权欧氏距离计算数值属性部分dis_n，使用式(14)计算分类属性部分dis_c，再使用式(8)将两部分结合.确定式(8)系数γ时，以GINI指数作为评价指标，在{0.1, 0.2, …, 0.9}中选择使GINI指数下降最大的值.
3 实验结果与分析本节将通过两部分实验来验证提出算法.第一部分实验用于说明在带有分类型属性的数据集上，属性加权、聚类以及使用属性值分布汇总代替众数的有效性；第二部分实验是与经典决策树算法比较泛化正确率和结点数量.
3.1 数据集表 4展示了实验使用的10个数据集，这些数据集源于UCI[16].其中，序号1~5为纯分类型属性数据集，6~10为混合型数据集.表 4“属性数”一列中，混合型数据集的属性数以“数值型属性数+分类型属性数”的形式给出.另外，原始数据集Abalone是29分类问题，本文将其视为3分类问题，原始类别1~8归为第1类，9和10归为第2类，其余类别归为第3类.
|
|
表 4 数据集 Table 4 Data sets |
为了验证属性加权、聚类以及特殊处理分类型属性的作用，实现了8个不同的结点划分方法产生决策树(见表 5).算法0不进行聚类，直接使用各个类别的中心作为锚点，分类型属性使用众数代替数值属性的均值作为锚点向量的分量，计算样本到锚点距离时，各个属性上的距离使用式(4)计算得出并求和；算法1与算法0的不同之处是，使用Relief-F计算每个属性的权重，删除小于最大权重1/5的属性后，样本和锚点距离使用权重向量和式(4)计算得到的距离向量的点积；算法2与算法0的区别在于加入了聚类过程，k-modes算法用于分类数据集，k-prototypes算法用于混合型数据集；算法3结合了算法1和算法2；算法4~7分别对应算法0~3，分类型属性上关于簇心和样本到簇心距离计算采用2.2节描述的方法.算法7就是本文提出的算法.实验中生成的决策树均采用最小父母数为5的预剪枝策略，并对生成的决策树使用悲观剪枝算法进行剪枝操作.实验报告的正确率为10次10折交叉验证的平均值.
|
|
表 5 对比不同划分方法的正确率 Table 5 Comparison of the accuracy for different split methods |
表 5展现了8个算法在10个数据集上的正确率，每行中最好的正确率被加粗.在10个数据集中，除了CMC和Zoo外，算法7都获得了最好的准确率，相比算法0正确率平均高出11.08 %.分别考虑3个方面的改善:算法1, 3, 5, 7比算法0, 2, 4, 6平均高出5.19 %，这是属性加权带来的改善；算法2, 3, 6, 7比算法0, 1, 4, 5平均高出4.27 %，这是聚类带来的改善；算法4~7比算法0~3平均高出1.31 %，这是样本属性值统计分布代替众数的改善.特别地，算法4相比于算法0有所下降，这说明同时联合多个分类型属性对结点进行划分时，在没有结合聚类以及属性加权的情况下，详细地统计各个类别在每个属性上属性值的样本分布反而不如简单地统计各个类别在每个属性上的众数.
3.3 与其他决策树对比为了验证提出算法的能力，选择流行机器学习工具Weka和Scikit-learn中的决策树进行对比，Weka中的J48是对C4.5的实现，Scikit-learn中的决策树模型在默认情况下是CART算法的优化.同样的10次10折交叉验证被使用，实验报告平均正确率和结点数量.
表 6展示了实验结果，最好的结果被加粗显示.正确率方面，本文算法在10个数据集上获得了77.79 %的平均正确率，分别比其他两个算法高2.93 %和0.41 %.模型结构复杂度方面，本文算法平均结点数量略小于C4.5，而远小于CART.
|
|
表 6 CMDT与C4.5和CART对比 Table 6 Comparison of CMDT, C4.5 and CART |
针对绝大部分多变量决策树只能联合数值型属性，而不能直接为带有分类型属性数据集进行分类的问题，提出一种可联合多种类型属性的多变量决策树算法.该方法使用基于距离的聚类算法划分决策树中非叶结点，快速生成决策树；通过为属性加权的方式代替经典决策树算法中使用不纯度指标进行启发搜索的过程；使用样本属性值分布统计来定义簇心表示及距离计算，使得分类型属性能以与数值型属性相似的方式参与加权聚类.实验结果表明，本文提出的算法具备比经典决策树更好的泛化正确率，以及更简洁的结构.
| [1] |
王蒙湘, 李芳芳, 于戈. 交互式数据探索框架的特征自适应技术[J]. 东北大学学报(自然科学版), 2018, 39(12): 1685-1690. (Wang Meng-xiang, Li Fang-fang, Yu Ge. Feature adaptive technology in interactive data exploration framework[J]. Journal of Northeastern University (Natural Science), 2018, 39(12): 1685-1690.) |
| [2] |
Zhou X, Yan D. Model tree pruning[J]. International Journal of Machine Learning and Cybernetics, 2019(1): 1-14. |
| [3] |
Guney S, Atasoy A. Freshness classification of horse mackerels with E-nose system using hybrid binary decision tree structure[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2020, 34(3): 1-17. |
| [4] |
Liu Z, Wang L, Li X, et al. Optimize x265 rate control:an exploration of lookahead in frame bit allocation and slice type decision[J]. IEEE Transactions on Image Processing, 2019, 28(5): 2558-2573. DOI:10.1109/TIP.2018.2887200 |
| [5] |
Quinlan J R. C4.5:programs for machine learning[J]. Machine Learning, 1994, 16(3): 235-240. |
| [6] |
Buntine W L. Learning classification trees[J]. Statistics & Computing, 1992, 2(2): 63-73. |
| [7] |
Quinlan J R.Combining instance-based and model-based learning[C]//The Tenth International Conference of Machine Learning.Amhers: Morgan Kaufmann, 1993: 27-29. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.6358
|
| [8] |
Murthy S K, Kasif S, Salzberg S. A system for induction of oblique decision trees[J]. Journal of Artificial Intelligence Research, 1996, 2(1): 1-32. |
| [9] |
López-Chau A, Cervantes J, López-García L, et al. Fisher's decision tree[J]. Expert Systems with Applications, 2013, 40(16): 6283-6291. DOI:10.1016/j.eswa.2013.05.044 |
| [10] |
Hong K S, Ooi P L, Ye C K, et al. Multivariate alternating decision trees[J]. Pattern Recognition, 2016, 50: 195-209. DOI:10.1016/j.patcog.2015.08.014 |
| [11] |
Wickramarachchi D C, Robertson B L, Reale M, et al. HHCART:an oblique decision tree[J]. Computational Statistics & Data Analysis, 2015, 96: 12-23. |
| [12] |
Katuwal R, Suganthan P N, Zhang L. An ensemble of decision trees with random vector functional link networks for multi-class classification[J]. Applied Soft Computing, 2018, 70: 1146-1153. DOI:10.1016/j.asoc.2017.09.020 |
| [13] |
Loh W Y, Shih Y S. Split selection methods for classification trees[J]. Statistica Sinica, 1999, 7(4): 815-840. |
| [14] |
Huang Z. Extensions to the k-means algorithm for clustering large data sets with categorical values[J]. Data Mining and Knowledge Discovery, 1998, 2(3): 283-304. DOI:10.1023/A:1009769707641 |
| [15] |
蒋盛益, 李庆华. 一种增强的k-means聚类算法[J]. 计算机工程与科学, 2006, 28(11): 56-59. (Jiang Sheng-yi, Li Qing-hua. An enhanced k-means clustering algorithm[J]. Computer Engineering & Science, 2006, 28(11): 56-59.) |
| [16] |
Lichman M.UCI machine learning repository[EB/OL].(2019-09-23)[2019-10-11].http://archive.ics.uci.edu/ml.
|