谱聚类很有效，这几乎是所有做speaker-diarization人的共识了。 但为什么谱聚类有效，比k-means好在哪里？

谱聚类简介

关于谱聚类，看这一篇文章就够了。https://arxiv.org/pdf/0711.0189.pdf 里面有很多公式/定理/推导，本节总结一些里面关键精华的部分。

查阅了资料，也有一些不错的中文链接

• https://zhuanlan.zhihu.com/p/29849122
• https://www.cnblogs.com/pinard/p/6221564.html
• https://www.cnblogs.com/sparkwen/p/3155850.html

这些之前的总结已经把谱聚类的基本算法原理和求解流程讲得很清楚了，这里尽量不再重复。

核心算法流程：

核心点：

• 问题的构建，使用图结构表述问题，构建相似矩阵并提出最优化函数
• 引入Graph-Laplace Matrix，使用线性代数中的矩阵分析方法，将优化问题转换为求解矩阵特征值/特征向量的问题，从而对原始问题进行了降维度求解

有一些引理的证明和代数方程的转化还是很巧妙的。特别是里面证明的关键公式，给我一种拍案的感觉。

另外一些比较有意思的点

• 使用时的一些细节，不同参数选取对结果的影响。一些经典case的分析
• random walk 观点和 spectral cluster方法直接的联系。一个好的Ncut切分，对应了一个低的transition probility（从一个顶点随机游走到非同簇另一个顶点的概率）， 以及一个低的 commute distance（更关系从某个顶点到目标顶点对应多条最短路径的集合，而非单一最短路径）
• spectral cluster 算法（both normalized and unnormalized）在理论具有对噪声扰动的鲁棒性。

advantage

为什么谱聚类有效？

传统的 kmeans 算法是基于point的数据驱动算法，每次迭代考虑的都是单个样本和其他样本的距离。 而谱聚类本质是一种图算法，考虑的是集合之间的距离。因此，谱聚类相当于从更”全局”的角度来考虑问题。

例如下图所示的一些数据样本： 图片来自于 https://www.quora.com/What-are-the-advantages-of-spectral-clustering-over-k-means-clustering

这些都是 k-means 算法很难处理的case。选择合适的核函数，可能会对case1/3/5处理得更好， 但选择核函数本身就是一件很困难的事情。究其原因，就是k-means只考虑临近点，并没有把同一个cluster当成一个整体导致的。 因此出现下列结果可能也不足为奇了。

实际使用中，个人感觉谱聚类的几个特点:

• 谱聚类算法层面，天然很适合处理稀疏数据
• 谱聚类对损失函数加了正则，所以很适合每个类别数目差不多的情况
• 谱聚类的流程上看，和 k-means 相比一定会有性能损失，主要是构建矩阵和求特征值的开销
• K = 2 的情况下，谱聚类几乎是最佳选择，而且上条中所述的性能损失也很有限。

（看上去谱聚类和SD问题是绝配 😊）

总结

谱聚类从另一个角度来讲，也可以认为是一种 embedding，毕竟后面还是接了一个普通的 cluster 算法。 算法实现上，直接在sklearn中调库+简单调参即可，之前在追一时候工程实现了对应的cpp代码，也并不复杂。但是算法背后的原理，以及图论对应思想，可能蕴含着更多有意思和启发性的东西。