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

摘要

聚类作为一种重要的数据分析手段,是机器学习、模式识别等领域的研究热点。聚类的目的是把对象按照性质上的亲疏程度分成多个类或簇,使得簇内的数据具有较高相似度,簇间的数据具有较高的相异度,它不考虑先验知识或假设,因此是一种无监督的学习过程。
　　谱聚类算法是近年来广受关注的一种高性能计算方法,与传统聚类方法相比,具有能在任意形状的样本空间上聚类且收敛于全局最优解的特点,非常适合于解决许多实际应用问题,如计算机视觉、图像分割等。目前,谱聚类算法的研究仍处于初级阶段,还存在许多亟需解决的问题,如算法受高斯核尺度参数的影响较大,对噪声点较为敏感,不能利用先验信息指导聚类过程等。针对以上问题,提出了一种基于路径相似度测量的鲁棒性谱聚类算法(Robust Path-Based similarity measurement for Spectral Clustering,RPB-SC),并将此算法扩展为半监督的形式,以便利用成对限制先验信息提高聚类性能,相应的算法称为基于路径相似度测量的鲁棒性半监督谱聚类算法(Robust Path-Based similarity measurement for Semi-supervised Spectral Clustering,RPB-SSC)。具体研究内容如下:
　　①构造相似矩阵。本文将路径聚类思想引入到谱聚类算法中来,设计一种新的相似度测量函数。该函数能够避免设置全局的尺度参数,减弱尺度参数对聚类结果的影响,使相似矩阵更加符合聚类假设。
　　②算法鲁棒性研究。谱聚类算法对噪声点较为敏感,根据对样本点邻域信息的统计分析,定义了具有鲁棒性的邻域加权尺度因子,抑制噪声的影响。
　　③半监督谱聚类方法研究。尝试将成对限制先验信息引入到谱聚类算法中,并将样本层面上的有限的限制信息进行空间传播,指导聚类过程。
　　④谱聚类算法在图像分割中的应用研究。提出基于本文改进算法的彩色图像分割方法框架,实现对包含噪声的图像分割,并利用先验信息指导分割过程。
　　为验证算法的有效性,本文在多个人工数据集、真实数据集和Berkeley图像分割数据库上进行了实验,并与一些具有代表性的算法对比。实验结果表明,本文算法能有效减弱高斯核尺度参数的影响,增强对噪声点的鲁棒性,取得了良好的聚类和分割效果。