谱聚类算法解析：从规范割集到图分割

"规范割集准则-谱聚类算法" 谱聚类是一种基于图论的聚类方法，它将数据点视为图中的顶点，利用数据点之间的相似性构建边，并通过图的分割来实现聚类。在这一过程中，规范割集准则起着关键作用。 规范割集准则，也称为最小N-cut准则，旨在找到图的最佳分割方式。该准则通过最小化N-cut函数来实现，N-cut函数衡量的是分割后的子图A和B之间的连接权重总和与两子图内部连接权重总和的比例。具体来说，Vol(A)和Vol(B)分别代表子图A和B内部所有顶点之间的连接权重之和。最小化N-cut的目标是找到一个分割，使得分割后的组间连接权重尽可能小，而组内连接权重尽可能大，以此达到区分不同类别的目的。 在谱聚类算法中，数据集首先被构建成一个无向加权图G=(V,E)，其中V是顶点集合，E是边的集合，wij是非负权重，表示顶点vi和vj之间的相似度。图的邻接矩阵W记录了顶点之间的边权重，而度矩阵D则包含每个顶点的度，即其与其他所有顶点连接的总权重。对于无向图，W是对称的，wij等于wji。 在处理图像数据时，谱聚类会将每个像素点视为一个顶点，像素间的相似性作为边的权重。相似度可以通过各种距离公式计算，如最常见的欧式距离。相似矩阵W包含了所有样本点之间的相似度信息。 将聚类问题转化为图分割问题，首先要确定顶点间的边如何定义，以及选择哪些边进行保留。这通常涉及到相似度阈值的选择，只保留超过一定相似度的边，以降低计算复杂度并突出重要连接。接着，通过拉普拉斯矩阵（Laplacian matrix）来表达图的结构，它可以有不同的形式，如归一化拉普拉斯矩阵或随机游走拉普拉斯矩阵，这些矩阵有助于找到图的“谱”，即其特征值和特征向量。谱分解后，选取前k个特征向量作为聚类的特征空间，然后应用如k-means等聚类算法对特征向量进行分组，最终得到k个类别。 谱聚类算法通过将数据建模为图，并利用规范割集准则来寻找最佳分割，实现了对高维数据的有效聚类。这种方法特别适用于发现潜在的、非凸形状的类别，而且在处理大规模数据集时也能展现出较好的性能。