统计学习方法（四）：决策树
决策树
决策树 (decision tree) 是一种基本的分类与回归方法。本文主要讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示介于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。
模型
决策树是树状模型，由叶子结点和非叶子结点构成，非叶子结点表示一个特征或属性，叶子结点表示一个类。决策树的分类过程很简单，从根结点依次遍历，依据结点的取值选择对应的分支继续遍历直到到达叶子结点，返回对应的类。决策树的各非叶子结点的属性要求互斥且完备。
决策树的学习
决策树的学习目标是根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。通常来说，对训练数据集能够完全正确分类的决策树可能有多个，也可能一个都没有，因此我们需要的是让决策树尽可能符合训练数据集，同时对测试数据也有很好的预测作用，换言之，我们的目标是保证准确率的基础上尽量提高决策树的泛化能力。
决策树学习的损失函数通常是正则化的极大似然函数，决策树的学习策略是以损失函数为目标函数的最小化。由于从所有可能的决策树中选择最优决策树是 \(NP\) 完全问题，因此通常用启发式算法来得到次最优 (sub-optimal) 的决策树。
决策树的学习过程为递归地选择最优特征并对该特征加以划分直到训练数据的每一个特征子集都对应一个类。很显然这样划分决策树容易造成过拟合现象，解决的方法通常为自下而上对决策树进行剪枝，剪掉贡献较小的特征，使其退回到父结点甚至更高的结点。因此决策树学习算法包含特征选择、决策树的生成和决策树的剪枝。
特征选择
特征选择的目的在于选出对训练数据具有分类能力的特征，提高决策树的学习效率，如果某个特征没有分类能力，则在学习过程中抛弃这些特征对学习的效果也不会有太大的影响。用于决定特征选择的方式是信息增益 (information gain) 或信息增益比。
信息增益
熵
首先给出熵 (entropy) 的定义：在信息论与概率统计中，熵是表示随机变量不确定性的度量。设 \(X\) 是一个取有限个值的离散随机变量，其概率随机分布为 \[ P(X=x_i)=p_i, \space \space \space \space i=1,2,\cdots,n \] 则随机变量 \(X\) 的熵定义为 \[ H(X)=-\sum_{i=1}^n{p_i log p_i} \] 其中 \(log\) 可以以 \(2\) 为底，也可以以 \(e\) 为底，这时熵的单位分别称作比特 (bit) 或纳特 (nat)。若 \(p_i=0\)，则定义 \(p_i log p_i=0\)。
由定义知，熵只依赖 \(X\) 的分布，与 \(X\) 的取值无关，所以也可将 \(X\) 的熵记作 \(H(p)\)，即 \[ H(p) = -\sum_{i=1}^n{p_i log p_i} \] 熵越大，随机变量的不确定性就越大，从定义可知 \[ 0 \leqslant H(p) \leqslant log \space n \]
条件熵
条件熵 \(H(Y|X)\) 表示在已知随机变量 \(X\) 的条件下随机变量 \(Y\) 的不确定性。随机变量 \(X\) 给定的条件下随机变量 \(Y\) 的条件熵 (conditional entropy) \(H(Y|X)\)，定义为 \(X\) 给定条件下 \(Y\) 的条件概率分布的熵对 \(X\) 的数学期望 \[ H(Y|X) = \sum_{i=1}^n{p_iH(Y|X = x_i)} \] 这里 \(p_i=P(X=x_i), i=1,2,\dots, n\)。
当熵和条件熵中的概率由数据估计 (特别是极大似然估计) 得到时，所对应的熵与条件熵分别称为经验熵 (empirical entropy) 和条件经验熵 (empirical conditional entropy)。
信息增益表示得知特征 \(X\) 的信息而使得类 \(Y\) 的信息的不确定性减少的程度。
特征 \(A\) 对训练数据集 \(D\) 的信息增益 \(g(D,A)\) 定义为集合 \(D\) 的经验熵 \(H(D)\) 与特征 \(A\) 给定条件下 \(D\) 的经验条件熵 \(H(D|A)\) 之差，即 \[ g(D, A) = H(D) - H(D|A) \] 一般地，熵 \(H(Y)\) 与条件熵 \(H(Y|X)\) 之差称为互信息 (mutual information)。
决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
决策树学习应用信息增益准则选择特征，对训练数据集计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征作为当前结点的特征。
信息增益比
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比 (information gain ratio) 可以对这一问题进行校正。
特征 \(A\) 对训练数据集 \(D\) 的信息增益比 \(g_R(D,A)\) 定义为其信息增益 \(g(D,A)\) 与训练数据集 \(D\) 关于特征 \(A\) 的值的熵 \(H_A(D)\) 之比，即 \[ g_R(D,A) = \frac{g(D,A)}{H_A(D)} \] 其中，\(H_A(D)=-\sum_{i=1}^n{\frac{|D_i|}{|D|}\space log_2\space \frac{|D_i|}{|D|}}\)，\(n\) 是特征 \(A\) 取值的个数。
决策树的生成
ID3 算法
ID3 算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点，再对子结点递归地调用以上方法，直到所有特征的信息增益均很小或没有特征可以选择。
ID3 相当于用极大似然法进行概率模型的选择。
C4.5 算法
C4.5 算法和 ID3 算法类似，区别在于 C4.5 算法利用信息增益比来选择特征。
决策树的剪枝
应用上述算法生成的决策树有一个很大的缺点，那就是容易过拟合，对于测试数据集有很好的预测，但对未知的测试数据却很难取得好的效果，解决这个问题的办法就是对决策树进行剪枝，可以证明，对决策树的剪枝就是利用带有正则化的极大似然估计进行模型选择。
首先定义决策树的损失函数，设树的叶结点个数为 \(|T|\)，\(t\) 是树 \(T\) 的叶结点，该叶结点有 \(N_i\) 个样本点，其中 \(k\) 类的样本点有 \(N_{tk}\) 个，\(k=1,2,\cdots,K\)，\(H_t(T)\) 为叶结点 \(t\) 上的经验熵，\(\alpha \geqslant 0\) 为参数，则决策树学习的损失函数可以定义为 \[ C_\alpha (T)=\sum_{t=1}^{|T|}{N_tH_t(T) + \alpha |T|} \] 其中经验熵为 \[ H_t(T)=-\sum_{k}{\frac{N_{tk}}{N_t} log\frac{N_{tk}}{N_t}} \] 对于每一叶结点，考察剪枝后的树与原树的损失函数，若剪枝后损失降低，则剪掉该结点，向上回退。由于两棵树的损失函数计算只在局部进行，可以使用动态规划加速计算。
分类与回归树
分类与回归树 (classification and regression tree, CART) 是应用广泛的决策树学习方法，可应用于分类和回归，该算法同样由特征选择、树的生成和树的剪枝组成。
CART 假设决策树树二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
CART 生成
决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数 (Gini index) 最小化准则，进行特征选择，生成二叉树。
回归树的生成
设 \(X\) 和 \(Y\) 分别为输入和输出变量，且 \(Y\) 是连续变量。一颗回归树对应着输入空间 (即特征空间) 的一个划分以及在划分单元上的输出值。假设已将输入空间划分为 \(M\) 个单元 \(R_1,R_2,\cdots,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\) 表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。则单元 \(R_m\) 上的 \(c_m\) 的最优值 \(\hat{c}_m\) 是 \(R_m\) 上的所有输入实例 \(x_i\) 对应的 \(y_i\) 的均值，即 \[ \hat{c}_m=avg(y_i|x_i\in R_m) \] 对于输入空间的划分可以用启发式的方法，选择第 \(j\) 个特征 \(x^{(j)}\) 和它的取值 \(s\) 作为切分变量 (splitting variable) 和切分点 (splitting point)，并定义两个区域 \[ R_1(j,s) = \{x|x^{(j)}\leqslant s\} \\ R_2(j,s) = \{x|x^{(j)}\gt s\} \] 随后遍历变量 \(j\)，对固定的切分变量 \(j\) 扫面切分点 \(s\)，使 \[ \underset{j,s}{min}[\underset{c_1}{min}\sum_{x_i\in R_1(j,s)}{(y_i-c_1)^2}+\underset{c_2}{min}\sum_{x_i\in R_2(j,s)}{(y_i-c_2)}^2] \] 最小化。其中 \(c_1\) 和 \(c_2\) 分别两个区域的输出值 (即属于该实例的样本的输出的平均值)。
最后更新 \(\hat{c}_m\)，对两个区域递归地进行划分直到满足停止条件。这样生成的回归树通常称为最小二乘回归树 (least squares regression tree)。
分类树的生成
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
首先对基尼指数定义：在分类问题中，假设有 \(K\) 个类，样本点属于第 \(k\) 类的概率为 \(p_k\)，则概率分布的基尼指数定义为 \[ Gini(p)=\sum_{k=1}^K{p_k(1-p_k)}=1-\sum_{k=1}^K{p_k^2} \] 对于二分类问题，若样本点属于第 \(1\) 个类的概率是 \(p\)，则概率分布的基尼指数为 \[ Gini(p) = 2p(1-p) \] 对于给定的样本集合 \(D\)，其基尼指数为 \[ Gini(D)=1-\sum_{k=1}^K{(\frac{|C_k|}{|D|})^2} \] 其中，\(C_k\) 是 \(D\) 中属于第 \(k\) 类的样本子集，\(K\) 是类的个数。
如果样本集合 \(D\) 根据特征 \(A\) 是否取某一可能值 \(a\) 被分割成 \(D_1\) 和 \(D_2\) 两部分，即 \[ D_1=\{(x,y) \in D | A(x)=a\} \\ D_2 = D - D_1 \] 则在特征 \(A\) 的条件下，集合 \(D\) 的基尼指数定义为 \[ Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2) \] 由此，可对某一个特征的所有切分点依次计算基尼指数，选择基尼系数最小的特征和切分点作为目标特征和目标切分点，构建决策树。
CART 剪枝
首先定义子树的损失函数 \[ C_\alpha(T) = C(T) + \alpha |T| \] 其中，\(C(T)\) 为对训练数据的预测误差 (如基尼指数)，\(|T|\) 为子树的叶结点个数，\(C_\alpha(T)\) 是参数为 \(\alpha\) 时的子树 \(T\) 的整体损失。
从整体树 \(T_0\) 开始剪枝。对 \(T_0\) 的任意内部结点 \(t\)，以 \(t\) 为单结点树的损失函数为 \[ C_\alpha(t) = C(t) + \alpha \] 以 \(t\) 为根结点的子树 \(T_t\) 的损失函数是 \[ C_\alpha(T_t) = C(T_t) + \alpha |T_t| \] 当 \(\alpha = 0\) 及 \(\alpha\) 充分小时，有不等式 \[ C_\alpha(T_t) \lt C_\alpha(t) \] 当 \(\alpha\) 增大时，在某一 \(\alpha\) 有 \[ C_\alpha(T_t) = C_\alpha(t) \] 当 \(\alpha\) 再增大时，不等式反向，只要 \(\alpha = \frac{C(t)-C(T_t)}{|T_t|-1}\)，\(T_t\) 与 \(t\) 有相同的函数损失值，而 \(t\) 的结点少，因此 \(t\) 比 \(T_t\) 更可取，故对 \(T_t\) 剪枝。
则可以得到剪枝算法：对 \(T_0\) 中的每个内部结点 \(t\)，计算 \[ g(t) = \frac{C(t)-C(T_t)}{|T_t|-1} \] 它表示剪枝后整体损失函数减少的程度。在 \(T_0\) 中剪去 \(g(t)\) 最小的 \(T_t\)，将得到的子树作为 \(T_1\)，同时将该最小的 \(g(t)\) 设为 \(\alpha_1\)，则 \(T_1\) 为区间 \([\alpha_1, \alpha_2)\) 的最优子树。如此剪枝至根节点，在这一过程中不断增加 \(\alpha\) 的值，产生新的区间。
最后对所有区间对应的子树分别计算误差，选择最小的作为最优子树。
停止条件
以下是决策树节点停止分裂的一般性条件：
达到最小节点数
当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。
熵或者基尼指数小于阀值
由上述可知，熵和基尼指数的大小表示数据的复杂程度，当熵或者基尼指数过小时，表示数据的纯度比较大，如果熵或者基尼指数小于一定程度数，节点停止分裂。
决策树的深度达到指定的条件
节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为1，因为这些节点与跟节点的距离为1，子节点的深度要比父节点的深度大1。决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。
所有特征已经使用完毕，不能继续进行分裂
被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶子节点。