决策树
决策树（Decision Tree）是一种简单但是广泛使用的分类器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。
决策树的损失函数通常是正则化的极大似然函数决策数有两大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。
决策树的生成算法有ID3、C4.5和CART三种算法。
以信息熵为度量，构造一颗熵值下降最快且树高度最矮的决策树模型。
决策树学习的目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。
决策树学习的本质：从训练集中归纳出一组分类规则，或者说是由训练数据集估计条件概率模型。
决策树学习的损失函数：正则化的极大似然函数
决策树学习的测试：最小化损失函数
决策树学习的目标：在损失函数的意义下，选择最优决策树的问题。
节点划分准则
1、信息增益
对于训练数据集D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
2、信息增益比
以信息增益作为划分训练集的特征，存在偏向于选择取值较多的特征的问题。
需要注意的是，增益率准则对可取值数目较少的属性有所偏好。因此，C4.5算法并不是直接选择增益率最大的候选划分属性。而是使用了一个启发式先从候选划分属性中找出信息增益高于平均水平的属性，再从
中选择增益率最高的。
3、基尼系数
基尼值反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，其值越小，数据集的纯度越高。
我们在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。
生成算法
1、ID3算法
2、C4.5算法
C4.5算法对ID3算法进行了改进，用信息增益比来选择特征。ID3算法只能处理离散属性，C4.5采用信息增益率作为分裂准则，采用二分法对连续属性进行处理。
决策树的损失函数
决策树的剪枝
1、预剪枝
(1) 一种最为简单的方法就是在决策树到达一定高度的情况下就停止树的生长。
(2) 到达此结点的实例具有相同的特征向量，而不必一定属于同一类， 也可停止生长。
(3) 到达此结点的实例个数小于某一个阈值也可停止树的生长。
(4) 还有一种更为普遍的做法是计算每次扩张对系统性能的增益，如果这个增益值小于某个阈值则不进行扩展。
2、后剪枝(参考链接：https://www.cnblogs.com/yonghao/p/5064996.html)
(1) REP-错误率降低剪枝
该剪枝方法是根据错误率进行剪枝，如果一棵子树修剪前后错误率没有下降，就可以认为该子树是可以修剪的。
REP剪枝需要用新的数据集，原因是如果用旧的数据集，不可能出现分裂后的错误率比分裂前错误率要高的情况。由于使用新的数据集没有参与决策树的构建，能够降低训练数据的影响，降低过拟合的程度，提高预测的准确率。
(2) PEP-悲观剪枝法
悲观剪枝认为如果决策树的精度在剪枝前后没有影响的话，则进行剪枝。怎样才算是没有影响？如果剪枝后的误差小于剪枝前经度的上限，则说明剪枝后的效果与剪枝前的效果一致，此时要进行剪枝。
(3) CCP-代价复杂度剪枝
代价复杂度选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。
实际上这个g(t)表示剪枝的阈值，即对于某一结点a，当总体损失函数中的参数alpha = g(t)时，剪和不剪总体损失函数是一样的（这可以在书中（5.27）和（5.28）联立得到）。
这时如果alpha稍稍增大，那么不剪的整体损失函数就大于剪去的。即alpha大于g(t)该剪，剪了会使整体损失函数减小；alpha小于g(t)不该剪，剪了会使整体损失函数增大。
（请注意上文中的总体损失函数，对象可以是以a为根的子树，也可以是整个CART树，对a剪枝前后二者的总体损失函数增减是相同的。）对于同一棵树的结点，alpha都是一样的，
当alpha从0开始缓慢增大，总会有某棵子树该剪，其他子树不该剪的情况，即alpha超过了某个结点的g(t)，但还没有超过其他结点的g(t)。这样随着alpha不断增大，不断地剪枝，就
得到了n+1棵子树，接下来只要用独立数据集测试这n+1棵子树，试试哪棵子树的误差最小就知道那棵是最好的方案了。
（原文链接：https://blog.csdn.net/zhengzhenxian/article/details/79083643）
连续值与缺失值
连续值
（参考链接：https://blog.csdn.net/u012328159/article/details/79396893）
由于连续属性的可取值数目不再有限， 因此，不能直接根据连续属性的可取值来对结点进行划分.此时连续属性离散化技术可派上用场 . 最简单的策
略是采用 二分法(bi-partition)对连续属性进行处理，这正是 C4.5决策树算法中采用的机制。需注意的是，与离散属性不同，若当前结点划分属性为连续属性?该属性还
可作为其后代结点的划分属性。
缺失值
（参考链接：https://blog.csdn.net/u012328159/article/details/79413610）
在决策树中处理含有缺失值的样本的时候，需要解决两个问题：
1） 如何在属性值缺失的情况下进行划分属性的选择？（比如“色泽”这个属性有的样本在该属性上的值是缺失的，那么该如何计算“色泽”的信息增益？）
2） 给定划分属性，若样本在该属性上的值是缺失的，那么该如何对这个样本进行划分？（即到底把这个样本划分到哪个结点里？）
决策树处理缺失值时，先计算无缺失样本的信息增益，选取信息增益最大的特征为划分节点，赋予正常样本的权值为1，赋予缺失样本的权值为N/N1,N为叶子节点中无缺失样本的数目，
N1为无缺失样本在该特征值上的样本数。
如果测试样本属性也有缺失值，C4.5中采用的方法是：测试样本在该属性值上有缺失值，那么就同时探查（计算）所有分支，然后算每个类别的概率，取概率最大的类别赋值给该样本。
CART算法
CART算法中决策树的生成就是递归地构建二叉决策树的过程，对回归树用平方误差最小化准则，对分类数用基尼系数最小化准则进行特征选择。
回归树
取划分空间内y的平均值作为叶子节点的输出值。
分类树
1、选用基尼系数作为划分准则的原因：
1） 在二分类过程中，基尼系数和熵之半的曲线很接近，都可以近似地代表分类误差率。
2） 使用基尼系数，计算量小。
2、对连续值和离散值的处理
1） CART分类树算法对连续值的处理，思想和C4.5相同，都是将连续的特征离散化。唯一区别在选择划分点时，C4.5是信息增益比，CART是基尼系数。
2） CART分类树算法对离散值的处理，采用的思路：不停的二分离散特征。
优缺点
优点：
简单直观，生成的决策树很直观。
基本不需要预处理，不需要提前归一化和处理缺失值。
使用决策树预测的代价是O(log2m)。m为样本数。
既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
可以处理多维度输出的分类问题。
相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以很好解释。
可以交叉验证的剪枝来选择模型，从而提高泛化能力。
对于异常点的容错能力好，健壮性高。
缺点：
决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
决策树会因为样本发生一点的改动，导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
寻找最优的决策树是一个NP难题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习的方法来改善。
有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。
