【决策管理】关于决策树剪枝的两点探讨

关于决策树剪枝的两点探讨

杨龙平

【摘要】数据挖掘中的决策树方法可以很好地实现对数据的分类，并根据生成的决策树模型，为决策者提供决策参考。但在创建决策树模型时，要避免两个主要

的问题：一是预防决策树过于庞大；二是防止决策树的过匹配。本文通过两

种简单的方法实现对决策树的预先剪枝。

【关键词】决策树信息增益属性剪枝

【作者简介】杨龙平，男，柳州运输职业技术学院信息工程系教师。广西柳州，545007

数据挖掘是一个利用各种分析工具在海量数据中发现模型和数据间关系的过程，使用这些模型和关系可以进行预测，它帮助决策者寻找数据间潜在的关联，发现被忽略的因素，因而被认为是解决当今时代所面临的数据爆炸而信息贫乏问题的一种有效方法。数据挖掘的方法有很多种，其中有一种方法是决策树方法。如何创建一个有效而合理的决策树，是很多专家长期以来一直探讨的问题。而充分合理地利用预先剪枝可以从很大程度上降低决策树计算的复杂度。

一、决策树概述

决策树是一个类似于流程图的树结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，而每一个树叶结点代表类或类分布。树的顶层是根结点。一颗典型的决策树结构如图1所示。内部结点用矩形表示，而树叶结点用椭圆表示。为了对未知的样本分类，样本的属性值在决策树上测

图1 决策树模型

当决策树创建时，由于数据中的噪声和孤立点，许多分枝反映的是训练集中的异常，同时对最终要拿给人看的决策树来说，在建立过程中让其生长的枝繁叶茂是没有必要的，这样既降低了树的可理解性和可用性，同时也使决策树对历史数据的依赖性增大，也就是说，这棵树对当前的样例数据可能非常准确，一旦用到新的数据时准确性急剧下降，我们称这种情况为训练过度。为了使得到的决策树所蕴涵的规则具有普遍意义，必须防止训练过度，这样也减少了训练时间，因此必须对决策树进行剪枝。剪枝是一种克服噪声的基本技术，同时它也能使决策树得到简化而变得更容易理解。

在收集到的这些毕业生数据中，并不是完美的，有些数据表中的字段并不一致，有些字段和课题的关系并不紧密，还有些数据并不准确、甚至含有噪音。由于基本的决策树构造并不考虑噪声，因此，生成的决策树完全与训练例子拟合。在有噪声情况下，完全拟合将导致过分拟合，即对训练数据的完全拟合反而使现实数据的分类预测性能下降。

剪枝有两种基本的策略：预先剪枝和后剪枝。从理论上讲，后剪枝好于预先剪枝，但计算复杂度大。

目前的决策树有很多种算法，最为常用的是ID3和C4.5算法，它们可以分别处理离散的信息和非离散的信息。

二、关于预先剪枝的两点探讨

ID3算法的基本思想是贪心算法，采用自上而下的分而治之的方法构造决策树。首先检测训练数据集的所有特征，选择信息增益最大的特征A建立决策树根节点，由该特征的不同取值建立分枝，对各分枝的实例子集递归，用该方法建立树的节点和分枝，直到某一子集中的数据都属于同一类别，或者没有特征可以在用于对数据进行分割。ID3算法总是选择具有最高信息增益(或最大熵压缩)的属性作为当前结点的测试属性。该属性使得结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。这种信息理论方法使得对一个对象分类所需的期望测试数目达到最小，并尽量确保一棵简单的(但不必是最简单的)树来刻画相关的信息。

在ID3算法中，计算信息增益时，由于信息增益存在一个内在偏置，它偏袒具有较多值的属性，太多的属性值把训练样例分割成非常小的空间。因此，这个属性可能会有非常高的信息增益，而且被选作树的根结点的决策属性，并形成一棵深度只为一级但却非常宽的树，这棵树可以理想地分类训练数据。但是这个决策树对于测试数据的分类性能可能会相当差，因为它过分地完美地分割了训练数据，不是一个好的分类器。解决此类问题最好的方法是对属性值进行分类，以减少其取值的数量。比如，某学院的专业数量有20多个，为了降低模型的复杂度，在进行数据处理时，对各专业按照其性质进行分类，可以有效地减少属性的取值，从而降低模型的复杂度。假设有表格数据如表1所示。

理想的决策树分为3种：①叶结点数最少；②叶子结点深度最小；③叶结点数最少，且叶子结点深度最小。决策树的好坏，不仅影响了分类的效率，而且影响分类的准确率。

根据信息熵的计算公式，有如下的结果： )(性别Gain =0.00005，)(专业Gain =0.025291 )(成绩Gain =0.031285，)(班干否Gain =0.003524

)(英语水平Gain =0.096703，)(计算机水平Gain =0.107777， )(综合能力Gain =0.255758，)(工资待遇Gain =0.047532

)(专业对口否Gain =0.039567，)(主观意愿

Gain =0.078395 )(行业发展Gain =0.048285

1．将信息增益值很小的属性忽略

为了减少决策树的深度和叶结点数，在计算信息熵的过程，可以将熵值很小的属性忽略。在第一次计算信息熵的时候，“性别”属性的增益值为0.00005，比最小的信息增益值0.003524还小差不多100倍，因此，在以后的计算过程中，可以不再对“性别”属性计算增益，这样一方面可以减少计算的工作量，另一方面，可以有效地防止创建一棵庞大的决策树。

2．引入替代错误率

决策树停止的条件有三个：给定结点的所有样本属于同一类；没有剩余属性可以用来进一步划分样本；分支的测试属性没有样本。但是，在计算过程中，对子树的某个分支上继续划分子集时，虽然所有的样本并不属于同一类，但是不同类别的记录数如果相差很大时，可以引入错误替代率公式：

（2－1）

其中， 表示分支的记录数， 表示该分支中多数类别的记录数， 表示训练集的记录总数。利用该公式计算的值，如果小于0.5%，则将子树转换为叶结点，从而可以预防决策树的过匹配问题。

m

n n pure '

-=

例如，有一个“主观意愿”属性作为子树的根结点，设它有两个属性值0和1，如果继续进行测试，则将0和1作为分支进行划分子集。假设对0分支划分子集时，若所有的子集并不属于同一类，如果有14个0（未就业），有1个1（成功就业），则可以通过上面的公式计算错误替代率（如果总记录数为500条），小于预定的值，因此将0分支转换为叶结点，该叶结点的类别为0。

经过实践证明，可以通过使用以上的两种相对简单的方法，将会大大减少计算的复杂度，而且可以减少决策树的复杂度，并且对决策树的预测准备度也影响很小。

参考文献

[1] 张云涛等. 数据挖掘原理与技术[M].北京：电子工业出版社，2004.4

[2] 毛国君,段立娟等. 数据挖掘原理与算法[M].北京：清华大学出版社，2005.7

[3] 陈文伟. 智能决策技术[M].北京:电子工业出版社，1998.6

[4] 王志海, 林友芳等.W.H.Inmon. 数据仓库[M]. 北京：机械工业出版社，2003.3

[5] Han Jiawei，Kamber M．数据挖掘概念与技术[M]. 范明, 盂小峰译. 北京：机械工业

出版社，2001.8

[6] Adam Drozdek．数据结构与算法（java语言版）[M]. 周翔, 王建芬等译．北京：机械

工业出版社，2003.7