目录
邻接矩阵或相似矩阵
切图
聚类>谱聚类算法原理
聚类>谱聚类(Spectral Clustering, SC)：是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类。即把所有的数据看做空间中的点，这些点之间可以用边连接起来。距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高，通过对所有数据点组成的图进行切图，让切图后不同的子图间边权重和尽可能的低，而子图内的边权重和尽可能的高，从而达到聚类的目的。
其中切割的最优子图的最优是指最优目标函数不同，可以是割边最小分割——如图1的Smallest cut(如后文的Min cut)， 也可以是分割规模差不多且割边最小的分割——如图1的Best cut(如后文的Normalized cut)。
图1 聚类>谱聚类无向图划分——Smallest cut和Best cut
这样，聚类>谱聚类能够识别任意形状的样本空间且收敛于全局最优解，其基本思想是利用样本数据的相似矩阵(拉普拉斯矩阵)进行特征分解后得到的特征向量进行聚类。
邻接矩阵或相似矩阵
由任意两点之间的权重值Wij组成的矩阵。即距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高，因此可以通过样本点距离度量的相似矩阵S来获得邻接矩阵W。应该有如下性质：
- 矩阵为N * N，N为对象总数
- 矩阵对角线的值为0，自己和自己没有相似的说法
- 矩阵为对称矩阵，及相似度是无向的
构建邻接矩阵W的方法有三类。ϵ-邻近法，K邻近法和全连接法。
-
ϵ-邻近法：即设定一个距离阈值，小于阈值的权重为0，大于阈值的权重为ϵ；
-
K邻近法：取样本点中的k个最邻近点计算权重（又分为单邻近和互邻近）。
-
全连接法：样本中一个点与其他所有点都连接，并计算相应权重。
切图
聚类>谱聚类本身也提供了好几种不同的分割(cut)方法，每种方法对应一种优化目标。聚类>谱聚类分类的方式为“切图”，如图：
切图的原则：同子图内的点相似度高，不同子图的点相似度低。与传统聚类组内离差平方和最小、组间离差平方和最大类似。切图的效果可用损失函数来评价，即划分时子图之间被“截断”的边的权重和：
切图的方法有多种，这里主要介绍Ratio cut和Ncut（Normalized Cut）两种：
n1和n2为划分到子图1和子图2中的顶点个数。
d1和d2分别为子图1和子图2的权重和。
由以上两个公式，结合切图的原则可知，Ncut的方法较好。
聚类>谱聚类算法思路
1. 计算对角矩阵D[N*N]。，公式如下：
D矩阵为对角矩阵，对角线上的值为W矩阵中对应行或列的和。
2. 计算拉普拉斯矩阵(Laplacian) L：
3. 归一化L矩阵
4. 计算归一化后L矩阵的K个最小特征值及对应的特征向量
将K个特征向量竖着并排放在一起，形成一个N*K的特征矩阵，记为Q。
5. 对特征矩阵Q做kmeans聚类，得到一个N维向量C
分别对应相似度矩阵W中每一行所代表的对象的所属类别，这也就是最终的聚类结果。
此外：
关于第3步中，对拉普拉斯矩阵归一化时，归一化公式进行变换得到：
令：
则在第4步中，我们可以将求L的K个最小特征值及其对应的特征向量的问题，转化为求矩阵E的K个最大的特征值及其对应的特征向量。
---可以证明：L的K个最小特征值对应的特征向量，分别对应于E的K个最大的特征值对应的特征向量。
且矩阵L的最小特征值为0，对应于矩阵E最大的特征值为1.矩阵L的第K小特征值等于1-矩阵E的第K大特征值
之所以要这么做，是因为在数值计算中，求矩阵的最大特征值，往往要比求最小特征值更方便和高效。
需要注意的关键点是
邻接矩阵的生成方式：
-
ϵ-邻近法
-
K邻近法
-
全连接法
切图的方式
-
Ncut
-
Rcut
最后的聚类方法
-
kmeans（通常）
