基于流形距离的聚类算法研究及其应用

论文摘要

聚类分析是一种数据缩减技术,即基于数据特征的相似性将数据聚集成不同的类,是数据挖掘中一种非常有效的工具,得到了人们广泛的关注。本论文主要从聚类算法中的相似性度量和初始化敏感问题入手,采用新的基于流形距离的相似性度量替代传统的基于欧氏距离的相似性度量,通过全局的方法选择初始聚类中心,提出两种方案解决引入流形距离带来的计算量增大问题,并将这两种聚类算法应用到聚类分析和图像分割当中。本论文取得的主要成果如下:在本文中,我们提出了一种流形聚类算法,称为基于流形距离的全局原型聚类算法（Global Prototypical Clustering Algorithm based-on Manifold Distance,GPMC）。在新算法中,聚类中心选自数据集本身,在选择每个聚类的聚类中心时,依据一种新的基于流形距离的相似性度量,该度量计算的是数据点间沿着流形的测地线距离。在确定初始聚类中心时,GPMC从优化的角度出发,使用全局的方法进行选择。对于部分人工数据集和UCI数据集的实验表明,从聚类性能和鲁棒性的角度来看,新算法在处理复杂、非凸的数据聚类问题时有效可行。在第三章中,本文提出了一种用于复杂分布数据的二阶段聚类算法（Two-Phase Clustering,TPC）,TPC包含两个阶段:首先,将数据划分为若干个球形分布的子类,每一子类用其聚类中心代表该类内的所有数据点;然后,利用可以处理复杂分布数据的流形进化聚类算法（Manifold Evolutionary Clustering Algorithm,MEC）对第一阶段得到的聚类中心进行类别划分;最后,综合两次聚类结果整理得到最终聚类结果。该算法基于改进的K均值算法和MEC算法。在进化聚类算法的基础上加入了流形距离,使算法能胜任复杂数据聚类。同时,新算法降低了引入流形距离所带来的计算量。我们在部分人工数据集和UCI数据集上测试了二阶段聚类算法,实验结果可以说明,无论对于简单或复杂、凸或非凸的数据,TPC都表现出良好的聚类性能。在第四章中,我们以基于流形距离的全局原型聚类算法为基础,结合形态学方法,提出一种用于图像分割的新方法,称为基于分水岭与流形距离的全局原型聚类图像分割算法（Global Prototypical Clustering Image Segmentation Algorithm based-on Watershed and Manifold Distance,WGPMC）。新算法首先使用分水岭算法的改进算法——内外标记的分水岭算法,对图像进行粗分割,将图像分为许多小区域;接下来,以小区域为单位,取得其图像特征,使用GPMC进行二次分割;对应两次分割的结果,得到带分割图像的最终分割结果。我们将新算法用于多种图像分割任务,包括SAR图像和自然图像,实验表明新算法可以成功地用于多种图像分割,具有良好的图像分割性能。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 背景介绍
• 1.2 聚类算法的研究现状与发展前景
• 1.2.1 聚类的定义
• 1.2.2 聚类分析的定义
• 1.2.3 聚类算法概况
• 1.2.4 传统聚类算法存在的问题
• 1.3 论文的主要工作及结构安排
• 第二章 基于流形距离的全局原型聚类算法
• 2.1 引言
• 2.2 流形距离
• 2.3 初始聚类中心全局选择策略
• 2.4 基于流形距离的全局原型聚类算法
• 2.5 实验结果分析.
• 2.5.1 人工数据集
• 2.5.2 UCI 数据集
• 2.5.3 鲁棒性分析
• 2.6 小结
• 第三章 复杂分布数据的二阶段聚类算法
• 3.1 引言
• 3.2 复杂分布数据的二阶段聚类算法
• 3.2.1 基于欧氏距离的粗聚类
• 3.2.2 基于流形距离的精细聚类
• 3.3 实验结果分析
• 3.3.1 人工数据集
• 3.3.2 UCI 数据集
• 3.3.3 运行时间比较
• 3.3.4 鲁棒性分析
• 3.4 小结
• 第四章 基于分水岭与流形距离的全局原型聚类图像分割
• 4.1 引言
• 4.2 基于聚类分析的图像分割
• 4.3 分水岭算法
• 4.3.1 分水岭算法原理及特性
• 4.3.2 分水岭变换的数学描述
• 4.3.3 标记分水岭算法
• 4.4 基于分水岭与GPMC 的图像分割
• 4.5 实验结果分析
• 4.5.1 SAR 图像
• 4.5.2 自然图像
• 4.6 小结
• 第五章 总结与展望
• 参考文献
• 致谢
• 硕士期间的学术成果