基本流程

决策树基于树结构进行决策。一决策树包含三类结点：

根结点：包含样本全集
内部结点：包含被划分后的样本子集
叶结点：对应决策结果

除叶结点外，根结点和内部结点还对应一个属性测试，其所办包含的样本（子）集按照属性测试结果被划分到对应的子结点中。从根结点到每个叶结点的路径对应了一个判定测试序列。

决策树学习的目的是为了产生一颗泛化能力强的决策树。决策树的生成是一个递归的过程。通过不断的属性测试从而不断地划分样本（子）集。在生成过程中，有三种情况会导致递归返回：

当前结点所包含的样本均属于同一类别，无需划分；
当前属性集为空，或所有样本在所有属性上的取值为空，无法划分；
当前结点包含的样本集为空，不能划分。

在1，2情况下，当前结点被标记为叶结点，且其决策结果为所含样本最多的决策结果；在3情况下，当前结点被标记为叶结点，但其决策结果为其父结点所含样本最多的决策结果。

输入：训练集 $D=\{(\vec{x}_1, y_1),(\vec{x}_2, y_2),\cdots,(\vec{x}_n, y_n)\}$ ；属性集 $A=\{a_1,a_2,\cdots,a_n\}$
过程：函数TreeGenerate( $D$ , $A$ )
1：生成结点node；
2：if $D$ 中的样本全属于同一类别 $C$ （情况1） then
3： $~$ 将node标记为 $C$ 类叶结点；return
4：end if
5：if $A=\emptyset$ OR $D$ 中的样本在 $A$ 上取值相同 then
6： $~$ 将node标记为叶结点，其类别为 $D$ 中样本数最多的类；return
7：end if
8：从 $A$ 中选择最优划分属性 $a_*$ ；
9：for $a_$ 的每个值 $a_^v$ do
10： $~$ 为node生成一个分支结点；令 $D_v$ 表示 $D$ 中在属性 $a_$ 上取值为 $a_^v$ 的样本子集；
11： $~~$ if $D_v=\emptyset$ then
12： $~~~~~$ 将分支结点标记为叶结点，其类别标记为其父结点 $D$ 中样本最多的类；return
13： $~~$ else
14： $~~~~~$ 以TreeGenerate( $D$ , $A-\{a_*\}$ )为分支结点
15： $~~$ end if

划分选择

决策树学习的关键是如何选择最优划分属性。在决策树划分的过程中，希望决策树的分支结点所包含的同类样本越多越好，即结点的“纯度”越来越高。信息增益、增益率以及基尼指数是三种常用的选择最优划分属性的度量指标。

信息增益

“信息熵”是度量样本集合纯度的一种指标。假设当前样本集合 $D$ 中第 $k$ 类样本所占比例为 $p_k$ （ $k=1,2,\cdots,|\mathcal{Y}|$ ），则 $D$ 的信息熵定义为

$\begin{aligned} Ent(\tilde{D}) = -\sum_{k=1}^{|\mathcal{Y}|}p_klog_2p_k \end{aligned}$

$Ent(D)$ 的值越小，则 $D$ 的纯度越高。

假定离散属性 $a$ 有 $V$ 个可能的取值 $\{a^1,a^2,...,a^V\}$ ，若使用 $a$ 对样本集 $D$ 进行划分，则会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含 $D$ 中所有在 $a$ 上取值为 $a^v$ 的样本，记为 $D^v$ 。其对应的信息熵为 $Ent(D^v)$ 。

由于每个分支结点包含的样本数量不同，每个分支结点的权重为 $|D^v|/|D|$ ，即样本数量越多的分支结点的影响越大。

因此，利用属性 $a$ 对样本集 $D$ 进行划分所获得的信息增益为

$\begin{aligned} Gain(D, a) = Ent(D) - \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v) \end{aligned}$

信息增益越大，就意味着利用属性 $a$ 进行划分所获得的“纯度提升”越大。因此，利用信息增益来进行决策树的划分属性选择为

$\begin{aligned} a_* = arg~max_{a\in A}Gain(D, a) \end{aligned}$

ID3决策树算法就利用信息增益来进行划分属性的选择。

增益率

信息增益对可取值数目较多的属性有所偏好（可取值越多，其对应的划分子集就越多，那么每个子集中所包含的样本的数量就越少，且样本类别就越有可能属于同一类）。为了减少这种影响，C4.5算法适用增益率来选择最优划分属性：

$\begin{aligned} Gain\_ratio(D,a) = \frac{Gain(D,a)}{IV(a)} \end{aligned}$

其中

$\begin{aligned} IV(a) = -\sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|} \end{aligned}$

$IV(a)$ 被称为 $a$ 的固有值。属性 $a$ 的可取值数目越多， $IV(a)$ 的值通常就越大。

增益率对可取值数目较小的属性有所偏好。因此C4.5通常会先从候选划分属性中选择一部分信息增益高于平均水平的属性，再从中选择出增益率最高的属性。

基尼指数

数据集 $D$ 的纯度可以用“基尼指数”来度量。CART决策树使用基尼值来选择划分属性：

$\begin{aligned} Gini(D) & = \sum_{k=1}^{|\mathcal{Y}|}\sum_{k'\neq k}p_kp_{k'} \\ & = 1 - \sum_{k=1}^{|\mathcal{Y}|}p_k^2 \end{aligned}$

$Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，且其类别不一致的概率。因此， $Gini(D)$ 越小， $D$ 的纯度就越高。

采用属性 $a$ 进行划分的基尼指数为：

$\begin{aligned} Gini\_index(D,a) & = \sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v) \end{aligned}$

因此，利用基尼指数来进行决策树的划分属性选择为

$\begin{aligned} a_* = arg~min_{a\in A}Gini\_index(D,a) \end{aligned}$

剪枝处理

剪枝是决策树应对过拟合的主要手段。其基本策略有两种：

预剪枝：在决策树生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来泛化性能的提升，则停止划分并将当前结点标记为叶结点；
后剪枝：对一颗完整的决策树自下而上地对非叶结点进行考察，若将改结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。

为了判定泛化性能是否提升，通常留出一部分样本作为验证集。因此，样本集被分为训练集和验证集。

预剪枝

令当前需要决定是否需要划分的结点为 node；最优划分属性为 $a_*$ 。

将node作为叶结点，并将其包含的训练样本数量最多的类别作为该叶结点的标记；
计算验证集的分类精度；
按照 $a_*$ 的 $V$ 个取值将 node 划分为 $V$ 个分支；
将 $V$ 个分支作为叶结点，并将其包含的训练样本数量最多的类别作为对应叶结点的标记；
计算划分后验证集的分类精度；
若划分后的分类精度大于先前的分类精度，则对 node进行划分；否则，停止划分。

注：验证集的评估是对当前决策树的完整评估。

预备剪枝能够降低过拟合的风险，还显著减少了决策树的训练时间开销和测试开销。但是，预剪枝可能会带来欠拟合的风险。

后剪枝

先从当前训练集生成一个完整的决策树，并计算验证集的分类精度。后剪枝是自下而上进行剪枝。

令当前判断是否需要剪枝的内部结点为 node。

删除 node 的分支，并将 node 作为叶结点，标记为其包含的训练样本数量最多类别；
重新计算验证集在剪枝后的决策树上的分类精度；
若剪枝后的分类精度大于先前的分类精度，则对 node 进行剪枝；否则，不剪枝。

后剪枝决策树通常比预剪枝包含更多的分支。后剪枝决策树欠拟合风险小，泛化性能一般优于预剪枝决策树。但后剪枝过程需要自下向上对所有非叶结点进行逐一考察，因此训练时间开销大。

连续与缺失值

连续值处理

在实际任务中，属性的取值可能是连续的，因此需要使用“二分法”对连续属性进行处理。

二分法具体指

给定样本集 $D$ 和连续属性 $a$ ，假定 $a$ 在 $D$ 上有 $n$ 个不同的取值，将这些值从小到大进行排序，记为 $\{a^1,a^2,\cdots,a^n\}$ 。基于划分点 $t$ ，可将 $D$ 分为两个不相交的子集 $D_t^-$ 和 $D_t^+$ ，其中 $D_t^-$ 包含在属性 $a$ 上取值不大于 $t$ 的样本； $D_t^+$ 包含在属性 $a$ 上取值大于 $t$ 的样本。

对于相邻取值 $a^i$ 和 $a^{i+1}$ ，在区间 $[a^i, a^{i+1}]$ 上的任意值 $t$ 所产生的划分结果 $D_t^-$ 和 $D_t^+$ 都是相同的。

因此，对连续属性 $a$ ，可考察 $n-1$ 个不同的划分点，这些划分点组成的集合为

$\begin{aligned} T_a = \{\frac{a^i + a^{i+1}}{2}|1\leq i \leq n-1\} \end{aligned}$

即把任意区间 $[a^i, a^{i+1}]$ 的中位点 $\frac{a^i + a^{i+1}}{2}$ 作为候选划分点。

在评估 $a$ 是否可以作为最优划分属性之前，需要从 $T_a$ 中选取出最优的划分点，这里以信息增益为例，

$\begin{aligned} Gain(D, a) & = max_{t\in T_a} Gain(D, a, t) \\ & = max_{t\in T_a}Ent(D) - \sum_{\lambda \in \{-, +\} }\frac{|D_t^\lambda|}{|D|}Ent(D_t^\lambda) \end{aligned}$

其中， $Gain(D, a, t)$ 是样本集 $D$ 基于划分点 $t$ 二分后的信息增益。我们需要选择最大化 $Gain(D, a, t)$ 的划分点。

与离散属性不同的是，若当前结点的划分属性是连续属性，则该属性还可以作为其后代结点的划分属性。（只是后代结点不再考虑划分点 $t$ ，即后面再考虑属性 $a$ 时，其对应的划分点集合为 $T_a-\{t\}$ 。）

缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失。在此情况下，需要解决两个问题：

如何在属性值缺失的情况下进行划分属性的选择？
给定划分属性，如样本在该属性上的值缺失，如何对该样本进行划分？

给定训练集 $D$ 和属性 $a$ ，令 $\tilde{D}$ 表示 $D$ 中在属性 $a$ 上没有缺失值的样本子集。

对于问题1，可以使用 $\tilde{D}$ 来判断 $a$ 的优劣。

假定属性 $a$ 有 $V$ 个可能的取值 $\{a^1,a^2,...,a^V\}$ ，令 $\tilde{D}^v$ 表示 $\tilde{D}$ 在属性 $a$ 上取值为 $a^v$ 的样本子集。令 $\tilde{D}_k$ 表示 $\tilde{D}$ 中属于第 $k$ 类（ $(k=1,2,...,|\mathcal{Y}|)$ ）的样本子集。

假设每个样本 $\vec{x}$ 都有一个权重 $w_{\vec{x}}$ ，

令

$\begin{aligned} \rho = \frac{\sum_{\vec{x}\in \tilde{D}}w_{\vec{x}}}{\sum_{\vec{x}\in D}w_{\vec{x}}} \end{aligned}$

其中 $\rho$ 表示在属性 $a$ 上无缺失值的样本占总样本的比例。

令

$\begin{aligned} \tilde{p}_k = \frac{\sum_{\vec{x}\in \tilde{D}_k}w_{\vec{x}}}{\sum_{\vec{x}\in \tilde{D}}w_{\vec{x}}} \end{aligned}$

其中 $\tilde{p}_k$ 表示在属性 $a$ 上第 $k$ 类无缺失值的样本占总无缺失值的样本的比例。

$\begin{aligned} \tilde{r}_v = \frac{\sum_{\vec{x}\in \tilde{D}^v}w_{\vec{x}}}{\sum_{\vec{x}\in \tilde{D}}w_{\vec{x}}} \end{aligned}$

其中 $\tilde{r}_v$ 表示表示在属性 $a$ 上取值为 $a^v$ 的无缺失值的样本占总无缺失值的样本的比例。

以信息增益为例，对划分属性 $a$ 的评估为

$\begin{aligned} Gain(D,a) & = \rho \times Gain(\tilde{D}, a) \\ & = \rho \times (Ent(\tilde{D}) - \sum_{v=1}^{V}\tilde{r}_v Ent(\tilde{D}^v, a)) \end{aligned}$

其中

$\begin{aligned} Ent(\tilde{D}) = -\sum_{k=1}^{|\mathcal{Y}|}\tilde{p}_klog_2\tilde{p}_k \end{aligned}$

对于问题2，

若样本 $\vec{x}$ 在属性 $a$ 上的取值已知，则将 $\vec{x}$ 划分到对应的子结点，且样本的权重保持为 $w_{\vec{x}}$ ；
若样本 $\vec{x}$ 在属性 $a$ 上的取值未知，则将 $\vec{x}$ 同时划分到所有的子结点中，并将其在每个子结点中权重调整为对应的 $\tilde{r}_v\times w_{\vec{x}}$ 。

决策树