分类器融合（3）：决策树

决策树简介

决策树是一种对实例分类的树形结构，由节点（node）和有向边（directed edge）组成，内部节点（internal node）表示特征或属性，叶节点（leaf node）表示类[1, P. 55]。决策树既可以看成if-then规则的集合，也可表示给定特征条件下类别的概率密度分布[1, P. 56]。从分类器融合的角度，决策树是一种有条件分类器融合的学习模型[2]。常用的决策树学习算法有 ID3、C4.5 和 C&RT（也记为 CART）。

决策树在实际中很有用，它可解释性强（广泛应用于商业和医学数据分析），简单容易实现，能高效的学习和预测，但是它是启发式方法，理论基础较薄弱。

［左］：观看MOOC课程的决策树［右］：递归定义的决策树算法

上图左的决策树用来判断是否观看 MOOC 课程。决策树是分类器的有条件融合，在不同条件采用不同的$g_t(\mathbf x)$：

• 基本假设（base hypothesis）$g_t(\mathbf x)$：每条路径终点的叶子🍃，此处是常数。
• 条件$q_t(\mathbf x)$：每条路径的内部节点，$\mathbf x$在路径$t$上么？上图左中菱形区域。

决策树是递归结构，每个分支对应一颗子决策树 \[ G(\mathbf x)=\sum_{c=1}^C[[b(\mathbf x)=c]]\cdot G_c(\mathbf x)， \] $b(\mathbf x)$表示分支条件，$G_c(\mathbf x)$表示第$c$个分支的子树。

上图右展示了递归方式定义的决策树算法，从中可以看出，有4个方面需要决定：分支数目、分支条件、终止条件、基本假设。

特征选择

如果特征数目过多，计算复杂度过大，可以在决策树学习之前进行特征选择，只选择对训练数据有足够分类能力的特征。如果利用一个特征进行分类的结果与随机分类结果没有很大差别，则这个特征没有分类能力。通常特征选择的准则是信息增益或信息增益比[1, Pp. 58-63]。

熵（entropy）表示随机变量不确定性的度量，熵越大随机变量的不确定性就越大。某一维的特征$x$的概率记为$p(x)$，特征$x$的熵表示为 \begin{equation} H(p)=-\sum_{j=1}^Mp(x_j)\log p(x_j)， \end{equation} $M$表示特征$X$能取不同特征值的个数。对数以2为底或以e为底时熵的单位分别称为比特（bit）或纳特（nat）。从定义可知$0\leq H(p)\leq \log M$。条件熵（conditional entropy）$H(Y|X)$表示已知随机变量$X$的条件下，随机变量$Y$的不确定性，定义为给定$X$条件下$Y$的条件概率分布的熵对$X$的数学期望 \begin{equation} H(Y|X)=-\sum_{j=1}^Mp(x_j)H(Y|X=x_j)。 \end{equation} 当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，熵和条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。若有$0$概率，令$0\log 0=0$。信息增益（information gain）表示得知特征$X$而使类$Y$信息不确定性减少的程度。特征$A$对训练集$\mathcal D$的信息增益定义为 \begin{equation} g(\mathcal D,A)=H(\mathcal D)-H(\mathcal D|A)， \end{equation} 经验熵$H(\mathcal D)$表示对$\mathcal D$分类的不确定性，经验条件熵$H(\mathcal D|A)$表示在给定特征$A$时对$\mathcal D$分类的不确定度。显然，信息增益大的特征具有更强的分类能力。

当数据集的经验熵很大时，信息增益也会偏大，使用信息增益比（information gain ratio） \begin{equation} g_R(\mathcal D,A)={g(\mathcal D,A)\over H(\mathcal D)}， \end{equation} 可校正这一问题。

$|\mathcal D|$表示$\mathcal D$的样本容量（样本个数），$|\mathcal C_k|$表示类$\mathcal C_k$的样本个数，$\sum_{k=1}^K|\mathcal C_k|=|\mathcal D|$。根据特征$A$的取值，将$\mathcal D$划分为$M$个子集$\mathcal D_1,\mathcal D_1,\ldots,\mathcal D_M$，子集$\mathcal D_{j}$中属于类别$\mathcal C_k$的样本集为$\mathcal D_{jk}$，$\mathcal D_{jk}=\mathcal D_{j}\cap \mathcal C_k$。经验熵和经验条件熵计算方式为 \begin{equation} H(\mathcal D)=-\sum_{k=1}^K{|\mathcal C_k|\over |\mathcal D|}\log_2{|\mathcal C_k|\over |\mathcal D|}，\quad H(\mathcal D,A)=-\sum_{j=1}^M{|\mathcal D_j|\over |\mathcal D|}\sum_{k=1}^K{|\mathcal D_{jk}|\over |\mathcal D_j|}\log_2{|\mathcal D_{jk}|\over |\mathcal D_j|}。 \end{equation}

根据如下贷款数据表

利用信息增益准则可以选出最优特征。由表中数据计算经验熵 \[ H(\mathcal D)=-{9\over 15}\log_2{9\over 15}-{6\over 15}\log_2{6\over 15}=0.971， \] 年龄特征对数据集$\mathcal D$的经验条件熵为 \begin{aligned} H(\mathcal D,年龄)= &-{5\over 15}\left({2\over 5}\log_2{2\over 5}+{3\over 5}\log_2{3\over 5}\right)\\ &-{5\over 15}\left({3\over 5}\log_2{3\over 5}+{2\over 5}\log_2{2\over 5}\right)\\ &-{5\over 15}\left({4\over 5}\log_2{4\over 5}+{1\over 5}\log_2{1\over 5}\right)=0.888， \end{aligned} 年龄特征对数据集$\mathcal D$的信息增益为$g(\mathcal D,年龄)=0.971-0.888=0.083$，同样可得其它信息增益为 \[ g(\mathcal D,有工作)=0.324，\quad g(\mathcal D,有自己的房子)=0.420，\quad g(\mathcal D,借贷情况)=0.363， \] 信息增益最大的特征“有自己的房子”是最优特征。

分类回归树

分类回归树（C&RT，classification and regression tree）既可用于分类又可用于回归。它是二叉树，分支数目$C=2$，基本假设$g_t(\mathbf x)$返回$E_{in}$最优时的常数。C&RT 的$g_t(\mathbf x)$比较简单：

• 二分类或多分类问题（基于0／1误差度量$E_{in}$）：$\{y_n\}$中占大多数的类的标签；
• 回归问题（基于平方误差度量$E_{in}$）：$\{y_n\}$的均值。

C&RT用decision stump进行二元分支，利用数据集大小加权的不纯度作为分支条件， \begin{equation} b(\mathbf x)=\underset{\mbox{decision stumps }h(\mathbf x)}{\arg\min}\sum_{c=1}^2|\mathcal D_c\mbox{ with }h|\cdot\mbox{impurity}(\mathcal D_c\mbox{ with }h)， \label{eq:dtree-decision-stump} \end{equation} 选择加权不纯度最小的分支方法。若用decision stump对有$m$个不同的取值的特征进行划分，对有序的特征共有$m-1$种二分法，对无序的特征共有$2^{m-1}-1$种二分法[3, Pp. 14-15]。回归的不纯度采用回归误差 \begin{equation} \mbox{impurity}(\mathcal D)={1\over N}\sum_{n=1}^N(y_n-\bar y)^2， \end{equation} $\bar y$表示$\{y_n\}$的均值。分类的不纯度可采用分类误差 \begin{equation*} \mbox{impurity}(\mathcal D)={1\over N}\sum_{n=1}^N[[y_n\neq y^*]]， \end{equation*} $y^*$表示$\{y_n\}$中占大多数的类的标签，但通常采用的是Gini指数 \begin{equation} \mbox{impurity}(\mathcal D)=1-\sum_{k=1}^K\left({\sum_{n=1}^N[[y_n=k]]\over N}\right)^2， \end{equation} $k$表示类标签，${\sum_{n=1}^N[[y_n=k]]\over N}$就是类$k$在$\mathcal D$中占的比率，也可采用 \begin{equation*} \mbox{impurity}(\mathcal D)=1-\max_{1\leq k\leq K}{\sum_{n=1}^N[[y_n=k]]\over N}。 \end{equation*} $\mathcal D$中的类越分散不纯度越高，类似于熵；$\mathcal D$中数据属于同一类时不纯度为0。

分类回归树“被迫”停止生长的两个终止条件：

1. 所有$y_n$都相同，不纯度为0，返回$g_t(\mathbf x)=y_n$；
2. 所有$\mathbf x_n$都相同，不存在decision stump。

这种被迫停止生长的树称为完全成长树（fully-grown tree）。

C&RT = 完全成长树 ＋ 常数叶子🍃 ＋ 二元分支 ＋ 纯化。

决策树剪枝

如果所有的$\mathbf x_n$都不同，完全成长的决策树使得$E_{in}(G)=0$，这会导致过拟合（$E_{out}$很大），因为底层的树建立在很小的数据集$\mathcal D_c$上。也就是说，决策树的variance较大，数据很小的改变就可能得到很不一样的决策树。

决策树需要正则化机制避免过拟合。利用控制树叶数目$\Omega(G)$，正则化决策树 \begin{equation} \underset{\mbox{all possible }G}{\arg\min}E_{in}(G)+\lambda\Omega(G)， \end{equation} 称为剪枝（pruning）。通常是采用交叉验证选择$\lambda$。若要列举所有的$G$，计算量非常大，通常的做法是从完全成长树入手构造可能的$G$：

• $G^{(0)}$为完全成长树；
• $G^{(i)}=\arg\min_GE_{in}(G)$，$G$表示从$G^{(i-1)}$中移除一片叶子（实际是合并叶子，将叶节点的父节点作为新的叶节点）。

决策树优势

几乎没有哪种其它的机器学习算法拥有如此多优良特性，除非其它决策树。

一、可解释性好

二、容易处理多分类问题

三、容易处理类别特征

决策树通过decision stump \begin{equation} b(\mathbf x)=[[x_i\leq \theta]]+1\quad\theta\in\mathbb R， \end{equation} 可以对数值特征进行分类；利用决策子集（decision subset） \begin{equation} b(\mathbf x)=[[x_i\in S]]+1\quad S\in\{1,2,\ldots,K\}， \end{equation} 决策树也很容易进行基于类别特征的分类¹。

四、容易处理遗失特征

假设数据集中遗失了体重特征，人处理这类问题的方法有：

• 获取体重特征；
• 用身高特征代替。

决策树利用类似的代替思想，采用替代分支（surrogate branch）。在训练的时候训练可用的替代分支，利用替代分支可以得到和原来差不多的效果。当使用时遇到特征遗失，利用替代分支解决。

五、高效的训练非线性模型

C&RT vs. AdaBoost

参考资料

1. [1]李航, 统计学习方法. 北京: 清华大学出版社, 2012.
2. [2]H.-T. Lin, “Lecture 9: Decision Tree.” Coursera, 2015. [Online]
3. [3]W.-Y. Loh, “Classification and regression trees,” Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, vol. 1, pp. 14–23, 2011.

脚注