统计学习方法笔记之决策树

作者: Aengus_Sun | 来源:发表于2019-08-04 17:05 被阅读0次

统计学习方法笔记之决策树
Decision Tree 决策树
决策树(decisionTree)
【决策树】统计学习方法笔记
决策树
决策树算法总结
决策树（一）
统计学习方法笔记(第四章个人笔记)
面试题目总结
数据挖掘干货总结（九）-- 决策树分类

更多文章可以访问我的博客Aengus | Blog

决策树的概念比较简单，可以将决策树看做一个if-then集合：如果“条件1”，那么...。决策树学习的损失函数通常是正则化后极大似然函数，学习的算法通常是一个递归的选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。可以看出，决策树算法一般包含特征选择，决策树的生成与决策树的剪枝过程。

特征选择

信息增益

熵和条件熵

在了解信息增益之前需先给出熵和条件熵的定义。

熵代表随机变量不确定性的度量，设在一个有限个值的离散随机变量，其概率分布为
$P(X=x_i) = p_i, i=1,2,\cdots,n$
则随便变量 $X$ 的熵定义为
$H(X) = - \sum^n_{i=1}p_i \log p_i$
如果 $p_i=0$ ，则定义 $0\log 0=0$ ；对数一般取以2为底或者以 $e$ 为底，这时候熵的单位分别称作比特（bit）和纳特（nat）。由定义可知，熵只依赖于 $X$ 的分布，而和 $X$ 的取值无关，因此也可以将 $X$ 的熵记作 $H(p)$ ，即：
$H(p) = - \sum^n_{i=1}p_i \log p_i$
熵越大，随机变量的不确定性就越大，根据定义可以得到：
$0 \leq H(p) \leq \log n$
条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下，随机变量 $Y$ 的不确定性。随机变量 $X$ 给定的条件下随机变量 $Y$ 的条件熵 $H(Y|X)$ ，定义为 $X$ 给定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望：
$H(Y|X) = \sum^n_{i=1}p_iH(Y|X=x_i)$
其中， $p_i=P(X=x_i), i=1,2, \cdots, n$ 。

当熵和条件熵中的概率由数据估计（尤其是极大似然估计）得到时，所对应的熵和条件熵分别称为经验熵和经验条件熵。

定义

信息增益表示得知特征 $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)$ 之差称作互信息。

根据信息增益选择特征的方法是选择信息增益最大的特征。

信息增益算法

对于给定的训练集 $D$ 和特征 $A$ ，计算特征 $A$ 对于训练集 $D$ 的信息增益 $g(D,A)$ 一般有以下步骤：

（1）计算数据集 $D$ 的经验熵 $H(D)$ ：
$H(D) = - \sum^K_{k=1} \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}$
（2）计算特征 $A$ 对数据集 $D$ 的经验条件熵 $H(D|A)$ ：
$H(D|A)=\sum^n_{i=1}\frac{|D_i|}{|D|}H(D_i)=- \sum^n_{i=1}\frac{|D_i|}{|D|}\sum^K_{k=1}\frac{|D_{ik}|}{|D_i|} \log_2 \frac{|D_{ik}|}{|D_i|}$
（3）计算信息增益
$g(D,A)=H(D)-H(D|A)$

信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比可以校正这一问题。

定义

对于给定的训练集 $D$ 和特征 $A$ ，特征 $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^n_{i=1} \frac{|D_i|}{|D|} \log_2\frac{|D_i|}{|D|}$ ， $n$ 是特征 $A$ 取值的个数。

决策树的生成

ID3算法

ID3算法的核心是在决策树各个结点上应用信息增益选择特征，递归的构建决策树。ID3相当于用极大似然法进行概率模型的选择。

假设输入训练数据集 $D$ ，特征集 $A$ 和阈值 $\varepsilon$ ，按照以下步骤求得决策树 $T$ ：

（1）如果 $D$ 中所有实例属于同一类 $C_k$ ，则 $T$ 为单结点树，并将类 $C_k$ 作为该结点的类标记，返回 $T$ ；

（2）若 $A=\varnothing$ ，则 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；

（3）否则，按照信息增益的算法计算 $A$ 中各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A_g$ ；

（4）如果 $A_g$ 的信息增益小于阈值 $\varepsilon$ ，则置 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类作为该结点的类标记，返回 $T$ ；

（5）否则，对 $A_g$ 的每一个可能值 $a_i$ ，依 $A_g=a_i$ 将 $D$ 分割为若干非空子集 $D_i$ ，将 $D_i$ 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 $T$ ，返回 $T$ ；

（6）对第 $i$ 个子结点，以 $D_i$ 为训练集，以 $A-\{A_g \}$ 为特征集，递归地调用（1）~（5）步，得到子树 $T_i$ 并返回；

C4.5算法

C4.5算法和ID3算法类似，不过是用信息增益比替换掉了信息增益；

假设输入训练数据集 $D$ ，特征集 $A$ 和阈值 $\varepsilon$ ，按照以下步骤求得决策树 $T$ ：

（1）如果 $D$ 中所有实例属于同一类 $C_k$ ，则 $T$ 为单结点树，并将类 $C_k$ 作为该结点的类标记，返回 $T$ ；

（2）若 $A=\varnothing$ ，则 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；

（3）否则，按照信息增益比的算法计算 $A$ 中各特征对 $D$ 的信息增益比，选择信息增益比最大的特征 $A_g$ ；

（4）如果 $A_g$ 的信息增益比小于阈值 $\varepsilon$ ，则置 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类作为该结点的类标记，返回 $T$ ；

（6）对第 $i$ 个子结点，以 $D_i$ 为训练集，以 $A-\{A_g \}$ 为特征集，递归地调用（1）~（5）步，得到子树 $T_i$ 并返回；

可以看到两个算法除了加粗的部分，其他部分都一样。

决策树的剪枝

决策树生成算法递归的产生决策树直到不能继续下去为止，这样的树往往对训练数据分类比较准确，但是对未知的测试数据往往没那么精准，即出现过拟合现象。对于这种情况可以将决策树进行简化，也被称为决策树的剪枝。

决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树 $T$ 的叶结点个数为 $|T|$ ， $t$ 是树 $T$ 的叶结点，该叶结点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk}$ 个， $k=1, 2, \cdots, K$ ， $H_t(T)$ 为叶结点 $t$ 上的经验熵， $\alpha \geq0$ 为参数，则决策树学习的损失函数可以定义为：
$C_\alpha (T) = \sum^{|T|}_{t=1}N_t H_t(T)+\alpha |T|$
其中经验熵为：
$H_t(T) = -\sum_k \frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t}$
在损失函数中，将损失函数右端的第一项记作
$C(T) = \sum^{|T|}_{t=1}N_t H_t(T) = -\sum^{|T|}_{t=1} \sum^K_{k=1}N_{tk} \log \frac{N_{tk}}{N_t}$
这时有
$C_\alpha(T) = C(T)+\alpha|T|$
剪枝就意味着当 $\alpha$ 确定时，选择损失函数最小的模型，即损失函数最小的子树（ $\alpha$ 较大时促使选择比较简单的模型，较小时促进选择复杂的模型）。

剪枝算法

输入生成的决策树 $T$ 以及参数 $\alpha$ ，输出剪枝后的子树 $T_\alpha$ ：

（1）计算每个结点的经验熵；

（2）递归地从树的叶结点向上回缩，设一组叶结点回缩到其父结点之前与之后的整体树分别为 $T_B$ 与 $T_A$ ，其对应的损失函数值分别是 $C_\alpha(T_B)$ 与 $C_\alpha(T_A)$ ，如果
$C_\alpha(T_A) \leq C_\alpha(T_B)$
则进行剪枝，即将父结点变为新的叶结点；

（3）重复步骤（2），直至不能继续为止，得到损失函数最小的子树 $T_\alpha$ ；

CART算法

分类与回归树（classification and regression tree, CART）模型是应用广泛的决策树学习方法，CART同样由特征选择、树的生成以及剪枝组成，既可以用于分类也可以用于回归。

CART是在给定输入随机变量 $X$ 的条件下输出随机变量 $Y$ 的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值是“是”或“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。CART算法由以下两步组成：

（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；

（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准；

CART生成

对于回归树用平方误差最小化准则，对分类树用基尼指数最小化准则进行特征选择，生成二叉树。

回归树的生成

一颗回归树对应着输入空间的一个划分以及在划分单元上的输出值。假设将输入空间划分为 $M$ 个单元 $R_1,R_2,\cdots,R_M$ ，并且在每个单元 $R_m$ 上有一个固定的输出值 $c_m$ ，于是回归树模型可表示为：
$f(x) = \sum^M_{m=1}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 = ave(y_i|x_i \in R_m)$
问题是怎样对输入空间进行划分，也就是如何选择划分结点：

假设输入训练集 $D$ ，在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。具体步骤为：

（1）选择第 $j$ 个变量 $x^{(j)}$ 和它取的值 $s$ 作为划分变量和划分点，并定义两个区域：
$R_1(j,s) = \{ x|x^{(j)} \leq s \},R_2(j,s)=\{ x|x > s \}$
然后寻找最优划分变量 $j$ 和最优划分点 $s$ ，具体的，求解：
$\min_{j,s} \left[ \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 \right]$
遍历变量 $j$ ，对固定的划分变量 $j$ 扫描切分点 $s$ ，选择式上式达到最小值的 $(j,s)$ ；

（2）用选定的 $(j,s)$ 划分区域 $R_1,R_2$ 并决定相应的输出值：
$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）继续对 $R_1,R_2$ 两个子区域调用步骤（1），（2），直到满足停止条件；

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

分类树的生成

基尼指数：在分类问题中，假设有 $k$ 个类，样本点属于第 $k$ 类的概率是 $p_k$ ，则概率分布的基尼指数定义为：
$Gini(p) = \sum^K_{k=1}p_k(1-p_k) = 1 - \sum^K_{k=1}p_k^2$
对于二分类问题，若样本点属于第一个分类的概率为 $p$ ，则概率分布的基尼指数为：
$Gini(p) = 2p(1-p)$
对于给定的样本集合 $D$ ，其基尼指数为：
$Gini(D) = 1-\sum^K_{k=1}(\frac{|C_k|}{|D|})^2$
这里， $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集， $K$ 是类的个数。

如果样本集合 $D$ 根据特征 $A$ 是否取值 $\alpha$ 被分割成 $D_1$ 和 $D_2$ 两部分，即：
$D_1 = \{ (x,y) \in D|A(x)=\alpha \},D_2 = D - D_1$
那么在特征 $A$ 的条件下，集合 $D$ 的基尼指数定义为：
$Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$
基尼指数 $Gini(D)$ 代表集合 $D$ 的不确定性，基尼指数 $Gini(D,A)$ 表示经 $A=\alpha$ 分割后集合 $D$ 的不确定性。基尼指数越大代表不确定性程度越大。

假设输入训练数据集 $D$ 以及停止计算的条件，根据训练集，从根结点开始，递归地对每个结点进行以下操作，构建决策树：

（1）计算现有特征对训练数据集的基尼指数。此时，对每一个特征 $A$ ，对其可能取的每个值 $\alpha$ ，根据样本点对 $A=\alpha$ 的测试为“是”或“否”，将 $D$ 分为 $D_1$ 和 $D_2$ 两部分，利用上式计算 $A=\alpha$ 的基尼指数；

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

（3）对两个子结点递归调用（1）和（2）步骤，直至满足停止条件；

（4）生成CART决策树；

算法停止的条件是结点中样本个数小于预定阈值或者样本的基尼指数小于预定阈值（此时此结点上的样本基本属于同一类），或者没有更多特征。

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$ 的叶结点个数；