（模式识别与智能系统专业论文）基于规范切和分水岭的聚类算法研究.pdf

摘要 摘要 聚类分析是机器学习的经典问题之一，它通过分析数据特征来获取数据之间 的相似度，并根据相似度对数据进行聚类操作，使得类内的对象满足相似度最大， 类间的对象满足相似度最小，从而通过聚类结果来发现聚类对象的内在关系。针 对聚类分析算法及其应用问题，本文主要做了三方面的工作。 聚类结果的好坏取决于聚类准则函数是否能够反应类内数据点的相似程度和 类间数据点的相异程度。为了进一步增大基于规范切的谱聚类算法中类内数据点 的相似性和类间数据点的相异性，本文提出了一种基于相似性与相异性的谱聚类 算法。该方法巧妙设计了新的聚类准则函数，在采用规范切的经典谱聚类算法的 基础之上，通过引入距离矩阵来进一步体现数据点间的相异性，使聚类结果得到 改善。 经典的分层凝聚聚类算法在非凸球形分布数据集上容易陷入局部最优。针对 这一不足，本文提出一种基于规范切的分层凝聚聚类算法。该方法直接利用规范 切作为判断各个类别是否合并的准则，从而巧妙克服经典算法存在的不足，使得 分层凝聚聚类算法在非凸形分布或具有一定流形分布的数据集上能够得到更好的 聚类结果。 通过研究各种聚类算法在医学图像处理方面的应用，发现现有的二维医学图 像分割技术存在不能充分利用图像的第三维信息的问题，而三维图像分割技术中 存在计算复杂度较大的问题。为了解决这些问题，本文提出一种基于三维区域分 水岭的腹部主要血管提取方法。该方法充分利用了图像的三维信息，并且在一定 程度上降低了计算复杂度，能够从复杂的腹部环境中得到较完整的腹部主要血管 系统。 本论文得到国家自然科学基金( n o 6 0 6 0 2 0 6 4 和n o 6 0 9 7 0 0 6 7 ) 的资助。 关键词：聚类谱聚类分层聚类分水岭医学图像分割 a b s t r a c t i i i a b s t r a c t c l u s t e r i n ga n a l y s i si sac l a s s i c a lp r o b l e mi nm a c h i n el e a r n i n g t h ei n n e rr e l a t i o n b e t w e e nt h eo b j e c t sc a nb es h o w e db yt h er e s u l t so ft h ec l u s t e r i n gm e t h o d sb a s e do nt h e a n a l y s i so ff e a t u r e so ft h eo b j e c t s t h eg o a lo fc l u s t e r i n ga n a l y s i s i st o g e tv a r i o u s c l u s t e r s o b j e c t sb e l o n g i n gt o t h es a m ec l u s t e rh a v et h em a x i m u ms i m i l a r i t y , a n d o b j e c t sb e l o n g i n gt od i f f e r e n tc l u s t e rh a v et h em j n i n l u l ns i m i l a r i t y b ys t u d y i n go n c l u s t e r i n ga l g o r i t h m s ，w em a i n l yp r o p o s et h r e ec l u s t e r i n gm e t h o d s ，i n c l u d i n gs p e c t r a l c l u s t e r i n gb a s e do ns i m i l a r i t ya n dd i s s i m i l a r i t y , h i e r a r c h i c a lc l u s t e r i n g b a s e do n n o r m a l i z e dc u t ( h c n ) a n dt h r e ed i m e n s i o n a lr e g i o n a lw a t e r s h e da l g o r i t h m ( t d r w a ) as p e c t r a lc l u s t e r i n gb a s e do ns i m i l a r i t ya n dd i s s i m i l a r i t ym e t h o di sp r o p o s e dt o f u r t h e rr e f l e c tt h es i m i l a r i t yb e t w e e nt h es a m p l e si ne v e r yc l u s t e r sa n dt h ed i s s i m i l a r i t y b e t w e e nd i f f e r e n tc l u s t e r s t h es p e c t r a lc l u s t e r i n gb a s e do ns i m i l a r i t ya n dd i s s i m i l a r i t y m e t h o da d o p t san e wc l u s t e r i n gc r i t e r i o nf u n c t i o ni nw h i c had i s t a n c em a t r i xb e t w e e n s a m p l e si s i n t r o d u c e di n t ot h e s p e c t r a lc l u s t e r i n g b a s e do nt h en o r m a l i z e dc u t e x p e r i m a n t ss h o wt h a tt h ep r o p o s e da l g o r i t h me x h i b i t sah i g h - p e r f o r m a n c e c l a s s i c a ld i s t a n c e b a s e dh i e r a r c h i c a lc l u s t e r i n gm e t h o d sc a ne a s i l yf a l li n t oal o c a l o p t i m u ms o l u t i o ni nn o n c o n v e xd a t a s e t s i n o r d e rt os o l v et h i sp r o b l e m ，an e w h i e r a r c h i c a lm e r g ec l u s t e r i n ga l g o r i t h mb a s e do nt h en o r m a l i z e dc u ti sp r o p o s e d i no u r a l g o r i t h m ，c l u s t e r sw h i c hh a v et h el a r g e s tn o r m a l i z e dc u ts h o u l db em e r g e df i r s t l y e x p e r i m e n t a lr e s u l t ss h o wt h a to u ra l g o r i t h mi sm o r ee f f i c i e n tt h a nc l a s s i c a lo n e so nt h e n o n - c o n v e xd i s t r i b u t e dd a t a s e t s i np r a c t i c e ，m a n ye x s i t i n gt e c h n i q u e so fm e d i c a li m a g ep r o c e s s i n gu s i n gc l u s t e r i n g m e t h o d sc a nn o tu s et h ei m a g ei n f o r m a t i o nc o m p l e t e l y ，a n dh a v el a r g ec o m p u a t i o n a l c o m p l e x i t y i no r d e rt os o l v et h e s ep r o b l e m s ，at d r w a i sp r e s e n t e df o re x t r a c t i n gt h e a b d o m i n a lb l o o dv e s s e l si n3d i m e n s i o n a lc ti m a g e s t d r w au s e st h e3d i m e n s i o n a l w a t e r s h e da n dt h er e g i o ng r o w i n gm e t h o d st op r o c e s s3d i m e n s i o n a lc ti m a g e sa n d e x t r a c ta b d o m i n a lb l o o dv e s s e l s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt d r w ac o u l d r e d u c et h er u n t i m ea n dg e tab e u e rr e s u l t t h i sw o r kw a ss u p p o r t e di np a r tb yt h en a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no f c h i n a ( n o 6 0 6 0 2 0 6 4a n dn o 6 0 9 7 0 0 6 7 ) k e y w o r d s ：c l u s t e r i n gs p e c t r a lc l u s t e r i n g h i e r a r c h i c a lc l u s t e r i n g w a t e r s h e dm e d i c a li m a g es e g m e n t a t i o n 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：遗器奎竭 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学：学校有权保留 送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容， 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 耳 一=_1_， 一翠钫一聋 名 名 签 签 人 师 本 导 第一章绪论 第一章绪论 1 1 聚类分析的研究背景及发展 1 1 1 聚类分析的研究背景 在人工智能中，机器学习是一个非常活跃的领域【l 】，随着计算机的发展、信息 化程度的不断加强，人类面临越来越繁重的数据处理任务，而机器学习就是通过 让计算机模拟人类学习的过程，从而帮助人类完成一定的任务。在某些人类已经 涉足研究的领域中，人们具有相当多的经验，对机器的学习可以提供一些指导性 的信息，这称之为有监督的学习。而对于那些对于人类来讲还是未知的学习领域， 人们却无法提供任何信息以帮助计算机的学习，计算机只能根据数据本身的属性 特征对其进行分析研究，这称之为无监督的学习。聚类方法就是一种重要的无监 督学习方法，它是将物理的或抽象的对象集合划分为由若干相似对象组成的不同 的类的过程 2 1 。 聚类分析是机器学习的经典问题之一，它虽然起源于分类学，但是却与分类 存在很大的不同，最明显的不同就是聚类所要求划分的类是未知的，即聚类分析 不需要先验知识或先验假设，它通过采用一定的数据特征分析数据之间的相似程 度，并根据相似程度对数据进行聚类操作，使得类内的对象满足相似度最大，类 间的对象满足相似度最小，从而通过聚类的结果发现聚类对象的内在特征。 1 1 2 聚类分析的发展 由于聚类分析技术可以对未知数据进行学习，从而得到数据的某些内在信息， 因此聚类分析已经成为机器学习中最热门的研究领域之一。各种聚类算法及其改 进方法被相继提出。1 9 6 7 年，m c q u e e n 等在其发表的文章中提出了经典的k - m e a n s 聚类算法f 3 1 ，这在很大程度上推进了聚类分析领域的研究，后来的d i d a y 和s y m o n 在深入研究k m e a n s 算法之后，提出了在k m e a n s 算法聚类的过程中动态地选择聚 类准则的方法【4 5 j ，使k m e a n s 聚类效果得到了很大程度的改进。19 6 6 年，z a d e h ， l a 等提出了模糊聚类的思想【6 】，突破了对数据点的硬化分，使聚类方式更加灵活。 w 矾、m u r t a g h 等人相继提出了最小方差的聚类分析算法r 7 ，8 】，为聚类算法提供了新 的血液。k i n g 在1 9 6 7 年提出了分层聚类中全连通的聚类思想【9 】，s n e a t h 和s o k a l 贝j j 在 自己的研究中对其进行了改进，在1 9 7 3 年提出了分层聚类思想中单连通的聚类思 想【1 0 1 。再后来的基于图论的聚类算法【1 l 】、最近邻聚类算法【1 2 1 、基于神经网络【1 3 1 和 基于进化算法的聚类思想 1 4 , 1 5 】将聚类分析与各个研究领域结合，大大扩展到了聚 2 基于规范切和分水岭的聚类算法研究 类分析所涉及的领域，促进了聚类研究的进步。所有这些聚类算法都是聚类分析 的经典算法，为聚类分析奠定了牢固的基础。 j a i n 和m u r t y 等人对聚类思想及各种聚类方法做了详细分析【1 6 1 ，他们指出聚类 分析是以计算机的应用为背景，对数据源进行探索及理解，以便能够进一步的应 用这些数据。同时他们分析了聚类的关键技术和主要步骤，并在参考j a i n 和d u b e s 的文章【1 7 】的基础上对各种现有的聚类算法做了详细的分类及说明。大部分聚类算 法在聚类分析的过程中采用了数据点的所有特征信息，而a n d e r b e r g 等人提出了连 续地采用单一特征划分数据点的方法【1 8 j ，突破了传统的思想。后来的s a l t o n 等人还 对该方法进行了改进，使其能够在具有很大特征维数的数据集上得到广泛的应用 1 9 1 o 随着聚类分析技术的不断发展，m a a r e k 和s h a u l 2 0 l 、c h e k u r i 2 1 】等将聚类算法 用在大量的非结构化数据的挖掘方面；d c o m a n i c i u 和r o d u d a 等人将聚类算法用 在模式识别方面 2 2 1 。聚类分析在机器学习、数据挖掘、图像处理、生物医学和模 式识别等领域发挥着越来越重要的应用 2 2 。2 7 】。 虽然聚类分析技术已经在各个领域发挥着很重要的作用，但是很多的聚类算 法还存在着不足，聚类效果仍然达不到人们所期望的要求，所以我们仍需要对聚 类分析技术做更多、更深入的学习和研究。 1 2 经典的聚类分析方法回顾 目前存在的聚类方法主要包括以下几类：划分法、层次法、基于密度的方法、 基于模型的方法和基于网络的方法等【2 8 1 。 这里以给定的包含刀个数据点的数据集，将其划分为k 个类别的聚类问题为 例，对以上各种方法进行对比说明。划分法是先创建一个初始类别，然后通过一 定的策略反复迭代改变类别，使得每一次改变后的类别分配情况都比上一次的更 优；层次法则是将数据集中的数据点按照逐层分解的思想来聚成需要的类别：基 于密度的方法将邻近的密度超过某个阈值的数据点进行聚类，从而达到将数据集 划分为k 个类别的目的；基于网络的方法则是用数据集中的n 个数据点形成一个网 络结果，再以此网络结果为基础，对数据集进行聚类；基于模型的方法为每一个 类别假定一个模型，然后通过优化参数，寻找数据最佳地拟合该模型来达到最佳 的聚类效果。由于划分的思想不同，这些方法都存在各自的特点与优点，已经在 各个领域当中得到了广泛的应用。 经典的聚类方法不胜枚举，我们在这里重点介绍与本研究相关的k m e a n s 聚类 方法、分层聚类方法、谱聚类方法和基于分水岭变换的聚类方法。以下对其思想 进行简要介绍。 第一章绪论 3 1 2 1k m e a n s 聚类方法 k - m e a n s 聚类是一种经典的聚类算法，早在1 9 6 7 年，m c q u e e n 等就在自己的文 章中对其进行了详细的说吲3 1 。k m e a n s 聚类属于划分法的一种2 9 1 ，该方法先从数 据集中随机选择k 个数据点作为初始聚类中心，再根据各剩余数据点与k 个聚类中 心之间的距离，把其分配到最近的一个类别当中。然后重新计算每个类别的平均 值( 即类别中心) ，重复上述过程，直到准则函数收敛。 通常我们采用平方误差作为k m e a n s 算法的准则函数。作为经典的聚类算法， k m e a n s 聚类在某些数据的分布上能得到非常理想的聚类效果，但是它也存在对初 始化及噪声敏感，只适用于凸球形数据分布情况的缺点。该方法在非凸球形分布 的数据集上容易陷入局部最优，而得不到好的聚类效果。很多研究者也对其存在 的缺点进行了改进研究【4 ，5 1 ，但这里所述的不足属于k m e a n s 聚类方法自身存在的问 题，改进相当困难。 1 2 2 谱聚类方法 谱聚类是一种典型的基于图的聚类方法，是近几年来机器学习的一个新的研 究热点【3 0 】。早在二十世纪6 0 、7 0 年代，就有很多研究者从事基于图的聚类方法研 究【l l 】，直n - 十世纪9 0 年代以后，基于谱图理论的谱聚类算法才得到广泛的发展 和使用【3 m 7 1 。 谱聚类以图论中的谱图理论为基础，其主要思想是将数据集聚类的过程转化 为与数据集对应图的最优划分的过程，通过将各个数据点及数据点之间的相似性 程度映射到图上，然后通过采用图划分的方法达到将数据点分为不同类别的目的。 该方法中将数据集中的各个数据点看成是图中的顶点，将各个数据点之间的相似 性度量作为各个顶点之间边的权重。 这种新兴的谱聚类算法可以在任意形状的数据分布上收敛于全局最优解，得 到较好的聚类效果。它的应用也由最初的用于计算机视觉【3 6 1 、v l s i 设计吲等领域， 扩展到了机器学习当中【3 6 】，并迅速地发展为机器学习领域的一个热点研究对象。 1 2 3 分层聚类方法 s t e p h e nc j o h n s o n 等人在1 9 6 7 年发表的文章中提出了分层聚类的策略 3 9 1 。分 层聚类就是对数据点数据集进行逐层的分解，直到达到满足一定条件为止( l k 如达 到聚类数为k 时停止) 。根据采用的分解策略的不同，分层聚类包括分层凝聚和分 层分裂两种方法【删，具体的聚类算法可参考文献【4 1 4 3 1 。 分层凝聚聚类采用的是自底向上的策略【4 4 , 4 5 】，它首先将每个数据点看成是一 个类别，这样包含玎个数据点的数据集就有n 个初始类别，再根据某种度量方法( 如 基于规范切和分水岭的聚类算法研究 类中心点的距离等) 将这些类别合并为较大的类别，如此逐层合并，直到所有的对 象都在一个类别当中，或是满足某个终止条件时为止。大多数的分层聚类算法都 采用凝聚的策略，只是合并度量准则的选择有所不同。 分层分裂的聚类刚好与分层凝聚相反，它采用自上向下的策略t 4 5 , 4 6 ，首先将 数据集中的所有的数据点看成是一个类别，然后根据某种度量方法逐步细分，将 原类别划分为较小的类别，直到每个数据点都属于一个单独的类别，或达到某个 终止条件( 希望达到的类别数) 。 不管从理解上还是实现上来说，分层聚类都是一种较简单的聚类算法，但是 由于分层聚类中每一次聚类都是在前面处理的基础上进行，不能进行回溯处理， 因此各个类别之间不能交换对象【4 0 】。也就是说，如果数据点被分配到某个类别， 就不能够再做调整，这样就会造成错误的不断积累。故在决定合并或分裂之前需 要检查和估算大量的数据点和类别。 1 2 4 基于分水岭变换的聚类方法 分水岭方法是经典的用于图像分割的形态学方法1 4 ”羽，用于灰度级形态学方 法的分水岭变化最先由d i g a b e l 和l a n n l e j o u l 等提出【4 9 5 0 】，b e c h e r 和l a n t u e j o u l 等人在 此基础上对其进行了更多的改进【5 ，这也奠定了分水岭方法在图像分割领域的广 泛应用1 5 2 , 5 3 】。 h d i g a b e l 和c l a n t u e j o u l 在1 9 7 8 年首次将分水岭这一概念引入数字图像处理 领域 4 9 1 用其进行简单的二值图像处理。其基本思想是把图像看作测地学上的拓扑 地貌，图像中每一点像素的灰度值表示该点的海拔高度，每一个局部极小值及其 影响区域称为集水盆，而集水盆的边界则形成分水岭。分水岭的概念和形成可以 通过模拟浸入过程来说明f 7 1 。在每一个局部极小值表面，刺穿一个小孔，然后把 整个模型慢慢浸入水中，随着浸入的加深，每一个局部极小值的影响域慢慢向外 扩展，在两个集水盆汇合处构筑大坝，即形成分水岭。最终的分水岭即为图像分 割的边缘点，边缘点包围的内部区域即为某一个类别区域。独特的思想使得分水 岭算法对微弱边缘具有良好的响应，图像中的噪声、物体表面细微的灰度变化， 都会产生过度分割的现象，所以说分水岭算法是得到封闭连续边缘的保证的，这 也为分析图像的区域特征提供了可能。但也正是因为该特点，使得分水岭算法容 易产生过分割现象，使得分割结果中常出现过多的伪边界。所以根据应用的不同， 经常我们需要抑制其过分割现象。 b e u c h e r 和l a n t u e j o u l 等人第一次将分水岭算法用于分割问题侈5 1 ，尝试用分水岭 的思想完成泡沫和显微照片图像的分割任务，但是该分割过程中出现了严重的过 分割现象，将图像分成了太多小的区域。后来m e y e r 和b e u c h e r 对分水岭的过分割 第一章绪论 5 现象进行了改进【5 6 】，他们在分割图像的过程中采用了半监督学习的思想，对图像中 的感兴趣区域( 目标等) 和非感兴趣区域( 背景灯) 进行了标记，再利用标记的数据对 分割过程进行指导，而且还采用了梯度图像来抑制过分割现象，使得分水岭分割 的效果大大提高。c l a r k e 等人在他们的文章中广泛地对图像分割的方法做了评论 【5 4 1 。随着学者们对分水岭算法不断关注和研究，该方法在图像分割领域发挥着越 来越重要的作用。 从某个角度来说，采用分水岭算法对图像进行分割就是将图像中的像素点进 行聚类的过程，所以后来人们又提出了基于分水岭变换的聚类算法【7 4 , 7 5 ，它的基 本思想是：对于一个数据点集( 即由一系列分布在二维空间的数据点构成的集合) 来说，首先要把数据点空间划分为固定边长的网格，接着估计每个网格中数据点 的密度，作为该网格的灰度值。为了使网格的灰度值易于观测，通常要把得到的 灰度值归一化到0 , 2 5 5 1 ，从而得到一幅数字灰度图像；然后用分水岭算法对得到 的数字灰度图像进行分割，得到的盆地个数就是聚类的个数；最后还要把分水岭 去掉，也就是把落在分水岭网格内的数据点也划分到某个聚类中。算法的流程如 图1 1 所示。 输入 样 划 密 灰 灰 分 去 聚 本 分 度 度 一 度 水除 输出。类 网 估 归图 岭 一 分 结 集 络计 - 像 变 水 换 岭 果 图1 1 分水岭聚类算法流程 传统的聚类算法在聚类的过程中需要知道期望的聚类数目，并且对高维数据 的处理能力较弱。基于分水岭变换的聚类算法能够克服这些不足，给出更好的聚 类效果。 图像分割可以理解为将图像中的像素点进行聚类处理，使得相似的像素点被 分配在同一个类别中，不相似的像素点被分配到不同的类别当中的过程。这里， 与其他聚类方法不同的是，分水岭处理的图像像素数据集包含位置信息，以像素 点的灰度值为特征进行分割处理的，处理的结果是将图像像素点分割为不同的类 别，且存在不属于某一个区域的分水岭像素点。 1 3 论文的主要工作和内容安排 随着聚类分析的不断研究深入，聚类分析的各种方法也得到了不断的改进和 6 基于规范切和分水岭的聚类算法研究 完善，有关聚类分析的理论分析及实际应用都取得了丰硕的成果。本文主要从聚 类分析中的谱聚类算法、分层聚类算法和分水岭方法出发，对聚类分析及相关的 应用问题进行了深入的研究，主要做了三方面的工作，分别对应于本文的第二至 四章。 第一章：介绍了聚类学习的研究背景及发展，对几种经典的聚类算法做了进 一步的介绍，包括k - m e a n s 方法、谱聚类方法、分层聚类方法和基于分水岭变换 的聚类方法。 第二章：主要包括谱聚类算法的常用术语，基本思想及算法步骤等。在研究 基于规范切的谱聚类算法的基础上，本章提出了一种基于相似性与相异性的谱聚 类算法，并在相同的实验平台上与传统的两种聚类算法进行了比较。实验结果表 明，用基于相似性与相异性的谱聚类方法得到的特征向量能够更好地表示数据之 间的分布情况，达到更优的聚类效果和更高的聚类正确率。 第三章：介绍了与本文相关的一些分层聚类算法的基础理论。考虑谱聚类算 方法中的规范切准则具有能更好地体现类别之间相似性和相异性的优点，分层聚 类方法中存在的在非凸数据集上容易陷入局部最优的不足，本章提出了一种基于 规范切的分层聚类算法，并在相同的实验平台上与传统的两种分层聚类方法进行 比较。实验结果表明，基于规范切的分层聚类算法不但可以在凸球形分布的数据 集上得到较好的聚类效果，而且可以克服经典分层聚类算法在具有流形分布的数 据集上聚类效果差的缺点。 第四章：通过研究计算机图形图像处理技术及其在医学图像处理方面的应用， 本章介绍了一种基于三维区域分水岭的腹部主要血管提取方法，该方法主要研究 了如何应用分水岭方法对三维腹部医学图像中的主要血管进行分割提取，保证在 充分利用图像三维信息的同时，尽可能减少算法的时间复杂度，并得到较好的图 像分割效果。实验结果表明，本方法可以较快、较好的完成医学图像的分割，提 取出腹部主要血管。 第五章：对本文提出的二、三、四章中的方法进行了总结，分析了其优缺点， 并对这些方法存在的问题提出了一些值得深入研究的方向，展望了其发展的前景。 第二章基于相似性与相异性的谱聚类算法 7 第二章基于相似性与相异性的谱聚类算法 谱聚类算法是近几年来机器学习领域一个新的研究热点。最初，它是用于负 载均衡和并行计算，以及v l s i 设计等方面，如h a g e n 和k a h n g 【3 4 j 将基于r a t i o c u t 的 目标函数图划分算法用于v l s i 设计中。最近，学者们也开始将谱聚类方法用于机 器学习中。s h i 和m a l i k 3 6 】在2 0 0 0 年根据谱图理论建立了2 - w a y 划分的 n o r m a i l i z e d c u t ( n c u t ) 的目标函数，设计了用于图像分割的算法，由此发展出一系 列算法：k w a y 划分的n c u t 算法( n g 和w e i s s 【7 6 1 ) ；n o r m a l i z e d c u t 与随机游动关系的 算法( m e i l a 和s 1 1 i ) ；基于二分图的算、法( z h a t 7 8 署1 1 d h i l l o n 硎) 等。此外谱聚类方法 的应用也开始从图像分割领域扩展到文本挖掘( d h i l l o n t 7 川) 和生物信息挖掘领域 ( c h r i sd i n gt 8 0 1 ) 等领域中。 通过深入学习研究谱聚类算法，为了进一步增加谱聚类算法中类内数据点的 相似程度，减小类间数据点的相似程度，从而得到更好的聚类结果，本章提出一 种基于相似性与相异性的谱聚类算法，该方法在经典谱聚类算法的基础之上，加 入距离矩阵的影响，在聚类的过程中进一步体现数据点之间的相似性与相异性， 从而提高谱聚类的效果。 2 1 谱聚类概述 谱聚类以图论中的谱图理论为基础，其主要思想是将数据集聚类的过程转化 为与数据集对应图的最优划分的过程，通过将各个数据点及数据点之间的相似性 程度映射到图上，然后通过采用图划分的方法达到将数据点分为不同类别的目的。 谱聚类方法能够在任意形状的数据分布空间上聚类，且收敛于全局最优解1 2 】。 在谱图理论中，图的划分方法有很多种，不同的划分方法则对应不同的聚类 准则，而聚类准则的好坏会直接影响到聚类结果的优劣。 2 1 1 谱聚类方法的准则函数 谱聚类以谱图理论为基础，而在谱图理论中，图的最优划分方法及准则已经 研究的相当成熟，其基本原则就是使划分成的两个子图内部相似度最大，子图之 间的相似度最小，这也正符合聚类的基本假设。需要注意的是，划分准则的好坏 会直接影响到聚类结果的优劣。 常见的谱聚类算法划分准则有最小切( m i n i m u mc u t ) 准则【5 7 1 ，平均切( a v e r a g e e u t ) 准贝t j t 5 8 1 ，规范切( n o r m a l i z e dc u t ) 准则【3 6 】，最小最大切( m i 啪a ) 【c u t ) 准则【3 3 1 ，比 例切( r a t i oc u t ) 准则3 0 ，3 4 】等。 8 基于规范切和分水岭的聚类算法研究 在谱图理论中，将图g 划分为没有交集的a ，b 两个子图( 即au b = v ， anb = i 2 j ，v 为图g 中所有顶点的集合) ，采用最小切( m i n i m u mc u t ) t 5 7 1 准则的 目标函数为： c u t ( a ，b ) = 呒， ( 2 - 1 ) 其中，呒，表示顶点z ，和1 ，之间的相似性程度。w u 和l e a l a y 提出最小化上述目标函 数值来划分图g ，他们用这个准则对一些图像进行分割，产生了较好的分割效果， 同时他们也注意到，该准则容易出现歪斜( 即偏向小区域) 分割。 s l l i 和m a l i k 在2 0 0 0 年发表的文章中f 3 6 】，根据谱图理论建立了2 - w a y 划分的 规范切( n o r m a l i z e dc u t ) 目标函数( n c u t ) ： n c 甜( a ，b ) ：巡垒：里2 + 塑垒：型 ( 2 2 )。7 a s s o c ( a ，v ) a s s o c ( b ，v ) 、7 其中 a s s o c ( a ，v ) = 呒， 最小化n c u t 函数( 2 2 ) 被称为规范切准则，数据数据点的最优划分就是该目标 函数的最小化。该准则不仅能够衡量类内数据点间的相似程度，也能衡量类间数 据点间的相异程度，它在最小化类间数据点相似程度的同时能最大化类内数据点 的相似程度，且能够有效避免最小切准则中容易出现的偏向小区域分割问题。 下面给出其它的各种划分准则目标函数，它们也都存在各自的优缺点。 h a g e n 和k a h n g 提出了比例切( 胁i oc u t ) t 3 4 】准则的目标函数： r 刚2 硐c u t ( a , b ) ( 2 - 3 ) 肌n i i a i ，l 廿i ) 其中i a i ，i b i 表示子图a ，b 中顶点的个数。比例切准则也能改善最小切准则的缺 点，减小过分割的可能，但其运行速度较慢。 平均切【5 s l ( a v e r a g ec u t ) 准则的目标函数： 彳v c u t ( a ，b ) 2 眢+ 眢 ( 2 - 4 ) 平均切准则与规范切准则都能得到较准确的分割，但同时运行二者时规范切准则 得到较好的效果。 最小最大害i j _ t ： j ( m i n - m a xc u t ) t 3 3 1 准则要求最小化c u t ( a ，b ) 的同时，最大化 a s s o c ( a ，a ) 与a s s o c ( b ，b ) 。该准则可通过最小化下面的目标函数得以实现： 第二章基于相似性与相异性的谱聚类算法 9 。m c u t ( a ，b ) ：! 丝! 垒：堡2 + ! 丝! 垒：堡2 ( 2 5 ) 。 a s s o c ( a ，a )a s s o c ( b ，b ) 。 最大最小切准则与规范切准则具有相似的行为，满足类间数据点间的相似度小而 类内数据点间的相似度大的原则，当类间重叠较大时，最大最小切准则比规范切 准则得到更佳的效果，但其实现速度较慢。 通过上述的对比分析可明显看到，在各种谱聚类的准则函数中，规范切准则 函数具有一定的优势。本文提出的两种聚类算法都是以规范切准则为基础的。 2 1 2 谱聚类算法的框架 根据谱聚类的基本思想可以知道，谱聚类的过程就是根据数据集构造一个图， 该图的每一个顶点对应一个数据点，将相似的点连接起来，并且用边的权重来衡 量数据点之间的相似度。谱聚类的过程就是把这个图用邻接矩阵的形式表示出来 ( 记为相似性矩阵w ，w 中的元素形，表示第f 个数据点和第，个数据点之间的相 似程度，彬，越大相似性越高) ，然后根据图的分割理论对其进行分割处理的过程， 其聚类算法流程主要包括四大步骤，见算法2 1 。 这里，随着聚类算法的不断发展，步骤4 中使用的k m e a n s 算法也可以用其他 的聚类算法替代来完成最后的聚类，得到最终的聚类结果。 2 2 以规范切为目标函数的谱聚类算法 s h i 和m a l i k 在2 0 0 0 年根据谱图理论建立了2 - w a y 划分的规范切目标函数 ( n c u t ) t 3 6 1 ，其目标函数如式( 2 2 ) 所示。g t d g n c u t 函数被称为规范切准则，数据样 算法2 1 ：谱聚类算法主要实现步骤 输入： s t e p l ： s t e p 2 s t e p 3 ： s t e p 4 ： 输出： 包含个数据的待分类数据集、待分类类别数目k ； 根据数据构造图g ，并计算数据的相似性矩阵w ； 把w 的每一行元素加起来得到个数，把它们放在对角线上( 其他地方都是零) ，组 成一个n xn 的矩阵，记为d 。并令l = d w ，( l 为拉普拉斯矩阵) ； 对矩阵l 进行特征分解，求出l 的前k 个最小特征值以及其对应的特征向量。把 这k 个特征( 列) 向量排列在起组成一个n k 的矩阵； 将n k 中每一行看作七维空间中的一个向量，并使用k - m e a n s 算法进行聚类。聚 类的结果中每一行所属的类别就是原来图g 中的顶点亦即最初的个数据点分别 所属的类别； 各个数据点的类别标记。 l o 基于规范切和分水岭的聚类算法研究 本的最优划分就是该目标函数的最小化。该准则不仅能够衡量类内数据点间的相 似程度，也能衡量类间数据点间的相异程度，它在最小化类间数据点相似程度的 同时能最大化类内数据点的相似程度，且能够有效避免最小割切中容易出现的偏 向小区域分割问题。 最小化规范切目标函数( 2 2 ) 可进一步表示为： 疵f ( a ，b ) ：曲塑掌 ( 2 6 ) y 1d y 舭 y y t d y ：- - 。i 其中1 表示全1 的列向量，y 为聚类结果指示向量，w 为数据数据点的相似性矩阵， 其元素可表示为： 形，：p 一( 吲2 盯2 ) 其中，f 和，表示数据集中的两个数据点，g 。，为数据点霸铂，之间的距离度量，一 般取其欧式距离，仃为事先指定的参数。将w 的第衍亍元素相加，即得到顶点i 的 度，以所有度值为对角元素构成的对角矩阵即为度矩阵d 。 可以看到式( 2 6 ) 表示的是瑞利方程，这样我们就可以考虑指示向量y 的连续 放松形式，通过对( d w ) y = 2 d y 进行特征分解来最小化( 2 - 6 ) 。基于规范切的谱 聚类算法就是通过对上式进行特征分解来实现的。 2 3 1 算法描述 2 3 基于相似性与相异性的谱聚类算法 在谱聚类算法中，增大类内数据数据点的相似程度和减小类间数据数据点的 相异程度可以大大提高聚类的效果，为进一步实现该目的，本章以经典的规范切 谱聚类算法为出发点，提出一种基于相似性与相异性的谱聚类算法。 基于相似性与相异性的谱聚类算法，具体实施即就是在进行特征分解的过程 中，加入距离矩阵的影响，将相似性矩阵w 和距离矩阵q 相结合得到新的准则函 数，如公式( 2 7 ) 所示： m i n 带盟旦塑l 一一 ( 2 7 ) y 1 ( ( 1 - 历) d + 聊q ) y 第二章基于相似性与相异性的谱聚类算法 1 1 f y 丁d y = 1 s f y t d l ：0 卜聪， 其中m 为决定距离矩阵影响程度的参数，m 越大，距离矩阵在聚类过程中的影响 就越大，当册= o 时，本章提出的方法与基于规范切的谱聚类算法等价，q 中数据 元素q 的大小与相似性矩阵w 中的对应元素形。，成反比例，q ，j 即两个数据数据 点，和之间的距离度量，距离越大，其相似程度越小，反之亦然。 从式( 2 6 ) 和式( 2 7 ) 可以明显看出，与规范切准则相比，基于相似性与相异性 的方法在其目标函数中增加了分母上的与距离矩阵q 有关的一项。式( 2 7 ) 的分子 可以展开如下： mmm y 1 ( d - w ) y = y 1d y - y 1w y = d j 。，砰一y , y j e ， = 1 2 ( q ，谚- 2 乃乃彬，+ b 巧) = 三( 形，彭一2 以乃彬，+ 乏乏形，巧) = 去( y , - y j ) 2 形，_ ， 其中，y ，和y ，为指示向量中第f 和j 个数据点对应的值，q ，为矩阵d 对角线上的 第f 个元素，即矩阵w 中第i 行所有元素的和。同理对式( 2 - 7 ) 的分母可以展开如 下： mmm y 1 ( d + m q ) y = y 1d y + m x y 上q y = d j ，y y j + m x 此乃q ， d f 为矩阵d 中第衍亍，第列对应的元素值。根据上面的展开形式可以将式( 2 - 7 ) 写成如下式( 2 8 ) 的形式： ( 乃- y j ) 2 形。， m i n ( 1 - 所) d i 。j y , y j + m x y , y j q , ， i , j = li , j = l ( 2 - 8 ) 1 2 基于规范切和分水岭的聚类算法研究 分析式( 2 - 8 ) 可知，按照聚类假设，当q 。，很小的时候，分母的第二项对整个 目标函数的影响较小，两个数据点f 和，倾向于被分到同一个聚类当中，此时分子 上的相似度彬取值较大，最小化目标函数即要求( 只- y ) 2 很小，数据点m 和乃的 相似性得到体现；当q ，很大的时候，两个数据点f 和倾向于被分到不同聚类当 中，此时，因为q 。，的影响，目标函数分母中与f 和j 相关的一项很大，此时即使 增加( 形一y ，) 2 来让距离远的数据点分得更开，也不会对整个目标函数产生大的影 响，这样就增加了数据点之间的相异程度，体现了其相异性。 综上所述，基于相似性与相异性的谱聚类算法通过增加距离矩阵q 的影响， 巧妙设计了新的聚类准则函数。从理论上来讲，基于该新准则函数的谱聚类算法 能更进一步增加类内数据数据点的相似程度和类间数据数据点的相异程度，为得 到更好的聚类结果提供保证。 同理于基于规范切的谱聚类算法，式( 2 - 7 ) 表示的是瑞利方程，考虑指示向量y 的连续放松形式，我们就可以通过对( d w ) y = 入( ( 卜m ) d + m q ) y 进行特 征分解来最小化式( 2 7 ) 。 2 3 2 算法实现步骤 根据上述的基于相似性与相异性的谱聚类算法基本原理，这里给出其实现步 骤，见算法2 2 。 算法2 2 基于相似性与相异性的谱聚类算法实现步骤 输入： s t e p l ： s t e p 2 ： s t e p 4 - 输出： 待聚类数据集； 输入待聚类数据集及期望的聚类数后； 根据下列公式分别计算数据集的距离矩阵q 和相似性矩阵w ： q ，：野，彬。，：p 一q ，2 仃2 计算度矩阵d ，并对下式进行广义特征分解： ( d w ) y = 入( ( 1 一m ) d + 仇q ) y 选择前七个最小特征值对应的特征向量，在该庇个特征向量组成的特征向量空间上， 采用经典的聚类算法进行聚类： 各个数据点的类别标记。 第二章基于相似性与相异性的谱聚类算法 1 3 2 4 实验结果及其分析 以下实验全部是在平台m a t l a b 7 0 环境，p i v2 6 g h z ，1 0 g b 内存的微机上进 行。基于相似性与相异性的谱聚类算法的仿真实验分别在3 组人工数据集和1 0 组u c i 数据集上进行。这里的距离矩阵q 中每个元素为两两数据数据点之间的欧 式距离，在特征向