熟悉算法--随机森林 有更新!

  |   0 评论   |   218 浏览

    随机森林算法原理(一)

    随机森林是用随机的方式建立一个森林,森林里面有很多的决策树组成,随机森林的每一棵决策树之间是没有关联的。在得到森林之后,当有一个新的输入样本进入的时候,就让森林中的每一棵决策树分别进行一下判断,看看这个样本应该属于哪一类,然后看看哪一类被选择最多,就预测这个样本为那一类。
    在建立每一棵决策树的过程中,有两点需要注意采样与完全分裂。首先是两个随机采样的过程,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

    评论

    发表评论

    validate