机器学习之决策树和随机森林

迈不过友情╰ 2022-07-14 13:14 205阅读 0赞

## 一、决策树 ##

决策树学习是[机器学习][Link 1]中一类常用的[算法][Link 2]。在决策树中，根节点包含样本全集。每个非叶子节点表示一种对样本的分割，通常对应一个划分属性，其将样本分散到不同的子节点中。每个叶子节点对应于决策的结果。因此从根节点到每个叶子节点的路径对应了一个判定序列。

可与下图做比对：

![这里写图片描述][20161205130901262]

在上图的决策树中，划分属性有年龄、是否为学生、信用率。

划分属性一般采用样本的某个特征或多个特征的组合。

决策树学习是一种有监督学习，根据样本为基础，自顶向下通过递归的方法来对样本进行划分属性。其基本思想是以 信息熵 为度量来构造一棵熵值下降最快的树，直到叶子节点处的熵值为0。

## 二、信息熵 ##

“信息熵”是度量样本集合纯度最常用的一种指标。假定在当前样本集合D中有k类样本（样本的标签有k类），其中第i类样本所占样本集合的比例为pi（i = 1，2，…..，k），则样本集合D的信息熵定义为

![这里写图片描述][20161205132450800]

由信息熵的公式，我们可以看出，当样本集合中只存在一类样本时，k=1，p1=1，这时候 信息熵Ent(D)的值为0；而当样本集合存在2类样本时，假定每类样本的概率为1/2，这时信息熵Ent(D)的值为1……当信息熵Ent(D)的值越小，则样本集合D的纯度越高。

而我们需要的决策树是以 信息熵 为度量来构造一棵熵值下降最快的，结点纯度越来越高的树。那我们怎么对样本集合分割，分类效果才会更好呢？如何选择我们的最优划分属性（特征）来作为我们分割样本集合时的非叶子节点？

于此，我们需要对样本的各个特征（属性）进行度量，选出当前最好的划分属性，使得我们的分类最纯。

通常的度量方法有如下方法：

*  信息增益（ID3）
 *  信息增益率（C4.5）
 *  基尼系数（CART）

## 三、信息增益 ##

对于样本中的某一个离散特征（属性） ![这里写图片描述][20161205135523892] ，其有k个可能的取值 ![这里写图片描述][20161205134748660]。若我们使用特征 ![这里写图片描述][20161205135523892] 对样本集合D进行划分，则会产生 k 个分支子节点。

在这些分支节点中，第 i 个分支节点中包含着样本集合D中所有在属性 ![这里写图片描述][20161205135523892] 上取值为 ![这里写图片描述][20161205135223969] 的样本。我们将第 i 个分支节点的样本集记作 ![这里写图片描述][20161205135940941] 。

我们可以根据 信息熵 的公式计算出 ![这里写图片描述][20161205135940941] 的信息熵 ![这里写图片描述][20161205140924923]。

那我们可以得到，根据属性 ![这里写图片描述][20161205135523892] 划分后所有分支的样本集合的信息熵的 加权为 ![这里写图片描述][20161205140845328] 。其中 |D| 表示样本集合D中的样本个数，|Di| 表示 第 i 个分支的样本集合中的样本个数。

由上我们得到了未划分前的样本集合D的信息熵 ![这里写图片描述][20161205141236823] 和 根据样本特征 ![这里写图片描述][20161205135523892] 所划分后的分支样本集合的信息熵的加权为 ![这里写图片描述][20161205140845328] 。

我们将划分前后的信息熵之差作为我们所说的“信息增益”，因此其公式为 ![这里写图片描述][20161205141647355]。其中 ![这里写图片描述][20161205135523892] 为对样本集合划分的某个属性（特征）。

又因为我们的决策树需要熵值下降最快，因此我们要选择的最优划分属性为 ![这里写图片描述][SouthEast]，其中 ai为用于划分样本集合D的第i个特征（属性）。

一般而言，信息增益越大，则意味着信息熵下降越快，分支的样本集合纯度越高。但我们会发现，当某个属性的分支较多（属性值分得较细）时，分支节点的纯度会很大，分支的样本集合的信息熵的权重和为 ![这里写图片描述][20161205140845328] 会变得很小，导致信息增益会变得很大。因此 信息增益 对分支比较多的属性 有所偏爱。

## 四、信息增益率 ##

为减少信息增益的偏好可能带来的不好影响，我们可以使用“信息增益率”来选择最优划分属性（特征）。

采用上面相同的符号，信息增益率的定义为 ![这里写图片描述][20161206153700757]。

其中 ![这里写图片描述][20161206153824382] 称为属性 ![这里写图片描述][20161205135523892] 的“固有值”（intrinsic value）。属性的固有值定义为： ![这里写图片描述][20161206154751459] 。其中 k 为属性 ![这里写图片描述][20161205135523892] 的可能取值数目，即可将样本集合D划分为k个分支节点。其中 |D| 表示样本集合D中的样本个数，|Di| 表示 第 i 个分支的样本集合中的样本个数。

当属性 ![这里写图片描述][20161205135523892] 可能的取值越多时，其属性“固有值”通常会很大，导致信息增益率会变小，在一定程度上解决了信息增益偏好带来的问题。但需注意的是，信息增益率在某种程序上可能对可取值数目较少的属性有所偏好。

## 五、基尼指数 ##

假定在当前样本集合D中有k类样本（样本的标签有k类），其中第 i 类样本所占样本集合的比例为pi（i = 1，2，…..，k），则样本集合D的纯度除了使用使用信息熵来定义，也可以使用基尼值来度量。

样本集合D的纯度可用基尼值来度量：![这里写图片描述][20161206160109987]。从公式可以看出，![这里写图片描述][20161206160231628] 反映了从样本集合D中随机抽取两个样本，其类别标记不一致的概率。

因此，![这里写图片描述][20161206160231628] 越小，则样本集合D的纯度越高。

同理，对于样本中的某一个离散特征（属性） ![这里写图片描述][20161205135523892] ，其有k个可能的取值 ![这里写图片描述][20161205134748660]。若我们使用特征 ![这里写图片描述][20161205135523892] 对样本集合D进行划分，则会产生 k 个分支子节点。

那我们可以得到，由样本特征（属性） ![这里写图片描述][20161205135523892] 所划分后的分支样本集合的基尼值的加权为 ![这里写图片描述][20161206160951193] 。其中 k 为属性 ![这里写图片描述][20161205135523892]的可能取值数目，即可将样本集合D划分为k个分支节点。其中 |D| 表示样本集合D中的样本个数，|Di| 表示 第 i 个分支的样本集合中的样本个数。

为使生成的决策树分类最纯，因此我们根据 基尼指数 的方法要选择的最优划分属性为 ![这里写图片描述][20161206161814406] ，其中 ai为用于划分样本集合D的第i个特征（属性）。

## 六、过拟合和剪枝 ##

决策树对训练样本具有很好的分类能力。而一棵对样本完全分类的决策树（完整树），对未知的[测试][Link 3]数据未必有很好的预测能力，泛化能力较差，容易出现过拟合现象。

完整树：决策树T的每个叶子节点的样本集合中的样本都为同一类型。

过拟合会导致构建出过于复杂的决策树，为解决这个问题，我们可以通过剪枝的方法来简化已生成的决策树，即将某个划分属性的节点的分支减掉，并将该节点作为一个对应某个决策结果的叶子节点（对应的决策结果可采用占多数的样本标记）。那怎么判断某个划分属性的节点是否需要剪枝呢？

因而，我们需要设计一个分类误差评估函数，然后通过极小化决策树整体的损失函数实现剪枝。

设决策树 T 有 n 个叶子节点，设第t个叶子节点的样本集合Dt有Nt个样本，这些样本的标记类别不一定相同，假设样本集合Dt中的样本有k种标记类别，第i种类别的样本有Nti个。

那么，第t个叶子节点的样本集合的经验熵 ![这里写图片描述][SouthEast 1]定义为：![这里写图片描述][SouthEast 2] 。可以看出，当第t个叶子节点的样本集合只有一种标记类型时，经验熵为0。

下面给出我们的决策树 T 的损失函数的定义：![这里写图片描述][SouthEast 3]。其中n为叶子节点数，也可以用|T|来表示，经验值参数α≥0。

C(T)表示决策树对训练数据的预测误差，参数α控制两者之间的影响，α越大，要求模型越简单，α=0表示不考虑模型的复杂度（即可以产生较多的叶子节点）。

剪枝的过程，就是当α确定时，选择损失函数最小的模型。分类越细，叶子节点的经验熵就越小，C(T)越小，但是由于分类越细会导致叶子节点的数目会很多，α|T|（或αn）越大。损失函数反映的是两者的平衡。

决策树的生成过程只考虑了样本集合分类的纯度，只考虑更好地拟合训练数据，而剪枝过程在于减小整体的复杂度。

树的剪枝算法：固定某个经验值α，对划分属性的结点进行剪枝预估，若剪枝后，决策树损失函数减小了，则减掉该结点的叶节点，将该结点作为新的叶节点，该结点对应的决策结果可以为其样本集合中占多数的样本标记。（或构造不同的α值得到一些备选树，通过交叉验证的方法得到最优树）

## 七、随机森林 ##

Bootstraping：一种有放回的抽样方法。

Bagging（ bootstrap aggregation）的策略：从样本集中进行有放回地选出n个样本；在所有属性上，对这n个样本建立分类器；重复上述两步m次，获得m个样本分类器；将数据都放在这m个样本分类器上，最终得到m个分类结果，再从这m个分类结果中决定数据属于哪一类。

随机森林采用了Bagging策略，且在其基础上进行了一些修改，采用了两个随机：

*  从样本集中使用Bootstrap采样（有放回地采样）选出n个样本
 *  从所有属性（特征）中随机选择k个部分属性（特征），选择最优划分属性作为节点来划分样本集合，建立CART决策树（不对树进行剪枝）
 *  重复以上两步m次，建立m棵CART决策树
 *  这m棵决策树形成了森林，可通过简单多数投票法（或其他投票机制）来决定森林的输出，决定属于哪一类型。（针对解决回归问题，可以采用单棵树输出结果总和的平均值）

随机森林在一定程序上提高了泛化能力，且可以并行地生成单棵树。

[Link 1]: http://lib.csdn.net/base/machinelearning
[Link 2]: http://lib.csdn.net/base/datastructure
[20161205130901262]: /images/20220714/03b8ed0e4c824e22832736b526860b8a.png
[20161205132450800]: /images/20220714/8614b0d8adf04c49bd56439de0b6d753.png
[20161205135523892]: /images/20220714/e9453f1c2ca64c2397f931e8d06b7ddf.png
[20161205134748660]: https://img-blog.csdn.net/20161205134748660
[20161205135223969]: https://img-blog.csdn.net/20161205135223969
[20161205135940941]: /images/20220714/6557be3aa927467a8b992c390c1830f2.png
[20161205140924923]: /images/20220714/f30581738c0845e185c8f5c328eacd8c.png
[20161205140845328]: /images/20220714/d06791c5b86c4d669127d7e4888cd89f.png
[20161205141236823]: https://img-blog.csdn.net/20161205141236823
[20161205141647355]: https://img-blog.csdn.net/20161205141647355
[SouthEast]: /images/20220714/03bf4faf3418455dbcfe1e0b9bd8c3c1.png
[20161206153700757]: /images/20220714/dd9f82962cff4e529c0c63d704579184.png
[20161206153824382]: https://img-blog.csdn.net/20161206153824382
[20161206154751459]: https://img-blog.csdn.net/20161206154751459
[20161206160109987]: https://img-blog.csdn.net/20161206160109987
[20161206160231628]: /images/20220714/f4deeae32bd6412880c4501ad3000c84.png
[20161206160951193]: https://img-blog.csdn.net/20161206160951193
[20161206161814406]: /images/20220714/36332df865ae4444a3dbd9af7124d470.png
[Link 3]: http://lib.csdn.net/base/softwaretest
[SouthEast 1]: https://img-blog.csdn.net/20161206170628250?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY3htc2Ni/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: /images/20220714/0f56351466db4e06b168ac5568f164eb.png
[SouthEast 3]: /images/20220714/2d454e1741264b5ca1f36440c02f2307.png