决策树学习

决策树/决策规则学习是一种决策支持工具,使用了树状图来模拟决策和对应结果。它的现实应用包括业务管理、客户关系管理和欺诈检测。最流行的决策树算法包括 ID3、CHAID、CART、QUEST 和 C4.5。

来源:机器之心
简介

决策树/决策规则学习是一种决策支持工具,使用了决策树来模拟决策和对应结果。它的现实应用包括业务管理、客户关系管理和欺诈检测。决策树本身是预测建模机器学习的一种重要算法,最流行的决策树算法包括ID3、CHAID、CART、QUEST和C4.5。

一个形象的决策树示例如下:

决策树的叶节点包含一个用于预测的输出变量y。通过遍历该树的分割点,直到到达一个叶节点并输出该节点的类别值就可以作出预测。决策树学习速度和预测速度都很快。它们还可以解决大量问题,并且不需要对数据做特别准备。

[图片及描述来源:机器学习新手必看十大算法|机器之心]

决策树可以看成为一个if-then规则的集合,即由决策树的根节点到叶节点的每一条路径构建一条规则,路径上内部节点的特征对应着规则的条件,而叶节点的类对应于规则的结论。因此决策树就可以看作由条件if(内部节点)和满足条件下对应的规则then(边)组成。

决策树的工作方式是以一种贪婪(greedy)的方式迭代式地将数据分成不同的子集。其中回归树(regression tree)的目的是最小化所有子集中的MSE(均方误差)或MAE(平均绝对误差);而分类树(classification tree)则是对数据进行分割,以使得所得到的子集的熵或基尼不纯度(Gini impurity)最小。

[描述来源:如何解读决策树和随机森林的内部工作机制?|机器之心]

发展历史

描述

决策树是一类树模型的统称,其最早可以追溯到1948年左右,当时克劳德·香农介绍了信息论,这是决策树学习的理论基础之一。随后,1963年,Morgan和Sonquist开发出第一个回归树,他们提出了一种分析调查数据的方法,它不对交互影响施加任何限制,侧重于减少预测误差,顺序操作,并且不依赖于分类中的线性程度或解释变量的排列顺序,当时他们起名为交互检测(AID)模型。由于AID没有真正考虑到数据固有的抽样变异性,Messenger和Mandell在1972提出了THAID树以弥补这一缺陷,1980年,Gordon V. Kass开发出CHAID算法,这是AID和THAID程序的正式扩展。

随后出现的是CART树——分类和回归树(简称CART)——是Leo Breiman引入的术语,指用来解决分类或回归预测建模问题的决策树算法。CART模型包括选择输入变量和那些变量上的分割点,直到创建出适当的树。使用贪婪算法(greedy algorithm)选择使用哪个输入变量和分割点,以使成本函数(cost function)最小化。1986年,Quinlan开发出ID3算法,并于随后几年提出了C4.5算法。根据谷歌趋势和谷歌学术的数据,C4.5仍然是各种决策树学习算法中最受关注和相关论文数量最多的。因此我们可以将其看作是单决策树学习应用中最流行的算法。过去几十年来,决策树已经在很多不同行业领域得到了应用,为管理和决策提供支持。决策树也可以为欺诈检测和故障诊断提供帮助。为了提高它的运算效率,Loh和Shih于1997年开发出QUEST。1999年,Yoav Freund和Llew Mason提出AD-Tree,在此之前,决策树已经在正确率上取得了很不错的成就,但是当时的决策树在结构上依旧太大,而且不容易理解,所以AD-Tree在节点上做了改变。该算法不仅对数进行投票,也对决策节点进行投票。并且每个决策节点都是有语义信息的,更容易理解。

此后决策树领域的发展比较稳定,直到深度学习崛起后,不少研究试图将决策树与神经网络结合起来。如2017年,针对泛化能力强大的深度神经网络(DNN)无法解释其具体决策的问题,深度学习殿堂级人物 Geoffrey Hinton 等人发表 arXiv 论文提出「软决策树」(Soft Decision Tree)。相较于从训练数据中直接学习的决策树,软决策树的泛化能力更强;并且通过层级决策模型把 DNN 所习得的知识表达出来,具体决策解释容易很多。这最终缓解了泛化能力与可解释性之间的张力。2018年,加州大学洛杉矶分校的朱松纯教授等人发布了一篇使用决策树对 CNN 的表征和预测进行解释的论文。该论文借助决策树在语义层面上解释 CNN 做出的每一个特定预测,即哪个卷积核(或物体部位)被用于预测最终的类别,以及其在预测中贡献了多少。决策树学习以其简单、易理解的优势受到了欢迎。

主要事件

年份

事件

相关论文/Reference

1948-1949

克劳德·香农介绍了信息论,这是决策树学习的基础之一

Shannon, C.E. (1948).A mathematical theory of communication. Bell System Technical Journal, 27: 379–423 and 623–656. //Shannon, C. E. (1949). Communication Theory of Secrecy Systems. Bell System Technical Journal 28 (4): 656–715.

1963

Morgan和Sonquist开发出第一个回归树

Morgan. J. N. & Sonquist, J. A. (1963) Problems in the Analysis of Survey Data, and a Proposal, Journal of the American Statistical Association, 58:302, 415-434.

1980

Gordon V. Kass开发出CHAID算法

Gordon V. K. (1980).An Exploratory Technique for Investigating Large Quantities of Categorical Data, Applied Statistics. 29(2): 119–127.

1984

Leo Breiman et al.开发出CART(分类与回归树)

Breiman, L.; Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984). Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software.

1986

Quinlan开发出ID3算法

Quinlan, J. R. (1986). Induction of Decision Trees. Mach. Learn. 1(1): 81–106

1993

Quinlan开发出C4.5算法

Quinlan, J. R. (1993). C4.5: Programs for machine learning. San Francisco,CA: Morgan Kaufman.

1997

Loh和Shih开发出QUEST

Loh, W. Y., & Shih, Y. S. (1997). Split selection methods for classification trees. Statistica sinica, 815-840.

1999

Yoav Freund和Llew Mason提出AD-Tree

Freund, Y., & Mason, L. (1999, June). The alternating decision tree learning algorithm. In icml (Vol. 99, pp. 124-133).

2017

Geoffrey Hinton等人发表arXiv论文提出「软决策树」(Soft Decision Tree)

Frosst, N.; Hinton, G. (2017).Distilling a Neural Network Into a Soft Decision Tree.arXiv:1711.09784.

2018

加州大学洛杉矶分校的朱松纯教授等人发布了一篇使用决策树对CNN的表征和预测进行解释的论文

Zhang, Q.; Yang, Y.; Nian Wu, Y.; Zhu, S-C. (2018). Interpreting CNNs via Decision Trees. arXiv:1802.00121.

发展分析

瓶颈

  • 在特定条件下的过拟合或欠拟合问题限制了决策树的应用。
  • 随着树规模的增长,树可能会变得无法被解释。

未来发展方向

  • 决策树的当前发展趋势更多关乎其结果的可靠性和算法的适应性。因此,可以预见会有集成学习等更多扩展或集成,也可能出现集成了本体论的「现代专家系统。」
  • 随着深度学习的发展,影响决策树的表现的特征选择可能会得到显著改善。

Contributor: Mos Zhang, Yuanyuan Li

相关人物
朱松纯
朱松纯
朱松纯是全球著名计算机视觉专家,统计与应用数学家、人工智能专家,现任美国加州大学洛杉矶分校 [UCLA] 统计系与计算机系教授,UCLA计算机视觉、认知、学习与自主机器人中心主任。
莱奥·布雷曼
莱奥·布雷曼
1928-2005,加州大学伯克利分校的杰出统计学家、美国国家科学院的成员。他的工作有助于弥合统计学和计算机科学之间的差距,特别是在机器学习领域。他最重要的贡献是在分类和回归树方面的工作。
简介
相关人物