基于本证间隙增大的K邻域加权谱聚类算法

聚类是近些年来无监督学习的热门方法之一。而谱聚类又是聚类方法研究中的热点，并且通常表现出良文章引用: 田文敏, 王晅, 田春霖. 基于本证间隙增大的K 邻域加权谱聚类算法[J]. 计算机科学与应用, 2020, 10(2): 289-302.

近些年来，聚类是无监督学习中的热门方法之一。聚类是许多应用过程中的非常重要的一环，包括机器学习，计算机视觉，信号处理，模式识别等。近些年来国内外很多研究学者已经提出了许多的聚类方法，包括基于划分的聚类(K-Means，K-Medoids) [1] [2]，基于层次的聚类(CURE) [3]，基于模糊理论的聚类(FCM) [4]， 基于密度的聚类(DBSCAN) [5]， 基于图的聚类(Spectral Clustering) [6]， 基于核的方法[7]。

其中，谱聚类和基于密度的聚类是当下比较热门的方法之一，它们通常表现出良好的聚类性能。基于密度的聚类的优点是能够找到任意形状的聚类并且对噪声具有鲁棒性。密度聚类算法假设聚类结构可以通过样本分布的紧密性来确定。通常密度聚类算法从样本密度的角度考虑样本之间的连通性，并基于可连接样本不断扩展聚类以获得最终的聚类结果。基于密度的噪声应用空间聚类(DBSCAN) [5]是一种众所周知的方法，它基于一组邻域参数(ε 和MinPts)来表征样本的数据结构。但是这两个参数ε 和MinPts 并不直观且难以选择。

谱聚类算法是一种基于图论的聚类算法[6] [8]。

谱聚类基于数据集构造无向图， 并使用非负相似矩阵表示整个无向图，从而得到一个相似度矩阵再得到拉普拉斯到矩阵，然后进行特征分解。最后通常使用K 均值算法对结果进行后处理以获得聚类指标。

谱聚类具有以下优点：(1) 易于实现；(2) 聚类结果更好， 约束更少；(3) 分割非线性可分离数据的效果具有明显的优势；(4) 具有以下优点能够在任何形状的样本空间上聚类并收敛到全局最优解。基于其受欢迎程度和上述几个优点，很多研究人员提出了许多谱聚类算法。Donath W E 等人[9]首先提出了相似矩阵的特征向量。找到相似矩阵的第二个特征向量可以将数据分为两个簇[10]。Hagen 和Kahng 在1992 年提出的比率削减在最小化类之间的相似性时引入了类尺度的平均项，并建立了基于矩阵谱分析谱聚类算法[11]。[12]提出的归一化割，解决了一类最小割中只有一个或几个孤立点的倾斜分割问题。[13]提出了NJW 算法(嵌入式特征空间上的K-means 算法)。

对于给定的数据集，谱聚类基于成对相似性将数据表征为加权无向图中的节点。谱聚类的目标是将无向加权图分为两个或多个子图，以使子图的内部节点相似而子图之间的节点是不同的。然后，使用非负相似度矩阵表示整个无向图， 再进行特征分解， 最后通过传统聚类从特征向量中获得最终的聚类分配。

总之， 相似度矩阵的构建直接影响聚类效果。

因此， 谱聚类的相似矩阵构造问题是一个关键点[14]。

通常， 通过相似矩阵获得拉普拉斯矩阵，然后直接选择对应于前k 个特征值，最后一步再进行k-means。根据矩阵扰动理论，矩阵特征值之间的差异称为本征间隙(Eigengap) [15]，矩阵扰动理论中的Davis-Kahan 定理