基于路径相似度测量的谱聚类算法研究.doc

基于路径相似度测量的谱聚类算法研究
重庆大学硕士学位论文
(学术学位)
学生姓名:李泽明
指导教师:范敏副教授
专业:控制科学与工程
学科门类:工学
重庆大学自动化学院
二 O 一四年四月
Study of Path-based Similarity Measurement
for Spectral Clustering
A Thesis Submitted to Chongqing University
in Partial Fulfillment of the Requirement for the
Master’s Degree of Engineering
By
Li Zeming
Supervised by Ass. Prof. Fan Min
Specialty:Control Science and Engineering
College of Automation of Chongqing
University, Chongqing, China
April, 2014
重庆大学硕士学位论文中文摘要
摘要
聚类作为一种重要的数据分析手段,是机器学习、模式识别等领域的研究热
点。聚类的目的是把对象按照性质上的亲疏程度分成多个类或簇,使得簇内的数
据具有较高相似度,簇间的数据具有较高的相异度,它不考虑先验知识或假设,
因此是一种无监督的学习过程。
谱聚类算法是近年来广受关注的一种高性能计算方法,与传统聚类方法相比,
具有能在任意形状的样本空间上聚类且收敛于全局最优解的特点,非常适合于解
决许多实际应用问题,如计算机视觉、图像分割等。目前,谱聚类算法的研究仍
处于初级阶段,还存在许多亟需解决的问题,如算法受高斯核尺度参数的影响较
大,对噪声点较为敏感,不能利用先验信息指导聚类过程等。针对以上问题,提
出了一种基于路径相似度测量的鲁棒性谱聚类算法(Robust Path-Based similarity
measurement for Spectral Clustering,RPB-SC),并将此算法扩展为半监督的形式,
以便利用成对限制先验信息提高聚类性能,相应的算法称为基于路径相似度测量
的鲁棒性半监督谱聚类算法( Robust Path-Based similarity measurement for
Semi-supervised Spectral Clustering,RPB-SSC)。具体研究内容如下:
①构造相似矩阵。本文将路径聚类思想引入到谱聚类算法中来,设计一种新
的相似度测量函数。该函数能够避免设置全局的尺度参数,减弱尺度参数对聚类
结果的影响,使相似矩阵更加符合聚类假设。
②算法鲁棒性研究。谱聚类算法对噪声点较为敏感,根据对样本点邻域信息
的统计分析,定义了具有鲁棒性的邻域加权尺度因子,抑制噪声的影响。
③半监督谱聚类方法研究。尝试将成对限制先验信息引入到谱聚类算法中,
并将样本层面上的有限的限制信息进行空间传播,指导聚类过程。
○4 谱聚类算法在图像分割中的应用研究。提出基于本文改进算法的彩色图像
分割方法框架,实现对包含噪声的图像分割,并利用先验信息指导分割过程。
为验证算法的有效性,本文在多个人工数据集、真实数据集和 Berkeley 图像
分割数据库上进行了实验,并与一些具有代表性的算法对比。实验结果表明,本
文算法能有效减弱高斯核尺度参数的影响,增强对噪声点的鲁棒性,取得了良好
的聚类和分割效果。
关键词:谱聚类,相似度测量,基于路径聚类,鲁棒性,半监督聚类
I
重庆大学硕士学位论文英文摘要
ABSTRACT
As an important means of data analysis, clustering is one of the major research in
the field of machine learning and pattern recognition. The purpose of clustering is to
divide a dataset into natural groups so that data points in the same group are similar
while data points in different groups are dissimilar to each other. It has been
traditionally viewed as an unsupervised method for data analysis without use of prior
knowledge or assumpt