入门决策树 | 概述篇 | 山人聊算法 | 6th
入门决策树 | 概述篇 | 山人聊算法 | 6th
说完了感知机的事儿。我们这次来聊聊决策树，决策树是一种可解释性好、对各种非线性情况适应性强的方法。
概念
看图说话，利于理解，决策树是下图这样式儿的。
决策树是本质上是对训练数据进行概率计算，然后进行树结构的分段拟合，即从训练数据集中归纳出一组分类规则。
这是一种结合了人类专家思维方式和概率计算的自动化规则生成方法，可以实现对训练数据集的最纯净划分，所谓最纯净指的是可以对训练数据集实现零误差分类，当然这样不代表模型对于新的数据也能很好的泛化，反而非常容易过拟合，所以这就涉及到剪枝的问题，后面细聊。
决策树也可以认为是if-then规则的集合，还可以说是在特征空间与类空间上的条件概率分布。树模型拟合出来的函数其实是分区间的阶梯函数。
用途
决策树既可以用于数据分类，也可以用于回归建模进行预测。由于其拟合适应性强的特点，在非常多的行业都会有应用。比如：在用决策树进行用户分级评估的时候，凡是积累了一定量的客户资源和数据，涉及对自己行业客户进行深入分析的企业和分析者都可能具备使用决策树的条件。
一般来说决策树的应用用往往都是和某一应用分析目标和场景相关的，比如：金融行业可以用决策树做贷款风险评估，保险行业可以用决策树做险种推广预测，医疗行业可以用决策树生成辅助诊断处置模型等等，当一个决策树的应用分析目标和场景确定，那该应用分析目标和场景所处的行业也就自然成为了决策树的应用领域。
优缺点
优点
1）模型具有可读性，树形模型更加接近人的思维方式，可以产生可视化的分类规则，产生的模型具有可解释性（可以抽取规则）。
2）分类速度快。
3）同时适用于线性和非线性拟合。
4）需要准备的数据量不大，多少数据都可以用，当数据离散性强的时候效果更好一些。
5）可以很好的处理多输入、多输出的问题。
缺点
1）如果你的边界很光滑动，决策树不会很好用。也就是说当你有不连续的实例时，决策树才表现最好。
2）如果有很多不相关的变量，决策树表现的不好。决策树的工作是通过找到变量间的相互作用。
3）高方差和不稳定性：扰乱一点，改动一点值，决策树就会改变。改变树的根结点，从另一个变量开始，你可能会得到不同的树。
4）决策树学习算法是基于启发式算法，如贪婪算法，寻求在每个节点上的局部最优决策。这样的算法不能保证返回全局最优决策树，比如对于NP完全问题无法给出很好的解决。
决策树模型定义
分类决策树模型是一种描述对实例进行分类的树形结构，决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或者属性，叶结点表示一个类。如西瓜书的图所示。方框形结点是内部节点，圆形结点是叶节点。
决策树的建立主要有三个阶段：特征选择、生成决策树、修剪决策树。本次先简要介绍三个阶段，后续逐渐展开细聊。
特征选择
特征选择的主要准则有信息增益或信息增益比。从信息论的角度，寻找特征中所蕴含信息价值的最大化。
策略
决策树学习用损失函数表示学习目标，通常选择正则化的极大似然估计。决策树的学习策略就是以损失函数为目标函数的最小化。
学习方法
决策树的生成算法有ID3, C4.5、CART算法等。三种方法的主要区别在于对特征重要性排序所选择的指标有区别，ID3算法用的是信息增益，C4.5算法用信息增益率；CART算法使用基尼系数。决策树方法是会把每个特征都试一遍，然后选取那个，能够使分类分的最好的特征。
三种方法对比：
- ID3的缺点，倾向于选择水平数量较多的变量，可能导致训练得到一个庞大且深度浅的树；另外输入变量必须是分类变量（连续变量必须离散化）；最后无法处理空值。
- C4.5选择了信息增益率替代信息增益。
- CART以基尼系数替代熵；最小化不纯度而不是最大化信息增益。
参考及拓展资料
- 统计学习方法，李航
- 决策树是如何工作的：http://dataaspirant.com/2017/01/30/how-decision-tree-algorithm-works/
- 机器学习，周志华
- 决策树与随机森林，https://www.cnblogs.com/fionacai/p/5894142.html
- 决策树的优缺点：https://blog.csdn.net/duxinyuhi/article/details/52786820；http://blog.csdn.net/gamer_gyt/article/details/51226904
- 决策树剪枝算法原理 损失函数 正则化：https://blog.csdn.net/bbbeoy/article/details/79469814