Page 127 - 计算机应用软件开发技术研究

第四章 大数据与机器学习

决策树是机器学习常见的一种方法。20 世纪末期，机器学习研究者
J.Ross Quinlan 将 Shannon 的信息论引入了决策树算法中，提出了 ID3 算法。
1984 年 I.Kononenko、E.Roskar 和 I.Bratko 在 ID3 算法的基础上提出了 AS-
SISTANTAlgorithm，这种算法允许类别的取值之间有交集。同年，A.Hart 提出了

Chi-Squa 统计算法，该算法采用了一种基于属性与类别关联程度的统计量。1984
年 L.Breiman、C.Ttone、R.Olshen 和 J.Freidman 提出了决策树剪枝概念，极大地
改善了决策树的性能。1993 年，Quinlan 在 ID3 算法的基础上提出了一种改进算

法，即 C4.5 算法。C4.5 算法克服了 ID3 算法属性偏向的问题增加了对连续属性
的处理通过剪枝，在一定程度上避免了“过度适合”现象。但是该算法将连续属
性离散化时，需要遍历该属性的所有值，降低了效率，并且要求训练样本集驻留
在内存，不适合处理大规模数据集。2010 年 Xie 提出一种 CART 算法，该算法

是描述给定预测向量 X 条件分布变量 Y 的一个灵活方法，已经在许多领域得到
了应用。CART 算法可以处理无序的数据，采用基尼系数作为测试属性的选择标
准。CART 算法生成的决策树精确度较高，但是当其生成的决策树复杂度超过一
定程度后，随着复杂度的提高，分类精确度会降低，所以该算法建立的决策树不

宜太复杂。2007 年房祥飞表述了一种叫 SLIQ（决策树分类）算法，这种算法的
分类精度与其他决策树算法不相上下，但其执行的速度比其他决策树算法快，它
对训练样本集的样本数量以及属性的数量没有限制。SLIQ 算法能够处理大规模
的训练样本集，具有较好的伸缩性；执行速度快而且能生成较小的二叉决策树。

SLIQ 算法允许多个处理器同时处理属性表，从而实现了并行性。但是 SLIQ 算
法依然不能摆脱主存容量的限制。2000 年 RajeevRaSto 等提出了 PUBLIC 算法，
该算法是对尚未完全生成的决策树进行剪枝，因而提高了效率。近几年模糊决策
树也得到了蓬勃发展。研究者考虑到属性间的相关性提出了分层回归算法、约束

分层归纳算法和功能树算法，这三种算法都是基于多分类器组合的决策树算法，
它们对属性间可能存在的相关性进行了部分实验和研究，但是这些研究并没有
从总体上阐述属性间的相关性是如何影响决策树性能。此外，还有很多其他的
算法，如 Zhang.J 于 2014 年提出的一种基于粗糙集的优化算法、Wang.R 在 2015

年提出的基于极端学习树的算法模型等。
随机森林（RF）作为机器学习重要算法之一，是一种利用多个树分类器进
行分类和预测的方法。近年来，随机森林算法研究的发展十分迅速，已经在生物

·115·