白话什么是谱聚类算法

谱聚类(Spectral Clustering, SC) , 是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远

换句话说，

当遇到比较复杂的聚类问题时，k-means 很难有较好的效果时，可以用谱聚类。

谱聚类算法流程为：

Input：
Output:

一句话总结这个流程就是，利用样本数据，得到相似矩阵(拉普拉斯矩阵)，再进行特征分解后得到特征向量，对特征向量构成的样本进行聚类。

其中涉及的主要概念：

如何得到这个邻接矩阵？

可以通过样本点距离度量的相似矩阵S来获得邻接矩阵W

构建邻接矩阵W的方法有三个：ϵ-邻近法，K邻近法和全连接法。

最常用的是全连接法，它选择不同的核函数来定义边权重，最常用的是高斯核函数RBF

那么如何切图可以让子图内的点权重和高，子图间的点权重和低呢：

先定义两个子图A和B之间的切图权重为：

再定义有 k 个子图的切图cut为：即所有子图 与其补集 之间的切图权重之和:

这样当我们最小化这个cut时，就相当于让子图间的点权重和低

但以最小化 cut 为目标，存在一个问题，就是有时候最小cut的切图方式，却不是最优的

为避免最小切图导致的切图效果不佳，需要对每个子图的规模做出限定，一般有两种切图方式，RatioCut，Ncut， 常用的是 Ncut切图

RatioCut 切图函数为：

它的优化目标为：

进一步令 ，则有 ，于是优化目标变为：

然后就可以求出 的最小的前k个特征值，求出特征向量，并标准化，得到特征矩阵F, 再对F进行一次传统的聚类方法，最终就完成了聚类任务。

一个用 sklearn 做谱聚类的小例子：

学习资料：
>

谱聚类概念 ：
谱聚类是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类的母的。谱聚类可以理解为将高维空间的数据映射到低维，然后在低维空间用其它聚类算法（如KMeans）进行聚类。

算法步骤

1 计算相似度矩阵 W
2 计算度矩阵 D
3 计算拉普拉斯矩阵L=D-W
4 计算L的特征值，将特征值从小到大排序，取前k个特征值将这个特征值向量转换为矩阵
5 通过其他聚类算法对其进行聚类，如k-means
详细公式和概念请到 大佬博客

相比较PCA降维中取前k大的特征值对应的特征向量，这里取得是前k小的特征值对应的特征向量。但是上述的谱聚类算法并不是最优的，接下来我们一步一步的分解上面的步骤，总结一下在此基础上进行优化的谱聚类的版本。

python实现
例子一：使用谱聚类从噪声背景中分割目标

效果图

例子2：分割图像中硬币的区域

效果图

注意
1）当聚类的类别个数较小的时候，谱聚类的效果会很好，但是当聚类的类别个数较大的时候，则不建议使用谱聚类；

（2）谱聚类算法使用了降维的技术，所以更加适用于高维数据的聚类；

（3）谱聚类只需要数据之间的相似度矩阵，因此对于处理稀疏数据的聚类很有效。这点传统聚类算法（比如K-Means）很难做到

（4）谱聚类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
（5）谱聚类对相似度图的改变和聚类参数的选择非常的敏感；

（6）谱聚类适用于均衡分类问题，即各簇之间点的个数相差不大，对于簇之间点个数相差悬殊的聚类问题，谱聚类则不适用；

参考
谱聚类算法介绍
sklearn官网

典型的聚类算法有：

K-means算法：将n个数据点分成k个簇，每个数据点属于距其最近的簇，簇的中心点通过所有点的均值计算得到。

层次聚类算法：通过不断合并或分裂簇来建立聚类树，包括凝聚层次聚类和分裂层次聚类两种方法。

密度聚类算法：通过给定密度阈值来确定簇，相对稠密的区域被视为簇的中心点，较稀疏的区域则被视为噪声。

基于概率模型的聚类算法：使用统计学方法，利用概率分布模型来描述数据，并通过最大化似然函数来确定簇。

谱聚类算法：通过计算样本之间的相似度矩阵，并将其转换为拉普拉斯矩阵，通过计算拉普拉斯矩阵的特征向量进行聚类。

K-means算法是一种常用的聚类算法，其原理如下：

初始化：随机选择k个初始质心，每个质心表示一个簇的中心点。

分配：对于每个数据点，计算其到k个质心的距离，将其分配给距离最近的质心所表示的簇。

重新计算质心：对于每个簇，重新计算其所有点的均值，得到新的质心位置。

重复2和3步，直到质心位置不再改变或达到预定的迭代次数。

K-means算法的不足包括：

对于数据分布较为复杂或存在异常值的情况，K-means算法的聚类效果不太理想，容易出现偏差。

K-means算法需要预先指定簇的数量k，但在实际情况中，确定簇的数量比较困难，容易影响聚类结果。

K-means算法的初始质心位置是随机选择的，容易受到初始值的影响，可能导致不同的聚类结果。

K-means算法只适用于欧几里得距离，无法处理其他类型的距离度量。

---