[关闭]
@hainingwyx 2017-05-12T02:29:20.000000Z 字数 7163 阅读 5611

谱聚类算法概述

聚类


写在之前

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

应用领域

语音识别、视频分割、图像分割、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 行向量规范化,并构建新矩阵
  3. 根据Q矩阵中对应元素的值进行聚类。在理想情况下
    表示两点被分在同一类,
    表示两点被分在不同类。而在一般情况下,当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进行特征值分解,然后选取特征向量构成空间,这些向量由前k个最大特征值对应的特征向量组成,使原数据与空间中的每一点一一对应,最后应用k均值等经典算法在空间完成聚类。

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

对于n个数据点,相似度矩阵的大小为。计算特征向量的复杂度为

MS算法

算法描述

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

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

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

概述.png

现有算法

总结

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

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

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

研究展望

  1. 如何构造相似矩阵W。由于核参数是人为选取的,使得该函数带有一定的局限性。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介绍了谱算法中算子谱刻画映射的能力,学者们开始思考将谱聚类算法与深度学习相结合并帮助提高算法效率。
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注