谱聚类(Spectral Clustering, SC), 是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图,使子图内部尽量相似,而子图间距离尽量距离较远
换句话说,
当遇到比较复杂的聚类问题时,k-means 很难有较好的效果时,可以用谱聚类。
谱聚类算法流程为:
Input:
Output:
最小的
个特征值所各自对应的特征向量f
一句话总结这个流程就是,利用样本数据,得到相似矩阵(拉普拉斯矩阵),再进行特征分解后得到特征向量,对特征向量构成的样本进行聚类。
其中涉及的主要概念:
如何得到这个邻接矩阵?
可以通过样本点距离度量的相似矩阵S来获得邻接矩阵W
构建邻接矩阵W的方法有三个:ϵ-邻近法,K邻近法和全连接法。
最常用的是全连接法,它选择不同的核函数来定义边权重,最常用的是高斯核函数RBF
那么如何切图可以让子图内的点权重和高,子图间的点权重和低呢:
先定义两个子图A和B之间的切图权重为:
再定义有 k 个子图的切图cut为:即所有子图
与其补集
之间的切图权重之和:
这样当我们最小化这个cut时,就相当于让子图间的点权重和低
但以最小化 cut 为目标,存在一个问题,就是有时候最小cut的切图方式,却不是最优的
为避免最小切图导致的切图效果不佳,需要对每个子图的规模做出限定,一般有两种切图方式,RatioCut,Ncut,常用的是 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