聚类之谱聚类（转）
从样本相似性到图
根据我们一般的理解，聚类是将相似的样本归为一类，或者说使得同类样本相似度尽量高，异类样本相似性尽量低。无论如何，我们需要一个方式度量样本间的相似性。常用的方式就是引入各种度量，如欧氏距离、余弦相似度、高斯度量等等。
度量的选择提现了你对样本或者业务的理解。比如说如果你要比较两个用户对音乐选择的品味，考虑到有些用户习惯打高分，有些用户习惯打低分，那么选择余弦相似度可能会比欧式距离更合理。
现在我们假设已有的样本为
这是一个完全图，我们的目的是去掉一些边，使得这个图变成K个连通子图。同一个子图内的节点归为一类。因此有两方面考虑：
- 子图内的连边权重尽量大，即同类样本间尽量相似
- 去掉的边权重尽量小，即异类样本间尽量不同
一个初步的优化方法是去掉部分权重小的边，常用的有两种方式：
- ϵ的所有边
- k邻近准则，即每个节点之保留权最大的几条边
现在我们得到一个较为稀疏的图。
图与图的Laplacian矩阵
为了下一步的算法推导，首先介绍图的Laplacian矩阵，我们记节点0，那么图对应的Laplacian矩阵为：