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

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 过拟合

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

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

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