白话什么是谱聚类算法

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

换句话说，

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

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

谱聚类算法流程为：

Input：

（x_1, ..., x_n）

Output:

(c_1, ..., c_{k_2})

1. 根据输入的相似矩阵的生成方式构建样本的相似矩阵S
2. 根据相似矩阵S构建邻接矩阵W，构建度矩阵D
3. 计算出拉普拉斯矩阵L
4. 构建标准化后的拉普拉斯矩阵

D^{−1/2} L D^{−1/2}

1. 计算

D^{−1/2} L D^{−1/2}

最小的

k_1

个特征值所各自对应的特征向量f

1. 将各自对应的特征向量f组成的矩阵按行标准化，最终组成n×k1维的特征矩阵F
2. 对F中的每一行作为一个k1维的样本，共n个样本，用输入的聚类方法进行聚类，聚类维数为k2。
3. 得到簇划分

(c_1, ..., c_{k_2})

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

其中涉及的主要概念：

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

w_{ij} = w_{ji}

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

d_i = \sum_{j=1}^n w_{ij}

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

\begin{pmatrix} d_1 & \cdots & \cdots \\ \cdots & d_2 & \cdots \\ \vdots & \vdots & \ddots \\ \cdots & \cdots & d_n \\ \end{pmatrix}

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

w_{ij}

如何得到这个邻接矩阵？

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

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

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

W_{ij}=S_{ij}=exp(-\frac{||x_i-x_j||_2^2}{2\sigma^2})

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

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

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

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

W(A,B) = \sum_{i∈A,j∈B} w_{ij}

再定义有 k 个子图的切图cut为：即所有子图

A_i

与其补集

\overline{A}_i

之间的切图权重之和:

cut(A_1,A_2,...A_k) = \frac{1}{2}\sum\limits_{i=1}^{k}W(A_i, \overline{A}_i )

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

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

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

1. Ncut切图：

RatioCut 切图函数为：

NCut(A_1,A_2,...A_k) = \frac{1}{2}\sum\limits_{i=1}^{k}\frac{W(A_i, \overline{A}_i )}{vol(A_i)}

它的优化目标为：

\underbrace{arg\;min}_H\; tr(H^TLH) \;\; s.t.\;H^TDH=I

进一步令

H = D^{-1/2}F

，则有

H^TLH = F^TD^{-1/2}LD^{-1/2}F

，于是优化目标变为：

\underbrace{arg\;min}_F\; tr(F^TD^{-1/2}LD^{-1/2}F) \;\; s.t.\;F^TF=I

然后就可以求出

D^{-1/2}LD^{-1/2}

的最小的前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