第十二讲 Decision Tree
决策树是一种依托策略抉择而建立起来的树，机器学习中的决策树是一种预测模型，可以用来代表对象属性与对象值之间的一种映射关系，从根节点到叶子节点所经历的路径对应一个判定测试序列
决策树可以是二叉树也可以是非二叉树，本质可以理解为 if else 语句，也可以认为是在特征空间上的条件概率分布
决策树的优点：
- 决策树算法中学习简单的决策规则建立决策模型的过程非常容易理解
- 决策树可以可视化，直观
- 应用范围广，可用于分类问题和回归问题
- 能够处理数值型样本和连续型样本
ID3算法的缺陷：
- 不能处理连续数据样本
- 不能剪枝
CD4.5算法可以：
- 处理连续数据样本
- 能够剪枝
背景内容
信息量
信息量是作为信息“多少”的度量，
- 事件A：巴西队进入了2026年世界杯决赛圈
- 事件B：中国队进入了2026年世界杯决赛圈
越不可能的事情发生，其中包含的信息量就越多，越可能的事情发生，我们能够获得的信息量就越少，因此可以认为：信息量与事情发生的概率有关（反比），
同时两个事件的信息量可以相加，并且两个独立事件的联合信息量应该是他们各自信息量的和，
信息熵（Entropy）
信息熵是接受信息量的平均值，用于确定信息的不确定程度，是随机变量的均值。信息熵越大，信息就越凌乱或传输的信息越多
条件熵
...
数据
Decision Tree 适合用来处理离散数据，解决分类问题，后面改进版的决策树也可以处理连续数据
模型
选择的模型本质上是一个 if-else 语句
损失函数
选择信息增益作为损失函数（信息增益的相反数？因为信息增益是越大越好的），但是在定义信息增益前需要先定义 Surprise.
注意：这里的log表示以2为底的对数
信息熵的定义：Surprise的期望---所有取值的概率乘以对应概率的 Surprise 值
前面学过的 ‘交叉熵’ 与这里定义的 ‘信息熵’ 是不一样的，具体区别如下：
Information Gaint 信息增益
信息增益作为损失函数，用来衡量一个特征对目标变量的影响
对于所有的指标，选择信息增益最大的作为最优特征，作为第一步的分类标准，类似下面这样，这就是ID3算法的递归过程
ID3算法是以信息论为基础，以信息熵和信息增益为衡量标准，从而实现对数据的归纳分类。
根据信息增益运用自顶向下的贪心策略是ID3建立决策树的主要方法。
运用ID3算法的主要优点是建立的决策树的规模比较小，查询速度比较快。 这个算法建立在“奥卡姆剃刀”的基础上，即越是小型的决策树越优于大的决策树。但是，该算法在某些情况下生成的并不是最小的树型结构。---引自
下图是通过计算不同特征的信息增益，来决定最优的分类特征的过程： 
Information Gain Ratio 信息增益比
ID3 算法其中的缺点：
通过信息增益发现算法倾向于选择 ‘取值结果比较多的特征’ ，但是很多时候这种情况（比如遇到连续的数据）并非最优解，因此利用信息增益做损失函数存在一些问题，同时ID3不支持剪枝。
解决方案---提出了新的优化算法：C4.5
Information gain ration is indroduced to solve the problem of ID3
It supports pruning
新的算法需要重新定义损失函数：在 信息增益
的基础上，计算除以当前特征的信息熵，得到的比值作为新的损失函数（这里其实我觉得叫评价指标可能会更好点，因为通常损失函数都是越小越好的）
C4.5其实很好理解，因为ID3的问题在于遇到特征取值很多的情况无法避开，C4.5在ID3基础上除以了当前特征的信息熵，因此可以避免特征取值过多的情况，在一定程度上将选择更 ‘理性’ 的分类指标。
面对连续的值，同一个特征可以多次用来分类： 
C4.5剪枝：前剪枝与后剪枝
C4.5的缺点：不支持回归，只能构建分类树
C4.5可以构建多叉树！
CART 决策树
引入了 Gini index 作为损失函数,但是只能构建二叉树
Gini index 越小越好
优化算法
以ID3算法为例：
因为是离散的数据，无法使用梯度下降，因此决策树采用 ‘ 贪心算法’ 来实现优化
随机选择一个特征，计算这个特征的所有可能取值，计算每个取值对应的信息增益，选择最大的信息增益（熵最小）作为最优特征
递归的构建决策树，直到满足停止条件，比如所有的数据属于同一类，或者所有的特征已经用完，或者满足停止条件
参考链接
【1】https://www.cnblogs.com/JetpropelledSnake/p/14513544.html