《数据挖掘》课件 第7章 常用大数据挖掘算法优化改进.pdf

数据挖掘高级大数据人才培养丛书之一，大数据挖掘技术与应用第七章常用大数据挖掘算法优化改进随着信息爆炸时代的来临，数据挖掘的应用日趋广泛。许多商业决策者利用数据 挖掘技术从海量的数据中获取有用的信息，为以后企业更好地决策提供帮助。然而，传 统的数据挖掘算法在面对海量数据的时候，由于各种原因，执行效率低下，已经不能够 满足人们日益增长的性能需求，需要寻找更加高效的算法或者执行策略。为了解决这一 系列效率低下的问题，本章对常用大数据挖掘算法进行优化和改进，并将改进后的算法 应用到具体的实例中。高级大数据人才培养丛书之一，大数据挖掘技术与应用第七章常用大数据挖掘算法优化改进7.1 分类算法7.2 聚类算法7.3 关联规则习题)7.1分类算法第7章常用大数据挖掘算法优化改进所谓分类，简单来说，就是根据数据的特征或属性，划分到已有的类别中。7.1.1 分类算法的并行化1.并行算法简介简单的说，算法就是求解问题的方法和步骤。并行算法，就是在并行机上用很多个 处理器联合求解问题的方法和步骤。2.并行算法的常规研究内容1)并行计算模型并行计算模型的第一代是共享存储模型,如SIMD-SM和MIMD-SM的一些计算模型,模型参数主要是CPU的单位计算时间。第二代是分布存储模型。在这个阶段，人们逐渐 意识到对并行计算机性能带来影响的不仅仅是CPU,还有通信。第三代是分布共享存储 模型。）7.1分类算法第7章常用大数据挖掘算法优化改进简单的说，算法就是求解问题的方法和步骤。并行算法，就是在并行机上用很多个 处理器联合求解问题的方法和步骤。2）并行算法的设计技术虽然并行算法研究还不是太成熟，但并行算法的设计依然是有章可循的，例如划分 法、分治法、平衡树法、倍增法等都是常用的设计并行算法的方法。另外人们还可以根 据问题的特性来选择适合的设计方法。3）并行算法分为多机并行和多线程并行多机并行，如MPI技术；多线程并行，如OpenMP技术。InfiniBand并行文件系统）7.1分类算法第7章常用大数据挖掘算法优化改进3.并行计算和并行算法1）并行计算从处理器的角度看，并行计算可划分为时间并行和空间并行，时间并行即流水线技 术，空间并行则是使用多个处理器同时计算。从算法设计的角度来看，并行计算可分为 数据并行和任务并行。从体系结构来说，空间并行导致两类并行机的产生：单指令流多数据流（SIMD）和 多指令流多数据流（MIMD）。MIMD类的机器又可分为常见的五类：并行矢量处理机（PVP）、对称多处理机（SMP）、大规模并行处理机（MPP）、工作站集群（COW）和分布式共享存储处理机（DSM）。从访存模型来说，并行计算有以下5种访存模型：均匀访存模型（UMA）、非均匀 访存模型（NUMA）、全高速缓存访存模型（COMA）、一致性高速缓存非均匀存储 访问模型（CC-NUMA）和非远程存储访问模型（NORMA）o2）并行算法并行算法是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定问题先 分解成若干个尽量相互独立的子问题，然后使用多台计算机同时进行求解，从而最终求 得原问题的解。)7.1分类算法第7章常用大数据挖掘算法优化改进4.共享内存共享内存技术是指开辟一块特殊内存区域，使得多个进程可以共享这块内存进行读 写操作。一旦进程将共享内存区映射到它的地址空间，这些进程间数据的传递就不再涉 及内核，有利于进程间交换大批量数据。InstructionsproblemCPUCPUCPU)7.1分类算法第7章常用大数据挖掘算法优化改进共享内存系统的应用程序开发有多进程和多线程两种方式。多进程程序中的各进程 管理各自的计算资源，进程间的数据共享通过消息方式数据传递实现；而多线程程序中 跑各线程可以分享主进程程序分配的所有计算资源，直接共享程序中的数据，如下图所 ZJo数据传递共享资源进程1内存资源 进程2内存资源 进程内存资源(a)各进程间数据共享方式(b)进程中各线程间数据共享方式)7.1分类算法第7章常用大数据挖掘算法优化改进5.MapReduce并行计算框架M叩Reduce本身就是一个并行计算框架，但是任务可以在MapReduce框架下并 行计算的前提是，任务所对应的数据集可分，且分割后的各子数据集可以并行地被计算,它们之间并没有依存关系，最终只需要合并它们各自产生的结果为最终结果。在M叩Reduce框架下,一个任务通常会被分为两个阶段：Map阶段和Reduce阶段,且所有的操作都是基于key,value键值对的。下图为M叩Reduce任务工作过程。)7.1分类算法第7章常用大数据挖掘算法优化改进7.1.2 并行化的决策树算法优化1.决策树算法的并行策略关于决策树算法的并行训练策略主要有以下两种实现方式。根据数据划分方式的不 同可以分为动态数据划分和静态数据划分；根据程序设计模式的不同可以分为主从模式 和对等模式。1)数据划分方式(1)动态数据划分法。动态数据划分方式就是根据任务进行分片。在构建决策树之前，主处理机上存储着 整个训练数据集。假设当前系统中有可供运行的n台处理机，则要将训练数据集划分为 n个训练子集，主处理机将划分好的n个训练子集分配给包含自己在内的n台处理机。这 n台处理机接收到训练子集后，并行地构建决策树的子树。主处理机重复上面的过程，为完成任务的处理机分配训练集直至所有的处理机都得到任务。)7.1分类算法第7章常用大数据挖掘算法优化改进(2)静态数据划分法。为了解决动态数据方式需要各处理机之间大量通信和频繁数据移动的缺点，给出了 静态数据划分方式。静态数据划分方式又可以分为横向数据划分和纵向数据划分。横向划分方式。横向数据划分方式是指将训练数据集进行水平分割，各个处理机保存的训练数据子 集的大小一样。假设训练数据集为N,处理机的个数为m,则每个处理机处理的数据集 大小为N/m。每个处理机按照同样的扩展策略负责统计本地数据，获取并计算每个属 性分裂点相关的信息，各个处理机之间需要互相通信，按照算法所采用的最佳属性测试 标准，找出最佳属性和分裂点。在划分数据集到各子节点的过程中，各处理机只对本机 数据进行划分。纵向划分方式。纵向划分就是将一个或若干个完整的属性列表分配给一个单独的处理机进行处理，每个处理机并行地完成一个或者多个属性分裂点相关信息的计算过程。)7.1分类算法第7章常用大数据挖掘算法优化改进2)程序设计模式(1)主从模式。基于主从模式前并行决策树方法中选择一个处理机运行主进程，其余处理机运行从 进程。各从进程之间不相互通信，也不要求进行同步。在主从模式下，主处理机先将训练数据集横向划分后平均分配到N个从处理机上，各 从处理机接收数据后并行统计和计算各分裂点的信息；然后，各从处理机把结果信息传 送给主处理机,主处理机综合各从处理机的结果信息，得出最佳分裂属性；最后，主处 理机根据最佳分裂属性的分裂结果形成哈希表后发送到各从处理机上，从处理机再根据 哈希表分割本机上的数据子集。(2)对等模式。在对等模式下，系统中所有处理机都是对等的，没有主从之分，处理器之间通过相 互通信完成决策树的创建。)7.1分类算法第7章常用大数据挖掘算法优化改进2.决策树中C4.5算法并行化对于C4.5决策树分类算法，如果给定数据集和属性集，在构造树的过程中需要计算 所有剩余属性各自对应的分裂指标值，此过程就需要对数据集进行划分，耗时最长，此 时可以利用M叩Reduce并行框架,可大大缩短时间。根据划分结果,分别计算各属性 对应的分裂指标值，从中找出最佳的分裂属性，以此属性为节点，再根据此属性的取值,进行分枝，递归地进行即可得到一颗完整的决策树。对于经典的C4.5算法,基于MapReduce的并行算法,在构造决策树时，分裂指标的 计算方法相同，所以逻辑上若数据集相同，它们构造的决策树应该相同，只是 MapReduce是一并行计算框架,数据集较大时，执行效率高,而经典的决策树算法对 大数据却无能为力。基于Hadoop平台的C4.5算法是为了解决传统的C4.5算法不能处理大规模数据的问 题。C4.5算法的并行化实现方法见数据挖掘一书的第157页。)7.1分类算法第7章常用大数据挖掘算法优化改进7.1.3 一种新的朴素贝叶斯改进方法针对朴素贝叶斯分类方法要求数据集独立性假设的问题，应用统计量分布的方法给 出一种x2分布加权的贝叶斯分类改进方法，有效地改进了卡方独立性假设对朴素贝叶 斯方法独立性假设难以广泛适用的情况。1.属性间的相关关系见数据挖掘一书的第159页。2管法设计设釐表T具有n个条件属性和m个决策属性,分别用随机变量Xj(i=l,2,n)和Y表示,则在加权朴素贝叶斯算法分类模型中权值表示为：叱=卬丫)=/二一J公式中四就作为分类表中第i个条件属性的权值系数。基于权值系数的改进朴素贝叶 斯算法的实现关键在于求解各条件属性与决策属性之间的相关系数。其算法的具体描述 步骤见数据挖掘一书的第159页。)7.1分类算法第7章常用大数据挖掘算法优化改进7.1.4 支持向量机并行优化改进1.并行支持向量机发展常见的并行支持向量机设计模式主要有分组式、级联式、反馈式和混合式4种。1)分组式并行支持向量机(GroupedPSVM)设计思路是：将原始训练集TD按照一定原则切分成n个子训练样本集，每个子训练 样本集中均匀分布着各类样本，之后利用Map操作在集群各节点上并行训练这n个子训 练样本集,训练结果为n个子支持向量集,最后采用Reduce简单地合并n个子支持向量 集，从而得到全局最优支持向量集。2)级联式并行支持向量机(CascadePSVM)同样采用数据分割的思想，通过并行处理样本子集节省大量时间，对子样本集的合 并并非像分组式那样全部合并，而是两两合并子集按照分而治之的原则进行再次训练，直至最终得到全局支持向量模型。将原始训练集TD按照一定原则切分成n个子训练样本 集(n为偶数,且n=2),SV为训练子样本集所得的支持向量。)7.1分类算法第7章常用大数据挖掘算法优化改进3)反馈式并行支持向量机(FeedbackPSVM)在CascadePSVM的基础上引入反馈,即将最后一步得到的全局支持向量反馈到初始 数据子集中进行再次训练，从而避免不合理的数据划分对分类模型性能产生的潜在影响，该策略以迭代的方式进行，通过判断迭代停止条件来终止迭代，从而提高训练精度。4)混合式并行支持向量机(HybridPSVM)常见的混合式并行SVM是分组式和级联式并行SVM的某种组合，该模型先将原始训 练样本集分成n个子集，分别对这些子集进行训练生成各子集的支持向量，这一步与分 组式SVM一样。之后根据预设值k,将这些支持向量合并到k个子集，再次并行训练后 得到最终结果，k个子集中，每个子集含有n/k个原始训练样本子集，这一步并非像分 组SVM整体合并,也不像级联SVM两两合并,而是选取适合的子集数进行合并。最后 合并这些支持向量，得到最终的SVM分类模型。)7.1分类算法第7章常用大数据挖掘算法优化改进2.反馈式并行支持向量机算法实现反馈式并行支持向量机就是将原始训练数据集 分块，通过并行训练子样本集加速全局支持向量的 训练速度，为消除初始数据集划分对分类器性能和 训练结果的潜在影响，特地引入迭代反馈机制，通 过反馈，将本次迭代的结果返回初始分类器进行调 整和更新，从而进一步提高分类准确率。设计和实现基于M a p Red u ce编程框架的反馈式 并行支持向量机时，需要格外重视数据集的划分和 如何迭代这两个问题。右图给出了FeedBackSVM 的流程图。高级大数据人才培养丛书之一，大数据挖掘技术与应用第七章常用大数据挖掘算法优化改进7分类算法7.2聚类算法7二3关联规则 习题)7.2聚类算法第7章常用大数据挖掘算法优化改进聚类就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别，使类别内的数据相似度较大而类别间的数据相似度较小。7.2.1 聚类分析研究的主要内容及算法应用1.目前聚类分析研究的主要内容(1)从对传统的聚类分析方法所做的总结来看，不管是k-means方法,还是CURE 方法，在进行聚类之前都需要用户事先确定要得到的聚类的数目。然而在现实数据中，聚类的数目是未知的，通常要经过不断的实验来获得合适的聚类数目，得到较好的聚类 结果。(2)传统的聚类方法一般都是适合于某种情况的聚类,没有一种方法能够满足各种 情况下的聚类。因此如何解决这个问题成为当前的一个研究热点，有学者提出将不同的 聚类思想进行融合以形成新的聚类算法，从而综合利用不同聚类算法的优点，在一次聚 类过程中综合利用多种聚类方法，能够有效地缓解这个问题。r L coni)7.2聚类算法第7章常用大数据挖掘算法优化改进(3)随着信息时代的到来，对大量的数据进行分析处理是一个很庞大的工作，这就 关系到一个计算效率的问题。有文献提出了一种基于最小生成树的聚类算法，该算法通 过逐渐丢弃最长的边来实现聚类结果，当某条边的长度超过了某个阈值，那么更长边就 不需要计算而直接丢弃，这样就极大地提高了计算效率，降低了计算成本。(4)处理大规模数据和高维数据的能力有待于提高。目前许多聚类方法处理小规模 数据和低维数据时性能比较好，但是当数据规模增大，维度升高时，性能就会急剧下降,而现实生活中的数据大部分又都属于规模比较大、维度比较高的数据集。有文献提出了 一种在高维空间挖掘映射聚类的方法PCKA,它从多个维度中选择属性相关的维度，去 除不相关的维度，沿着相关维度进行聚类，以此对高维数据进行聚类。(5)目前的许多算法都只是理论上的，经常处于某种假设之下，比如聚类能很好地 被分离，没有突出的孤立点等，但是现实数据通常是很复杂的，噪声很大，因此如何有 效地消除噪声的影响，提高处理现实数据的能力还有待进一步提高。）7.2聚类算法第7章常用大数据挖掘算法优化改进2.聚类算法的应用聚类主要应用于模式识别中的语音识别、字符识别等，机器学习中的聚类算法应用 于图像分割和机器视觉，图像处理中聚类用于数据压缩和信息检索。聚类的另一个主要 应用是数据挖掘（多关系数据挖掘）、时空数据库应用（GIS等）、序列和异类数据分 析等，聚类分析对生物学、心理学、考古学、地质学、地理学以及市场营销等研究也都 有重要作用。30）7.2聚类算法第7章常用大数据挖掘算法优化改进典型的聚类过程主要包括数据（或称之为样本或模式）准备、特征选择、特征提取、接近度计算和聚类（或分组）、对聚类结果进行有效性评估等步骤。典型的聚类过程步骤如下：1.数据准备：包括特征标准化和降维。2.特征选择：从最初的特征中选择最有效的特征，并将其存储于向量中。3.特征提取：通过对所选择的特征进行转换形成新的突出特征。4.聚类（或分组）：首先选择合适特征类型的某种距离函数（或构造新的距离函数）进行接近程度的度量；而后执行聚类或分组。5.聚类结果评估：是指对聚类结果进行评估。评估主要有3种：外部有效性评估、内 部有效性评估和相关性测试评估。）7.2聚类算法第7章常用大数据挖掘算法优化改进7.2.2并行聚类相关技术及算法体系结构和模型1.并行聚类相关技术并行计算体系结构主要有以下四种：1）集群（Cluster）具有免费、稳定、开源的Unix和Linux操作系统的计算机集群系统，已成为当下最流 行的高性能计算平台，在高性能计算方式中占有越来越大的比重。2）对称多处理（SMP）由高速缓存Cache、处理单元、总线、交叉开头、共享内存以及输入/输出等组成。3）分布式共享存储多处理（DSM）它能够很好改善SMP的可扩展能力，当前主流的高性能计算机很多都采用这种方式。4）大规模并行处理（MPP）它是目前并行计算机发展过程的主要方向，大规模并行处理可在上万台机器上进行 并行处理，并可应用多种并行计算框架和文件存储系统等。）7.2聚类算法第7章常用大数据挖掘算法优化改进2.并行聚类算法体系结构和模型1）并行算法的基本体系结构相对于串行计算来说，如果按照划分方式来分，并行计算可以划分为时间上的并行 和空间上的并行。空间上的并行主要是利用多个处理器并发计算执行的，目前主要的研 究工作是空间上的并行，而时间上的并行又叫作流水线技术。从程序和算法设计人员的 角度看，并行计算按逻辑又可分为数据并行和任务并行，数据并行的方法就是将大的数 据任务分割成若干个子任务；任务并行和数据并行相似，就是将大的任务分割成若个子 任务，这种方式要比数据并行复杂一些。2）并行计算模型并行计算模型现在没有一个统一的模型，目前计算采用的都是冯诺伊曼的串行模型,这种模型一直用到今天，其他并行模型没有冯诺伊曼式模型这么成熟和应用广泛。筛选光谱簇完成聚类)7.2聚类算法第7章常用大数据挖掘算法优化改进7.2.3 kmeans聚类算法的一种改进方法聚类一直以来都是研究最广泛的学科之一。现在基于划分数据的聚类算法已经成为 数据挖掘和k-means聚类算法的热点研究对象。然而k-means聚类算法也有很多的不 足之处。1.k-means聚类算法的局限性k-means聚类算法使用了迭代的方式，后来被称为劳埃德算法。无论是在随机或使 用其他一些启发式数据时，劳埃德算法首先将输入点划分成初始值集。然后计算出每个 集合的平均点或重心。它通过关联每一个点构造一个新的分区。然后再重新计算出新的 集群点，并通过交替应用这两个步骤的算法程序，直到收敛，这是获得当前点不再开关 集群，利用coresets原始数据相类似的一种算法设计。在性能方面的算法并不保证返回全局最优。该算法的结果质量在很大程度上依赖于 初始集合的数据集，并且在实践中比全局最优要差得多。由于算法的速度非常快，一个 常用的方法是运行算法几次迭代并返回最好的解到集群中去。k-means算法的一个缺点是：数据集的k数目是一个输入参数。如果选择不适合的k 值，可能会产生糟糕的结果。该算法还假定了方差集群分散的适当措施。)7.2聚类算法第7章常用大数据挖掘算法优化改进2.算法流程描述k-means聚类算法的主要流程描述步骤见下表。步 骤内 容口后个初始中心是从数据集中随机选出来的依照聚类数据对象中所求出来的平均值，将每个数据对象分配到最合适该数据的类中去，即将该数 据对象分配到最近邻的类中去又一次计算出每个类的平均值，计算出每一个类中所有数据对象的平均值：L工同；同时对类 进行更新一计算出误差平方和函数值，即：联汇2一叶一 i=l x&：f5*直到聚类准则函数值E不发生任何改变或者相邻之间的差值小于给定的值，否则返回到步骤2做进 一步的迭代)7.2聚类算法第7章常用大数据挖掘算法优化改进3.改进算法的主要思想大量的研究工作集中在对初始聚类中心的选择上。利用蚁群算法来处理最大动态的 数据集中心数量的能力。通过初始搜索密度和分布中心及其他的方法来提高kmeans算 法。建立初始聚类数0二/乂也就是说初始类分到大规模的空间中心的样品中，从最大 maxdis点的所有样品质量的中心计算，以质量为中心，以maxdis为半径画一个圆，将 所有样品分布在圈子包围点内。被分成n个区间，在该点的样品中，样品可以归因于这 样的点。所有样品被分为n个类，每一类导出其质量中心。4.改进算法的基本流程改进算法的基本流程步骤见数据挖掘一书的第166页。如果第一类n存在于任何样品中，具有大的第i级中心取得的抽样小于最大欧几里德 距离的点，那么第一类和第i类就可以组合起来。实践证明，通过基于改变初始聚类中 心的k-means聚类算法比随机选取k-means算法初始聚类中心的聚类结果质量要好得 多。)7.2聚类算法第7章常用大数据挖掘算法优化改进7.2.4 基于S pa r k的k m ea n s算法并行化设计与实现Spark与Hadoop之间最大相异之处为Spark对所有类簇中心点的全部迭代计算基本 都是于内存中计算完成的，当数据处理量远小于节点的内存容量时，计算过程中几乎不 需要再与磁盘进行I/O,而Hadoop则不行,基于Spark的k-means算法的并行实现流 程如下图所示。从HDFS中读取数据 集并创建RDD数据对象向量化 并cache入缓存执行Random函数得到 k个初始类簇中心输出聚类结果A)7.2聚类算法第7章常用大数据挖掘算法优化改进7.2.5 基于Spark的Z-means改进算法的并行化为了提高k-means聚类算法对维度比较高的海量数据集的聚类效率，同时也解决匕 means算法类簇初始中心点的选取和k值的选取问题,选取Canopy粗糙聚类算法来对 基于Spark分布式框架的k-means并行算法进一步改进。通过Canopy算法优化初始中 心点和k值可以降低k-menas算法的迭代次数，从而改进k-means聚类算法在处理大数 据集时数据挖掘的效率和实用性，也可以避免局部最优解。1.Canopy算法思想概述Canopy算法适用于高维度的大数据集预聚类分析，它使用简单粗糙的距离测量方法 可以把数据对象集高效地分割为多个不完全重叠却可以相交的子集Canopy,接着再在 各个Canopy中执行精细聚类算法,这样粗细聚类的结合能提高海量数据处理的效率和 准确性。1086420-2-4-6-4-2 0 2 4 6 8 10-6）7.2聚类算法第7章常用大数据挖掘算法优化改进Canopy算法聚类逻辑过程是这样的，首先从数据对象点集中随机地选择一个数据对 象点A作为第一个子集Ei的聚类中心点,然后再根据其他数据对象点与A的相似度（一 般以欧式距离作为相似度计算准则），将一些数据对象点划分到子集Ei中；接着通过子 集Canopies的创建，将数据对象集中的所有数据对象划分到各个子集Canopy中，使 这些Canopy子集必须完全包含全部数据对象。每个数据对象至少要属于其中的任何一 个Canopy字集,而且它还有可能同时属于一个以上的Canopy子集。由上述Canopy算法定义可知：任意两个数据对象点如果没有归属于同一个子集 Canopy,那么这两个数据对象点就一定不可能是同一类簇的数据对象。）7.2聚类算法第7章常用大数据挖掘算法优化改进2.Canopy算法流程详述虽说Canopy算法可以不用如k-means算法那样人为设置聚类的数目，但仍需要设置 两个相似性度量标准L、丁2来间接决定聚类后子集Canopy的数目和每个子集Canopy 中数据对象点的数目，Canopy算法的详细计算流程步骤见下表。步禁内 容/Id将数据对象集。预处理后得到一个数据向蚩列表D后写入内存，选取距离阈值：1、石。口、石可以通过 交叉校蛉决定2d从数据列表。中随机选取数据对象尸，并计算尸与全部Canopy子集中心点之间的距离（假如Canopy不 存在，则可以将数据对象尸作为一个新的Canopy而加入到Canopy列表中去，同时将P从D中去除），如果 P与某个Canopy中心的距离小于等于不，则可以将点尸加入此Canopy中的数据对象列表劣。=L2L大）3p只要数据对象尸与某个Canopy中心的距离小于等于A,则需要将数据对象尸从数据列表。中去除，这一 步主要是判断数据对象点尸与此Canopy已经比较接近，故尸不能再当作另外Canopy子集的中心4d重复步骤2、3,当数据列表为空时迭代计算结束2)7.2聚类算法第7章常用大数据挖掘算法优化改进3.基于Spark的Canopy_K-means(CKM)算法的并行化设计CKM算法主要由Canop师k-means两部分组成,基于Spark的并行化思路就是依据 CKM算法的两部分来执行并行化设计。基于Spark的CKM并行算法与其串行逻辑大致 相同，不同之处就在于CKM并行算法在使用DAG并行编程模型的同时也利用了Spark 最具特色的RDD。CKM算法基于Spark平台实现其并行化的流程步骤见下表。步骤F内 容1-配置Spark和Yarn集群的有关参数，初始化集群计算环境2从HDFS中读出数据对象集生成初始RDD3 r各节点执行Map操作对原始数据进行格式化，将文本数据向量化4-集群中各个并行节点执行Map操作，计算各自分片的数据对象与Canopy中心点的距离，从而得到局部 Canopy中心点一5执行Reduce操作合并成全局Canopy子集中心点6卡各节点依据全局Canopy中心点执行Map操作，将数据对象全集划分到不同的Canopy,并执行cache操 作将其数据持久化72将Canopy中心点列表赋值给Cluster中心点列表8。各节点再对经过cache之后的RDD进行Map操作执行左-means局部聚类一加主控节点执行Reduce操作，将各个计算节点产生的局部聚类结果归并为全局聚类结果，更新类簇中心点10判断迭代退出条件是否满足，如果满足则输出全局聚类结果，如果不满足则重复执行步骤8和步骤9)7.2聚类算法第7章常用大数据挖掘算法优化改进7.2.6基于MapReduce的聚类算法并行化1.基于M叩Reduce的k-means并行算法的设计k-means聚类算法进行MapReduce的基本思路：对串行算法中每1次迭代启动对应 的1次M叩Reduce计算过程，完成数据记录到聚类中心的距离计算以及新的聚类中心 的计算。下图描述了匕means聚类算法MapReduce并行化实现方法。）7.2聚类算法第7章常用大数据挖掘算法优化改进2.M叩函数的设计M叩函数的任务是完成每个记录到中心点距离的计算，并重新标记其属于的新聚类 类别，其输入为待聚类所有记录数据和上一轮迭代（或初始聚类）的聚类中心，输入数 据记录Key,Value对的形式为行号，记录行Reduce函数的任务是根据M叩函数得到的中间结果计算出新的聚类中心，供下一轮 M叩Reduce工作使用。判断该聚类是否已收敛：比较上一轮M叩Reduce工作得到的聚类中心与本轮 M叩Reduce工作聚类中心距离，若变化小于给定阈值，则算法结束；反之，则用本轮 的聚类中心文件替换上一轮的中心文件，并启动新一轮的MapReduce工作。7.2聚类算法第7章常用大数据挖掘算法优化改进7.2.7谱聚类算法并行化方法1.谱聚类并行化设计下图是谱聚类算法并行化的流程图，从图中可以看出第一部分是数据的输入,输入 数据作为一个整体上传至HDFS时进行分块，将分好块的数据交给M叩进行处理，图中 第二部分是中间部分的处理。谱聚类并行化的M叩Reduce过程分为两个阶段，一部分 是Map阶段，另一个是Reduce阶段。）7.2聚类算法第7章常用大数据挖掘算法优化改进2.谱聚类并行化过程1）构建相似矩阵首先要对原始数据进行处理、构建文本向量，在构建文本向量时要计算每个词在文 本中出现的次数,这就要利用TF-IDF算法。2）并行计算对角矩阵对角矩阵前算方法很简单，为上一步中求出的相似矩阵每一行相加，这是由对角矩 阵的公式所决定的，计算得出的结果再按照相似矩阵的形式将数据放到相应的对角位置 上。3）并行化计算Laplacian矩阵这一步主要的工作是并行计算规范Laplacian矩阵，Laplacian矩阵有规范和非规范 化之分,非规范化Laplacian矩阵表示为L=D-W,由非规范Laplacian矩阵可以推导出 规范的Laplacian矩阵。）7.2聚类算法第7章常用大数据挖掘算法优化改进4）并行计算特征向量及特征值这一步主要计算Laplacian矩阵的最小特征值及特征向量,计算矩阵的最小特征值及 特征向量有很多方法，5）并行k-means算法谱聚类的最后步骤是要选择一个合适的聚类算法，对上几步处理过的数据进行最后 的聚类，在此选择了k-means算法对数据进行最后的聚类。并行k-means算法的思想 是将每个样本分配给其选定的中心点,重复迭代,这个过程是可以在Hadoop平台上并 行执行的，k-means算法并行化主要工作是M叩阶段设计、Combiner函数设计、Reduce函数设计。T3Z P9A6 2AollR COUX9Q8 coujujnui(jG?|onuq高级大数据人才培养丛书之一，大数据挖掘技术与应用第七章常用大数据挖掘算法优化改进7分类算法7.2 聚类算法7.3 关联规则习题，7.3关联规则第7章常用大数据挖掘算法优化改进关联规则是形如X-Y的蕴涵式，其中,X和Y分别称为关联规则的先导和后继关联规 贝必丫，存在支持度和信任度。7.3.1 Apriori算法的一种改进方法1.各种改进的Apriori算法(1)基于压缩矩阵的方法是罗丹提出来的，改进的主要思路是，将数据压缩存储在0-1矩阵中，并用两个额外的数组来分别记录矩阵中各行各列中1的总数，减少了扫描矩 阵的次数，并且能够减少那些不能连接的项目集，提高了空间的利益率，增加了结果的 准确率。(2)基于划分和压缩矩阵的方法是由胡绿慧提出来的，主要是为了解决处理大规模数 据时，效率比较低的问题。(3)基于Spark的方法是由牛海玲提出的，主要是为了使算法能够并行化运行。改进 的主要方面是利用Spark技术，将频繁项集的计算引入到内存中，并且利用矩阵存储来 减少数据库的扫描，将局部剪枝和全局剪枝结合起来，减少候选项集的生成。，7.3关联规则第7章常用大数据挖掘算法优化改进2.基于Hadoop平台的Apriori并行化算法改进1）Apriori算法并行化在生成频繁项集的过程中，需要多次扫描事务数据库，算法运行过程需要通过扫描 数据库得到每一个阶次的候选项集合中元素的出现次数（即支持度计数），然后决定是 要删减还是要保留输出。2）算法改进方向Apriori算法总体来说思想简单，就是通过不断地迭代找出所有的项集，而且算法易 于实现。在运算过程中，通过剪枝操作，在连接生成候选项集的过程中减少不必要项集 的生成，从而减少了接下来工作的任务量。，7.3关联规则第7章常用大数据挖掘算法优化改进3)算法并行化分析一般情况，每次在执行一个MapReduce任务时,都有一个初始化的过程,这个过程 所需要的时间基本上是一定的，每多一次M叩Reduce任务，就会多一次初始化时间消 耗,所以在算法设计的过程中,应该尽可能地减少M叩Reduce迭代次数。Apriori算法的核心就是通过逐层的迭代,来生成1-k阶频繁项集。完全地将Apriori 算法应用到M叩Reduce之上，并不能适应其框架特点，对于Apriori算法的并行化改进 方法，提出了一种基于幕集的M叩Reduce改进算法，新的算法基于幕集定义,将每一 个事务根据幕集思想进行拆分，将得到的所有子集追加到最初定义的集合中，通过不断 地追加计数，得到数据集中所有候选项集的支持度计数，这种算法的好处是，减少了数 据集扫描次数，一次得到所有候选项集的同时也获得了各项集对应的支持度计数。这种 改进方式在时间复杂度和空间复杂度上相对于串行算法有一定优势。4)POP-Apriori算法的实现流程见数据挖掘一书的第175页。7.3关联规则第7章常用大数据挖掘算法优化改进7.3.2 Apriori算法基于Spark的分布式实现1.并行Apriori算法实现思路Apriori算法分布式实现使用Scala语言进行编程。结 合Spark框架和其RDD算子进行综合设计。算法的实现 思路主要分为以下两步：步骤1:产生频繁1，项集L。(1)使用flatMap将事务集T以RDDvString,1的 形式分布到多个机器上。(2)使用reduceByKey累计项目数。(3)使用Filter过滤掉低于支持度的项集。步骤2:从频繁k项集Lk产生频繁k+l项集L*i。(1)自连接,产生Ci。(2)扫描数据库,比对Ci(采用步骤1的方法)，产生L。频繁1项集J右图为分布式Apriori算法的实现流程图。，7.3关联规则第7章常用大数据挖掘算法优化改进2.并行Apriori算法核心步骤步骤1：得到频繁1项集L并保存。步骤2:频繁1项集J自连接产生J,扫描数据库比对Ci,产生fim?，保存。步骤3:循环产生3项集到8项集。mine函数主要包括L自连接和扫描DB过滤C。下图为步骤2和步骤3的流程图。，7.3关联规则第7章常用大数据挖掘算法优化改进7.3.3 并行FP-Growth关联规则算法研究1.并行化基本思想当处理大规模数据集时，FP-Growth算法的缺点是不能构建基于内存的全局Fp-tree,并且算法递归挖掘条件Fp-tree的时间消耗较大。为了解决算法在时间和空间上的局限 性，通常利用数据分解的思想来设计并行FP-Growth算法。数据分解的基本思想是分而治之。对于任意的原始数据集D,当D的大小比可用内存 容量M小时，则采用某种基于内存的关联规则算法来挖掘关联规则。当D的大小超过内 存时，则采用某种分解策略将D分解为k个子数据集必，D2，,Dk，然后对每一个Dk递 归调用数据分解算法。在上述分解算法中，最重要的是分解策略，它的目的是将大规模数据集划分为一个 个小规模的数据子集。这样的划分可以解决FP-Growth算法在时间和空间上的局限性。，7.3关联规则第7章常用大数据挖掘算法优化改进2.并行FP-Growth算法的设计并行化算法分为2个阶段：并行化统计频繁1项集列表。并行化挖掘局部Fp-tree 上的关联规则。1）频繁1项集的并行化方法统计频繁1项集的过程类似于计数统计，因此可以利用数据分解中的划分策略进行数 据集分解。每个处理节点需要对划分到本地数据集中的数据项进行频数的统计，得到局 部的项集计数。然后各个节点之间通信得到每个项目的全局频数，根据最小支持度阈值 删除非频繁项集，从而得到频繁1项集。将频繁1项集广播至各个子节点，保证每个子 节点都保存了频繁1项集列表。2）关联规则的并行化方法从FP-Growth算法可知，在得到频繁1项集列表之后，需要建立全局的Fp-tree才能 获得每个项目的条件模式基,当数据集过大时全局Fp-tree无法放入内存。因此，并行 化的方法将数据集分解为子集之后,在数据子集上建立Fp-tree,这被称为局部Fp-tree,然后针对局部Fp-tree调用FP-Growth方法递归挖掘局部的关联规则。，7.3关联规则第7章常用大数据挖掘算法优化改进7.3.4 基于Spark的FP-Growth算法的并行化实现1.基于Spark的并行FP-Growth算法的设计思想实现算法的并行化需要考虑任务的划分与结果合并的问题。与Hadoop不同,Spark 只需要对其弹性分布式数据集RDD调用相关的转换或动作操作即可，它可以对同一数 据集进行多次操作，更易于实现数据挖掘的并行化。因为FP-Growth算法是依靠消耗 内存来提高算法效率的，因此目前所实现的并行化算法大都会有内存瓶颈，而Spark是 一个基于内存计算的分布式计算框架，采用多线程模型，更适合计算内存密集型的任务。所以，可以结合Spark的优势，实现FP-Growth算法的并行化。在Spark平台上实现的FP-Growth算法的主要思路也分为5步。其算法步骤见数据 挖掘一书的第180页。Spark，7.3关联规则第7章常用大数据挖掘算法优化改进2.基于Spark的FP-Growth算法的并行化实现1）并行计算item支持度在计算item支持度之前,首先,经过转换操作将原始事务集转移到RDD中,以后的 挖掘算法完全是基于该RDD,而不需要再重复扫描事务集。2）数据分组数据分组需要先将F_list中的项进行映射使得频繁项的项名映射成为其在F_list中的位 置，得到映射集合F_map,集合中key值为项名,value值为项在Fist中的位置。3）并行化频繁模式挖掘在对事务集进行分组划分后，需要对每组进行频繁模式的本地挖掘，每组只需挖掘 本组的项的频繁模式，这样可以避免重复挖掘，保证结果的正确性。4）聚合当每组的挖掘工作完成以后，就需要对各个组的结果进行聚合以得到最终结果了。高级大数据人才培养丛书之一，大数据挖掘技术与应用第七章常用大数据挖掘算法优化改进7分类算法72聚类算法7.3关联规则习题习题：1.常用的分类算法有哪些算法？单一的分类方法主要哪些？组合单一分类方法 有哪些？并行算法的常规研究内容是哪些？什么叫并行计算？什么叫共享内存？2.从体系结构来说，空间并行导致哪两类并行机的产生？多指令流多数据流(MIMD)的机器又可分为常见的哪五类？从访存模型来说，并行计算有哪五种 访存模型？并