基于随机化属性选择和决策树的组合分类器

马　源

(福州大学 物理与信息工程学院，福州　350108)



基于随机化属性选择和决策树的组合分类器

马源

(福州大学 物理与信息工程学院，福州350108)

摘要：针对决策树泛化能力差，容易产生过拟合问题，提出基于随机化属性选择和决策树组合分类器。首先运用随机化邻域属性约减产生多个分类较高的属性子集；其次每个属性子集作为分类回归树(CART)的输入，训练多个基分类器；最后对得到的多个分类精度结果进行投票融合的方式获得最后的分类结果。实验表明，提出的随机属性选择和决策树集成算法有效性。

关键词：过拟合；随机化；决策树；分类器；融合

0引言

经典粗糙集理论[1]是波兰华沙理工大学教授Pawlak1982年，在研究不完整和不精确知识的表达时提出的。粗糙集有以下优点：能够客观地挖掘出数据内部的消息，也就是可以找到数据的本质信息；可以将数据通过一定的原则进行提炼，得到数据的内涵信息。由于上述作用，粗糙集理论在数据挖掘中得到广泛应用，邻域粗糙集[2]是为了解决经典粗糙集便于处理数值型属性的数据集合而提出的。邻域粗糙集约减可以对样本数据集进行属性选择，选择出分类能力强的属性，达到去噪和降维的功能，从而减少分类计算复杂度，提高分类效果。

决策树[3]是一种非常适合数据挖掘的算法。相比较神经网络、贝叶斯、支持向量机等分类器，其主要优点是模型具有可解释性，容易被人们所理解，且构建速度快。同时决策树生成算法不需要附加信息，例如数据和类别分布的先验知识。然而其主要缺点是分类结果准确率不高，容易产生过拟合问题，当数据集中的属性过多，用决策树分类容易出现结构性差等问题。

目前，数据挖掘主要的研究方向由单一的方法逐渐发展成为多种方法结合。粗糙集在化简训练样本，消除冗余信息，处理大数据量的时候具有一定优势。但粗糙集分类精度不高，往往结果不太稳定。研究表明[4]粗糙集和决策树具有很高的优势互补性，因此可以将两者结合。在实际应用中，粗糙集理论结合决策树分类器发挥两者的优越性，取得了较好的效果。

针对决策树构造中存在抗噪声能力差、选择最优属性困难的问题，文献[5]提出一种基于变精度粗糙集模型的决策树构建。文献[6]提出一种邻域粗糙集快速约减算法，从中选择最大属性重要度的属性加入约减集合中，直到所有剩余属性重要度为0，并将此应用在CART分类器上验证了该约减算法的可以提高分类效果。然而实际数据中约减是种NP问题，存在多个保持原始样本数据具有区分能力的属性子集，因此为了尽可能利用不同子空间的分类能力，文献[7]提出WADF方法和文献[8]提出一种随机属性约减算法寻求多个约减。本文将邻域粗糙集随机属性选择与CART决策树相结合，设计出一种集成学习分类器。通过随机化邻域约减产生的多个约减，作为CART的输入，最后对分类结果进行加权投票的方式融合不同的结果做出决策，提高泛化能力和减少过拟合问题。从实验数据测试结果可以看出，本文提出方法的有效性。

1邻域粗糙集模型基本概念

邻域粗糙集模型不需要像经典粗糙集事先要属性离散化，它可以对数值形属性直接处理，直接用于知识约减。下面介绍邻域粗糙集模型相关概念[1]。

定理1给定实数空间Ω上的非空有限集合U={x1,x2,…xn}，对于∀xi的邻域δ定义为：δ(xi)={x|x∈U,Δ(x,xi)≤δ}，其中δ≥0，Δ(x,xi)为距离函数，表示x与xi之间的距离。常见的距离计算函数例如：曼哈顿距离函数、欧式距离函数等。

定理2假设有一邻域决策系统NDS=(U,A,D)，其中U为全部样本构成的集合，A为样本的属性子集，D为分类决策属性。决策属性D将U划分为N个等价类(x1,x2,…xN)，∀B∈A，D关于B的上下近似定义为：

定理3决策属性D对于条件属性B的依赖度定义为：

其中PosB(D)为决策邻域决策系统的下近似。

定理4属性重要度定义为：条件属性对决策属性的影响程度，若属性a∈B，那么条件属性a对于决策属性D的重要度公式为：

Sig(a,B,D)=γB(D)-γB-{a}(D)

定理5对于决策系统NDS=(U,A,D)，B∈A，a∈B，如果满足：

(1)γB(D)=γA(D)

(2)∀a∈B:γB-{a}(D)<γB(D)

则称B是一个属性约减。

2CART分类算法

2.1CART分类算法简介

CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的方法，假设决策树是二叉树，内部节点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。CART主要由决策树生成和决策树剪枝组成[9]。

2.2CART决策树生成

CART决策树的生成就是递归地构建二叉决策树的过程。构建回归树和分类树采用不同的准则，对回归树用平方误差最小准则，对分类树用基尼系数最小化准则，进行特征选择，生成二叉树。由于篇幅有限，只介绍分类树的生成。

分类树用基尼指数选择最优特征，基尼系数计算公式为：

其中，K为样本类的个数，pk为样本点属于第k类的概率。

假设训练数据集为D，根据训练数据集，从根节点开始，递归地对每个节点进行以下操作，构建二叉决策树：

1)计算现有特征对该数据集的基尼系数，对于每个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或“否”将D分割成D1和D2两部分，计算A=a的基尼系数。

2)在所有可能的特征A以及它们所有可能的切分点a中，选择基尼系数最小的特征极其对应的切分点作为最有特征与最优切分点。依最优特征与最优切分点，从现节点生成两个子节点，将训练数据集依特征分配到两个子节点中去。

3)对2个子节点递归地调用1)和2)，直至满足停止条件。

4)生成CART决策树。

算法停止计算的条件是节点中的样本个数小于预定阀值，或样本集的基尼系数小于预定阀值，或者没有更多特征。

2.3CART决策树剪枝

当决策树生成时，需要从完全生长的决策树的底端剪去一些子树，目的是为了使决策树变小，模型变简单，减少过拟合问题，从而能够对未知数据有更准确的预测。CART剪枝算法首先从生成算法产生的决策树T0底端开始不断剪枝，知道T0的根节点，形成一个子树序列{T0,T1,…,Tn}；然后通过交叉验证在独立的验证数据集上对子树序列进行测试，从而选择最优子树。CART剪枝算法如下：

1)设k=0，T=T0。

2)设a=+∞。

4)自上而下地访问内部节点t，如果有g(t)=a，进行剪枝，并对叶节点t以多数表决法决定其类，得到树T。

5)设k=k+1，ak=a，Tk=T。

6)如果T不是由根节点单独构成的树，则回到步骤4)

7)采用交叉验证法在子树序列T0,T1,…,Tn中选取最优子树Ta。

3基于随机属性选择和决策树的集成学习分类器

3.1基本思想

本文提出的集成学习分类器结构图如图1所示。给定一个邻域决策系统NDS=(U,A,D)，多次运用邻域随机化属性约减算法可以得到多个属性约简子集(a1,a2,…an)，每个约减子集作为CART分类器的输入，采用十字交叉验证得到一组决策，最后对每组决策通过加权投票的方式最终可以得到每个样本的类标号。

图1　结构图Fig.1　Structure chart

3.2算法描述

本文提出的一种随机属性选择和CART的集成学习分类器，利用邻域随机化属性产生多个约减的属性子集，从而产生对样本数据进行特征选择的多个子集，具体过程如算法1所示，然后利用CART进行分类学习。本文采用了10折交叉验证方法，在对每一个子集进行分类学习时，将该子集划分为10等份，利用其中的9份作为训练集用于构建一个CART分类器，剩余的1份作为测试集进行测试。在10折交叉验证之后，该子集将会产生一个决策输出，同理对于剩下的子集采用同种方法，每个子集产生的决策输出最后通过投票融合的方法最终决策输出。具体算法如算法2。

算法1(基于邻域粗糙集随机化属性约减)：

输入：NDS=(U,A,D)，参数δ和随机数N

输出：约减reduce={a1,a2,…an}

1)属性约减初始化reduce为空集

2)对任意的ai∈A-reduce计算属性ai的重要度SIG(ai,reduce,D)

3)选择ak，ak为属性集{A-reduce}中重要度SIG(ai,reduce,D)前F个最大中的一个

4)如果SIG(ai,reduce,D)>0，则reduce∪ak→reduce

5)回到第二步

6)否则返回约减reduce，约减完成。

算法2(基于邻域粗糙集随机化属性约减和决策树的集成学习)：

输入：原始数据集通过约减的属性集{a1,a2,…an}

输出：验证集上的分类正确率

步骤：

1)初始化

①读入原始数据集{a1,a2,…an}

2)For(iin 1∶10)

①将原始数据集{a1,a2,…an}中的每个子集划分成10等份

②在训练集上运行CART创建分类器

③在测试集上执行分类预测

3)对于每个子集的预测采用投票，输出分类正确率

3.3时间复杂度分析

邻域随机属性约减在选定随机数F后，每次运行即可以得到1个随机化约减。这个算法的时间复杂度为(2n-k)(k+1)×(k+1)×mlogm/2，其中n和m分别为样本和特征的数据，k为约减中属性的个数。约减后的各个属性子集作为CART分类器的输入，设约减后的数据集维数为m*，训练样本个数为n*。在构建CART树的过程中，训练1个不进行剪枝的树，训练每一个基分类器的计算时间小于O(m*n*(logn*)2)，对于k个基分类器的时间复杂度近似为O(km*n*(logn*)2)，本实验采用10折交叉验证，需运行CART算法10次，最终k个基分类器的时间复杂度约为10×O(km*n*(logn*)2)。

在进行实验时，我们设置运行随机属性约减算法10次，这样将会产生10个约减结果，然后利用CART分类器学习。实验表明，提出的集成学习运行时间上是可以接受的，算法具有较好的扩展性。

4实验结果及分析

4.1实验数据与方法

从UCI数据库中下载4个数据集，分别是zoo、heart 、wdbc、soy、wine、wpbc数据集描述如表1所示。算法采用matlab2014a实现

表1　数据描述

4.2实验结果分析

在分类学习之前对数据进行了预处理，首先剔除缺省值和无关属性，然后归一化处理，使得每个属性的取值在[0,1]之间。本文提出的设计方法分类精度如表2所示。

表2　提出方法的分类精度

为了进一步说明本设计的优越性，比较本文提出的设计方法和基于快速约减的贪心算法的CART、使用原始特征的CART的分类精度，比较结果如图2所示。3种分类方法在6个不同数据集分类准确度的平均值柱状图如图3所示。

图2　3种分类方法比较Fig.2　Comparison of classification among three methods

图3　3种分类方法平均值比较Fig.3　Comparison of average classification among three methods

从实验结果可以发现提出基于随机属性选择和决策树的组合分类器可以较大的提高CART分类器的准确度，准确度优于基于快速约减的贪心算法的CART分类器。从绘出的分类曲线可以看出，快速贪心约减算法并不完全可以使CART分类效果提高，在有些数据集上分类效果差于直接使用原始数据集的CART。从平均值柱状图可以看出，提出的方法在6个数据集的平均准确度相比较直接使用原始数据集的CART提高了4.93%，比基于快速约减算法的CART提高了4.95%。

5结语

目前CART决策树分类稳定性差，易产生过拟合，分类精度有待提高。本文提出的基于随机属性选择和决策树的组合分类器，首先利用邻域粗糙集的随机属性选择方法，得到多个保持原始样本数据具有区分能力的属性子集，在不同属性集上分别构建CART决策树，最后通过加权融合的方法得到判决。通过实验结果表明可以较大改善CART分类器准确度不高和过拟合问题，以后将使用此方法应用到实际数据中。

参考文献：

[1] 杨启贤.粗糙集及其应用简介[J].贵州师范大学学报(自然科学版),1988,6(2):4-9.

[2] HU Q,YU D,XIE Z.Neighborhood classifiers[J]. Expert Systems with Applications,2008,34(2):866-876.

[3] PONKIYA P.A Review on Tree Based Incremental Classification[J].International Journal of Computer Science and Information Technologies,2014,5(1):306-309.

[4] PAL P,MOTWANI D.The Based on Rough Set Theory Development of Decision Tree after Redundant Dimensional Reduction[C]// Advanced Computing & Communication Technologies (ACCT), 2015 Fifth International Conference on IEEE, 2015:278-282.

[5] WANG F.Improved Algorithm of Decision Trees Construction Based on Variable Precision Rough Set[J].Computer & Digital Engineering, 2013，41(3):337-339.

[6] 胡清华,于达仁,谢宗霞.基于邻域粒化和粗糙逼近的数值属性约简[J].软件学报,2008,19(3):640-64.

[7] WU Q X,BELL D,MCGINNITY M.Multiknowledge for decision making[J].Knowledge & Information Systems, 2005,7(2):246-266.

[8] 朱鹏飞,胡清华,于达仁.基于随机化属性选择和邻域覆盖约简的集成学习[J].电子学报,2012,40(2):273-279.

[9] 李航.统计学习方法[M].北京:清华大学出版社,2012:67-73.

文章编号：1004—5570(2016)01-0098-05

收稿日期：2015-08-12

作者简介：马源(1991-)，男，硕士研究生，研究方向：数据挖掘，图像处理与通信，E-mail：251394667@qq.com.

中图分类号：TP391.4

文献标识码：A

Ensemble classifier based on randomized attribute selection and decision tree

MA Yuan

(Institute of Physics and Information Engineering,Fuzhou University,Fuzhou,Fujian 350108,China)

Abstract:Aiming at the problems of poor generalization ability and easy to overfitting in decision tree.We introduce an ensemble classifier based on randomized attribute selection and combination of decision tree.Firstly,multiple subsets with higher accuracy are produced by use of randomization adjacent attribute reduction;Secondly each attribute subset as classification and regression tree’s input;Finally the final classification result is obtained by multiple classification results fusion.The experiment result shows that the proposed random attribute selection and decision tree integration algorithm is effective.

Key words:overfitting；randomization;decision tree;classifier; fusion