3月机器学习在线版第八课笔记--决策树与随机森林

机器学习

初识决策树

紧随着第六课的最大熵模型的学习，我想着先完成与熵相关性很大的决策树这一课的笔记，原谅我没有理会你—第七课的聚类分析。好吧，作为开篇，让我们举一个浅显易懂的例子来说明决策树的分类思想。现在有一个女孩的母亲要给闺女介绍男朋友，有这样的对话：

女儿：多大年纪了？
母亲：26.
女儿：长得帅不帅呢？
母亲：挺帅的。
女儿：收入如何？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我和他约个时间见见吧。

这个女孩的决策过程就是一个典型的决策树分类过程（类别：见，不见）。相当于通过年龄、长相、收入、是否是公务员来决定是否与这个男人见面。假设这个女孩对潜在男友的要求是：30岁以下、长相中等以上并且是高收入或者中等以上收入的公务员，那么下面这个图可以很好地表示女孩的决策逻辑：

上图就是一个非常典型的决策树。实际生活中，对于是否出去玩，我们会考察多种因素：天气、温度、湿度等；针对此问题，我们将一个人的多次决策行为做成了一张表（每一列的含义依次是：outlook，temperature, humidity,windy,play），下面表格记录的就是多次决策行为（每一行代表一次决策）。

有了这组数据，实际上就可以画出类似于下面的决策树了。

可以知道，有很多个决策树可以被画出来，但是肯定有一个决策树优于任何其他的。那么到底哪个决策树才是最好的呢？这是第一个值得讨论的问题：怎样的决策树才是最好的，选择的规则是什么？另外，还有一个与之相关的问题：以上图决策树为例，为什么选择outlook这个特征（属性）作为第一个划分节点？更广泛的说，每一次选择节点划分的依据是什么？这两个问题是有关联的，它们与熵这个概念息息相关。我们来探讨。

---

通过这两个例子，我们来简单说一说决策树的一些定义与概念：
决策树是一种树形结构，其中每一个内部节点表示在一个特征（属性）上的测试，每个分支代表一个测试输出，每个叶子节点代表一种类别。
从例子中可以看到，决策树学习是一种归纳学习，从一堆数据中归纳出一个学习模型出来。决策树学习采用的是自顶向下的递归学习，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，树不断构建的过程也就是熵不断下降的过程。而其中节点的具体特征选择取决于哪个特征在当前节点的熵下降最快（如在构建根节点的时候，比较了年龄、长相、收入、是否公务员这些特征，发现选择年龄这一特征会导致熵下降最快，于是选择年龄作为根节点）。以此类推，到了叶子节点处的熵值即为零。至于说具体如何比较及计算熵下降的程度，稍后会给出。

决策树的优缺点

决策树算法的最大优点是：它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练实例进行较好的标注，就能够进行学习。像之前的”是否出去玩”例子，只要给定一个表格，并且每一列（最后一列是标注列）都给定（并不需要知道每一列表示的含义），那么决策树就会自己构造出一种基于规则的决策算法。
决策树缺点：可以看出，决策树的决策过程实质上是贪心法，在每一步的时候都选择当前状态下的最优解，一直走下去。我们知道贪心法并不能保证得到的最终结果是全局最优的，这也是决策树的缺陷之一，有可能会导致过拟合的问题（下面会有相应的办法来解决这个问题）。

知识点补充：
经验熵与经验条件熵
通过第六课的学习，我们知道：只要给定一个随机变量P，我们就可以求得该随机变量的熵。但是实践中，我们得到的并不是真正的随机变量p，得到的只是p的若干采样，那么我们实践中得到的熵就不一定是真正的随机变量p的熵，于是，我们称实践中得到的熵为经验熵，类似地也就有了经验条件熵的概念。教科书上的表述：当熵和条件熵中的概率是由数据估计得到时，所对应的熵和条件熵分别称为经验熵和经验条件熵。

决策树的生成算法--ID3、C4.5、CART

建立决策树的关键，是在当前状态下选择哪个特征（即属性）作为节点。之前已经讲过，选择节点的依据取决于哪个特征在当前节点的熵下降最快。那么给出了一堆数据，那么如何求每个特征的熵（或熵下降的程度）呢？根据不同的目标函数，决策树算法主要有三种算法：ID3、C4.5、CART。

---

信息增益--ID3

信息增益表示的是得知特征（即属性）$A$的信息而使得类X的信息的不确定性减少的程度。具体定义如下：特征$A$对训练集$D$的信息增益$g(D,A)$,定义为集合$D$的经验熵$H(D)$与特征$A$给定条件下 $D$的经验条件熵$H(D|A)$之差，即：

$$g(D,A)=H(D)-H(D|A) ~~~~~~~~~~(1)$$
从表达式中可以知道，这即为训练数据集$D$与特征$A$的互信息(第六课知识)。

让我们来详细计算一下信息增益。需要定义如下符号：
设训练数据集为$D$，$|D|$表示其容量，即样本个数。假设有$K$个类$C_k$,$k=1,2,...,K$,$|C_k|$为属于类$C_k$的样本个数。$\sum_k|C_k|=|D|$。假设特征$A$有$n$个不同的取值{$a_1,a_2,...,a_n$},根据特征$A$的取值将$D$划分为$n$个子集$D_1,D_2,...,D_n$,$|D_i|$为$D_i$的样本个数，$\sum_i|D_i|=D$.记子集$D_i$中属于类$C_k$的样本的集合为$D_{ik}$,$|D_{ik}|$为$D_{ik}$的样本个数。

比较复杂的符号概念，但是理解起来并不复杂。以“是否出去玩”那个例子来说，类别只有两个：出去玩、不出去玩。而特征temperature有三个取值：hot,mild,cool。根据特征temperature可以将整个数据集划分为3个子集，而每个子集中属于“出去玩”的样本数目可以计算出来，属于“不出去玩”的样本数目也可以计算出来。

得到了各样本集合的数目后，我们就可以计算信息增益了。首先，计算数据集$D$的经验熵：

$$H(D)=-\sum_{k=1}^{K}\frac{C_k}{D}log\frac{C_k}{D} ~~~~~~~~~~(2)$$
这里我们使用了“通过频率估计概率”这种思想。接下来计算特征$A$对数据集$D$的经验条件熵:
$$\begin{aligned} H(D|A)&=-\sum_{i,k}p(D_k,A_i)log~p(D_k|A_i)\\ &=-\sum_{i,k}p(A_i)p(D_k|A_i)log~p(D_k|A_i)\\ &=-\sum_{i=1}^n\sum_{k=1}^Kp(A_i)p(D_k|A_i)log~p(D_k|A_i)\\ &=-\sum_{i=1}^np(A_i)(\sum_{k=1}^Kp(D_k|A_i)log~p(D_k|A_i)\\ &=-\sum_{i=1}^n\frac{|D_i|}{|D|}\sum_{k=1}^K(\frac{|D_{ik}|}{|D_i|}log\frac{|D_{ik}|}{|D_i|}) \end{aligned}$$
进而可以计算公式（1）来信息增益了。值得注意的是，这里计算的是该选择哪一个特征（属性）来作为根节点，所以使用的是全集数据集$D$。如果是计算的是中间节点，那么得到的数据集不再是全集$D$,而是上一节点经过划分之后传送给该节点的数据集$\hat{D}$。已经被树的较高节点选取的特征被排除在外，以便任何给定的特征在树的任意路径中最多仅出现一次。

ID3示例

OUTLOOK	TEMPERATURE	HUMIDITY	WINDY	PLAY
sunny	85	85	false	Don't Play
sunny	80	90	true	Don't Play
overcast	83	78	false	Play
rain	70	96	false	Play
rain	68	80	false	Play
rain	65	70	true	Don't Play
overcast	64	65	true	Play
sunny	72	95	false	Don't Play
sunny	69	70	false	Play
rain	75	80	false	Play
sunny	75	70	true	Play
overcast	72	90	true	Play
overcast	81	75	false	Play
rain	71	80	true	Don't Play

在全集中，出去玩占9，不出去玩占5，那么可得：
$H(D)=\frac{9}{14}log\frac{9}{14}+\frac{5}{14}log\frac{5}{14}=0.94$.

计算$H(D|Outlook)$：看表可得，Outlook特征（属性）将全集分成了三个子集，其中Sunny占5，rain占5，overcast占4；Sunny子集中出去玩占2，不出去玩占3；另外两子集数目也可计算得到，那么代入公式可得：

$$\begin{aligned} H(D|Outlook)&=\frac{5}{14}*(\frac{2}{5}log\frac{2}{5}+\frac{3}{5}log\frac{3}{5})+\frac{5}{14}*(\frac{2}{5}log\frac{2}{5}+\frac{3}{5}log\frac{3}{5}) \\ &+\frac{4}{14}*(\frac{4}{4}log\frac{4}{4}+0)=0.694 \end{aligned}$$
那么特征Outlook相对于全集D的信息增益为$g(D,Outlook)=0.94-0.694=0.246$。
类似的做法，我们还可以求出特征Windy相对于全集D的信息增益为$g(D,Windy)=0.94-0.892=0.048$。于是根据信息增益作为目标函数的做法，根节点上选取特征Outlook是要好于选取特征Windy的。
以上就是通过信息增益来得出决策树的方法，即ID3算法。通过上面的推导可以知道，只需要知道各个集合（如$D_{ik},D_i$等）的个数，代入公式去计算就可以了。

---

信息增益率--C4.5

之前已经说过，决策树算法的不同主要是因为目标函数的不同。ID3算法使用了信息增益作为目标函数，而C4.5算法则是在ID3的基础上得出的算法，目标函数有略微不同而已。严格上讲，C4.5只能是ID3的改进算法。

为什么会产生C4.5算法呢？这还得从ID3算法自身的缺点说起。ID3算法在选择具体特征作为节点的时候，它会偏向于选择取值较多的特征（如：Windy只有False、Ture两个取值，而Outlook有Sunny，rain，overcast三个取值）。一个极端的情况为：以是否出去玩为例，假设新来的一列特征为Partner,它有14个取值（即每个取值只有一条记录），那么经过计算可以发现，$H(D|Partner)=0$, 这样信息增益即为最大的，必然选择此特征作为节点。可以想象，这样做必然会导致构造的决策树很庞大却深度很浅，这样构造的效果并不好。

C4.5算法试图修正上述ID3的不足，它采用的是信息增益率作为目标函数：

$$g_r(D,A)=\frac{g(D,A)}{H_D(A)}$$
其中$H_D(A)$称为“分裂信息（split information）”,分裂信息$H_D(A)$类似于经验熵$H(D)$,定义如下：
$$H_D(A)=-\sum_{j=1}^{v}\frac{|D_j|}{|D|}log\frac{|D_j|}{|D|}$$
它表示的是数据集D被特征A划分为$v$个分区所产生的信息熵。可以知道，面对上面举例的特征Partner,信息增益率会在信息增益的基础上除以一个较大的分裂信息$H_D(A)$作为修正。

---

基尼指数--CART

Classification And Regression Tree，即分类回归树算法，简称CART算法，它是决策树的一种实现。与之前提到的ID3、C4.5算法不同，CART算法是一种二分递归分割技术，把当前样本集合划分为两个子集合，它生成的每个非叶子节点都只有两个分支（即二叉树）。要知道，ID3、C4.5的每个节点并没有规定是二分支，可以三分支、四分支。而CART则是规定的二分支。
在具体分析CART的建树过程之前，我们先来了解一下GINI指数的概念：给定一个数据集$D$,其中包含的分类类别总数为$K$，类别$k$在数据集中的个数为$|C_k|$,其GINI指数表示为：

$$\begin{aligned} GINI(D)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2=1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2 \end{aligned}$$
可以知道，数据集内包含的类别越杂乱，GINI指数就越大。

CART的建树过程也是较为简单的：

1.在决策树的非叶子节点$A$上尝试按照节点上数据的任何特征（属性）的任何分裂点进行划分，产生当前节点$A$的左右两个子节点$B$、$C$。最好划分依据是使得

$$GINI(A)-(GINI(B)+GINI(C))$$ 最大的那一个划分。
2.停止条件：一个节点产生左右子节点后，递归地对左右子节点进行划分，即可产生分类回归树。那么什么时候节点就可以停止分裂了？最直观的情况是：当节点包含的数据都属于同一个类别的时候就可以停止分裂了。在实际操作中，还可以通过设定节点最小记录数、子节点记录数占父节点记录数的最小百分比等这些参数来设定停止条件。

实际上，CART中对连续值特征（属性）的处理极为方便，因为只需要通过特征将数据集一分为二即可。假设连续值特征在数据集中的取值有m个，那么选择分裂点的时候可以尝试的分裂点即有m-1个（取数据集特征中大小相邻的两个数的平均值作为一个可能的分裂点）。

决策树常见问题及完善方法指引

Q1：如何处理连续值属性（针对ID3、C4.5）？
直到现在为止，不管是ID3还是C4.5，我们讨论到的特征（属性）的值都是离散型的，那么当特征取值是连续型的怎么做呢？
A1：可以通过动态地定义新的离散值属性来实现，即先把连续型特征的值域分割为多个离散的区间集合。至于如何选择划分区间的边界（阈值），可以考虑选择产生最大信息增益的阈值。具体做法可以参考决策树的相应文献[1]。

Q2:如何处理缺少属性值的训练样本？
在某些情况下，可供使用的数据可能缺少某些属性的值。
A2：一个处理策略是：将在现节点下的所有训练样本中该属性的最常见的值赋予该缺少属性值的训练样本。更复杂的策略可以参考文献[2]。

Q3:决策树的过拟合问题（在训练集合效果很好，在测试集合效果不好）有哪些解决办法？
A3：不管是ID3、C4.5还是CART,它们都是使用贪心算法构造出的决策树，过拟合问题均有可能发生。有几类方法可以避免决策树学习中的过拟合:1.通过设定停止规则及早停止树的增长（如设定节点最小记录数、子节点记录数占父节点记录数的最小百分比等）；2.后修剪法，即允许树过度拟合数据，然后对这棵树进行后修剪[3][4]。3.随机森林，该方法将在下一章节中详细讲解。

多模型融合之--Bagging方法

Bagging是bootstrap aggregation的简称，它是一种有放回的抽样方法。标题已经说明了，Bagging方法是多模型融合方法，它之所以提出来是为了解决单一分类器容易产生过拟合的问题。Beriman 于199年首次在文章中提出该方法，又兴趣看原文的请戳这里。
针对分类问题，Bagging的策略是这样的：

1. 从样本集合中重采样（有重复的）选出n个样本；
2. 在所有特征（属性）上，对这n个样本建立分类器（可以是ID3、C4.5、CART、SVM、Logistic回归等）；
3. 重复上面两步骤 m次，即可获得m个分类器；
4. 将按照以上步骤得到的数据放在这m个分类器上，最后根据这m个分类器的投票结果，决定数据属于哪一类。

说白了Bagging方法就是一种投票策略。只不过值得注意的是它的采样（也称为Bootstrap采样）是重采样。研究表明，Bagging采样中大约有63.2%不是重复数据，剩下的都是重复数据。

针对回归问题，Bagging的策略是一样的，只不过具体操作中最后一步不是投票，而是求所有预测值的均值。

下图是Bagging的选择策略:

Bagging解析

1. m个分类器其实没有必要都是一样的分类器（比如说都是CART），可以是多个分类器共同构成（如CART、SVM、Logistic回归结合起来用）。
2. 投票过程也是一个值得研究的过程，不同的投票方式（如一票否决、少数服从多数、阈值表决、贝叶斯投票机制等）可能会导致不同的结果。
3. 可以通过设置权重来表示不同分类器的重要性程度。

随机森林(Random Forest)

随机森林在Bagging基础上做了一定的修改。它的流程如下：

1. 从样本集合中使用Boostrap采样选出n个样本；
2. 从所有特征（属性）中随机选择k个特征（属性），选择最佳分类特征（属性）作为节点建立CART决策树(也可以是ID3、C4.5)；
3. 重复上面两步骤 m次，即建立了m棵CART决策树；
4. 这m个CART形成随机森林，通过投票表决结果，决定数据属于哪一类。

通过对比我们可以看到，随机森林将Bagging方法中的第二步做了小小的修改，随机森林中从所有特征中随机选取k个特征，而不是使用所有特征。随机森林中的"随机"是指：
1. Bootstrap中的随机选择子样本；
2. Random subspace的算法从特征集中随机选择k个特征，每个树节点分裂时，从这随机的k个特征，选择最优的；

当然，就像Bagging一样，在随机森林中，我们也可以使用SVM、Logistic回归作为基础分类器。习惯上，这些分类器组成的“总分类器”，依然叫做随机森林。