谱聚类综述论文由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“聚类分析毕业论文”。
谱聚类综述论文
1.引 言
聚类分析是数据分析中最常用的方法之一。所谓聚类，就是将数据点划分为若干个类或簇，使得同一类中的数据点之间具有较高的相似度，而不同类中的数据点之间具有较高的相异度。传统的聚类算法，如K-means算法、EM算法等都是建立在凸球形的样本空间上，当样本空间非凸时，算法易陷入局部最优。
为了能在任意形状的样本空间上聚类，且收敛于全局最优，一类新型的聚类算法——谱聚类被提出。谱聚类根据样本间的相似关系建立矩阵，通过计算特征向量找出数据样本间的内在联系。与传统的聚类算法相比，谱聚类算法具有诸多优点：(1)直接通过求解拉普拉斯矩阵的特征向量进行划分，不含有凸球形数据分布的隐性假设，从而能够识别非凸类型的簇；(2)用现有的线性代数软件可以直接求解拉普拉斯矩阵的特征向量，实现简单；(3)谱聚类仅与数据点的数目有关，而与维数无关，因而可以避免由高维特征向量造成的奇异性问题；(4)诸多数据集上的对比实验表明，谱聚类的性能优于一般的聚类算法；(5）可用于大规模数据集。基于上述优点，谱聚类被广泛应用于计算机视觉[1]、语音识别[2]、VLSI设计[3]、文本挖掘[4]等领域。
近年来，谱聚类作为一种非常有前途的聚类算法，吸引了众多学者对其进行研究、改进，出现了许多成功的谱聚类的改进算法。本文作为一篇综述性的文章，旨在对现有的谱聚类改进算法分类进行详细介绍，使读者能够更加系统、全面地了解该领域的研究现状，促进该领域的发展。本文首先从图分割的角度介绍了谱聚类的基本原理和经典算法，然后重点分类介绍了谱聚类的改进算法，最后进行归纳总结，提出未来的几个研究向。
2.谱聚类的基本原理和算法
2.1 聚类与图划分问题
对于给定的n个d维的数据点x , x , , xn 1 2 L，聚类的目标是将这n个点分成k个簇，使得同一簇中的数据点比较相似，不同簇中的数据点比较相异。假设将数据点i x 看作图中的一个顶点i v，将两点之间的相似度作为边的权重ij W，这样就得到一个基于相似度的无向图G =(V , E），其中V是顶点的集合，E是边的集合。
新的目标函数都在寻求一种类内相似度尽可能大，类间相似度尽可能小的最优划分，同时兼顾了划分的均衡性。但是它们均被证明为NP难解问题[9]。而谱聚类则是一种利用特征向量求得这些问题近似解的新聚类算法。
2.2 谱聚类的基本原理
首先介绍三种常见的拉普拉斯矩阵，根据Rayleigh-Ritz理论，谱聚类算法求得的拉普拉斯矩阵的若干特征向量就是最优划分问题松弛后的近似解。
2.3 谱聚类算法框架和经典算法
谱聚类算法的基本步骤如下：
(1)根据某种相似度定义，由原始的数据集构建相似度矩阵W。
(2)由相似度矩阵构建拉普拉斯矩阵，并求解它的某些特征向量。以这些向量作列，构建矩阵H ??n?k。
(3)用k-means等经典聚类算法将H中的各行聚成k个簇k S , S , , S 1 2 L。最终将点i x 分到簇j A 中，当且仅当H中i x 对应的第i行在k-means中被分配到簇j S 中。
除了这种常用的多路谱聚类直接将数据划分为k类外，还有二分谱聚类。它对数据集不断进行迭代二分，直到满足一定的终止条件。
大多数谱聚类算法都是基于多路谱聚类框架的，只是某些细节的实现略有不同。最早关于谱聚类的研究始于1973年，当时，Donath和Hoffman提出可以基于邻接矩阵的特征向量建立图的划分[11]。同年，Fiedler建议用拉普拉斯矩阵的第二特征向量进行图划分[12]。此后，很多人对谱聚类算法进行了深入的研究。从2000年开始，谱聚类逐渐成为机器学习领域的一个研究热点。这主要得益于以下三个经典谱聚类算法的提出：
(1)2000年，Shi 和Malik提出Ncut算法[7]。先求满足等式Lx = lDx的特征向量(即rw L 的特征向量），再用k-means进行聚类，找出数据的内在联系。
(2)2001年，Meila 和Shi将两点间的相似度解释为Markov链中随机游走的概率，并尝试使用概率转移矩阵P = D W = I1W 的前k 个最大特征值k l , ,l 1 ? 均为1，后面的第k+1 个特征值k +1 l 会远小于1，这样k +1 l 与k l 之间就存在一个较大的差值，被称为eigen gap。基于该启发式规则，可以将特征值从大到小进行排列，找到使得k l , ,论文代写,l 1 ? 都很大，而k +1 l 却很小的k值作为要划分的聚类数目。
后来，Azran和Ghahramani于2006年提出，根据M步随机游走后的概率矩阵P M 的eigengap确定的k值要比根据原始概率矩阵P 的eigen gap确定的k值更准确，更接近真实的聚类数目[24]。
3.3 如何选择特征向量
原始的谱聚类算法直接选择前k 个特征值对应的特征向量进行求解。但是08 年Xiang等人提出这前k个特征向量不一定是最好的，应选择最有用的前k个特征向量进行聚类[25]。他们提出了“向量相关度”的概念，用该定义衡量每个向量的相关度，从而选出相关度最高的k个特征向量进行聚类。实验证明利用这些相关度较高，信息量较多的特征向量得到的聚类效果更好。
2006 年，Jenen等人用Parzen窗估计Renyi 熵，发现该熵的最大化与核矩阵(即高斯核函数求得的相似度矩阵）有关[26]。经推导发现Renyi 熵最大化问题的近似解是核矩阵的使(1）2 iTi l e 取得较大值的前k 个特征向量(其中i l 是特征值，i e 是对应的特征向量，1 表示元素全为1 的列向量），而不是像kernel PCA或原始谱聚类(文献[27]证明了二者的等价性）那样只是简单地取核矩阵的前k个最大特征值对应的特征向量。
3.4 如何创建相似度矩阵W
经典谱聚类使用k-means 对特征向量进行后处理。它首先将由特征向量构成的矩阵H的每一行看作是从原始空间映射到特征空间的一个k维数据点，然后用k-means 将这些聚成k个簇，进而对应得到原数据的聚类结果。Fisher 等人在文献[17]中提出也可以使用k-lines 进行后处理。此外，由于映射后的数据点所形成的k个簇将彼此正交地分布于k维特征空间中，比较容易聚类，因此后处理也可以使用其它简单的聚类算法如层次聚类等。
3.5 如何加快谱聚类的运行速度
应用谱聚类不可避免地要求矩阵的特征值与特征向量。求非稀疏矩阵特征向量的复杂度为O(n3），所以要处理海量数据的时候，谱聚类的计算量会急剧增加，而且相似度矩阵也会很大，可能超出计算机的内存。因此，如何加快算法的运行速度，减少运行所需的内存空间成为谱聚类一个亟待解决的问题。
最早提出的加速思想是稀疏化相似度矩阵，将权值小于阈值e 的边权置零，使其变为稀疏矩阵。这样就可以采用Lanczos 算法快速求得前k 个特征向量[28]。其收敛速度和eigengap(即+1-k k l l）有关，eigen gap越大，收敛越快。
现有的一些加速算法则基于抽样原理，用小样本去估算原相似度矩阵的特征向量，从而降低算法的时间和空间复杂度。如文献[29]提出对数据集进行抽样，再利用Nystr?m方法，根据抽样样本之间的相似度矩阵以及抽样样本与未抽样样本之间的相似度矩阵来近似原相似度矩阵，然后利用该近似矩阵的特征向量来近似原矩阵的特征向量。该方法被公认为谱聚类最经典的加速算法。09 年，Yan 等人提出Fast Approximate 谱聚类[30]。首先利用k-means或RP-tree，将数据分成若干个微簇，然后对从每个微簇选择的代表点进行聚类，最后对应得到所有数据的类标号。实验表明该加速算法能够使单个机器在几分钟之内完成百万级数据的处理。
此外，还有学者研究谱聚类在多处理器上的并行实现，从而加快算法的运行速度
[31]。
4.结论
谱聚类是一种基于相似度矩阵的算法，不需要事先知道数据的真实分布，而且实现
简单，性能又优于一般的聚类算法，因此被广泛应用于各个领域。本文主要从以下三个方面对谱聚类进行了综述：
(1)从谱图分割的角度解释了谱聚类算法的合理性。
(2)结合谱聚类的经典算法，给出了谱聚类的基本框架。
(3）将现有的谱聚类改进算法，从改进原因，改进基于的原理和改进后的效果等方面，分类进行了详细的介绍和分析。
虽然谱聚类算法的性能经过改进得到了很大的提高，但是仍然存在一些问题没有得到充分解决。
第一，如何定义相似度。如何能够更准确地反映数据点之间真实的近似程度，使求得的相似度矩阵的块对角性更明显，是定义一个好的相似度必须解决的问题。
第二，如何选择特征向量。采用哪种形式的拉普拉斯矩阵，选择拉普拉斯矩阵的多少特征向量以及哪些特征向量聚类都是谱聚类算法需要妥善解决的现实问题。
第三，如何处理海量数据和流数据
