1 决策树
决策树通过树结构存储判断流程和规则，实现复杂规则的有效记录
一般来说，树的非叶节点存储了判断逻辑，并通过树分支表达多个判断结果 通过自上而下的多层逻辑判断，最终在叶节点输出预测的分类结果
决策树示例：
1.1 决策树ID3算法
ID3算法主要利用信息增益进行特征的选择，并通过递归方法构建特征
- 从根节点开始，计算所有特征的信息增益
- 选择信息增益最大的特征作为此节点的判断逻辑，并构建子节点
- 对子节点递归地调用以上方法，直到最大信息增益过低或没有特征停止递归
- 将叶节点的最大概率结果作为预测结果进行输出
ID3算法缺点：
- 不适用于连续型数据
- 倾向于选择类别多的特征
- 没有考虑缺失值的情况
- 可能会出现过拟合的情况
1.2 决策树 C4.5算法
C4.5算法主要用于修正 决策树ID3算法的几个关键缺陷，并作出了几下几处改进：
- 对连续型特征进行离散化处理
- 使用信息增益比取代信息增益
- 对缺失值进行特定的修正
- 引入了正则化系数进行初步的剪枝
缺失值处理细节：
缺失值处理主要需要解决的是两个问题，一是如何在某特征缺失的情况下选择最优的划分属性，二是选定了划分属性，如何处理在该属性上缺失特征的样本。
对于第一个子问题，对于某一个有缺失特征值的特征A。C4.5的思路是对每个样本设置一个权重（初始可以都为1），然后根据特征A无缺失部分的数据集计算加权重后的信息增益比，最后乘上一个系数（特征A无缺失数据的占比）进行修正
对于第二个子问题，可以将缺失特征的样本同时进入后续的所有子节点，并选择叶节点概率最高的分支作为最终结果。需要注意的是该样本的权重会按各个子节点样本的数量比例进行调整。比如缺失特征A的样本a之前权重为1，特征A有3个特征值A1,A2,A3。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则a将同时划分入A1，A2，A3。对应权重调节为2/9,3/9, 4/9。
C4.5仍然有优化的空间
- 剪枝方法有优化的空间，比如预剪枝和后剪枝
- C4.5采用多叉树，允许效率低于二叉树
- C4.5只适用于分类问题，不能用于解决回归问题
- C4.5包含连续型变量的处理以及大量熵相关计算，存在运算性能的优化空间
1.3 CART 算法
CART的全称是Classification And Regression Tree，也就是分类与回归树
1.3.1 分类树
在ID3算法中我们使用了信息增益来选择特征，信息增益大的优先选择。
在C4.5算法中，采用了信息增益比来选择特征，以减少信息增益容易选择特征值多的特征的问题。
但是无论是ID3还是C4.5,都是基于信息论的熵模型的，这里面会涉及大量的对数运算。因此CART分类树算法使用基尼系数来代替信息增益比，起到简化计算的作用。基尼系数越高，信息越不纯，所以最佳特征的选择策略为基尼系数最小。
对于连续特征处理的改进：
- 比如m个样本的连续特征A有m个，从小到大排列为$a_1,a_2,...,a_m$，则CART算法取相邻两样本值的平均数作为划分点，一共可取得m-1个划分点
- 对于这m-1个点，分别计算以该点作为二元分类点时的基尼系数。选择基尼系数最小的点作为该连续特征的二元离散分类点，这样就实现了连续特征的离散化。
对于离散特征处理的改进：
- 用多个二叉树取代多叉树
- 提高模型的运算性能
1.3.2 回归树
两者的区别在于样本输出，分类树的样本输出是离散值，而回归树的样本输出是连续值。
CART回归树不同于CART分类树的主要两点
- 连续值的处理方法不同，回归树在取得m-1个划分点后，会对划分后的两份数据分别计算均方差，并找到均方差之和最小所对应的特征和特征值划分点
- 预测结果的输出方式不同，回归树的结果是最终叶节点的均值或者中位数
1.3.3 CART的剪枝
决策时算法很容易出现过拟合的问题，导致泛化能力差
为了解决这个问题，我们需要对CART树进行剪枝
剪枝类似于线性回归的正则化，可以用来增加决策树的泛化能力
CART采用的办法是后剪枝法
- 先生成决策树，然后通过调整参数$\alpha$产生所有可能的剪枝后的CART树
- 使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略
剪枝的损失函数度量 $$C_a(T_t)=C(T_t)+\alpha |T_t|$$
- $\alpha$为正则化参数，$\alpha\to 0$时最优子树为原始树，$\alpha\to \infty$时最优子树为根节点
- $C(T_t)$为训练数据的预测误差，分类树是用基尼系数度量，回归树是均方差度量
- $|T_t|$是子树T的叶子节点的数量
CART树的交叉验证策略
- 计算出每个子树是否剪枝的阈值$\alpha$
- 针对不同的$\alpha$所对应的剪枝后的最优子树做交叉验证
- 选择验证结果最优的子树作为最终结果
1.3.4 CART算法总结
修正：ID3算法应该是支持剪枝的
CART算法的缺点
- 只选择一个最优特征的用于分类决策，有时最优决策可能是一组特征决定的
- 样本的细微扰动，可能会导致CART树结构的剧烈变化，不够稳健鸭
2 决策树算法总结
决策树算法的优点：
- 简单直观，生成的决策树很直观
- 基本不需要预处理，不需要提前归一化，处理缺失值
- 使用决策树预测的代价是$O(log_2(n))$。 n为样本数
- 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值
- 可以处理多维度输出的分类问题
- 相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
- 可以交叉验证的剪枝来选择模型，从而提高泛化能力。
- 对于异常点的容错能力好，健壮性高。
决策树算法的缺点:
- 决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
- 决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
- 寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
- 有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
- 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。