LogoML：基于LOGO分布式计算框架与随机样本分区（RSP）数据模型的开放式机器学习库

《IEEE Transactions on Big Data》：LogoML: An Open Machine Learning Library for Distributed Big Data Analytics

　　

在MapReduce中实现分布式机器学习算法（distributed machine learning algorithms）面临三项挑战：迭代算法（iterative algorithms）执行效率低、数据可扩展性（data scalability）差，以及将复杂算法分解为Map和Reduce操作的刚性结构具有较高复杂度。最后一项挑战使许多有用的大数据分析算法在当前分布式系统中不可用。本文提出LogoML，一个用于分布式大数据分析的机器学习算法库。LogoML实现于局部操作与全局操作（Local Operation and Global Operation, LOGO）分布式计算框架和随机样本分区（Random Sample Partition, RSP）数据表示模型之上。与MapReduce算法不同，LogoML中的算法本质上是顺序算法（sequential algorithms）。借助LogoML，数据分析任务通过LOGO分布式计算框架中的两个核心操作完成。局部操作（Local Operation, LO）在多个节点或虚拟机上并行执行数据分析算法，以处理一组随机样本数据块并生成一组局部结果。全局操作（Global Operation, GO）执行集成算法（ensemble algorithm），将局部结果聚合为最终集成结果（final ensemble result）。通过创新性设计与实现，LogoML库在分布式大数据分析中表现出以下优点：由于顺序算法易于在LogoML中实现，因而具有丰富的算法；在执行迭代算法方面高效，并且可扩展至大数据；其开放结构（open structure）允许用户向库中添加新算法。LogoML算法的性能、效率和数据可扩展性通过合成数据集和真实数据集的实验结果得到验证。

研究背景与问题：随着产业界追求业务运营智能化以提高效率、降低成本并减少错误，数据集成、预处理、分析和模型构建已成为现代企业的重要业务流程。为处理大规模复杂业务数据，支持大数据分析的分布式计算平台在促进数据驱动的智能业务运营中发挥关键作用，典型系统包括Hadoop、Spark、Flink和Storm等。产业界对分布式数据分析平台的重要要求是具备丰富、易用、处理高效且可扩展至大数据的算法集合，并可服务于数据集成、预处理、特征工程、模型构建和可视化等任务。传统数据分析系统如R、Matlab、Weka、Smile和Sklearn虽提供大量数据处理与分析算法，但其算法为顺序实现，无法在并行与分布式计算环境中运行，因而不能处理大数据集。分布式大数据分析系统如Hadoop MapReduce和Spark也提供Mahout、MLlib等算法库，但可用数据分析算法非常有限；例如Mahout仅提供27种机器学习算法，Spark中的MLlib具有48种用于分类、回归、聚类和频繁模式挖掘的算法，而数据探索、数据集成、数据预处理、特征工程、自然语言处理（Natural Language Processing, NLP）和可视化等许多必要算法缺失。造成分布式系统缺乏必要分析算法的首要原因，是难以实现可在分布式大数据集上高效运行的分布式算法。MapReduce编程模型存在迭代算法执行效率低和数据可扩展性差的问题，并且将复杂算法分解为Map和Reduce操作具有较高复杂度，使复杂算法难以实现。为此，研究人员提出LogoML，一个面向分布式大数据分析的开放式机器学习库，旨在解决极大规模数据集分布式分析中的上述问题。

研究人员开展的研究、结论与意义：研究人员提出LogoML，其建立在随机样本分区（RSP）数据模型和局部操作与全局操作（LOGO）分布式计算框架两项新技术之上。RSP数据模型将分布式数据文件表示为RSP数据块文件集合，每个数据块均为该数据文件的随机样本，并可独立分析。LOGO计算框架采用非MapReduce计算范式，通过两个操作完成数据分析任务：局部操作（LO）在虚拟机上并行、独立地处理多个RSP数据块并生成局部估计；全局操作（GO）在主节点上执行集成算法，将局部估计聚合为最终结果。由于LO阶段去除节点间数据通信，LogoML算法可在集群上高效执行。LogoML具有三方面特点：无需将顺序算法改写为分布式版本即可高效执行迭代算法；GO仅需一次将局部结果从从节点传输至主节点，且集成算法无沉重迭代过程；开放架构允许新算法方便加入。研究人员在真实和合成数据集上测试LogoML算法，并与Spark分布式算法比较，结果表明LogoML算法产生更准确结果、效率更高且可扩展至大数据集。其意义在于面向商业领域常见的数TB级极大规模数据集分布式分析，弥补现有分布式大数据分析系统在此类任务中的不足。

关键技术方法（不超过250字）：研究人员采用随机样本分区（RSP）数据表示模型，将分布式数据文件表示为可独立分析的随机样本数据块；采用LOGO分布式计算框架，以局部操作（LO）并行执行顺序算法生成局部结果，以全局操作（GO）执行集成算法聚合局部结果；设计标准算子与数据格式转换模板，将Smile、scikit-learn等来源的顺序算法封装入LogoML；采用投票、加权投票、平均、加权平均、stacking、聚类再聚类及频繁项集挖掘（FIM）投票与支持度平均等集成方法；实验在单服务器与30节点Spark/YARN集群上开展，比较Smile、SparkML和SparkML-OS；实验数据包括真实数据集HIGGS、MNIST_PCA及两组合成数据集。

研究结果：小数据集评估：研究人员在HIGGS和MNIST_PCA两个真实数据集上使用14种算法（10种分类、4种聚类），比较LogoML、SparkML和Smile的执行时间、分类准确率和聚类纯度。结果表明LogoML方法效率最高，数据集越大、算法越复杂，LogoML执行越高效；LogoML分类模型准确率优于或等于其他两种方法，原因在于其采用集成学习（ensemble learning）构建模型；四种聚类算法的纯度在三种方法间非常接近，LogoML优势在于包含更多聚类算法且处理大数据集高效。SparkML迭代算法因MapReduce式实现存在较大数据通信开销，效率提升不显著；部分Smile算法因内存限制无法生成最终结果；SVM和RBF在单机上难以完整分析HIGGS，MNIST_PCA上SVM、RDA和QDA因仅适用于二类数据而无法使用。大数据集评估：研究人员使用第一组合成数据集DS1至DS20（100 GB至2 TB）评估监督与无监督算法，使用第二组DS29至DS38（50万至500万笔交易）评估FP-Growth生成近似频繁项集。结果表明SparkML算法受内存限制明显，接近内存上限时执行时间因节点间数据通信和内存与硬盘间换入换出开销而指数增长；LogoML和SparkML-OS仅处理5%数据，SparkML-OS执行时间随数据规模线性增加，而LogoML执行时间几乎不变，原因在于LogoML采用块级随机采样，较SparkML-OS的记录级采样更快；分类模型准确率上LogoML优于SparkML和SparkML-OS，聚类结果LogoML与SparkML相近而SparkML-OS稍差；LogoML频繁项集挖掘结果的召回率（recall）和精确率（precision）随数据规模增加而提高并趋近100%，总体均高于97%。数据可扩展性评估：研究人员使用DS20至DS28（2 TB至10 TB）评估三种分类算法和两种聚类算法，使用DS30至DS48（10⁷至10⁹笔交易）评估频繁项集挖掘算法。结果表明LogoML算法可高效处理TB级大数据并具有可扩展性，SparkML因内存限制无法运行，SparkML-OS需单独记录采样时间；LogoML采用非MapReduce计算范式，避免节点间数据通信开销，而SparkML-OS的MLlib算法为MapReduce分布式实现，消耗更多内存并存在通信开销；数据分析显示Spark MLlib六种算法通信开销占总执行时间比例显著，Bisecting K-means和FP-Growth在去除通信开销后分别减少72.3%和72.7%的总执行时间，平均约50%总执行时间可通过LogoML算法替代相应Spark MLlib算法而节省。

讨论与结论：研究人员总结LogoML在RSP数据表示模型和LOGO分布式计算框架支持下，相对于Spark MLlib和Mahout等分布式大数据分析机器学习算法库具有以下优点：计算高效，因其非MapReduce计算范式在执行迭代算法时显著减少数据通信和输入/输出（I/O）开销；可扩展至大数据，因其使用样本数据块而非整个数据集进行数据分析；算法丰富，因其使用顺序算法并行处理大规模数据集并开展分布式数据分析；具有开放架构，可向库中添加新算法。LogoML代表一种面向分布式数据分析和机器学习计算的新型算法库，针对TB级及以上极大规模数据集问题。当前研究人员正在探索将LogoML部署于多个集群以分析存储在地理分布式数据中心的大数据，同时也在探索和设计新的计算架构以使LogoML支持深度学习算法。

研究结论翻译：本文提出LogoML，一个面向分布式大数据分析的开放式数据分析与机器学习算法库。在RSP数据表示模型和LOGO分布式计算框架赋能下，LogoML库相对于Spark MLlib和Mahout等分布式大数据分析机器学习算法库具有以下优点：其计算高效，因为其非MapReduce计算范式在执行迭代算法时显著减少数据通信和I/O开销；其可扩展至大数据，因为其在数据分析中使用样本数据块而非整个数据集；其具有丰富的算法集合，因为其使用顺序算法并行处理大规模数据集并开展分布式数据分析；其具有开放架构，可向库中添加新算法。LogoML代表一种用于数据分析和机器学习分布式计算的新型算法库，解决了TB级及以上极大规模数据集问题。当前，研究人员正在探索将LogoML部署在多个集群中以分析存储在地理分布式数据中心的大数据。同时，研究人员也在探索和设计新的计算架构，以使LogoML支持深度学习算法。