ML-决策树

概要

决策树（decision tree）是一种基本的分类和回归方法。其主要呈现为树状结构，在分类问题中，表示基于特征对实例进行分类的过程，可以被认为是 if-then 的规则集合，也可以被认为是定义在特征空间与类空间上的条件概率分布。

其优点主要有分类速度快、模型具有可读性，在学习时利用训练数据根据损失函数最小化的原则建立决策树模型；而在预测时对新的数据利用决策树模型进行分类。

决策树模型主要包含以下步骤：

特征选择
决策树的生成
决策树的修剪

决策树

决策树模型

分类决策树模型是一种描述对实例进行分类的树状结构。决策树有结点（node）和有向边（directed edge）组成，结点有两种类型：内部结点（internal node）和叶结点（leaf node），其中内部结点表示一个特征或属性，叶结点表示一个类。

用决策树分类，首先从根结点开始对实例的某一个特征进行测试，根据测试结果将实例分配到其子结点上，每个子结点对应着一个特征的取值。如此递归地对实例进行测试和分配，直至到达叶结点，最后将实例分配到叶结点的分类中。

分类过程

if-then 规则集合
决策树可以看成是 if-then 规则的集合。将决策树转换为 if-then 规则的流程如下：由决策树的根结点到叶结点的每一条路径构建一个规则；路径上的内部结点的特征表示规则的条件，而叶结点的分类则对应的规则的结论。
决策树上的路径或其对应的 if-then 规则集合具有一个重要的性质：互斥且完备。也就是说每一个实例都被一条路径或对应的一条规则覆盖，而且仅被一条路径或一条规则所覆盖。
覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。
条件概率分布
决策树还可以表示为给定特征条件下类的条件概率分布，该条件概率分布定义在特征空间的划分（partition）上。将特征空间划分为互不相交的单元或区域，并在每个单元或区域定义一个类的概率分布就可以构成一个条件概率分布。
决策树中的每一条路径对应花粉中的某个单元，决策树所表示的条件概率分布就是由各个单元在给定特征条件下类的条件概率分布组成。

决策树学习

决策树学习根据给定的训练数据集构建一个决策树模型，使之可以正确地进行分类，但其本质就是从训练数据集中归纳总结出一组分类规则，而最终所需要的是具有很好的泛化能力，既可以对训练数据有很好的拟合，也可以对未知数据有很好的预测。
那么如何对这一要求如何体现呢？决策树模型使用损失函数来表示这一目标，其通常是正则化的极大似然函数，策略是以损失函数为目标函数的最小化。

决策树学习的算法通常就是一个递归地选择特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类，这一过程对应特征空间的划分，也是决策树的构建。
在开始时构建根结点，将所有的训练数据都放在根结点，此时选择一个最优特征，根据这一特征将训练数据集划分为子集，使得各个子集在当前分类情况下是最好的分类；如果这些子集可以被基本正确分类，那就构建叶结点，并将子集分配到对应的叶结点中；如果这些子集不能被正确分类，则为这些子集重新选择新的最优特征，继续对其划分并构建相应的结点；如此递归下去直至训练数据子集都能被正确分类，或者没有合适的特征为止，至此每个子集都会被分配到对应的叶结点上，这就生成了一颗决策树。

以上方法生成的决策树可以很好的对训练数据集进行分类，但对于未知的数据集却未必有很好的分类能力，即可能发生过拟合现象。因此需要对生成的决策树进行剪枝，将决策树变得简单化，使其具有更好的泛化能力。

生成算法

`ID3`

ID3 算法的核心在于对决策树上的各个结点应用信息增益准则选择特征，递归地构建决策树。
具体方法是：

从根结点（root node）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点。
再对子结点递归地调用以上方法，构建决策树。
直到所有特征的信息增益都很小或没有特征可以选择为止。
最终就会得到一个决策树，其本质是使用 极大似然法 进行概率模型的选择。

示例：

输入：训练数据集 D，特征集 A，阈值 $\omega$

输出：决策树
过程：

若 D 中所有实例属于同一类 $C_k$，则 T 为单结点树，并将类 $C_k$ 作为该结点的类标记，返回 T。

若 A = $\phi$，则 T 为单结点树，并将 D 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 T。

否则计算 A 中各个特征对 D 的信息增益，选择信息增益最大的特征 $A_g$。

如果 $A_g$ 小于阈值 $\omega$，则置 T 为单结点树，并将 D 中实例数最大的类 $C_k$ 作为该类的标记，返回 T。

否则对 $A_g$ 的每一个可能值 $a_i$，依据 $A_g$ = $a_i$ 将 D 划分为若干个非空子集 $D_i$，将 $D_i$ 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 T，返回 T。

对第 i 个子结点，以 $D_i$ 为训练集，以 A - $A_g$ 为特征集，递归地调用 1, 2, 3, 4, 5 得到子树 $T_i$，返回 $T_i$。

`C4.5`

C4.5 算法与 ID3 算法类似，C4.5 在生成过程中使用了信息增益比来选择特征。

`CART`

分类与回归树（classification and regression tree, CART）模型是应用非常广泛的决策树学习方法，既可以用于分类，也可以用于回归，将用于分类和回归的树统称为决策树。

CART 是在给定输入随机变量 X 条件下输出随机变量 Y 的条件概率分布的学习方法。解释其含义就是，CART 假设决策树是二叉树，内部结点特征取值为“是”或 “否”，即左分支是取值为“是”的分支，右分支是取值为“否”的分支，这样决策树就等价于递归地对每个特征进行二分，即将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

CART 算法由以下两步组成：

决策树生成：基于训练数据集生成决策树，生成的决策树要尽可能的大。
决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，此时使用损失函数最小化作为剪枝的标准。

特征选择

特征选择在于选取对训练数据具有分类能力的特征，这样可以大大提高决策树学习的效率。如果一个特征进行分类的结果和随机分类的结果没有太大的差别，则这个特征没有分类能力，实际中这样的特征对决策树学习的准确度影响不大。
特征选择的准则是：

信息增益
信息增益比
基尼系数

信息增益

在信息论与概率统计中，熵（entropy）用来度量随机变量的不确定性。

条件熵 H(Y|X) 表示在已知随机变量 X 的条件下随机变量 Y 的不确定性，即定义为 X 给定条件下 Y 的条件概率分布的熵对 X 的数学期望。

$$ H(Y|X) = \sum_{i=1}^n p_i H (Y | X = x_i) $$

其中 $p_i$ = P(X = $x_i$ ), i = 1, 2, ..., n

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

信息增益（information gain）表示得知特征 X 的信息而使得类 Y 的信息的不确定性减少的程度。
特征 A 对训练数据集 D 的信息增益 $g(D, A)$，定义为集合 D 的经验熵 $H(D)$ 与特征 A 给定条件下 D 的经验条件熵 $H(D|A)$ 之差，即

$$ g(D, A) = H(D) - H(D|A) $$

给定训练数据集 D 与特征 A，经验熵 $H(D)$ 表示数据集 D 进行分类的不确定性；而经验条件熵 $H(D|A)$ 表示在特征 A 给定条件下对数据集 D 进行分类的不确定性，那么他们的差即信息增益，表示由于特征 A 而使得对数据集 D 的分类的不确定性减少的程度。由此可以得到信息增益依赖于特征，不同的特征具有不同的信息增益，而信息增益大的特征具有更强的分类能力。

一般地，熵 H(Y) 与条件熵 H(Y|X) 之差称为互信息（mutual information），决策树学习中的信息增益等价于训练数据集中类与特征的互信息，因此决策树学习应用信息增益准则选择特征。

在实际中根据信息增益准则选择特征的方式是：对训练数据集 D，计算其每个特征的信息增益，并比较其大小，择优选择信息增量最大的特征。

信息增益算法示例：

输入：训练数据集 D 和特征 A
输出：特征 A 对训练数据集 D 的信息增益 g(D, A)
过程：

计算数据集 D 的信息增益
$$ H(D) = - \sum_{k=1}^K {\frac {\vert {C_k}\vert} {\vert {D} \vert} } log_2 {\frac {\vert {C_k}\vert} {\vert {D} \vert} } $$

计算特征 A 对数据集 D 的经验条件熵
$$ H(D|A) = \sum_{i=1}^n {\frac {\vert {D_i} \vert} {\vert {D} \vert} H(D_i) } $$

计算信息增益
$$ g(D, A) = H(D) - H(D|A) $$

信息增益比

信息增益的大小是相对于训练数据而言的，并没有绝对意义，而在训练数据集的经验熵大的时候，信息增益也会偏大。反之信息增益值会偏小。因此使用信息增益比可以解决这一问题，也是特征选择的另一个准则。
特征 A 对训练数据集 D 的信息增益比 $g_r(D, A)$，定义为其信息增益 $g(D, A)$ 与训练数据集 D 的经验熵 $H(D)$ 之比：

$$ g_r(D, A) = {\frac {g(D, A)} {H(D)} } $$

基尼系数

决策树的生成是递归地构建二叉决策树的过程，对回归树使用平方误差最小化准则，对分类树使用基尼系数（Gini index）最小化准则，进行特征选择生成二叉树。

生成回归树

假设 X, Y 分别表示输入和输出变量，且 Y 是连续变量，给定的数据集表示为：$D = { (x_1, y_1), (x_2, y_2), …, (x_N, y_N)}$，那么回归树如何生成？

一个回归树对应着输入空间（特征空间）的一个划分以及在划分单元上的输出值。假设已将输入空间划分为 M 个单元 $R_1, R_2, …, R_M$ 并且在每个单元 $R_m$ 上有一个固定的输出值 $C_m$，于是回归树的模型可以表示为

$$ f(x) = \sum_{m=1}^M C_m I(x \in R_m) $$

当输入空间的划分确定时就可以使用平方误差 $\sum_{x_i \in R_m} (y_i - f(x_i))^2$ 表示回归树对训练数据集的预测误差，即平方误差最小时表示该单元上的最优输出值。

那输入空间（特征空间）的切分点如何划分呢？这里采用启发式的方法，选择第 j 个变量 $X_j$ 和对应的取值 $C_j$ 作为切分变量（splitting variable）和切分点（splitting point） ，定义两个区域
$$R_1(j, C_j) = {X | X_j <= C_m}, R_2(j, C_j) = {x | X_j > C_m}$$
然后寻找最优变量 j 和最优切分点 $C_m$ 。即求解

$$ \min_{j,C_m}[\min_{C_1}\sum_{x_i \in R_1(j, C_m)}(y_i - C_1)^2 + \min_{C_2}\sum_{x_i \in R_1(j, C_m)}(y_i - C_2)^2] $$

而对于固定输入变量 j 就可以找到最优切分点 $C_m$

$$ \bar{c_1} = ave(y_i | x_i \in R_1(j, C_m)) , \bar{c_2} = ave(y_i | x_i \in R_2(j, C_m)) $$

接着遍历输入所有变量，找到最优的切分变量 j，构成一个 $(j, C_m)$。依次将输入空间划分为两个区域，接着对上述区域进行重复划分，直至满足条件为止。即可以生成被称为最小二乘回归树（least squares regression tree）。

最小二乘回归树生成算法示例：

输入：训练数据集 D
输出：回归树 $f(x)$

过程：

在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域的输出值。

计算划分数据集的最优切分变量 j 和最优切分点 $C_m$，求解
$$ \min_{j,C_m}[\min_{C_1}\sum_{x_i \in R_1(j, C_m)}(y_i - C_1)^2 + \min_{C_2}\sum_{x_i \in R_1(j, C_m)}(y_i - C_2)^2] $$
遍历变量 j，对固定的切分变量 j 和切分点 $C_m$ 能得到最小值的对 $(j, C_m)$。

用选定的最小值的对 $(j, C_m)$ 划分区域并计算对应的输出值
$$ R_1(j, C_m) = {x|x_j <= C_m}, R_2(j, C_m) = {x|x_j > C_m} $$
$$ \bar{C_m} = {\frac {1} {N_m}} \sum_{x_i \in R_m(j, C_m)} y_i, x \in R_m, m = 1, 2 $$

继续对两个子区域调用步骤 2, 3，直至满足条件。

至此就可以得到将输入空间划分为 M 个区域 $R_1, R_2, …, R_M$ 即可生成回归决策树。
$$ f(x) = \sum_{m=1}^M \bar{C_m} I(x \in R_m) $$

生成分类树

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
在分类问题中，假设有 K 个类，样本点属于第 k 类的概率为 Pk，则概率分布的基尼指数定义为：

$$ Gini(p) = \sum_{k=1}^K P_k (1-P_k) = 1-\sum_{k=1}^K p_k^2 $$

对于二分类问题，若样本点属于第一个类的概率为 p，则概率分布的基尼指数为：

$$ Gini(p) = 2p(1-p) $$

对于给定的样本集合 D，其基尼指数为：

$$ Gini(D) = 1 - (\sum_{k=1}^K)({\frac {\vert{C_k}\vert} {\vert{D}\vert} })^2 $$

其中 $C_k$ 是 D 中属于第 k 类的样本子集，K 是类的个数。

如果样本集合 D 根据特征 A 是否取某一个可能值 a 被分割为 D1 和 D2，即 $D1 = {(x, y) \in D | A(x) \in a}, D2 = D - D1$
则在特征 A 的条件下，集合 D 的基尼指数定义为：

$$ Gini(D, A) = {\frac {\vert {D1} \vert} {\vert {D} \vert} } Gini(D1) + {\frac {\vert {D2} \vert} {\vert {D} \vert} } Gini(D2) $$

基尼指数 Gini(D, A) 表示 A = a 分割后集合 D 的不确定性。

基尼指数越大，样本集合的不稳定性则越大。

CART 决策树基尼系数生成算法示例：

输入：训练数据集 D，停止计算的条件
输出：CART 决策树
过程：

根据训练数据集，根结点的数据集为 D，计算现有特征对该数据集的基尼指数，对于特征 A 有一个可能的取值 a，根据样本对 A = a 的测试为“是”或“否”，从而将数据集 D 拆分为 $D_1$ 和 $D_2$ 两部分，计算对应的基尼指数，

在计算特征 A 所有取值 a 对应的基尼指数后，选择其中基尼指数最小的特征作为对应的最优特征和最优切分点，至此就可以将数据集切分为两部分，生成两个子结点，将数据集分配到对应的子结点中。

对两个子结点递归地调用 1, 2，直至结点中的数据集个数小于预定阈值，或者基尼指数低于预定阈值，又或者没有足够的特征。

至此在满足所有条件后即可生成 CART 决策树。

决策树修剪

决策树通过生成算法递归地产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但是却对未知的数据分类没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多的考虑如何提高针对训练数据的正确分类，从而构建出复杂的决策树，那么解决这个问题就是将复杂的决策树进行简单化。
在决策树的学习中将已生成的树进行简化的过程称为剪枝（pruning），具体就是剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化树模型。

决策树的剪枝往往通过极小化决策树整体的 损失函数（lose function） 或 代价函数（cost function） 来实现。
设树 T 的叶结点个树为 ${\vert {T} \vert}$，t 是树 T 的叶结点，该叶结点有 $N_t$ 个样本点，其中 k 类的样本点有 $N_{tk}$ 个 k = 1, 2, ..., K，$H_t(T)$ 为叶结点 t 上的经验熵，a >= 0 为参数，则决策树学习的损失函数可以定义为：

$$ C_a(T) = \sum_{t=1}^{\vert {T} \vert} N_t H_t (T) + a {\vert {T} \vert} $$

其中经验熵为：

$$ H_t(T) = -\sum_k {\frac {N_{tk} } {N_t} } log {\frac {N_{tk} } {N_t} } $$

那么：

$$ C(T) = \sum_{t=1}^{\vert {T} \vert} N_t H_t (T) = -\sum_{t=1}^{\vert {T} \vert} N_t \sum_{k=1}^K {\frac {N_{tk} } {N_t} } log {\frac {N_{tk} } {N_t} } = -\sum_{t=1}^{\vert {T} \vert} \sum_{k=1}^K {N_{tk} } log {\frac {N_{tk} } {N_t} } $$

即可得到：

$$ C_a(T) = C(T) + a(T) $$

上述中 $C(T)$ 表示模型对训练数据的预测误差，即模型和训练数据的拟合程度，${\vert {T} \vert}$ 表示模型复杂度，参数 a >= 0 控制两者之间的影响。那么较大的 a 就意味着选择较简单的决策树，较小的 a 选择较简单的决策树，a = 0 也就意味着只考虑决策树与训练数据的拟合程度，不考虑决策树的复杂度。
决策树剪枝也就是当 a 确定时，选择损失函数最小的决策树，即损失函数最小的子树，刚好通过使得损失函数最小化来平衡复杂的模型和训练数据的拟合程度。

下面就是具体的剪枝算法示例：

输入；算法生成的决策树 T，参数 a
输出：修剪后的子树 $T_a$

过程：

计算每个结点的经验熵。

递归地从树的叶结点向上回缩。

假设一组叶结点回缩到其父结点之前与之后的整体树分别为 $T_B$ 与 $T_A$，其对应的损失函数为 $C_a(T_B)$ 与 $C_a(T_A)$，如果 $ C_a(T_B) <= C_a(T_A) $ 则进行剪枝，即将父结点变为新的叶结点。

返回 2，直至不能继续为止，即可得到损失函数最小的子树 $T_a$。

`CART` 剪枝

CART 剪枝算法从决策树底端剪去一些子树，使决策树变小，模型变简单，从而能够对未知数据更准确的预测。
CART 剪枝算法由两步组成：

首先从算法生成的决策树 $T_0$ 底端开始不断剪枝，直到 $T_0$ 的根结点，形成一个子树序列（$T_0$, $T_1$, …, $T_n$）。
剪枝过程中，计算子树的损失函数：
$$ C_a(T) = C(T) + a{\vert {T} \vert} $$
T 为任意子树，$C(T)$ 为对训练数据的预测误差，${\vert {T} \vert}$ 为子树的叶结点个树，a >= 0 为参数，$C_a(T)$ 为参数是 a 时的子树 T 的整体损失。
对于某个的 a，一定存在使损失函数 $C_a(T)$ 最小的子树 $T_a$，即 $T_a$ 在损失函数 $C_a(T)$ 最小时最优。当 a 大的时候，最优子树 $T_a$ 偏小；当 a 小的时候，最优子树 $T_a$ 偏大；而极端情况下 a = 0，整体树最优；当 a -> $\infty$ 时，根结点组成的单结点树是最优的。

具体从整树 $T_0$ 开始剪枝，对 $T_0$ 的任意内部结点 t，以 t 为单结点树的损失函数为：
$$ C_a(T) = C(t) + a $$

以 t 为根结点的子树 $T_t$ 的损失函数为：
$$ C_a(T_t) = C(T_t) + a {\vert {T_t} \vert} $$
- 当 a = 0 及 a 充分小的时候，有不等式：$ C_a(T_t) < C_a(t) $
- 当 a 增大时，在某一个 a 有：$ C_a(T_t) = C_a(t) $
- 当 a 继续增大时，只要 $a = {\frac {C(t) - C(T_t)} { {\vert {T_t}\vert} } - 1}$ 即 $T_t$ 与 t 具有相同的损失函数，而 t 的结点较少，因此 t 比 $T_t$ 更可取，对 $T_t$ 进行剪枝。
为此计算 $T_0$ 中每个内部结点 t
$$ g(t) = {\frac {C(t) - C(T_t)} { {\vert {T_t}\vert} - 1} }$$
表示剪枝后整体损失函数减小的程度。

在 $T_0$ 中剪去 g(t) 最小的子树 $T_t$，将得到子树作为 $T_1$，同时将最小的 g(t) 设为 $a_1$，$T_1$ 为区间 $[a_1, a_2)$ 的最优子树。如此剪枝下去直至根结点，而在这一过程中，不断递增 a，不断产生新的区间。
接着通过交叉验证法在独立的验证数据集上对子树序列进行测试，从而选出最优子树。
利用验证数据集测试子树序列 $T_0, T_1, …, T_n$ 中各个子树的平均方差或基尼系数，平方误差或基尼系数最小的子树也就是最优的决策树，而当最优子树被确定时，子树对应的 a 也会被确定，即可得到最优子树 $T_a$。

下面就是具体的 CART 剪枝算法示例：

输入：CART 算法生成的决策树 $T_0$

输出：最优决策树 $T_a$

过程：

设 $k = 0, T = T_0$。

设 a $ = + \infty$。

自上而下地对各内部结点 t 计算 $C(T_t)$，${\vert {T_t} \vert}$ 以及
$$ g(t) = {\frac {C(t) - C(T_t)} { {\vert {T_t} \vert} - 1} } $$
$$ a = min(a, g(t)) $$
$T_t$ 表示以 t 为根结点的子树，$C(T_t)$ 是对训练数据的预测误差，${\vert {T_t} \vert}$ 是 $T_t$ 的叶结点个树。

自上而下地访问内部结点 t，如果有 g(t) = a，则进行剪枝并对叶结点 t 以多数表决法决定其类，得到树 T。

设 $k = k + 1, a_k =$ a $, T_k = T$。

如果 T 不是由根结点单独组成的树，则返回 4。

采用交叉验证法在子树序列 $T_0, T_1, …, T_n$ 中选取最优子树 $T_a$。

总结

分类决策树模型是用于表示基于特征对实例进行分类的树形结构体，决策树可以转换为 if-then 规则集合，也可以看作是定义在特征空间上划分的条件概率分布。
决策树学习宗旨是构建一个可以对训练数据很好的分类，但同时复杂度较小的决策树。
决策树学习算法包含三部分：特征选择、树的生成、树的剪枝。
常用的算法：ID3、 C4.5、 CART。
特征选择的目的在于能够选取对实例分类有用的特征，常用的准则如下：
- 样本集合 D 对特征 A 的信息增益：
  $$ g(D, A) = H(D) - H(D|A) $$
  $$ H(D) = - \sum_{k=1}^K {\frac {\vert {C_k}\vert} {\vert {D} \vert} } log_2 {\frac {\vert {C_k}\vert} {\vert {D} \vert} } $$
  $$ H(D|A) = \sum_{i=1}^n {\frac {\vert {D_i} \vert} {\vert {D} \vert} H(D_i) } $$
- 样本集合 D 对特征 A 的信息增益比：
  $$ g_r(D, A) = {\frac {g(D, A)} {H(D)} } $$
- 样本集合 D 的基尼指数：
  $$ Gini(D) = 1 - \sum_{k=1}^K ({\frac {\vert {C_k} \vert} {\vert {D} \vert} })^2 $$
  特征 A 条件下集合 D 的基尼指数：
  $$ Gini(D, A) = {\frac {\vert {D1} \vert} {\vert {D} \vert} } Gini(D1) + {\frac {\vert {D2} \vert} {\vert {D} \vert} } Gini(D2) $$
决策树的生成同时是采用信息增益最大、信息增益比最大或基尼指数最小作为特征选择的准则，然后从根结点开始，通过特征选择准则划分正确的子集，递归地生成决策树。
生成决策树的过程中会产生过拟合问题，因此需要剪枝，从已生成的决策树上剪掉一些叶结点或者子结点，并将其父结点作为新的叶结点，从而简化决策树。

引用

个人备注

此博客内容均为作者学习《统计学习方法》所做笔记，侵删！
若转作其他用途，请注明来源！

概要

决策树