机器学习笔记-决策树

Pijriler

发布时间 2023.08.29阅读数 1101 评论数 0

前言
本章的决策树旨在了解最基础的决策树知识以及常见的几个决策树算法，至于更近阶的集成学习则不加以介绍。

1、决策树思想
决策树是机器学习一个非常重要的分支，作为最重要的机器学习算法之一，掌握决策树成为学习机器学习的重要目标。
首先需要明确的是，决策树可以解决回归和分类问题，但是这里主要讨论的是分类问题。决策树的学习的基本形式是一种树型结构，和svm、感知机这类的机器学习算法不同，决策树不能学习出来具体的表达式，但能学习出一系列if-then规则。所以我们也认为决策树是定义在特征空间与类空间上的条件概率分布。并且决策树的主要优点有可读性强，分类速度快。而一般的决策树学习过程主要分为三步：特征选择、决策树的生成、决策树的剪枝。下面我们就一般决策树的三种步骤进行详细的介绍。

2、特征选择
要想生成一棵决策树，第一步就是特征选择，那么什么是特征选择呢？
假设给定的训练数据集为：

征，我们在进行生成决策树时，总要选择先从那个特征进行分类，后从那个特征进行分类，这就叫特征选择，我们首先应该选择最具有分类能力的特征作为我们的特征，因为这样能提高学习的效率。到底怎么看出哪个特征是最具分类能力的呢？
这就需要引入一个评判标准叫做信息增益和信息增益比，而信息增益是建立在什么是信息的基础上的，于是又需要引入一个能反映信息多少的概念：熵。
熵表示随机变量不确定性的度量。设X是一个取有限个值得离散随机变量，其概率分布为：

在上述式子中，如果pi等于0，那么定义H(X)也等于0，说明熵的值为0，不携带任何信息，且log一般取值为log2。假设随机变量只取两个值时，例如抛硬币问题，结果只会出现正面和反面，则此时X的分布为：P(X=正面)=p,P(X=反面)=1−p,0≤p≤1
此时的熵为

H(p)=−plog2p−(1−p)log2(1−p)

而条件熵H(Y∣X)表示在已知随机变量X的条件下随机变量Y的不确定性。且有：

信息增益的含义就是得知特征X的信息而使得类Y的信息的不确定性减少的程度。计算方式如下：

g(D,A)=H(D)−H(D∣A)

一般的，熵H(Y)与条件熵H(Y∣X)之差称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
在使信息增益选择特征时，信息增益大的特征往往具有更强的分类能力，于是就有了决策树采用比较特征的信息增益来选择的特征的方法。下面给出一个样本集特征的信息增益的计算方式。

的计算方法如下：
（1）先计算数据集D的经验熵H(D)

（3）计算信息增益
g(D,A)=H(D)−H(D∣A)
这就得到了信息增益的计算方法。
除了信息增益以外，我们还可以用信息增益比来作为选择特征的标准，信息增益比的计算方式如下：

大的情况。
另外还有一种选择特征的标准是基尼指数，基尼指数的定义为：

所以对于一个给定的数据集D，其基尼指数为：

则在特征A的条件下，集合D的基尼指数定义为

而基尼指数和信息增益与信息增益相比，基尼指数没有对数计算，在信息增益特征选择中，我们选择信息增益大的特征作为分类特征，而基尼指数则选择数值较小的特征作为分类特征。

3 常见的几种决策树生成算法
3.1、ID3算法
ID3算法是采用信息增益作为选择标准的生成算法，对于给定的训练数据集，我们可以通过ID3算法生成一棵决策树。
输入：训练数据集D,特征集A阈值ε
输出：决策树T

这里的决策树算法是通用的算法步骤，在后面的其它决策树算法种类中也可以看见这些步骤，我们只需要记住一个决策树是如何产生的即可。在决策树的生成算法中，前几步介绍的都是特例情况，例如在步骤1中，当数据集中所有的y值均为一个类别时，这时树就是单结点，这个结点返回的就是单个类别的值；在2中，若A AA中无特征，此时只剩下预测值标签一列，返回的树也是单结点树，并且此结点的类标记就是标签值y中类别数最多的类；在3中，排除1、2的特殊情况（存在特征、标签不是单单一种），此时是学习一个棵决策树的开始，而在训练一棵决策树我们知道可以分为三步：选择特征、决策树的生成、决策树的剪枝，此时就是选择特征阶段，而在ID3算法中，选择特征所用的标准为信息增益；在4中，假设我们找到了最大的信息增益特征，但是此时特征的信息增益实在是过小，则算法不会再使用此特征进行分类，直接返回当前树，而当前树的当前结点，则是归为当前结点中实例数最大的类（其实这一步相当于在学习决策树中的跳出循环步骤）；在5中，如果4的条件不满足，从3直接跳转到5，进行决策树的分支，这也是学习决策树的最主要的步骤；在6中，这也是不断学习决策树的步骤保证；

3.2、C4.5算法
C4.5算法和ID3算法从学习步骤上是没有太大差别的，我们可以理解C4.5算法为ID3算法的改进，在ID3算法中用到的是信息增益作为选择新特征的标准，而C4.5算法中使用的是信息增益比作为选择新特征的标准，这可以算是一种改进，而其它所有的算法步骤和ID3中步骤一样。

3.3、CART算法
在CART算法中，需要学习的知识又和前面不一样了，C4.5和ID3是最简单的决策树算法，这两种算法应用于分类树的比较多，但是CART算法是可以完全适应回归树的。
CART的全称就是：classification and regression tree 含义就是分类与回归树，说明CART在处理分类问题和回归问题时均有办法。
在学习CART决策树之前，我们需要知道CART决策树的几个特点，首先CART决策树是一个完全二叉树，内部结点特征的取值为连续值或者离散值中的“是”或“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间划分为有限个单元。当我们面临特征为多类别时，即特征A存在类别输入A1、A2、A3时，不能使用CART算法将特征A AA一次性分完，只能找到最优的组合例如A1、A2和A3这种组合形式来进行二分，而后续再对A1、A2进行二分，总之CART的树为完全二叉树。
先看比较熟悉的处理分类问题，CART在处理分类问题时和C4.5与ID3唯一的不同点就是选择新特征的标准不一样，CART使用的是基尼指数，在前面介绍特征选择时我们详细介绍了基尼指数，基尼指数和信息熵、信息增益比类似，都能作为决策树选择特征时的标准，当决策树选择使用基尼指数作为标准时，可以不需要进行对数运算，其它的几乎没什么改变，而且在很多实验中表明，其实选择基尼指数和信息增益比学习的树模型带来的误差不大。算法步骤在ID3那一节中已经介绍过了。
CART最主要的还是回归部分，这一部分是ID3和C4.5没有的。下面就来详细介绍CART的回归部分。首先我们要知道，在分类算法中，决策树用来选择特征方法是基于各个特征的基尼指数的大小，基尼指数小的特征说明样本集合不确定性小，也即分类效果好。但是在回归树中，由于预测值是连续的数值，此时不能再使用基尼指数、信息增益比、信息增益来作为选择特征的标准了。此时我们使用的标准就是平方误差最小。
假设X与Y分别未输入和输出变量，并且Y是连续变量，给定训练数据集

下面考虑如何生成一个回归树。
一棵回归树对应着一个输入空间的一个划分以及划分的单元上的输出值。假设输入空间已经被划分为

然后寻找最优的切分变量j和最优的切分点s，具体的有：

对固定输入变量j可以找到最优切分点s。

变量所有的变量，找到最优的切分变量j和最优的切分点s，构成一对(j,s)。以此将输入空间划分为两个区域，接着，对每个区域重复上述步骤，直到算法满足条件停止。我们将着整个流程称为最小二乘回归。
下面是生成最小二乘回归树的步骤：
输入：训练数据集D；
输出：回归树f(x)。

2.用选定的对(j,s)划分区域并决定相应的输出值：
3.继续对两个子区域调用步骤1、2，直到满足条件为止。

这里算法步骤是引用李航老师的《统计学习方法》。其实在了解算法一步步在干什么，编程实现起来就会很简单。上面的步骤要理解需要注意几个点：
1、在找最优的(j,s)时，回归树其实是两次遍历，即找j jj和找s ss。找j jj是找最属性，找s ss是找对应j jj属性下的最优切分点，最后最优的组合(j,s)应该是全局最优的；
2、在找到(j,s)后，CART回归树会把输入空间一分为二，此时划分后的空间会有两个输出值，我们记为c1和c2，求解这两个值的方法就是求所属空间类样本值的平均。再一次二分之后，重复1、2步骤再次二分，这样无限循环下去，还有个重要的点就是这样二分下去，计算的误差是越来越小的，这个误差就是使用c1和c2在所属的空间内计算均方误差，直到最后的误差为0；
3、在进行二分时，我们每一次二分过后产生了一个新的结点，此时仍然需要重新进行遍历找到最优的$(j,s)。
到这里，CART算法的生成我们就介绍完了，后面还有一部分就是CART的剪枝。

4、决策树的剪枝
4.1、ID3和C4.5算法的剪枝
决策树最重要的三大步骤最后一步：剪枝。这一步是保证决策树拥有强泛化能力的保证，在线性模型中存在过拟合情况，决策树是非线性模型，也存在过拟合情况，如果决策树不进行剪枝，那么一棵训练完的决策树很有可能会出现过拟合情况。用一句话来解释决策树的过拟合是：决策树在学习样本点时学习的“太好了”，以至于把一些样本点的特点当作所有样本点的共性而导致过拟合。
先来了解一下决策树的过拟合情况。前面学习了决策树的生成方法，从生成方法中可以看到，一棵决策树在生成过程中是不断迭代生成的，直到不能再生成下去为止，这种情况生成的决策树一般来说都是非常“深”的，这种“深”是基于训练数据学习出来的，在训练集数据中拟合的非常好，但是如果在验证集上进行预测，那么得到的效果就不一定会很好，当在训练集上预测的效果非常好，但是在验证集上的效果非常差时，此时决策树就很有可能存在过拟合现象。解决过拟合的思路也很简单，就是减小决策树的“深度”。一般来说决策树防止过拟合的方法不止剪枝一个，还有一种可靠的方法就是在每次决策树生成新结点的同时，计算此时生成结点后的决策树在验证集上的误差和未生成结点前的决策树在验证集上的误差，将两误差进行比较，如果后者误差大，我们就继续生成新结点，反之则不生成新结点，这种防止过拟合的方法是每一次生成树支时均需要进行一次判断，而且还需要预留一部分数据作为验证集。另一种防止过拟合的方法就是剪枝。前者叫做预剪枝，后者称为后剪枝，预剪枝基于贪心算法来决定是否生成新支点的，这种思想最大的坏处就是容易产生欠拟合。
决策树的剪枝其实思想非常简单，就是对于以生成的一棵完整的决策树，我们从树的最底端往上进行剪枝，剪枝依据的准则由损失函数决定。

其中经验熵：

在损失函数中如果我们记：

这时有：

这时的损失函数被我们变成两个部分，分为C(T)和α∣T∣这两个部分，第一部分表示的含义表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，至于为什么这个公式可以理解为模型的预测误差，我们可以从公式中找到答案，在公式中，T表示叶子结点的个数，叶子结点就是没有子结点的

子结点个数的乘积，反映的就是整个树模型的结构误差。当α的值为0时，说明我们的损失函数只需要考虑预测误差，此时的树应该拟合的越深越好，但是此时树模型的复杂度也就很高。随着α的值在不断变大，模型的复杂度在不断下降，模型的拟合程度也在下降，我们在给定α的情况下，总能找到一个最好的树。此时这个最好的树就是我们需要的生成树，剪枝的过程就是让树模型不仅仅考虑拟合程度，还需要考虑整个树的复杂度。
注意：ID3和C4.5算法的剪枝思路是一样的
决策树剪枝算法步骤简介：
输入：一棵未剪枝的决策树T和参数α

上面的决策树剪枝算法有几个需要注意的点：1、计算每个结点的经验熵，而不是计算叶结点的经验熵，这里计算所有结点的经验熵是因为剪枝前我们不知道需要剪枝到哪一个叶结点，所以需要计算所有的叶结点的经验熵。2、这里的误差进行比较其实就是比较父结点和子结点两个结点之间的损失函数大小。3、这就是不断迭代过程，不断迭代最终找到的树就是最优的树，最优的树对应的损失函数就是最小的，且此时不会出现剪枝情况。

4.2、CART算法的剪枝
前面介绍了CART的生成，这一部分要介绍CART的剪枝，关于CART的剪枝部分，又于ID3和C4.5不一样。
在前面介绍剪枝操作时，我们说剪枝操作就是控制树模型的复杂度和预测精度之间关系，在CART剪枝方法中也是如此，CART剪枝其实还是一个比较复杂的事情，我在第一次学习CATR剪枝时也是搞不明白，下面就一起来看看CART的剪枝。
先提供网上几篇有助于我理解CART剪枝的
博客园-CART剪枝实例
知乎-理解CART剪枝
其它的我就是对着李航老师的《统计学习方法》这本书进行学习。
在学习CART剪枝前，我们回顾一下上文树模型的损失函数的形式：