大数据环境下增量式迭代计算框架的研究与优化

The fixed point iterative algorithms widely exist in the area of data mining and machine learning, which have been applied in many fields, such as social network analysis, high-performance computing and recommended system. In big data environment with time-varying, the data changes very fast. It will leads to a waste of computing resources and the performance loss that the whole iterative algorithm will be run again whenever data is changed. We study the incremental iterative method, use the relations between the adding or deleting data and the original iteration results. Proposed the incremental iterative computing model includes positive incremental computing process and negative incremental computing process. To avoid repeatedly computation on complete data and improve the efficiency of iterative computing in big data environment. On the basis of this, we consider the optimization method of incremental iterative computing frame according to the characteristics of the incremental iterative computing method. To further improve the performance of iterative computing, we study how to optimize the framework from two perspective, the initial point set in iterative computing and load balancing. At last, we construct an incremental iterative computing framework by extending the HaLoop framework based on incremental iterative computing model and optimization method. Also, we test the use of the practical situation on this framework from the application of a real e-commerce need, to verify the topic of our research.

不动点迭代广泛存在于数据挖掘和机器学习算法中，这些算法已应用到诸如社会网络分析、高性能计算、推荐系统、搜索引擎、模式识别等诸多领域中。在大数据时变性环境下，由于数据的快速变化，每当数据发生改变整个迭代算法也需要重新运行，这将会导致大量的运算资源浪费和性能损失。本课题拟利用新增或删减数据和原始迭代结果数据关系研究增量式迭代计算方法，提出包括正增量与负增量计算过程的增量式迭代计算模型。避免全集数据的反复重新计算，大幅度的提高大数据环境下迭代计算的效率。在此基础上考虑增量式迭代计算框架优化方法的研究，根据增量式迭代计算方法的特点，从迭代计算本身的初始点设置及负载均衡角度研究如何对其进行优化，从而进一步提高迭代计算性能。最后，在增量式迭代计算模型与优化方法的基础上，基于HaLoop迭代计算框架进行扩展构建一个增量式的迭代计算框架，并以真实的电子商务需求测试该框架的实际应用情况，以验证本课题的研究。

在大数据的背景下, 随着数据挖掘、机器学习等相关领域的发展, 越来越多的迭代计算应用诸多领域中。然而在大数据背景下, 迭代算法也出现诸多不适用性。低价值密度导致多次迭代计算的输入数据既重叠又会有所差异，迭代结果无法复用；时变性在数据产生变化后原始数据的迭代结果将不再适用, 整个迭代算法也需要在数据全集上重新运行, 这将浪费大量的时间和资源；同时，大数据迭代分析算法期望作用在全集数据而非局部数据之上，当局部数据进行汇总后，需要在全集数据上进行重新迭代计算，严重影响了迭代计算的效率。.针对大数据环境下的迭代计算框架及优化方法的研究，本课题将基于现有迭代计算的研究成果，以基于Spark计算模型框架为基础，展开了研究工作。具体研究包括：提出一个可复用的且适用于大部分算法的迭代计算模型，在不损失迭代精度的前提下利用原始的迭代结果和数据的变化量获得新的迭代结果，采用理论证明以及实验分析的方法, 证明了可复用迭代计算模型的正确性和性能优势；其次，迭代算法的特性由其迭代变量所表征，迭代变量的选择对于迭代算法的收敛速度起到至关紧要的作用。结合可复用迭代计算模型,提出一种迭代变量初始点选择算法, 以优化迭代计算的效率；再次，异构的分布式计算环境中, 由于节点计算能力的差异, 并行性难以保证, 节点间同步时会相互等待,浪费计算资源, 严重影响计算性能。从负载均衡的角度出发, 提出了基于任务分发和调整的负载均衡算法, 提高节点并行性, 进而提高迭代计算的性能；最后，提出了基于Spark框架的归并迭代计算模型以及归并迭代损失弥补模型和函数，归并迭代计算模型在不损失迭代结果精度的情况下利用现有的迭代数据分布情况对迭代数据进行区内迭代，并合并区内迭代结果以得到最终迭代结果。