单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第七章,常用,大数据挖掘算法优化,改进,of,57,1,随着,“信息爆炸”时代的来临，数据挖掘的应用日趋广泛。许多商业决策者利用数据挖掘技术从海量的数据中获取有用的信息，为以后企业更好地决策提供帮助。然而，传统的数据挖掘算法在面对海量数据的时候，由于各种原因，执行效率低下，已经不能够满足人们日益增长的性能需求，需要寻找更加高效的算法或者执行策略。为了解决这一系列效率低下的问题，本章对常用大数据挖掘算法进行优化和改进，并将改进后的算法应用到具体的实例中。,More,第七章常用大数据挖掘算法优化改进of571 随着“信,7.1,分类算法,第七章,常用,大数据挖掘算法优化,改进,7.2,聚,类算法,7.3,关联规则,习题,of,57,2,7.1分类算法第七章常用大数据挖掘算法优化改进7.2聚,1.,并行算法简介,7.1.1,分类,算法的并行化,of,57,3,7.1,分类算法,第,7,章,常用,大数据挖掘算法优化,改进,简单的说，算法就是求解问题的方法和步骤。并行算法，就是在并行机上用很多个处理器联合求解问题的方法和步骤。,所谓,分类，简单来说，就是根据数据的特征或属性，划分到已有的类别中,。,2.,并行算法,的常规研究内容,1,）并行计算模型,并行计算,模型的第一代是共享存储模型，如,SIMD-SM,和,MIMD-SM,的一些计算模型，模型参数主要是,CPU,的单位,计算时间。,第二代是分布存储模型。在这个阶段，人们逐渐意识到对并行计算机性能带来影响的不仅仅是,CPU,，还有通信,。第,三代是分布共享存储模型。,1.并行算法简介7.1.1 分类算法的并行化of5,of,57,4,7.1,分类算法,第,7,章,常用,大数据挖掘算法优化,改进,简单的说，算法就是求解问题的方法和步骤。并行算法，就是在并行机上用很多个处理器联合求解问题的方法和步骤。,2,）并行算法的设计技术,虽然,并行算法研究还不是太成熟，但并行算法的设计依然是有章可循的，例如划分法、分治法、平衡树法、倍增,法等,都是常用的设计并行算法的方法。另外人们还可以根据问题的特性来选择适合的设计方法。,3,）并行算法分为多机并行和多线程并行,多,机并行，如,MPI,技术；多线程并行，如,OpenMP,技术。,of5747.1 分类算法第7章 常用大数据挖掘算法优化改进,of,57,5,7.1,分类算法,第,7,章,常用,大数据挖掘算法优化,改进,1,）并行计算,从,处理器的角度看，并行计算可划分为时间并行和空间并行，时间并行即流水线技术，空间并行则是使用多个处理器同时计算。从算法设计的角度来看，并行计算可分为数据并行和任务,并行。,从,体系结构来说，空间并行导致两类并行机的产生：单指令流多数据流（,SIMD,）和多指令流多数据流（,MIMD,）。,MIMD,类的机器又可分为常见的五类：并行矢量处理机（,PVP,）、对称多处理机（,SMP,）、大规模并行处理机（,MPP,）、工作站集群（,COW,）和分布式共享存储处理机（,DSM,）。,从,访存模型来说，并行计算有以下,5,种访存模型：均匀访存模型（,UMA,）、非均匀访存模型（,NUMA,）、全高速缓存访存模型（,COMA,）、一致性高速缓存非均匀存储访问模型（,CC-NUMA,）和非远程存储访问模型（,NORMA,）,。,2,）并行算法,并行算法是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定问题先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时进行求解，从而最终求得原问题的解。,3.,并行计算,和并行算法,of5757.1 分类算法第7章 常用大数据挖掘算法优化改进,of,57,6,7.1,分类算法,第,7,章,常用,大数据挖掘算法优化,改进,共享,内存技术是指开辟一块特殊内存区域，使得多个进程可以共享这块内存进行读写操作。一旦进程将共享内存区映射到它的地址空间，这些进程间数据的传递就不再涉及内核，有利于进程间交换大批量数据,。,4.,共享内存,of5767.1 分类算法第7章 常用大数据挖掘算法优化改进,of,57,7,7.1,分类算法,第,7,章,常用,大数据挖掘算法优化,改进,共享,内存系统的应用程序开发有多进程和多线程两种方式。多进程程序中的各进程管理各自的计算资源，进程间的数据共享通过消息方式数据传递实现；而多线程程序中的各线程可以分享主进程程序分配的所有计算资源，直接共享程序中的数据，,如,下,图所,示。,of5777.1 分类算法第7章 常用大数据挖掘算法优化改进,of,57,8,7.1,分类算法,第,7,章,常用,大数据挖掘算法优化,改进,MapReduce,本身就是一个并行计算框架，但是任务可以在,MapReduce,框架下并行计算的前提是，任务所对应的数据集可分，且分割后的各子数据集可以并行地被计算，它们之间并没有依存关系，最终只需要合并它们各自产生的结果为最终结果。,在,MapReduce,框架下，一个任务通常会被分为两个阶段：,Map,阶段和,Reduce,阶段，且所有的操作都是基于,键值对的。,下图为,MapReduce,任务工作过程,。,5.MapReduce,并行计算框架,of5787.1 分类算法第7章 常用大数据挖掘算法优化改进,of,57,9,7.1,分类算法,第,7,章,常用,大数据挖掘算法优化,改进,7.1.2,并行化,的决策树算法优化,1.,决策,树算法的并行,策略,关于,决策树算法的并行训练策略主要有以下两种实现方式。根据数据划分方式的不同可以分为动态数据划分和静态数据划分；根据程序设计模式的不同可以分为主从模式和对等,模式。,1,）数据划分方式,（,1,）动态数据划分法。,动态,数据划分方式就是根据任务进行分片。在构建决策树之前，主处理机上存储着整个训练数据集。假设当前系统中有可供运行的,n,台处理机，则要将训练数据集划分为,n,个训练子集，主处理机将划分好的,n,个训练子集分配给包含自己在内的,n,台处理机。这,n,台处理机接收到训练子集后，并行地构建决策树的子树。主处理机重复上面的过程，为完成任务的处理机分配训练集直至所有的处理机都得到任务。,of5797.1 分类算法第7章 常用大数据挖掘算法优化改进,of,57,10,7.1,分类算法,第,7,章,常用,大数据挖掘算法优化,改进,（,2,）静态数据划分法。,为了,解决动态数据方式需要各处理机之间大量通信和频繁数据移动的缺点，给出了静态数据划分方式。静态数据划分方式又可以分为横向数据划分和纵向数据划分。,横向划分方式。,横向,数据划分方式是指将训练数据集进行水平分割，各个处理机保存的训练数据子集的大小一样。假设训练数据集为,N,，处理机的个数为,m,，则每个处理机处理的数据集大小为,N/m,。每个处理机按照同样的扩展策略负责统计本地数据，获取并计算每个属性分裂点相关的信息，各个处理机之间需要互相通信，按照算法所采用的最佳属性测试标准，找出最佳属性和分裂点。在划分数据集到各子节点的过程中，各处理机只对本机数据进行划分。,纵向划分方式。,纵向,划分就是将一个或若干个完整的属性列表分配给一个单独的处理机进行处理，每个处理机并行地完成一个或者多个属性分裂点相关信息的计算过程。,of57107.1 分类算法第7章 常用大数据挖掘算法优化改,of,57,11,7.1,分类算法,第,7,章,常用,大数据挖掘算法优化,改进,2,）,程序设计模式,（,1,）主从模式。,基于,主从模式的并行决策树方法中选择一个处理机运行主进程，其余处理机运行从进程。各从进程之间不相互通信，也不要求进行同步。,在,主从模式下，主处理机先将训练数据集横向划分后平均分配到,N,个从处理机上，各从处理机接收数据后并行统计和计算各分裂点的信息；然后，各从处理机把结果信息传送给主处理机，主处理机综合各从处理机的结果信息，得出最佳分裂属性；最后，主处理机根据最佳分裂属性的分裂结果形成哈希,表后,发送到各从处理机上，从处理机再根据哈希表分割本机上的数据子集,。,（,2,）对等模式。,在,对等模式下，系统中所有处理机都是对等的，没有主从之分，处理器之间通过相互通信完成决策树的创建,。,of57117.1 分类算法第7章 常用大数据挖掘算法优化改,12,of,57,13,7.1,分类算法,第,7,章,常用,大数据挖掘算法优化,改进,2.,决策树,中,C4.5,算法,并行化,对于,C4.5,决策树分类算法，如果给定数据集和属性集，在构造树的过程中需要计算所有剩余属性各自对应的分裂指标值，此过程就需要对数据集进行划分，耗时最长，此时可以利用,MapReduce,并行框架，可大大缩短时间。根据划分结果，分别计算各属性对应的分裂指标值，从中找出最佳的分裂属性，以此属性为节点，再根据此属性的取值，进行分枝，递归地进行即可得到一颗完整的决策树。,对于经典的,C4.5,算法，基于,MapReduce,的并行算法，在构造决策树时，分裂指标的计算方法相同，所以逻辑上若数据集相同，它们构造的决策树应该相同，只是,MapReduce,是一并行计算框架，数据集较大时，执行效率高，而经典的决策树算法对大数据却无能为力。,基于,Hadoop,平台的,C4.5,算法是,为了解决传统的,C4.5,算法不能处理大规模数据的问题。,C4.5,算法的并行化实现,方法见,数据挖掘,一书的第,157,页。,12of57137.1 分类算法第7章 常用大数据挖掘算法优,of,57,13,7.1,分类算法,第,7,章,常用,大数据挖掘算法优化,改进,7.1.3,一,种新的朴素贝叶斯改进方法,针对,朴素贝叶斯分类方法要求数据集独立性假设的问题，应用统计量分布的方法给出一,种,分布,加权的贝叶斯分类改进方法，有效地改进了卡方,独立性假设,对朴素贝叶斯方法独立性假设难以广泛适用的情况,。,1,.,属性间的相关关系,见,数据挖掘,一书的第,159,页。,2,.算法设计,设分类表,T,具有,n,个条件属性和,m,个决策属性，分别用随机变量,X,i,(i=1,2,n),和,Y,表示，,则在加权朴素贝叶斯算法分类模型中权值表示为：,公式中,w,i,就作为分类表中第,i,个条件属性的权值系数。基于权值系数的改进朴素贝叶斯算法的实现关键在于求解各条件属性与决策属性之间的相关系数。其算法的具体描述步骤见,数据挖掘,一书的第,159,页。,of57137.1 分类算法第7章 常用大数据挖掘算法优化改,of,57,14,7.1,分类算法,第,7,章,常用,大数据挖掘算法优化,改进,7.1.4,支持,向量机并行优化改进,常见,的并行支持向量,机设计,模式主要有分组式、级联式、反馈式和混合式,4,种。,1,）分组式并行支持向量机（GroupedPSVM）,设计思路是：将原始训练集,TD,按照一定原则切分成,n,个子训练样本集，每个子训练样本集中均匀分布着各类样本，之后利用,Map,操作在集群各节点上并行训练这,n,个子训练样本集，训练结果为,n,个子支持向量集，最后采用,Reduce,简单地合并,n,个子支持向量集，从而得到全局最优支持向量集。,2,）级联式并行支持向量机（CascadePSVM）,同样采用数据分割的思想，通过并行处理样本子集节省大量时间，对子样本集的合并并非像分组式那样全部合并，而是两两合并子集按照分而治之的原则进行再次训练，直至最终得到全局支持向量模型。将原始训练集,TD,按照一定原则切分成,n,个子训练样本集（,n,为偶数，且,n=2,），,SV,为训练子样本集所得的支持向量。,1.,并行,支持向量机,发展,of57147.1 分类算法第7章 常用大数据挖掘算法优化改,of,57,15,7.1,分类算法,第,7,章,常用,大数据挖掘算法优化,改进,3,）反馈式并行支持向量机（FeedbackPSVM）,在,CascadePSVM,的基础上引入反馈，即将最后一步得到的全局支持向量反馈到初始数据子集中进行再次训练，