葛君伟，杨广欣

（重庆邮电大学计算机科学与技术学院，重庆 400065）

0 概述

聚类是将数据按照一定的相似性度量规则分为多个不同的类别，将差异小的样本尽可能聚为同一类，将差异大的样本聚为不同的类。聚类算法在处理数据之前无需指定数据集的标签信息，属于无监督的机器学习领域，被广泛应用在图像处理和模式识别等领域［1］。根据算法特点大致分为基于划分的聚类算法（如K-means 算法）、基于层次的聚类算法（如BIRCHIS 算法）、基于密度的聚类算法（如DBSCAN 算法）、基于网格的聚类算法（如STING 算法等［2］）。对于凸数据集，许多聚类算法都能获得较好的聚类效果，但是对于非凸数据集则难以识别复杂的数据集从而无法很好的聚类。由于谱聚类算法在非凸数据集上有较好的聚类效果，近年谱聚类算法的研究迅猛发展［3-4］。谱聚类算法将数据集中的每个点视为图的顶点，并将任意两点之间的相似性视为连接两个顶点的边的权重。根据图划分方法，将图分为几个不连续的子图，子图中包含的点集则是聚类后生成的簇［5］。

尽管谱聚类算法在实践中取得了良好的性能，但作为一种新的聚类方法仍处于发展阶段，有许多问题需要进一步研究。谱聚类算法的聚类性能主要由相似性矩阵的构造决定。在现有相似性矩阵的研究中，大多数研究都是基于欧几里得距离、余弦相似度或高斯核函数来评估数据点之间的相似度。文献［6］提出一种基于数据本身蕴含信息的集成度量学习方法的谱聚类算法。……