Opencv2.4.9源码分析——Random Trees.docVIP

Opencv2.4.9源码分析——Random Trees 一、原理 随机森林（Random Forest）的思想最早是由Ho于1995年首次提出，后来Breiman完整系统的发展了该算法，并命名为随机森林，而且他和他的博士学生兼同事Cutler把Random Forest注册成了商标，这可能也是OpenCV把该算法命名为Random Trees的原因吧。 一片森林是由许多棵树木组成，森林中的每棵树可以说是彼此不相关，也就是说每棵树木的生长完全是由自身条件决定的，只有保持森林的多样性，森林才能更好的生长下去。随机森林算法与真实的森林相类似，它是由许多决策树组成，每棵决策树之间是不相关的。而随机森林算法的独特性就体现在“随机”这两个字上：通过随机抽取得到不同的样本来构建每棵决策树；决策树每个节点的最佳分叉属性是从由随机得到的特征属性集合中选取。下面就详细介绍这两次随机过程。 虽然在生成每棵决策树的时候，使用的是相同的参数，但使用的是不同的训练集合，这些训练集合是从全体训练样本中随机得到的，这一过程称之为bootstrap过程，得到的随机子集称之为bootstrap集合，而在bootstrap集合的基础上聚集得到的学习模型的过程称之为Bagging (Bootstrap aggregating)，那些不在bootstrap集合中的样本称之为OOB（Out Of Bag）。Bootstrap过程为：从全部N个样本中，有放回的随机抽取S次（在Opencv中，S=N），由于是有放回的抽取，所以肯定会出现同一个样本被抽取多次的现象，因此即使S=N，也会存在OOB。我们可以计算OOB样本所占比率：每个样本被抽取的概率为1/N，未被抽取的概率为(1－1/N)，抽取S次仍然没有被抽到的概率就为(1－1/N)S，如果S和N都趋于无穷大，则(1－1/N)S≈e－1＝0.368，即OOB样本所占全部样本约为36.8%，被抽取到的样本为63.2%。随机森林中的每棵决策树的bootstrap集合是不完全相同的，因此每棵决策树的OOB集合也是不完全相同的，所以对于训练集合中的某个样本来说，它可能属于决策树Ti的bootstrap集合，而属于决策树Tj的OOB集合。 因为在生成每棵决策树之前，都要进行bootstrap过程，而每次bootstrap过程所得到的bootstrap集合都会不同，所以保证了每棵决策树的不相关以及不相同。 为了进一步保证决策树的多样性，Breiman又提出了第二个随机性。一般的决策树是在全部特征属性中进行计算，从而得到最佳分叉属性，决策树的节点依据该属性进行分叉。而随机森林的决策树的最佳分叉属性是在一个特征属性随机子集内进行计算得到的。在全部p个特征属性中，随机选择q个特征属性，对于分类问题，q可以为p的平方根，对于回归问题，q可以为p的三分之一。对于随机森林中的所有决策树，随机子集内的特征属性的数量q是固定不变的，但不同的决策树，这q个特征属性是不同，而对于同一棵决策树，它的全部节点应用的是同一个随机子集。另外由于q远小于p，所以构建决策树时无需剪枝。 以上内容是在训练过程中，随机森林与其他基于决策树算法的不同之处。而在预测过程中，方法基本相同，预测样本作用于所有的决策树，对于分类问题，利用投票的方式，最多得票数的分类结果即为预测样本的分类，对于回归问题，所有决策树结果的平均值即为预测值。 再回到前面的训练过程中，为什么我们要使用Bagging方法？这是因为使用Bagging方法可以减小训练过程中的噪声和偏差，并且更重要的是，它还可以评估预测的误差和衡量特征属性的重要程度。 常用的评估机器学习算法的预测误差方法是交叉验证法，但该方法费时。而Bagging方法不需要交叉验证法，我们可以计算OOB误差，即利用那些36.8%的OOB样本来评估预测误差。已经得到证明，OOB误差是可以代替bootstrap集合误差的，并且其结果近似于交叉验证。OOB误差的另一个特点是它的计算是在训练的过程中同步得到的，即每得到一棵决策树，我们就可以根据该决策树来调整由前面的决策树得到的OOB误差。对于分类问题，它的OOB误差计算的方法和步骤为： ◆构建生成了决策树Tk，k=1, 2, …, K ①用Tk预测Tk的OOB样本的分类结果 ②更新所有训练样本的OOB预测分类结果的次数（如样本xi是T1的OOB样本，则它有一个预测结果，而它是T2的bootstrap集合内的样本，则此时它没有预测结果） ③对所有样本，把每个样本的预测次数最多的分类作为该样本在Tk时的预测结果 ④统计所有训练样本中预测错误的数量 ⑤该数量除以Tk的OOB样本的数量作为Tk时的OOB误差 对于回归问题，它的OOB误差计算的方法和步骤为： ◆构建