决策树技术研究综述

李泓波　白劲波　杨高明　黄少伟

摘要：决策树是一种重要的数据挖掘技术，广泛应用于电子商务、医学、天文学和决策分析等多个领域。针对决策树技术研究越来越受到重视的现实情况，通过介绍决策树技术相关概念、理论及其发展过程，阐述决策树技术的国内外研究现状，指出决策树技术面临的困难和挑战，并展望其研究方向。

关键词：决策树；数据挖掘；现状；研究方向

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）24-0001-04

Review on Decision Tree Technology Research

LI Hong-bo1， BAI Jin-bo2*， YANG Gao-ming3， HUANG Shao-wei1

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

Abstract： Decision tree is an important data mining technology， widely used in electronic commerce， medicine， astronomy， and decision analysis， and other fields. Aiming at the reality that the decision tree technology is paid more and more attention， this article points out the difficulties and challenges that the decision tree technology is facing， and prospects the research orientations by introducing the related concept， theory and its development process， elaborating its research status at home and abroad.

Keywords： decision tree； data mining； status； research orientation

1研究现状

决策树是一种重要的数据挖掘技术，常用于分类预测以及规则提取等诸多领域[1-8]。决策树采用贪婪策略，通过递归方式自顶向下进行构造。从发展脉络上看，目前丰富的决策树算法均起源于Hunt，Marin和Stone在1966年提出的单概念学习系统[9]。

1979年，Quinlan 提出ID3算法，并于1983年和1986年对其进行进一步的完善和发展。通过不懈的努力，Quinlan不但使ID3成为经典的决策树算法，还通过开办公司的方式使之成功走向应用。1986年，Schlimmer 和Fisher 在ID3的基础上，通过创建缓冲区，提出可伸缩的递增式决策树算法ID4。1988年，Utgoff 在ID4基础上又提出效率更高的ID5算法。1993年，Quinlan 提出C4.5算法，突破了ID3算法只能处理布尔函数样例的束缚。

为进一步提高缩效率，研究者在ID4的基础上又提出了一批可伸缩的决策树算法，代表性的有SLIQ、SPRINT、RainForest、BOAT算法。目前来看，综合指标最佳的算法是BOAT，不但可伸缩而且效率更高（仅需扫描训练样例集两遍），并且是增量式学习算法[10]。

目前对决策树技术的研究主要集中在已下几个方面[11]：1）与其他技术相结合，如与神经网络[12-13]、模糊集[14-15]、遗传算法及遗传编程 [16-20]、多智能体[21-23]等原理和技术相结合；2）寻找可视化的交互式决策树构造方法[24]；3）寻找更好的剪枝算法[25]；4）寻找训练样本集、检验样本集特性与生成树特性之间的联系[26-27]；5）包括半监督学习在内的非确定环境下的决策树研究[28]；6）时间复杂度与分类准确性的折衷研究[29]。

相对而言，国内对决策树技术的研究尚不够活跃，但值得关注的是朱鸣和陈文伟提出的决策规则树方法——IBLE方法。IBLE方法采用信道容量作为衡量样例的目标属性的标准，是一个不依赖正、反例比例的量。而且，该方法迥异ID3算法的一个重要区别是每次遴选一组相对重要的属性，依其建立的规则作为决策树的非叶子结点，更富有效率并更准确 [30]。

2 决策树技术概览

由ID3、ID4.5等算法生成的决策树是一种类似二叉树和多叉树的树形结构。决策树中的非叶子结点代表一个目标属性，每个叶子结点表示一个分类，从根结点到叶子结点的所有结点表示一个分类规则。

2.1 决策树与归纳学习

决策树的本质是归纳学习，是一种从部分数据中归纳出整体数据特征完备描述的技术。归纳学习是人类知识增长的一种重要方式。例如，看到乌鸦、喜鹊、黄鹂、燕子、大雁等鸟类具备飞行的能力，在未对所有鸟类都进行观察的情况下，归纳出以下的规则：鸟类都具备飞行的能力。于是，按此规则可以进一步预测云雀、百灵、鹦鹉都具备飞行的能力。虽然此规则未必适用所有鸟类，如鸵鸟，但其基本是准确的，准确率可以达到百分之九十以上。决策树的分类预测能力，完全来自于它能够从部分数据归纳和概括出整体数据特征描述（决策树技术通过测试和筛选训练样本集合的属性集合，并生成新的属性子集的方式实现这种描述）的能力。

2.2决策树应用步骤

利用决策树应用大致可以分为以下四大步骤：

1）对训练样本集进行数据补齐、数据清洗、离散化、规范化等预处理；

2）使用ID3、ID4等具体算法，利用训练样本集训练（构建）一棵决策树，并对决策树进行前剪枝或后剪枝处理。

3）对经过训练的决策树输入检验样本集进行检验：如果对分类结果不满意，则转（1）。

4）应用训练好的决策树对需要预测分类的样本进行分类。

2.3 决策树的特点

目前存着许多分类方法和技术，如贝叶斯信念网络、BP网络、支持向量机、关联分类、近邻学习、粗糙集方法、模糊集方法等，决策树之所以能够如此流行并得到高度关注，一个重要原因是它具备一些区别于其他分类方法的鲜明特点：

1）从理论上说，决策树技术可以处理任意高维的数据；

2）决策树算法虽然简单，但比较高效；

3）决策树技术具有较高的分类预测准确率；

4）在决策树的构造过程中，无需任何的先验知识，也无需以交互方式设定参数；

5）获取的知识用树形结构表示，既直观又易于理解。

2.4 ID3决策树建立算法

在决策树技术的发展历程中，先后经历了从不可伸缩到可伸缩、布尔函数分类预测到多值函数预测等阶段，涌现了多个优秀的算法。以下以经典的ID3算法[31]说明决策树技术的基本原理。

输入：ID3（Examples，Target_attribute，Attributes），Examples即训练样例集，Target_attribute是决策树要预测的目标属性，Attributes是除去目标属性之外供学习到的决策树测试的属性列表。

输出：一棵能正确分类给定Examples的决策树Root。

1.创建树的Root结点

2.如果Examples都为正例，那么返回label = + 的单结点树Root

3.如果Examples都为反例，那么返回label = - 的单结点树Root

4. 如果Attributes为空，那么返回单结点树Root，label = Examples中最普遍的Target_attribute值

5.否则开始

1） A ← Attributes中分类Examples能力最好的属性

2） Root的决策属性 ← A

3） 对于A的每个可能值vi

（1） 在Root下加一个新的分支对应测试 A = vi

（2） 令Examplesvi为Examples中满足A属性值为vi的子集

（3） 如果Examplesvi为空

① 在这个新分支下加一个叶子结点，结点的label = Examples中最普遍的Target_attribute值

② 否则在这个新分支下加一个子树ID3（Examplesvi，Target_attribute，Attributes - |A|）

6. 结束

7. 返回Root

在算法的（1）处所描述的分类能力最好的属性为具有最高信息增益的属性。

2.5 熵与信息增益

1）信息熵

ID3算法认为，对于一个拥有n个反例和p个正例的样例集合S来说，能对其正确分类的决策树的信息量为：

[I（p，n）=-pp+nlog2pp+n-np+nlog2np+n] （1）

若以属性A作为当前样例集S的根，并设A有v个值v1，v2，…，vv，并将分S为对应的v个子集S1，S2，…，Sv，且某子集Si中含有Pi个正例和Ni个反例，规定Si的信息熵为：

[E（Si）=-PiPi+Nilog2PiPi+Ni-NiPi+Nilog2NiPi+Ni] （2）

又规定以属性A为根进行分类的信息熵为：

[E（A）=i=1vpi+niP+NE（Si）] （3）

2）信息增益

ID3中规定，信息增益最大的属性A可评为分类最好属性，其定义式为：

[Gain（A）=I（p，n）-E（A）] （4）

综合公式（1）～（ 4），可以推知在当前样例集下，属性A的信息增益最大时，其信息熵E（A）最小。

2.6 决策树建立举例

本小节以2.5中介绍的ID3算法为例，基于表1中描述的元组为训练样本集S，简述决策树建立过程。

首先，计算对S中元组分类所需的期望信息：

[I（p，n）=-914log2914-514log2514=0.940bits]

下一步，计算每个属性的期望信息需求。例如元组根据age属性进行划分，对S中的元组进行分类所需的期望信息为：

[E（age）=514×（-25log225-35log235）]

[+414×（-44log244-04log204）]

[+514×（-35log235-25log225）]

[=0.694bits]

因此，以属性age进行划分的信息增益为

[Gain（age）=0.940-0.694=0.246bits]

类似可求得

[Gain（income）=0.029bits]

[Gain（student）=0.151bits]

[Gain（credit_rating）=0.048bits]

由于age属性具有最大的信息增益，所以被选作分裂属性。根结点用age标记，并对应于它的每个属性值长出一个分枝。然后，元组据此划分，如图1所示。

图1 按属性age分类产生的决策树分枝

在每一个分枝所对应的训练子集上，重复前述步骤，即可得到最终的决策树。

3 未来研究方向

结合目前的研究 [9-10，30-33]，未来决策树技术的研究应该包括以下几个方面。

1）基于量子免疫克隆算法的决策树优化。

决策树本身的优化需要面对以下理论问题（洪家荣教授首次证明了这几个问题都是NP难问题）：①最优覆盖问题，即决策树中叶子结点数目最少；②最简公式问题，即保证决策树的每个叶子深度最小；③最优示例学习问题，即决策树叶子最少且每个叶子的深度最小[33]。对于决策树的自身优化，学术界已经有了一些研究成果，提出了一些近似或启发算法。但这些算法还存在一些不足，如易陷入局部最优、时间成本高、分类预测准确率较低等。

由于量子计算所拥有的量子相干特性，可以有效避免一些启发式算法陷于局部最优，免疫算法易实现数据的分布式存储，克隆算法具有强大的自适应能力，因此，决策树的优化还应结合量子计算、免疫算法、克隆算法等相关技术，以便实现优势互补。

2）基于IBLE方法和支持向量机相结合的决策规则树研究。

IBLE方法具有实现简单，学习正确性较高，所得知识在表示和内容上与专家知识有较高的一致性等优点，但在处理小样本的情况下性能较差。而支持向量机特别适于处理小样本的情况，将二者相结合，可以期望会有更好的表现。

3）不确定环境下的决策树研究。

不确定环境下的决策研究一直是一个热点。但如何比较科学地确定决策阈值，目前还是一个鲜有人涉足的课题。

4）连续属性值离散化问题的研究。

由于决策树技术要求属性值为离散值，因此连续值在使用前需要进行离散化处理。按惯常作法，一般将连续值离散为7个以内的离散值。离散值的个数及其具体数值直接影响到决策树的分类质量和效率，科学地取值以及科学地确定离散值数量，是一个值得深入研究的课题。

4 小结

本文介绍了决策树技术及其发展过程，综述了近几年决策树技术的国内外研究现状，展望了进一步的研究方向。

参考文献：

[1] Liang Chun-quan， Zhang Yang， Shi Peng， et al. Learning accurate very fast decision trees from uncertain data streams. International Journal of Systems Science， 2015，46（16）：3032-3050

[2] Li Pei-pei， Wu Xin-dong， Hu Xuegang， et al. Learning concept-drifting data streams with random ensemble decision trees. 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. Biological conservation， 2015，189（SI）：33-38.

[4] Dhurandhar Amit. Bounds on the moments for an ensemble of random decision trees. 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. 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. 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. Plos One， 2013，8（12）： 82799.

[8] Lupascu Carmen Alina； Tegolo Domenico； Trucco Emanuele. Accurate estimation of retinal vessel width using bagged decision trees and an extended multiresolution Hermite model.Medical Image Analysis， 2013，17（8）：1164-1180.

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

[10] 韩家炜， Kam ber. M. 数据挖掘：概念与技术[M].2版. 机械工业出版社， 2007

[11] John Durkin， 蔡竞峰， 蔡自兴. 决策树及其当前研究方向[J]. 控制工程，2005，12（1）：15-21.

[12] Boz o. Extracting decision trees from trained neural networks. Edmonton， Alberta， Cananda： Proc of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2002.

[13] Sethi L. Entropy nets： from decision trees to neural networks. Proc of IEEE， 1990， 78（10）：1605-1613.

[14] Olaru C， wehenkel L. A complete fuzzy decision tree technique. Fuzzy Sets and Systems， 2003， 138（2）：221-254.

[15] Dong M， Kothari R. Look-ahead based fuzzy decision tree induction. IEEE Transactions on Fuzzy Systems， 2002，9（3）：461-468.

[16] Cantu-Paz E， Kamath C. Inducing oblique decision trees with evolutionary Algorithms. IEEE Transactions on Evolutionary Computation， 2003，7（1）：54-68.

[17] Papagelis A， Kalles D. Breeding decision trees using evolutionary techniques. USA： Proceedings of ICML' 01， USA， 2001.

[18] Papagelis A， Kalles D. GA tree： genetically evolved decision trees. USA： Proceedings of ICTAI'00， 2000.

[19] Tur G， Guvenir H A. Decision tree induction using genetic programming. Ankara， Turkish： Proceedings of the Fifth Turkish Symposium on Artificial Intelligence and Neural Networks， 1996.

[20] Eggermont J. Evolving fuzzy decision trees with genetic programming and clustering. Milan， Italy： Proceedings of the 4th European Conference on Genetic Programming， 2001.

[21] Stone P， Veloso M. Using decision tree confidence factors for multiagent control. Minnesota， USA： Proceedings of the 2nd International Conference on Autonomous Robots， 2000.

[22] Stone P， Veloso M. A layered approach to learning client behaviors in the RoboCup soccer server. Applied Artificial Intelligence（AAI）， 1998， 12（2-3）： 165-187.

[23] Stone P， Veloso M. Multiagent system： a survey from a machine learning perspective. Autonomous Robots， 2000， 8（3）： 345-383.

[24] Ankerst M， Elsen C， Ester M， et al. Visual classification： an interactive approach to decision tree construction. San Diego： In Proceedings of International Conference on Knowledge Discovery and Data Mining， 1999.

[25] Fournier D， Cremilleux B. A quality index for decision tree pruning. Knowledge-based Systems， 2002，15（1）：37-43.

[26] Sebban M， Nock R， Chauchat J H， et al. Impact of learning set quality and size on decision tree performances. IJCSS，2000，1（1）：85-105.

[27] Oates T， Jensen D. The effects of training set size on decision tree complexity. Nashville， Tennessee： Proc of the 14th International Conference on Machine Learning，1997.

[28] Elouedi Z， Mellouli K， Smets Ph. Decision Trees using the belief function theory. Madrid， Spain： Proceedings of the Eighth International Conference IPMU， 2000.

[29] Yildiz O T， Alpaydin E. Omnivariate decision trees. IEEE Transactions on Neural Networks， 2001， 12（6）：1539-1546.

[30] 陈文伟. 数据仓库与数据挖掘教程[M]. 清华大学出版社，2006.

[31] Tom M. Mitchell. 机器学习[M]. 机械工业出版社，2003.

[32] 陈文伟， 廖建文. 决策支持系统及其开发[M].3版.清华大学出版社，2008.

[33] 朱明. 数据挖掘[M].2版.中国科学技术大学出版社，2008.