白话什么是谱聚类算法

作者: 不会停的蜗牛 | 来源:发表于2018-12-11 21:51 被阅读78次

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

换句话说，

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

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

谱聚类算法流程为：

Input： $（x_1, ..., x_n）$
Output: $(c_1, ..., c_{k_2})$

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

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

其中涉及的主要概念：

无向图：边上的权重和两点的方向无关: $w_{ij} = w_{ji}$
度：和该顶点相连的所有边的权重之和 $d_i = \sum_{j=1}^n w_{ij}$
度矩阵D：是一个对角矩阵，只有主对角线有值，为每个顶点的度值

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

邻接矩阵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})$

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

无向图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切图

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

白话什么是谱聚类算法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

机器学习

数据科学家