熟悉算法 -- 随机森林

随机森林算法原理(一)：

随机森林是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类，然后看看哪一类被选择最多，就预测这个样本为那一类。
在建立每一棵决策树的过程中，有两点需要注意采样与完全分裂。首先是两个随机采样的过程，random forest 对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为 N 个，那么采样的样本也为 N 个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现 over-fitting。然后进行列采样，从 M 个 feature 中，选择 m 个（m << M）。之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现 over-fitting，当层数较低的时候。

随机森林原理和步骤（二）:

随机森林，指的是利用多棵树对样本进行训练并预测的一种分类器。简单来说，随机森林就是由多棵 CART（Classification And Regression Tree）构成的。对于每棵树，它们使用的训练集是从总的训练集中有放回采样出来的，这意味着，总的训练集中的有些样本可能多次出现在一棵树的训练集中，也可能从未出现在一棵树的训练集中。在训练每棵树的节点时，使用的特征是从所有特征中按照一定比例随机地无放回的抽取的，根据 Leo Breiman 的建议，假设总的特征数量为 M，这个比例可以是 sqrt(M),1/2sqrt(M),2sqrt(M)。
1: 随机森林的 训练过程 如下：
(1)给定训练集 S，测试集 T，特征维数 F。确定参数：使用到的 CART 的数量 t，每棵树的深度 d，每个节点使用到的特征数量 f，终止条件：节点上最少样本数 s，节点上最少的信息增益 m;
对于第 1-t 棵树 i：
(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 都被训练过。

2:随机森林的 预测过程 如下：
对于第 1-t 棵树 i：
(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值越小，在寻找最佳的分类特征和阈值时。
1：评判标准为：argmax（Gini-GiniLeft-GiniRight），即寻找最佳的特征 f 和阈值 th，使得当前节点的 Gini 值减去左子节点的 Gini 和右子节点的 Gini 值最大。
2：对于回归问题，相对更加简单，直接使用 argmax(Var-VarLeft-VarRight)作为评判标准，即当前节点训练集的方差 Var 减去减去左子节点的方差 VarLeft 和右子节点的方差 VarRight 值最大。

Random Forest与Bagging的区别 在于：Bagging 每次生成决策树的时候从全部的属性 Attributes 里面选择，而 Random Forest 是随机从全部 Attributes 的集合里面生成一个大小固定的子集，相对而言需要的计算量更小一些。 == TODO bagging