机器学习算法三：bagging及随机森林算法

在学习随机森林算法之前，首先需要对一些基础知识有一些了解。

1 信息、熵，信息增益及决策树

在学习任何跟决策树有关的算法时，都会接触到题目中的这几个概念，理解这几个概念有助于以后的学习，废话不多说。

1.1 信息

信息这个概念真的极其的抽象，看了很多博主的文章感觉还是理解不了，再看看香农的话，信息是用来消除随机不确定性的东西，更让人不知所云。
要理解信息的概念，就必须了解信息含量这个东西是如何去量化的，举个例子：小明说“明天NBA总决赛骑士VS勇士，我觉得骑士赢！”和小王说“明天NBA总决赛骑士VS勇士第四场，之前比分为3：0，我觉得骑士赢定了”。NBA总决赛谁会最终取得胜利这个不得而知，是一个不确定事件，但是相比于小明的话，小王的话显得更让人信服，因为小王提供了更多的信息，让一个不确定的事件变得似乎更确定了，所以信息的量化跟不确定性的变化趋势是相关的，当一个事件由不确定变得似乎确定时，说明提供给该事件的信息量得到了增加，如果提供的信息不影响事件的确定性，则说明信息量没有增加，比如：你说“明天太阳会从东边升起来”，就算你把这句话说一百遍，然后给我一堆解释为什么太阳要从东边升起，但是对于事件本身来说信息量没有丝毫的增加，因为这个事件本身就是确定的，任何话都不会改变这个事件的确定性。
那么这个不确定性的变化跟什么有关了？
1.跟事情的可能结果的数量有关
2.跟事件结果发生概率有关
我们该如何用数学公式来表示信息量呢？某类信息量的定义公式如下：

一个事件的信息量就是这个事件发生的概率的负对数。
1.跟事情的可能结果的数量有关：假设事件每一个可能的结果出现的概率一样，如果可能出现结果数量越多则每个结果所占的概率越小，那么新信息有更大的潜力具有更多的信息量，所以上式定义的信息量变大大。
2.跟事件结果发生概率有关：假如一个事件中结果A发生的概率为99%，那么新信息能够提供的信息量就很小，因为不论提供什么信息都很难改变事件的结果，所以上式定义的信息量会较小，公式满足。

1.2 信息熵

在信息论和概率论中熵是对随机变量不确定性的度量与信息量联系起来，熵便是信息的期望值，可以记作：

熵只依赖X的分布，和X的取值没有关系，熵是用来度量不确定性，当熵越大，概率说X=xi的不确定性越大，反之越小，在机器学期中分类中说，熵越大即这个类别的不确定性更大，反之越小，当随机变量的取值为两个时，熵随概率的变化曲线如下图：
当p=0或p=1时，H(p)=0,随机变量完全没有不确定性，当p=0.5时，H(p)=1,此时随机变量的不确定性最大

1.3 信息增益

信息增益在决策树算法中是用来选择特征的指标，信息增益越大，则这个特征的选择性越好，在概率中定义为：待分类的集合的熵和选定某个特征的条件熵之差（这里只的是经验熵或经验条件熵，由于真正的熵并不知道，是根据样本计算出来的），公式如下：

D是样本集，a是属性集，v指不同的属性。

1.4 决策树

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。常见的决策树算法有C4.5、ID3和CART。

2 集成学习

集成学习方法可以形象的理解为“三个臭皮匠顶个诸葛亮”，一个学习器没有办法达到很好的泛化性能，那我们就用一堆学习器来弥补。通过输入不同的测试集（或者具有不同分布的测试集）给各个学习器，从而得到了许多偏向性不同模型，然后采用结合各个模型的优势综合得出结论来提高模型的泛化性能。根据学习器的之间的关系可以分为：学习器之间有强依赖关系的串联生产方式（Adaboost、gradient boosting machine、XGBoost）、学习器之间没有强依赖关系的并行生成方式（bagging，随机森林）。

3 bagging方法

bagging 方法是随机森林法的基础，其实现的主要原理是采用了自助采样法(boostrap sampling），前面提到为了使得集成学习方法的性能优于单个学习器模型，我们要尽量是每个学习器得到偏好不同的模型，怎么样才能使模型的偏好不同呢？最直接的方法就是改变每个学习器的输入参数，但是样本的数量是固定的，怎么才能即得到很多组不同的输入参数，又能最大化的使用输入集。自助采样法就可以很好的解决这个问题，其原理是：假设训练集大小为N,随机有放回的从训练集中抽取N个不同的样本，这新样本集中有很多重复出现的样本，也有很多原始样本集中的样本未被抽中,其概率满足下面公式

这里我们应该就能理解bagging方法是如何实现得到不同偏好的学习模型的了。

4 随机森林

现在我们应该不难理解随机森林了，它就是bagging方法的变体，是在将bagging方法的基学习器确定为决策树，并且在决策树的训练过程中引入了随机属性选择。具体说，传统决策树在选择属性时是在当前节点的属性集合M中选择最优属性，而随机森林是先在当前节点的属性集合中随机挑选m(m < M)个属性的子集，然后再在子集中选择最优属性。
这里可以总结随机森林的特点：
1.采用自助采样法，生成随机输入集；
2.在训练决策树时，先对属性集合随机采样再择优。

随机森林的构建过程大致如下：

1.从原始训练集中使用Bootstraping方法随机有放回采样选出m个样本，共进行n_tree次采样，生成n_tree个训练集
2.对于n_tree个训练集，我们分别训练n_tree个决策树模型
3.对于单个决策树模型，假设训练样本属性个数为N，那么每次分裂时先从属性集合N中随机采样n（推荐值n=long2N$lon{g}_{2}N$）个属性，然后根据信息增益/信息增益比/基尼指数选择最好的特征进行分裂
4.每棵树都一直这样分裂下去，直到该节点的所有训练样例都属于同一类。在决策树的分裂过程中不需要剪枝
5.将生成的多棵决策树组成随机森林。对于分类问题，按多棵树分类器投票决定最终分类结果；对于回归问题，由多棵树预测值的均值决定最终预测结果

这些特点就导致随机森林有许多优点：
具有极高的准确率
随机性的引入，使得随机森林不容易过拟合
随机性的引入，使得随机森林有很好的抗噪声能力
能处理很高维度的数据，并且不用做特征选择
既能处理离散型数据，也能处理连续型数据，数据集无需规范化
训练速度快，可以得到变量重要性排序
容易实现并行化

推荐一篇很好的随机森林的博文，既有理论讲解，又有代码示例
http://www.cnblogs.com/maybe2030/p/4585705.html