白话什么是谱聚类算法

谱聚类(Spectral Clustering, SC), 是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远

换句话说，

1. 就是首先要将数据转换为图，即所有的数据看做空间中的点，点点之间用边相连。距离较远的两个点，它们之间边的权重值较低，距离较近的两点之间边的权重值较高。
2. 然后要对这个图进行切图。
3. 目标，是要让切图后不同的子图间边权重和尽可能的低，而子图内的边权重和尽可能的高。即子图间距离尽量较远，子图内部尽量相似。
   这样就完成了将原数据聚类为不同子集的过程。

当遇到比较复杂的聚类问题时，k-means 很难有较好的效果时，可以用谱聚类。

---

谱聚类算法流程为：

Input：
Output:

1. 根据输入的相似矩阵的生成方式构建样本的相似矩阵S
2. 根据相似矩阵S构建邻接矩阵W，构建度矩阵D
3. 计算出拉普拉斯矩阵L
4. 构建标准化后的拉普拉斯矩阵
5. 计算 最小的 个特征值所各自对应的特征向量f
6. 将各自对应的特征向量f组成的矩阵按行标准化，最终组成n×k1维的特征矩阵F
7. 对F中的每一行作为一个k1维的样本，共n个样本，用输入的聚类方法进行聚类，聚类维数为k2。
8. 得到簇划分

一句话总结这个流程就是，利用样本数据，得到相似矩阵(拉普拉斯矩阵)，再进行特征分解后得到特征向量，对特征向量构成的样本进行聚类。

---

其中涉及的主要概念：

1. 无向图：边上的权重和两点的方向无关:

2. 度：和该顶点相连的所有边的权重之和

3. 度矩阵D：是一个对角矩阵，只有主对角线有值，为每个顶点的度值

4. 邻接矩阵W：它的第i行的第j个值对应权重

如何得到这个邻接矩阵？

可以通过样本点距离度量的相似矩阵S来获得邻接矩阵W

构建邻接矩阵W的方法有三个：ϵ-邻近法，K邻近法和全连接法。

最常用的是全连接法，它选择不同的核函数来定义边权重，最常用的是高斯核函数RBF

5. 拉普拉斯矩阵： L=D−W。D 为度矩阵，W 为邻接矩阵

6. 无向图G的切图：就是将图G(V,E)切成相互没有连接的k个子图

那么如何切图可以让子图内的点权重和高，子图间的点权重和低呢：

先定义两个子图A和B之间的切图权重为：

再定义有 k 个子图的切图cut为：即所有子图 与其补集 之间的切图权重之和:

这样当我们最小化这个cut时，就相当于让子图间的点权重和低

但以最小化 cut 为目标，存在一个问题，就是有时候最小cut的切图方式，却不是最优的

为避免最小切图导致的切图效果不佳，需要对每个子图的规模做出限定，一般有两种切图方式，RatioCut，Ncut，常用的是 Ncut切图

7. Ncut切图：

RatioCut 切图函数为：

它的优化目标为：

进一步令 ，则有 ，于是优化目标变为：

然后就可以求出 的最小的前k个特征值，求出特征向量，并标准化，得到特征矩阵F, 再对F进行一次传统的聚类方法，最终就完成了聚类任务。

---

一个用 sklearn 做谱聚类的小例子：

    sklearn.cluster import SpectralClustering
    import numpy as np
    import math

    X = np.array([[185.4, 72.6],
    [155.0, 54.4],
    [170.2, 99.9],
    [172.2, 97.3],
    [157.5, 59.0],
    [190.5, 81.6],
    [188.0, 77.1],
    [167.6, 97.3],
    [172.7, 93.3],
    [154.9, 59.0]])

    w, h = 10, 10;

     #构建相似度矩阵，任意两个样本间的相似度= 100 - 两个样本的欧氏距离
    Matrix = [[100- math.hypot(X[x][0]- X[y][0], X[x][1]- X[y][1]) for x in range(w)] for y in range(h)]

    sc = SpectralClustering(3, affinity='precomputed', n_init=10)
    sc.fit(Matrix)

    print('spectral clustering')   
    print(sc.labels_)

---

学习资料：
https://www.cnblogs.com/pinard/p/6221564.html
https://www.cnblogs.com/sparkwen/p/3155850.html