资 源 简 介
应用背景Spectral Clustering（谱聚类）是一种基于图论的聚类方法，它能够识别任意形状的样本空间且收敛于全局最有解，其基本思想是利用样本数据的相似矩阵进行特征分解后得到的特征向量进行聚类。谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远，以达到常见的聚类的目的。其中的最优是指最优目标函数不同，可以是割边最小分割。关键技术图划分的目的是将有权无向图划分为两个或以上子图，使得子图规模差不多而割边权重之和最小。图的划分可以看做是有约束的最优化问题，它的目的是看怎么把每个点划分到某个子图中，比较不幸的是当你选择各种目标函数后发现该优化问题往往是NP-hard的。
怎么解决这个问题呢？松弛方法往往是一种利器（比如SVM中的松弛变量），对于图的划分可以认为能够将某个点的一部分划分在子图1中，另一部分划分在子图2中，而不是非此即彼，使用松弛方法的目的是将组合优化问题转化为数值优化问题，从而可以在多项式时间内解决之，最后在还原划分时可以通过阈值来还原，或者使用类似K-Means这样的方法，之后会有相关说明。
