谱聚类综述论文

《谱聚类综述论文》由会员分享，可在线阅读，更多相关《谱聚类综述论文（6页珍藏版）》请在金锄头文库上搜索。

1、谱聚类综述论文1. 引 言聚类分析是数据分析中最常用的方法之一。 所谓聚类， 就是将数据点划分为若干个 类或簇， 使得同一类中的数据点之间具有较高的相似度， 而不同类中的数据点之间具有较高 的相异度。 传统的聚类算法， 如 K-means 算法、 EM 算法等都是建立在凸球形的样本空间上， 当样本空间非凸时，算法易陷入局部最优。为了能在任意形状的样本空间上聚类， 且收敛于全局最优， 一类新型的聚类算法 谱聚类被提出。 谱聚类根据样本间的相似关系建立矩阵， 通过计算特征向量找出数据样本 间的内在联系。与传统的聚类算法相比，谱聚类算法具有诸多优点：(1) 直接通过求解拉普拉斯矩阵的特征向量进行划分

2、， 不含有凸球形数据分布的隐性假设， 从而能够识别非凸类型 的簇； (2) 用现有的线性代数软件可以直接求解拉普拉斯矩阵的特征向量，实现简单；(3) 谱聚类仅与数据点的数目有关， 而与维数无关， 因而可以避免由高维特征向量造成的奇异性问 题；(4) 诸多数据集上的对比实验表明， 谱聚类的性能优于一般的聚类算法； (5)可用于大规 模数据集。 基于上述优点， 谱聚类被广泛应用于计算机视觉 1 、语音识别 2、VLSI 设计 3、 文本挖掘 4 等领域。近年来，谱聚类作为一种非常有前途的聚类算法，吸引了众多学者对其进行研究、 改进， 出现了许多成功的谱聚类的改进算法。 本文作为一篇综述性的文章，

3、旨在对现有的谱 聚类改进算法分类进行详细介绍， 使读者能够更加系统、 全面地了解该领域的研究现状， 促 进该领域的发展。 本文首先从图分割的角度介绍了谱聚类的基本原理和经典算法， 然后重点 分类介绍了谱聚类的改进算法，最后进行归纳总结，提出未来的几个研究向。2. 谱聚类的基本原理和算法2.1 聚类与图划分问题对于给定的 n 个 d 维的数据点 x , x , , xn 1 2 L ，聚类的目标是将这 n 个点分成 k 个簇，使得同一簇中的数据点比较相似，不同簇中的数据点比较相异。假设将数据点 i x 看 作图中的一个顶点 i v ，将两点之间的相似度作为边的权重 ij W ，这样就得到一个基于

4、相 似度的无向图 G = (V , E )，其中V是顶点的集合，E是边的集合。新的目标函数都在寻求一种类内相似度尽可能大，类间相似度尽可能小的最优划 分，同时兼顾了划分的均衡性。 但是它们均被证明为 NP 难解问题 9 。而谱聚类则是一种利 用特征向量求得这些问题近似解的新聚类算法。2.2 谱聚类的基本原理首先介绍三种常见的拉普拉斯矩阵，根据 Rayleigh-Ritz 理论，谱聚类算法求得的 拉普拉斯矩阵的若干特征向量就是最优划分问题松弛后的近似解。2.3 谱聚类算法框架和经典算法谱聚类算法的基本步骤如下：(1) 根据某种相似度定义，由原始的数据集构建相似度矩阵W 。(2) 由相似度矩阵构建

5、拉普拉斯矩阵，并求解它的某些特征向量。以这些向量作列， 构建矩阵 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

6、提出可以基于邻接矩阵的特征向量建立图的划分 11。同年， Fiedler 建议用拉普拉斯矩阵的第二特征向量进行图划分 12。 此后，很多人对谱聚类算法进行了深入的研究。从 2000 年开始，谱聚类逐渐成为机器学习 领域的一个研究热点。这主要得益于以下三个经典谱聚类算法的提出：(1)2000年，Shi和Malik提出Ncut算法7。先求满足等式Lx = IDx的特征向量(即 rw L 的特征向量)，再用 k-means 进行聚类，找出数据的内在联系。2001年，Meila和Shi将两点间的相似度解释为Markov链中随机游走的概率，并尝试使用概率转移矩阵 P = D W = I - Lrw -1

7、 的特征向量进行聚类，从另一个角度解释了 谱聚类 13 。(3)2001 年， Ng 等提出 NJW 算法14。它首先求 sys L 的特征向量，再对特征向 量作列构成的矩阵 H 的每一行进行归一化，最后用 k-means 进行后处理，克服了 Meila 和 Shi算法当各个簇的簇内总度数()i assoc A差别大时效果不理想的缺点，稳定性更好，是最常用、最经典的谱聚类算法之一。3. 谱聚类的改进 尽管谱聚类具有坚实的理论基础谱图理论，并且在实践中也取得了很好的效果，但是它仍然存在一些问题。 下面按照前面提到的谱聚类基本步骤， 分类介绍学者们针对 这些问题，对谱聚类所进行的改进。3.1 如何

8、创建相似度矩阵 W如何创建相似度矩阵 W ，使其更加真实地反映数据点之间的近似关系，使得相近 点之间的相似度更高， 相异点之间的相似度更低， 是每个谱聚类算法必须要解决的一个问题。 这方面的改进主要包括以下三个方面：3.1.1 对高斯核函数的改进 经典谱聚类算法中计算两点间相似度使用的是高斯核函数。 虽然该函数使原始的谱 聚类算法取得了一些成功，但其中存在一个明显的问题，即如何确定参数s。NJW算法提出可以预先指定几个 s 的值 ,代写硕士论文， 分别执行谱聚类， 最后选取使聚类结果最好的 s 作 为参数，但这样运算时间就增加了。3.1.2 对 W 的进一步优化理想情况下，同一个类的两点间相似

9、度为 1，不同类的两个点间相似度为0。根据相似度函数求得初始的相似度矩阵后，可以对 W 做进一步的优化，使其更接近理想矩阵， 更有利于聚类。文献 7 提出可以将权重小于某一阈值的边权重都置为零，利用由此得到的稀疏权矩阵 （接近理想矩阵） 的特征向量来近似原相似度矩阵的特征向量。Fischer 在提出基于路径的聚类后， 又将路径与高斯核函数相结合， 提出基于路径的谱聚类 20 。2008 年 Chang 等在此基础上，利用 M-estimation ，通过增加权重，提出了健壮的基于路径的谱聚类算法， 能有效抵抗噪声的影响 21 。3.1.3 寻求获得 W 的新途径近年来，还有学者为了避免遇到人工

10、确定参数 s 的问题，提出在计算相似度时不使用高斯核函数。如 Gong等人借鉴 Wang等在半监督中使用的方法，将每个点的 k近邻对 该点进行线性近似表示时所占的权重作为两点间的相似度。通过求 n 个二次规划问题， 就可以求得相似度矩阵 W ，不再需要使用高斯核函数，大大降低了谱聚类算法对参数的敏感性， 使算法更稳定 22 23 。3.2 如何自动确定聚类数目由相似度矩阵得到拉普拉斯矩阵后， 接下来要确定特征向量的数目。 由前面的讨论 可知该数目等于要划分的聚类数目k。虽然可以事先由人工确定k，但面对一堆数据，即使是专家也不一定能准确地给出 k 的取值。而 k 的设定是否恰当直接影响到聚类效率

11、和最终 的聚类质量。因此，如何自动确定聚类数目成为谱聚类需要解决的一个关键问题。虽然一般聚类算法中提出的确定聚类数目 k 的方法也可以用于谱聚类， 但谱聚类常 用基于启发式的eigen gap方法来确定k。理想情况下，如果一个数据集中包含k个簇，则其对应的概率转移矩阵 P = D - 1W 的前 k 个最大特征值 k l , ,l 1 ? 均为 1，后面的第 k+1 个 特征值 k +1 l 会远小于 1，这样 k +1 l 与 k l 之间就存在一个较大的差值， 被称为 eigen gap。 基于该启发式规则，可以将特征值从大到小进行排列， 找到使得k I ,论文代写，1 1 ?都很大， 而

12、 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 个特征向量

13、进行聚类。 实验证明利用这些相关度较高， 信息量较多的特征向量 得到的聚类效果更好。2006年，Jenssen等人用Parzen窗估计Renyi熵，发现该熵的最大化与核矩阵（即高斯核函数求得的相似度矩阵） 有关 26。经推导发现 Renyi 熵最大化问题的近似解是核矩 阵的使 （1 ）2 iTi I e 取得较大值的前 k 个特征向量 （其中 i I 是特征值， i e 是对应的特征向 量， 1 表示元素全为 1 的列向量），而不是像 kerneI PCA 或原始谱聚类 （文献 27 证明了二者的等价性）那样只是简单地取核矩阵的前k个最大特征值对应的特征向量。3.4 如何创建相似度矩阵 W经典

14、谱聚类使用 k-means 对特征向量进行后处理。它首先将由特征向量构成的矩 阵 H 的每一行看作是从原始空间映射到特征空间的一个 k 维数据点，然后用 k-means 将这 些聚成 k 个簇，进而对应得到原数据的聚类结果。 Fisher 等人在文献 17 中提出也可以使用 k-lines 进行后处理。此外，由于映射后的数据点所形成的 k 个簇将彼此正交地分布于 k 维 特征空间中，比较容易聚类，因此后处理也可以使用其它简单的聚类算法如层次聚类等。3.5 如何加快谱聚类的运行速度 应用谱聚类不可避免地要求矩阵的特征值与特征向量。 求非稀疏矩阵特征向量的复 杂度为 O(n3 )，所以要处理海量数

15、据的时候，谱聚类的计算量会急剧增加，而且相似度矩 阵也会很大， 可能超出计算机的内存。 因此， 如何加快算法的运行速度， 减少运行所需的内 存空间成为谱聚类一个亟待解决的问题。最早提出的加速思想是稀疏化相似度矩阵，将权值小于阈值 e 的边权置零，使其 变为稀疏矩阵。 这样就可以采用 Lanczos 算法快速求得前 k 个特征向量 28 。其收敛速度和 eige ngap (即+1 - k k II )有关，eigen gap 越大，收敛越快。现有的一些加速算法则基于抽样原理，用小样本去估算原相似度矩阵的特征向量， 从而降低算法的时间和空间复杂度。如文献 29 提出对数据集进行抽样， 再利用 N

16、ystr?m 方法，根据抽样样本之间的相似度矩阵以及抽样样本与未抽样样本之间的相似度矩阵来近似 原相似度矩阵， 然后利用该近似矩阵的特征向量来近似原矩阵的特征向量。该方法被公认 为谱聚类最经典的加速算法。 09 年， Yan 等人提出 Fast Approximate 谱聚类 30 。首先利 用k-means或RP-tree，将数据分成若干个微簇，然后对从每个微簇选择的代表点进行聚类， 最后对应得到所有数据的类标号。 实验表明该加速算法能够使单个机器在几分钟之内完成百 万级数据的处理。此外，还有学者研究谱聚类在多处理器上的并行实现，从而加快算法的运行速度 31。4. 结论谱聚类是一种基于相似度矩阵的算法