1 决策树模型与学习

1.1 决策树模型

  定义 5.1 (决策树) 分类决策树模型是描述对实例进行分类的树形结构。决策树由 结点 (node) 和 有向边(directed edge) 组成。结点有两种类型：内部结点与外部结点。内部结点表示一个特征或属性，外部结点表示一个类。

1.2 决策树与 if-then 规则

  可以将决策树看做一个 if-then 规则的集合。从根节点到叶节点的每一条路径都可以看做是一个规则：
  (1) 内部节点的特征对应着规则的条件；
  (2) 叶节点的类对应着规则的结论。
  这样的规则具有互斥性和完备性，即每一个实例都由一条路径覆盖，并且这个实例只能被这条路径覆盖。

   k 近邻算法可以完成很多分类任务，但是其最大的缺点是无法给出数据的内在含义。决策树由于采用 if-then 规则从而具有较好的可解释性。

1.3 决策树与条件概率分布

  决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特则空间的一个划分上。将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。

1.4 决策树学习

  给定训练数据集其中， 为输入实例， 为特征个数， 为类标记，， 为样本容量。
  ● 决策树的目标：根据给定数据集构建一个决策树模型，使它能够对实例进行正确的分类；
  ● 决策树学习的本质：从训练集中归纳出一组分类规则，或者说是由训练数据集估计条件概率模型；
  ● 决策树学习的损失函数：正则化的极大似然函数；
  ● 决策树的学习算法包含特征选择、决策树的生成与决策树的剪枝三个过程；
  ● 决策树学习常用的算法有 ID3、C4.5 与 CART。

2 特征选择

  特征选择在于选取对训练数据集具有分类能力的特征，这样可以提高决策树学习的效率。通常特征选择的准则是信息增熵或信息增益比。

2.1 信息增益

• 信息熵
    信息熵 (entropy) 是表示随机变量不确定性的度量。熵越大，则随机变量的不确定性就越大。设 是一个取有限值的离散随机变量，其概率分布为则随机变量 的熵定义为：若有 0 概率，则定义 。 通常，式中的对数以 2 为底或以 为底，这是熵的单位分别称为比特 (bit)或纳特 (nat)。由于熵只依赖于 的分布，而与 的取值无关，故也可将 的熵记作 。从定义验可验证 。

这里给出 的证明：
证明：
  信息熵的非负性是显然的，这里只证明。这个证明是容易的：不妨设 以自然对数为底，那么  因此，根据对数不等式取等号的条件，，即 当且仅当 ， 时，等号成立。Q.E.D.

• 条件信息熵
    设有随机变量 ，其联合概率分布为  条件熵 (conditional entropy) 表示在已知随机变量 的条件下随机变量 的不确定性，定义为 给定条件 的条件概率分布的熵对 的数学期望这里 ，。若有 0 概率，则定义 。

  当熵和条件熵中的概率由数据估计（尤其是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵。

• 信息增益
    信息增益 (information gain) 表示得知特征 的信息而使得类 的信息的不确定性减少的程度。
    定义 5.2 (信息增益) 特征 对训练数据集 的信息增益 ，定义为集合 对经验熵 与特征 给定条件下 的经验条件熵 之差，即  一般的，熵 与条件熵 之差称为互信息 (mutual information)。
    决策树学习应用信息增益准则选择特征。由于信息增益表示一个特征对数据集的分类的不确定性减少的程度，故信息增益越大的特征往往具有更强的分类能力。

• 更多有关熵、条件熵、信息增益的数学性质可参考：熵、条件熵和互信息的性质
• 如果不理解熵、条件熵、信息增益的概念可参考：通俗理解信息增益

2.2 信息增益比

  以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比 (information gain ratio) 可以对这一问题进行校正。这是特征选择的另一准则。
  定义 5.2 (信息增益比) 特征 对训练数据集 的信息增益比 ，定义为信息增益 与训练数据集 关于特征 的值的熵 之比，即其中，， 为特征 的取值的个数。

3 决策树的生成

3.1 ID3 算法与 C4.5 算法

  从第 2 小节信息论相关的知识中我们知道：信息熵越大，从而样本纯度越低。ID3 算法的核心思想就是在决策树的各个结点以信息增益准则来进行特征选择，递归地构建决策树。 其大致步骤为：
  (1) 从根结点开始，对结点计算所有可能的特征的信息增益；
  (2) 选择信息增益最大的特征作为该结点的特征；
  (3) 根据步骤 (2) 所选取特征的不同取值建立子节点（即按照特征的取值来划分不同分支的数据集合)，再对子节点递归地调用步骤 (1)；
  (4) 重复上述步骤，若子集只包含单一特征或子集中的信息增熵小于阈值，则设为单节点。直至生成最后一棵单节点决策树。

从 ID3 算法的具体步骤我们分析不难发现其可能具有如下缺点：

• 采用信息增益准则对可取值数目较多的特征有所偏好 (如类似“编号”的特征)；
• 只能用于处理离散分布的特征 (这是因为连续分布的特征取值数目会很大)；

  为了克服 ID3 的上述缺点，我们可以采取如下方法：
  (1) 对于特征取值数目的偏重这一缺点，采用引入信息增益比作为分类标准的 C4.5 算法来进行决策树的生成；
  (2) 对于无法处理连续分布的特征，可以将连续特征离散化，C4.5 算法中采用的方法如下：先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分类点。

  信息增益率对可取值较少的特征有所偏好（分母越小，整体越大)，因此实际上 C4.5 算法可以采用一种类似于启发式方法进行改进：先从特征中找到信息增益高于某一阈值（如平均值）的特征，再从中选择信息增益率最高的。

4 决策树的剪枝

  决策树的剪枝处理——从已经生成的决策树上裁掉一些子树或者叶节点，并将其根节点或者父节点作为新的叶节点，从而简化分类树模型。
  决策树的剪枝往往通过极小化决策树整体的损失函数来实现。设树 的叶结点个数为 ， 是树 的叶结点，该叶结点有 个样本点，其中 类样本点有 个，， 为叶结点 上的经验熵， 为参数，则决策树学习的损失函数可以定义为其中经验熵为  不难发现，上式定义的损失函数极小化等价于正则化的极大似然估计。

5 CART 算法

  CART (classification and regression tree)：分类与回归树，可以用于分类与回归。
  CART 是在给定输入随机变量 条件下输出随机变量 的条件概率分布的学习方法。CART 假设决策树是二叉树，这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

5.1 CART 生成

  决策树的生成就是递归地构建二叉树的过程，对回归树用平方误差最小准则，对分类树用基尼指数最小化准则。
  1. 回归树的生成
  算法 5.5 (最小二乘回归树生成算法)
  输入：训练数据集 ；
  输出：回归树 ；
  在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域的输出值，构建二叉决策树：
  (1) 选择最优切分变量 与切分点 ，求解  遍历变量 ，对固定的切分变量 扫描切分点 ，选择使上式达到最小的 ；
  (2) 对选定的 划分区域并决定相应的输出值：   (3) 继续对两个子区域调用步骤 (1)，(2)，直至满足停止条件；
  (4) 将输入空间划分为 个区域 ，生成决策树：
  2. 分类树的生成
  定义 5.4 (基尼指数) 分类问题中，假设有 个类，样本点属于第 类的概率为 ，则概率分布的基尼指数定义为对于二分类问题，若样本点属于第一个类的概率是 ，则概率分布的基尼指数为对于给定的样本集合 ，其基尼指数为这里， 是 中属于第 类的样本子集， 是类的个数。
  若样本集合 根据特征 是否取某一可能值 被分割成 和 两个部分，即则在特征 的条件下，集合 的基尼指数定义为基尼指数 表示集合 的不确定性，基尼指数 表示集合 经过 分割后的不确定性。基尼指数越越大，表示样本集合的不确定性也就越大。

  算法 5.6 (CART 生成算法)
  输入：训练数据集 ，停止计算的条件；
  输出：CART 决策树；
  (1) 计算现有特征对数据集的基尼指数，对每一个特征 ，对其可能取的每个值 ，将 划分成 与 ，计算 时的基尼指数。
  (2) 在所有可能的特征 以及它所有可能的切分点 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。根据其将数据分配到两个子节点中去。
  (3) 对两个子节点递归地调用 (1)，(2)，直至满足停止条件。
  (4) 生成 CART 决策树
  算法的停止条件是节点中的样本个数小于阈值，或样本集的基尼指数小于预定阈值，或者没有更多的特征。

5.2 CART 剪枝

  算法 5.7 (CART 剪枝算法)
  输入：CART 算法生成的决策树；
  输出：最优决策树 ；
  (1) 设 ，；
  (2) 设 ；
  (3) 自下而上地对各内部结点 计算 ， 以及  其中， 表示以 为根结点的子树， 为预测误差， 为 的叶结点个数；
  (4) 对 的内部结点 进行剪枝，并以多数表决法决定其类，得到树 ；
  (5) 设 ，，；
  (6) 若 不是由根节点及两个叶结点构成的树，则回到步骤 (2)；否则令
  (7) 采用交叉验证法在子树数列 中选取最优子树 。

6 习题

习题6.1 根据表 5.1 所给训练集，运用 C4.5 算法生成决策树。
解：
(1) 根据例题 5.2，我们得到：
数据集 的经验熵：
(年龄) 对数据集 的信息增益：
(有工作) 对数据集 的信息增益：
(有自己的房子) 对数据集 的信息增益：
(信贷情况) 对数据集 的信息增益：

(2) 计算数据集 关于各个特征 ， 的值的熵：

(3) 计算各特征对数据集 的信息增益比：

(4) 由于特征 (有自己的房子) 的信息增益比最大，所以选择特征 作为根节点的特征。它将训练数据集 划分为两个子集 ( 取值为“是”) 和 ( 取值为“否”)。由于 只有同一类的样本点，所以它成为一个叶结点，结点的类标记为“是”。

(5) 对 则需从特征 中选择新的特征。根据例题 5.3，我们得到：
(年龄) 对数据集 的信息增益：
(有工作) 对数据集 的信息增益：
(信贷情况) 对数据集 的信息增益：

(6) 计算数据集 关于各个特征 的值的熵：

(7) 计算各特征对数据集 的信息增益比：

(8) 由于特征 (有工作) 的信息增益比最大，所以选择特征 作为叶结点的特征。它将训练数据集 划分为两个子集 ( 取值为“是”) 和 ( 取值为“否”)。由于 , 都只有同一类的样本点，所以它们分别成为一个叶结点，结点的类标记分别为“是”和“否”。

 这样我们就采用 C4.5 算法构建了一个决策树，这个决策树只用了两个特征。

|--- 有自己的房子
|   |--- class: 否
|   |   |--- 有工作
|   |   |   |--- class: 否
|   |   |--- 有工作
|   |   |   |--- class: 是
|--- 有自己的房子
|   |--- class: 是