谱聚类算法毕业设计.docx

沈阳理工大学学士学位论文摘 要谱聚类作为一类新兴的、有效的聚类方法得到广泛的关注，并已成功的应用于图像分割。本文研究基于谱聚类的图像分割技术，并成功的应用到图像分割中。本文主要工作如下:谱聚类算法是利用图像的相似性矩阵进行图像分割，如何构造一个对图像信息表达更充分的相似性矩阵，对算法性能有很大影响。本文应用Nystrom谱聚类算法进行图像分割技术的研究，而且还具有良好的方向分析能力，它能反映出图像在不同分辨率上沿多个方向的变化，能更好地描述图像的几何结构。该方法为的是在聚类的时候取得较好且稳定的性能，然而KHM仅在对低维数样本聚类时较KM算法要好。为了缓解谱聚类对初始化敏感的问题，本文采用了基于优化策略的K均值算法，实现了基于Nystrom谱聚类的图像分割方法。通过在Nystrom谱聚类算法仿真实验表明:本文的方法无论在细纹理、粗纹理、非均匀纹理和混合纹理上，其视觉效果和评价指标上都要优于的方法。关键词:图像分割;谱聚类；Nystrom谱聚类算法；K-Means聚类算法AbstractSpectral clustering as a class of new and effective clustering method has beenwidely concerned and successfully applied in image segmentation. The imagesegmentation algorithm, based on initialization-independent multi-parameter kernelspectral clustering which was raised by Ma Xiuli, has been researched, improved andsuccessfully applied in texture image and SAR image segmentation in this dissertation.The main achievement of this dissertation can be summarized as follows:Spectral clustering uses the image similarity matrix in image segmentation.How to construct a similarity matrix which expresses more information of image has agreat influence on algorithm performance. It can reflect that image changes on different resolutions along several directions, anddescribe the geometry of image better.K-means based on optimization strategy has been adopt to realize the imagesegmentation based on complex wavelet feature and spectral clustering. A large numberof simulation experiments in Brodatz library show that: In terms of fine texture, roughtexture, non-uniform texture and blending textures, our method is better than themethod according to the visual effects and evaluation indicators.Keyword: Image Segmentation；Spectral Clustering Dual-Tree Complex；K means Spectral Clustering目 录1 绪 论11.1数字图象处理技术11.1.1 简介11.1.2 图像处理的主要目的11.1.3常用方法11.2图像分割技术11.3MATLAB编程软件的介绍21.3.1简介21.4谱聚类的简述21.4.1 简介21.4.2 图划分准则21.5课题研究的目的及本文的主要内容32 图像分割技术与边缘检测42.1 图像分割定义和方法分类42.1.1 图像分割的定义42.1.2 图像分割算法52.1.3灰度阈值分割52.1.4 阈值法62.2 边缘检测算子62.2.1 基于边缘检测的分割62.2.2 普通梯度算子72.3 区域生长82.3.1 区域生长的主要步骤92.4本章小结93 谱聚类算法分析与研究103.1 基本理论103.1.1 图和矩阵的表示103.1.2 谱图理论133.1.3 图划分准则133.1.4 相似度矩阵、拉普拉斯矩阵153.2 谱聚类算法163.2.1 谱聚类算法163.2.2 谱聚类算法与K_Means算法的比较183.3 谱聚类算法存在的问题以及研究进展203.4 本章小结214 基于Nystrom谱聚类图像分割算法研究224.1 Nystrom谱聚类算法224.1.1 Nystrom扩展方法224.1.2 Nystrom 扩展谱聚类算法234.1.3 Nystrom谱聚类图像分割算法244.2 程序流程图264.3 仿真与分析274.3.1结果274.3.2分析284.5 本章小结28结 论29致 谢30参考文献31附录A 英文原文32附录B 中文翻译40附录C 计算程序45IV1 绪 论1.1 数字图象处理技术1.1.1 简介数字图象处理（Digital Image Processing）又称为计算机图像处理，它是指将图像信号转换成数字信号并利用计算机对其进行处理的过程。1.1.2 图像处理的主要目的（1）提高图像的视感质量，如进行图像的亮度、彩色变换，增强、抑制某些成分，对图像进行几何变换等，以改善图像的质量。（2）提取图像中所包含的某些特征或特殊信息，这些被提取的特征或信息往往为计算机分析图像提供便利。提取特征或信息的过程是模式识别或计算机视觉的预处理。提取的特征可以包括很多方面，如频域特征、灰度或颜色特征、边界特征、区域特征、纹理特征、形状特征、拓扑特征和关系结构等。（3）图像数据的变换、编码和压缩，以便于图像的存储和传输。1.1.3常用方法 图像变换，图像编码压缩，图像增强和复原，图像分割，图像描述，图像分类（识别）。1.2 图像分割技术图像分割技术：图像分割是数字图像处理中的关键技术之一。图像分割是将图像中有意义的特征部分提取出来，其有意义的特征有图像中的边缘、区域等，这是进一步进行图像识别、分析和理解的基础。虽然已研究出不少边缘提取、区域分割的方法，但还没有一种普遍适用于各种图像的有效方法。因此，对图像分割的研究还在不断深入之中，是图像处理中研究的热点之一。1.3 MATLAB编程软件的介绍本论文运用matlab来进行编程，下面来介绍一下MATLAB编程软件。1.3.1简介MATLAB是一款由美国MathWorks公司出品的主要对科学计算、可视化以及交、互式程序设计的高科技计算软件。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模系统的建模和仿真等诸多强大功能集成在一个抑郁使用的视窗环境中。MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分先相似，故用MATLAB来解算要比C等语言完成相同的事情简捷的多。本论文运用版本是MATLAB2010b，在这个版本中也加入了对C、C+、Java的支持，可以直接调用。 1.4 谱聚类的简述1.4.1 简介谱聚类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并且计算矩阵的特征值和特征向量，然后选择合适 的特征向量聚类不同的数据点。谱聚类算法建立在图论中的谱图理论基础上，其本质是将聚类问题转化为图的最优划分问题，是一种点对聚类算法，对数据聚类具有很好的应用前景。1.4.2图划分准则常见的划分准则有(1)最小割集准则：（Minimum cut)(2)规范割集准则：（Normalized cut）(3)比例割集准则：（Ratio cut）(4)平均割集准则：（Average cut）(5)最小最大割集准则：（Minmax cut）(6)多路规范割集准则（Multiway Normalized cut）1.5 课题研究的目的及本文的主要内容本章介绍了本文各项理论基础的简述。第二章 将详细介绍图像分割技术的基本理论，然后详细介绍各个算法的应用，及发展前景。第三章 将详细介绍谱聚类的基本理论，然后详细介绍了谱聚类在图像分割中的应用算法、存在的问题以及研究的进展。第四章 针对上两章给出nystrom算法对目标图像进行分割处理，并写明操作的流程图。由于编程较多因此不写入本论文中。对程序的运行，检查，以及调整。实现其结果。最后对本论文进行总结，并结合论文工作提出进一步展望。2 图像分割技术与边缘检测2.1 图像分割定义和方法分类图像分割是将图像中有意义或有用的特征提取出来，也可以说，将图像分成各具特点的区域并提取出感兴趣目标的技术和过程。图像分割是由图像处理到图像分析的关键步骤。图像读入（光电转换）图像处理（增强，编码）图像分析（分割，描述）图像理解（解释，理解）光图像数字图像处理过的图像解释判断特征数据图2.1 一般的图像处理过程2.1.1 图像分割的定义令集合R代表整个图像区域，对R的分割可看作将R分成若干个满足以下5个条件的非空子集（子区域）R1，R2 ，Rn （2.1） 对所有的i和j，ij，有 （2.2） 对i=1，2，n，有P（Ri）=TRUE （2.3） 对ij，有 P（RiRj）=FALSE （2.4） 对i=1，2，n，Ri是连通域。 其中P（Ri）代表所有集合Ri中元素的某种性质。2.1.2 图像分割算法根据相邻象素在象素值方面的相似性和不连续性可分为区域法和边界法；根据处理策略不同分为串行算法和并行算法。表2.1分割目标与处理方法边界区域并行处理PB（Boudary-Based Parallel Techniques）并行边界技术，如微分算子PR(Region-Based Parallel Techniques)并行区域技术，如阈值串行处理SB(Boundary-Based Sequential Techniques)串行边界技术，如边沿跟踪SR(Region-Based Sequential Techniques)串行区域技术，如四叉树分割2.1.3 灰度阈值分割灰度阈值分割是一种常见的分割方法，由于它实现的直观性和简单性，它在图像分割中占有十分重要的地位。灰度阈值分割法就是根据图像的不同灰度级来选取一个合适的灰度阈值，以此来确定有意义的区域或者分割物体的边界。灰度阈值分割法就是将图像进行二值化处理，即选择一个阈值，将原始图像转换成黑白二值图像。灰度阈值分割法的处理函数如下： gx,y=0 0&fx,yT255 T&fx,yT2），T1用来找到每条线段，T2用来在这些线段的两个方向上延伸寻找边缘的断裂处，并连接这些边缘。2.3 区域生长区域生长的基本思想：将具有相似性质的像素结合起来构成区域。具体先对每个需要分割的区域找一个种子像素作为生长的起点，然后将种子像素周围邻域中与种子像素有相同或相似性质的像素(根据某种事先确定的生长或相似准则来判定)合并到种子像素所在的区域小。将这些新像素当做新的种子似素继续进行上面的过程，直到再没有满足条件的像素可被包括进来，这样一个区域就长成了。在实际应用区域生长法时需要解决三个问题：(1)选择或确定一组能正确代表所需区域的种子像素；(2)确定在生长过程中能将相邻像素包括进来的准则；(3)制定让生长过程停止的条件或规则。2.3.1 区域生长的主要步骤：(1)对图像进行逐行扫描，找出尚没有归属的像素；(2)以该像素为中心检查它的邻域像素，即将邻域中的像素逐个与它比较，如果灰度值小于预先确定的阈值，将它们合并；(3)以新合并的像素为中心，返回步骤2，检查新像素的邻域，直到区域不能进一步扩张；(4)返回到步骤1，继续扫描到不能发现没有归属的像素，则结束整个生长过程2.4 本章小结本章介绍了图像分割技术和边缘检测。具体介绍了图像分割定义，图像分割的算法（串行算法和并行算法），灰度阈值分割。详细介绍了阈值法，由于图像背景大多较为复杂，尤其地物区域间灰度混叠严重，再加上斑点噪声的影响，使得图像的灰度直方图呈现不规则变化，利用阈值进行自动分割就较为困难。针对图像的阈值分割方法主要研究阈值的自适应选择以进行更有效的分割，但对于地物交错的复杂区域其分割效果仍不理想。也介绍了边缘检测的几种算子（Roberts 算子，Sobel 算子，Prewitt 算子，拉普拉斯算子，Canny 算子）以及区域生长。3 谱聚类算法分析与研究3.1 基本理论近些年来，谱聚类算法渐渐成为了机器学习领域的研究热点，其是一种建立在谱图理论基础上有效的方法。可将它的思想简单的表述为：首先把聚类相关问题转变为带权无向图的多路划分问题，然后使用一种有效的连续松弛形式的方法将图划分问题转变为特征分解问题，可以理解为计算包含待聚类数据的所有信息矩阵的特征值和特征向量，再使用经典K-Means聚类算法对计算出来的特征向量进行聚类操作，继而得到划分结果。谱聚类算法仅与数据点的数目有关，而与数据维数无关，因而可以避免由高维特征向量造成的奇异值问题。研究学者利用了谱聚类算法能在任意形状的样本空间上聚类，且收敛于全局最优解的优点，解决了很多原先棘手的问题，因此谱聚类算法的研究具有重大意义。目前，谱聚类算法的应用尚且处于初级阶段，主要是因为所涉及的理论知识较多，很大程度的限制了它的应用发展。3.1.1 图和矩阵的表示本文所讨论的图是指某类具体事物和这些事物之间的联系。如果我们用点表示具体的事物，两事物之间用连线来表示它们之间的关系，该连线我们称为两点之间的边，那么，一个图就是由一个表示具体事物的点集合和表示事物之间联系的边的集合所构成。定义非空点集和中元素的无序对的一个集合 构成了图的二元组，记为简记为，V(Vertex)中的元素称为顶点。顶点是图中的基本元素，图中的每个顶点和我们所研究事物中的每个具体对象一一对应。E(Edge)中的元素称为边，边是图中的另一个基本的元素，在图中表现为有关联的两个顶点之间的连线。可以用表示图G中的边数，用表示图的顶点个数，在表示清楚的情况下的情况下简记和。对则称为与相邻，否则称为不相邻，记作。如果边、有一个公共顶点，那么称、相邻。必须规定一个图的顶点集合是非空的，因为至少有一个顶点才能成为图。权值是指赋予连接两个顶点的边上的值，它表示两个顶点之间关联的紧密程度，对应所研究事物中表示为具体的两个对象之间关联的紧密程度。边上的权值用或表示。边上有权值的图称为加权图（weightedgraph），再加上边的有向和无向性，可以把图分为：带权有向图和带权无向图。权值并不是一个图必不可缺少的元素，有些图中权值是可有可无。本文所用为带权无向图。顶点的度（degree）在图G中，与顶点相关联的边的总数称为是的度，记为。无混淆情况下简记为或。顶点的度的大小说明了图中顶点在图中和其它顶点的关联程度。度为0的顶点称为孤立（顶）点（isolatedvertex），度为1的顶点称为端点。而度大的顶点经常就是图的关键点。所以顶点的度和边权值都是在对图进行分割时要考虑的重要的参考因素。子图（sub-graph）设图,假如并且，则称图G1是图G的一个子图。如图3.1所示，G1和G2均为图G的子图。图3.1 图G的子图G1，G2一个图G的子图和子图，若满足，则称图G1和图G2互为补图。如图3.1中所示，图G1和图G2互为补图。设图的顶点集为,用表示图G中与之间的边。称为矩阵为G的邻接矩阵。设图的顶点集为，点的度为:，则G的度矩阵定义为。假设将每个数据样本看作为图中的顶点V，根据样本之间的相似度将顶点间的边赋权值，就得到一个带权无向图，那么在图G中我们可将聚类问题转变为在图G上的图划分问题。既然图像可以映射为图，如何尽可能保全图像的信息同时降低图像处理过程的计算复杂度，是图像处理和模式识别领域的一个挑战性话题。下面讨论图的几种矩阵表示方法。不同的图可以映射成不同的矩阵，同一个图也可以用不同的矩阵来描述，对于同一个问题不同的矩阵表示可以达到不同的效果。1）二值邻接矩阵：图，其中是顶点集，是边集，i,j表示矩阵的行和列，则对应的二值邻接矩阵可以表示为： (3.1)2）加权邻接矩阵：加权邻接矩阵又称为相似度矩阵。对于图，可以用： (3.2)其中来表示图中两点之间的距离，称为超参数，也称之为带宽参数。它的取值对于谱聚类算法的性能有很大的影响。在谱聚类算法中，最常用的相似度函数是高斯核函数，也就是(3.2)式。实际上，任何对称的并且是距离函数的一个非递减的函数都可以作为一个相似度函数。使用高斯核函数的另外一个好处就是，用该相似度函数计算得到的相似度矩阵是一个正定的相似度矩阵。我们从核的观点来看待这个函数，即存在一个从低维到高维的映射，这样就有可能将一个不可分的数据集经过映射之后就变得线性可分了39 。3）拉普拉斯(Laplace）矩阵：所述，广泛使用的拉普拉斯矩阵的定义有如下三种形式：(1)非归一化的拉普拉斯矩阵： L=D-A (3.3)(2)对称的归一化拉普拉斯矩阵： (3.4) (3)随机游走的归一化拉普拉斯矩阵： L=D-A (3.5)其中，矩阵D是一个对角阵，并且对角线上的元素满足，矩阵I表示的是单位阵。有关拉普拉斯矩阵，数学上有很多应用的例子。有关对称的拉普拉斯矩阵和随机游走的拉普拉斯矩阵之间的特征向量和特征值是密切联系的。具体地说，如果是对应于随机游走的拉普拉斯矩阵的特征值和特征向量，那么就是对应于对称的拉普拉斯矩阵的特征值和特征向量10。上述邻接矩阵和拉普拉斯矩阵都具有沿对角线对称的特性，对称性为矩阵的进一步分解提供了可能。加权邻接矩阵中各点间距离通过他们之间的权值来表示；拉普拉斯矩阵对角线表示度，二值化后得到的拉式矩阵后各个行和、列和均为零，能够更方便的表示顶点间关系，拉式矩阵的全部特征值具有非负性。3.1.2 谱图理论谱图理论历史悠久，它是利用矩阵理论和线性代数理论来对图的邻接矩阵进行分析，从而找到图的某些性质。上世纪70年代，Fiedler以图的拉普拉斯矩阵为基础提出了谱图理论。带权无向图,邻接矩阵表示为，其中表示连接顶点和的权值。可以得到该图的拉普拉斯矩阵表示为： (3.6)其中，D为对角矩阵： (3.7)拉普拉斯矩阵是半正定的对称矩阵，因此全部的特征值都是非负的实数，即：0123n (3.8)如果G是联通的，是G的连接代数值，其对应的特征向量为Fiedler向量，即拉普拉斯矩阵的第二小特征向量。目前很多谱聚类算法都是通过将图划分问题转化为求解Laplace矩阵的第二小特征向量问题，进而进行最终聚类划分的。这里的第二小特征向量指的是Laplace矩阵的第二最小特征值所对应的特征向量，它代表了最优图划分的一个解，我们把这一特征向量称为Fiedler向量。与特征向量(不一定是Fiedler向量)对应的特征值称为谱。3.1.3 图划分准则谱图理论与谱聚类算法有着密切关系。大多数聚类算法的准则是：相同类别的数据点具有的相似度较高，而不同类别的数据点间相似度较小。图中顶点V表示数据集的每个样本点，V的相邻各个边的权重值为W表示为样本点间的相似度，我们能够得到关于样本相似度的带权无向图。我们可以将聚类问题转化为在图G上的图划分问题。图论理论的最优划分准则与聚类算法的准则类似，是针对划分结束后得到的两个子图，使子图之间的相似度尽可能小，而子图内部相似度尽可能大。聚类效果与图划分准则息息相关，通常的划分准则有Minimum cut,Average cut,Normalized cut,Min-max cut,Ratio cut,MNcut等,下文对这几种准则分别给予介绍：1）最小割集准则12(Minimum cut)谱图理论中，按照上述准则，将图G划分为A和B两个子图，令它们的关系满足,其目标函数为：cut(A,B)=W(u,v) (3.9)Wu和Leahy提出可以采用最小化(3.7)式子中的值来划分图G，该准则被称为最小割集准则。使用这个准则对部分图像进行分割，可以产生较好的效果，同时我们需要指出的是，该准则容易产生偏向小区域的分割，Shi和Malik提出来的的规范割集准则及Hagen和Kaling提出的比例割集准则基本上都可以避免这种情况的发生。2）比例割集准则13(Ratio cut)Hagen和Kahng共同提出比例割集目标函数(Rcut)为：Rcut=cut(A,B)min(A,B) (3.10)其中，,分别表示了子图A,B中所包含顶点的个数，使该函数最小化能够使类别间的相似性最小，然而相伴的就是可能会产生过分割问题。但采用该准则运行的速度较慢，效率不高，易产生倾斜划分。3）规范割集准则14(Normalized cut)Shi和Malik根据谱图理论在2000年提出并建立了2-way划分的规范割的目标函数 (Ncut): (3.11) 式中:assoc=uA,tVW(u,t) (3.12)规范割集准则即为最小化Ncut函数，该准则的目标函数既可以衡量同一类别内的样本之间相似程度，又能够衡量类间样本的相异程度。也就是，类内样本间的相似度大，类间样本间相似度小。规范切判据引入容量的概念来规范化类间相关，从而考虑了相对于类内连接强度的类间连接。4）平均割集准则 (Average cut)平均割目标函数被表示为： (3.13)可以看出的是Avcut和Ncut函数都表示在无向图G中，边界损失与区域分割相关性的比值之和，因此，最小化Avcut和Ncut准则的目标函数都能产生比较准确的划分，但是两者的共同缺点都是倾向于欠分割并且容易分割出尽包含几个顶点的较小子图。Luxburg11通过实验证明了规范化割集准则和平均割集准则用于分割同一图像，规范化割集准则产生的划分效果更好。5）最大最小割集准则15(Min-max cut)最大最小割集准则要求最小化cut(A,B)的同时，最大化assoc(A,A)与assoc(B,B)。目标函数为： Mcut=cut(A,B)assoc(A,A)+cut(A,B)assoc(B,B) (3.14)最大最小割集准则通过最小化式子(3.12)实现。最小化该函数可以避免分割出仅包含几个顶点的较小子图，因此它比较倾向于产生平衡割集，但是该准则的实现速度较慢。Mcut与Ncut同样可以满足不同类别间样本的相似度小，而且同类内样本的相似度大，但当类间重叠较大时，Ncut效果不如Mcut效果好。6）多路规范割集准则16（Multiway Normalized cut）上面的五种都是将图划分为两个子图的划分函数,但多路规范割集准则是函数的目的是将图G同时划分为多个子图。尽管多路规范割集准则在实际应用中合理，但优化问题通常难以解决17。以上简单介绍现今比较常用的几类划分准则，分别就其目标函数及其存在的优缺点予以简要分析。总之，上述的规范割集准则的各自特点都伴着优点缺点，然而规范割集准则(Normalized cut)以及它应用到多路问题中的多路规范割集准则（Multiway Normalized cut）在现今的研究应用中使用最为广泛。故本文算法中也采用规范割集准则作为划分准则。3.1.4 相似度矩阵、拉普拉斯矩阵鉴于图划分问题的本质，是求图划分准则的最优解，这其实是个NP难问题，我们考虑求该问题相应的连续放松形式，这样可将原问题转变成求解相似矩阵或者拉普拉斯矩阵的谱分解，得到的特征向量即是谱向量，并以此为基础来聚类不同的数据点。因此这类方法被称为谱聚类算法，同时可以将谱聚类看作是对图划分准则的逼近20。3.2 谱聚类算法3.2.1 谱聚类算法标准谱聚类算法处理的是两类问题，多类划分问题可以通过递归调用两类划分方法来实现。谱聚类算法的基础是谱图理论，也就是图划分准则的逼近。根据不同的划分准则函数以及谱映射方法，该算法发展了很多不同的具体实现方法，但其都可以归纳为下述基本框架1819 ：输入：数据集X，聚类数k。步骤一：基于某种相似性度量，构造数据集的相似度矩阵。步骤二：计算拉普拉斯（Laplace）矩阵，矩阵是一个对角阵，并且对角线上的元素满足，是相似度矩阵。步骤三：计算矩阵L的特征值，并找到前k个最小特征值对应的最小特征向量。步骤四：以L的前k个特征向量为列向量组成矩阵U。步骤五：以矩阵U的每一行，作为数据点用K-Means算法将n个k维数据点聚到k个类中。输出：k个聚类M1,M2,Mk。以上步骤只是谱聚类算法的一个通用框架，在算法编码仿真过程中，不同算法的不同之处可能在于构造的相似度矩阵的差异、使用的特征向量的差异、从特征向量获得最终聚类的方法的差异或从连续变量放松到离散变量的方法，即谱松弛方法差异等方面。一般情况下，我们根据能够同时将图G划分成的子图数目的多少，将图划分准则分为二分型和多分型两大类，再根据所用的划分准则的不同，将谱聚类算法分为迭代谱和多路谱两大类，分别就两类中经典的算法予以简单介绍如下：标准的谱聚类方法处理的是两类问题，可以递归地调用两路划分方法来实现多类聚类问题，然而该方法计算效率低、不稳定，且没有利用包含有用划分信息的其它特征向量。一种求解多类聚类问题的思路是构造多路图划分判据。下面介绍三种目前流行的谱聚类算法，分别是SM算法12， NJW算法13和MS算法。其中，SM算法能够自发式的找到聚类数K.。为了进行相对公平的对比，我们假设进行对比的算法聚类数目K都事先给定。我们依然采用上节中对谱图理论相关公式的定义，聚类是将图G的中的顶点V划分成互不相交的非空子集。图论中，聚类表示对图G的一种多路划分(multiway cut)1.SM算法SM算法首先由Shi和Malik提出，它是一种自发式算法，目标是最小化由他们(Shi和Malik)提出的规范切准则(Normalized Cut, NCut)，如式3.9所示，设有集合I分为两个簇和，其中，在I所有可能的两种分块上最小化。这个问题就是NP难题，在某种特殊条件下谱算法能够找到最优解。SM算法类似于递归二叉算法，具体实现步骤。2.NJW算法13NJW算法一个比较流行的谱聚类算法，它是Ng等人在2002年提出的一种简单而有效的多类实现方法。他们选取了Laplacian矩阵的前K个最大的特征值所对应的特征向量，使它们在空间中构成与原先数据一一对应的表述，然后在该空间中