A. 谱聚类算法总结
聚类三种方法：k-means聚类、密度聚类、层次聚类和 谱聚类Spectrum Clustering
谱聚类 是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远，以达到常见的聚类的目的。其中的最优是指最优目标函数不同，可以是割边最小分割,也可以是分割规模差不多且割边最小的分割。
谱聚类算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并且计算矩阵的特征值和特征向量 ， 然后选择合适 的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉 、VLS I 设计等领域， 最近才开始用于机器学习中，并迅速成为国际上机器学习领域的研究热点。谱聚类算法建立在谱图理论基础上，其本质是 将聚类问题转化为图的最优划分 问题，是一种 点对聚类算法 ，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。
根据不同的图拉普拉斯构造方法，可以得到不同的谱聚类算法形式。 但是，这些算法的核心步骤都是相同的：
谱聚类是从图论中演化过来的。主要思想是把所有的数据看做是空间中的点，这些点之间可以用边链接起来。距离比较远的两个点之间的边权重比较低，距离较近的两点之间权重较高，通过对所有的数据点组成的图进行切割，让切图后不同的子图间权重和尽可能低，而子图内的边权重和尽可能高，从而达到聚类的目的。
对于有边连接的两个点v i 和v j ,w ij >0，若没有边连接，w ij =0，度d i 定义为和它相连的所有边的权重之和，即
谱聚类中，通过样本点距离度量的相似矩阵S来获得邻接矩阵W。
构造邻接矩阵W的方法有 ϵ -邻近法，K邻近法和全连接法 。
ϵ -邻近法 :设置距离阈值ϵ，然后用欧氏距离s ij 度量任意两点x i 和x j 的距离，即s ij =||x i -x j || 2 2
邻接矩阵W定义为：
L=D-W,D为度矩阵，是一个对角矩阵。W为邻接矩阵。
其性质如下：
对于无向图G的切图，我们的目标是将图G(V,E)切成相互没有连接的k个子图，每个子图点的集合为：A 1 ,A 2 ,..A k ，它们满足A i ∩A j =∅,且A 1 ∪A 2 ∪...∪A k =V
对于任意两个子图点的集合A,B⊂V, A∩B=∅, 我们定义A和B之间的切图权重为：
RatioCut切图为了避免最小切图，对每个切图，不光考虑最小化cut(A 1 ,A 2 ,..A k )，它同时还考虑最大化每个子图点的个数，即：
Ncut切图和RatioCut切图很类似，但是把Ratiocut的分母|Ai|换成vol(Ai). 由于子图样本的个数多并不一定权重就大，我们切图时基于权重也更合我们的目标，因此一般来说Ncut切图优于RatioCut切图。
这样我们就可以继续按照RatioCut的思想，求出D -1/2 LD -1/2 的最小的前k个特征值，然后求出对应的特征向量，并标准化，得到最后的特征矩阵F,最后对F进行一次传统的聚类（比如K-Means）即可。
D -1/2 LD -1/2 相当于对拉普拉斯矩阵L做了一次标准化，
谱聚类主要的注意点为相似矩阵的生成方式，切图的方式以及最后的聚类方法。
最常用的相似矩阵的生成方式是基于高斯核距离的全连接方式，最常用的切图方式是Ncut。而到最后常用的聚类方法为K-Means。下面以Ncut总结谱聚类算法流程。
输入：样本集D=(x1,x2,...,xn)，相似矩阵的生成方式, 降维后的维度k1, 聚类方法，聚类后的维度k2
输出： 簇划分C(c1,c2,...ck2)
谱聚类算法的主要优点有：
1）谱聚类只需要数据之间的相似度矩阵，因此对于处理稀疏数据的聚类很有效。这点传统聚类算法比如K-Means很难做到
2）由于使用了降维，因此在处理高维数据聚类时的复杂度比传统聚类算法好。
谱聚类算法的主要缺点有：
1）如果最终聚类的维度非常高，则由于降维的幅度不够，谱聚类的运行速度和最后的聚类效果均不好。
转自： https://www.cnblogs.com/pinard/p/6221564.html