大数据背景下机器学习并行算法研究

马巍巍 殷凤梅 张江

摘要 面对海量、多样变化的大数据，基于小数据的传统机器学习算法计算负担的困难日益显现，并行计算是解决这一问题的主流方法。阐述了大数据环境下的机器学习研究现状;在此基础上，分析梳理了当前大数据下机器学习并行算法的关键技术;最后对其发展前景进行了展望。

[关键词]机器学习算法 并行计算 大数据

1 引言

大数据时代已经来临。最早提出这一概念的是全球知名咨询公司麦肯锡，麦肯锡称：“数据，已经渗透到当今每一个行业和业务职能领域，成为重要的生产因素。人们对于海量数据的挖掘和运用，预示着新一波生产率增长和消费者盈余浪潮的到来。”我们所感兴趣的是大数据中所隐含的相较小型数据所不具备的大量未知的知识和价值，通过数据挖掘分析，它们能为社会带来巨大的商业价值，实现多种高附加值的增值服务，让人们的生活更加方便快捷。

机器学习和数据分析是将大数据转换成有用知识的关键技术，并且有研究表明，在很多情况下，处理的数据规模越大，机器学习模型的效果会越好。因此，机器学习是大数据智能化分析处理应用中的重要手段。在大数据背景下，计算数据量级己升至TB级或PB级，这对传统机器学习带来了挑战和机遇。机器学习算法本身含有大量的迭代计算，非常适用于并行化。目前，对大数据机器学习并行化研究己成为应对大数据应用需求的热点研究方向。

本文首先介绍了大数据的内涵和机器学习算法的主要问题;然后重点分析总结了目前处理大数据机器学习的并行方法;最后阐述了大数据时代机器学习并行算法发展趋势。

2 大数据与机器学习

2.1 大数据内涵

大数据的含义是由人类日益普及的网络行为所伴生的，它被相关部门、企业按照某种意图收集的多源异构、动态多变的数据。过去只有公司或科研机构才拥有数据;而现在，我们每个人都是数据的生产者，同时也是数据的消费者。根据美国互联网数据中心的数据显示互联网上的数据每年将增长50%，每两年便将翻一番，而目前世界上90%以上的数据是最近几年才产生的。

目前在各行各业均存在大数据，然而大数据并不仅仅是指数量庞大的数据。它的真正含义是指数据一定有被学习算法利用的价值，也就是说除了数据量大外，还包含着挖掘这些数据价值的新的技术。由于大数据研究的重要性，在产业界和学术界受到了空前的关注，2012年，美国政府宣布将“大数据战略”上升为国家战略。我国也把大数据列为重大研究课题。

目前业界普遍认可大数据具有的5V特征是由IBM提出的，即：Volume（大量）、Velocity（高速）、Variety（多样）、Value（价值密度）、Veracity（真实性）。具体见图1。

2.2 大数据下的机器学习

机器学习即让机器自己学习问题解决的算法，是目前信息技术领域中最受关注的方向之一。它涉及的内容非常广泛，如机械应用中的无人驾驶汽车，瀏览新闻时自动跳出你最近经常看的相关内容，生物学中的人类基因组分类等各个行业和基础科学中都有着机器学习算法的身影。

传统的机器学习主要包括四个方面：人类的学习过程的理解和模拟;研究计算机系统与人类用户之间的自然语言接口;问题的推理能力，自动规划设计能力;设计可发现新事物的程序。

针对大数据的5V特性，机器学习算法不仅仅解决数据库方面的问题，它还必须智能化。在构建机器学习算法时，我们需要实现两个任务：

（1）在训练数据时，我们需要求解优化问题以及存储和处理海量数据的高效算法。

（2）一旦习得了某种模型，它的表示和用于推理的算法解也必须是高效的。

在机器学习特定的应用中，算法的空间复杂度和时间复杂度，或者说算法的效率是和算法的准确率同样重要的问题。传统的机器学习算法大多是串行的，在数据量、数据维度不断地增长的情况下，单机的存储容量和运行时长都是无法忍受的。在这种情况下，考虑将算法并行化是一个非常自然的想法。研究人员开始寻求新的算法以及计算平台加速大数据的运算。

3 大数据并行算法

为适应大数据处理的特征要求，学术界和产业界正在进行各种研究和探索，开发并行计算模型。目前，处理大数据机器学习的并行方法主要有分布式并行计算、多核异构计算平台和以上两种方式混合的并行计算。

3.1 分布式并行

早期的分布式并行计算需要大量复杂的通信、同步以及调度等并发控制操作，例如较流行的分布式存储体系结构的MPI （MessagePassing Interface，消息传递接口），在提升计算性能方面也取得了很多成果，但也出现了很多问题。其中最主要的问题是随着系统的复杂化和大数据的处理要求，管理和维护困难，并且硬件费用和运行成本高昂，因此一直局限于国家大型机构或实验室应用，很难推广。

以MapReduce /Hadoop为代表的大规模数据分布式并行计算模型能改善这一状况。MapReduce是一个基于集群的高性能并行计算平台，最早由谷歌公司研究提出，后基于Java设计开发的Hadoop开源实现后，已经成为事实上的大数据处理的工业标准。目前MapReduce己在数据挖掘、机器学习、图形图像处理等众多领域实现应用。MapReduce提供了抽象的操作和并行编程接口，执行阶段由Map和Reduce两个函数编程实现，降低了并行编程难度，方便完成大规模数据的编程和计算处理。为提高并行效率，目前国内外的学者对MapReduce做了大量的优化研究工作。

Spark是继Hadoop之后的新一代大数据分布式处理框架，由UC Berkeley的Mateaaharia主导开发。Spark架构较新，它启用了内存分布数据集，对于需要多次迭代使用的数据保存在分布式内存中，省去大量的磁盘读写操作，缩短访问延迟。同时，Spark提供了更为通用和灵活的操作接口，降低了编程难度。因此对于有较多迭代运算的机器学习算法，Spark平台明显比Hadoop有着显而易见的优势。国内外学者对此进行了相关研究并取得了相关的结论。文献[6]实验结果表明对于机器学习中的K-means聚类算法，改进后的基于Spark的并行加速比要优于Hadoop平台，并且数据量增大时，并行计算效果更好。

另外，Spark和Hadoop都是面向批处理的并行计算模型，然而在大数据应用中，我们还需要处理基于数据流的数据挖掘。数据流应用要求低延迟，以保证数据价值的时效性。Spark提供了大量的库，其中Spark Streaming可以实现高吞吐量的、具备容错机制的实时流数据的处理。它的处理方式是首先接收实时流数据，按规定的时间间隔拆分数据，最后通过Spark Engine得到处理后的结果。文献[7]实现了基于Spark Streaming的KMeans数据流聚类算法，其吞吐能力等运行性能表现优异，但还存在大量可以优化的方面。

3.2 多核异构计算平台

近年来，多核異构的并行编程模型不断涌现。由于其具有低成本高性能，且降低并行编程难度的优势，目前在加速算法方面得到了广泛的使用。目前较多的异构计算发生在CPU+GPU平台上，早期的GPU （GraphicsProcessing Unit，图形处理器）主要目标是处理图运算工作，而现在GPU在通用计算方面的能力已经显现，并行计算方面，GPU可以提供数十倍乃至于上百倍相较CPU的性能。GPU通用计算方面的标准目前有OPENCL、CUDA和ATI STREAM。文献[8]基于GPU平台提出一种并行冒泡的新型KNN并行算法，分别使用两种异构编程模型实验，结果表明改进后的使用OPENCL并行算法比未改进的使用CUDA并行算法快16倍。文献[9]在深度神经网络的计算中基于GPU并行计算，取得了较好的实验效果。

此外CPU+FPGA异构平台也引起了研究人员的关注，FPGA （Field Programmable GateArray，FPGA现场可编程门阵列）具有低功耗，高吞吐量等优点，利用芯片中的众多逻辑门同时进行逻辑运算实现高度并行计算。文献[10]基于FPGA对机器学习K-means算法优化，实验显示与基于Spark框架的8核心CPU平台相比，FPGA异构平台的计算性能最高提升4.4倍。文献[11]对以上两种并行平台均进行了实验，并与串行方式进行比较，结果都有较大提升。

3.3 混合方式

上述两种并行方式对计算性能的提升都有很大帮助，但也存在着各自的问题。例如GPU的运算能力远超CPU，但是GPU集群对大数据的存储能力不足;而分布式MapReduce架构在大量不断的优化下，易于扩展、性价比高，但对于复杂大数据的处理性能不佳。鉴于此，国内外学者开始尝试以混合两种方式来提升机器学习并行算法。

文献[12]采用MapReduce与GPU集群混合的方法，并细致的描述了这种方法的计算有效性。当然，除此之外，还存在很多有效的混合方式，如文献[13]实现了基于MPI的GPU并行通信系统，文献[14]则讨论了三级并行编程环境CUDA+MPI+OpenMP的快速搭建以及多粒度混合并行编程方法，这些方法的实现为并行平台的多样化发展提供了有益的借鉴。

4 结论

并行平台能有效改善高性能计算系统的性能瓶颈和海量数据存储问题，同时也带来了大量的研究挑战。随着基础硬件资源的不断更新发展，以及物联网、云计算等的兴起，决定了并行计算模型的多样化和应用性。目前并行计算模型的的研究已经展开，但仍在摸索阶段，有很多大量关键的问题等待解决完善。在大数据背景下，针对具体的应用场景，设计出更加高效地并行算法完成数据挖掘任务，满足实际应用的需求，是未来所要努力的方向。

参考文献

[1]黄宜华.大数据机器学习系统研究进展[J]，大数据，2015，TOPIC专题，

[2]何清，李宁等，大数据下机器学习算法综述[J].模式识别与人工智能，2014， 27 （04）： 327-337.

[3]（土）阿培丁（Alpaydin，E.）著，范明译，机器学习导论（原书第3版）[M].北京：机械工业出版牡，2015：2.

[4] CHEN L， AGRAWAL G. Optimizing MapReducefor GPUs with effective shared memoryusage[C]. proceeding of the 21stinternational symposium on High-Performace Parallel and DistributedComputing （HDPC2012）.

[5] Apache Spark Project [EB/OL].[2016-03-20]. http：，/spark. apache. org/mllib/.

[6]孟建良，刘德超，一种基于Spark和聚类分析的辨识电力系统不良数据新方法…，电力系统保护与控制，2016，44 （03）：85-91.

[7]唐振坤，基于Spark的机器学习平台设计与实现[D].厦门大学，2014.

[8]贺江，蒲宇亮，李海波等.一种基于OpenCL的高能效并行KNN算法及其GPU验证[J]，电子技术应用，2016，42 （02）：14-16.

[9] Seide F，Fu H，Droppoj， et al. l-bittochastic gradient descent andits application to data-paralleldistributed training of speechDNNs [C]. Interspeech.2 014： 1058-1062.

[10]胡雷钧，庞松，朱炯等，基于FPGA的大数据K-means算法优化[J].电力信息与通信技术，2016，14 （08）：1—6.

[11]黄海洋，面向大数据的CPU_GPU_FPGA计算平台研究[D].成都：电子科技大学，2017.

[12]徐顺苟.GPU计算在大数据处理中的应用[D].兰州大学，201 5.

[13]侯景德，陈庆奎等，基于MPI的GPU集群并行通信系统实现[J].计算机应用与软件，2016，33 （04）116-121.

[14]滕人达，刘青昆.CUDA、MPI和OpenMP三级混合并行模型的研究[J].微计算机应用，2010，31（09）：63-69.