《数据挖掘》课件 第7章 常用大数据挖掘算法优化改进.pdf
《《数据挖掘》课件 第7章 常用大数据挖掘算法优化改进.pdf》由会员分享,可在线阅读,更多相关《《数据挖掘》课件 第7章 常用大数据挖掘算法优化改进.pdf(50页珍藏版)》请在咨信网上搜索。
1、数据挖掘高级大数据人才培养丛书之一,大数据挖掘技术与应用第七章常用大数据挖掘算法优化改进随着信息爆炸时代的来临,数据挖掘的应用日趋广泛。许多商业决策者利用数据 挖掘技术从海量的数据中获取有用的信息,为以后企业更好地决策提供帮助。然而,传 统的数据挖掘算法在面对海量数据的时候,由于各种原因,执行效率低下,已经不能够 满足人们日益增长的性能需求,需要寻找更加高效的算法或者执行策略。为了解决这一 系列效率低下的问题,本章对常用大数据挖掘算法进行优化和改进,并将改进后的算法 应用到具体的实例中。高级大数据人才培养丛书之一,大数据挖掘技术与应用第七章常用大数据挖掘算法优化改进7.1 分类算法7.2 聚类
2、算法7.3 关联规则习题)7.1分类算法第7章常用大数据挖掘算法优化改进所谓分类,简单来说,就是根据数据的特征或属性,划分到已有的类别中。7.1.1 分类算法的并行化1.并行算法简介简单的说,算法就是求解问题的方法和步骤。并行算法,就是在并行机上用很多个 处理器联合求解问题的方法和步骤。2.并行算法的常规研究内容1)并行计算模型并行计算模型的第一代是共享存储模型,如SIMD-SM和MIMD-SM的一些计算模型,模型参数主要是CPU的单位计算时间。第二代是分布存储模型。在这个阶段,人们逐渐 意识到对并行计算机性能带来影响的不仅仅是CPU,还有通信。第三代是分布共享存储 模型。)7.1分类算法第7
3、章常用大数据挖掘算法优化改进简单的说,算法就是求解问题的方法和步骤。并行算法,就是在并行机上用很多个 处理器联合求解问题的方法和步骤。2)并行算法的设计技术虽然并行算法研究还不是太成熟,但并行算法的设计依然是有章可循的,例如划分 法、分治法、平衡树法、倍增法等都是常用的设计并行算法的方法。另外人们还可以根 据问题的特性来选择适合的设计方法。3)并行算法分为多机并行和多线程并行多机并行,如MPI技术;多线程并行,如OpenMP技术。InfiniBand并行文件系统)7.1分类算法第7章常用大数据挖掘算法优化改进3.并行计算和并行算法1)并行计算从处理器的角度看,并行计算可划分为时间并行和空间并行
4、,时间并行即流水线技 术,空间并行则是使用多个处理器同时计算。从算法设计的角度来看,并行计算可分为 数据并行和任务并行。从体系结构来说,空间并行导致两类并行机的产生:单指令流多数据流(SIMD)和 多指令流多数据流(MIMD)。MIMD类的机器又可分为常见的五类:并行矢量处理机(PVP)、对称多处理机(SMP)、大规模并行处理机(MPP)、工作站集群(COW)和分布式共享存储处理机(DSM)。从访存模型来说,并行计算有以下5种访存模型:均匀访存模型(UMA)、非均匀 访存模型(NUMA)、全高速缓存访存模型(COMA)、一致性高速缓存非均匀存储 访问模型(CC-NUMA)和非远程存储访问模型(
5、NORMA)o2)并行算法并行算法是用多台处理机联合求解问题的方法和步骤,其执行过程是将给定问题先 分解成若干个尽量相互独立的子问题,然后使用多台计算机同时进行求解,从而最终求 得原问题的解。)7.1分类算法第7章常用大数据挖掘算法优化改进4.共享内存共享内存技术是指开辟一块特殊内存区域,使得多个进程可以共享这块内存进行读 写操作。一旦进程将共享内存区映射到它的地址空间,这些进程间数据的传递就不再涉 及内核,有利于进程间交换大批量数据。InstructionsproblemCPUCPUCPU)7.1分类算法第7章常用大数据挖掘算法优化改进共享内存系统的应用程序开发有多进程和多线程两种方式。多进
6、程程序中的各进程 管理各自的计算资源,进程间的数据共享通过消息方式数据传递实现;而多线程程序中 跑各线程可以分享主进程程序分配的所有计算资源,直接共享程序中的数据,如下图所 ZJo数据传递共享资源进程1内存资源 进程2内存资源 进程内存资源(a)各进程间数据共享方式(b)进程中各线程间数据共享方式)7.1分类算法第7章常用大数据挖掘算法优化改进5.MapReduce并行计算框架M叩Reduce本身就是一个并行计算框架,但是任务可以在MapReduce框架下并 行计算的前提是,任务所对应的数据集可分,且分割后的各子数据集可以并行地被计算,它们之间并没有依存关系,最终只需要合并它们各自产生的结果为
7、最终结果。在M叩Reduce框架下,一个任务通常会被分为两个阶段:Map阶段和Reduce阶段,且所有的操作都是基于key,value键值对的。下图为M叩Reduce任务工作过程。)7.1分类算法第7章常用大数据挖掘算法优化改进7.1.2 并行化的决策树算法优化1.决策树算法的并行策略关于决策树算法的并行训练策略主要有以下两种实现方式。根据数据划分方式的不 同可以分为动态数据划分和静态数据划分;根据程序设计模式的不同可以分为主从模式 和对等模式。1)数据划分方式(1)动态数据划分法。动态数据划分方式就是根据任务进行分片。在构建决策树之前,主处理机上存储着 整个训练数据集。假设当前系统中有可供运
8、行的n台处理机,则要将训练数据集划分为 n个训练子集,主处理机将划分好的n个训练子集分配给包含自己在内的n台处理机。这 n台处理机接收到训练子集后,并行地构建决策树的子树。主处理机重复上面的过程,为完成任务的处理机分配训练集直至所有的处理机都得到任务。)7.1分类算法第7章常用大数据挖掘算法优化改进(2)静态数据划分法。为了解决动态数据方式需要各处理机之间大量通信和频繁数据移动的缺点,给出了 静态数据划分方式。静态数据划分方式又可以分为横向数据划分和纵向数据划分。横向划分方式。横向数据划分方式是指将训练数据集进行水平分割,各个处理机保存的训练数据子 集的大小一样。假设训练数据集为N,处理机的个
9、数为m,则每个处理机处理的数据集 大小为N/m。每个处理机按照同样的扩展策略负责统计本地数据,获取并计算每个属 性分裂点相关的信息,各个处理机之间需要互相通信,按照算法所采用的最佳属性测试 标准,找出最佳属性和分裂点。在划分数据集到各子节点的过程中,各处理机只对本机 数据进行划分。纵向划分方式。纵向划分就是将一个或若干个完整的属性列表分配给一个单独的处理机进行处理,每个处理机并行地完成一个或者多个属性分裂点相关信息的计算过程。)7.1分类算法第7章常用大数据挖掘算法优化改进2)程序设计模式(1)主从模式。基于主从模式前并行决策树方法中选择一个处理机运行主进程,其余处理机运行从 进程。各从进程之
10、间不相互通信,也不要求进行同步。在主从模式下,主处理机先将训练数据集横向划分后平均分配到N个从处理机上,各 从处理机接收数据后并行统计和计算各分裂点的信息;然后,各从处理机把结果信息传 送给主处理机,主处理机综合各从处理机的结果信息,得出最佳分裂属性;最后,主处 理机根据最佳分裂属性的分裂结果形成哈希表后发送到各从处理机上,从处理机再根据 哈希表分割本机上的数据子集。(2)对等模式。在对等模式下,系统中所有处理机都是对等的,没有主从之分,处理器之间通过相 互通信完成决策树的创建。)7.1分类算法第7章常用大数据挖掘算法优化改进2.决策树中C4.5算法并行化对于C4.5决策树分类算法,如果给定数
11、据集和属性集,在构造树的过程中需要计算 所有剩余属性各自对应的分裂指标值,此过程就需要对数据集进行划分,耗时最长,此 时可以利用M叩Reduce并行框架,可大大缩短时间。根据划分结果,分别计算各属性 对应的分裂指标值,从中找出最佳的分裂属性,以此属性为节点,再根据此属性的取值,进行分枝,递归地进行即可得到一颗完整的决策树。对于经典的C4.5算法,基于MapReduce的并行算法,在构造决策树时,分裂指标的 计算方法相同,所以逻辑上若数据集相同,它们构造的决策树应该相同,只是 MapReduce是一并行计算框架,数据集较大时,执行效率高,而经典的决策树算法对 大数据却无能为力。基于Hadoop平
12、台的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表示,则在加权朴素贝叶斯算法分类模型中权值表示为:叱=卬丫)
13、=/二一J公式中四就作为分类表中第i个条件属性的权值系数。基于权值系数的改进朴素贝叶 斯算法的实现关键在于求解各条件属性与决策属性之间的相关系数。其算法的具体描述 步骤见数据挖掘一书的第159页。)7.1分类算法第7章常用大数据挖掘算法优化改进7.1.4 支持向量机并行优化改进1.并行支持向量机发展常见的并行支持向量机设计模式主要有分组式、级联式、反馈式和混合式4种。1)分组式并行支持向量机(GroupedPSVM)设计思路是:将原始训练集TD按照一定原则切分成n个子训练样本集,每个子训练 样本集中均匀分布着各类样本,之后利用Map操作在集群各节点上并行训练这n个子训 练样本集,训练结果为n个
14、子支持向量集,最后采用Reduce简单地合并n个子支持向量 集,从而得到全局最优支持向量集。2)级联式并行支持向量机(CascadePSVM)同样采用数据分割的思想,通过并行处理样本子集节省大量时间,对子样本集的合 并并非像分组式那样全部合并,而是两两合并子集按照分而治之的原则进行再次训练,直至最终得到全局支持向量模型。将原始训练集TD按照一定原则切分成n个子训练样本 集(n为偶数,且n=2),SV为训练子样本集所得的支持向量。)7.1分类算法第7章常用大数据挖掘算法优化改进3)反馈式并行支持向量机(FeedbackPSVM)在CascadePSVM的基础上引入反馈,即将最后一步得到的全局支持
15、向量反馈到初始 数据子集中进行再次训练,从而避免不合理的数据划分对分类模型性能产生的潜在影响,该策略以迭代的方式进行,通过判断迭代停止条件来终止迭代,从而提高训练精度。4)混合式并行支持向量机(HybridPSVM)常见的混合式并行SVM是分组式和级联式并行SVM的某种组合,该模型先将原始训 练样本集分成n个子集,分别对这些子集进行训练生成各子集的支持向量,这一步与分 组式SVM一样。之后根据预设值k,将这些支持向量合并到k个子集,再次并行训练后 得到最终结果,k个子集中,每个子集含有n/k个原始训练样本子集,这一步并非像分 组SVM整体合并,也不像级联SVM两两合并,而是选取适合的子集数进行
16、合并。最后 合并这些支持向量,得到最终的SVM分类模型。)7.1分类算法第7章常用大数据挖掘算法优化改进2.反馈式并行支持向量机算法实现反馈式并行支持向量机就是将原始训练数据集 分块,通过并行训练子样本集加速全局支持向量的 训练速度,为消除初始数据集划分对分类器性能和 训练结果的潜在影响,特地引入迭代反馈机制,通 过反馈,将本次迭代的结果返回初始分类器进行调 整和更新,从而进一步提高分类准确率。设计和实现基于M a p Red u ce编程框架的反馈式 并行支持向量机时,需要格外重视数据集的划分和 如何迭代这两个问题。右图给出了FeedBackSVM 的流程图。高级大数据人才培养丛书之一,大数
17、据挖掘技术与应用第七章常用大数据挖掘算法优化改进7分类算法7.2聚类算法7二3关联规则 习题)7.2聚类算法第7章常用大数据挖掘算法优化改进聚类就是对大量未知标注的数据集,按数据的内在相似性将数据集划分为多个类别,使类别内的数据相似度较大而类别间的数据相似度较小。7.2.1 聚类分析研究的主要内容及算法应用1.目前聚类分析研究的主要内容(1)从对传统的聚类分析方法所做的总结来看,不管是k-means方法,还是CURE 方法,在进行聚类之前都需要用户事先确定要得到的聚类的数目。然而在现实数据中,聚类的数目是未知的,通常要经过不断的实验来获得合适的聚类数目,得到较好的聚类 结果。(2)传统的聚类方
18、法一般都是适合于某种情况的聚类,没有一种方法能够满足各种 情况下的聚类。因此如何解决这个问题成为当前的一个研究热点,有学者提出将不同的 聚类思想进行融合以形成新的聚类算法,从而综合利用不同聚类算法的优点,在一次聚 类过程中综合利用多种聚类方法,能够有效地缓解这个问题。r L coni)7.2聚类算法第7章常用大数据挖掘算法优化改进(3)随着信息时代的到来,对大量的数据进行分析处理是一个很庞大的工作,这就 关系到一个计算效率的问题。有文献提出了一种基于最小生成树的聚类算法,该算法通 过逐渐丢弃最长的边来实现聚类结果,当某条边的长度超过了某个阈值,那么更长边就 不需要计算而直接丢弃,这样就极大地提
19、高了计算效率,降低了计算成本。(4)处理大规模数据和高维数据的能力有待于提高。目前许多聚类方法处理小规模 数据和低维数据时性能比较好,但是当数据规模增大,维度升高时,性能就会急剧下降,而现实生活中的数据大部分又都属于规模比较大、维度比较高的数据集。有文献提出了 一种在高维空间挖掘映射聚类的方法PCKA,它从多个维度中选择属性相关的维度,去 除不相关的维度,沿着相关维度进行聚类,以此对高维数据进行聚类。(5)目前的许多算法都只是理论上的,经常处于某种假设之下,比如聚类能很好地 被分离,没有突出的孤立点等,但是现实数据通常是很复杂的,噪声很大,因此如何有 效地消除噪声的影响,提高处理现实数据的能力
20、还有待进一步提高。)7.2聚类算法第7章常用大数据挖掘算法优化改进2.聚类算法的应用聚类主要应用于模式识别中的语音识别、字符识别等,机器学习中的聚类算法应用 于图像分割和机器视觉,图像处理中聚类用于数据压缩和信息检索。聚类的另一个主要 应用是数据挖掘(多关系数据挖掘)、时空数据库应用(GIS等)、序列和异类数据分 析等,聚类分析对生物学、心理学、考古学、地质学、地理学以及市场营销等研究也都 有重要作用。30)7.2聚类算法第7章常用大数据挖掘算法优化改进典型的聚类过程主要包括数据(或称之为样本或模式)准备、特征选择、特征提取、接近度计算和聚类(或分组)、对聚类结果进行有效性评估等步骤。典型的聚
21、类过程步骤如下:1.数据准备:包括特征标准化和降维。2.特征选择:从最初的特征中选择最有效的特征,并将其存储于向量中。3.特征提取:通过对所选择的特征进行转换形成新的突出特征。4.聚类(或分组):首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量;而后执行聚类或分组。5.聚类结果评估:是指对聚类结果进行评估。评估主要有3种:外部有效性评估、内 部有效性评估和相关性测试评估。)7.2聚类算法第7章常用大数据挖掘算法优化改进7.2.2并行聚类相关技术及算法体系结构和模型1.并行聚类相关技术并行计算体系结构主要有以下四种:1)集群(Cluster)具有免费、稳定、开源的Uni
22、x和Linux操作系统的计算机集群系统,已成为当下最流 行的高性能计算平台,在高性能计算方式中占有越来越大的比重。2)对称多处理(SMP)由高速缓存Cache、处理单元、总线、交叉开头、共享内存以及输入/输出等组成。3)分布式共享存储多处理(DSM)它能够很好改善SMP的可扩展能力,当前主流的高性能计算机很多都采用这种方式。4)大规模并行处理(MPP)它是目前并行计算机发展过程的主要方向,大规模并行处理可在上万台机器上进行 并行处理,并可应用多种并行计算框架和文件存储系统等。)7.2聚类算法第7章常用大数据挖掘算法优化改进2.并行聚类算法体系结构和模型1)并行算法的基本体系结构相对于串行计算来
23、说,如果按照划分方式来分,并行计算可以划分为时间上的并行 和空间上的并行。空间上的并行主要是利用多个处理器并发计算执行的,目前主要的研 究工作是空间上的并行,而时间上的并行又叫作流水线技术。从程序和算法设计人员的 角度看,并行计算按逻辑又可分为数据并行和任务并行,数据并行的方法就是将大的数 据任务分割成若干个子任务;任务并行和数据并行相似,就是将大的任务分割成若个子 任务,这种方式要比数据并行复杂一些。2)并行计算模型并行计算模型现在没有一个统一的模型,目前计算采用的都是冯诺伊曼的串行模型,这种模型一直用到今天,其他并行模型没有冯诺伊曼式模型这么成熟和应用广泛。筛选光谱簇完成聚类)7.2聚类算
24、法第7章常用大数据挖掘算法优化改进7.2.3 kmeans聚类算法的一种改进方法聚类一直以来都是研究最广泛的学科之一。现在基于划分数据的聚类算法已经成为 数据挖掘和k-means聚类算法的热点研究对象。然而k-means聚类算法也有很多的不 足之处。1.k-means聚类算法的局限性k-means聚类算法使用了迭代的方式,后来被称为劳埃德算法。无论是在随机或使 用其他一些启发式数据时,劳埃德算法首先将输入点划分成初始值集。然后计算出每个 集合的平均点或重心。它通过关联每一个点构造一个新的分区。然后再重新计算出新的 集群点,并通过交替应用这两个步骤的算法程序,直到收敛,这是获得当前点不再开关 集
25、群,利用coresets原始数据相类似的一种算法设计。在性能方面的算法并不保证返回全局最优。该算法的结果质量在很大程度上依赖于 初始集合的数据集,并且在实践中比全局最优要差得多。由于算法的速度非常快,一个 常用的方法是运行算法几次迭代并返回最好的解到集群中去。k-means算法的一个缺点是:数据集的k数目是一个输入参数。如果选择不适合的k 值,可能会产生糟糕的结果。该算法还假定了方差集群分散的适当措施。)7.2聚类算法第7章常用大数据挖掘算法优化改进2.算法流程描述k-means聚类算法的主要流程描述步骤见下表。步 骤内 容口后个初始中心是从数据集中随机选出来的依照聚类数据对象中所求出来的平均
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据挖掘 数据挖掘课件 第7章 常用大数据挖掘算法优化改进 数据 挖掘 课件 常用 算法 优化 改进
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【曲****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【曲****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。