决策树算法综述

作者：谢妞妞

来源：《软件导刊》2015年第11期

        摘要摘要：决策树算法是数据挖掘领域的一个研究热点，通常用来形成分类器和预测模型，在实际中应用广泛。介绍了决策树技术及其发展过程，重点阐述了几种典型的决策树算法，分析了它们的优缺点，并对几种算法作了比较，最后探讨了决策树算法今后的发展方向。

        关键词关键词：数据挖掘；分类器；决策树；测试属性

        DOIDOI：10.11907/rjdk.151871

        中图分类号：TP312

        文献标识码：A文章编号文章编号：16727800（2015）011006303

        作者简介作者简介：谢妞妞（1986-），女，河南郑州人，硕士，河南化工职业学院信息工程系助教，研究方向为数据挖掘、智能决策。

        0引言

        随着数据库技术的发展，人们搜集数据的能力大幅度提高，可以非常方便地获取和存储大量的数据，但却无法从这些数据中发现潜在的规律，无法预测未来的发展趋势。如何有效的利用这些数据为人类服务，已成为人们研究的热点之一。数据挖掘技术能自动和智能地从大型数据库中提取隐含的、未知的信息和知识。

        分类是数据挖掘的重要分支，可用于提取、描述重要数据类的模型或预测未来的数据趋势[4]。通过分类和预测，能够对各个行业提供良好的决策支持，对整个社会的发展产生重要而深远的影响[5]。决策树算法是数据挖掘分类算法中常见的一种方法。它以树状结构表现，叶子结点代表一个结论，内部结点描述一个属性，从上到下的一条路径，确定一条分类规则。与其它技术相比，决策树算法结构简单直观，容易理解，有较高的分类精度，在数据挖掘、机器学习、人工智能等领域等都有广泛的应用。所以研究并提出高效、适用的决策树算法对整个社会的发展意义重大。

        本文对几种经典的决策树分类算法进行了分析，指出不同算法的优点和不足，并讨论了决策树算法今后的研究方向。

        1几种决策树分类算法介绍

        决策树算法是一种逼近离散值目标函数的方法，它将分类规则以树状结构表示[6]。

        1.4SLIQ算法

        决策树分类算法研究一直朝着处理大数据集的方向进行，但大部分方法在减少了运算时间的同时也降低了算法的精度。SLIQ的分类精度与其它决策树算法不相上下，但其执行的速度比其它决策树算法快。SLIQ算法对训练样本集的样本数量以及属性的数量没有。SLIQ提高了分类的精确度[21]。

        SLIQ算法能够处理大规模的训练样本集，具有较好的伸缩性；执行速度快而且能生成较小的二叉决策树；SLIQ算法允许多个处理器同时处理属性表，从而实现了并行性[21]。但是SLIQ算法依然不能摆脱主存容量的。

        1.5SPRINT算法

        SLIQ算法要求类表驻留内存，当训练集大到类表放不进内存时，SLIQ算法就无法执行。为此，IBM研究人员提出SPRINT算法，它处理速度快、不受内存的。

        SPRINT算法可以处理超大规模训练样本集，数据样本集数量越大，SPRINT的执行效率越高，并且可伸缩性更好。但是，SPRINT算法存在着一些缺陷：在SLIQ的类表可以存进内存时，SPRINT算法的执行速度比SLIQ算法慢；该算法由于使用了属性表，增加了存储代价。

        1.6PUBLIC算法

        上述含有剪枝的算法都是分成两步进行，即先建树再剪枝。然而，这种方法将已生成的分枝再剪去是一种效率较低的重复劳动，于是Rajeev RaSto等人在2000年提出了PUBLIC算法（Pruning and Building Integrated in Classification）[23]。由于PUBLIC算法是对尚未完全生成的决策树进行剪枝，因而提高了效率。近几年，模糊决策树也得到了蓬勃发展[2425]。

        上述算法未考虑属性间的相关性。因此，后来人们又提出了分层回归算法、约束分层归纳算法和功能树算法。

        分层回归算法、约束分层归纳算法和功能树算法都是基于多分类器组合的决策树算法，它们对属性间可能存在的相关性进行了部分实验和研究，但是这些研究并没有从总体上阐述属性间的相关性是如何影响决策树性能的[2628]。

        基于粗糙集的决策树方法也是典型的决策树算法。文献[29]提出了基于粗糙集的优化算法，并且分析了各自的优缺点。文献[30]通过设计特殊的Hashtable减少了每次读取I/O的开销，这种方法很大程度上降低了时间复杂度，但是并没有考虑到精确度的改进，而且由于数据量大时，哈希表也会很占内存。文献[31]提出了基于极端学习树的模型，也是能够降低时间复杂度，但是不易实现并行化计算和设计。

        1.7经典决策树算法比较

        基于决策树的分类算法自提出至今，种类不下几十种。各种算法在执行速度、可扩展性、输出结果的可理解性、分类预测的准确性等方面各有所长。表1是几种经典的决策树算法比较[32]。

        2结论及展望

        决策树虽然在理论研究和实际应用方面都取得了很多进展，但还存在不少问题亟待解决，这正是今后的研究方向，主要有：

        （1） 实验证明：要找到最优的决策树是NP问题[33]，必须寻找更好的方法，将决策树技术和其它新兴技术相结合，取长补短，提高决策树的抗噪声能力和准确性。

        （2） 研究属性间的相关性对决策树产生的影响，以及如何利用或者消除这些相关性来构造决策树，值得关注。

        （3） 决策树技术中如何处理时间复杂度和分类准确性之间的矛盾，一直以来都是一个令人感兴趣的问题。怎样在提高准确度的前提下降低时间复杂度，是今后研究的一个重点及难点。

        （4） 决策树技术软件化一直是决策树技术的方向之一。如何开发出功能更加强大、使用更加方便、界面更加友好的软件以实现决策树技术，是今后需努力实现的目标。

        参考文献参考文献：

        [1]赵翔.数据挖掘中决策树分类算法的研究[D].镇江：江苏科技大学，2008.

        [2]HAN，M KAMBER.数据挖掘：概念与技术[M].范明，孟小峰，译.北京：机械工业出版社，2001.

        [3]史忠植.知识发现[M].北京：清华大学出版社，2002.

        [4]JIAWEI HAN.数据挖掘——概念与技术[M].北京：机械工业出版社，2001.

        [5]邓春燕，陶多秀 ，吕跃进，粗糙集与决策树在电子邮件分类与过滤中的应用[J].计算机工程与应用，2009，45（16）：138140.

        [6]AGRAWAL R，MANNLA H，SCRIKEANT R，et al.Fast discovery of association rule[C].Advances in Knowledge Discovery and data Mining，AAAI Press/The MIT Press，1996：307328.

        [7]J R QUINLAN.Induction of decision trees[J].Machine Learning，1986，1（1）：81106.

        [8]LIU YUXUN，XIE NIUNIU.Improved ID3 algorithm[J].Computer Science and Information Technology （ICCSIT） ，2010：465468.

        [9]毛国君，段立娟，王实，等.数据挖掘原理与算法[M].北京：清华大学出版社，2005：117121.

        [10]谢妞妞，刘於勋.决策树属性选择标准的改进[J].计算机工程与应用，2010，46（34）：115118.

        [11]陆秋.基于决策树ID3算法的数据挖掘技术研究与应用[D].桂林：桂林工学院，2007：16.

        [12]I KONONENKO，I BRATKO，E ROSKAR.Experiments in automatic learning of medical diagnostic rules[J].Jozef Stefan Institute，Ljublijana，Yugoslavia，1984.

        [13]A.HART.Experience in the use of an inductive system in knowledge engineering[M].Cambridge：Cambrige University Press，1984.

        [14]L BREIMAN，J H FRIEDMAN，R A OLSHEN，et al.Classification and regression trees[M].Wadswords，Belmont，CA，1984.

        [15]T NIBLETT.Constructing decision trees in noisy domains[M].Progress in machine leaning.England：Sigma Press，1984.

        [16]J R QUINLAN.Simplifying decision trees[J].International Journal of ManMachine Studies，1987（27）：221234.

        [17]J MINGERS.Expert system—rule induction with statistical data[J].Journal of the Operational Rsearch society，1987（38）：347352.

        [18]I KONONENKO.Estimating attributes：analysis and extensions of RELIEF[M].Machine Leamjng ECML94，1994：171182.

        [19]QUINLAN J R.C4.5：programs for machine learning[M].Morgan Kauffman，1993：2330.

        [20]XIE NIUNIU ，LIU YUXUN.Review of decision trees [J].Computer Science and Information Technology （ICCSIT） ，2010（5）：105109.

        [21]房祥飞.基于决策树的分类算法的并行化研究及应用[D].济南：山东师范大学，2007：1418.

        [22]刘薇.数据挖掘中决策树方法研究及其在房地产中介的应用[D].西安：西安电子科技大学，2006：3234.

        [23]G I WEBB.Further experimental evidence against the utility of Occam's Razor[J].Journal of Artificial Intelligence Research，1996（4）：397411.

        [24]A SUPAREZ，J F LUTSKO.Optimal fuzzy decision trees for classification and regression[J].IEEE Trans.Pattern Anal.And Mach.Intelligence，1999（21）：12971311 .

        [25]M GUETOVA，S HUOLLDOBLER，H P STORR.Incremental fuzzy decision trees[C].Presented at Proceedings of the 25th Geman Conference on Artificial Intelligence（KI2002），Aachen，Gemany，2002.

        [26]吴强.智能群体决策支持系统中若干关键理论与方法研究[D].合肥：中国科学技术大学，2006：2425.

        [27]HUIMIN ZHAO ，SUDHA RAM.Constrained cascade generalization of decision trees[J].IEEE Transactions on Knowledge and Engineering， 2004，16（6）：727739.

        [28]J GAMA.Functional trees[J].Machine Learning，2004（55）：219250.

        [29]ZHANG J，WONG J，LI T，et al.A comparison of parallel largescale knoledge acquisition using rough set theory on different MapReduce runtime systems[J].International Journal of Approximate Reasoning，2014，55（3）：6907.

        [30]DAI W，JI W.A MapReduce implementation of C4.5 decision tree algorithm[J].International Journal of Database Theory and Application，2014，7（1）：4960.

        [31]WANG R，HE Y L，CHOW C Y，et al.Learning ELMTree from big data based on uncertainty reduction[J].Fuzzy Sets and Systems，2015（258）：79100 .

        [32]S J YEN，A L P CHEN.An efficient approach to discovering knowledge from large databases[C].In 4th Intl Conf.Parallel and Distributed Info，1996.

        [33]HYAFIL L，RIVEST R L.Constructing optimal binary decision trees Is NP—complete[J].Info Proc Letters，1976，5（1）：1517.

        责任编辑（责任编辑：杜能钢）