b站 5分钟学算法 决策树
CSDN 决策树原理详解

1 简介

决策树（Decision Tree），它是一种以树形数据结构来展示决策规则和分类结果的模型，作为一种归纳学习算法，其重点是将看似无序、杂乱的已知数据，通过某种技术手段将它们转化成可以预测未知数据的树状模型，每一条从根结点（对最终分类结果贡献最大的属性）到叶子结点（最终分类结果）的路径都代表一条决策的规则。例：

2 决策树基本流程

1. 开始位置，将所有数据划分到一个节点，即根节点。
2. 经历橙色的两个步骤，橙色的表示判断条件： 若数据为空集，跳出循环。如果该节点是根节点，返回null；如果该节点是中间节点，将该节点标记为训练数据中类别最多的类。 若样本都属于同一类，跳出循环，节点标记为该类别；
3. 如果经过橙色标记的判断条件都没有跳出循环，则考虑对该节点进行划分，选择当前条件下的最优属性划分
4. 经历上步骤划分后，生成新的节点，然后循环判断条件，不断生成新的分支节点，直到所有节点都跳出循环。
5. 结束。这样便会生成一棵决策树。

3 决策树划分依据（寻找最优划分属性）

3.1 算法ID3（信息增益）

1. 信息熵：信息熵描述随机变量的不确定性（也就是混乱程度）。信息熵越大越混乱。 假设某随机变量的概率分布为：
   则它的信息熵计算公式为：
2. 信息增益（表示决策树的样本集，经过某属性划分后，样本集划分为个子集，）
   其中为划分前的信息熵，，表示第i类别的样本数占总样本数D的比例。 ，表示该属性第i个值的样本数。相当于用色泽划分样本集D，样本集D中色泽=青绿的样本数。可以想象成一个权重。的计算方法同。
   

3.2 算法C4.5（信息增益+增益比）

1. 算法ID3的不足：信息增益虽然在理论上可以找到最优的划分属性，但在某些情况下会存在问题。信息增益比较偏好可取值较多的属性，比如我们的样本有一个属性叫序号，每一个样本都具有一个单独的序号，因此使用序号划分后，每个子结点只有一个样本，熵为0。这样的话信息增益最大，算法就会以此属性作为最优划分属性。这显然与我们的意愿不同。因此引申出了增益比的思想。 可以这么说，增益比就是为了矫正信息增益偏好的问题，为了使算法不偏向可取值较多的属性。
2. 增益比：
   其中
   是属性a的固有属性，当属性a可取值增多的时候，一般也增大，因此在一定程度上能抑制信息增益偏好取值多的属性的特点，但是增益比偏好取值较少的属性。
   

3.3 CART决策树（基尼系数）

1. 基尼系数： 可以看出，基尼指数与信息熵虽然值不同，但是趋势一致。同样的，使用基尼指数来选择最优划分属性也是对比不同属性划分后基尼指数的差值，选择使样本集基尼指数减小最多的属性。
2. CART决策树与ID3和C4.5的区别
   1. 划分准则不同，如刚才所说，CART决策树使用基尼指数。
   2. ID3、C4.5划分时，一个节点可以划分为多个子结点，子结点数量根据属性可取值的数量决定。而CART决策树是严格的二叉树结构，就是说1个节点最多划分为2子结点。用下图可以浅显的解释

剪枝处理

如果按照我们之前的方法形成决策树后，会存在一定的问题。决策树会无休止的生长，直到训练样本中所有样本都被划分到正确的分类。实际上训练样本中含有异常点，当决策树节点样本越少的时候，异常点就可能使得该结点划分错误。另外，我们的样本属性并不一定能完全代表分类的标准，可能有漏掉的特征，也可能有不准确的特征。这样就会导致决策树在训练集上准确率超高，但是在测试集上效果不好，模型过拟合，泛化能力弱。因此我们需要适当控制决策树的生长。 剪枝处理是防止决策树过拟合的有效手段。剪枝，其实就是把决策树里不该生长的枝叶剪掉，也就是不该划分的节点就不要继续划分了。剪枝分为“预剪枝”和“后剪枝”。两种操作在决策树生辰步骤的位置如下图：

1. 预剪枝：在决策树生成过程中，对每个结点在划分前先进性估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。它的位置在每一次生成分支节点前，先判断有没有必要生成，如没有必要，则停止划分。
2. 后剪枝：先从训练集生成一棵完整的决策树（相当于结束位置），然后自底向上的对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点，相当于将子树剪去。值得注意的是，后剪枝时要用到一个测试数据集合，如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子。
3. 理论上讲，后剪枝生成的决策树要比预剪枝生成的效果好，但是后剪枝在计算复杂度上比预剪枝高。