决策树/决策规则学习是一种决策支持工具，使用了决策树来模拟决策和对应结果。它的现实应用包括业务管理、客户关系管理和欺诈检测。决策树本身是预测建模机器学习的一种重要算法，最流行的决策树算法包括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