机器学习西瓜书（周志华）第四章 决策树_西瓜书第四章课后答案

1. 概述

       决策树（decision tree）是一种基本的分类与回归方法。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合（互斥并且完备），也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据利用决策树模型进行分类。决策树学习通常包括三个步骤：特征选择、决策树的生成和决策树的修剪。

• 特征选择：从训练数据的特征中选择一个特征作为当前节点的分裂标准（特征选择的标准不同产生了不同的特征决策树算法）。
• 决策树生成：根据所选特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止声场。
• 决策树剪枝：决策树容易过拟合，需要剪枝来缩小树的结构和规模（包括预剪枝和后剪枝）。

决策树学习的本质是从训练数据集中归纳出一组分类规则或者说是条件概率模型，与训练数据集不相矛盾的决策树可能有多个或者一个没有，我们需要找到一个与训练数据集矛盾较小的决策树，同时具有很好的泛化能力。换句话说，我们选择的条件概率模型应该不仅对现有的训练数据集有很好的拟合效果，而且能够对未知的数据有很好的预测（泛化能力）。实现的方法通过以上的三个方法。
决策树特点：

优点：

• 计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
• 准确性高: 挖掘出来的分类规则准确性高, 便于理解, 决策树可以清晰的显示哪些字段比较重要, 即可以生成可以理解的规则。
• 可以处理连续和离散字段
• 不需要任何领域知识和参数假设
• 适合高维数据
  缺点：
• 对于各类别样本数量不一致的数据, 信息增益偏向于那些更多数值的特征
• 容易过拟合
• 忽略属性之间的相关性

适用数据类型：数值型和标称型

2. 特征选择

特征选择决定用哪个特征来划分空间，即如何选择最优划分属性。在划分的过程中，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。
特征选择的准则：信息增益、信息增益比（增益率）、基尼指数

数据集

2.1 信息增益

熵是表示随机变量不确定性的度量。熵只依赖于D的分布，与D的取值无关。

信息增益表示在得知特征D的属性对应的属性值的种类和个数a后，而使得类信息不确定性的减少程度。
熵（不确定性）与条件熵（知道信息以后可确定的部分）之差称为互信息，决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
信息增益准则的特征选择方法：对于训练集，计算每个特征D的信息增益，选择信息增益最大的特征作为特征选择的属性。

2.2 信息增益率

为什么引入信息增益率？
这是为了解决信息增益的使用过程中，对属性值种类较多的属性比较偏好，这个问题，所以引入信息增益率。比如当误把编号当成属性时，此时条件熵为0，信息增益达到最大，因此将选择编号作为分类的一个属性，这显然是不合理的。

需要注意的是，信息增益率对属性值较少的属性比较偏好，因此，C4.5算法并不是直接选择增益率最大的作为候选划分属性，而是使用一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性（保证属性值多的属性被选择），再从中选择增益率最高的（在属性值多的属性中挑属性值少的属性），这样是保证了相对准确。

2.3 基尼指数

3. 决策树生成

决策树生成算法：

输入：训练数据集D，特征集A，阈值ε（预剪枝用，后剪枝不需要此项）；

输出：决策树T。

（1）若D中所有样本属于同一类$C_k$,则 T 为单结点树，并将$C_k$作为该结点的类标记，返回T；

（2）若A = Ø,则T为单结点树，并将D中样本数最多的类$C_k$作为该结点的类标记，返回T；

（3）否则，计算A中各个特征对D的信息增益或者信息增益比，选择信息增益或信息增益比最大的特征 $A_g$；

（4）如果 $A_g$ 的信息增益或信息增益比小于阈值ε，则置T为但结点树，并将D中样本数最多的类Ck作为该结点的类标记，返回T；（后剪枝没有这步）

（5）如果 $A_g$的每一种可能值 $a_i$，依 $A_g=a_i$