spectral-cluster聚类算法详解

spectral clustering，称之为谱聚类算法，和近邻传播AP算法一样，也是基于图论的算法，都是将样本点两两相连，构成图这一数据结构，不同的是，谱聚类是通过切图的方式来划分不同的cluster, 其思想是使得子cluster内部边的权重之和尽可能高，而不同子cluster之间边的权重之和尽可能低。

要理解该算法，首先要搞清楚以下几个基本概念

1. 邻接矩阵

英文为Adjacency Matrix， 是用来描述图这一结构的最常见方法，示例如下

上图中，如果两个点相连，即存在边，在邻接矩阵中，对应的值为1， 否则为0。

在谱聚类算法中，对边定义了权重，所以就需要在是否相连的基础上引入权重的定量指标，基本思想是在相似度的基础上进一步操作，这里的相似度采用欧式距离来衡量，常见的方法有以下3种

1）

邻近法

定义一个阈值

，欧式距离大于阈值，则权重为0，否则为

，对应的公式如下

2）K近邻法

此方法又细分为两种，第一种对应的公式如下

第二种对应的公式如下

与第一种刚好相反。但是都应用了高斯核函数。

3）全连接法

不论点的距离远近，权重统一定义如下

高斯核函数，也称之为径向基函数，简写RBF, 在scikit-learn中，默认就是采用了基于高斯核函数的全连接法来构建权重矩阵。

2. 度矩阵

英文为Degree Matrix，一个顶点的度表示为与该点新连的边的个数，示例如下

可以看到，对于度矩阵而言，只有对角线有值，其他都为0。

3. 拉普拉斯矩阵

英文为laplacian Matrix， 请定义的方式是L = D -A, D 表示的是度矩阵，A表示的是邻接矩阵，图示如下

上述概念的定义都是为了更方便的理解后续的切图运算，谱聚类算法的本质是通过切图来划分不同的cluster, 图示如下

具体地，有以下两种切图的方法

1. RatioCut 切图

2. Ncut切图

两种方法具体的数学推导比较繁琐，但是共性在于都需要对拉普拉斯矩阵进行PCA降维，挑选最小的K个特征，并标准化得到特征矩阵，最后在特征矩阵的基础上进行传统的聚类，比如k-means聚类。

在scikit-learn中，使用谱聚类的代码如下

>>> from sklearn.cluster import SpectralClustering
>>> import numpy as np
>>> X = np.array([[1, 1], [2, 1], [1, 0],[4, 7], [3, 5], [3, 6]])
>>> clustering = SpectralClustering(n_clusters=2,assign_labels="discretize",random_state=0).fit(X)
>>> clustering
SpectralClustering(assign_labels='discretize', n_clusters=2, random_state=0)
>>> clustering.labels_
array([1, 1, 1, 0, 0, 0], dtype=int32)

对于谱聚类而言，由于只需要样本点的相似度矩阵，所以对于稀疏数据的聚类很有效，同时由于采用了降维技术，对于高维数据的聚类也很有效果，但是同时该算法的结果又对于两个因素非常敏感，权重矩阵的构建方法以及特征矩阵的聚类算法。

·end·