随机森林基础内容：这里只是准备简单谈谈基础的内容，主要参考一下别人的文章，对于随机森林与GBDT，有两个地方比较重要，首先是information gain，其次是决策树。

这里特别推荐Andrew Moore大牛的Decision Trees Tutorial，与Information Gain Tutorial。

Moore的Data Mining Tutorial系列非常赞，看懂了上面说的两个内容之后的文章才能继续读下去。

决策树实际上是将空间用超平面进行划分的一种方法，每次分割的时候，都将当前的空间一分为二，比如说下面的决策树：就是将空间划分成下面的样子：这样使得每一个叶子节点都是在空间中的一个不相交的区域，在进行决策的时候，会根据输入样本每一维feature的值，一步一步往下，最后使得样本落入N个区域中的一个（假设有N个叶子节点）随机森林(Random Forest):随机森林是一个最近比较火的算法，它有很多的优点：∙在数据集上表现良好∙在当前的很多数据集上，相对其他算法有着很大的优势∙它能够处理很高维度（feature很多）的数据，并且不用做特征选择∙在训练完后，它能够给出哪些feature比较重要∙在创建随机森林的时候，对generlization error使用的是无偏估计∙训练速度快∙在训练过程中，能够检测到feature间的互相影响∙容易做成并行化方法∙实现比较简单随机森林顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。

在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。

在建立每一棵决策树的过程中，有两点需要注意- 采样与完全分裂。

首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。

对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。

假设输入样本为N个，那么采样的样本也为N个。

这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。

然后进行列采样，从M 个feature中，选择m个(m << M)。

之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。

一般很多的决策树算法都一个重要的步骤- 剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。

按这种算法得到的随机森林中的每一棵都是很弱的，但是大家组合起来就很厉害了。

我觉得可以这样比喻随机森林算法：每一棵决策树就是一个精通于某一个窄领域的专家（因为我们从M个feature中选择m让每一棵决策树进行学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数据），可以用不同的角度去看待它，最终由各个专家，投票得到结果。

随机森林的过程请参考Mahout的random forest。

这个页面上写的比较清楚了，其中可能不明白的就是Information Gain，可以看看之前推荐过的Moore的页面。

随机森林算法详解：定义：随机森林是一个分类器，它有一系列的单株树决策器{h （X,，θk ）；k=1，......}来组成,其中{θk }是独立同分布的随机变量。

再输入X 时，每一棵树只投一票给它认为最合适的类。

在机器学习中，随机森林是一个包含多个决策树的分类器， 并且其输出的类别是由个别树输出的类别的众数而定,构成随机森林的基础分类器称为决策树。

Leo Breiman 和Adele Cutler 发展出推论出随机森林的算法。

这个术语是1995年由贝尔实验室的Tin Kam Ho 所提出的随机决策森林（random decision forests ）而来的。

这个方法则是结合 Breimans 的 "Bootstrap aggregating" 想法和 Ho 的"random subspace method"" 以建造决策树的集合。

随机森林是一个组合分类器，构成随机森林的基础分类器是决策树。

决策树算法决策树可以视为一个树状预测模型，它是由结点和有向边组成的层次结构。

树中包含3个节点：根节点。

内部节点，终节点（叶子节点）。

决策树只有一个根节点，是全体训练集的结合。

树中的每个内部节点都是一个分裂问题，它将到达该节点的样本按某个特定的属性进行分割，可以将数据集合分割成2块或若干块。

每个终结点（叶子节点）是带有分裂标签的数据集合，从决策树的根节点到叶子节点的每一条路径都形成一个类；决策树的算法很多，例如ID3算法，CART 算法等。

这些算法均采用自上而下的贪婪的算法，每个内部节点选择分类效果最好的属性进行分裂节点，可以分为两个或若干个子节点，继续此过程到这可决策树能够将全部训练数据准确的分类，或所有属性都被用到为止。

具体步骤如下：1)假设T 为训练样本集。

2)选择一个最能区分T 中样本的一个属性。

3)创建一个数的节点，它的值是所选择的属性，创建此节点的子节点，每个子链代表所选属性的唯一值，适用子链的值进一步将样本细分为子类。

对于3)创建的三个子类（1）如果子类的样本满足预定义的标准，或者树的这条路的剩余可选属性集为空，为沿此路径的新的样本指定类别。

（2）如果子类不满足于定义的标准，或者至少有一个属性能细分树的路径，设T 为当前子类样本的集合，返回步骤2），以下简单的给出二分树的结构图示：根节点 中间节点 叶节点 规则1 叶节点 规则2中间节点建树算法在属性的选择标准非常重要。

属性的选择的方法有很多种，例如信息增益（information gain）、信息增益比（information gain ratio）Gini指标（Gini Index）等方法。

ID3算法依据信息增益来选择属性。

信息增益是在熵作为尺度的，是衡量属性对训练数据的分类的能力的标准。

CART算法是利用Gini指标作为尺度来分裂属性的。

Gini指标适用于二进制连续数值等类型的字段。

为了防止决策树和训练样本集的过度拟合，需要对决策树进行剪枝。

剪枝通常有事先剪枝法和事后剪枝法两种方法。

事先剪枝法事建树过程中判断当前节点是否需要继续划分的简直方法。

通常是通过重要性检测（ 2或信息增益等）判断是否停止分裂节点。

事后剪枝方法是让树“充分成长”之后在判断是否进行停止分裂节点。

常用到的方法是根据错误分类率（或决策树编码长度）进行决策树的事后剪枝。

决策树具有以下四个优点：决策树方法不需要假设先验概率的分布，这种非参数化的特点使其具有更好的灵活性和鲁棒性。

决策树方法不仅可以利用连续实数或离散的数值样本，而且可以利用“语义数据”比如离散的语义数据：东、南、西、北等。

决策树方法产生的决策树或产生式规则具有结构简单直观，容易理解以及计算效率高的特点。

决策树方法能够有效地抑制训练样本噪音和解决属性缺失问题。

因此可以防止由于训练样本存在噪声和数据确实引起的精度降低。

但决策树也有与生俱来的缺点：1）分类规则杂2）收敛到非全局的局部最优解3）过度拟合由于分类复杂则它可能过于适合噪声从而导致过度拟合问题。

为了克服以上的缺点，引入了另一种预测模式——随机森林。

随机森林的特征随机森林具有以下的特征：在现有的算法中随机森林算法的精度是无可比拟的。

随机森林能够有效地处理大的数据集。

随机森里面可以处理没有删减的成千上万的变量。

随机森林能够在分类的过程中可以生成一个泛化误差的内部无偏估计。

随机森林是一种有效地估计缺失数据的一种方法，当数据集中有大比例的数据缺失时仍然可以保持精度不变。

在不平衡的数据集的类别总图中可以平衡误差。

保存生成的随机森林以备解决其他的数据。

技术原型的计算可以给出变量之间的相关性和分类的信息。

可以计算实例组之间的相似度，可以用来做聚类分析，确定异常点（通过缩放比例）给出数据集的有趣诠释。

上述的能力可以为没有标签的数据导出无监督的聚类方法和异常点检测。

随机森林提供了一种检测变量交互作用的实验方式。

特别值得注意的是随机森林的运行速度非常的块并且不会产生过度拟合，可以根据需要来生成任意多的树。

基于随机树上的诸多优点，随机森林在当前的机器学习领域是一个新的研究热点。

随机森林的理论基础随机森林之所有那么多的优点，是因为有强大的数学知识做后盾。

一个随机森林是否能够进行正确的分类，分类的效果如何，以及如何评价随机森林的分类效果都有数学知识的基础。

R.F 不会过度拟合的保证——大数定律随机森林的一个与众不同的特征就是它不会产生过度拟合。

那么它为什么不会产生过度拟合呢？不会产生过度拟合的理论依据是什么呢？下面解释这一个问题。

给定一系列分类器h （x ，θ1），h （x ，θ2），，，，，，h （x ，θk ）随机取出服从随机向量Y ,X 分布的训练集。

定义边际函数为：))((max ))((),(j x I a y x I a Y X h v h v m k k y j k k g =-==≠其中I(.)是示性函数，(.)v k a 表示取平均。

于是，边际函数刻画了在正确分类Y下X 的得票超过其他分类的最大平均得票数的程度。

该值越大，表明分类器的置信度越高。

泛化误差由下式得出：)0),((,<=*Y X P m P E g Y X 其中，下标X,Y 表明了概率的定义空间。

在随机森林中，)(x h k =h （x ，θk ）。

当树的数目很大时，它会遵循大数定律，因此树的结构为：随着分类树数目的增加，由于所有的序列θi ，*pE 几乎处处收敛到)0),((max )),(((,<=-==≠j x h y y X h p p p Y j Y X θθθθ其中θ是对应单棵树决策树的随机变量，h （x ，θ）是基于x 和θ的输出。

这以结果解释了为什么随机森林不会随着分布树的增加而产生过拟合，但是却有一个有限的繁华误差值。

它的依据是大数定律。

在有关随机森林的实验中，装袋方法和随机特征选择并行应用。

袋装方法的每一个新的训练集都是在原始训练集中通过一种叫做步步为营法随机重复采样得到的。

应用这种方法的训练集一般只能包含原训练集中大约百分之六十七的样本，其余的样本作为袋外数据，基于新的训练集生成树可以充分的成长，不进行剪枝。

应用袋装方法的两个原因。

其一，当使用随机特征时，结合袋装方法可以提高精度。

其二，袋装方法可以对一个树集的总体泛化误差*pE 不断变化的上界进行估计，与效能和相关性的估计一样的好。