改进的并行随机森林算法及其包外估计

Improved parallel random forest and its out＿of＿bag estimator

传统的包外估计记录全局数据与树之间的对应关系来测算泛化误差。然而基于MapReduce机制的并行随机森林算法(MR_RF)是建立在多个互不可见的分块数据上。对此分析MR_RF与RF的区别,设计了一个新的适用于MR_RF的包外泛化误差估计方法。主要将测算限定在数据块内,最终森林的泛化误差估计取块结果的平均。实验结果表明,新的包外估计方法与交叉验证在默认分块上的结果近似,却随着分块的增加出现偏差,对此分析了可能的原因,并给出选择集成方案思想,且分块大小与分类准确率成反比,与分类速率成正比。

Traditional out_of _ bag（ OOB） estimator needs to record the relationship of global data and the trees so as to estimate generation error. However parallel random forest based on MapReduce algorithm（ MR _RF） is built on blocks that independently with each other. This paper analyzed the difference between the MR_RF and random forest,and designed a new oob estimator that was applicable to estimate MR_RF＇s generalization error. Its key idea was putting the OOB calculator just into that particular block and using the average result of all blocks as the final OOB estimator result. Experiments show that in the case of the default partition,the new method is as effective as cross validation. However it shows deviation as the blocks increase. This paper analyzed the reason and gave the idea of selective ensemble scheme. Meanwhile,the block size is proportional to the classification rate but inversely proportional to the classification accuracy. When dealing with large data classification problems,it is necessary to adjust the block size to take the compromise between accuracy and rate.