决策树学习笔记

决策树的基本流程

参考决策树（上）——ID3、C4.5、CART（非常详细）
决策树（亦称判定树）是一个非常常见并且优秀的机器学习算法，它易于理解、可解释性强，其可作为分类算法，也可用于回归模型。

其基本流程遵循简单的“分而治之”（divide-and-conquer）策略，如下图所示。

根据上面的分析可知，必须解决三个问题，划分的选择、连续与缺失值、剪枝处理。

1. 由第8行可知我们必须选择一最优化分属性，常用的划分指标有三种（信息增益、增益率、基尼指数），对应三种算法（ID3,C4.5,CART）。

2. 当我们进行划分时，遇到属性值是连续值或者缺失值的时候我们需要连续值与缺失值处理技术。

3. 当决策树建好之后，预测问题便成了树的查找问题，因此我们希望建立树的高度低的决策树，更重的要是，决策树的分支过多会导致“过拟合”，因此有必要进行剪枝处理，基本的剪枝处理有预剪枝和后剪枝

传统的决策树的划分是基于单一属性的，我们用多个属性的线性组合进行划分可以产生更加复杂的决策树，这种类型的决策树称为多变量决策树。

划分的选择

​ 一般而言，随着划分的不断进行，我们希望决策树的分支点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。

1. 信息增益

优缺点

**信息增益准则最可取值数目多的属性有所偏好 **

2. 增益率

优缺点

1. 增益率准则对可取值数目少的属性有所偏好

2. 增益率准则倾向于不平衡的分裂，其中一个子集比其他小得多

C4.5并不是直接选取增益率大的作为候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

3. 基尼指数

优缺点

1. 偏向于多值属性

2. 当类数目较大时，计算困难

3. 倾向于导致大小相等的分区和纯度

三种算法

1. ID3

ID3 算法是建立在奥卡姆剃刀原理（如无必要，勿增实体）的基础上：越是小型的决策树越优于大的决策树。

1.1 思想

从信息论的知识中我们知道：信息熵越大，从而样本纯度越低，。ID3 算法的核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间（C4.5 也是贪婪搜索）。 其大致步骤为：

1. 初始化特征集合和数据集合；
2. 计算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点；
3. 更新数据集合和特征集合（删除上一步使用的特征，并按照特征值来划分不同分支的数据集合）；
4. 重复 2，3 两步，若子集值包含单一特征，则为分支叶子节点。

1.2 划分标准

ID3 使用的分类标准是信息增益

1.3 缺点

• ID3 没有剪枝策略，容易过拟合；
• 信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
• 只能用于处理离散分布的特征；
• 没有考虑缺失值。

2. C4.5

C4.5 算法最大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准。C4.5并不是直接选取增益率大的作为候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

2.1 思想

C4.5 相对于 ID3 的缺点对应有以下改进方式：

• 引入悲观剪枝策略进行后剪枝；
• 引入信息增益率作为划分标准；
• 将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；
• 对于缺失值的处理可以分为两个子问题：
• 问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）
• 问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）
• 针对问题一，C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
• 针对问题二，C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值（乘以每一属性值的样本所占样本集的比重），其实也就是以不同概率划分到不同节点中。

2.2 划分标准

利用信息增益率可以克服信息增益的缺点。C4.5并不是直接选取增益率大的作为候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

2.3 剪枝策略

为什么要剪枝：过拟合的树在泛化能力的表现非常差。

2.3.1 预剪枝

主要思想：在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分，并标记为叶节点

在节点划分前来确定是否继续增长，及早停止增长的主要方法有：

• 节点内数据样本低于某一阈值；
• 所有节点特征都已分裂；
• 节点划分前准确率比划分后准确率高。
  

2.3.2 后剪枝

主要思想： 后剪枝是先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点

C4.5 采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。

2.4 缺点

• 剪枝策略可以再优化；
• C4.5 用的是多叉树，用二叉树效率更高；
• C4.5 只能用于分类；
• C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
• C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

3. CART 树怎么进行剪枝?
4. 决策树（上）——ID3、C4.5、CART（非常详细）