学校编码 :10384 分类号密级 学号 :23020101153007 UDC 硕士学位论文 基于云的分布式机器学习框架 Cloud Based Distributed Machine Learning 蒋文瑞 指导教师姓名 : 倪子伟副教授 专 业名称 : 计算机技术 论文提交日期 :2013 年 论文答辩时间 :2013 年 学位授予日期 :2013 年 月 月 月 答辩委员会主席 : 评阅人 : 2013 年月 IV
厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下, 独立完成的研究成果 本人在论 文写作中参考其他个人或集体已经发表的研究成果, 均在文中以适当方式明确标 明, 并符合法律规范和 厦门大学研究生学术活动规范 ( 试行 ) 另外, 该学位论文为 ( ) 课题 ( 组 ) 的研究 成果, 获得 ( ) 课题 ( 组 ) 经费或实验室的资助, 在 ( ) 实验室完成 ( 请在以上括号内填写课题或课题组负责人或 实验室名称, 未有此项声明内容的, 可以不作特别声明 ) 声明人 ( 签名 ): 年 月 日
厦门大学学位论文著作权使用声明 本人同意厦门大学根据 中华人民共和国学位条例暂行实施办法 等规定保 留和使用此学位论文, 并向主管部门或其指定机构送交学位论文 ( 包括纸质版和 电子版 ), 允许学位论文进入厦门大学图书馆及其数据库被查阅 借阅 本人同 意厦门大学将学位论文加入全国博士 硕士学位论文共建单位数据库进行检索, 将学位论文的标题和摘要汇编出版, 采用影印 缩印或者其它方式合理复制学位论文 本学位论文属于 : ( )1. 经厦门大学保密委员会审查核定的保密学位论文, 于年月日解密, 解密后适用上述授权 ( )2. 不保密, 适用上述授权 ( 请在以上相应括号内打 或填上相应内容 保密学位论文应是已经厦门大学保密委员会审定过的学位论文, 未经厦门大学保密委员会审定的学位论文均为公开学位论文 此声明栏不填写的, 默认为公开学位论文, 均适用上述授权 ) 声明人 ( 签名 ): 年月日
摘要 摘要 如今, 数据挖掘在生活中也扮演着越来越重要的角色, 不管是公共事业还是私人行业 银行业, 保险业, 医疗业, 零售业大量的使用数据挖掘来发掘金融 欺诈, 评估金融风险, 减少成本, 加强研究, 增加销售额等等 然而激增的数据为传统的数据挖掘方式提出了严重的挑战 商业巨头 Google, Yahoo 和 Amazon 需要浏览 TB 与 PB 级的数据来发掘哪些网站是最有吸引力的, 哪些书籍是最受欢迎的, 哪些广告应该呈现给浏览者 传统的工具面对这些情形越来越显无能为力 在这样的背景下,Google 提出了 MapReduce 处理模型,Doug Cutting 基于此开发了开源系统 Hadoop,CMU 提出了 GraphLab 处理模型 这些模型与框架能有效地处理海量数据 然而单纯的这种模型与框架并不能直接用于数据的分析 在这样的背景下, 本文提出 CB-DML( 基于云的分布式数据挖掘 ) 模型, 利用 MapReduce 和 GraphLab 强大的并行机制, 并结合经典的数据挖掘算法, 提供可扩展的机器学习能力, 从海量数据中挖掘高价值量的重要信息 本文事先充分研究了机器学习算法的可并行性, 并行方式及并行策略 并研究了 Mapreduce 源代码, 框架并行特性, 使用场景及框架本身的性能优化策略 最终实现了基于云的分布式机器学习框架 CB-DML, 提供 6 大类并行机器学习算法 : 聚类 分类 线性回归 统计 图处理 相似项挖掘 部分机器学习算法在并行化之前, 亦做了相关的改进与优化 CB-DML 最终在自建的分布式集群上测试通过, 性能表现优越, 与此同时, 框架最终还应用于实际的工业场景 时间序列分析, 并表现出了优良的性能 关键词 : 机器学习, MapReduce, GraphLab,CB-DML I
Abstract Abstract Today, Data mining is becoming increasingly common in both the private and public sectors. Industries such as banking, insurance, medicine, and retailing commonly use data mining to detect fraud, assess risk, reduce costs, enhance research, and increase sales. The exponential growth of data first presents challenges to traditional data mining tools. Businesses such as Google, Yahoo and Amazon need to go through terabytes and petabytes of data to figure out which websites were popular, what books are in demand, and what kinds of ads appeal to people. Existing tools were becoming inadequate to process such large data sets. Then Google was the first to publicize MapReduce, Doug Cutting developed an open source version of it called Hadoop and CMU developed GraphLab after then System they had used to scale their data processing needs. In this backgraoud, we propose CB-DML(Cloud based- Distributed Machine Learning) model, a scalable machine learning platform Leveraging the power of MapReduce and GraphLab. It gives scalable parallel machine learning services, making large data sets not a barrier any more. We researched parallelism, parallel way and strategies of the ML algorithms. Also researched MapReduce source code, parallel features of the framework and performance optimization strategy of the framework itself. CB-DML was realized ultimately, giving parallel machine learning algorithms like: clustering, classification, regression, statistical, graph processing, similarity mining. Part of the machine learning algorithms were improved and optimized before parallelization. CB-DML was tested giving perfect performance on our own cluster. At the same time, the model was applied to actual industrial scene - time series analysis, and exhibited excellent performance. Key Words: Machine Learning, MapReduce, GraphLab, CB-DML III
目录 目 录 摘要... I Abstract... III 第一章概述... 1 1.1 研究背景 数据挖掘与工业应用... 1 1.2 研究现状... 2 1.3 课题研究目的及意义... 4 1.4 本文主要工作及文章结构... 6 第二章 CB-DML 总体设计架构图及设计原则... 9 2.1 CB-DML 整体架构图... 9 2.2 CB-DML 功能模块... 10 2.3 CB-DML 设计原则... 10 第三章分布式框架相关理论... 13 3.1 MapReduce 概述... 13 3.2 GraphLab... 16 第四章机器学习算法详述... 21 4.1 CB-DML 算法选取依据... 21 4.2 所选算法详述... 22 第五章分布式机器学习算法设计与实现... 27 5.1 并行化 K-means... 27 5.2 并行 C45... 33 5.3 并行朴素贝叶斯... 35 5.4 并行 KNN... 37 5.5 并行 TF-IDF... 38 5.6 并行 PageRank... 41 5.7 并行相似性挖掘系统... 42 V
目 录 5.8 并行回归模型... 51 第六章 CB-DML 处理大数据性能测试... 59 6.1 实验环境 Hadoop 集群搭建... 59 6.2 集群性能调优... 65 6.3 性能测试... 68 第七章总结与展望... 79 7.1 工作总结... 79 7.2 未来工作展望... 79 参考文献... 83 攻读硕士学位期间发表论文及科研情况... 89 致谢... 91 VI
Contents Contents Abstract(CH)... I Abstract(EN)... II Chapter 1 Introduction... 1 1.1 Research Backgroud Data Mining and Industrial Application... 1 1.2 Research Status... 2 1.3 Research Purpose and Significance... 4 1.4 Main Research Contents and Outline... 6 Chapter 2 CB-DML Architecture and Design Principles... 9 2.1 CB-DML Architecture... 9 2.2 CB-DML Function Module... 10 2.3 CB-DML Design Principles... 10 Chapter 3 Distributed Framework Theory... 13 3.1 MapReduce... 13 3.2 GraphLab... 16 Chapter 4 Machine Learning Algorithms Overview... 21 4.1 CB-DML Algorithms Selection... 21 4.2 Introduction to the Selected Algorithms... 22 Chapter 5 Distributed ML Algorithm Design and Implementation... 27 5.1 Parallel K-means... 27 5.2 Parallel C45... 33 5.3 Parallel Naïve Bayes... 35 5.4 Parallel KNN... 37 5.5 Parallel TF-IDF... 38 5.6 Parallel PageRank... 41 5.7 Parallel Similarity Mining System... 42 5.8 Parallel Regression Model... 51 VII
Contents Chapter 6 CB-DML - Performance... 59 6.1 Enviroment Hadoop Cluster Constrution... 59 6.2 Cluster Performance Tuning... 65 6.3 Performance Testing... 68 Chapter 7 Conclusion and Prospect... 79 7.1 Conclusion... 79 7.2 Prospects of Future... 79 Reference... 83 Publications... 89 Acknowledgements... 91 VIII
第一章概述 第一章概述 1.1 研究背景 数据挖掘与工业应用 数据挖掘在工业与生活中扮演着越来越重要的角色, 不管是公共事业还是私 人行业 银行业, 保险业, 医疗业, 零售业大量的使用数据挖掘来发掘金融欺 诈, 评估金融风险, 减少成本, 加强研究, 增加销售额等等 数据挖掘诞生由来已久, 图 1-1 揭示了它的诞生 图 1-1 数据挖掘的诞生 数据挖掘在工业应用中的统计如图 1-2 所示 : 1
基于云的分布式机器学习框架 CRM/ consumer analytics Banking Health care/ HR Fraud Detection Direct Marketing/ Fundraising Finance Telecom / Cable Science Insurance Advertising Education Web usage mining Credit Scoring Retail Medical/ Pharma Manufacturing e-commerce Social Networks Search / Web content mining Government/Military Biotech/Genomics Investment / Stocks Entertainment/ Music Security / Anti-terrorism Travel / Hospitality Social Policy/Survey analysis Junk email / Anti-spam Other 图 1-2 数据挖掘在工业中应用情况 在工商业中, 数据的存在形式是丰富多样的, 其大小更是呈现飞速增长, 截 至 2011 平均的数据吞吐量已按照 PB 级计算 1.2 研究现状 0.0% 5.0% 10.0% 15.0% 20.0% 25.0% 30.0% 数据挖掘在工业中扮演者举足轻重的角色, 然而, 激增的数据为传统的数据 挖掘方式提出了严重的挑战, 如今, 数据无处不在, 而其增长速度更是超出人 们的想象 商业巨头 Google, Yahoo 和 Amazon 需要浏览 TB 与 PB 级的数据来 发掘哪些网站是最有吸引力的, 哪些书籍是最受欢迎的, 哪些广告应该呈现给浏 览者 传统的工具面对这些情形越来越显无能为力 图 1-3 揭示 2010 与 2011 待分析数据的增长情况 : 2
第一章概述 图 1-3 2010 与 2011 数据增长统计 在这样的背景下, 需要一些有力的工具或平台来存储 分析与日俱增的大数 据, 并且这些框架还必须要满足低成本的要求, 基于这样的一个需求, 接下来本 文介绍分布式框架的研究现状, 着重介绍 Google Mapreduce [1], Apache Hadoop [2] 以及 CMU Graphlab [3] 等平台的研究与诞生 MapReduce 处理模型是由 Google 提出 [4], 基于此基础,Doug Cutting 此开发 了开源系统 Hadoop [5] 这种模型与框架能有效地处理海量数据 Hadoop 的两 大核心构件是 HDFS [6] 与 MapReduce, 其中 HDFS [7] 用于大数据的分布式存储, 其具有极强的低成本性和可扩展性, 能完美的满足云的需求, 而 MapReduce 则 用于数据的高效 实时分析, 在保证能应对大数据的前提下, 依然保持着运算高 效率 然而 MapReduce 和 Hadoop 并非是万能的, 这也就引出了本文所用的 GraphLab 平台 : MapReduce 适用于数据任务之间独立性强的计算, 对于那些富含迭代的运算 或者数据任务之间有交互的计算不适合 这个来源于 Mapreduce 的信息交互方式 是 I/O 方式, 每轮迭代之间需要走 I/O 来传递信息, 这样的开销是比较大的 由 于大多数的机器学习问题包含迭代问题, 因此 Mapreduce 在处理迭代问题时并不 能表现出完美地性能, 尤其是对于图问题,Mapreduce 表现出来的性能很一般 3
基于云的分布式机器学习框架 为解决机器学习的流处理,Google 提出了 Pregel 框架 [8],Pregel 是严格的 BSP 模型, 采用 计算 - 通信 - 同步 的模式完成机器学习的数据同步和算法迭代 Goolge 曾称其 80% 的程序使用 MapReduce 完成,20% 的程序使用 Pregel 实现 然后它的最大不方便之处正是在于不开源 那么我们必须继续探寻其他适用于迭代运算的框架 幸运的是,2010 年,CMU 的 Select 实验室提出了 GraphLab 框架,GraphLab 是面向机器学习的流处理并行框架 [1] 其对自然图的处理, 做出了显著的改进. 这 种框架有效弥补了 Mapreduce 框架的不足之处, 能有效处理迭代问题, 其信息传递方式是信息共享, 这种框架实现了分布式共享内存, 故而在处理迭代问题和任务间交互性强的计算时, 性能表现优越 因而他适合于机器学习的并行化, 更适于处理大图问题 在处理大图问题时, 其对图有一套有效的图分割 - 分布式存储机制然而光有这些分布式框架还不行, 还需要将这些强大的分布式框架与传统 经典的数据挖掘算法相结合, 才能诞生一个有效应对大数据的利器 目前的一个研究现状是中国移动研究院的大云平台 :BC-PDM BC-PDM ( 基于大云的并行数据挖掘 ) 为云存储与分布式计算框架, 提供 SaaS 服务, 高效的存储 处理海量数据 包含常见 ETL 和数据挖掘算法 平台采用 MapReduce,Hadoop,HugeTable 等大规模分布式处理技术 1.3 课题研究目的及意义 如今大数据无处不在, 各种科学领域, 社交网络, 互联网, 工业应用, 商业 中都会产生大量的数据 [9]. 而且大数据中也蕴藏着不可低估的价值, 这一点已是不可否认的事实既然大数据中蕴含着如此巨大的价值, 那么一个能有效存储 分析大数据的平台也就迫在眉睫, 但是仍有人提出采用高性能服务器的方案来处理大数据, 高性能服务器相比云的方案有一个很大好处 : 不用部署分布式环境, 不必将原有的程序额外花时间扩展成分布式程序 那么它的实际性能如何呢, 以下是高性能服务器与集群运行能力的一个对比 : 4
第一章概述 Time: 1600 Unix Servers 1400 1200 1000 800 600 400 200 0 BC-PDM(10 times data) BC-PDM(100 times data) 图 1-4 高性能服务器与集群运算能力对比图 1-4 中, 每种算法最左边为 Unix 高性能服务器运行时间, 中间为集群处理 10 倍数据量时的时间, 最右边为集群处理 100 倍数据时的时间 处理算法包括连接, 统计, 采样, 决策树, 聚类等算法, 从图中可以看出, 集群的处理性能优越于高性能服务器 那么这两种架构的成本又如何呢? 表 1-1 对比了二者的成本 5
Degree papers are in the Xiamen University Electronic Theses and Dissertations Database. Full texts are available in the following ways: 1. If your library is a CALIS member libraries, please log on http://etd.calis.edu.cn/ and submit requests online, or consult the interlibrary loan department in your library. 2. For users of non-calis member libraries, please mail to etd@xmu.edu.cn for delivery details.