稀疏化相似矩阵并行分析及MapReduce并行实现

上传者：孙中
|
上传时间：2015-05-04
|
密次下载

稀疏化相似矩阵并行分析及MapReduce并行实现

（2）基于Hadoop MapReduce 并行优化算法性能：目前，基于Hadoop MapReduce 并行计算
近似谱聚类算法研究刚起步，国内外学者基于Hadoop MapReduce 并行计算主要侧重于优化
聚类算法性能，提高聚类算法的加速比与可扩展性，以解决不能求解海量算数据聚类问题。
研究 k-means 聚类算法特点，为获得加速比与扩展性，利用 MapReduce 并行化后部署到
Hadoop 集群运行[50]与利用Hadoop 集群Mapreduce 编程模型实现k-means 聚类算法降低大
数据聚类的时间复杂度[51]，以及利用 Combine 函数减少网络流量改进基于 MapReduce 传
统的并行k-means 聚类算法，用以分析和挖掘海量数据[52]；Plaza 等人[53]结合高光谱图像
中空间和谱信息，在基于商业用途的集群上（包括高性能并行计算体系结构：欧洲巴塞罗那
并行计算中心的分布式存储、多指令多数据的多机组等）并行化使用多信道波形变换的无监
督技术提出并行数据分析策略；Lv Z等人[54]基于MapReduce 并行编程模型并行k-means 聚
类算法聚类远程传感图像。
文献[55]是该领域的理论专著，文献[56]和[57]分别是 MapReduce 并行大规模高维数据集研
究的专著和最新的云计算分布式并行研究专著。目前，国内外基于Hadoop MapReduce 并行
聚类与谱聚类算法研究都处于刚起步状况，其发展趋势：向并行大规模高维数据的近似谱聚
类方向发展。
第三节论文工作量及主要贡献
本文在确保谱聚类聚类质量（或准确性）的前提下，为聚类大规模高维数据，对 k-means
聚类中心初始化位置选择、距离相似度近似法、相似矩阵稀疏化方法、拉普拉斯矩阵特征向
量分解、k-means 聚类算法以及Apache Hadoop 系统MapReduce 并行框架进行了深入研究，
介绍了谱聚类算法及其近似法研究现状，此外，简单介绍了基于Hadoop MapReduce 谱聚类
的发展趋势，Hadoop MapReduce 平台架构与编程模型等，并从以下三个方面开展了相关研
究工作。
一、稀疏化相似矩阵并行分析及MapReduce 并行实现
相似矩阵中元素直接决定谱图矩阵中元素的构成，因此影响谱聚类准确性。基于国内外研究
现状及发展趋势，本文在前人研究基础上，提出一种新的相似矩阵优化法---使用稀疏化
Euclidean 距离矩阵并调整为对称矩阵后，对相似矩阵列向量的离群点进行优化，并在优化
引理的前提下理论证明该方法最优解的存在，并说明其时间复杂度。论文使用该方法应用于
构建相似矩阵并基于Hadoop 集群系统下MapReduce 并行编程框架，对上述优化后的稀疏相
似矩阵进行并行算法设计与并行编程实现，在设计的过程中，分析Hadoop MapReduce 并行
前后稀疏化近似相似矩阵的时间复杂度，以及通过大规模高维数据实验验证所设计的
Hadoop MapReduce 并行算法加速比，使用实验结果阐述应用该方法的ASC 并行后的性能。
二、特征向量分解并行分析及MapReduce 并行实现
相对于聚类而言谱聚类必须对拉普拉斯矩阵进行特征向量分解，否则，得不到数据集的低阶
表示，即维简约。谱聚类算法时间复杂度正是由于其特征分解过程所产生的。针对大规模
数据集而言，从理论分析可得出：k-means 聚类的时间杂度（）相对于拉普拉斯矩阵特征
向量分解几乎可忽略不计。因此，本文在前人研究基于MapReduce 编程框架Tall and Skinny
QR 矩阵分解[58]的基础上对其进行修改，使其能够计算由近似相似矩阵求得的近似拉普拉
斯近似矩阵的特征向量分解。并设计基于Hadoop 集群系统下MapReduce 并行编程框架的并
行算法与并行编程实现，在设计的过程中，分析Hadoop MapReduce 并行前后特征向量分解
的时间复杂度，以及通过大规模高维数据实验验证所设计的Hadoop MapReduce 并行算法加
速比，使用实验结果阐述应用该设计的ASC 并行后的性能。
三、k-means 聚类算法并行分析及MapReduce 并行实现
k-means 聚类中心初始化位置决定其算法收敛时迭代次数，直接影响谱聚类计算时间。基于
国内外研究现状及发展趋势，本文基于Hadoop 集群系统下MapReduce 并行编程框架对适合

教育资源为主的文档平台

文档分类