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