决策树

作者: 单调不减 | 来源:发表于2019-06-16 22:30 被阅读0次

机器学习6-决策树
决策树
决策树
决策树算法总结
机器学习 - 决策树算法[一]
机器学习系列（三十六）——回归决策树与决策树总结
[机器学习]决策树
经典机器学习系列之【决策树详解】
第5章决策树
决策树与随机森林

决策树在看西瓜书的时候已记录过，此次看《统计学习方法》的决策树部分，除了当作复习，也有若干新的思考。因此本篇可视为https://www.jianshu.com/p/8b56ea5a1607
的一个补充。

1、决策树与条件概率分布

决策树除了可以看作一个 $if-then$ 规则的集合以外，还可以表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上，将特征空间划分为互不相交的单元或区域，并在每个单元或区域定义一个类的概率分布就构成了一个条件概率分布。

假设 $X$ 为表示特征的随机变量， $Y$ 为表示类的随机变量，则这个条件概率分布可表示为 $P(Y|X)$ 。 $X$ 取值于给定划分下单元的集合， $Y$ 取值于类的集合。各叶结点上的条件概率往往偏向于某个类，即属于某个类的概率较大，决策树分类将该结点的实例强行分到条件概率大的那一类去。

2、决策树学习

决策树本质上是从训练数据集中归纳出一组分类规则。与训练数据集不矛盾的决策树可能有多个也可能一个都没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。另一个角度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应不仅对训练数据很好的拟合，而且对未知数据有很好的预测。

从所有可能的决策树中选择最优的决策树是NP-Hard的，因此现实中通常采用启发式算法。这样得到的决策树是次最优的（sub-optimal）的。

决策树学习算法通常递归地选择最优特征，并根据该特征对训练数据集进行分割，这一过程对应特征空间的划分与决策树的构建。生成决策树后为了解决过拟合问题通常要由下向上进行决策树剪枝。

可以看到，决策树学习算法包含特征选择、决策树生成与决策树剪枝过程。决策树的生成只考虑局部最优，决策树剪枝则考虑全局最优。

3、信息增益

这部分《统计学习方法》比西瓜书讲得要细致。信息增益是信息论的内容，这里也只是较为浅显的理解。但对于决策树而言这样的理解已经足够了。

熵是随机变量不确定性的度量。设 $X$ 是一个取有限个值的离散随机变量，其概率分布为：

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

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

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

可以看到，熵只依赖于 $X$ 的概率分布而与其具体取值无关。因此也可以将 $X$ 的熵记为 $H(p)$ ：

$H(p)=-\sum_{i=1}^n p_i log(p_i)$

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

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

这里 $p_i=P(X=x_i)\quad i=1,2,\dots,n$ 。

一般的，熵 $H(Y)$ 与条件熵 $H(Y|X)$ 之差称为互信息：

$I(X;Y)=H(Y)-H(Y|X)$

互信息是一个随机变量（X）包含另一个随机变量（Y）的信息量的度量。也可以看作给定X知识下Y的不确定性的缩减量。

决策树学习中的信息增益等价于训练数据集中的类与特征的互信息：

$g(D,A)=H(D)-H(D|A)$

这里 $A$ 表示特征或属性， $D$ 表示训练数据集。 $H(D)$ 表示对数据 $D$ 分类的不确定性， $H(D|A)$ 表示在特征 $A$ 给定条件下对数据集 $D$ 进行分类的不确定性。所以两者之差，即信息增益，表示由于特征 $A$ 使得对数据集 $D$ 分类的不确定性减少的程度。

因此基于信息增益的决策树算法就很自然了，每次选择信息增益最大的结点划分方式直至信息增益小于某个阈值或结点中样本类别相同为止。

采用信息增益作为划分结点的指标有一个问题——算法会偏向于选择取值较多的特征。为解决这个问题，我们可以采用信息增益比：

$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$

其中 $H_A(D)$ 是训练数据集 $D$ 关于特征 $A$ 的熵。显然 $A$ 的取值越多，其不确定性倾向于越大，从而熵倾向于越大，这样就相当于在信息增益基础上增加了一个关于特征取值多少的罚项。

4、决策树生成——ID3&C4.5&CART

ID3算法：

输入：训练数据集 $D$ ，特征集 $A$ ，阈值 $\epsilon$

（1）若D中所有实例属于同一类 $C_k$ ，择 $T$ 为单节点树，将类 $C_k$ 作为该结点类标记，返回 $T$ 。

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

（3）否则计算各特征对D的信息增益，选择信息增益最大的特征 $A_g$ 。

（4）如果 $A_g$ 的信息增益小于阈值 $\epsilon$ ，则置 $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$ ，返回 $T_i$ 。

C4.5算法：

C4.5算法和ID3算法唯一的差异就是把结点划分准则由信息增益改进为信息增益比。

CART(Classification And Regression Tree，分类与回归树)算法：

CART假设决策树是二叉树，内部结点取值特征为“是”和“否”，左分支是取值为“是”的分支，右分支为取值为“否”的分支。

在特征选择方面，对于回归树，采用平方误差最小准则，对分类树采用基尼系数最小化准则。

（a）最小二乘回归树：

（1）选择最优切分变量 $j$ 和切分点 $s$ ，求解：

$\min_{j,s}[\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]$

这里 $R_1(j,s)=\{x|x^{(j)}\leq s\}$ 和 $R_2(j,s)=\{x|x^{(j)} > s \}$ 表示由切分变量 $x^{(j)}$ 和切分点 $s$ 产生的两个划分区域， $c_1=ave(y_i|x_i\in R_1(j,s))$ 和 $c_2=ave(y_i|x_i\in R_2(j,s))$ 则表示在 $R_1$ 和 $R_2$ 区域上的样本输出值的均值。

也就是说，遍历 $j$ ，对固定的 $j$ ，扫描切分点 $s$ ，找到使得上式最小的 $(j,s)$ 。

（2）用选定的 $(j,s)$ 划分区域并决定相应的输出值：

$R_1(j,s)=\{x|x^{(j)}\leq s\} \quad 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,\quad x\in R_m,\quad m=1,2$

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

（b）分类树CART算法：

（1）设结点的训练数据集为 $D$ ，计算现有特征对该数据集的基尼系数，此时对每一个特征及其可能取的每个取值 $a$ ，根据样本点对 $A=a$ 的测试为是或否将 $D$ 分割成 $D_1$ 和 $D_2$ 两个部分，利用下式计算 $A=a$ 时的基尼系数：

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

$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$

基尼系数 $Gini(D)$ 表示集合 $D$ 的不确定性， $Gini(D,A)$ 表示经过 $A=a$ 分割后集合 $D$ 的不确定性。基尼指数越大不确定性越大。

（2）在所有可能特征 $A$ 以及它们所有可能的切分点 $a$ 中选择基尼指数最小的特征及对应切分点作为最优特征与最优切分点，将此结点分成两个子结点。

（3）对两个子结点递归地调用（1）（2）直至满足停止条件（结点中样本个数小于阈值或基尼系数小于阈值或没有更多特征）。

5、决策树剪枝

决策树剪枝往往通过极小化决策树整体的损失函数来实现，设树 $T$ 的叶结点个数为 $|T|$ ， $t$ 是树 $T$ 的叶结点，改叶结点有 $N_t$ 个样本点，其中第 $k$ 类样本点有 $N_{tk}$ 个， $k=1,2,\dots,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_t H_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|$ 表示模型复杂度，在这里作为正则项来防止模型过拟合。

树的剪枝算法：

（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剪枝：

CART剪枝算法由两步组成：

从生成的决策树 $T_0$ 底端开始不断剪枝，直到 $T_0$ 的根结点，形成一个子树序列 $\{T_0,T_1,\dots,T_n \}$ 。
通过交叉验证法在独立的验证集上对子树序列进行测试，从中选出最优子树。

如何形成子树序列呢？Breiman等人证明：可以用递归的方式对数进行剪枝，将 $\alpha$ 从小增大，产生一系列的区间 $[\alpha_i,\alpha_{i=1}),i=1,2,\dots,n$ ；剪枝得到的子树序列对应着各区间的最优子树序列。

这个结论其实不难理解，当我们缓慢增加 $\alpha$ 的时候，可能得到的最优子树并不会发生变化，也就是说当 $\alpha$ 在某个区间内取值时，我们得到的最优子树都是相同的，而当 $\alpha$ 超过某个阈值，则剪枝后得到的子树更优，此时最优子树才发生改变。于是很自然的思路就是找到这些区间的端点来进行分析。

具体地，从整体树 $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)<C_\alpha(t)$

当 $\alpha$ 增大时，在某一 $\alpha$ 有：

$C_\alpha(T_t)=C_\alpha(t)$

此时解出的 $\alpha$ 为：

$\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$

为此，对 $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)$ 的最优子树。

总结下来算法流程如下：

（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))$

（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,\dots,T_n$ 中选取最优子树 $T_\alpha$ 。

机器学习6-决策树
一. 决策树概述 1.1 什么是决策树决策树输入: 测试集决策树输出: 分类规则(决策树) 1.2 决策树算法概...
决策树
1、决策树决策树学习通常包括3个步骤：特征选择。决策树生成。决策树剪枝。决策树的学习目标是：根据给定的训...
决策树
决策树决策树模型与学习特征选择决策树的生成决策树的剪枝 CART 算法决策树模型呈树形结构，在分类问题中...
决策树算法总结
目录一、决策树算法思想二、决策树学习本质三、总结一、决策树（decision tree）算法思想：决策树...
机器学习 - 决策树算法[一]
1 决策树模型与学习 1.1 决策树模型决策树定义：分类决策树模型是一种描述对实例进行分类的树形结构。决策树由...
机器学习系列（三十六）——回归决策树与决策树总结
本篇主要内容：回归决策树原理、回归树学习曲线、决策树总结回归决策树原理回归决策树树是用于回归的决策树模型，回归...
[机器学习]决策树
决策树 @(技术博客)[机器学习, 决策树, python] 学习决策树首先要搞清楚决策树是什么（what），在弄...
经典机器学习系列之【决策树详解】
这节我们来讲说一下决策树。介绍一下决策树的基础知识、决策树的基本算法、决策树中的问题以及决策树的理解和解释。 ...
第5章决策树
内容一、决策树内容简介二、决策树的模型与学习三、特征选择四、决策树生成五、决策树剪枝六、CART算法 ...
决策树与随机森林
PART I 决策树 (Decision Tree) 决策树基本知识决策树何时停止生长：(I) all leaf...