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

一种新的基于密度的聚类算法研究

作　者: 廖礼
导　师: 路永刚
学　校: 兰州大学
专　业: 计算机软件与理论
关键词: 模式识别聚类算法密度估计
分类号: TP311.13
类　型: 硕士论文
年　份: 2013年
下　载: 40次
引　用: 0次
阅　读: 论文下载

内容摘要

模式识别是机器学习中的一个基本问题,其目的是将数据对象进行分类。这里的数据对象一般与应用领域相关联,比如我们常说的图像、信号波形或者任何可以被测量且需要分类的对象。作为无监督的模式识别方法—聚类分析,是模式识别的一个重要研究领域。聚类分析算法能够深入到输入数据对象的内部,探索其群组结构。目前聚类分析已经被广泛应用于各种数据分析场合,例如计算机视觉分析、图像处理、医疗信息处理、统计分析、生物科学和心理科学等。其基本原理就是将输入的数据对象分成不同的群组,同一组中的数据对象拥有相似的特性,反之不同组中的数据对象特性相异。针对目前国内外关于聚类分析算法的研究现状,本文主要选择了一些经典算法：K-means、K-means++、Mean Shift以及DBSCAN进行了比较深入的研究。主要是对它们的内容进行了简单介绍,指出了其算法的优缺点,并针对其缺点进行了一些改进,提出了新的基于密度的聚类算法—Potential-based算法和KNN-Potential-based—算法。首先,本文介绍了模式识别的研究背景与意义,简单的分析了聚类分析的发展与应用现状,指出了聚类分析在当今科学研究中的重要地位。其次,本文就聚类分析的相关基础理论做了一个比较全面的介绍,从最基本的聚类定义及表示开始,到相似度测量,再到常见聚类方法,最后着重介绍了四种常见的聚类算法—K-means、K-means++、Mean Shift和DBSCAN。对这四种经典算法的思路及流程做了比较详细的描述,总结了这些算法的优缺点。又给出了聚类的评价函数,旨在提高聚类算法的有效性。接着,本文结合基于势能模型的聚类,对Mean Shift算法做出了相应的改进,提出了Potential-based算法。利用势能替换了Mean Shift中每个数据对象的密度估计,并且每个数据对象的移动向着势能最低的方向进行。通过理论分析和实验仿真可以看出,该算法能够识别出各种形状各种分布的簇,自动确认簇的数目,无需人为干预。尤其是对均匀分布的簇,该算法表现出了较完美的效果。最后,本文在前文介绍的势能聚类模型的基础上,结合KNN近邻算法,提出了另外一种新的基于密度的聚类算法—KNN-Potential-based算法。该算法主要创新点在于密度估计方面。通过两次密度的调整,得到最终的每个数据对象的密度,再利用此密度在一个半径球内找到密度最大的数据对象作为父辈节点,再通过父辈节点找到每个点的根节点,从而构建聚类树。通过理论分析和实验仿真可以看出,该算法不具备随机性,因而只需做一次聚类就可以找到最优聚类结果,而且能够识别出各种形状各种分布的簇,自动确认簇的数目。

全文目录

摘要  3-5
Abstract  5-10
第一章绪论  10-14
  1.1 本课题的研究背景与意义  10-11
  1.2 聚类分析的发展与应用现状  11-13
    1.2.1 聚类分析的发展  11-12
    1.2.2 聚类分析的应用  12-13
  1.3 论文的主要内容及其安排  13-14
第二章聚类分析基本概念及相关算法  14-26
  2.1 聚类的定义及表示  14
  2.2 相似度测量  14-17
  2.3 常见的聚类方法  17-19
    2.3.1 划分方法(Partitioning methods)  17
    2.3.2 层次方法(Hierarchical methods)  17-18
    2.3.3 密度方法(Density-based methods)  18
    2.3.4 基于网格方法(Grid-based methods)  18
    2.3.5 基于模型方法(Model-based methods)  18-19
  2.4 常见的聚类算法  19-25
    2.4.1 K-means算法  19-20
    2.4.2 K-means++算法  20
    2.4.3 Mean Shift算法  20-23
    2.4.4 DBSCAN算法  23-25
  2.5 本章小结  25-26
第三章聚类评价函数  26-30
  3.1 外部度量法  26-28
  3.2 内部度量法  28
  3.3 相对度量法  28-29
  3.4 本章小结  29-30
第四章基于Mean Shift的改进算法Potential-based  30-40
  4.1 势能场的基本原理  30
  4.2 基于势能的聚类模型  30-31
  4.3 问题的提出  31-32
  4.4 改进思路及实现流程  32-34
  4.5 实验平台及数据  34-35
  4.6 仿真结果及分析  35-38
  4.7 本章小结  38-40
第五章结合KNN和势能聚类模型的KNN-Potential-based聚类算法  40-50
  5.1 问题的提出  40
  5.2 相关定义  40-42
    5.2.1 初始密度  40-41
    5.2.2 修正密度  41-42
    5.2.3 簇  42
  5.3 算法的改进思路及实现流程  42-44
  5.4 实验平台及数据  44-45
  5.5 仿真结果及分析  45-49
  5.6 本章小结  49-50
第六章总结与展望  50-52
  6.1 主要结论  50
  6.2 研究展望  50-52
参考文献  52-55
在学期间的研究成果  55-56
致谢  56

一种新的基于密度的聚类算法研究

内容摘要

全文目录

相似论文