学位论文 > 优秀研究生学位论文题录展示

基于Hadoop的聚类算法的研究与应用

作　者: 尹超
导　师: 王民
学　校: 西安建筑科技大学
专　业: 信号与信息处理
关键词: 聚类 MapReduce CURE Binary-Positive 重复删除技术直方图
分类号: TP311.13
类　型: 硕士论文
年　份: 2013年
下　载: 36次
引　用: 0次
阅　读: 论文下载

内容摘要

随着计算机信息技术的迅猛发展，人们能够接触的信息越来越多，数据的重要性也与日俱增。而数据具有海量、多样化、异构等特征，使得传统的聚类分析方法很难满足对海量数据的分析和处理，因此高效的聚类技术应运而生。本文首先综述了现有的聚类技术与并行化编程模型MapReduce，随后提出了基于MapReduce的并行化聚类算法。这一算法建立在MapReduce并行框架的基础之上，可以通过分布式计算框架，更好地将原本计算复杂度较高、内存消耗较大的聚类算法直接应用于大规模数据聚类上。（1）当CURE算法在处理不均匀的海量数据时，针对随机抽样不具有代表性的问题，提出了一种健壮的并行化改进算法。该算法使用Binary-Positive算法得到原始数据的有效属性，并利用MapReduce并行框架对有效数据进行层次聚类，从而实现了正确率与效率的一种权衡。实验分析表明，改进后的CURE算法具有更高的执行效率，并且聚类效果良好；（2）对于大规模数据库中的的重复图片，本文首先使用颜色直方图细化的方法从图像中提取特征值，然后使用基于MapReduce的k-means算法对特征值进行聚类，最后再使用重复数据删除技术对图片进行清理，以达到节约磁盘空间，提高写入性能和节约网络带宽的目的；（3）本文对MapReduce和MPI的k-means算法进行了设计，并对其性能进行了深入的分析。

全文目录

摘要  3-4
ABSTRACT  4-9
1 绪论  9-14
  1.1 课题背景及意义  9-10
  1.2 国内外研究现状  10-12
    1.2.1 国外研究现状  10-11
    1.2.2 国内研究现状  11-12
  1.3 研究内容  12-13
  1.4 本文结构  13-14
2 聚类算法与 Hadoop 介绍  14-23
  2.1 聚类的定义  14
  2.2 经典聚类算法  14-19
    2.2.1 基于层次的聚类方法  14-15
    2.2.2 基于划分的聚类方法  15-17
    2.2.3 基于网格的聚类方法  17
    2.2.4 基于密度的聚类方法  17-18
    2.2.5 基于模型的聚类方法  18-19
  2.3 Hadoop 相关技术介绍  19-21
    2.3.1 Hadoop 简介  19-20
    2.3.2 云计算简介  20-21
  2.4 MapReduce 并行编程框架介绍  21-22
  2.5 与网格计算的对比  22
  2.6 本章小结  22-23
3 Binary-Positive 算法下的并行化 CURE 算法  23-35
  3.1 背景  23-24
  3.2 CURE 算法分析  24-25
    3.2.1 CURE 算法思想  24
    3.2.2 随机抽样  24-25
    3.2.3 数据的划分与标记  25
  3.3 Binary-Positive 算法下的并行化 CURE 算法  25-31
    3.3.1 类间距离的计算  25-27
    3.3.2 Binary-Positive 预处理  27
    3.3.3 MapReduce 下的 CURE 算法  27-31
  3.4 实验及结果分析  31-34
    3.4.1 实验环境  31
    3.4.2 数据集  31-32
    3.4.3 实验结果  32-33
    3.4.4 实验分析  33
    3.4.5 并行算法分析  33-34
    3.4.6 类似工作分析  34
  3.5 本章小结  34-35
4 聚类算法在重复数据删除技术中的研究与应用  35-43
  4.1 图像特征提取  35-36
    4.1.1 颜色直方图  35-36
    4.1.2 直方图细化  36
    4.1.3 特征提取  36
  4.2 基于 MapReduce 的 k-means 算法在图像聚类中的应用  36-40
    4.2.1 k-means 算法分析  37-38
    4.2.2 基于 MapReduce 的 k-means 算法框架  38-39
    4.2.3 图像聚类的设计与实现  39-40
  4.3 重复数据删除  40-41
    4.3.1 Data deduplication 技术  40-41
    4.3.2 重复数据删除的过程  41
  4.4 实验结果  41-42
  4.5 本章小结  42-43
5 MapReduce 与 MPI 在聚类算法中的对比  43-50
  5.1 MPI 介绍  43-45
    5.1.1 MPI 的并行应用模式  43
    5.1.2 MPI 编程模型  43-45
  5.2 基于 MPI 的 k-means 聚类算法  45-48
    5.2.1 基于 MPI 的 k-means 聚类算法设计  45-46
    5.2.2 基于 MP I 旳并行 K-Means 算法实现  46-48
  5.3 基于 MapReduce 的 k-means 算法与基于 MPI 的 k-means 算法的比较  48-49
  5.4 本章小结  49-50
6 总结与展望  50-51
  6.1 论文工作总结  50
  6.2 下一步工作与展望  50-51
致谢  51-52
参考文献  52-55
作者攻读硕士期间研究成果  55

基于Hadoop的聚类算法的研究与应用

内容摘要

全文目录

相似论文