文档介绍：分类号密级 U D C 学校代码硕士研究生学位论文基于Hadoop MapReduce并行近似谱聚类算法研究与实现学院(部、所):信息学院专业:计算机应用技术研究方向:计算机网络与分布式计算姓名:杨煜导师:赵成贵教授论文起止时间: 2013年5月~2014年5月学位论文原创性声明声明:本人所呈交的学位论文,是本人在导师的指导下,独立进行研究工作所取得的成果。尽我所知,除文中已经注明引用的内容外, 本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。论文作者签名: 日期: 年月日学位论文版权使用授权书本人完全了解云南财经大学有关保留、使用学位论文的规定,即: 学校有权保留并向国家有关部门或机构送交论文和论文电子版,允许学位论文被查阅或借阅;学校可以公布学位论文的全部或部分内容, 可以采用影印、缩印或其它复制手段保存、汇编、发表学位论文;授权学校将学位论文的全文或部分内容编入、提供有关数据库进行检索。(保密的学位论文在解密后遵循此规定) 论文作者签名: 导师签名: 日期: 年月日日期: 年月日摘要 I 摘要随着互联网信息呈现几何级数增长,对与之产生的大规模高维数据的谱聚类的计算时间和内存使用提出了新的挑战。Hadoop MapReduce并行近似谱聚类算法为减少计算时间和内存使用而展开研究,首先,在构建近似谱聚类算法的稀疏化相似矩阵过程中,研究t最近邻稀疏化相似矩阵法和Nystr?m低阶子矩阵抽样近似相似矩阵法,侧重因在t最近邻稀疏化相似矩阵使用主观性设置扩大了参数t的近邻范围,而造成的稀疏化相似矩阵中离群点对近似谱聚类算法质量的影响。提出一种基于t最近邻近似相似矩阵离群点优化的解决方法,通过证明含有离群点的t最近邻近似相似矩阵在该优化方法中存在最优解,并把该方法应用于近似谱聚类算法,提出优化的近似谱聚类算法,以期提高大规模高维数据近似谱聚类的质量。此外,论文在近似谱聚类算法设计中使用?最近邻粗糙集模型选择k-means初始化聚类中心位置,避免聚类大规模高维数据时,近似谱聚类算法获得空聚类或非最佳聚类的结果。通过将上述近似谱聚类算法与经典的基于正交化Nystr?m低阶子矩阵抽样近似相似矩阵谱聚类算法和基于t 最近邻稀疏化近似相似矩阵谱聚类算法进行辅助对比实验,结果显示虽然近似相似矩阵优化时间较高,但是其聚类精确度优于后者。论文主要设计并实现Hadoop分布式文件系统MapReduce并行计算编程模型下近似谱聚类算法对大规模高维数据的聚类。通过研究Mapper和Reducer并行编程流程及Hadoop MapReduce并行算法中相互依赖步骤分解,分别研究并设计基于MapReduce优化离群点的t 最近邻近似相似矩阵、Laplacian特征分解和基于?最近邻初始化聚类中心位置的k-means并行策略与map()和reduce() 函数, 并分析了Hadoop MapReduce并行前后各自的时间复杂度,其中所设计的并行策略与依赖步骤的分解处理也为机器学****数据挖掘、模式识别、信息检索、Web 数据分析、计算机视觉、医学成像、信号与图形图像处理以及生物信息学等领域提供一种分析大规模高维数据的参考思路。通过在12台Dell 2161服务器构成的Hadoop集群使用UCI Bag of Words数据集对所设计的MapReduce近似谱聚类算法的性能和聚类质量进行验证,实验结果显示所设计的并行近似谱聚类算法摘要 II 达到了一定的预期结果,并行实验中使用经典的谱聚类评估标准也进一步验证了所设计的并行近似谱聚类算法在处理大规模高维数据上的正确性和有效性。关键词:Hadoop分布式系统;MapReduce并行计算;近似谱聚类算法;稀疏化近似相似矩阵;Laplacian特征分解;k-means初始化方法;大规模高维数据 Abstract III Abstract Withthe increasing exponentially of the scale of data on the , spectral clustering suffers from a new challenge in putational time and memory use for large-scale high-dimensional on the challenge, Hadoop MapReduce parallel approximate spectral clustering algorithm starts to embrace. First of and foremost, t