需要求一张图的拉普拉斯矩阵，根据矩阵求特征向量，然后对向量进行聚类。

如何建立表征相似度的哪张图？

其实，第一种建立相似矩阵的办法是欧式距离，但是实践层面上往往是用高斯距离——高斯相似度函数，rbf 径向基函数，只有一个参数，即带宽 $\sigma$，
注意：近邻图不一定是对称的，所以实践层面直接忽略方向，我们用的互近邻，而非 K 近邻。

下图中的拉式矩阵， 0 一定是它的特征值，并且 0 有可能是 k 重的，k 重的意思意味着，图有k个连通分量（可以理解为k个不同的簇，彼此不连通），

• 第i行第j列如果等于0，表示没有相似性，将它自己的相似性赋值为0（即第i行第i列）。这样每一行加起来，就是度矩阵
• 未正值化拉式矩阵：左边和右边都乘以一个对称阵，
• 正则化拉式矩阵：
  • adddd
  • 对这一行，让其加和为1，相当于任何一个点，给出的不仅是相似度，还是转移概率（我这个点转移到别的点的概率值，），如果转移概率大，就非常容易转移到别的点，如果小则不太容易转移。给一个喝醉酒的醉汉，让他随机的去游走，随机的去玩，去晃悠，他最终走完的那块区域，我们就认为是它的图的范围——随机游走的概念。
  • 按照点的转移概率，去把它转到别的点上，然后最终得到的那个图，就是它的聚类的过程，这也是随机游走的思路。
  • 可以用矩阵的乘法去解释马尔科夫
    
    后面把谱聚类算法的过程，做一个介绍
• 算相似矩阵和度矩阵，
• 由于拉式矩阵是n×n的，所以特征向量u1是n×1的列向量，将k个向量合并为n×k的矩阵
• 特征提取类似与主成分分析，从n个特征中提取k个特征，然后进行聚类。
• 任何一个聚类，都不能解决所有问题；谱聚类可以作为一个标杆，如果某个聚类，比谱聚类做的好，至少说明这个聚类算法还行。就好像分类算法和神经网络进行比较，如果比神经网络效果好，那说明这个分类算法做的不会太差。

• 如果说一张图，假定说是下图下左一，已经有了两个联通分量，即然有两个联通分量的话，那么对于0这样一个特征值（最小的），它其实就会有两个特征向量，拿这两个特征向量去聚类，一定会得出下左一的聚类结果，这就是安装最小的情况做聚类的情况，当然，你可以选几个特征向量（>2)，来得到其他的聚类情况，
• 谱聚类是从小到大去排列特征值和特征向量的，

• 随机游走拉普拉斯矩阵，仅仅是多了下图红色部分，其它完全不变

• 对称的拉式矩阵，在选择样本的时候，需要做一个单位化，单位化之后，再去做聚类，就这个区别，
• 那这三个如何选择呢（随机游走、对称、未正则拉式矩阵）？实践中首先随机游走拉式矩阵。

• 如何自适应的选择k值？如下图所示，左下角，第5个红色的点跳跃最大，就利用这个间距，谁的跳跃值最大，我们就选那个作为 K 值，左下角的图中，选择前4个作为1类，比较合适
  

参考资料

[1] 谱聚类（Spectral Clustering）原理及Python实现 2018.6