1、决策树
1.1、决策树的概念
决策树是一个有监督的分类模型，本质是选择一个最大信息增益的特征值对树进行分割，直到到达结束条件或者叶子结点纯度到达一定阈值。
是二分类器
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。
1） 开始：构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按着这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。
2） 如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。
3）如果还有子集不能够被正确的分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如果递归进行，直至所有训练数据子集被基本正确的分类，或者没有合适的特征为止。
4）每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。
1.1 应用场景
可以用以解决二分类和多类别分类的分类的问题以及回归的问题。
2、预备知识：信息熵
信息熵可以决定哪个做父节点
信息熵表示随机变量的不确定性，也就是随机变量的复杂du，因此条件熵越小，表示数据集X的纯度越大
公式：
二元的信息熵函数图像.png
从函数图像可以看到当 P1 取值为 0.5 时，因为是二元分类，则另外一个概率（P2）为 1-0.5 = 0.5 时，信息熵函数取最大值，则说明当信源不确定性越大时，其信息熵越大。
信息增益（information gain）：可以用于表示为划分前的信息熵值减去划分后的信息熵值。则可以得出如果信息增益越大，则代表划分后不确定性越小，则叶子节点的类别越肯定。
3、算法介绍
3.1、ID3 算法
算法步骤【以特征值为离散的情况举例】：
1、从整个数据集中遍历 n 个特征值，依据各个特征属性的不同取值划分数据集，并计算每个特征值划分前后所对应的信息增益，选择信息增益最大所对应特征属性进行划分数据集；
2、遍历所划分各个子节点，重复步骤1，直到节点中所有类别一致或没有可以接着划分的特征属性，并将该节点设为叶子节点，将多数的类别作为该节点的类别。
3.2、c4.5 算法
C4.5 算法最大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准
基于信息增益率准则选择最优分割属性的算法
信息增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的属性。
信息增益率对可取值较少的特征有所偏好（分母越小，整体越大），因此 C4.5 并不是直接用增益率最大的特征进行划分，而是使用一个启发式方法：先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的
剪枝
剪枝2分为预剪枝和后剪枝
预剪枝：预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险
节点内数据样本低于某一阈值；
所有节点特征都已分裂；
节点划分前准确率比划分后准确率高。
后剪枝:后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。
缺点
剪枝策略可以再优化；
C4.5 用的是多叉树，用二叉树效率更高；
C4.5 只能用于分类；
C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行
3.3、CART 算法
CART全称为 classification and Regression Tree，即说明这个算法可以用于解决分类问题和回归拟合问题。其中需要说明的一点是CART树假设决策树是二叉树，内部节点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间及特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
算法步骤如下：
1、设节点的训练数据集为：D，计算现有特征对该数据集的信息熵。并对每一个特征，对其可能取的每个值，根据样本点对的测试为“是”或“否”将分割成两部分，以及计算所对应的信息熵；
2、在所有可能的特征以及它们所有可能的且分店中，选择信息增益最大的特征及其对应的切分点。依据最优特征与最优切分点，从现节点生成连个子节点，将训练数据集D依特征分配到两个子节点中去。
3、对两个子节点递归地调用步骤1~2，直至满足停止条件。
4、生成 CART 决策树。
备注：算法停止计算的条件是节点中的样本个数小于预定阈值，或样本集的信息增益小于预定阈值（样本基本属于同一类），或者没有更多特征。
4、信息熵的替换算法
前面三种算法均采用了信息熵来作为数据集划分的依据，但我们也可以采用 Gini index 和 misclassification ERROR来替换信息熵，下面分别介绍一下两个函数：
4.1、基尼指数
Gini index 函数公式如下：
其可以用于CART、SLIQ和SPRINT。
当一个节点 p 被切分成 K 个分支时，衡量切分的好坏的公式如下：
衡量切分后的 Gini index 公式.png
其中：
- ni = 子节点 i 的样本数量
- n = 节点 P 的样本数量
备注：其中切分后的 Gini Index 函数值越小，其切分效果越好。
4.2、misclassification ERROR
其公式如下：
