谱聚类算法毕业设计.docx

沈阳理工大学学士学位论文
摘 要
谱聚类作为一类新兴的、有效的聚类方法得到广泛的关注，并已成功的应用于图像分割。本文研究基于谱聚类的图像分割技术，并成功的应用到图像分割中。本文主要工作如下:
谱聚类算法是利用图像的相似性矩阵进行图像分割，如何构造一个对图像信息表达更充分的相似性矩阵，对算法性能有很大影响。本文应用Nystrom谱聚类算法进行图像分割技术的研究，而且还具有良好的方向分析能力，它能反映出图像在不同分辨率上沿多个方向的变化，能更好地描述图像的几何结构。
该方法为的是在聚类的时候取得较好且稳定的性能，然而KHM仅在对低维数样本聚类时较KM算法要好。为了缓解谱聚类对初始化敏感的问题，本文采用了基于优化策略的K均值算法，实现了基于Nystrom谱聚类的图像分割方法。通过在Nystrom谱聚类算法仿真实验表明:本文的方法无论在细纹理、粗纹理、非均匀纹理和混合纹理上，其视觉效果和评价指标上都要优于的方法。
关键词:图像分割;谱聚类；Nystrom谱聚类算法；K-Means聚类算法

Abstract
Spectral 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 绪 论 1
1.1 数字图象处理技术 1
1.1.1 简介 1
1.1.2 图像处理的主要目的 1
1.1.3常用方法 1
1.2 图像分割技术 1
1.3 MATLAB编程软件的介绍 2
1.3.1简介 2
1.4 谱聚类的简述 2
1.4.1 简介 2
1.4.2 图划分准则 2
1.5 课题研究的目的及本文的主要内容 3
2 图像分割技术与边缘检测 4
2.1 图像分割定义和方法分类 4
2.1.1 图像分割的定义 4
2.1.2 图像分割算法 5
2.1.3 灰度阈值分割 5
2.1.4 阈值法 6
2.2 边缘检测算子 6
2.2.1 基于边缘检测的分割 6
2.2.2 普通梯度算子 7
2.3 区域生长 8
2.3.1 区域生长的主要步骤 9
2.4 本章小结 9
3 谱聚类算法分析与研究 10
3.1 基本理论 10
3.1.1 图和矩阵的表示 10
3.1.2 谱图理论 13
3.1.3 图划分准则 13
3.1.4 相似度矩阵、拉普拉斯矩阵 15
3.2 谱聚类算法 16
3.2.1 谱聚类算法 16
3.2.2 谱聚类算法与K_Means算法的比较 18
3.3 谱聚类算法存在的问题以及研究进展 20
3.4 本章小结 21
4 基于Nystrom谱聚类图像分割算法研究 22
4.1 Nystrom谱聚类算法 22
4.1.1 Nystrom扩展方法 22
4.1.2 Nystrom 扩展谱聚类算法 23
4.1.3 Nystrom谱聚类图像分割算法 24
4.2 程序流程图 26
4.3 仿真与分析 27
4.3.1结果 27
4.3.2分析 28
4.5 本章小结 28
结 论 29
致 谢 30
参考文献 31
附录A 英文原文 32
附录B 中文翻译 40
附录C 计算程序 45

IV

1 绪 论
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，i≠j，有 （2.2）
③ 对i=1，2，…，n，有P（Ri）=TRUE （2.3）
④ 对i≠j，有 P（Ri∪Rj）=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,y<T255 T<&fx,y<255 （2.5）
其中，f(x,y)是原始图像的像素值，g(x,y)是处理后的黑白图像的像素值。灰度阈值分割法是一种非线性的运算。如果图像像素值大于我们所设置的阈值，则将这个像素灰度值设置为255，反之将其灰度值设置为0
当原始图像的灰度直方图的双峰特性不明显时，也就是图像中的前景和背景之间的灰度值相差较小时，根据图像的直方图就不易选择一个合适的阈值。所以，这时我们就要选择其他方法来确定阈值，常用方法有：
(1)最小误差阈值法
(2)最大方差阈值法
(3)最佳阈值法
(4)差别分析法
2.1.4 阈值法
阈值法是一种并行的区域分割技术，主要利用图像的灰度信息，通常的做法是根据图像灰度直方图的谷底简单地确定一个或几个阈值，将图像的灰度直方图分成几类，认为图像中灰度值在同一灰度类的像素属于同一类物体。
根据使用的图像的整体信息还是局部信息，可分为上下文相关(contextual)方法和上下文无关(non-contextual)方法;根据对全图使用同意与之还是对不同区域使用不同阈值，可以分为全局阈值(global thresholding)方法和局部阈值(localthresholding，也叫自适应阈值方法adaptive thresholding)方法;另外还可以分为单阈值(bilever thresholding)方法和多阈值(multithresholding)方法。阈值法分割的结果依赖于阈值的选取，确定闭值是阈值法分割的关键。阈值分割实质上就是按照某个准则求出最佳阈值的过程。常用的全局阈值选取方法有利用图像灰度直方图的峰谷法、最小误差法、最大类间方差法、最大嫡自动阈值法以及其他一些方法。
2.2 边缘检测算子
函数的导数反映图像灰度变化的显著程度，一阶导数的局部极大值和二阶导数的过零点都是图像灰度变化极大的地方。因此可以将导数值作为相应点的边界强度，通过设置门限的方法，提取边界点集。
2.2.1 基于边缘检测的分割
这类方法主要基于图像灰度级的不连续性，基本思想是通过检测图像中不同均匀区域之间的边界来实现对图像的分割，其难点在于边缘检测时抗噪性和检测精度的矛盾。若提高检测精度，则噪声产生的伪边缘会导致不合理的轮廓;若提高抗噪性，则会产生轮廓漏检和位置偏差。为此，人们提出各种多尺度边缘检测方法，根据实际问题设计多尺度边缘信息的结合方案，以较好地兼顾抗噪性和检测精度，但仍不能从根本上克服此矛盾。所以只有当图象质量较好时，可以采用基于边缘的图象分割方法。
对于图像，图像本身存在乘性相干斑噪声，使得边缘像素灰度值的起伏较大，难以精确定位边缘像素位置，所以减少虚警边缘和提高边缘定位精度是边缘检测的难点。提取了基于增强边缘的图像分割方法;文献提出边缘检测与区域融合的图像分割。
2.2.2 普通梯度算子
假设f(x,y)是一个连续函数，那么在点（x,y）出的梯度定义为：

∇fx,y=∂f∂x∂f∂yT=∇xf2+∇yf2T （2.6）
梯度是一个矢量，它的 幅值和相位分别为：
幅值 ∇f=∇xf2+∇yf212 （2.7）
相位 ∇f=fx,y-f(x+1,y)+fx,y-f(x,y+1) （2.8）
对于普通梯度算子中将幅值用两个分量的的绝对值之和来表示，即：
∇f=(fx,y-f(x+1,y))2+(fx,y-f(x,y+1))212 （2.9）
（1）Roberts 算子
Roberts算子是一种利用局部差分算子寻找边缘的算子，对具有陡峭的低噪声的图像效果好。卷积核分别为：
（2.10）

采用范数1衡量梯度的幅度：
（2.11）
（2）Sobel 算子
Sobel算子对灰度渐变和噪声较多的图像处理得较好。卷积核分别为

（2.12）

采用∞范数衡量梯度的幅度：
（2.13）
（3）Prewitt 算子
Prewitt算子对灰度渐变和噪声较多的图像处理得较好。卷积核分别为：

（2.14）

采用∞范数衡量梯度的幅度：
（2.15）
（4）拉普拉斯算子
拉普拉斯算子是一个二阶微分算子，定义为梯度∇f的散度（∇∙f）,即：
∆f=∇2f=∇∙∇f=∂2f∂x2∂2f∂f2 （2.16）
（5）Canny 算子
Canny 算子的梯度是用高斯滤波器的导数计算的。该方法不容易受噪声的干扰，能够检测到弱边缘，但是检测边缘的连续性不好。
算法步骤：
a.用高斯滤波器平滑图像；
b.计算滤波后图像梯度的幅值和方向；
c.对梯度幅值应用非极大值抑制，其过程为找出图像梯度中的局部极大值点，把其他非局部极大值点置零以得到细化的边缘；
用双阈值算法检测和连接边缘，使用两个阈值T1和T2（T1>T2），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)
拉普拉斯矩阵是半正定的对称矩阵，因此全部的特征值都是非负的实数，即：
0≤λ1≤λ2≤λ3∙∙∙≤λn (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=u∈A,t∈VW(u,t) (3.12)
规范割集准则即为最小化Ncut函数，该准则的目标函数既可以衡量同一类别内的样本之间相似程度，又能够衡量类间样本的相异程度。也就是，类内样本间的相似度大，类间样本间相似度小。规范切判据引入容量的概念来规范化类间相关，从而考虑了相对于类内连接强度的类间连接。
4）平均割集准则 (Average cut)
平均割目标函数被表示为：
(3.13)
可以看出的是Avcut和Ncut函数都表示在无向图G中，边界损失与区域分割相关性的比值之和，因此，最小化Avcut和Ncut准则的目标函数都能产生比较准确的划分，但是两者的共同缺点都是倾向于欠分割并且容易分割出尽包含几个顶点的较小子图。Luxburg[11]通过实验证明了规范化割集准则和平均割集准则用于分割同一图像，规范化割集准则产生的划分效果更好。
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 谱聚类算法
标准谱聚类算法处理的是两类问题，多类划分问题可以通过递归调用两类划分方法来实现。
谱聚类算法的基础是谱图理论，也就是图划分准则的逼近。根据不同的划分准则函数以及谱映射方法，该算法发展了很多不同的具体实现方法，但其都可以归纳为下述基本框架[18][19] ：
输入：数据集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算法[13]
NJW算法一个比较流行的谱聚类算法，它是Ng等人在2002年提出的一种简单而有效的多类实现方法。他们选取了Laplacian矩阵的前K个最大的特征值所对应的特征向量，使它们在空间中构成与原先数据一一对应的表述，然后在该空间中