文档介绍：随机森林
学****算法
根据以下算法而建造每棵树：
1. 用 N 来表示训练例子的个数，M表示变量的数目。
2. 我们会被告知一个数 m ，被用来决定当在一个节点上做决定时，会使用到多少个变量。m应小于M
3. 从N个训练案例ion 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的平板标准，,。
对于分类问题〔将某个样本划分到某一类〕，也就是离散变量问题，CART使用Gini值作为评判标准。定义为Gini=1-∑(P(i)*P(i)),P(i)为当前节点上数据集中第i类样本的比例。例如：分为2类，当前节点上有100个样本，属于第一类的样本有70个，属于第二类的样本有30个，那么Gini=1-×07-×03=，可以看出，类别分布越平均，Gini值越大，类分布越不均匀，Gini值越小。在寻找最正确的分类特征和阈值时，评判标准为：argmax〔Gini-GiniLeft-GiniRight〕，即寻找最正确的特征f和阈值th，使得当前节点的Gini值减去左子节点的Gini和右子节点的Gini值最大。
对于回归问题，相对更加简单，直接使用argmax(Var-VarLeft-VarRight)作为评判标准，即当前节点训练集的方差Var减去减去左子节点的方差VarLeft和右子节点的方差VarRight值最大。
有时现有的库无法满足要求，就需要自己设计一个分类器算法，这局部讲一下如何设计自己的随机森林分类器，代码实现就不贴了，因为在工作中用到了，因此比拟敏感。
首先，要有一个RandomForest类，里面保存整个树需要的一些参数，包括但不限于：训练样本数量、测试样本数量、特征维数、每个节点随机提取的特征维数、CART树的数量、树的最大深度、类别数量〔如果是分类问题〕、一些终止条件、指向所有树的指针，指向训练集和测试集的指针，指向训练集label的指针等。还要有一些函数，至少要有train和predict吧。train里面直接调用每棵树的train方法即可，predict同理，但要对每棵树的预测输出做处理，得到森林的预测输出。
 
其次，要有一个sample类，这个类可不是用来存储训练集和对应label的，这是因为，每棵树、每个节点都有自己的样本集和，如果你的存储每个样本集和的话，需要的内存实在是太过巨大了，假设样本数量为M，特征维数为N，那么整个训练集大小为M×N，而每棵树的每层都有这么多样本，树