第10章-大数据分析算法并行化技术及案例分析

《大数据挖掘及应用》第10章大数据分析算法的并行化重庆邮电大学计算机科学与技术学院目录21.1并行算法设计基础1.2典型数据挖掘算法并行化案例1.3大数据分析应用案例1.4小结并行算法设计基础并行计算或称平行计算是相对于串行计算来说的，是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。并行算法设计基础定义10.1并行算法（ParallelAlgorithm）是一些可同时执行的各个进程的集合，这些进程互相作用和协调动作，从而达到给定问题的求解。所谓并行算法，可以朴素地解释为适合于在各种并行计算模型上求解问题和处理数据的算法。按照处理对象的类型，可以分为数值计算的并行算法和非数值计算的并行算法；按照进程的通信方式，又可以分为同步并行算法、异步并行算法以及分布并行算法。并行算法设计基础定义10.2数值计算（NumericalComputation）是指基于代数关系运算的一类，包括矩阵运算、多项式求解、解线性方程组等计算问题，属于数值分析的范畴。定义10.3非数值计算（Non-NumericalComputation）是指基于比较关系运算的一类，包括排序、选择、搜索、匹配以及图论等方面的计算问题，属于符号处理的范畴。定义10.4同步算法（SynchronizedAlgorithm）是指某些进程必须等待别的进程的一类并行算法。并行算法设计基础定义10.5异步算法（AsynchronizedAlgorithm）是指各个进程的执行一般不必互相等待的一类并行算法，进程的通信通过动态读取（修改）共享存储器的全局变量实现。定义10.6分布算法（DistributedAlgorithm）是指由通信链路连接的多个场点或节点，协同完成问题求解的一类并行算法。并行算法编程模型7（1）数据并行模型：数据并行模型既可以在SIMD（SingleInstructionMultipleData，单指令多数据流）计算机上实现，也可以在SPMD（SingleProgramMultipleData，单程序多数据流）计算机上实现。其特点包括：单线程、并行操作于集合数据结构上、松散同步、全局命名空间、隐式相互作用、隐式数据分配等（2）消息传递模型：在消息传递模型中，驻留在不同节点上的进程可以通过网络传递消息（指令、数据、同步信号或中断信号等）互相通信。其特点包括：多线程、异步并行性、分离地址空间、显式相互作用、显式分配并行算法编程模型8（3）共享变量模型：在共享变量模型中，驻留在各处理器上的进程可以通过读/写公共存储器中的共享变量相互通信。并行算法编程模型9特征数据并行共享变量消息传递典型代表HPFOpenMPMPI，PVM可移植性SMP，DSM，MPPSMP，DSM所有流行并行计算机并行粒度进程级细粒度线程级细粒度进城级大粒度并行操作方式松散同步异步异步数据存储模式共享存储共享存储分布式存储数据分配方式半隐式隐式显式学习入门难度偏易容易较难可扩展性一般较差好MPI101992年4月组建了一个制定消息传递接口标准的工作组1992年10月初稿形成，主要定义了点对点通信接口1993年1月第一届MPI会议在Dallas举行1993年2月公布了MPI-1修定版本(原来MPI初稿及个版本的统称)1993年11月MPI的草稿和概述发表在Supercomputing’93的会议论文集中1994年5月MPI标准正式发布1994年7月发布了MPI标准的勘误表1997年MPI论坛发布了一个修订的标准,叫做MPI-2,同时,原来的MPI更名为MPI-1MPI程序的执行11并行计算模型12（1）面向批处理的并行计算模型：具有代表性的面向批处理式分析的分布式并行计算模型有微软公司的Dryad、谷歌公司的MapReduce等。（2）面向流处理的并行计算模型：低延迟是对数据流处理系统的一个基本要求。具有代表性的有Yahoo!的S4、Facebook的Puma、谷歌的MillWheel、Twitter的Storm等（3）面向大图数据的并行计算模型：目前具有代表性的大图并行计算模型有Pregel、HAMA、Giraph、DistributedGraphLab以及Trinity等。（4）基于内存的并行计算模型：具有代表性的是UCBerkeley的基于内存的分布式并行处理框架Spark，其利用内存计算避免了高延迟的磁盘物化，有效保证了处理的实时性并提供了交互式的迭代分析能力。并行算法设计的策略和技术13并行算法的设计在处理数值型和非数值型数据类型时有一定的相似性，一般有三种设计策略：1）串行算法的直接并行化：就是充分发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法，这是数值并行算法中最常用的设计策略。2）从问题描述和计算原理开始重新设计：从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。3）借用已有的算法求解新问题：借鉴别处的已有算法，解决新发现的问题，可能会取得令人满意的结果。并行算法设计的策略和技术14问题划分映射组合通信采用PCAM设计方法学设计并行算法分为四个阶段：划分、通讯、组合、映射。它反映了并行算法设计的自然过程，首先尽量开拓算法的并发性，满足算法的可扩展性，然后着重优化算法的通信成本和全局执行时间，同时通过必要的整个过程的反复回溯，以期最终达到一个满意的设计典型数据挖掘算法并行化案例15回顾一下KMeans算法的基本步骤：1.从数据集x中随机选择一个点作为第一个初始点；2.计算数据集中所有点与当前中心点的距离；3.选择下一个中心点，使得最大。4.重复1、2步过程，直到K个初始点选择完成。典型数据挖掘算法并行化案例16假设样本数据有n个，预期生成k个cluster，则KMeans算法t次迭代过程的时间复杂度为O(nkt)，需要计算ntk次相似度，那么在MapReduce计算框架下，如果能够将各个点到中心点的相似度计算工作分摊到不同的机器上并行地计算，是不是能够减少计算时间呢？MR-KMeans17尝试从以下出发点进行MapReduceKMeans算法改造：将所有的数据分布到不同的节点上，每个节点只对自己的数据进行计算；每个节点能够读取上一次迭代生成的聚簇中心，并判断自己的各个数据点应该属于哪一个聚簇；每个节点在每次迭代中根据自己的数据点计算出相关结果；综合每个节点计算出的相关数据，计算出最终的实际聚类结果。令k=2，欲生成cluster-0和cluster-1随机选取A(1,1)作为cluster-0的中心，C(3,4)作为cluster-1的中心假定将所有数据分布到2个节点node-0和node-1上,即node-0：A(1,1)和C(3,4)node-1：B(2,1)和D(5,5)对象属性1(X)属性2(Y)A11B22C34D55迭代次数0ClusteridCluster中心被分配的点数Cluster-0A(1,1)0Cluster-1C(3,4)0MR-KMeans实例计算各个数据点到各个cluster的距离Node-0Node-1Node-0输出：cluster-0,A(1,1)cluster-1,C(3,4)Node-1输出：cluster-1,B(2,1)cluster-1,D(5,5)数据点到各个聚簇的距离比较分配的聚簇Cluster-0Cluster-1A(1,1)0,近Cluster-0C(3,4)0,近Cluster-1B(2,2)5^(1/2),近Cluster-1D(5,5)45^(1/2),近Cluster-1MR-KMeans实例Map阶段Map的输出（即Combiner的输入）：Combiner的输出键–聚簇ID值–[包含的点数，mean]node-0emit：cluster-0,[1,(1,1)]cluster-1,[1,(3,4)]node-1emit：cluster-1,[2,(3.5,3.5)]Node-0输出：cluster-0,A(1,1)cluster-1,C(3,4)Node-1输出：cluster-1,B(2,2)cluster-1,D(5,5)MR-KMeans实例Combine阶段由于map阶段emit的key是cluster-id，所以每个cluster的全部数据将被发送同一个reducer，包括：该cluster的id该cluster的数据点的均值，及对应于该均值的数据点的个数然后经计算后输出当前的迭代计数clusteridclustercenter属于该clustercenter的数据点的个数MR-KMeans实例Reduce阶段两个reducer分别收到计算可得cluster-0的中心cluster-1的中心Reducer-0：cluster-0,[1,(1,1)]Reducer-1：cluster-1,[1,(3,4)]cluster-1,[2,,(3.5,3)]MR-KMeans实例Reduce阶段在第i次迭代后，已经生成了K个聚类。如果满足了终止条件，即可停止迭代，输出K个聚类终止条件：设定迭代次数;均方差的变化（非充分条件）每个点固定地属于某个聚类其他设定条件......与具体的应用高度相关迭代终止条件Mahout简介24ApacheMahout是ApacheSoftwareFoundation(ASF)开发的一个全新的开源项目，其主要目标是希望建立一个可靠、文档详实、可伸缩的项目，在其中实现一些常见的机器学习算法，供开发人员在Apache许可下免费使用。Mahout最大的优点就是基于hadoop实现，把以前运行于单机上的经典算法，转化到MapReduce计算框架下，大大提升了算法可处理的数据量和处理性能。25算法分类算法名称中文名称分类算法LogisticRegression逻辑回归Bayesian贝叶斯SVM支持向量机Perceptron感知器算法NeuralNetwork神经网络RandomForests随机森林RestrictedBoltzmannMachines有限波尔兹曼机聚类算法CanopyClusteringCanopy聚类K-meansClusteringK均值聚类FuzzyK-means模糊K均值ExpectationMaximizationEM聚类（期望最大化聚类）MeanShiftClustering均值漂移聚类HierarchicalClustering层次聚类DirichletProcessClustering狄里克雷过程聚类LatentDirichletAllocationLDA聚类SpectralClustering谱聚类关联规则挖掘ParallelFPGrowthAlgorithm并行FPGrowth算法回归LocallyWeightedLinearRegression局部加权线性回归降维/维约简SingularValueDecomposition奇异值分解PrincipalComponentsAnalysis主成分分析IndependentComponentAnalysis独立成分分析GaussianDiscriminativeAnalysis高斯判别分析进化算法并行化了Watchmaker框架推荐/协同过滤Non-distributedrecommendersTaste(UserCF,ItemCF,SlopeOne）DistributedRecommendersItemCF向量相似度计算RowSimilarityJob计算列间相似度VectorDistanceJob计算向量间距离非Map-Reduce算法HiddenMarkovModels隐马尔科夫模型集合方法扩展Collections扩展了java的Collections类Mahout中的机器学习算法简介