决策树剪枝研究

李泓波+彭三城+白劲波+杨高明+黄少伟

DOI：10.16644/j.cnki.cn33-1094/tp.2016.02.001

摘  要： 决策树技术是一种重要的机器学习技术，现已广泛应用于工业、商业、金融、医疗卫生等多个学科和领域，并成为学术热点问题。在众多的应用中，存在由于使用剪枝算法简化决策树而导致系统性能下降的情况。针对滥用剪枝问题，通过对决策树技术的研究，阐述剪枝与过拟合现象的关系，并从奥卡姆剃刀原理、没有免费午餐原理、人类本能、孤立点分析等方面对剪枝的合理性和必要性展开讨论，提出了慎用剪枝的主张以及免剪枝措施。

关键词： 决策树; 机器学习; 过拟合; 剪枝; 免剪枝措施

中图分类号：TP391          文献标志码：A     文章编号：1006-8228（2016）02-01-03

Study on decision tree pruning

Li Hongbo1， Peng Sancheng1， Bai Jinbo2， Yang Gaoming3， Huang Shaowei1

（1. School of Computer/School of Software， Zhaoqing University， Zhaoqing， Guangdong 526161， China; 2. College of Economics & Management， Zhaoqing University; 3. College of Computer Science and Engineering， Anhui University of Science & Technology）

Abstract： Decision tree technology is an important machine learning technology， has been widely used in industrial， commercial， financial， medical and health care， and other disciplines and fields， and become the academic hot issue. There are decision tree performance degradation phenomena existing in many applications because of using of pruning algorithms to simplify the decision tree. In view of the problem of abusing pruning， through a brief introduction to decision tree technology， explaining the relationship between pruning and over fitting phenomenon， and discussing on the rationality and necessity of pruning from several aspect， such as Occam's razor theorem， no free lunch theorem， the human instinct， outlier analysis， etc.， the careful pruning claims and avoiding pruning measures are put forward.

Key words： decision tree; machine learning; over fitting; pruning; avoiding pruning measure

0 引言

决策树是一种重要的非参数机器学习技术，其本质为归纳学习，主要用于分类、预测和规则获取等[1-9]，现已广泛应用于工业、商业、金融、医疗卫生等多个学科和领域[10-13]。一般认为，决策树应用大致分为数据预处理、决策树训练和剪枝、决策树检验和应用四大步骤[9]。从目前研究看，在众多实际应用中都采用了剪枝算法对决策树进行简化处理。然而，在有些情况下，剪枝处理会导致决策树性能的下降。

1 过拟合现象与剪枝

1.1 过拟合

在训练决策树的过程中，可能会现一种称为过拟合（也称为过渡拟合或过适应）的现象。以下简述过拟合的相关概念，并通过介绍这些概念的引入阐释过拟合现象。

⑴ 训练误差：是指在训练样本集上决策树误分类所占的比例。

⑵ 泛化误差：经过训练样本集训练过的决策树在进行分类预测样本集上的期望误差。

⑶ 噪声：对于噪声的定义尚未统一，为对其有多角度的观察和更加开放的目光进行审视，下面给出两个经典的定义。一个定义来自著名模式识别专家Duda;另一个来自决策树技术专家Quinlan。Duda给出的定义是：噪声是一个非常广义的概念，如果一个感知到的模式属性（值）并非来自真正模式的模型，而是来自环境中的某种随机性或者是传感器的性能缺憾，那么就是噪声[14]。Quinlan的定义是：训练样本中的错误就是噪声;它包含两方面，一是属性值取错，二是分类类别取错。概括地说，Duda和Quinlan都认为，噪声产生的原因是训练样本集合存在错误数值，这些数值跳出了其正常的取值范围。

⑷ 过拟合：如果训练误差低而泛化误差高，则称为过拟合。出现过拟合现象主要有两个原因：一是训练样本数量少，二是噪声的存在。

1.2 剪枝

⑴ 剪枝的作用

人们发现，在有些时候，一棵经过训练的决策树过于“繁茂”，知识过多，或者说得到的规则集合过大。经过剪枝，可以得到一棵相对简洁的决策树，较少的规则使得在进行分类预测时，决策树效率更高。同时，剪枝也可以减少过拟合现象的发生。

⑵ 先剪枝

所谓的先剪枝是指在决策树的构造过程中，当满足设定条件时，以当前分枝的样例子集中出现次数最多的类别值作为当前分枝的节点标记名，而提前停止决策树的构造。

⑶ 后剪枝

所谓的后剪枝是指在决策构造完成之后，删去某些满足某种条件的结点及其子孙结点和分枝，并以该结点分枝的样例子集中出现次数最多的类别值作为当前分枝的节点标记名。

图1为一棵剪枝前的决策树，图2为对前图所示决策树剪枝后的情形。

2 决策树剪枝讨论

一般说来，经训练获得一棵决策树后，考虑到简洁和效率因素，并为避免过拟合现象，往往要对其进行剪枝。但是，剪枝是否总是合理或必要则是个问题。

2.1 奥卡姆剃刀原理与剪枝

奥卡姆剃刀原理由14世纪哲学家奥卡姆提出，如今已经广泛应用于哲学、管理学、社会科学、自然科学等多个领域，取得了辉煌成就。奥卡姆剃刀原理的哲学内涵非常丰富，其中的“思维经济原则”后来演变为“如无必要，勿增实体”，也称“简单有效原则”。依据这一原则，如果一个问题存在多个解决方案，则应该选取前提条件最少且最简单的那一个。因此，决策树剪枝就是该原理的一次应用——尽量去除冗余“实体”，只保留必要“实体”。在很多情况下，一棵经过剪枝的决策树，不但具有更加清晰的知识表示，而且更富执行效率。

然而，从目前的研究现状看，存在滥用剪枝并导致决策树分类性能下降的现象[14]。从本质上说，剪枝滥用现象来源于人们对奥卡姆剃刀原理的片面理解，一味强调“勿增实体”，而忽视“如非必要”这一前提条件。剪枝之所以在实践中起作用，仅仅是因为这恰好与它们所要解决的问题相“匹配”[14]。

2.2 没有免费午餐原理与剪枝

没有免费午餐原理揭示了获得与付出的共生性。许多剪枝算法虽然能提高效率或避免过拟合现象的发生，但同时也要付出很大的代价。例如，先剪枝算法由于前瞻性不足而过早停止生长，导致视野效应，难以确定被剪结点的子结点对分类的贡献程度，往往不能得到比较优化的决策树[15]。再如，后剪枝算法虽然可避免先剪枝算法带来的弊端，但或者具有较高的时间复杂度，或者需要额外的检验样例集，或者不能得到较优的决策树。因此，经过剪枝的决策树也许更易理解、更富效率，但其性能却未必最佳。正如Duda所指出的那样：不存在与“语境无关”（context-free）或与“应用无关”（usage-free）的任何理由来认定某种学习或分类算法比另外一种更好[14]。

2.3 人类本能与剪枝

既然剪枝后的决策树不一定拥有最佳性能，那么是什么原因使我们更偏爱剪枝后的决策树呢？一种解释是：由于在强大的自然选择作用下，为了生存，人类更喜欢理解简单、耗时最少的分类器[14]。在人类社会早期，自然条件十分恶劣，为保证在种间和种内竞争中保持优势并成为胜出者，人类更喜欢高效率的工具。经过几十万年的沉淀，这种认知已经深深印入了人类集体意识中，选择简单、高效的工具已经变成了人类的一种本能。因此，对决策树的剪枝行为也许恰恰是人类本能的反映。

2.4 孤立点与剪枝

决策树剪枝既能提高效率又能在很大程度上避免过拟合现象的发生，但也存在着一个很大的弊端，即将训练样例集中的孤立点等同于噪声一样处理，从而会使得与孤立点相关的规则（知识）被屏蔽掉，而这些规则往往具有重要价值。事实上，孤立点在科学研究中往往具有特殊的作用，孤立点检测已经广泛应用于网络入侵检测、电信和信用卡欺骗、气象预报、客户分类、RFID数据流及传感器数据处理等诸多领域[16]。屏蔽掉孤立点相关规则，虽然会使得决策树具有较强的泛化能力，但同时也可能失去重要规则（知识）。

3 免剪枝措施

虽然决策树剪枝可以提高效率，避免过拟合现象，但由于剪枝行为可能只是迎合了人类本能，或忽视了奥卡姆剃刀原理的前提，并需要额外代价，有可能造成决策性能下降，以及存在丢失重要规则的可能，因此本文主张慎用剪枝，在有些情况下不用剪枝。

为避免剪枝，建议采取以下措施。

⑴ 加强数据预处理。在训练决策树之前，加强对训练样例集进行数据清洗、数据补齐、离散化，以及规范化等处理，尽量平抑噪声。

⑵ 扩大训练样例集规模。因决策树本质上为归纳学习方法，而噪声数据相对于正常数据毕竟所占比例较低，因此适当扩大训练样例集规模可以有效减少噪声的影响。

⑶ 缩小测试属性集合规模。在实际应用中，除分类属性外，存在测试属性强相关的情况。对测试属性集合进行尽可能的约简，去除强相关属性，可以有效缩小决策树规模和减少生成规则的维度。

4 结束语

本文通过阐释剪枝与过拟合现象的关系，从奥卡姆剃刀原理前提条件被忽视、没有免费午餐原理所揭示的获得与付出的共生性、人类追求简单性的本能，以及孤立点规则被屏蔽等多个方面对决策树剪枝的合理性和必要性展开了讨论，提出了慎用剪枝的主张以及免剪枝措施。

参考文献（References）：

[1] Liang Chunquan， Zhang Yang， Shi Peng， et al. Learning

accurate very fast decision trees from uncertain data streams[J]. International Journal of Systems Science，2015.46（16）：3032-3050

[2] Li Peipei， Wu Xindong， Hu Xuegang， et al. Learning

concept-drifting data streams with random ensemble decision trees[J]. Neurocomputing，2015.166：68-83

[3] Kretser Heidi E， Wong Ramacandra， Roberton Scott， et al.

Mobile decision-tree tool technology as a means to detect wildlife crimes and build enforcement networks[J]. Biological Conservation，2015.189（SI）：33-38

[4] Dhurandhar Amit. Bounds on the moments for an

ensemble of random decision trees[J]. Knowledge and Information Systems，2015.44（2）：279-298

[5] Czajkowski Marcin， Grzes Marek， Kretowski Marek.

Multi-test decision tree and its application to microarray data classification[J]. Artificial Intelligence in Medicine，2014.61（1）：35-44

[6] Mehenni Tahar， Moussaoui Abdelouahab. Data mining

from multiple heterogeneous relational databases using decision tree classification[J].Pattern Recognition Letters，2014.40：136-136

[7] Tuerkcan Silvan， Masson Jean-Baptiste. Bayesian Decision

Tree for the Classification of the Mode of Motion in Single-Molecule Trajectories[J]. Plos One，2013.8（12）：e82799

[8] Lupascu Carmen Alina; Tegolo Domenico; Trucco

Emanuele. Accurate estimation of retinal vessel width using bagged decision trees and an extended multiresolution Hermite model[J]. Medical Image Analysis，2013.17（8）：1164-1180

[9] 韩家炜，Kam ber. M.数据挖掘：概念与技术（第2版）[M].机械

工业出版社，2007.

[10] 梁循.数据挖掘算法与应用[M].北京大学出版社，2006.

[11] 郭宇红，王路宁，毛玉琪.SPSS Clementine决策树建模在图

书馆中的应用[J].计算机时代，2014.4：30-33

[12] 陈玉珍.基于决策树的高职学生创业倾向分析[J].计算机时

代，2010.3：31-35

[13] 张立敏，晋新敏.基于决策树的心理危机预警模型研究[J].计

算机时代，2013.1：3-5

[14] Richard O. Duda， David G. Stork. 模式分类[M]. 北京-机

械工业出版社， 2003

[15] 郑伟，马楠.一种改进的决策树剪枝算法[J].计算机与数字工

程，2015.43（6）：960-966，971

[16] 孙焕良，鲍玉斌，于戈等.一种基于划分的孤立点检测算法[J].

软件学报，2006.17（6）：1009-1016