决策树（Decision Tree）是一种基本的分类与回归方法。本章主要讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据利用决策树模型进行分类。决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。下图是一个决策树模型。

具有两个可能结果（例如 true 或 false）的条件称为二元条件。仅包含二元条件的决策树称为二元决策树。非二元条件有两种以上的可能结果。因此，非二元条件比二元条件具有更强的区分能力。包含一个或多个非二元条件的决策称为非二元决策树。过于强大的条件也更容易过拟合，因此，决策森林通常使用二元决策树。

选择最佳的属性

特征选择在于选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。

熵和信息增益

熵（Entropy）是一个随机变量不确定性的度量。设 $X$ 是一个取有限个值的离散随机变量，其概率分布为

$P(X = x_i) = p_i, \quad i = 1, 2, \cdots, n$

则随机变量 $X$ 的熵定义为

$\begin{align} H(X) = -\sum_{i=1}^n p_i \log p_i \end{align}$

若 $p_i = 0$ ，则定义 $0 \log 0 = 0$ 。通常，式中的对数以 2 为底或以 e 为底（自然对数），这时熵的单位分别称作比特（bit）或纳特（nat）。由定义可知，熵只依赖于 $X$ 的分布，而与 $X$ 的取值无关，所以也可将 $X$ 的熵记作 $H(p)$ ，即

$\begin{align} H(p) = -\sum_{i=1}^n p_i \log p_i \end{align}$

熵越大，随机变量的不确定性就越大。
设有随机变量 $(X,Y)$ ，其联合概率分布为

$P(X = x_i, Y = y_j) = p_{ij}, \quad i = 1, 2, \cdots, n, \quad j = 1, 2, \cdots, m$

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

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

这里， $p_i = P(X = x_i), \quad i = 1, 2, \cdots, n$ 。
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵 (Empirical Entropy) 和经验条件熵 (Empirical Conditional Entropy)。此时，如果有 0 概率，令 $0 \log 0 = 0$ 。
信息增益 (Information Gain) 表示得知特征 $X$ 的信息而使得类 $Y$ 的信息的不确定性减少的程度。
特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$ 定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差，即

$\begin{align} g(D,A) = H(D) - H(D|A) \end{align}$

一般地，熵 $H(Y)$ 与条件熵 $H(Y|X)$ 之差称为互信息（Mutual Information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
设训练数据集为 $D$ , $|D|$ 表示其样本容量，即样本个数。设有 $K$ 个类 $C_k$ ， $k = 1, 2, \cdots, K$ ， $|C_k|$ 为属于类 $C_k$ 的样本个数， $\sum_{k=1}^{K} |C_k| = |D|$ 。设特征 $A$ 有 $n$ 个不同的取值 $\{a_1, a_2, \cdots, a_n\}$ ，根据特征 $A$ 的取值将 $D$ 划分为 $n$ 个子集 $D_1, D_2, \cdots, D_n$ ， $|D_i|$ 为 $D_i$ 的样本个数， $\sum_{i=1}^{n} |D_i| = |D|$ 。记子集 $D_i$ 中属于类 $C_k$ 的样本的集合为 $D_{ik}$ ，即 $D_{ik} = D_i \cap C_k$ ， $|D_{ik}|$ 为 $D_{ik}$ 的样本个数。于是信息增益的步骤如下：

计算数据集 $D$ 的经验熵 $H(D)$
$H(D) = -\sum_{k=1}^{K} \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}$
计算特征 $A$ 对数据集 $D$ 的经验条件熵 $H(D|A)$
$H(D|A) = \sum_{i=1}^{n} \frac{|D_i|}{|D|} H(D_i) = -\sum_{i=1}^{n} \frac{|D_i|}{|D|} \sum_{k=1}^{K} \frac{|D_{ik}|}{|D_i|} \log_2 \frac{|D_{ik}|}{|D_i|}$
计算信息增益
$g(D, A) = H(D) - H(D|A)$

一般地，信息增益值最大的特征作为最优特征。
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比（Information Gain Ratio）可以对这一问题进行校正。这是特征选择的另一准则。特征 $A$ 对训练数据集 $D$ 的信息增益比 $g_R(D, A)$ 定义为其信息增益 $g(D, A)$ 与训练数据集 $D$ 关于特征 $A$ 的值的熵 $H_A(D)$ 之比，即

$\begin{align} g_R(D, A) = \frac{g(D, A)}{H_A(D)} \end{align}$

其中， $H_A(D) = -\sum_{i=1}^n \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}$ ， $n$ 是特征 $A$ 取值的个数。

基尼系数

基尼系数（Gini Index）是指根据数据集的类分布标记数据集中的随机数据点时，对此随机数据点进行错误分类的概率。分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$ ，则概率分布的基尼指数定义为

$\begin{align} \text{Gini}(p) = \sum_{k=1}^{K} p_k (1 - p_k) = 1 - \sum_{k=1}^{K} p_k^2 \end{align}$

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

$\text{Gini}(p) = 2p(1 - p)$

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

$\begin{align} \text{Gini}(D) = 1 - \sum_{k=1}^{K} \left( \frac{|C_k|}{|D|} \right)^2 \end{align}$

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

决策树的生成

ID3 算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一棵决策树。ID3 相当于用极大似然法进行概率模型的选择。
C4.5 算法与ID3 算法相似，C4.5 算法对ID3 算法进行了改进。C4.5 算法在生成的过程中，用信息增益比来选择特征。
分类与回归树（Classication And Regression Tree，CART）模型是应用广泛的决策树学习方法。CART 同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。以下将用于分类与回归的树统称为决策树。决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。
CART 剪枝是CART的一部分。它的目标是在构建出一个可能过拟合的庞大决策树后，通过移除对模型泛化能力贡献不大或导致过拟合的子树（分支），来简化模型、提高其在新数据上的预测性能。它基于在验证集上计算代价复杂度，目标是平衡模型的复杂度和预测误差。它是在决策树完全生长之后进行的后处理步骤，目的是得到一个更简单、更具有耐操性的模型。