面向大数据的渐进式集成学习方法与分布式算法研究

One big challenge in big data analysis is the scalability of distributed analysis algorithms. To solve this problem, this project proposal proposes an asymptotic ensemble learning strategy that builds an ensemble learning model in steps and each step only uses a small portion of big data to compute a subset of component models distributedly. The final model is the ensemble of the subsets of component models learnt in all steps. This learning strategy can significantly increase the ability of distributed big data analysis on a platform with memory and computing constraints and scale to terabytes data in learning classification models. The objectives of this project are to study new theory and methods for research of distributed algorithms scalable to big data and develop a distributed framework for implementation of asymptotic ensemble learning algorithms. The research tasks include: (1) studying the asymptotic ensemble learning method and the statistical theory based on partition of a big data set by random sample subsets. (2) developing sampling methods of subsets of random samples in big data partition and distributed algorithms. (3) developing a distributed framework of asymptotic ensemble learning, asymptotic distributed random forests algorithms and MapReduce implementations. (4) applying asymptotic distributed random forests algorithms to smart grid big data for classification and prediction. The expected outcomes of this project will set up a theoretical foundation of asymptotic ensemble learning and provide an algorithm framework for development of asymptotic distributed ensemble learning algorithms. The outcomes will also provide new sacalable random forests technology for applications of big data classification and prediction. The research results will promote technology innovation in big data area and big data applications in China.

大数据分析算法研究的挑战之一是分布式算法的数据可扩展性。针对这一挑战，本项目提出渐进式集成学习策略，在内存和计算资源有限的条件下，通过采用部分数据逐步分批计算来建立集成学习模型，提高分布式算法处理大数据的能力，使之能解决TB级大数据分类问题。本项目的目标是，针对大数据高可扩展分布式分析算法的研究，提出新的理论、方法、框架和实现技术。主要研究内容包括：（1）基于随机样本子集划分的渐进式集成学习方法和统计原理；（2）大数据随机样本子集划分的抽样方法和分布式算法；（3）渐进式集成学习分布式算法框架、渐进式随机森林算法和MapReduce实现；（4）渐进式集成学习算法在智能电网大数据分类和预测中应用。本项目的预期研究成果将为渐进式集成学习方法提供理论基础，为基于渐进式集成学习的分布式算法研究提供算法框架，为大数据分类与预测应用提供高可扩展的随机森林分析技术，促进我国大数据领域的技术创新和产业应用。

大数据的处理与分析需要运行多种迭代算法，算法运行依赖内存计算（in-memory computing），业界普遍应用的Spark 技术基于此需求开发，弥补了MapReduce 的缺陷。但是，当数据超过内存时，迭代算法变得低效或无法运行，因此，内存成为大数据计算的瓶颈。采用样本的近似计算（approximate computing）是提高大数据分析能力的有效策略。但是，从分布式大数据文件中抽取随机样本，特别是抽取许多小的随机样本集进行大数据近似分析 (如Michael Jordan等提出的Bag of Little Bootstraps分析方法)，由于读磁盘和节点间通信的开销过高，在线抽取随机样本的时间过长、效率低，成为大数据近似计算的瓶颈。这两个瓶颈降低了当前大数据技术的计算能力，以及对数据的扩展性。.本项目针对上述两个瓶颈进行了研究，主要内容包括：支持大数据在线抽样和近似计算的分布式大数据划分模型；HDFS大数据文件与大数据划分模型的转换算法；基于大数据划分模型的分布式近似计算框架；聚类与分类算法以及智能电网大数据的应用。.本项目取得如下重要成果：（1）提出了随机样本划分（RSP）的分布式数据模型及其理论证明，将大数据在线抽样的时间从小时缩短到秒级，有效地支持了大数据近似计算；（2）开发了高效的HDFS大数据文件向RSP数据模型的转换算法，实现了10TB大数据的转换能力；（3）提出了基于RSP模型的大数据跨数据中心处理与分析的理论和方法；（4）提出并验证了逼近式集成学习框架，提高了小计算集群分析大数据的能力，近似计算能力扩展到10TB以上的大数据；(5) 研究开发了新的聚类和分类算法和软件包，应用于智能电网大数据，取得了显著的成果。.本项目取得了如下技术突破：（1）突破了内存计算的内存瓶颈，使不可计算的任务可以计算；（2）RSP技术实现了跨数据中心大数据的直接计算；（3）突破了分布式大数据文件在线抽样的瓶颈；（4）实现了复杂串行算法的分布式运行，拓展了大数据分析的算法库。这些技术创新为开发后Spark时代的大数据技术奠定了基础，具有广泛的应用前景，同时开辟了大数据近似计算理论研究的新方向。