核k均值和谱聚类之间的实际区别是什么？

Question

最近我一直在想核k均值和谱聚类算法及其区别。

• 我知道光谱聚类是一个更广泛的术语，不同的设置可能会影响它的工作方式，但一个流行的变体是使用K-均值聚类对亲和矩阵的谱嵌入。
• 另一方面，核K-均值直接将K-均值聚类应用于亲和矩阵.因此，一个直接的、理论上的不同之处在于它忽略了谱嵌入步骤，即它不寻找具有特征向量的数据的低维表示。

我认为在高维环境下它可能是有益的(有很多观测要聚在一起)，但是它能为小样本提供任何提升吗，例如从10到20个观测？

使用这两种算法对另一种算法的其他实际意义是什么(例如，哪种算法对亲和力的变化更敏感，等等)？

Answer 1

两者之间的差异确实不算太大。有一篇名为核k-均值、谱聚类和归一化割集的论文，作者是来自2004年KDD的Inderjit S. Dhillon，Yu强官，Brian，正在讨论这种关系。证明了归一化割集的谱聚类是加权核k-均值的一个特例.其原因是“图割问题和加权核k-均值问题都可以写成迹最大化问题”。

他们写的

这具有重要的意义：( a)基于特征向量的算法，在计算上是禁止的，对于最小化归一化割集并不重要；( b)各种技术，如局部搜索和加速方案，可能用于提高核k-均值的质量和速度。

此外，他们结合了双方的想法，以提高总体成果和

结果表明，利用特征向量对核k均值进行初始化得到了较好的初始目标函数值和最终目标函数值，并获得了较好的聚类结果。

关于谱聚类的鲁棒性，您可能想看看Aleksandar Bojchevski、Yves Matkovic、Stephan Günnemann在2017年知识发现和数据挖掘会议上发表的噪声数据的鲁棒谱聚类：https://www.kdd.org/kdd2017/papers/view/robust-spectral-clustering-for-noisy-data。

英德吉特S.迪隆，关玉强，布赖恩.库利斯，核k-均值:光谱聚类和归一化割集，KDD '04:第十届ACM SIGKDD知识发现和数据挖掘国际会议记录，2004年8月，第551-556页，https://doi.org/10.1145/1014052.1014118