学习算法根据下列算法而建造每棵树：1. 用N 来表示训练例子的个数，M表示变量的数目。

2. 我们会被告知一个数m ，被用来决定当在一个节点上做决定时，会使用到多少个变量。

m应小于M3. 从N个训练案例中以可重复取样的方式，取样N次，形成一组训练集（即bootstrap取样）。

并使用这棵树来对剩余预测其类别，并评估其误差。

4. 对于每一个节点，随机选择m个基于此点上的变量。

根据这m 个变量，计算其最佳的分割方式。

5. 每棵树都会完整成长而不会剪枝（Pruning）（这有可能在建完一棵正常树状分类器后会被采用）。

优点随机森林的优点有：1. 对于很多种资料，它可以产生高准确度的分类器。

2. 它可以处理大量的输入变量。

3. 它可以在决定类别时，评估变量的重要性。

4. 在建造森林时，它可以在内部对于一般化后的误差产生不偏差的估计。

5. 它包含一个好方法可以估计遗失的资料，并且，如果有很大一部分的资料遗失，仍可以维持准确度。

6. 它提供一个实验方法，可以去侦测variable interactions 。

7. 对于不平衡的分类资料集来说，它可以平衡误差。

8. 它计算各例中的亲近度，对于数据挖掘、侦测偏离者（outlier）和将资料视觉化非常有用。

9. 使用上述。

它可被延伸应用在未标记的资料上，这类资料通常是使用非监督式聚类。

也可侦测偏离者和观看资料。

10. 学习过程是很快速的。

缺点1. 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟2. 对于有不同级别的属性的数据，级别划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的。

在机器学习中，随机森林由许多的决策树组成，因为这些决策树的形成采用了随机的方法，因此也叫做随机决策树。

随机森林中的树之间是没有关联的。

当测试数据进入随机森林时，其实就是让每一颗决策树进行分类，最后取所有决策树中分类结果最多的那类为最终的结果。

因此随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。

随机森林可以既可以处理属性为离散值的量，比如ID3算法，也可以处理属性为连续值的量，比如C4.5算法。

另外，随机森林还可以用来进行无监督学习聚类和异常点检测。

随机森林由决策树组成，决策树实际上是将空间用超平面进行划分的一种方法，每次分割的时候，都将当前的空间一分为二，比如说下面的决策树（其属性的值都是连续的实数）：随机深林的优点：比较适合做多分类问题；训练和预测速度快；对训练数据的容错能力，是一种有效地估计缺失数据的一种方法，当数据集中有大比例的数据缺失时仍然可以保持精度不变；能够有效地处理大的数据集；可以处理没有删减的成千上万的变量；能够在分类的过程中可以生成一个泛化误差的内部无偏估计；能够检测到特征之间的相互影响以及重要性程度；不过出现过度拟合；实现简单容易并行化。

当可以生成好决策树后，就比较容易生成随机森林了。

下面是随机森林的构造过程：1. 假如有N个样本，则有放回的随机选择N个样本(每次随机选择一个样本，然后返回继续选择)。

这选择好了的N个样本用来训练一个决策树，作为决策树根节点处的样本。

2. 当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m << M。

然后从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。

3. 决策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶子节点，无须继续分裂了）。

一直到不能够再分裂为止。

注意整个决策树形成过程中没有进行剪枝。

4. 按照步骤1~3建立大量的决策树，这样就构成了随机森林了。

从上面的步骤可以看出，随机森林的随机性体现在每颗数的训练样本是随机的，树中每个节点的分类属性也是随机选择的。

有了这2个随机的保证，随机森林就不会产生过拟合的现象了。

随机森林有2个参数需要人为控制，一个是森林中树的数量，一般建议取很大。

另一个是m 的大小，推荐m的值为M的均方根。

1.随机森林原理介绍随机森林，指的是利用多棵树对样本进行训练并预测的一种分类器。

该分类器最早由Leo Breiman和Adele Cutler提出，并被注册成了商标。

简单来说，随机森林就是由多棵CART （Classification And Regression Tree）构成的。

对于每棵树，它们使用的训练集是从总的训练集中有放回采样出来的，这意味着，总的训练集中的有些样本可能多次出现在一棵树的训练集中，也可能从未出现在一棵树的训练集中。

在训练每棵树的节点时，使用的特征是从所有特征中按照一定比例随机地无放回的抽取的，根据Leo Breiman的建议，假设总的特征数量为M，这个比例可以是sqrt(M),1/2sqrt(M),2sqrt(M)。

因此，随机森林的训练过程可以总结如下：(1)给定训练集S，测试集T，特征维数F。

确定参数：使用到的CART的数量t，每棵树的深度d，每个节点使用到的特征数量f，终止条件：节点上最少样本数s，节点上最少的信息增益m对于第1-t棵树，i=1-t：(2)从S中有放回的抽取大小和S一样的训练集S(i)，作为根节点的样本，从根节点开始训练(3)如果当前节点上达到终止条件，则设置当前节点为叶子节点，如果是分类问题，该叶子节点的预测输出为当前节点样本集合中数量最多的那一类c(j)，概率p为c(j)占当前样本集的比例；如果是回归问题，预测输出为当前节点样本集各个样本值的平均值。

然后继续训练其他节点。

如果当前节点没有达到终止条件，则从F维特征中无放回的随机选取f维特征。

利用这f维特征，寻找分类效果最好的一维特征k及其阈值th，当前节点上样本第k维特征小于th的样本被划分到左节点，其余的被划分到右节点。

继续训练其他节点。

有关分类效果的评判标准在后面会讲。

(4)重复(2)(3)直到所有节点都训练过了或者被标记为叶子节点。

(5)重复(2),(3),(4)直到所有CART都被训练过。

利用随机森林的预测过程如下：对于第1-t棵树，i=1-t：(1)从当前树的根节点开始，根据当前节点的阈值th，判断是进入左节点(<th)还是进入右节点(>=th)，直到到达，某个叶子节点，并输出预测值。

(2)重复执行(1)直到所有t棵树都输出了预测值。

如果是分类问题，则输出为所有树中预测概率总和最大的那一个类，即对每个c(j)的p进行累计；如果是回归问题，则输出为所有树的输出的平均值。

注：有关分类效果的评判标准，因为使用的是CART，因此使用的也是CART的平板标准，和C3.0,C4.5都不相同。

对于分类问题（将某个样本划分到某一类），也就是离散变量问题，CART使用Gini值作为评判标准。

定义为Gini=1-∑(P(i)*P(i)),P(i)为当前节点上数据集中第i类样本的比例。

例如：分为2类，当前节点上有100个样本，属于第一类的样本有70个，属于第二类的样本有30个，则Gini=1-0.7×07-0.3×03=0.42，可以看出，类别分布越平均，Gini值越大，类分布越不均匀，Gini值越小。

在寻找最佳的分类特征和阈值时，评判标准为：argmax （Gini-GiniLeft-GiniRight），即寻找最佳的特征f和阈值th，使得当前节点的Gini值减去左子节点的Gini和右子节点的Gini值最大。

对于回归问题，相对更加简单，直接使用argmax(Var-VarLeft-VarRight)作为评判标准，即当前节点训练集的方差Var减去减去左子节点的方差VarLeft和右子节点的方差VarRight值最大。

3.如何自己设计随机森林程序有时现有的库无法满足要求，就需要自己设计一个分类器算法，这部分讲一下如何设计自己的随机森林分类器，代码实现就不贴了，因为在工作中用到了，因此比较敏感。

首先，要有一个RandomForest类，里面保存整个树需要的一些参数，包括但不限于：训练样本数量、测试样本数量、特征维数、每个节点随机提取的特征维数、CART树的数量、树的最大深度、类别数量（如果是分类问题）、一些终止条件、指向所有树的指针，指向训练集和测试集的指针，指向训练集label的指针等。

还要有一些函数，至少要有train和predict 吧。

train里面直接调用每棵树的train方法即可，predict同理，但要对每棵树的预测输出做处理，得到森林的预测输出。

其次，要有一个sample类，这个类可不是用来存储训练集和对应label的，这是因为，每棵树、每个节点都有自己的样本集和，如果你的存储每个样本集和的话，需要的内存实在是太过巨大了，假设样本数量为M，特征维数为N，则整个训练集大小为M×N，而每棵树的每层都有这么多样本，树的深度为D，共有S棵树的话，则需要存储M×N×D×S的存储空间。

这实在是太大了。

因此，每个节点训练时用到的训练样本和特征，我们都用序号数组来代替，sample类就是干这个的。

sample的函数基本需要两个就行，第一个是从现有训练集有放回的随机抽取一个新的训练集，当然，只包含样本的序号。

第二个函数是从现有的特征中无放回的随机抽取一定数量的特征，同理，也是特征序号即可。

然后，需要一个Tree类，代表每棵树，里面保存树的一些参数以及一个指向所有节点的指针。

最后，需要一个Node类，代表树的每个节点。

需要说明的是，保存树的方式可以是最普通的数组，也可是是vector。

Node的保存方式同理，但是个人不建议用链表的方式，在程序设计以及函数处理上太麻烦，但是在省空间上并没有太多的体现。

随机森林是一个用随机方式建立的，包含多个决策树的分类器。

其输出的类别是由各个树输出的类别的众数而定。

随机性主要体现在两个方面：（1）训练每棵树时，从全部训练样本中选取一个子集进行训练（即bootstrap取样）。

用剩余的数据进行评测，评估其误差；（2）在每个节点，随机选取所有特征的一个子集，用来计算最佳分割方式。

随机森林的主要优点：（1）在大的、高维数据训练时，不容易出现过拟合而且速度较快；（2）测试时速度很快；（3）对训练数据中的噪声和错误鲁棒。

MATLAB随机森林分类器（Random Forest）Factor = TreeBagger(nTree, train_data, train_label);[Predict_label,Scores] = predict(Factor, test_data);scores是语义向量(概率输出)。

实验中nTree = 500。