基于MapReduce框架下的数据挖掘方法研究
2017-05-06 22:56杨震宇
中国高新技术企业 2017年4期
杨震宇
摘要：大规模数据处理分析工作，在单个处理节点上部署时往往会遇到机器性能局限所带来的计算瓶颈。如今，技术更加先进且成本低廉的分布式计算平台为这一问题带来了改善的解决方案。文章运用MapReduce框架这一优势，研究了将数据挖掘的任务部署到分布式平台上的方案以及提出了相关研究展望。
关键词：MapReduce框架；Hadoop；数据挖掘方法；数据处理；聚类算法 文献标识码：A
中图分类号：TP316 文章编号：1009-2374（2017）04-0008-03 DOI：10.13535/j.cnki.11-4406/n.2017.04.005
1 概述
随着时代发展，各行各业的日常运营过程中都会产生海量的数据信息，甚至这些信息正呈几何级数增长。无论是零售业、制造业还是政府机关和校园教育都可以從数据信息中发掘出有用的信息来帮助领导者做出决定，进一步优化自身发展的各处细节。数据挖掘就是解决这类问题的重要方法，但随之而来的便是如何快速有效地处理超大规模数据的疑问，提高计算核心的计算能力的确是重要的解决方案，而这确实不易实现。
鉴于半导体技术的不断进步，科技工艺几乎触及其极限，当年的摩尔定律已经无法支撑着如今的制造厂商有效定期提升其产品的处理、计算能力。对于解决大数据信息的有效处理问题，时下流行的方案便是应用云计算，将分析处理任务交给分布式计算平台，在节约计算的时间同时，巧妙地规避了硬件既定的制约。由当年Google公司提出的MapReduce计算模型已成为了分布式计算平台中首选的数据计算框架，本文将对在该框架下部署大规模的数据挖掘进行研究，并探寻可行的解决
方案。
2 研究背景
20世纪60年代，IBM公司推出的CICS成为了最早研究中间件技术的尝试，在80年代中期，贝尔实验室提出了Tuxedo，成为第一代正式中间件产品，90年代发展出很多不同用途的产品。中间件技术帮助信息能够在不同系统甚至网络环境中进行传输，帮助分布式系统的计算方式取得了可喜的进步。在后期也出现了如网格技术、移动Agent技术、P2P技术等多方面的探索成果，但缺乏技术的统一标准也制约了它们广泛应用的能力。在21世纪初的几年，世界范围内对于分布式计算平台的研究方兴未艾。当科技界正探讨如何在集群计算平台中处理大数据样本时，美国科技公司Google的工程师团队率先提出了MapReduce框架的概念，并给出了实施方案，其中除了该计算框架，还包括分布式文件系统、海量数据的分布式数据库系统、分布式锁等重要设计模型。由于提出了一整套的分布式计算的解决方案，该框架的提出引起了业界广泛关注并迅速普及。
利用MapReduce框架进行数据处理的研究也取得了相当多的成果：参考文献[3]提出了在该框架下运行机器学习算法程序来对文本信息进行处理的方案，将大规模的文本处理并行化提升了运算速率；参考文献[4]在对MapReduce框架原理进行深度研究后，提出了利用树构造算法与多路查询算法对内存读写进行开销评估，增强该框架的高并发情境中的读写速率；参考文献[5]提出了将成熟算法部署到MapReduce框架中求解高复杂度问题的思路。
数据挖掘作为网络时代最重要的信息处理技术，已经有了多种领域的应用。参考文献[6]中针对目前网站访问过程中用户端加载速度不理想的现状，提出对用户浏览数据进行数据挖掘处理，获得个人喜好以及访问兴趣，对网页进行预读取，可以有效提升网页加载速度；参考文献[7]用过综合运用关联算法以及聚类算法可以实现一自适应的检测模型，可以有效实时检测出DoS攻击并分析查出异常的数据包的攻击类别；参考文献[8]创新地将数据挖掘技术应用于运营商客户消费行为的趋势分析中，提出了多维度事实物理分类聚类算法，有效获取多维数据中的数据类型，能提高运营商提供服务的精确度；参考文献[9]提出将数据挖掘方法应用到教育领域中的EDM新技术，通过发掘出收集的教育环境数据中的数据独有的类型信息，进而发现受教育者的学习方式以及兴趣，提升其学习效果。
由以上的研究成果可以发现，分布式系统中的MapReduce框架能够帮助多种大数据运算高效完成多类型、高强度的计算任务并提供更简洁易于管理的计算流程。数据挖掘算法也发展出了很多的应用方案，能够解决很多复杂情景中的分类及趋势分析问题。本文将继续对MapReduce框架与数据挖掘算法进行合并研究，探究出将数据挖掘任务部署在MapReduce下的方案。
3 MapReduce并行化计算
作为分布式计算平台中的计算框架，MapReduce主要完成了两大任务：（1）“Map”（映射），将要进行处理或计算的数据样本进行分割并分发至从工作节点；（2）“Reduce”（归约），将各个从节点的数据计算结果统一进行收集进而获取总的结果。程序设计者只需要将数据对象所需要进行并行计算的部分做设计，分发至各个从节点上，最后将需要进行的数据归约处理的规则“告知”Reduce节点，而非需要详细了解系统的底层设计。下面将对该框架进行详细的研究说明：
3.1 Map与Reduce
如上文所介绍，Map、Reduce分别对应了MapReduce框架需要进行的两大任务，映射与归约。通过将数据处理任务的合理分配，对节点的计算结果进行规约汇总，能够实现实时的并行化计算，由于可以将处于同一网络中的普通计算机虚拟化为分布式计算节点，充分利用计算机内存来进行网络数据交换与运算，能够有效节省计算成本提高计算效率。
Map任务根据设计主要分为4大流程：record reader、mapper、combiner和partitioner：（1）record reader：负责解析分发的小的数据块解析为
Reduce任务由框架的设计主要分为：shuffle and sort、reducer和输出格式（output format）3大流程：（1）shuffle and sort：主要是将Map任务提交的输出数据提取到reduce节点中，将中间结果进行数据大小分析，满足条件则直接储存到内存中，通过sort流程进而对数据建立顶堆的规则进行重组，可以帮助数据信息在reduce任务中进行迭代处理；（2）reducer：对上一阶段的处理好的作为输入参数，并利用已有的或自定义例如聚合、过滤等方式对数据进行归约处理。reduce函数的输入是键以及包含与该键对应的所有值的List记录，例如：
3.2 框架工作流程
根据MapReduce框架的map与reduce任务的设计，其框架的计算流程如图1所示：
图1 MapReduce计算流程示意图
通过图1所示，运用Google公司提出的Hadoop分布式计算平台的文件系统HDFS来实现样本数据的存储、传输以及读取，预处理的数据由HDFS中的待处理数据分块得出，框架将分块后的数据块读入到Map任务中，通过数据解析模块的处理，将键值对数据作为参数传递给map函数计算结果以键名存储到list中，中间结果随机传输到下一阶段Reduce任务中，通过打乱并排序操作对中间结果进行处理传输到reduce流程中，经过归约计算输出格式化输出存储到HDFS中。该框架的主从模式的并行化计算的架构由图2展示：
图2 MapReduce并行计算示意图
通过图2所示，主节点通过HDFS分发数据处理作业亦称作Job-Tracker作为分发工作的追踪者，HDFS能够进一步与其余从节点通过接收分块数据并进一步map计算，上传中间结果传输给reduce计算节点进行归约运算，将计算结果上传到HDFS供主节点读取。
4 MapReduce下的数据挖掘综述
在数据挖掘现有的常用算法中，主要分三类，分别为分类与预测、聚类分析和频繁项挖掘。数据挖掘过程主要体现在数据的预处理、样本的统计数据的计算以及概率学计算的使用，这些都可以简化为map函数的相关程序进行并行化计算。
通过前文的相关描述，将数据挖掘任务部署到MapReduce框架下是可行的。在不对数据挖掘的应用领域做要求的情况下，对于分类与预测和聚类的数据挖掘进行MapReduce并行化运算的方案进行研究。
4.1 分类与预测的并行化研究
该类算法的思路是：（1）对预先获取的大量样本对象进行学习运算，获得对数据分类的分类器；（2）运用构建的分类器对目标数据进行分类的判断。在MapReduce框架中主要以离散方式对大数据对象进行运算操作的，运算规模是具有很大弹性的。而针对像朴素贝叶斯分类器的MapReduce实现，需要做出相关的改进。
训练阶段：对于样本的离散取值的统计工作可以并行化处理，包括对属性的均值、标准差计算，都可以交给map函数来处理。进而需要将统计结果（中间结果）进行规约化处理，该项流程也能够写入reduce函数来实现。整合的结果并不能直接用作分类器，因为受到并行化处理的影响，其表现仍是离散的，无法满足贝叶斯分类算法的连续性要求。此时需要将结果放到主处理函数中来进行进一步的连续性转换，才可得出最终的分类器。
预测阶段：将数据样本提取到Map任务中，完成对数据的计算及分类处理，输出的分类中间结果交由Reduce任务来进行最终分类概率的统计。
图3 训练阶段流程示意图
在预测过程处理时，应对数据样本进行规模判断，如果较小，可以单一机器完成，则不需要其他操作；如果较大，便将分类器模型分配到各个map节点中，按照主从模式来进行分布式运算来减少计算时间。
4.2 聚类算法的并行化研究
聚类算法目的是运用分析方法对数据样本进行处理，将对象整体划分为簇的单位，应做到被分类到同簇的数据对象应是相似的，不同则不相似。重点是需要对数据样本进行维度特征的相似度计算（例如k-means的簇中对象的平均值，k-modes算法中需要求出不同维度下的众数），并不断进行迭代直至结果稳定。将聚类算法在MapReduce框架下进行并行化运算的实现思路是：（1）Map任务阶段，选取初轮的簇中心，分配到Map节点上，通过map函数计算每个数据样本的聚类中心距，通过目标函數累加，获取的每个簇的中心数据传递到Reduce节点；（2）Reduce任务阶段，接收Map节点的分类数据进行规约化计算，汇总计算目标函数中的值，获取并更新每个聚类中心的数据，并继续传递给主函数进行判断；（3）主函数处理阶段，判断计算结果是否与上一轮冲突，如果两轮结果不同则返回Map、Reduce任务继续运算，否则停止并输出结果。
该类算法的性能主要由需要进行迭代运算次数决定，通过将任务分配到分布式平台上，可以显著减少不必要的迭代操作，从而提升算法效率。如能获得快速收敛的相似度计算函数方法，该算法计算速率仍能取得较大的增强。
5 研究展望
通过云计算方式去处理日益增长的巨大规模的数据已经成为时下的发展趋势，数据挖掘也同时获得了数据分析业界的重点关注，通过前文描述的相关算法，可以看出该领域日趋成熟的特点，多学科技术的应用也使得其适用面愈加宽广。
作为分布式系统的重要组成部分，MapReduce框架有着不可替代的地位，尤其在大数据处理需求逐年增长，并行化计算体现着显著重要性的业界环境中，与其余并发模型相比较，该框架能够提供较高的编程效率，并且能充分且高效地利用分布式系统各个计算节点的资源，都使得它能够占据领先地位。同时提供了较完善的故障处理的解决机制，也是其成为容错性强的并行化模型的重要优势。
利用MapReduce框架来实现庞大计算的数据挖掘，能够在如今对计算资源较为普遍但难以应付巨型数据处理任务的现实中，取得空间、时间成本与计算开销较为理想的平衡。但在研究过程中，也发现仍有一些问题需要在今后的工作中进行改善：（1）MapReduce框架中的大量中间计算产生的临时读写文件可能承载了数据挖掘运算中的重要数据，如何能够在进一步的迭代过程中加以利用和回溯仍是需要思考的问题；（2）许多数据挖掘算法涉及到机器学习方法，某些监督型算法如何有效地在map过程中进行仍将需要投入精力去研究。
参考文献
[1] 周晓峰，王志坚.分布式计算技术综述[J].计算机时代，2004，（12）.
[2] Dean J，Ghemawat S.MapReduce：Simplified Data Processing on Large Clusters[A].Conference on Symposium on Opearting Systems Design&Implementation[C].2004.
[3] 李锐，王斌.文本处理中的MapReduce技术[J].中文信息学报，2012，26（4）.
[4] 亓开元，韩燕波，赵卓峰，等.支持高并发数据流处理的MapReduce中间结果缓存[J].计算机研究与发展，2013，50（1）.
[5] 吴昊，倪志伟，王会颖.基于MapReduce的蚁群算法[J].计算机集成制造系统，2012，18（7）.
[6] 徐宝文，张卫丰.数据挖掘技术在Web预取中的应用研究[J].计算机学报，2001，24（4）.
[7] 高能，冯登国，向继.一种基于数据挖掘的拒绝服务攻击检测技术[J].计算机学报，2006，29（6）.
[8] 刘蓉，陈晓红.基于数据挖掘的移动通信客户消费行为分析[J].计算机应用与软件，2006，23（2）.
[9] Romero C，Ventura S.Data mining in education[J].Wiley Interdisciplinary Reviews Data Mining&Knowledge Discovery，2013，3（1）.
[10] 李成华，张新访，金海，等.MapReduce：新型的分布式并行计算编程模型[J].计算机工程与科学，2011，33（3）.
[11] 李建江，崔健，王聃，等.MapReduce并行编程模型研究综述[J].电子学报，2011，39（11）.
[12] 蒋良孝.朴素贝叶斯分类器及其改进算法研究[D].中国地质大学，2009.
[13] Han J，Kamber M.Data Mining：Concepts and Techniques，Morgan Kaufmann[J].Machine Press，2006，5（4）.
（責任编辑：黄银芳）
猜你喜欢
