面向海量超高维数据的随机森林算法理论及优化方法研究

Thousands upon thousands of features of ultra-high-dimensional large scale data become a new challenge to classification algorithms. Currently, the accuracy of most classification algorithms is low for ultra-high-dimensional data, and most algorithms cannot process large scale data. Many research works have shown that the random forest algorithm outperforms other classification algorithms in high dimensional data. But it still has the bottleneck to process TB scale ultra-high-dimensional data. This project will further improve the random forest theory and optimize the algorithm to process bigger data based on our preliminary works. The major tasks of this project include: 1) Prove that the accuracy of the weighted subspace sampling random forest algorithm is higher than Breiman's approach in ultra-high-dimensional data. The proof will enrich the theories of random forest algorithms. 2) For the problems of complex data, design a hybrid random forest algorithm, which builds multiple decision trees simultaneously with different decition tree algorithms; and design an interactive random forest optimization method, which reduces the shortcomings of random forests built with a single decision tree algorithm. 3) For the problems of large scale data, design a MapReduce scalable random forest algorithm and experimental platform, which can build classification models for TB scale data.The expected delivables will contribute new theories and tools to solve large scale data classification problems.

具有成千上万个属性的大规模超高维数据给现有分类算法带来前所未有的挑战，目前常用的算法对超高维数据分类的精度低，无法处理大数据。许多研究结果表明，随机森林分类算法处理高维数据优于其它分类算法，但用于TB级规模超高维数据的分类建模还有很大瓶颈。本项目基于前期的研究成果，进一步从理论和算法优化两个方面深入研究大数据分类的随机森林技术。研究内容包括：1）从理论上证明在超高维数据条件下，属性加权子空间抽样随机森林算法的精度不低于Breiman随机森林算法的精度，进一步丰富随机森林算法的理论；2）针对数据属性繁杂问题，研究多种决策树算法同时运用的混合随机森林优化方法和动态交互式随机森林优化方法，弥补目前采用单一决策树算法的缺陷； 3）针对数据规模大问题，开发基于MapReduce编程模型的高可扩展随机森林算法和实验系统，突破TB级大数据分类的技术瓶颈。预期成果将为大数据分类提供新的理论及应用工具。

随机森林（random forests）是一种有监督的集成学习分类技术，其分类模型由一组决策树分类器组成，模型对数据的分类是通过单个决策树的分类结果进行集体投票来决定最终结果。多个不同的对比研究表明，对于高维复杂数据，随机森林的综合性能指标，如算法效率、分类精度等，明显优于其他单分类器和集成分类器。因此, 本项目将系统地从理论和算法优化两个方面深入研究并完善大数据分类的随机森林技术。重点研究内容和执行情况如下：1）针对超高为高维数据给随机森林算法带来的一系列性能下降的问题，我们创新地提出了一系列的解决方法，包括提出用p-value评估方法，找出重要的特征子集，我们提出了eQRF算法；提出多层特征抽样的改良方法ssRF，通过p-value可以找到可以区分特征属性信息含量的断裂点，计算出不同信息含量特征属性的软子空间权重，我们可以按比例对不同子空间权重的特征属性子集进行抽样。ssRF算法要比eQRF算法的准确性更好，相关的成果已经连续两年在PAKDD会议上发表。2）针对数据属性繁杂问题，研究多种决策树算法同时运用的混合随机森林优化方法和动态交互式随机森林优化方法，弥补目前采用单一决策树算法的缺陷；我们开发了一套完整的交互式可视化系统，申请了相关的专利和软件著作权 3）随机森林在实际问题中的使用，我们提出了多种利用随机森林算法解决基因数据分类和SNPs特征提取的方法，包括具有引导性正则约束的随机森林方法和基于双层质量提高的随机森林算法。相关论文已在国外高水平期刊上发表。我们还尝试使用随机森林算法解决湄公河水位预测的实际问题，取得了较好的成果。本项目取得的成果已经为随机森林大数据分析提供新的理论及应用工具。