基本流程
决策树 (decision tree) 是一类常见的机器学习方法，它基于树结构来进行决策。例如，我们要对“这是好瓜吗？”这样的问题进行决策时，通常会进行一系列的判断或“子决策”，如下图所示：
一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。
决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之” 策略。决策树学习基本算法如下所示
输入：训练集 $D={(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),…,(\boldsymbol{x}_m,y_m)}$；
$\quad\quad$ 属性集 $A={a_1,a_2,…,a_d}$
过程：函数 $\text{TreeGenerate}$$(D,A)$
生成结点 $\text{node}$；
$\textbf{if}$ $D$ 中样本全属于同一类别 $C$ $\textbf{then}$
$\quad$将 $\text{node}$ 标记为 $C$ 类叶结点；$\textbf{return}$
$\textbf{end if}$
$\textbf{if}$ $A = \varnothing$ $\textbf{OR}$ $D$ 中样本在 $A$ 上取值相同 $\textbf{then}$
$\quad$ 将 $\text{node}$ 标记为叶结点，其类别标记为 $D$ 中样本数最多的类；$\textbf{return}$
$\textbf{end if}$
从 $A$ 中选择最优划分属性 $a_{*}$；
$\textbf{for}$ $a_{*}$ 的每一个值 $a_{*}^v$ $\textbf{do}$
$\quad$ 为 $\text{node}$ 生成一个分支；令 $D_v$ 表示 $D$ 中在 $a_{}$ 上取值为 $a_{}^v$ 的样本子集；
$\quad$ $\textbf{if}$ $D_v$ 为空 $\textbf{then}$
$\quad\quad$ 将分支结点标记为叶结点，其类别标记为 $D$ 中样本最多的类；$\textbf{return}$
$\quad$ $\textbf{else}$
$\quad\quad$ 以 $\text{TreeGenerate}$$(D_v, A \backslash {a_*})$ 为分支结点（从 $A$ 中去掉 $a_{*}$）
$\quad$ $\textbf{end if}$
$\textbf{end for}$
显然，决策树的生成是一个递归过程。在决策树基本算法中，有三种情形会导致递归返回：
- 当前结点包含的样本全属于同一类别，无需划分；
- 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；
- 当前结点包含的样本集合为空，不能划分。
注意：第 2 种情形下，我们把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；在第 3 种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父节点所含样本最多的类别。这两种情形的处理实质不同：情形 2 是在利用当前结点的后验分布，而情形 3 则是把父结点的样本分布作为当前结点的先验分布。
划分选择
由之前的决策树学习基本算法可以看出，决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程的不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度 (purity) 越来越高。
信息增益
信息熵 (information entropy) 是度量样本集合纯度最常用的一种指标。假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k$ $(k=1,2,…,\vert\mathcal{Y}\vert)$，则 $D$ 的信息熵定义为： \(\text{Ent}(D) = -\sum_{k=1}^{\vert\mathcal{Y}\vert} p_k \log_2 p_k \tag{2.1}\)
信息熵可以看做是对集合混乱程度（不确定性）的一种度量，$\text{Ent}(D)$ 的值越小，则 $D$ 的纯度越高。
注：若 $p = 0$，则 $p\log_2 p = 0$。$\text{Ent}(D)$ 的最小值为 $0$，最大值为 $\log_2 \vert\mathcal{Y}\vert$。
假定离散属性 $a$ 有 $V$ 个可能的取值 ${a^1,a^2,…,a^V}$，若使用 $a$ 来对样本集 $D$ 进行划分，则会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^v$ 的样本，记为 $D^v$。我们可根据 $(2.1)$ 计算出 $D^v$ 的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 $\frac{\vert D^v \vert}{\vert D \vert}$，即样本数越多的分支结点的影响越大，于是可计算出用 $a$ 对样本集 $D$ 进行划分所获得的信息增益 (information gain)
\[\text{Gain}(D,a) = \text{Ent}(D) - \sum_{v=1}^V \frac{\vert D^v \vert}{\vert D\vert} \text{Ent}(D^v) \tag{2.2}\]$(2.2)$ 中前面一项表示数据集 $D$ 的混乱程度，第二项表示在使用属性 $a$ 进行划分后数据集 $D$ 的混乱程度，那么它们的差就表示通过属性 $a$ 的划分使数据集 $D$ 混乱程度的减少量，也就是增加的信息量，因此称为信息增益。一般而言，信息增益越大，则意味着使用属性 $a$ 来进行划分所获得的纯度提升越大。
因此我们可以使用信息增益来进行决策树的划分属性选择，即在决策树学习算法中选择属性
\[a_{*} = \mathop{\arg\max}_{a\in A}\text{Gain}(D,a)\]著名的 ID3 决策树学习算法就是以信息增益为准则来选择划分属性。
以下表中的贷款申请数据集为例，我们演示一下通过 ID3 算法建立决策树。数据包括贷款申请人的 4 个属性：年龄、工作、有自己的房子、信贷情况。表的最后一列是类别，即是否同意贷款。
\[\begin{array}{c|c|c|c|c|c} \hline 编号&年龄&有工作&有房子&信贷&类别\\ \hline 1&青年&否&否&一般&否\\ \hline 2&青年&否&否&好&否\\ \hline 3&青年&是&否&好&是\\ \hline 4&青年&是&是&一般&是\\ \hline 5&青年&否&否&一般&否\\ \hline 6&中年&否&否&一般&否\\ \hline 7&中年&否&否&好&否\\ \hline 8&中年&是&是&好&是\\ \hline 9&中年&否&是&非常好&是\\ \hline 10&中年&否&是&非常好&是\\ \hline 11&老年&否&是&非常好&是\\ \hline 12&老年&否&是&好&是\\ \hline 13&老年&是&否&好&是\\ \hline 14&老年&是&否&非常好&是\\ \hline 15&老年&否&否&一般&否\\ \hline \end{array}\]显然 $\vert\mathcal{Y}\vert = 2$。在决策树学习开始时，根结点包含 $D$ 中的所有样本，其中正例占 $p_1 = \frac{9}{15}$，反例占 $p_2 = \frac{6}{15}$。于是根据 $(2.1)$ 可以计算出根结点的信息熵为
\[\text{Ent}(D) = -\sum_{k=1}^2 p_k\log_2 p_k = -\Big(\frac{9}{15}\log_2\frac{9}{15}+\frac{6}{15}\log_2\frac{6}{15}\Big) = 0.971\]然后，我们要计算出当前属性集合 ${年龄,有工作,有房子,信贷}$ 中的每个属性的信息增益。以属性“年龄”为例，它有 3 个可能取值：${青年,中年,老年}$，使用该属性对 $D$ 进行划分，可得 3 个子集，分别记为 $D^1(年龄=青年)$，$D^2(年龄 = 中年)$，$D^3(年龄 = 老年)$。
于是可以根据 $(2.2)$ 计算出用“年龄”划分之后的信息增益为：
\[\begin{align} \text{Gain}(D,年龄) &= \text{Ent}(D)-\sum_{v=1}^3\frac{\vert D^v \vert}{\vert D\vert}\text{Ent}(D^v)\\ &= 0.971-\Big[\frac{5}{15}\Big(-\frac{2}{5}\log_2\frac{2}{5} - \frac{3}{5}\log_2\frac{3}{5}\Big)\\ &\quad+\frac{5}{15}\Big(-\frac{3}{5}\log_2\frac{3}{5}-\frac{2}{5}\log_2\frac{2}{5}\Big)+\frac{5}{15}\Big(-\frac{4}{5}\log_2\frac{4}{5}-\frac{1}{5}\log_2 \frac{1}{5}\Big)\Big]\\ &=0.971 - 0.888 = 0.083 \end{align}\]类似的，我们可以计算出其他属性的信息增益：
\[\begin{gather} \text{Gain}(D,有工作) = 0.324;\\ \text{Gain}(D,有房子)=0.420;\\ \text{Gain}(D,信贷) = 0.363. \end{gather}\]显然，属性“有房子”的信息增益最大，于是它被选为划分属性。它将 $D$ 划分为两个子集 $D^1(有房子=是)$，$D^2(有房子 = 否)$。由于 $D^1$ 只有同一类样本，所以它成为一个叶结点，结点的类别标记为“是”。对 $D^2$ 则需要从 ${年龄,有工作,信贷}$ 中选择新的划分属性：
\[\begin{gather} \text{Gain}(D^2,年龄) = 0.251;\\ \text{Gain}(D^2,有工作) = 0.918;\\ \text{Gain}(D^2,信贷) = 0.474. \end{gather}\]选择信息增益最大的属性“有工作”作为结点的划分属性，于是从这一结点引出两个子集：$D^1(有工作=是)$，$D^2(有工作 = 否)$。$D^1$ 中包含 3 个样本，属于同一类，所以这是一个叶结点，类别标记为“是”；$D^2$ 包含 6 个样本，也属于同一类，所以这也是一个叶结点，类别标记为“否”。
这样生成一个如下图所示的决策树，该决策树只用了两个划分属性（有两个内部结点）
增益率
在上面的介绍中，我们有意忽略了表中的“编号”一列。若把“编号”也作为一个候选划分属性，则根据 $(2.2)$ 可计算出它的信息增益远大于其他候选划分属性。这很容易理解：“编号”将产生 17 个分支，每个分支结点仅包含一个样本，这些分支结点的纯度已达最大。然而这样的决策树显然不具有泛化能力，无法对新样本进行有效预测。
实际上，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的 C4.5 决策树算法不直接使用信息增益，而是使用增益率 (gain ratio) 来选择最优划分属性。采用与 $(2.2)$ 相同的符号来表示，增益率定义为
\[\text{Gain-ratio}(D,a) = \frac{\text{Gain}(D,a)}{\text{IV}(a)} \tag{2.3}\]其中
\[\text{IV}(a) = -\sum_{v=1}^V \frac{\vert D^v \vert}{\vert D \vert} \log_2 \frac{\vert D^v \vert}{\vert D \vert} \tag{2.4}\]称为属性 $a$ 的固有值 (intrinsic value)。属性 $a$ 的可能取值数目越多（即 $V$ 越大），则 $\text{IV}(a)$ 的值通常会越大。需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此 C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
基尼指数
CART 决策树使用基尼指数来选择划分属性，采用与 $(2.1)$ 相同的符号，数据集 $D$ 的纯度可用基尼值来度量：
\[\begin{align} \text{Gini}(D) &= \sum_{k=1}^{\vert \mathcal{Y} \vert}\sum_{k' \ne k} p_kp_{k'} \\ &=1-\sum_{k=1}^{\vert\mathcal{Y}\vert} p_k^2 \end{align} \tag{2.5}\]直观来说，$\text{Gini}(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。因此，$\text{Gini}(D)$ 越小，则数据集 $D$ 的纯度越高。
采用与 $(2.2)$ 相同的符号表示，属性 $a$ 的基尼指数定义为
\[\text{Gini-index}(D,a) = \sum_{v=1}^V \frac{\vert D^v \vert}{\vert D \vert} \text{Gini}(D^v) \tag{2.6}\]于是，我们在候选属性集合 $A$ 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即
\[a_{*} = \mathop{\arg\min}_{a \in A} \text{Gini-index}(D,a)\]剪枝
决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。
决策树剪枝的基本策略有预剪枝 (prepruning) 和后剪枝 (postpruning)。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。
对决策树泛化性能的评估可以使用各种性能评估方法，例如使用留出法，即预留一部分数据用作“验证集”以进行性能评估。
预剪枝
对于每一个结点，首先不进行划分，直接将其标记为叶结点，将类别标记为训练样例最多的类别，然后使用验证集对决策树进行评估；然后使用选出的最优划分属性对结点进行划分，同样使用验证集评估分类的精度。如果划分后验证集精度有提升，则进行划分，否则就停止。
一般情况下，相比于未剪枝决策树，预剪枝将使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能的暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。
后剪枝
对于通过学习算法生成好的决策树，我们自底向上地对非叶结点进行考察，即假设对当前结点不进行划分，将其类别标记为训练样例最多的类别，然后通过验证集对剪枝后的决策树进行评估，如果验证集精度有提高则进行剪枝。
一般情况下，后剪枝决策树通常比预剪枝决策树保留了更多的分支。通常情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。
连续与缺失值
连续值处理
前面我们只讨论了基于离散属性来生成决策树，而在现实学习任务中，我们经常会遇到连续属性。由于不能直接根据连续属性的可取值来对结点进行划分，因此我们可以使用连续属性离散化技术。最简单的策略是采用二分法 (bi-partition) 对连续属性进行处理，这正是 C4.5 决策树算法中采用的机制。
给定样本集 $D$ 和连续属性 $a$，假如 $a$ 在 $D$ 上出现了 $n$ 个不同的取值，将这些值从小到大进行排序，记为 ${a^1,a^2,…,a^n}$。基于划分点 $t$ 可将 $D$ 分为子集 $D_t^{-}$ 和 $D_t^+$，其中 $D_t^-$ 包含那些在属性 $a$ 上取值不大于 $t$ 的样本，$D_t^+$ 则包含那些在属性 $a$ 上取值大于 $t$ 的样本。显然，对相邻的属性取值 $a^i$ 与 $a^{i+1}$ 来说，$t$ 在区间 $[a^i,a^{i+1})$ 中取任意值所产生的划分结果相同。因此，对连续属性 $a$，我们可考察包含 $n-1$ 个元素的候选划分点集合
\[T_a = \Big\{\frac{a^i + a^{i+1}}{2} \text{ | } 1\le i \le n-1\Big\} \tag{4.1}\]即把区间 $[a^i,a^{i+1})$ 的中位点 $\frac{a^i + a^{i+1}}{2}$ 作为候选划分点。然后，我们就可像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。
可将划分点设为该属性在训练集中出现的不大于中位点的最大值，从而使得最终决策树使用的划分点都在训练集中出现过。
例如，可对 $(2.2)$ 稍加改造
\[\begin{align} \text{Gain}(D,a) &= \max_{t \in T_a} \text{Gain}(D,a,t)\\ &= \max_{t\in T_a} \text{Ent}(D) - \sum_{\lambda \in \{-,+\}}\frac{\vert D_t^\lambda \vert}{\vert D \vert} \text{Ent}(D_t^\lambda) \end{align} \tag{4.2}\]其中 $\text{Gain}(D,a,t)$ 是样本集 $D$ 基于划分点 $t$ 二分后的信息增益。于是，我们就可选择使 $\text{Gain}(D,a,t)$ 最大化的划分点。
需要注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。例如在父结点上使用了“密度 $\le 0.381$”，不会禁止在子结点上使用“密度 $\le 0.294$”。
缺失值处理
现实任务中常会遇到不完整样本，即样本的某些属性值缺失。如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对数据信息极大地浪费。
我们需要解决两个问题：
- 如果在属性值缺失的情况下进行划分属性选择？
- 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
给定训练集 $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,…,\vert \mathcal{Y}\vert$) 的样本子集，则显然有 $\tilde{D} = \bigcup_{k=1}^{\vert \mathcal{Y}\vert}\tilde{D}_k$，$\tilde{D} = \bigcup_{v=1}^V \tilde{D}^v$。假定我们为每一个样本 $\boldsymbol{x}$ 赋一个权重 $w_{\boldsymbol{x}}$，并定义
\[\begin{align} \rho &= \frac{\sum_{\boldsymbol{x}\in\tilde{D}} w_{\boldsymbol{x}}}{\sum_{\boldsymbol{x}\in D} w_{\boldsymbol{x}}}\\ \tilde{p}_k &=\frac{\sum_{\boldsymbol{x}\in\tilde{D}_k}w_{\boldsymbol{x}}}{\sum_{\boldsymbol{x}\in\tilde{D}}w_{\boldsymbol{x}}} \quad(1\le k\le \vert\mathcal{Y}\vert)\\ \tilde{r}_v &= \frac{\sum_{\boldsymbol{x}\in\tilde{D}^v} w_{\boldsymbol{x}}}{\sum_{\boldsymbol{x}\in\tilde{D}}w_{\boldsymbol{x}}} \quad(1\le v\le V) \end{align} \tag{4.3}\]在决策树学习开始阶段，根结点中各样本的权重初始化 1。
直观地看，对属性 $a$，$\rho$ 表示无缺失值样本所占的比例，$\tilde{p}_k$ 表示无缺失值样本中第 $k$ 类所占的比例，$\tilde{r}_v$ 则表示无缺失值样本中在属性 $a$ 上取值 $a^v$ 的样本所占的比例。显然，$\sum_{k=1}^{\vert\mathcal{Y}\vert}\tilde{p}_k = 1$，$\sum_{v=1}^V\tilde{r}_v = 1$。
基于上述定义，我们可将信息增益的计算式 $(2.2)$ 推广为
\[\begin{align} \text{Gain}(D,a) &= \rho \times \text{Gain}(\tilde{D},a)\\ &= \rho \times \Bigg(\text{Ent}\Big(\tilde{D}\Big) - \sum_{v=1}^V \tilde{r}_v \text{Ent}\Big(\tilde{D}^v\Big)\Bigg) \end{align} \tag{4.4}\]其中由 $(2.1)$，有
\[\text{Ent}(\tilde{D}) = -\sum_{k=1}^{\vert \mathcal{Y} \vert} \tilde{p}_k \log_2 \tilde{p}_k \tag{4.5}\]对问题 2，若样本 $\boldsymbol{x}$ 在划分属性 $a$ 上的取值已知，则将 $\boldsymbol{x}$ 划入与其取值对应的子结点，且样本权值在子结点中保持为 $w_\boldsymbol{x}$。若样本 $\boldsymbol{x}$ 在划分属性 $a$ 上的取值未知，则将 $\boldsymbol{x}$ 同时划入所有子结点，且样本权值在与属性值 $a^v$ 对应的子结点中调整为 $\tilde{r}_v\cdot w_{\boldsymbol{x}}$；直观地看，这就是让同一个样本以不同的概率划入到不同的子结点中去。C4.5 算法使用了上述解决方案。
参考
李航《统计学习方法》
周志华《机器学习》