决策树

什么是决策树？
模型和训练
特征选择：信息增益
决策树的生成
- ID3
- C4.5
决策树剪枝
CART算法、剪枝
Python、R实现
决策树相关面经和其他资料
小结

什么是决策树？

决策树（descion tree）是一种既可以做回归也可以分类的算法。其模型呈树状结构，我们主要讨论分类问题，可以认为其是 if-then 规则的集合。其优点在于模型的可解释性和分类速度较快。决策树学习通常包括3个步骤：特征选择（信息增益）、决策树生成和剪枝。

决策树模型

先来介绍一下决策树的定义。

决策树由节点（node）、有向边（directed edge）组成。节点分为内部节点（internal node）和叶节点（leaf
node）。内部节点表示一个特征（feature）或属性，叶节点表示一个类（class）。

首先我们要从根节点（root）开始，对实例的某一特征开始测试，根据结果，将实例分配到其子节点；这时，每一个子节点对应该特征的一个取值，如此递归对其进行测试和分配，直到达到叶节点。

所以我们也可以把决策树看成一个 if-then 规则的集合。从根节点到叶节点的每一条路径，我们都可以构建一条规则，路径上的内部节点的特征对应条件，而叶节点对应结论。并且每个实例被且仅被一条路景或者一条规则覆盖。

决策树还表示给定特征下类的条件概率分布。

我们可以将特征空间划分为互不相交的区域，决策树表示的条件概率分布由各个区域给定条件下类的条件概率分布组成。

在训练一个决策树的过程中，决策树学习用损失函数（正则化的极大似然函数），策略是以损失函数为目标函数的最小化。在损失函数确定之后，问题就变成了在损失函数意义下选择最优决策树的问题。但是我们实际上不能从所有可能的决策树中选取最优，我们一般近似求解这一最优化问题。

特征选择

为了提高决策树学习的效率，我们要选取对训练数据具有较强分类能力的特征，其准则一般是信息增益（比）。

先来介绍一下熵的定义，在信息论和概率统计中，熵（entropy）表示随机变量的不确定性（混乱程度）。设 $X$ 是一个取有限个值的离散随机变量，其概率分布为

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

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

$H(X) = -\sum_{i=1}^{n}p_ilogp_i$

熵越大也以为这随机变量的不确定性越大，熵只依赖于 $X$ 的分布，所以也可记为 $H(p)$ ，其随概率 $p$ 变化的曲线如图：

当 $p = 0$ 或 $p = 1$ ， $H(p) = 0$ ，随机变量完全没有不确定性。当 $p = 0.5$ 时， $H(p) = 1$ ，熵取值最大，随机变量不确定性最大。

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

$H(Y|X) = \sum_{i=1}^{n}p_iH(Y|X = x_i)$

信息增益（information gain）表示得知特征 $X$ 的信息而使得类 $Y$ 的信息的不确定性减少的程度。

一般来说，熵 $H(Y)$ 和条件熵 $H(Y|X)$ 之差称为互信息（mutual information），决策树学习使用信息增益准则选择特征，我们对训练集 $D$ ，计算每个特征的信息增益，并比较大小，选择信息增益最大的特征。

设训练数据集为 $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 \bigcap C_k$ ， $|D_{ik}|$ 为 $D_{ik}$ 的样本个数。于是信息增益的算法如下。

输入：训练数据集 $D$ 和特征 A；
输出：特征 $A$ 对训练集 $D$ 的信息增益 $g(D,A)$

（1）计算数据集 $D$ 的经验熵 $H(D)$
$H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$
（2）计算特征 $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_{i=1}^{K}\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|}$
（3）计算信息增益
$g(D,A)=H(D)-H(D|A)$

决策树的生成

ID3算法

ID3算法是由Quinlan首先提出的，该算法是以信息论为基础，以信息熵和信息增益为衡量标准，从而实现对数据的归纳分类。

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对子节点递归地调用以上方法，构建决策树；知道所有特征的信息增益均很小或没有特征可以选择为止。

C4.5算法

C4.5算法与ID3算法相似，并进行了改进，C4.5在生成的过程中，用信息增益比来选择特征。

既然信息增益可以计算，为什么C4.5还使用信息增益比？

在使用信息增益的时候，如果某个特征有很多取值，使用这个取值多的特征会得到大的信息增益，这个问题会出现很多分支，将数据划分更细，模型复杂度高，出现过拟合的机率更大。使用信息增益比就是为了解决偏向于选择取值较多的特征的问题. 使用信息增益比对取值多的特征加上的惩罚，对这个问题进行了校正。

信息增益比：

特征 $A$ 对训练数据集 $D$ 的信息增益比 $g_R(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练数据集 $D$ 关于特征 $A$ 的值的熵 $H_A(D)$ 的比

$g_R(D,A) = \frac{g(D,A)}{-\sum_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}}$

决策树的剪枝

决策树生成算法递归产生决策树，直到不能继续下去为止。这样的树往往会出现过拟合现象。那么可以考虑减少决策树的复杂度，对已生成的决策树进行简化。

在决策树学习中将已生成的树进行简化的过程叫做剪枝（pruning）。具体地，剪枝从已生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶节点，从而简化分类树模型。

决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）来实现。设树 $T$ 的叶节点个数为 $|T|$ ， $t$ 是树 $T$ 的叶节点，该叶节点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk}$ 个， $k = 1,2,\cdots,K$ ， $H_t(T)$ 为叶节点 $t$ 上的经验熵， $\alpha \geq 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}$

在损失函数中，第一个公式右端的第一项记作

$C(T) = \sum_{t=1}^{|T|}N_tH_t(T) = -\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_t}$

这时有

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

$C(T)$ 表示模型对训练数据的预测误差，即模型与训练数据的拟合程度， $|T|$ 表示模型复杂度，参数 $\alpha \geq 0$ 控制两者之间的影响。较大的 $\alpha$ 促使选择较简单的模型，较小的 $\alpha$ 促使选择较复杂的模型。 $\alpha = 0$ 意味着只考虑模型与训练程度的拟合程度，不考虑模型的复杂度。

所以决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。

CART 算法

分类与回归树模型由 Breiman 等人在1984年提出，是应用广泛的决策树学习方法。CART同样由特征选择、树的生成以及剪枝组成，既可以用于分类也可以用于回归。

CART 是在给定输入随机变量 $X$ 条件下输出随机变量 $Y$ 的条件概率分布的学习方法。CART 假设决策树是二叉树，内部节点特征的取值为是或者否，做分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入控件即特征空间划分为有限个单元，并在这些单元是哪个确定预测的概率分布。

CART 算法步骤：

决策树生成：基于训练数据生成决策树，生成的决策树尽量大
决策树剪枝：用验证数据对已经生成的树来剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

CART 的生成就是递归地构建二叉树的过程，对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。

对于回归树，我们采用最小二乘回归树生成算法：

输入：训练集 $D$
输出：回归树 $f(x)$
在训练集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树

（1）选择最优切分变量 $j$ 与切分点 $s$ ，求解
$\min_{j,s}\Bigg[\min_{c_1}\sum_{x_i \in R_1(j,s)}(y_i-c_1)^2+\min_{c_2}\sum_{x_i \in R_2(j,s)}(y_i-c_2)^2\Bigg]$
遍历变量 $j$ ，对固定的切分变量 $j$ 扫描切分点 $s$ ，选择使得上式达到最小值的对 $(j,s)$ 。

（2）用选定的对 $(j,s)$ 划分区域并决定相应的输出值：
$R_1(j,s) = \{x|x^{(j)}\leq s\}, \ R_2(j,s) = \{x|x^{(j)} > s\}$
$\hat c_m = \frac{1}{N_m}\sum_{x_i \in R_m(j,s)}y_i, \ x \in R_m, \ m = 1,2$

（3）继续对两个子区调用步骤（1），（2），直到满足停止条件。

（4）将输入空间划分为 $M$ 个区域 $R_1,R_2,\cdots, R_M$ ，生成决策树：
$f(x) = \sum_{m=1}^{M}\hat c_mI(x \in R_m)$

对于分类树，我们采用基尼指数选择最优特征，同时决定该特征的最庸二值切分点。

基尼指数：

分类问题中，假设有 $K$ 个类，样本点属于第 $K$ 类的概率为 $p_k$ ，则概率分布的基尼指数定义为：

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

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

$Gini(D) = 1 - \sum_{k=1}^{K}\Bigg(\frac{|C_k|}{|D|}\Bigg)^2$

基尼指数 $Gini(D)$ 表示集合 $D$ 的不确定性，基尼指数 $Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$ ，其中 $D = D_1+D_2$ 。基尼指数越大，样本集合的不确定性也就越大，这一点和熵相似。

如下图，横坐标表示概率 $p$ ，纵坐标表示损失。

CART 生成算法：

输入：训练集 $D$ ，终止条件
输出：CART 决策树
根据训练集，从根节点开始，递归地对每个结点进行下面的操作，构建二叉决策树：

（1）设结点的训练数据集为 $D$ ，计算现有特征对该数据集的基尼指数。此时，对每一个特征 $A$ ，对其可能取的每个值 $a$ ，根据样本点对 $A = a$ 的测试为“是”或“否”将 $D$ 分割成 $D_1$ 和 $D_2$ 两部分，利用 $Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$ 计算 $A = a$ 时的基尼指数。

（2）在所有可能的特征 $A$ 以及他们所有可能的切分点 $a$ 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子节点，将训练集依特征分配到两个子节点中去。

（3）对两个子节点递归地调用（1），（2），直到满足停止条件

（4）生成CART树

同样，CART算法也需要剪枝，来形成一个子树序列，也就是来添加一个 $\alpha|T|$ 的惩罚变量到损失函数当中。

CART 剪枝算法：

输入：CART 算法生成的决策树 $T_0$
输出：最优决策树 $T_\alpha$

（1）设 $k=0, T = T_0$

（2）设 $\alpha = +\infty$

（3）自下而上地对各内部节点 $t$ 计算 $C(T_t)$ ， $T_t$ 以及
$g(t) = \frac{C(t) - C(T_t)}{|T_t|-1}$
$\alpha = \min(\alpha,g(t))$
这里， $T_t$ 表示以 $t$ 为根节点的子树， $C(T_t)$ 是对训练数据的预测误差， $|T_t|$ 是 $T_t$ 的叶节点个数。

（4）对 $g(t) = \alpha$ 的内部节点 $t$ 进行剪枝，并对叶节点 $t$ 以多数表决法决定其类，得到数 $T$ 。

（5）设 $k = k+1$ ， $\alpha_k = \alpha$ ， $T_k = T$

（6）如果 $T_k$ 不是由根节点及两个叶节点构成的树，则回到步骤（2）；否则令 $T_k = T_n$ 。

（7）采用交叉验证法在子树序列 $T_0,T_1,\cdots,T_n$ 中选取最优子树 $T_\alpha$

Python、R实现

决策树相关面经和其他资料

小结

分类决策树模型是基于特征对实例进行分类的树形结构。其既可以看作 if-then 的集合，也可看作是定义在特征空间划分上的类的条件概率分布。

决策树学习算法包括：

特征选择（信息增益（比））
树的生成和剪枝

常用算法有：

ID3
C4.5
CART

决策树的生成通常使用信息增益（比）最大或者基尼指数最小作为特征选择的准则。从根节点爱是递归产生决策树，相当于用信息增益来不断选取局部最优的特征，将训练集分割成能正确分类的子集。