一、前述
谱聚类（spectral clustering）是一种基于图论的聚类方法，主要思想是把所有的数据看做空间中的点，这些点之间可以用边连接起来。距离较远（或者相似度较低）的两个点之间的边权重值较低，而距离较近（或者相似度较高）的两个点之间的边权重值较高，通过对所有数据点组成的图进行切图，让切图后不同的子图间边权重和尽可能的低，而子图内的边权重和尽可能的高，从而达到聚类的目的。
二、具体原理
1、优点谱聚类相较于前面讲到的最最传统的k-means聚类方法，谱聚类又具有许多的优点：
1.只需要待聚类点之间的相似度矩阵就可以做聚类了。
2.对于不规则的数据（或者说是离群点）不是那么敏感。
3.k-means聚类算法比较适合于凸数据集（数据集内的任意两点之间的连线都在该数据集以内，简单理解就是圆形，可能不准确），而谱聚类则比较通用。
2、相关概念
相似度矩阵S的构建
构建相似度的矩阵的过程中，可以使用欧氏距离、余弦相似度、高斯相似度等来计算数据点之间的相似度，选用哪个要根据你自己的实际情况来。不过在谱聚类中推荐使用的是高斯相似度，但是我在我的工程中使用的是余弦相似度。
拉普拉斯矩阵
它的定义很简单，拉普拉斯矩阵。是度矩阵，也就是相似度矩阵的每一行（或者每一列）加和得到的一个对角矩阵。W就是图的邻接矩阵。相似矩阵
邻接矩阵，它是由任意两点之间的权重值组成的矩阵。通常我们可以自己输入权重，但是在谱聚类中，我们只有数据点的定义，并没有直接给出这个邻接矩阵，那么怎么得到这个邻接矩阵呢？基本思想是，距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高，不过这仅仅是定性，我们需要定量的权重值。一般来说，我们可以通过样本点距离度量的相似矩阵来获得邻接矩阵。构建邻接矩阵的方法有三类。-邻近法，K邻近法和全连接法。
对于-邻近法，它设置了一个距离阈值，然后用欧式距离度量任意两点和的距离。即相似矩阵的, 然后根据和的大小关系，来定义邻接矩阵如下： 从上式可见，两点间的权重要不就是,要不就是0，没有其他的信息了。距离远近度量很不精确，因此在实际应用中，我们很少使用-邻近法。 第二种定义邻接矩阵的方法是K邻近法，利用KNN算法遍历所有的样本点，取每个样本最近的k个点作为近邻，只有和样本距离最近的k个点之间的。但是这种方法会造成重构之后的邻接矩阵W非对称，我们后面的算法需要对称邻接矩阵。为了解决这种问题，一般采取下面两种方法之一： 第一种K邻近法是只要一个点在另一个点的K近邻中，则保留 第二种K邻近法是必须两个点互为K近邻中，才能保留 第三种定义邻接矩阵的方法是全连接法，相比前两种方法，第三种方法所有的点之间的权重值都大于0，因此称之为全连接法。可以选择不同的核函数来定义边权重，常用的有多项式核函数，高斯核函数和Sigmoid核函数。最常用的是高斯核函数RBF，此时相似矩阵和邻接矩阵相同： 在实际的应用中，使用第三种全连接法来建立邻接矩阵是最普遍的，而在全连接法中使用高斯径向核RBF是最普遍的。3、算法流程：
输入：样本集D=，相似矩阵的生成方式, 降维后的维度, 聚类方法，聚类后的维度
输出： 簇划分
1) 根据输入的相似矩阵的生成方式构建样本的相似矩阵S
2）根据相似矩阵S构建邻接矩阵W，构建度矩阵D
3）计算出拉普拉斯矩阵L
4）求L的最小的个特征值所各自对应的特征向量
6) 将特征向量组成维的特征矩阵F
7）对F中的每一行作为一个维的样本，共n个样本，用输入的聚类方法进行聚类，聚类维数为。
8）得到簇划分
4、总结
谱聚类算法是一个使用起来简单，但是讲清楚却不是那么容易的算法，它需要你有一定的数学基础。如果你掌握了谱聚类，相信你会对矩阵分析，图论有更深入的理解。同时对降维里的主成分分析也会加深理解。
谱聚类算法的主要优点有： 1）谱聚类只需要数据之间的相似度矩阵，因此对于处理稀疏数据的聚类很有效。这点传统聚类算法比如K-Means很难做到 2）由于使用了降维，因此在处理高维数据聚类时的复杂度比传统聚类算法好谱聚类算法的主要缺点有： 1）如果最终聚类的维度非常高，则由于降维的幅度不够，谱聚类的运行速度和最后的聚类效果均不好。 2) 聚类效果依赖于相似矩阵，不同的相似矩阵得到的最终聚类效果可能很不同。
三、代码
# !/usr/bin/python# -*- coding:utf-8 -*-import numpy as npimport matplotlib.pyplot as pltimport matplotlib.colorsfrom sklearn.cluster import spectral_clusteringfrom sklearn.metrics import euclidean_distancesdef expand(a, b): d = (b - a) * 0.1 return a-d, b+dif __name__ == "__main__": matplotlib.rcParams['font.sans-serif'] = [u'SimHei'] matplotlib.rcParams['axes.unicode_minus'] = False t = np.arange(0, 2*np.pi, 0.1) data1 = np.vstack((np.cos(t), np.sin(t))).T data2 = np.vstack((2*np.cos(t), 2*np.sin(t))).T data3 = np.vstack((3*np.cos(t), 3*np.sin(t))).T data = np.vstack((data1, data2, data3)) n_clusters = 3 m = euclidean_distances(data, squared=True) sigma = np.median(m) plt.figure(figsize=(12, 8), facecolor='w') plt.suptitle(u'谱聚类', fontsize=20) clrs = plt.cm.Spectral(np.linspace(0, 0.8, n_clusters)) for i, s in enumerate(np.logspace(-2, 0, 6)): print(s) af = np.exp(-m ** 2 / (s ** 2)) + 1e-6 y_hat = spectral_clustering(af, n_clusters=n_clusters, assign_labels='kmeans', random_state=1) plt.subplot(2, 3, i+1) for k, clr in enumerate(clrs): cur = (y_hat == k) plt.scatter(data[cur, 0], data[cur, 1], s=40, c=clr, edgecolors='k') x1_min, x2_min = np.min(data, axis=0) x1_max, x2_max = np.max(data, axis=0) x1_min, x1_max = expand(x1_min, x1_max) x2_min, x2_max = expand(x2_min, x2_max) plt.xlim((x1_min, x1_max)) plt.ylim((x2_min, x2_max)) plt.grid(True) plt.title(u'sigma = %.2f' % s, fontsize=16) plt.tight_layout() plt.subplots_adjust(top=0.9) plt.show()