学习笔记-决策树

2020-03-09 本文已影响0人 Pluto_wl

决策树是一种基本的分类与回归方法。从名字上看，决策树是一种树形结构，包括结点和边。结点分为内部结点和叶结点，内部结点表示属性或特征，叶结点表示结果。边表示属性或特征的取值。
比如使用房子大小预测房价，房子大小就是内部结点，房子价格就是叶结点，边就是房子大小的具体取值。
决策树还对应于特征空间的划分，每次从一个结点分出多个结点时，就意味着将特征空间划分的更小。如下图所示：先根据 $x_1$ 与 $\theta _1$ 的大小将特征划分为两部分，即大于 $\theta _1$ 和小于等于 $\theta _1$ ，以此类推，将整个特征空间进行划分。

图片来自于网络

特征选择方法

决策树的构建过程是基于选择特征，选择好的特征便能构建出好的决策树。
好的特征。通常决策树使用以下三种方式作为特征选择的准则。
先来介绍熵与条件熵的概念：

熵：是表示随机变量不确定性的度量。 $H(X)=\sum^n_{i=1} p_i()logp_i$ ,熵越大，随机变量X的不确定性越大。当 $p_i=0$ 或 $p_i=1$ 时，熵最小，当 $p_i=0.5$ 时，熵最大。因为概率为0或1时，随机变量是确定的，所以不确定性为0，概率为0.5时，随机变量没有任何偏向，所以最不确定，熵也就最大。
条件熵：随机变量X在给定特征A的情况下的熵。 $H(X|A)=\sum^n_{i=1}p_iH(A=a_i)$ , $a_i$ 表示特征A的取值情况

决策树选取特征时希望选取使不确定下降最大的特征。

信息增益（互信息）
信息增益表示特征A对数据集D不确定性减少的程度
$g(D, A)=H(D)-H(D|A)$
假设特征A将数据集分为n个不同的取值 $a_i$ ，根据不同取值可以将数据集分为n个子集，每个子集上A的取值为 $a_i$ ,所有 $a_i$ 构成的子集记作 $D_i$
$g(D,A)=H(D)-\sum^n_{i=1} \frac{D_i}{D}H(D_i)$
信息增益比
信息增益的缺点是会对数值取值较多的特征有偏好，信息增益比的目的就使为了减轻这种偏好。
信息增益比公式如下：
$g_R=\frac{g(D|A)}{H_A(D)}$
$g(D|A)$ 为特征A对数据集D的信息增益， $H_A(D)$ 为在特征A的信息熵
$H_A(D)=-\sum^n_{i=1} \frac{D_i}{D}H(D_i)$ n使A取值的个数。通常A的个数越多，熵就越大。
基尼指数
基尼指数与熵的含义类似，都可以表示不确定性。
在分类问题中，假设有K个类，样本点属于第k个类的概率为 $p_k$ ,则概率分布的基尼指数定义为 $Gini(p)=\sum^K_{k=0} p_k(1-p_k)=1-\sum^K_{k=0}p_k ^2$ .
我们从上述公式中看到，当类别个数少的时候，基尼指数也就越大；当类别个数多的时候，基尼指数就越小。说明类别少的时候基尼指数大，但确定性高；类别多的时候基尼指数小，但确定性小。
如果数据集D根据特征A是否取值为a被划分为 $D_1$ 和 $D_2$ 两部分，则在特征A的条件下，集合D的基尼指数定义为
$Gini(D,A) = \frac{|D1 |}{|D|}Gini(D_1) + \frac{|D2 |}{|D |} Gini(D2)$
基尼指数Gini(D,A)表示根据特征A的划分后的不确定性。Gini(D,A)越低，表示不确定性越小，A的特征划分效果约明显。

生成算法

整体流程如下：
采用自顶向下的递归过程

计算每个特征下的信息增益（信息增益比，基尼指数）。
选取最优特征建树
达到停止条件即return

停止条件

当前结点内所有样本属于同于类别
当前结点内特征为空或所有样本特征取值相同
当前结点内没有样本

ID3
ID3算法使用信息增益作为特征选择的依据。将所有特征的信息增益计算出来，选择出信息增益最大的特征作为当前结点分类依据。

图片来自网络
C4.5
C4.5算法使用信息增益比作为特征选择的依据。计算过程和ID3类似。
cart
cart分类中使用基尼指数作为特征选择的依据。将所有特征下的基尼指数计算出来，选择使基尼指数最小的特征作为分类依据。
需要注意的是，cart是一个二叉树。

决策树剪枝

我们先来看结点个数与分类准确率之间的关系

图片来自于网络

从图中看到，并不是结点越多，准确率越高。那么通过剪枝的方式降低决策树的复杂度是必要的。
决策树剪枝分为预剪枝和后剪枝。预剪枝是在建树过程中对树进行剪枝，提前结束树的建立。后剪枝是建树后使用验证集对树进行剪枝。

预剪枝

树的深度
信息增益小于一定值
性能在划分后没有提升或提升不大
结点下的个数小于一定值

后剪枝
第一步：删除以此结点为根结点的叶结点
第二步：将此根结点作为叶结点
第三步：如果验证集准确率变高，那么真正删除此结点的叶结点，否则保留此结点的叶结点

处理连续值问题

对于特征是连续值的特征，如何划分特征呢？
通常采用的是方差，循环选取结点作为阈值，计算划分后小于阈值的方差a和大于等于阈值的方差b，选择使a+b的值最小的阈值作为划分点。具体过程请看《统计学习方法》第二版的80页。

在分类问题中，选择完划分点后需要计算信息增益，进而选择特征
在回归问题中，需要循环每个特征计算方差，选择使数据集D方差最小的特征。具体过程请看下一节。
连续特征与离散特征不同，离散值特征在作为划分依据后，就不能参与后面的划分，但连续值是需要的。

处理回归问题

cart决策树可以处理回归问题，回归树用平方误差最小化准则进行特征选择，生成二叉树。
假设X与Y分别为输入和输出向量，并且Y使连续变量，给定数据集 $D=\{ (x_1,y_1),(x_2,y_2),...,(x_n,y_n) \}$ 。在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。

假设已经将输入空间X划分为M个单元 $R_1$ , $R_2$ ,..., $R_M$ ,并且每个单元 $R_m$ 上都有一个给固定输出值 $c_m$ 。 $c_m$ 等于 $R_m$ 上 $y$ 的均值。回归树的模型如下：
$f(x)=\sum^M_{m=1} c_m I(x\in R_m)$
$c_m$ 为特征单元 $R_m$ 在训练数据上的均值， $I(x\in R_m)$ 是指示函数，当x在单元 $R_m$ 中树,指示函数的值为1，否则为0。

当输入空间划分确定时，使用平方误差 $\sum_{x_i \in Rm } (y_i-c_m) ^2$ 来表示训练误差。

选择最佳切分变量j和切分点s
假设s将切分为两个区域：
$R_1(j,s)=\{x|x^{(j)}<=s \}$ 和 $R_2(j,s)=\{x|x^{(j)}>s \}$
循环遍历每个特征，寻找最优切分变量j和最优切分点s
$min_{j,s}[min_{c_1} \sum_{x_i \in R_1}(y_i -c_1) ^2 + min_{c_2}\sum_{x_i \in R_2}(y_i -c_2) ^2 ]$
固定输入变量j，可以找到最优切分点s。可以求出切分点左右两端的 $c_1$ 和 $c_2$
都每个区域重复上述划分过程，直到满足停止条件为止，生成一个回归树。这样的树称为最小二乘回归树。