决策树

树的生成

决策树（Decision Tree）是一种用于分类和回归的有监督学习方法。其目标是创建一个模型，通过学习从数据特性中归纳出一组分类规则来预测目标变量的值。下图是一颗决策树

决策树是一种由节点（node）和有向边（directed edge）组成的树形结构。从根节点（root node）开始，包含若干内部节点（internal node）和叶节点（leaf node）。其中每个叶节点对应一种分类结果，其他每个节点表示一个特征的判断条件，每个分支代表一个判断结果的输出。

其实决策树可以看做一个if-then规则的集合。我们从决策树的根结点到每一个都叶结点构建一条规则，并且我们将要预测的实例都可以被一条路径或者一条规则所覆盖。

Hunt 算法：决策树学习旨在构建一个泛化能力好，并且复杂度小的决策树。因为从可能的决策树中直接选取最优决策树是 NP 完全问题，可构造的决策树的数目达指数级，找出最佳决策树在计算上时不可行的。现实中采用启发式方法，在合理的时间学习一颗次优的决策树。

给定的数据集

$D=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),\cdots,(\mathbf x_N,y_N\}$

包含 $N$ 个样本， $p$ 个特征。其中，第 $i$ 个样本的特征向量为 $\mathbf x_i=(x_{i1},x_{i2},\cdots,x_{ip})^T$ 。目标变量 $y_i\in\{c_1,c_2,\cdots,c_K\}$ ，有 $K$ 个类别。

Hunt 算法以递归方式建立决策树，使得各分支结点所包含的样本尽可能属于同一类别。设节点 $t$ 处的数据集为 $D_t$ ，样本量为 $N_t$ 。决策树的生成流程如下：

在根节点从所有训练样本开始；
在节点 $t$ 处，选择一个特征 $x_t$ 将数据集 $D_t$ 划分成更小的子集；
对于每个子节点，递归的调用此算法，只到满足停止条件。

从上述步骤可以看出，决策树生成过程中有两个重要的问题

如何选择最优的划分特征：常用的算法有 ID3、C4.5 和 CART
什么时候停止划分：
- 当一个节点100%是一个类别时；
- 当分裂一个节点导致树超过最大深度时 (maximum depth)；
- 如果分裂一个节点导致的纯度提升低于阈值；
- 如果一个节点的样本数低于阈值。

限制决策树深度和设置阈值的一个原因是通过保持树的小巧而不容易导致过拟合

决策树的特点

决策树的一些优点：

决策树是一种非参数模型。换句话说，它不要求任何先验假设，不假定类和特征服从一定概率分布。
决策树可以被可视化，简单直观。
对于异常点的容错能力好，健壮性高。

决策树的缺点包括：

决策树算法非常容易过拟合，导致泛化能力不强，可以通过剪枝改进。
决策树可能是不稳定的。事实证明，只需要改变极少量训练样本，信息增益最大的特征就可能发生改变，会生成一颗完全不同的树。可以通过集成学习来缓解这个问题。
寻找最优的决策树是一个NP完全问题，我们一般是通过启发式算法（如贪婪算法），容易陷入局部最优。可以通过集成学习之类的方法来改善。
有些比较复杂的边界关系，决策树很难学习。

特征二元化

连续特征离散化：待划分的特征分为离散型和连续型两种。对于离散型的特征，按照特征值进行划分，每个特征值对应一个子节点；对于连续型的数据，由于可取值数目不再有限，一般需要离散化，常用二分法处理。

假定第 $j$ 个特征 $x^{(j)}$ 是连续变量，若样本中 $x$ 有 $K$ 个值，选取这些值的 $K-1$ 个中点值作为候选切分值。定义候选值是 $s$ 切分的两个区域

$R_1(j,s)=\{(\mathbf x,y)|x^{(j)}\leqslant s\} \quad \text{and}\quad R_2(j,s)=\{(\mathbf x,y)|x^{(j)}> s\}$

以基尼指数为例，求解最优切分值

$\arg\min_{s}[w_1\text{Gini}(R_1(j,s))+w_2\text{Gini}(R_2(j,s))]$

其中， $w_1,w_2$ 是区域 $R_i,R_2$ 的样本数占比。

然后，我们就可以像离散特征一样来使用。需注意的是，与离散特征不同，若当前结点为连续特征，该特征还可作为其后代结点的划分特征。

one-hot encoding：某些算法（CART）只产生二元划分。如果一个离散特征可以取 $K$ 个值，可以通过创建 $K$ 个取值为0或1的二元特征来替换。如下图示例

划分特征选择

显然，决策树学习的关键在于划分数据集，我们希望不断地选取局部最优的特征，将无序的数据变得更加有序，即结点的纯度 (purity) 越来越高。由于纯度的度量方法不同，也就导致了学习算法的不同，常用的算法有 ID3 、C4.5和 CART。

信息增益

信息熵（information entropy）是度量数据集纯度的最常用的指标。给定的数据集

$D=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),\cdots,(\mathbf x_N,y_N\}$

包含 $N$ 个样本， $p$ 个特征。其中，第 $i$ 个样本的特征向量为 $\mathbf x_i=(x_{i1},x_{i2},\cdots,x_{ip})^T$ 。目标变量 $y_i\in\{c_1,c_2,\cdots,c_K\}$ ，有 $K$ 个类别。经验分布为

$\mathbb P(y=c_k)=P_k$

则信息熵为

$H(D)=-\sum_{k=1}^KP_k\log P_k$

注意，计算信息熵时约定 $0\log 0 = 0$ 。由定义可知，熵只依赖于 $y$ 的分布，与取值无关，所以也可将熵记作 $H(P)$ 。

对于二分类问题，目标变量 $y_i\in \{0,1\}$ 。正样本比例为 $P_1\ (0\leqslant P_1\leqslant 1)$ ，则负样本比例 $P_0=1-P_1$ 。信息熵可写为

$H(P_1)=-P_1\log P_1-(1-P_1)\log (1-P_1)$

二元变量的熵曲线如下图

条件熵（condition entropy）用来表示离散特征 $x$ 划分后的数据集 $D$ 纯度。使用划分后子集的熵的加权平均值来度量

$H(D|x)=\sum_{m=1}^M w_mH(D_m)$

其中，离散特征值 $x$ 有 $M$ 个值。 $w_m=N_m/N$ 代表离散特征 $x$ 划分后的子集 $D_m$ 的样本数占比， $H(D_m)$ 代表子集 $D_m$ 的信息熵。条件熵一般小于熵，例如，知道西瓜的色泽（青绿,乌黑,浅白）后，西瓜质量的不确定性就会减少了。

信息增益（Information Gain）表示使用特征 $x$ 的信息进行划分而使数据集 $D$ 纯度提升的程度

$\text{Gain}(D,x)=H(D)-H(D|x)$

以二元离散特征 $x$ 为例，将二分类数据集 $D$ 划分为 $D^{\text{left}}$ 和 $D^{\text{left}}$ 两个子集，则信息增益为

$\text{Gain}(D,x)=H(P_1)-\left(w^{\text{left}}H(P_1^{\text{left}})+w^{\text{right}}H(P_1^{\text{right}})\right)$

其中 $P_1$ 表示子集中正样本的比例， $w$ 表示子集的样本数占比。

ID3（Iterative Dichotomiser 3, 迭代二分器 3）算法在迭代中选取信息增益最大的特征进行划分

$\arg\max\limits_{x}\text{Gain}(D,x)$

其中特征 $x\in\{x_i,x_2,\cdots,x_p\}$ 。对于所有的节点来说，节点处数据集的熵是个不变的值，所以最大化信息增益等价于最小化条件熵。

以吴恩达老师的猫分类数据集为例：

根节点的熵为： $H(P_1^{\text{root}})=H(0.5)=-\cfrac{1}{2}\log \cfrac{1}{2}-\cfrac{1}{2}\log \cfrac{1}{2}=1$

然后，计算各特征的信息增益：

Ear shape: $H(0.5)-(\cfrac{3}{10}H(0.67)+\cfrac{4}{10}H(0.75)+\cfrac{3}{10}H(0))=0.4$
Face shape: $H(0.5)-(\cfrac{7}{10}H(0.57)+\cfrac{3}{10}H(0.33))=0.03$
Whiskers: $H(0.5)-(\cfrac{4}{10}H(0.75)+\cfrac{6}{10}H(0.33))=0.12$
Weight: $H(0.5)-(\cfrac{4}{10}H(1)+\cfrac{6}{10}H(0.17))=0.61$

显然，Weight ⩽ 9 的信息增益最大，于是Weight被选为在根节点划分的特征。类似的，再对每个分支结点进行上述操作，进一步划分，最终得到整颗决策树。

信息增益率

从信息增益的公式中，其实可以看出，信息增益准则偏向取值较多的特征。原因是当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的条件熵更低。为减少这种偏好可能带来的不利影响，C4.5通过信息增益率（Information Gain Rate）来选择最优划分特征

$\text{Gain\_rate}(D,x)=\frac{\text{Gain}(D,x)}{\text{IV}(x)}$

其中 $\text{IV}(x)$ 称为特征 $x$ 的固有值（intrinsic value）

$\text{IV}(x)=-\sum_{m=1}^Mw_m\log w_m$

其中，离散特征值 $x$ 有 $M$ 个值。 $w_m=N_m/N$ 代表离散特征 $x$ 划分后的子集 $D_m$ 的样本数占比。 $\text{IV}(x)$ 可看作数据集 $D$ 关于 $x$ 的信息熵，特征 $x$ 的取值越多，通常 $\text{IV}(x)$ 越大。

需注意的是，信息增益率准对可取值数目较少的特征有所偏好。因此， C4.5算法并不是直接选择增益率最大的特征划分，而是使用了一个启发式：先从候选特征中找出信息增益高于平均水平的特征，再从中选择增益率最高的划分。

基尼指数

基尼指数（Gini Index）给定的数据集

$D=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),\cdots,(\mathbf x_N,y_N\}$

$\mathbb P(y=c_k)=P_k$

基尼指数可表示数据集 $D$ 的纯度

$\text{Gini}(D)=\sum_{k=1}^KP_k(1-P_k)=1-\sum_{k=1}^KP_k^2$

直观来说，基尼指数反应了从数据集中随机抽取两个样本，其类别不一致的概率。因此，基尼指数越小，则数据集的纯度越高。

对于二分类问题，目标变量 $y_i\in \{0,1\}$ 正样本比例为 $P_1\ (0\leqslant P_1\leqslant 1)$ ，则负样本比例 $P_0=1-P_1$ 。二分类变量的基尼指数可写为

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

数据集 $D$ 在离散特征 $x$ 划分后的基尼指数定义为

$\text{Gini}(D,x)=\sum_{m=1}^Mw_m\text{Gini}(D_m)$

可理解为划分后子集基尼指数的加权平均值。其中，离散特征 $x$ 有 $M$ 个值， $w_m=N_m/M$ 代表离散特征 $x$ 划分后的子集 $D_m$ 的样本数占比， $\text{Gini}(D_m)$ 代表子集 $D_m$ 的基尼指数。

CART（Classification and Regression Trees）是使用划分后基尼指数最小的特征作为最优划分特征

$\arg\min\limits_{x}\text{Gini}(D,x)$

同时，CART使用二叉树准则减少对取值较多特征的偏向，并且可以分类也可以回归，也提供了优化的剪枝策略。

回归树

给定的数据集

$D=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),\cdots,(\mathbf x_N,y_N\}$

包含 $N$ 个样本， $p$ 个特征。其中，第 $i$ 个样本的特征向量为 $\mathbf x_i=(x_{i1},x_{i2},\cdots,x_{ip})^T$ 。目标变量 $y_i\in\R$ 。

假设回归树将特征空间划分为 $J$ 个互不相交的区域 $R_1,R_2,\cdots,R_J$ ，每个区域 $R_j$ 对应树的一个叶结点，并且在每个叶节点上有个固定的输出值 $c_j$ 。规则为

$\mathbf x\in R_j \implies T(\mathbf x)=c_j$

那么树可以表示为

$T(\mathbf x;\Theta)=\sum_{j=1}^Jc_j\mathbb I(\mathbf x\in R_j)$

参数 $\Theta=\{(R_1,c_1),(R_2,c_2),\cdots,(R_J,c_J)\}$ 表示树的区域划分和对应的值， $J$ 表示树的复杂度（即叶节点的个数）。

回归树使用平方误差最小的值作为最优输出值。易知，区域 $R_j$ 上的最优值 $c_j$ 对应此区域上所有目标变量 $y_i$ 的平均值

$c_j=\bar y,\quad y_i\in R_j$

回归树使用加权均方误差选择最优划分特征。由于输出值 $c_j$ 为区域 $R_j$ 目标变量的平均值，所以区域 $R_j$ 的均方误差等价于方差。设节点 $t$ 处的区域数据集为 $D_t$ ，样本数为 $N_t$ ，则划分特征为

$\arg\min\limits_{x}\sum_{m=1}^Mw_{tm}\text{var}(D_{tm})$

其中，离散特征 $x$ 有 $M$ 个值。 $D_{tm}$ 为节点 $t$ 处特征 $x$ 划分的子集， $w_{tm}=N_{tm}/N_t$ 为子集的样本数占比。

剪枝处理

递归生成的决策树往往过于复杂，从而过拟合。对决策树进行简化的过程称为剪枝（pruning），剪枝的基本策略有预剪枝和后剪枝。剪枝过程中一般使用验证集评估决策树泛化能力的提升。

决策树学习的代价函数定义为

$C_\alpha(T)=C(T)+\alpha|T|$

其中， $|T|$ 是决策树 $T$ 中叶节点个数， $\alpha$ 是平衡树的复杂度和不纯度的超参数。 $C(T)$ 是叶节点不纯度的加权平均值。以基尼指数为例，给定数据集 $D$ ，样本数为 $N$ ，则

$C(T)=\sum_tw_t\text{Gini}(D_t)$

其中， $D_t$ 为叶节点 $t$ 处的数据集， $w_t=N_t/N$ 为叶节点 $t$ 处的样本数占比。

预剪枝：（pre-pruning）是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。

预剪枝使得决策树的很多分支都没有展开，限制减少了决策树的时间开销，同时也给预剪枝决策树带来了欠拟含的风险。

后剪枝：（post-pruning）先从训练集生成一棵完整的决策树，然后剪掉一些叶结点或叶结点以上的子树，若能带来决策树泛化性能提升，则将其父结点作为新的叶结点，从而递归的简化生成的决策树。

一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树，但决策树的时间开销要大得多。

CART 剪枝：首先从生成的决策树 $T_0$ 底端开始不断剪枝，直到根节点，形成一个子树序列 $\{T_0,T_1,\cdots,T_n\}$ 。然后通过交叉验证法选择最优子树。

决策边界

若我们把每个特征视为坐标空间中的一个坐标轴，则每个样本对应一个数据点，两个不同类之间的边界称为决策边界（decision boundary）。决策树所形成的分类边界有一个明显的特点：由于节点测试只涉及单个特征，它的决策边界由若干个与坐标轴平行的分段组成。这就限制了决策树对连续特征之间复杂关系的建模能力。