决策树与随机森林

决策树（decision tree）是一种基本的分类与回归方法，本文主要讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布，其主要优点是模型具有可读性，分类速度快。决策树学习通常包括三个步骤：特征选择，决策树的生成和决策树的修剪。而随机森林则是由多个决策树所构成的一种分类器，更准确的说，随机森林是由多个弱分类器组合形成的强分类器。

本文将先对决策树特征选择的算法ID3, C4.5和CART进行计算，然后介绍决策树的剪枝策略，最后介绍随机森林。

---

预备知识

条件熵

在信息论中，条件熵描述了在已知第二个随机变量X的前提下，随机变量Y的信息熵还剩多少。基于X条件的Y的信息熵，用H(Y|X)表示。

如果H(Y|X=x)为变数Y在变数X取特定值x条件下的熵，那么H(Y|X)就是H(Y|X=x)在X取遍所有可能的x后取平均的结果。

我们可以借助上图来帮助理解熵和条件熵：红色的整个圆表示变量X的熵，蓝色的整个圆表示变量Y的熵。
首先，熵可以理解为事件的不确定性，联系到上面的X, Y就是H(X)表示的是未知的不确定的X（也即红色的圆），而蓝色的则表示未知不确定的Y，而条件熵表示的是在知道某一事件后对另一事件未知性的减少（前提是这两个事件有交集）。放在上面则是知道确定了X后Y的不确定性还剩多少，也就是右侧蓝色的圆减去两个圆交叉的部分后剩余的，这就是条件熵H(Y|X)。
现在理解了条件熵，那么两事件X, Y中间的交集互信息该如何理解呢？既然条件熵是知晓了X后Y未知性还剩余的多少，那么互信息就可以理解为知晓了事件X后Y事件有多少也是可以确定的，也即X对Y造成的干扰部分，即为互信息I(X; Y)。
而联合熵就比较好理解了，就是事件X未知性和事件Y的未知性之和减去他们的交集部分。

首先需要知道的是熵的公式：

随机变量X的熵 对上式做简单的说明：
（1）P(x_i)表示事件x_i的概率；
（2）-P(x_i)logP(x_i)表示事件x_i的熵；

条件熵的推导公式如下：

根据条件熵的定义式，可以得到： 上式最后可以看做是给定X条件下，Y的熵值的期望

决策树生成算法

决策树分类从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点。每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶节点，最后将实例分配到叶节点的类中。

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行划分。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。通常特征选择的准则是信息增益或信息增益比，特征选择的常用算法有ID3，C4.5，CART。

信息增益

信息增益表示得知特征A的信息而使得数据X的信息的不确定性的程度。
信息增益定义：特征A对训练数据集D的信息增益g(D, A)定义为集合D的经验熵H(D)与给定特征A的条件下D的经验条件熵H(D|A)之差，即：

信息增益，也叫作互信息

根据信息增益选择特征的方法是：对于给定数据集D，计算其每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。使用信息增益选择特征的算法称为C3算法。

基本记号：
信息增益的计算方法：

信息增益比

信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在分类为题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。因此，使用信息增益比可以对这一问题进行校正，这是另一种特征选择算法，也即C4.5算法。

信息增益比定义：特征A对训练数据集D的信息增益比g_R(D, A)定义为其信息增益g(D, A)与训练集D的经验熵之比：

信息增益比

基尼指数

基尼指数是CART分类树用来选择最优特征的算法，同时决定了该特征的最优二值切分点。

定义：假设有K个类，样本点属于第k类的概率为p_k，则概率分布的基尼指数定义：

对于给定的样本集合D，其基尼指数为：

这里，C_k是D中属于第k类的样本子集，K是类的个数。

一个特征的信息增益/基尼系数越大，表明特征对样本的熵减少的能力更强，这个特征使得数据由不确定性变成确定性的能力越强。

决策树的剪枝

决策树生成算法产生的决策树对于训练数据的分类往往很准确，但对于未知数据的分类却没有这么准确，即容易出现过拟合情况。解决的办法便是考虑树的复杂度，对已生成的树进行剪枝简化。

决策树的剪枝往往通过极小化决策树整体的损失函数来实现。
设树T的叶节点个数为|T|，t是树T的叶节点，该叶节点有N_t个样本点，其中k类的样本点有N_tk个，k=1,2,3...K, H_t(T)为叶节点t上的经验熵, α>=0为参数，则决策树学习的损失函数可以定义为：

α|T|可看作是模型复杂度的正则化项 其中经验熵为： 在损失函数式子中，等式右端第一项记作： C(T)为模型与预测数据的拟合程度 最后，损失函数表示为： image.png

损失函数中C(T)表示模型对训练数据的预测误差，也即拟合程度。|T|表示模型复杂度，即节点越多模型越复杂，使用参数α来控制两者之间的影响。α越大模型越简单，对数据拟合差；α越小模型越复杂，对数据拟合性好；α=0时则不考虑模型复杂度。

因此，剪枝就是在确定了α时，选择损失函数最小的树。

随机森林

参考：
《统计学习方法》李航
机器学习. 邹博