谱聚类算法概述

聚类

写在之前

如需转载，请注明出处。如有错误，烦请指正。
谱聚类算法是一种基于图论的聚类算法。它建立在谱图理论的基础上，其本质是将聚类问题转化为图的最优划分问题。与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点，而且可以获得在放松了的连续域中的全局最优解。

应用领域

语音识别、视频分割、图像分割、VLSI设计、网页划分、文本挖掘

图像分割应用

传统谱聚类算法易受到彩色图像大小和相似性测度的影响，会导致计算量大和分割精度低的问题。基于测地线的超像素谱聚类彩色图像分割(2015)提出了一种谱聚类分割算法，该算法基于超像素集测地线特征。先对彩色图像进行预分割得到超像素集，以超像素集为基础构造加权图，利用测地线距离特征和颜色特征构造权值矩阵，再应用NJW 算法得到最终的分割结果，实验表明该算法在分割精度和计算复杂度上都有较大改善。

半监督学习应用

半监督谱聚类特征向量选择算法(2011)提出了一种有约束的半监督谱聚类特征向量选择算法。该算法通过大量的监督信息寻找能体现数据结构特征的向量组合，来获得优于传统谱聚类算法的聚类性能，采用MNIST 手写体数据集和UCI 标准数据集进行仿真实验，结果验证了该算法的有效性和鲁棒性。

大数据分析应用

一种大数据环境下的新聚类算法(2015)提出了一种新的聚类算法NGKCA 。首先利用谱聚类NJW算法对大数据集进行列降维和数据归一化处理，其次引入对初始值不敏感的粒子群算法对数据集进行行降维从而选出临时的聚类中心集，接着通过全局Kmeans算法获取聚类中心点，最后使用粒子群算法调整聚类中心点获取最终的聚类划分。实验结果表明，该算法具有更好的稳定性和更高的检测率、更优的时间复杂度，适用于解决大数据环境下的聚类问题。

其他

基于谱聚类的聚类集成算法(2012)提出基于谱聚类的聚类集成算法。先利用谱聚类的内在特性构造多样性的聚类成员，然后用连接三元组算法计算相似度矩阵，再对该矩阵使用谱聚类算法以得到集成结果。最后，用Nystrom采样算法有效降低了算法的计算复杂度，使得算法能扩展到大规模应用。实验结果表明，较之其它常见的聚类集成算法，该算法更优越、更有效，能较好地解决数据聚类、图像分割等问题。

分类

图划分准则：最小割集准则(minimum Cut)，规范割集准则(Normalized Cut)，比例割集准则(Ratio Cut)，平均割集准则(AVerage Cut)，最小最大割集准则(Min-max Cut)，多路规范割集准则(Multiway Normalized Cut)，

多路比例割集准则(MRc)，多路最小最大割集准则(MMMc)。

根据不同的图划分准则与谱图映射方法，开发出了多种谱聚类的具体算法，基本框架是：

1. 构造样本集的表示矩阵z，不同的算法会使用不同的数据集矩阵；
2. 通过对矩阵Z的特征分解得其前K个特征值与其对应的特征向量，构建特征空间；
3. 在特征空间内利用经典聚类算法如k-means对特征空间内的特征向量进行聚类

谱聚类算法分为迭代谱聚类和多路谱聚类

迭代谱聚类

PF算法(1998)

对相似度矩阵W进行特征分解，取其最大的特征值所对应的特征向量进行聚类，同时指出在处理对角分块的相似度矩阵时，根据其特征向量中的元素是否为0而划分为两类。

SM算法(2000)

求解minNcut(A，B)，最后转化为求解下式

1. 构造出相似性矩阵，据此计算矩阵W和D
2. 计算第二小的特征值对应的特征向量V(Fiedeler向量)
3. 据启发式规则在Fiedler向量中寻找划分点i，在该点上得到的Ncut 最小。将Fiedler向量中大于等于该值的点归为一类，小于该值的点归为另一类。

SM的效果要明显好于用PF算法及最小化Avcut标准得到的聚类效果。

　SLH算法

SLH算法将相似度矩阵A和数字k为输入，然后通过下面的步骤输出一个新矩阵Q：

1. 求矩阵A的前k阶特征向量(较大的k个特征值对应的)构造矩阵X
2. 把矩阵X 行向量规范化，并构建新矩阵 $$Q=XX^T$$ ；
3. 根据Q矩阵中对应元素的值进行聚类。在理想情况下 $$Q (i,j)=1$$ 表示两点被分在同一类， $$Q(i,j)=0$$ 表示两点被分在不同类。而在一般情况下，当Q值接近1时属于同一类的点，接近0属于不同类的点。

weiss提出了一种将SLH算法和SM算法相结合的新型谱聚类算法，该算法将SLH算法中的原始相似矩阵w用规范相似矩阵N代替。实验表明，此算法能够更加快速地产生正确的聚类结果。

KVV算法(2000)

SM算法十分相似，不同之处仅在于SM算法是寻找使Ncut(A,B)值最小的划分点，而Kvv算法则是寻找使Rcut(A,B)值最小的划分点。降低了过分割的可能性，算法的运行速度相对较慢。

Mcut算法(2001)

算符步骤和Ncut一样，求取Fielder向量的时候公式有区别。算法的划分结果更加平衡，特别在类间样本重叠较大时，效果更加明显。

多路谱聚类

NJW算法(2002)

是最常用的算法。

算法描述

首先，对规范化拉普拉斯矩阵L进行特征值分解，然后选取特征向量构成$R^k$空间，这些向量由前k个最大特征值对应的特征向量组成，使原数据与$R^k$空间中的每一点一一对应，最后应用k均值等经典算法在$R^k$空间完成聚类。

1. 构建样本数据相似度矩阵A，同时得到规范化矩阵L；
2. 计算矩阵三的前k个最大特征值所对应的特征向量$x_1,x_2,\dots,x_k$(必要时正交化处理)，构造矩阵$X =[x_1,x_2,\dots,x_k]$
3. 将矩阵X的行向量单位化，得到矩阵Y，在新的特征空间内使用经典算法进行聚类，得到k个分类；
4. 根据变换后的点被分配的簇，把原数据也分配到对应的簇。

对于n个数据点，相似度矩阵的大小为$n\times n$。计算特征向量的复杂度为$O(n^3)$。

MS算法

算法描述

用马尔科夫(Markov)链中随机游动来描述数据点问的相似性关系，该马尔科夫链的概率转移矩阵即为规范化相似度矩阵$P=D^{-1}W$，这些算法步骤与NJW算法类似，但这种算法是用马尔科夫链的概率转移矩阵P的前k个特征向量构成矩阵x，然后直接将矩阵x中的各行看成特征空间$R^k$中的各点完成聚类。

1. 确定并构造出数据点集的相似性矩阵W，并由此得到P
2. 求P 的k 个最大特征值，构造对应的特征向量组成的矩阵V
3. 把V 的每一行认为是存在在$R^k$空间内的一个数据点，划分它为k类
4. 根据变换后的点被分配的簇，把原数据也分配到对应的簇。

在实际应用中MS算法取得了一定效果，但当度矩阵D中各对角线元素差别较大时，聚类效果会较差。

现有算法

• 改进的谱聚类集成算法研究与应用--2014，硕士学位论文

  1. 提出了一种基于压缩感知(CS)谱聚类(SC)的集成算法，将其应用于高光谱图像的分割。压缩后的随机特征，k 均值算法的随机初始化以及Nyström 逼近为该集成算法提供了必要的多样性。与此同时将该算法得到的分割图，与SVM 得到的分类图应用空谱分类的思想结合在一起，用以实现对高光谱图像的最终分类。
  2. 在约束谱聚类(CSP，半监督谱聚类算法)的基础上提出了一种聚类集成算法，该算法不仅充分利用了已知的先验信息，同时相对于单个学习器，算法性能更加稳定。算法中由多个聚类结果得到的互联合矩阵作为一种新的约束信息加入到谱聚类算法中以得到最终的聚类结果。此外，为了避免尺度参数的选择，个体谱聚类的尺度参数在有限区间内随机选择，这同时增加了集成系统的多样性。
  3. 针对谱聚类算法复杂度过高不适于处理大规模数据的问题，我们首先利用Autoencoder 构造的深度学习网络对原始的样本数量进行约减，然后在处理后的少量样本集中进行谱聚类，并提出了两种方法来得到原始样本集上的聚类结果。

• 基于随机投影和谱聚类的SAR图像地物分割方法研究--2014，硕士学位论文

  1. 引入随机投影方法，对待分割图像数据进行降维；其次，使用改进相似性测度的谱聚类算法对降维后的数据聚类，根据聚类结果得到带有标记的SAR地物类别。从得到的实验结果可以看出，相对于传统的谱聚类算法，本文的方法即使在很低的采样率下，分割的结果依旧保持相对鲁棒。
  2. 由于SAR不断提升，图像数据的特性越发被人们所熟知，将二维随机观测引入Nystrom谱聚类算法中，并通过小波包和灰度共生矩阵提取特征。本文的方法利用使用了随机投影对规模庞大的数据点进行简单、有效的降维，从得到的实验结果可以看出，本文所提出的方法产生了较为有效的结果。
  3. 随机投影相关理论得到：通过随机投影观测可以保证映射到低维的数据能够保持高维数据所具有的特性，在变换的维数相对足够充分时。在我们应用中，还会有一定的冗余存在在于换的向量中，需要对该信号去冗余处理。进而本文提出了基于随机投影和正交局部保持投影的谱聚类的SAR地物方法。本文的方法从实验结果可以看出，其有效地被验证，得到了较好的分割效果。

• 基于协同进化和谱聚类的大规模数据集快速聚类方法研究--2014，硕士学位论文

  本章介绍了一种基于稀疏近邻传播的快速谱聚类算法。首先通过构造数据稀疏图，从而简化了一般谱聚类算法构造的稠密相似度矩阵，使其变为一个稀疏的相似度矩阵。接着，采用近邻传播算法选择出具有代表性的数据点。这样输入的是一个稀疏的相似度矩阵，所以近邻算法的时间复杂度大大降低。最后，对于这些代表点，采用LSC的方法，找到所有数据点所属的类别。

• 谱聚类算法分析及其在高维情形下的应用--2014，硕士学位论文

  对谱聚类算法进行了推广，将谱聚类算法推广到高维情形，给出了一种数据维数较高时的谱聚类算法。该算法的核心思想是先对高维数据通过随机投影进行降维得到维数较低的数据，再对降维以后的数据使用谱聚类算法。因为使用的降维技术是随机投影，为了克服随机投影降维经常出现的降维结果不稳定的缺点，本文在聚类算法上进行了改进：通过多次对原始数据使用随机投影得到降维数据后计算相似矩阵，再对得到的相似矩阵的每一个元素取平均，最后对取平均后的相似矩阵进行谱聚类算法中的操作。

• 基于特征值和谱聚类的极化SAR图像分割--2014，硕士学位论文

  提出了一种基于特征值度量谱聚类的极化SAR 图像分割方法。分析了极化相干矩阵特征值的统计特性，构造了一致性约束的相似度矩阵；将这种构造方式用于Nyström 谱聚类算法(快速谱聚类算法)完成对极化SAR图像的分割，并通过谱聚类集成来稳定分割结果。

• 基于谱聚类的复杂网络社团结构发现算法--2014，硕士学位论文

  给出了谱聚类算法在探索复杂网络社团结构问题上的应用

• 基于面向对象SVM和谱聚类的极化SAR分类--2014，硕士学位论文

  介绍了一种基于支持向量机和谱聚类的极化SAR分类方法，该方法的主要思想是利用支持向量积对样本进行训练，然后取出其支持向量，这一过程可以看做是降维，然后在降维的基础上进行谱聚类，根据支持向量求出聚类的中心，然后利用聚类的中心完成其它样本的最终分类。

• 基于免疫克隆选择优化和谱聚类的复杂图像分割--2014，博士学位论文

  提出了基于非负矩阵分解的谱聚类集成SAR 图像分割方法。通过不同采样点集合、不同尺度参数以及不同的空间位置权重，采用基于逼近的谱聚类算法来产生多样性的个体分割结果，然后利用非负矩阵分解的方法进行合并，产生最终的分割结果

• Denoised Kernel Spectral Data Clustering--IEEE Conference

  核谱聚类(KSC)在原始对偶框架下解决了加权核主成分分析问题，它是使用优化问题的对偶解在数据的子集中建立非监督模型。对未知数据点的推广性能好。但是对于含噪声的数据，泛化能力就减弱了。本文提出了用于聚类含噪数据的两步处理法。首先用基于最新提出的MDD(基于逐点距离分布的模型选择标准)为KPCA提供参数，KPCA(核主成分分析)消除噪声的干扰以获得数据的潜在信息，这种方法能更好的保留数据的结构信息。然后使用KSC，以获得优质的聚类。

• Agglomerative Hierarchical Kernel Spectral Data Clustering--IEEE Conference

  将AH-KSC技术从网络移植到数据集和图像中。使用BAF(balanced angulat fitting)标准估计最优的核参数。然后这些参数的特征投影的方法确定一系列增加的距离阈值。然后迭代建立亲和度矩阵建立一个自下而上的凝聚分层组织。

• Adaptive Spectral Co-clustering for Multiview Data--IEEE Conference

  提出了新的谱聚类方法用于处理多维视角的数据。新方法中使用了协同训练的方法。当数据有多于3个视角时，在一般的协同训练中很难处理不同视角数据之间的相关性。为此，当信息在训练阶段的时候，本文提出的方法将反映出不同视角下的数据的相关性。在嵌入谱的过程中，不同视角下的相关性被找到。当选定一个视角时，将通过使用微笑线性模型最小化相关因子构造其他视角的新的数据，这样一来，新的其他视角的数据保留信息的同时，与选定的视角相互独立。嵌入谱完成之后，使用一般的谱聚类算法即可。Spectral Co-clustering for Multiview Data是在2011年提出的。

• Spectral Clustering Method for High Dimensional Data based on K-SVD--IEEE conference

  通过SVD字典学习获得字典中所有数据样本的稀疏代表因子。稀疏代表因子矩阵标准化得带相似度矩阵，最后使用相似度矩阵进行谱聚类。

• GANY: A Genetic Spectral-based Clustering Algorithm for Large Data Analysis

  提出了基于Nystrom、谱、遗传算法的一种新的谱聚类算法，GANY。GANY使用一种结合谱投影的遗传编码。

• Unsupervised Classification of PolSAR data using large scale spectral clustering

  为了减少相似度矩阵的计算压力，建立数据点和从数据代表点的数据集之间的两偶图和，然后利用两偶图建立一个大尺度的近似图，在近似图上用奇异值分解做谱分析，为完善环境信息，引入基于平滑的马尔科夫随机场以得到最后的聚类。未来的工作时定量评估和自动选择合适的聚类参数。

• Self-adaptive Spectral Cluster Number Detecting with Particle Swarm Optimization Algorithm

  本文使用一种用于模糊聚类的有效性测量来确定基于粒子群优化的谱聚类的分类数量

• Hypergraph-Based Spectral Clustering for Categorical Data

  提出了一种基于超图模型的用于分类数据的谱聚类算法。

总结

各种谱聚类算法主要在一下几个方面存在差异：

1. 构造的矩阵不同；
2. 使用的矩阵的特征向量不同；
3. 由特征向量获得最后聚类结果的方法不同；
4. 使用的谱放松方法不同，即由连续变量获得离散变量的方法不同

会议论文的方向主要是处理高维和大量数据、多维视角的数据、含噪声的数据，据此提出不同的算法。

研究展望

1. 如何构造相似矩阵W。由于核参数$W_{ij}=e^{-\frac{||x_i-x_j||^2}{2\sigma ^2}}$是人为选取的，使得该函数带有一定的局限性。Zelnil—Manor和Perona提出了Self-Tuning算法(Self-tuning spectral clustering 2004)，以根据数据集自身情况自己的确定参数。Fisher也提出了一种动态确定参数的方法(Robust path-based spectral clustering 2008)。Normalized Cuts and Image Segmentation(2000)提出可以将权重小于某一阈值的边权重都置为零, 利用由此得到的稀疏权矩阵（接近理想矩阵）的特征向量来近似原相似度矩阵的特征向量。有一些学者借助“路径”对W进行进一步优化。
2. 如何处理特征向量。在应用谱方法进行聚类问题的研究中，用多少个特征向量进行聚类，如何选取、计算及使用这些特征向量等问题均没有得到很好的理论解释，这些都是未来急需解决的问题。08 年Xiang等人提出这前k个特征向量不一定是最好的，相关度较高，信息量较多的特征向量得到的聚类效果更好。
3. 如何选取Laplacian矩阵：谱聚类算法所使用的Laplacian矩阵有三种形式，但这三种形式的Laplacian矩阵所应用的具体环境还没有得到彻底解决。
4. 如何自动确定聚类数目：聚类数目的多少直接影响聚类的质量。已有的自动确定聚类数目的谱聚类算法有：基于Rcut的谱聚类算法，非线性降维算法和基于距离的启发式方法(eigen gap)。但用这些算法在一些公共数据集上得出的聚类数和相应的聚类结果都不能令人满意。还有学者研究谱聚类在多处理器上的并行实现，从而加快算法的运行速度。
5. 如果数据本身存在不相关特征，此时算法往往表现很差
6. 如何运用到大规模数据和流数据：谱聚类的时间和空间复杂度相当高，很难对大规模数据进行处理。Fowlkes等人提出了Nystrom近似的方法,而U．Luxburg．等人则提出使用稀疏化矩阵的方法。09 年，Yan 等人提出Fast Approximate 谱聚类。
7. 不适于具有不规则混乱背景以及多尺度的聚类问题；
8. 如何与深度学习相融合。An empirical comparison of spectral learning methods for classification介绍了谱算法中算子谱刻画映射的能力，学者们开始思考将谱聚类算法与深度学习相结合并帮助提高算法效率。