《稀疏化相似矩阵并行分析及MapReduce并行实现》由会员分享，可在线阅读，更多相关《稀疏化相似矩阵并行分析及MapReduce并行实现（10页珍藏版）》请在金锄头文库上搜索。
1、（2）基于 Hadoop MapReduce 并行优化算法性能：目前，基于 Hadoop MapReduce 并行计算近似谱聚类算法研究刚起步，国内外学者基于 Hadoop MapReduce 并行计算主要侧重于优化聚类算法性能，提高聚类算法的加速比与可扩展性，以解决不能求解海量算数据聚类问题。研究 k-means 聚类算法特点，为获得加速比与扩展性，利用 MapReduce 并行化后部署到 Hadoop 集群运行50 与利用 Hadoop 集群 Mapreduce 编程模型实现 k-means 聚类算法降低大数据聚类的时间复杂度51，以及利用 Combine 函数减少网络流量改进基于MapR
2、educe 传统的并行 k-means 聚类算法，用以分析和挖掘海量数据52；Plaza 等人53结合高光谱图像中空间和谱信息，在基于商业用途的集群上（包括高性能并行计算体系结构：欧洲巴塞罗那并行计算中心的分布式存储、多指令多数据的多机组等）并行化使用多信道波形变换的无监督技术提出并行数据分析策略；Lv Z 等人54基于 MapReduce 并行编程模型并行 k-means 聚类算法聚类远程传感图像。文献55是该领域的理论专著，文献56和57 分别是 MapReduce 并行大规模高维数据集研究的专著和最新的云计算分布式并行研究专著。目前，国内外基于 Hadoop MapReduce 并行聚类
3、与谱聚类算法研究都处于刚起步状况，其发展趋势：向并行大规模高维数据的近似谱聚类方向发展。第三节 论文工作量及主要贡献本文在确保谱聚类聚类质量（或准确性）的前提下，为聚类大规模高维数据，对 k-means聚类中心初始化位置选择、距离相似度近似法、相似矩阵稀疏化方法、拉普拉斯矩阵特征向量分解、k-means 聚类算法以及 Apache Hadoop 系统 MapReduce 并行框架进行了深入研究，介绍了谱聚类算法及其近似法研究现状，此外，简单介绍了基于 Hadoop MapReduce谱聚类的发展趋势，Hadoop MapReduce 平台架构与编程模型等，并从以下三个方面开展了相关研究工作。一
4、、稀疏化相似矩阵并行分析及 MapReduce 并行实现相似矩阵中元素直接决定谱图矩阵中元素的构成，因此影响谱聚类准确性。基于国内外研究现状及发展趋势，本文在前人研究基础上，提出一种新的相似矩阵优化法-使用 稀疏化Euclidean 距离矩阵并调整为对称矩阵后，对相似矩阵列向量的离群点进行优化，并在优化引理的前提下理论证明该方法最优解的存在，并说明其时间复杂度。论文使用该方法应用于构建相似矩阵并基于 Hadoop 集群系统下 MapReduce 并行编程框架，对上述优化后的稀疏相似矩阵进行并行算法设计与并行编程实现，在设计的过程中，分析 Hadoop MapReduce并行前后稀疏化近似相似矩
5、阵的时间复杂度，以及通过大规模高维数据实验验证所设计的Hadoop MapReduce 并行算法加速比，使用实验结果阐述应用该方法的 ASC 并行后的性能。二、特征向量分解并行分析及 MapReduce 并行实现相对于聚类而言谱聚类必须对拉普拉斯矩阵进行特征向量分解，否则，得不到数据集的低阶表示，即维简约。谱聚类算法时间复杂度 正是由于其特征分解过程所产生的。针对大规模数据集而言，从理论分析可得出：k-means 聚类的时间杂度（ ）相对于拉普拉斯矩阵特征向量分解几乎可忽略不计。因此，本文在前人研究基于 MapReduce 编程框架 Tall and Skinny QR 矩阵分解58的基础上对
6、其进行修改，使其能够计算由近似相似矩阵求得的近似拉普拉斯近似矩阵的特征向量分解。并设计基于 Hadoop 集群系统下 MapReduce 并行编程框架的并行算法与并行编程实现，在设计的过程中，分析 Hadoop MapReduce 并行前后特征向量分解的时间复杂度，以及通过大规模高维数据实验验证所设计的 Hadoop MapReduce并行算法加速比，使用实验结果阐述应用该设计的 ASC 并行后的性能。三、k-means 聚类算法并行分析及 MapReduce 并行实现k-means 聚类中心初始化位置决定其算法收敛时迭代次数，直接影响谱聚类计算时间。基于国内外研究现状及发展趋势，本文基于 H
7、adoop 集群系统下 MapReduce 并行编程框架对适合聚类大规模数据集的 粗糙集模型框架下基于数据密度 Astrahan 的 k-means 聚类中心初始化位置选择方法进行算法时间复杂度及方法中迭代步骤之间依赖性进行分析，设计基于该方法的 k-means 聚类算法并行策略并编程实现。在设计的过程中，分析 Hadoop MapReduce 并行前后特征向量分解的时间复杂度，以及通过大规模高维数据集实验验证所设计的 Hadoop MapReduce 并行算法加速比，使用实验结果阐述应用该设计的 ASC 并行后的性能。在设计的过程中，分析 Hadoop MapReduce 并行前后 k-me
8、ans 聚类算法的时间复杂度，以及通过大规模高维数据集实验验证所设计的 Hadoop MapReduce 并行算法加速比，使用实验结果阐述应用该设计的 ASC 并行后的性能。论文基于 Hadoop MapReduce 谱聚类发展趋势文献综述，对 Hadoop 集群系统下 MapReduce并行编程框架下 k-means 聚类进行设计，以上述 粗糙集模型框架下基于数据密度 Astrahan 的 k-means 聚类中心初始化位置并行计算结果的分布式文件为其初始化中心位置，同时设计 Combine 函数减少网络通信，实现本地相同 Map 任务中同一 key 值归并的功能。论文分析该并行算法，并通过
9、理论证明与并行算法加速比和可扩展性实验结果阐述并行化后该方法的性能。第四节 论文结构第一章，绪论。阐述论文研究背景与意义；综述谱聚类算法及其近似法的研究现状及基于Hadoop MapReduce 谱聚类发展趋势；并叙述论文研究的工作量及主要贡献。第二章，Hadoop MapReduce 技术框架概述与谱聚类近似法基本概念与理论分析。详细阐述分布式文件系统 HDFS 系统架构与 MapReduce 并行编程模型；探讨了谱聚类近似法基本概念理论，涉及近似谱聚类算法基本理论、k-means 聚类中心初始化方法、谱聚类常用近似技术研究与特征向量分解。第三章，近似谱聚类算法研究与设计。详细论述了近似谱聚
10、类算法的设计思路，同时，证明了所提出的优化近似相似矩阵最优解的存在；描述了应用优化近似相似矩阵后谱聚类算法步骤；最后，通过小数据集的 Matlab 实验验证所提出的近似谱聚类算法的性能和与经典近似谱聚类的对比实验，以及与其它近似谱聚类算法的对比分析。第四章，MapReduce 并行计算近似谱聚类算法研究与设计。分析了 Hadoop MapReduce 并行算法设计理念及算法中迭代步骤的分解；根据分析结果，详细研究了稀疏化近似相似矩阵、基于 MapReduce 的拉普拉斯特征向量分解和 k-means 及其初始化聚类中心并行策略，及其 Hadoop MapReduce 并行编程框架下 Mappe
11、r 和 Reducer 阶段的设计（或 Combiner 阶段设计） 。第五章，实验与结果评估分析。概述了实验的目的与设计；详细叙述了实验平台搭建和Hadoop MapReduce 分布式环境配置；阐述了实验评估标准；描述了实验过程中所使用的大规模高维数据并进行了并行近似谱聚类算法的实验；本章最后，通过阐述的实验评估标准对基于 Hadoop MapReduce 近似谱聚类算法实验的聚类质量和加速比性能进行分析。第六章，总结与展望。总结了论文主要研究内容与贡献，同时，指出论文基于 Hadoop MapReduce 并行近似谱聚类算法研究的不足之处；展望进一步工作与未来研究的发展趋势。第二章 Ha
12、doop MapReduce 技术框架概述与谱聚类近似法基本概念与理论分析第一节 Hadoop MapReduce 技术框架概述Hadoop MapReduce 是使用分布式文件系统 HDFS 执行 MapReduce 并行编程框架的开源软件，其基本架构由 HDFS 和 MapReduce 并行计算编程模型组成，数据以 HDFS 文件格式分布式存储在 Hadoop 集群系统中，是目前进行大规模数据分析主流技术框架 59。HDFS 主要负责分布式存储大规模海量数据；MapReduce 则负责并行计算存储在 Hadoop 分布式文件系统中的分块数据。一、分布式文件系统 HDFS 系统架构（1） H
13、DFS 系统架构简介 HDFS 分布式文件系统基础架构采用主从式，其设计灵感最初来自 Google 文件系统60 ，旨在利用部署在廉价机器上 Hadoop 集群系统，可靠地分布式存储大规模数据文件且以流式读写为主，具有数据吞吐量访问的容错功能。如图 2.1 HDFS 系统基础架构图所示，HDFS 系统架构主要组件包括 NameNode、SecondNameNode、DataNode 与 JobClient，一个Hadoop 集群系统中只有一个 NameNode 节点与一定数目的 DataNode 节点。图 2.1 HDFS 系统基础架构图（2）NameNode 、DataNode 与 Seco
14、ndNameNodeJobClient（用户作业 MapReduce 应用程序，通常包括 Map、Reduce 和 JobConf 函数）通过负责管理文件系统的 NameNode 与负责数据存储的 DataNode 交互实现 HDFS 中分布式文件的访问。其中，NameNode 配置在 masters 节点上，主要维护 HDFS 系统目录树和管理存储子系统控制单元（如图 2.1 所示的 Block）的元数据信息，以及监控 Hadoop 集群中所有DataNode 节点运行状态并根据配置文件备份失效 DataNode 节点上的数据文件；DataNode配置在 sladves 节点上，主要负责分布
15、式数据文件存储并通过周期性地向 NameNode 发送心跳包汇报其存储信息状态。SecondNameNode 通常也配置在 masters 上，其设计目的是减少NameNode 负载，主要负责合并 HDFS 中元数据镜像文件（fsimage）与 HDFS 中改动的日志文件（editlog）并将其最终结果传输给 NameNode。（3）HDFS 容错性机制HDFS 通过冗余备份存放机制、心跳检验机制等容错性机制确保在故障条件下分布式文件存储的完整性与可靠性。Hadoop 系统集群通过交换机通信部署在多个机架上。就带宽而言，显然，不同机架节点通信带宽小于机架内节点的通信带宽，且考虑到机架与节点的可
16、靠性，冗余备份存放机制分别将副本存储在同一节点、机架内不同节点以及不同机架中；心跳检验机制是指 DataNode 定期向 NameNode 发送心跳包并汇报其存储状态（空闲、处理中、完成） 。如果心跳包发生丢包现象，NameNode 就标记 DataNode 宕机，NameNode 不再向其发送访问请求且存储在宕机 DataNode 上的所有数据将被复制到其它节点。二、MapReduce 并行编程模型（1）MapReduce 简介MapReduce 是 Hadoop MapReduce 引擎在集群中分布式分配作业的关键算法61 。MapReduce 诞生于搜索领域，由 Google 在 2004 年首次提出62，主要解决搜索引擎抓取网页和索引过程中面临海量大规模数据文件存储需求和索引问题，以及数据计算能力与存储能力可扩展性差问题，因此，受到并行处理密集型数据计算和大规模高维数据分析领域青睐。MapReduce 并行计算存储在 HDFS 中的分布式数据文件，其并行编程模型采用主从式架构，其主要组
