一.前言我想写一个关于簇系列算法的介绍，簇系列的其他一些算法原理比较简单，网上有很多教程。 这里主要介绍频谱聚类算法，做学习笔记，同时也希望对想了解该算法的朋友有所帮助。 关于聚类的其他系列算法，这里推荐不错的博客。
频谱聚类近年来受欢迎的主要原因是其实现简单，聚类效果优于传统的聚类算法(如k均值算法)。 在刚开始学习谱聚类时，yydfbx发现该算法似乎很难，但在真正深入理解该算法时，其实其原理并不难，但要理解该算法需要一定的数学基础。 掌握谱聚类算法后，可以对矩阵分析、图论、降维中的主成分分析等有更深入的理解。
本文首先简要介绍了谱聚类的简单过程，并对这些过程的细节，以及在这些过程中谱聚类是如何实现的进行了进一步分解，然后总结了谱聚类的几种算法，接下来是谱聚类介绍一下光谱聚类的基本原理吧。
2 .介绍了光谱聚类的基本原理2.1光谱和光谱聚类2.1.1光谱集中的金鱼作为线性算子，其所有特征值的总体统称为集中金鱼的光谱。 集中的金鱼的光谱半径是最大的特征值。 矩阵a的谱半径是矩阵的最大特征值。
2.1.2光谱聚类是一种基于图论的聚类方法，通过对样本数据淡黄豆矩阵的特征向量进行聚类，达到样本数据聚类之母。 光谱聚类可以理解为将高维空间的数据映射到低维空间，在低维空间中使用k均值等其他聚类算法进行聚类。
2.2谱聚类算法简述输入： n个采样点和聚类数k；
输出：集群
(1)使用以下公式计算的相似度矩阵w；
w是组成的相似度矩阵。
)2)用下式计算度矩阵d；
即，相似度矩阵w各行的元素之和
d构成对角矩阵。
)3)计算淡淡的大豆矩阵
(4)计算l的特征值，按照从小到大的顺序排列特征值，取最初的k个特征值，计算最初的k个特征值的特征值。
(5)将上面的k个列向量设为矩阵
(6)令是第行的向量，其中；
(7)使用k均值算法将新采样点聚类；
(8)输出集群，其中：
以上是未标准化的频谱聚类算法的说明。 也就是说，首先从样本点计算相似度矩阵，然后计算度矩阵和淡淡的大豆矩阵，接着计算淡淡的大豆矩阵的前k个特征值所对应的特征向量，最后将与该k个特征值对应的特征向量构成的矩阵u、u的各行作为新生成的样本点这是谱聚类算法的基本思想。 在PCA降维中，比较与前k个较大特征值相对应的特征向量，在此获取与前k个较小特征值相对应的特征向量。 但上述谱聚类算法并不是最优的，所以接下来对上面的步骤进行进一步分解，并在此基础上总结进行优化的谱聚类算法的版本。
2.3谱聚类算法中的重要属性2.3.1相似度矩阵介绍相似度矩阵是样本点中任意两点之间的距离度量，聚类算法中距离近的点之间相似度高，距离远的点之间相似度低，可以忽略不计。 这里，用-近邻法(-neighborhood graph )、k近邻法(k-nearest nerghbor graph )和全连结法)这3种方式表示相似度矩阵。 介绍一下这三种方法吧。
33558 www.Sina.com/- neighborhood graph :
表示采样点的任意两点之间的欧式距离
用这种方法构筑的相似度矩阵表示如下：
因为相似度矩阵将距离近的点的距离表示为0，距离远的点的距离表示为0，所以矩阵类型关于数据集的信息很少，所以此方法一般很少使用，即使在sklearn中也不使用。
（1）
由于每个样本点的k个近邻可能不完全相同，因此用该方法构造的相似度矩阵不是对称的。 因此，这里用两种方式表示对称的knn相似度矩阵。 第一种方式是在的k区域时或在的k区域时与的距离，否则； 第二种方案是，如果位于前k个区域且位于前k个区域中，则与之间的距离；否则为。 很明显，第二种方式比第一种方式生成的相似度矩阵更稀疏。 这两种方式在公式中表示为：
第一种方法：
第二种方法：
（2）k-nearest nerghbor graph：
该方法是算法描述中的hpdhlb相似度方法，采用以下公式。
该方法也是最常用的方法，在sklearn中默认为该方法，表明任意两个采样点存在相似度，但相隔的采样点之间的相似度低得可以忽略不计。 其中的参数控制着采样点的邻域宽度。 也就是说，越大，采样点与距离较远的采样点的相似度越大，反之亦然。
2.3.2淡大豆矩阵介绍光谱聚类最重要的工具是淡大豆矩阵。 下面
面我们来介绍淡定的黄豆矩阵的三种表示方法。（1）未标准化的淡定的黄豆矩阵：
未标准化的淡定的黄豆矩阵定义如下：
其中W是上节所说的相似度矩阵，D是度矩阵，在算法描述中有介绍。很显然，W与D都是对称矩阵。
未标准化的淡定的黄豆矩阵L满足下面几个性质：
（a）对任意一个向量都有：
证明如下：
（b）L是对称的和半正定的，证明如下：
因为，所以，所以为半正定矩阵。由于W和D都是对称矩阵，所以L为对称矩阵。
（c）L最小的特征值为0，且特征值0所对应的特征向量为全1向量，证明如下：
令表示的全1向量，则
由D和W的定义可以得出上式。
（d）L有n个非负的实数特征值：
（2）标准化淡定的黄豆矩阵
标准化淡定的黄豆矩阵有两种表示方法，一是基于随机游走（Random Walk）的标准化淡定的黄豆矩阵和对称标准化淡定的黄豆矩阵，定义如下：
标准化的淡定的黄豆矩阵满足如下性质：
（a）对任意一个向量都有：
（b）当且仅当是的特征值，对应的特征向量为时，则是特征值，对应的特征向量为u；
（c）当且仅当时，是的特征值，对应的特征向量为u；
（d）0是的特征值，对应的特征向量为，为的全1向量；0也是的特征值，对应的特征向量为；
（e）和是半正定矩阵并且有非负实数特征值：.
关于各个版本的谱聚类算法的不同之处，就是在于相似度矩阵的计算方式不同和淡定的黄豆矩阵的表示方法不同，其它步骤基本相同。下面就来介绍关于谱聚类的两个比较流行的标准化算法。
2.4 标准化谱聚类算法介绍 2.4.1 随机游走淡定的黄豆矩阵的谱聚类算法描述输入：n个样本点和聚类簇的数目k；
输出：聚类簇
（1）计算的相似度矩阵W；
（2）计算度矩阵D；
（3）计算淡定的黄豆矩阵；
（4）计算的特征值，将特征值从小到大排序，取前k个特征值，并计算前k个特征值的特征向量；
（5）将上面的k个列向量组成矩阵，；
（6）令是的第行的向量，其中；
（7）使用k-means算法将新样本点聚类成簇；
（8）输出簇，其中，.
2.4.2 对称淡定的黄豆矩阵的谱聚类算法描述输入：n个样本点和聚类簇的数目k；
输出：聚类簇
（1）计算的相似度矩阵W；
（2）计算度矩阵D；
（3）计算淡定的黄豆矩阵；
（4）计算的特征值，将特征值从小到大排序，取前k个特征值，并计算前k个特征值的特征向量；
（5）将上面的k个列向量组成矩阵，；
（6）令是的第行的向量，其中；
（7）对于，将依次单位化，使得；
（8）使用k-means算法将新样本点聚类成簇；
（9）输出簇，其中，.
上面两个标准化淡定的黄豆算法加上未标准化淡定的黄豆算法这三个算法中，主要用到的技巧是将原始样本点转化为新的样本点，然后再对新样本点使用其它的聚类算法进行聚类，在这里最后一步用到的聚类算法不一定非要是KMeans算法，也可以是其它的聚类算法，具体根据实际情况而定。在sklearn中默认是使用KMeans算法，但是由于KMeans聚类对初始聚类中心的选择比较敏感，从而导致KMeans算法不稳定，进而导致谱聚类算法不稳定，所以在sklearn中有另外一个可选项是'discretize'，该算法对初始聚类中心的选择不敏感。
三. 用切图的观点来解释谱聚类聚类算法给我们的直观上的感觉就是根据样本点的相似性将他们划分成不同的组，使得在相同组内的数据点是相似的，不同组之间的数据点是不相似的。对于给定的样本点计算相似度，形成相似度图，因而谱聚类的问题可以被重新描述如下：我们想要找到图形的一个分区，使得不同分区之间的边具有非常低的权重（这意味着不同分区中的点彼此不相似）并且分区内的边具有高权重（这意味着其中的点彼此相似）。在这个小节我们将讨论如何推导谱聚类为近似的图分区的问题。
3.1 最小切（mincut）对于无向图G，我们的目标是将图切成互相没有连接的子图，每个子图点的集合为，其中且。
对于任意两个子图点的集合，，我们定义A和B之间的权重切图为：
对于k个子图集合，我们定义切图cut为：
其中，为A的补集。
我们可以想到的切图方法就是最小化上式，也就是使各个组之间的权重尽可能的小，但是在许多情况下mincut只是简单的将图中的一个定点与其余的顶点分开，在并不是我们想要的结果，合理的切分结果应该是组内的样本点尽可能的多。所以mincut在实际中并不常用。下面我们介绍另外两个切图方式RatioCut和Ncut。
3.2 RatioCut切图在RatioCut切图中，不仅要考虑使不同组之间的权重最小化，也考虑了使每个组中的样本点尽量多。
定义为子集A中的顶点个数，RatioCut的表达式如下：
将图中顶点V分成k个分区，我们定义指示向量为：，其中：
我们令为包含k个指示向量作为列向量的矩阵，注意到H的列向量彼此正交，即，然后我们计算下式：
，证明如下：
结合上面可以得到：
其中Tr(A)表示矩阵A的迹，也就是矩阵A的对角线之和。
所以我们此时的目标函数成为：
，约束条件为：
注意到我们H矩阵里面的每一个指示向量都是n维的，向量中每个变量的取值为0或者，就有种取值，有k个子图的话就有k个指示向量，共有种H，因此找到满足上面优化目标的H是一个NP难的问题。那么是不是就没有办法了呢？
注意观察中每一个优化子目标，其中是单位正交基， 为对称矩阵。在PCA中，我们的目标是找到协方差矩阵（对应此处的淡定的黄豆矩阵L）的最大的特征值，而在我们的谱聚类中，我们的目标是找到目标的最小的特征值，得到对应的特征向量，此时对应二分切图效果最佳。也就是说，我们这里要用到维度规约的思想来近似去解决这个NP难的问题。
对于，我们的目标是找到最小的L的特征值，而对于，则我们的目标就是找到k个最小的特征值，一般来说，k远远小于n，也就是说，此时我们进行了维度规约，将维度从n降到了k，从而近似可以解决这个NP难的问题。
通过找到L的最小的k个特征值，可以得到对应的k个特征向量，这k个特征向量组成一个nxk维度的矩阵，即为我们的H。一般需要对H矩阵按行做标准化，即
由于我们在使用维度规约的时候损失了少量信息，导致得到的优化后的指示向量h对应的H现在不能完全指示各样本的归属，因此一般在得到nxk维度的矩阵H后还需要对每一行进行一次传统的聚类，比如使用K-Means聚类。
3.3 Ncut切图Ncut在最小化损失函数之外，还考虑了子图之间的权重大小。Ncut切图与Ratiocut类似，只是把RatioCut分母中的替换成了，其中：
由于子图样本的个数多并不一定权重就大，我们切图时基于权重也更合我们的目标，因此一般来说Ncut切图优于RatioCut切图。所以Ncut的目标函数如下：
，证明同上
在Ncut中使用子图权重来表示指示向量h，定义如下：
我们的优化目标函数是：
但是此时我们的，而是。推导如下：
也就是说，此时我们的优化目标最终为：
约束条件：
令，则问题变成如下形式：
约束条件为：
可以发现这个式子和RatioCut基本一致，只是中间的L变成了。这样我们就可以继续按照RatioCut的思想，求出的最小的前k个特征值，然后求出对应的特征向量，并标准化，得到最后的特征矩阵,最后对进行一次传统的聚类（比如K-Means）即可。
一般来说，相当于对淡定的黄豆矩阵做了一次标准化，即，所以Ncut会产生标准化的谱聚类，而RatioCut会产生未标准化的谱聚类。
四. 谱聚类算法的优缺点 4.1 优点（1）当聚类的类别个数较小的时候，谱聚类的效果会很好，但是当聚类的类别个数较大的时候，则不建议使用谱聚类；
（2）谱聚类算法使用了降维的技术，所以更加适用于高维数据的聚类；
（3）谱聚类只需要数据之间的相似度矩阵，因此对于处理稀疏数据的聚类很有效。这点传统聚类算法（比如K-Means）很难做到
（4）谱聚类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
4.2 缺点（1）谱聚类对相似度图的改变和聚类参数的选择非常的敏感；
（2）谱聚类适用于均衡分类问题，即各簇之间点的个数相差不大，对于簇之间点个数相差悬殊的聚类问题，谱聚类则不适用；
close allclear all clc;%读入一副图像 % global slide_window interpixel_distance qutity_level ktic%读图I=imread('oil3-01.jpg');% I=rgb2gray(I);figure,imshow(I);I1=double(I);% I1=rgb2gray(I1);L=harrl(I1);LL=harrll(L); matrix=LL;II=mat2gray(matrix);figure,imshow(II);II=matrix(:);m=size(II,1); %聚类数k=2;Delta=0.0012;d=zeros(m,m);W=zeros(m,m);%尺度系数for i=1:m for j=1:m d(i,j)=abs(II(i)-II(j))^2; W(i,j)=exp(-d(i,j)/2*Delta^2); endend % W=affiliate(ent,Delta);Y=cut(W);Y=Y(:,2);% matrix=mat2gray(Y); % MATRIX=reshape(matrix,[60,60]);% figure,imshow(MATRIX);% imwrite(MATRIX,'featureIMAGE');Y=Y./sum(Y);%Y=Y';% plot(m,n) %T=0.5*(max(Y)+min(Y));%while true% g=Y>=T;% Tn=0.5*(mean(Y(g)+mean(Y(~g))));% done=abs(T-Tn)<0.1;% T=Tn;% end % figure,imshow(image); label_matrix1=k_meanclusterings(Y,k); label_matrix2=reshape(label_matrix1,64,64); label_map=label2rgb(label_matrix2); figure,imshow(label_map);imwrite(label_map,'oil3-02.jpg');toc% im_matric=label_matrix;% im_matric1=reshape(im_matric,[m,n]);%label_map=mat2gray(im_matric1);%figure,imshow(label_map);