（计算机应用技术专业论文）关联图的谱分析及谱聚类方法研究.pdf

摘要 随着聚类分析应用的领域扩展和深入，高维聚类问题成为当前聚类分析研究 的重点。近年来，大量图的聚类问题研究相当活跃。聚类研究中如何衡量样品间 的亲疏程度的数量指标通常归纳为相似系数和距离两种。图的聚类尤其是大量关 联图的聚类问题的难点在于图的表达方法，图的距离函数的定义等方面。本文以 图的谱理论和统计理论为基础，研究关联图的谱及谱分解特征、关联图的低维空 间的表达和聚类分析。主要的内容包括四个方面：1 ) 图的谱分析及其图的谱分 解；2 ) 图的谱降维及低维空间的视觉化显示；3 ) 图的谱聚类；4 ) 基于图的谱 编辑距离的聚类研究。本文的研究内容和创新之处如下： 图像的关联图描述研究。图像的图的数据化表达可根据图像的几何特征来构 成，图像几何特征包括角点、顶点、拐点、边缘和纹理等，通过这些特征又可以 构成关联图，如区域邻接图、线段构成的图、特征点构成的图和角点构成的图等。 正是由于几何特征在抗噪声方面的优势，再加上图像几何特征提取技术的日益发 展，使得关联图在图像处理及模式识别方面的研究日趋活跃。文中对每幅图像提 取相应的角点特征，并以此构成不同的关联图。实验中用d e l a u n a y 图构成相应 的矩阵，研究的矩阵主要有二值邻接矩阵、加权邻接矩阵和拉普拉斯矩阵等。 图的谱及图的谱分解研究。一个图的邻接矩阵的特征值是该图的谱，将特征 值按降序排列，以此为索引指数，由此构成模特征矩阵。文中用模特征矩阵进行 图的谱分解从而得到新的谱特征，它们包括：主分量特征值、特征模体积、特征 模周界、c h e e g e r 常数、模间邻接矩阵和模间距离。同时用拉普拉斯矩阵的特征 值和特征向量构成拉普拉斯特征值、谱系数夹角两个新的谱特征。它们从不同的 方面描述了图中点和边等的关联关系，表达了图的结构分布情况，使得一个图的 结构信息通过这些特征向量来表达，为进一步的研究奠定了很好的基础。 图的谱降维研究。图的谱及谱分解后的谱特征具有较高的维数，为提高聚类 的性能和显示高维数据，便于在低维空间发现关联图的图之间的固有结构相似 性。本文实现了些谱特征降维方法，它们包括线性内嵌方法和非线性内嵌方法， 分别是主成分分析( p c a ) 、独立成分分析( i c a ) 、局部保持投影( l p p ) 、多维 尺度变换( m d s ) 和局部线性内嵌( l l e ) 诸方法。同时给出拉普拉斯矩阵的特 m 征值和谱系数夹角特征在不同降维方法下的图的表达，并与邻接矩阵谱特征进行 了比较。 图的谱聚类研究。用数据间的相似程度来衡量样本间的亲疏程度，并以此思 想进行关联图的聚类研究。文中搭建了序列图像的聚类系统框图，同时在特征空 间实现图的谱聚类算法。具体的步骤是：1 ) 计算图的谱特征；2 ) 进行图的谱降 维；3 ) 在低维特征空间进行模糊c 一均值( f c m ) 和模糊c 一中值( f c m e d ) 聚 类研究；4 ) 最后用几种有效性函数给出该算法的有效性分析。实验结果显示该 方法有较好的鲁棒性。同时发现拉普拉斯矩阵的谱系数夹角特征对图的谱聚类也 有较好的效果。 图的谱编辑距离聚类研究。谱编辑距离也是衡量样品间的亲疏程度的一项常 用指标。文中提出了图的谱编辑距离聚类算法的系统框图，以图的谱编辑距离定 义关联图的广义距离，组成该距离矩阵，用矩阵更新的合并聚类算法完成不同关 联图的聚类。具体的方法是：1 ) 以图的谱方法构成每个图的点对应的谱序列；2 ) 改进传统的串编辑距离算法计算图与图间的广义距离即谱编辑距离；3 ) 以此距 离为依据完成基于矩阵更新的合并聚类算法。实验显示该方法得到较好的聚类结 果。 人脸识别方面的应用研究。将图的谱特征、关联图的表达、图的谱聚类和图 的谱编辑距离聚类方法应用到人脸检测和人脸识别应用研究上，在人脸的结构描 述、人脸的表情聚类和不同人脸的聚类和识别上进行实验研究。结果证明，图的 谱方法在表达人脸结构图和聚类分析方面是有效的。 关键词：关联图；关联图谱；谱系数夹角：谱聚类；谱编辑距离。 a b s t r a c t a st h ea p p l i c a t i o no fc l u s t e r i n gi se x t e n d e da n df u r t h e ri n v e s t i g a t e d ，t h e p r o b l e m so f c l u s t e r i n gi nh i g hd i m e n s i o n sb e c o m et h eh o tt o p i co f c l u s t e r i n gr e s e a r c h i nt h el a s tf e wy e a r s ，c l u s t e r i n go fg r a p h si nh u g ed a t a b a s ei sa l s oa na c t i v er e s e a r c h p r o b l e mi nc l u s t e r i n g ，m e t r i cf e a t u r e sw h i c hm e a s u r et h ef r i e n d l i n e s sr e l a t i o n s h i p s a r eo f t e nc l a s s i f i e di n t o s i m i l a r i t yc o e f f i c i e n t s a n dd i s t a n c e st h ed i f f i c u l t yo f c l u s t e r i n go fg r a p h s ，e s p e c i a l l yt h ec l u s t e r i n go fl a r g ea m o u n to fr e l a t i o n a lg r a p h s ， l i e so nt h er e p r e s e n t a t i o no fg r a p h sa n dt h ed e f i n i t i o no fd i s t a n c ef u n c t i o n t h i s d i s s e r t a t i o ni sb a s e do ns p e c t r at h e o r yo fg r a p h sa n ds t a t i s t i c a lt h e o r i e s i nt h i s d i s s e r t a t i o n ，w ei n v e s t i g a t eg r a p hs p e c t r aa n ds p e c t r a lf e a t u r e s ，r e l a t i o n a lg r a p h r e p r e s e n t a t i o na n dc l u s t e r i n gi nl o wd i m e n s i o n a ls p a c e s t h e r ea r ef o u rr e s e a r c h a s p e c t s ：1 ) g r a p hs p e c t r aa n ds p e c t r a ld e c o m p o s i t i o n ；2 ) d i m e n s i o n a l i t yr e d u c t i o no f s p e c t r af e a t u r e sa n dt h ev i s u a l i z a t i o no fg r a p hs e t si nl o wd i m e n s i o n a ls p a c e s ；3 ) s p e c t r a lc l u s t e r i n go fg r a p h s ；4 ) g r a p hc l u s t e r i n ga n a l y s i sb a s e do ns p e c t r a le d i t d i s t a n c e t h e c o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ea sf o l l o w s ： r e l a t i o n a lg r a p hd e s c r i p t i o no fi m a g e st h er e l a t i o n a lg r a p hr e p r e s e n t a t i o no f i m a g e sc a nb ec o n s t r u c t e db yg e o m e t r i c a lf e a t u r e si ni m a g e s ，s u c ha sc o r n e rp o i n t s ， v e r t e xp o i n t s ，i n f l e c t i o np o i n t s ，b o u n d a r i e sa n dt e x t u r e s u s i n gt h e s ef e a t u r e s ，w ec a n c o n s t r u c tr e l a t i o n a lg r a p h s ，s u c ha sr e g i o n a la d j a c e n tg r a p h s ，g r a p h sb u i l tb yl i n e s e g m e n t s ，f e a t u r ep o i n t sa n dc o m e rp o i n t sb e c a u s eo ft h es u p e r i o r i t yi na n t i n o i s i n g o fg e o m e t r i c a lf e a t u r e s ，a n dt h eg r e a td e v e l o p m e n to fs e g m e n t a t i o no fg e o m e t r i c a l f e a t u r e si ni m a g e s ，t h er e s e a r c ho nr e l a t i o n a lg r a p h sb e c o m e sm o r ea n dm o r ea c t i v e w ee x t r a c tf e a t u r e so fc o m e rp o i n t si ni m a g e s ，a n dc o n s t r u c td i f f e r e n tt y p e so f r e l a t i o n a lg r a p h sd e l a u n a yg r a p h sa r eu s e dt oc o n s t r u c tt h ec o r r e s p o n d i n gm a t r i c e si n e x p e r i m e n t s ，m a t r i c e si nr e s e a r c hm a i n l yi n c l u d eb i n a r ya d j a c e n tm a t r i x ，w e i g h t e d a d j a c e n tm a t r i xa n dl a p l a c i a nm a t r i x g r a p hs p e c t r aa n ds p e c t r a ld e c o m p o s i t i o nt h ee i g e n v a l u e so ft h ea d j a c e n c y m a t r i xo far e l a t i o n a lg r a p hi si t ss p e c t r ae a c he i g e n v a l u eh a si t sc o r r e s p o n d i n g e i g e n v e c t o r t h e s ee i g e n v a l u e sa r ea r r a n g e di nd e s c e n d i n go r d e r u s i n gt h eo r d e r e d v e i g e n v a l u e sa sa ni n d e x ，w ec o n s t r u c te i g e n m o d em a t r i xb a s e do nt h ec o r r e s p o n d i n g e i g e n v a l u e si nt h i sd i s s e r t a t i o n ，w ep e r f o r ms p e c t r a ld e c o m p o s i t i o no fg r a p h s ，a n d c o n s t r u c ts o m en e ws p e c t r a lf e a t u r e sb a s e do ne i g e n m o d em a t r i c e s ，s u c ha sp r i n c i p a l e i g e n v a l u e s ，e i g e n m o d ev o l u m e ，e i g e n m o d ep e r i m e t e r , c h e e g e r c o n s t a n t ， b e t w e e n m o d ea d j a c e n tm a t r i xa n db e t w e e n m o d ed i s t a n c em e a n w h i l e ，u s i n gt h e e i g e n v a l u e sa n de i g e n v e c t o r so fl a p l a c i a nm a t r i x ，w ec o n s t r u c ta n o t h e rt w on e w s p e c t r a lf e a t u r e s ：l a p l a c i a ne i g e n v a l u e sa n dt h ea n g l eb e t w e e ns p e c t r a lc o e f f i c i e n t v e c t o r st h e yd e s c r i b et h er e l a t i o n s h i p sb e t w e e nv e r t i c e sa n de d g e si ng r a p h sf r o m d i f f e r e n ta s p e c t s ，a n ds h o wt h ec o n f i g u r a t i o no fg r a p hs t r u c t u r e sr e s e a r c ho ns p e c t r a l d i m e n s i o n a l i t yr e d u c t i o n t h eg r a p hs p e c t r aa n dt h es p e c t r a lf e a t u r e sh a v eh i g h d i m e n s i o n si nn a t u r et oi m p r o v et h ep e r f o r m a n c eo fc l u s t e r i n ga n dv i s u a l i z a t i o no f h i g h - d i m e n s i o n a ld a t a , a n dt oi n v e s t i g a t et h ei n t r i n s i cs t r u c t u r eo fr e l a t i o n a lg r a p h si n l o wd i m e n s i o n s ，w er e a l i z es o m em e t h o d sf o rs p e c t r a ld i m e n s i o n a l i t yr e d u c t i o n ， w h i c hc o n t a i n sl i n e a re m b e d d i n ga n dn o n l i n e a re m b e d d i n gm e t h o d s ，s u c ha sp r i n c i p a l c o m p o n e n ta n a l y s i s ，i n d e p e n d e n tc o m p o n e n ta n a l y s i s ，l o c a l i t yp r e s e r v i n gp r o j e c t i o n s ， m u l t i d i m e n s i o n a ls c a l i n g ，l o c a ll i n e a re m b e d d i n g ，a n ds oo nm e a n w h i l e ，w ec o m p a r e t h ec l u s t e r i n gp e r f o r m a n c eo ft h el a p l a c i a ne i g e n v a l u e sa n dt h ea n g l eb e t w e e n s p e c t r a lc o e f f i c i e n tv e c t o r st ot h a to f t h es p e c t r a le i g e n v a l u e so f t h ea d j a c e n tm a t r i c e s r e s e a r c ho ns p e c t r a lc l u s t e r i n go fg r a p h sw eu s et h es i m i l a r i t yo ft h es p e c t r a l f e a t u r e sf o rr e l a t i o n a l g r a p hc l u s t e r i n g i n t h i s d i s s e r t a t i o n ，w ec o n s t r u c tt h e f r a m e w o r ko f c l u s t e r i n gs y s t e mf o rs e q u e n c eo f i m a g e s ，a n dr e a l i z es p e c t r a lc l u s t e r i n g m e t h o d si nf e a t u r es p a c e si nd e t a i l ，t h e r ea r ef o u rs t e p s ：1 ) c o m p u t i n gs p e c t r a l f e a t u r e so fg r a p h s ；2 ) p e r f o r m i n gs p e c t r a ld i m e n s i o n a | i t yr e d u c t i o no fg r a p h s ；3 ) p e r f o r m i n gf u z z yc m e a nm e t h o d ( f c m ) a n df u z z yc m e d i a nm e t h o d ( f c m e d ) i n l o ws p e c t r a lf e a t u r es p a c e ；4 ) p e r f o r m i n gv a l i d i t ya n a l y s i su s i n gs e v e r a lv a l i d i t y f u n c t i o n se x p e r i m e n t a lr e s u l t ss h o wt h e r o b u s t n e s so f t h ep r o p o s e dm e t h o d sw e f i n d t h eh i g hp e r f o r m a n c eo ft h ea n g l eb e t w e e ns p e c t r a lc o e f f i c i e n tv e c t o r sf o rs p e c t r a l c l u s t e r i n go f g r a p h s r e s e a r c ho ns p e c t r a le d i td i s t a n c eo fg r a p h sw ec o n s t r u c taf r a m e w o r ko f s p e c t r a lg r a p he d i t d i s t a n c e a l g o r i t h m ，a n d d e f i n et h eg e n e r a l i z e dd i s t a n c eo f r e l a t i o n a lg r a p hu s i n gs p e c t r a le d i td i s t a n c ead i s t a n c em a t r i xi si n t r o d u c e df o r c l u s t e r i n gd i f f e r e n tr e l a t i o n a lg r a p h sb a s e do n am a t r i xu p d a t i n gm e t h o dt h ed e t a i l e d m c t h o di sa st h ef o l l o w i n g ：1 ) c o n s t r u c t i n gs p e c t r as e q u e n c e sf o re a c hg r a p h ；2 ) c o m p u t i n gg e n e r a l i z e dd i s t a n c e sb e t w e e ng r a p h s ，t h a ti s ，s p e c t r a le d i td i s t a n c e ， u s i n gi m p r o v e dt r a d i t i o n a ls t r i n ge d i td i s t a n c e ；3 ) u s i n gt h i sd i s t a n c et oc o n s t r u c ta c o m b i n e dc l u s t e r i n ga l g o r i t h mb a s e do nm a t r i xu p d a t i n g e x p e r i m e n t ss h o wt h a tt h e p r o p o s e dm e t h o dh a sb e t t e rp e r f o r m a n c e a p p l i c a t i o n so nf a c er e c o g n i t i o ni nt h el a s tp a r to f t h i sd i s s e r t a t i o n ，w ea p p l yt h e p r o p o s e dm e t h o d so fs p e c t r a lf e a t u r e s ，r e p r e s e n t a t i o no fr e l a t i o n a lg r a p h s ，s p e c t r a l c l u s t e r i n go fg r a p h sa n ds p e c t r a ie d i td i s t a n c ec l u s t e r i n gm c t h o d st of a c ea n a l y s i s e x p e r i m e n t so nt h es p e c t r a ld e s c r i p t i o no ff a c es t r u c t u r ea n dt h es p e c t r a lc l u s t e r i n go f f a c ee x p r e s s i o no fd i f f e r e n tp e r s o n sa r ec o n d u c t e d e x p e r i m e n t a lr e s u l t ss h o wt h e v a l i d i t yo fg r a p hs p e c t r a lm e t h o d si nr e p r e s e n t i n gf a c es t r u c t u r ea n dc l u s t e r i n g a n a l y s i s k e y w o r d s ：r e l a t i o n a lg r a p h ；r e l a t i o n a lg r a p hs p e c t r a ；s p e c t r a lc o e f f i c i e n t a n g l e s p e c t r a lc l u s t e r i n g ；s p e c t r a le d i td i s t a n c eo f g r a p h s ； v i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得戈缘d 彰或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名：暾 签字日期： 加6 年r 月6 日 学位论文版权使用授权书 本学位论文作者完全了解撇有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权嚷魄水茏可以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 签字日瓤加年r 月占日 学位论文作者毕业去向： 工作单位：茵獭韧灿 通讯地址：幽溯喇 导师签名 签字日期 电话 邮编 熙 昭 窍 舢 眄 第零章绪论 第零章绪论 模式识别( p a t t e r nr e c o g n i t i o n ) 是一门以应用为基础的学科，目的是将 对象进行分类。这些对象可以与应用领域有关，它们可以是图像、信号波形或者 任何可测量且需要分类的对象。早在2 0 世纪6 0 年代以前，模式识别主要是统计 学领域中的理论研究，但计算机的发展提高了对模式识别实际应用的需求，而反 过来有对理论发展提出了更高的要求】。 模式识别的重要性主要体现在应用领域的广泛性和迫切性，它在很多方面都 与机器视觉和图像处理密切相关。光学字符识别( o p t i c a lc h a r a c t e r r e c o g n i t i o n ，o c r ) 系统已经开始在商业中应用；计算机辅助诊断早已在医疗中 广泛应用，如x 射线、计算机断面图、超声波图、心电图和脑电图；另外指纹识 别、签名认证、表情和手势识别等也吸引了众多的研究者。而要在所有这些应用 中达到目标，模式识别还依赖于其他一些学科的发展，如计算机图形学和计算机 视觉等吣w6 川。 模式识别大体可分为模板匹配( t e m p l a t em a t c h i n g ) 、句法( s y n t a c t i c ) 模式识别、神经网络( n e u r a ln e t w o r k s ) 方法、统计模式识别( s t a t i s t i c a l p a t t e r nr e c o g n i t i o n ) 、结构模式识别( s t r u c t u r a lp a t t e r nr e c o g n i t i o n ) 五 种基本方法。聚类( c l u s t e r i n g ) 分析和聚类算法的研究是模式识别中很重要的 一个分支，它广泛地应用了以上各种方法。 o 1 引言 在上个世纪八十年代以前，句法模式识别和结构模式识别由于缺乏健全的理 论基础，无法用精确的数学表示方法来表达实际的问题1 2 1 。在近二十多年来，统 计模式识别和神经网络方法的不断研究，使得模式识别在其他各学科的同时发展 下，得以不断地发展并应用到各个方面 ”。 o 1 1 模式识别系统 一个模式识别系统本质上包含三个方面：数据获取和预加工、数据表示和结 果输出，不同的问题可能就需要选择不同的传感器和不同的预处理、不同的数据 关联图的谱分析及谱聚类方法研究 表示模式和不同的后处理决策。五种不同的模式识别方法都在不同的方面有其独 特的一面，它们不需要各自独立，有时同一种方法可能还有不同的解释。表l 概要地列举不同方法之间的比较 , 1 l 1 2 , 1 3 。 表1五种模式识别方法比较 t a b l e1 c o m p a r i s o no fp a t t e r nr e c o g n i t i o n m e t h o d 方法表示法表示函数典型准则 模板匹配样本，象素，曲线相关，距离测量分类误差 统计识别特征判别式分类误差 句法和结构识别本原特征规则，语法接受误差 神经网络 样本，象素，特征网络函数平均平方误差 模式识别系统一般都有两个阶段组成：训练( 或学习，t r a i n i n g ，l e a r n i n g ) 和 测试( t e s t i n g ) 。训练是指用一定数量的样本( 称为训练集或学习集) 来进行分类 器( c l a s s i f i e r ) 的设计；测试是指用所设计的分类器对待识别的样本( 称为测试 集) 进行分类。 一个统计模式识别系统一般要包括以下几个部分( 如图0 1 ) 5 , 6 , 9 3 ： 1 ) 数据获取这通常取自一些传感器( s e n s o r t r a n s d u c e r ) ，譬如摄像机； 2 ) 目标分割将需要的对象从背景中分割出来，它是模式识别中最深层的问 题之一，且依赖于具体的问题和具体的领域； 3 ) 处理目的是去除噪声，加强有用的信息，进行归一化，并对一些退化现 象进行复原等； 4 ) 特征形成提取选择在文献中它们以不完全相同的意义所使用。特征形 成( 或表示模式) 是指由传感器测得的一组基本向量，如，由脸像的形状结构而 得到的二维坐标数据，这样产生的特征称为原始特征，也可称为( 原始测量) 。 我们要尽可能少的但显著的特征，这既会降低测量的代价，也会使分类器的设计 变得简单。对原始特征进行变换得到有利于分类、更本质、更少的新特征的过程 称为特征提取( 或特征压缩) 。准确地说，提取后的特征应称为二次特征。特征 选择是在给定的一组特征中选择一个子集的过程。特征选择也是由研究人员来完 成的，研究人员通过经验、己掌握的知识，以及对问题的认识来决定哪些变量对 第零章绪论 训练阶段 v l l 练梗式广 广l 特征形戚f 厂 一目标分割f 二刊颓处理f 二刊提取，选择f 二司学习i 竺压函h 匦丑也霉一矗橱 一一1 j 。一 测试阶段分类结果 图01 统计模式识别系统( 图中虚线箭头是反馈回路) f i g0ls y s t e mo f s t a t i s t i c a lp a t t e r nr e c o g n i t i o n 分类有用。我们希望获得的特征是：1 ) 保持信息( 或信息丢失可以控制) ；2 ) 来自同一类( c l u s t e r ) 的不同模式的特征非常接近，而不同类的模式的特征相距甚 远。当然也倾向于选择更鲁棒( r o b u s t ) 的特征，即对噪声或者其它干扰不敏感。 注意，特征选择后的特征保持它们原来的物理意义，而特征提取产生的新特征则 缺乏认知学上的意义。 5 ) 学习根据特征提取得到的特征设计分类器，完美性能的分类器通常不可 获得。学习是重要的，过去2 5 年来的反复实验和经验表明从样本集的学习是设 计分类器的最有效方法，( 从样本集的学习) 是大多数模式识别系统重要的属性 ”1 。p e 打o u ( “1 定义“模式识别系统的学习就是允许她处理现实的过程”，并指出 系统必须学习三种类型的不确定性：1 ) 测量误差；2 ) 类内的变差及3 ) 知识表 征( e l i c i t a t i o n ) 误差。 6 ) 分类利用分类器给待测试模式一个类别标记。分类的难易程度取决于两 个因素：1 ) 来自于同一个类别的不同个体之间的特征值的波动；2 ) 属于不同类 别的样本的特征值之间的差异。 7 ) 后处理根据分类结果评价分类器性能，分类器性能的一个简单度量是分 类器错误率。 以上提及的每一步，这些步骤的操作相互独立，但其区分也不是绝对的，在 应用中有些步骤可以合并。 关联图的谱分析及谱聚类方法研究 0 1 2 图像处理和图像描述 图像是客观世界能量或状态以可视化形式在二维平面上的投影，是社会生活 中最常见的一种信息媒体。它传递着物理世界的能量和事物状态的信息，是人类 获取外界原始信息的主要途径。“图”是物体投射或反射光的分布，“像”是人 的视觉系统对图的接受在大脑中形成的印象和反映，是主观和客观的结合。我们 在生产、科研或日常生活中看到的场景图像，包含着物体的“大量”的信息，通 过感觉、知觉、记忆、认知、搜索、形成概念，直到最终理解和识别视觉刺激。 数字图像处理实际上是利用计算机( 或数字技术) 对图像信息进行加工处理， 以改善图像质量、压缩图像数据或从图像数据中获取更多信息。图像的研究目的 和内容就是：1 ) 为改善视觉效果而进行的图像增强、恢复和变换；2 ) 为提高图 像传输和存储效率进行图像的编码、变换；3 ) 为进行图像分析、理解和识别需 要图像的增强、变换及图像的分割与描述；4 ) 图像重建。 在模式识别中，我们对图像的分割和描述往往更感兴趣。图像的描述大致有 区域描述、关系描述和结构描述，区域描述是在图像中感兴趣的区域被分割出来 后，对各个分割区域特点的描述，如形状、凹凸度等，关系描述则是研究把这些 区域组织为一个有意义的结构。这些描述之间即可独立往往又相互关联。图像特 征：投影特征、标记、f o u r i e r 描绘子、矩特征、比例特征、边心矩、边缘( e d g e ) 、 角点( c o r n e r ) 。本文中研究的是图像的结构，图像的结构描述较多的有图像或部 分图像边缘、角点及形状( s h a p e ) 等。我们以角点和边缘等可以形成图像相应的 结构，以获取图像的结构信息。图o 2 显示了原始图像在边缘检测后得到的图像 中感兴趣部分的一个例子吣l 。 - 沁j 奠 ， 警露每、； 一。：弋蔓始、 二 图o2 原始图像( 左) f i g 0 2t h er s wi m a g e ( 1 e f t ) 二ro 和边缘检测后的边缘图像 a n di m a g eo fe d g ep r o c e s s i n g 4 第零章绪论 o 2 聚类分析 聚类源于许多研究领域，包括数据挖掘、统计学、模式、机器学习等。在机 器学习领域，聚类是无监督学习( u n s u p e r v i s e dl e a r n i n g ) 的的一个例子。有 监督学习( s u p e r v i s e dl e a r n i n g ) 是集中每个样本都存在一个标记( 1 a b e l ) ， 表明它的类别，无监督学习所要研究的样本集中的样本没有类别标记，系统基于 样本间的度量相似性寻找样本集的“自然”分组，系统也可以先训练分类器，再 对样本集进行分类( 1 6 , 1 7 。 o 2 1 聚类分析概述 聚类是一个将数据集划分成若干组( c l a s s ) 或类的过程，使得同一类内的 数据对象具有较高的相似度，而不同类之间的数据对象相似度较低。聚类问题的 关键是把相似的事物聚集在一起。聚类可以是一个独立工具也可以是模式算法中 的一个预处理过程。聚类在处理模式识别和图像处理领域发挥着重要的作用。聚 类可以解决以下问题，如：哪类顾客喜欢哪类商品，喜欢同一类商品的人之间有 什么共同点，哪类用户决定购买商品是基于价格，而又有哪类用户购买商品是基 于商品的质量等问题吣1 。 如图0 3 给出了为完成一个分类任务必须遵循的步骤】。 匝4 譬 图0 3 分类的一般步骤 f i g 0 3p r o c e s so fc l u s t e r i n g 1 ) 特征选择必须适当地选择特征，尽可能多地包含任务关心的信息。在特 征中，使信息多余减少和最小化是主要目标。因为在有监督学习中，在应用之前 特征的预处理是必要的。 2 ) 近邻测度用于定量测量两个特征向量如何“相似”或“不相似”。很自 然地。保证所有选中的特征具有相同的近邻性，并且没有占支配地位的特征，这 关联图的谱分析及谱聚类方法研究 是预处理期间必须要注意的点。 3 ) 聚类准则这依赖于专家对“可判断”的解释，聚类准则以蕴涵在数据 集中类的类型为基础。例如，l 维空间的致密类特征向量可以根据一个准则判断， 但拉长类却需要另一个准则判断。 4 ) 聚类算法己经采用近邻测度和聚类准则，这一步涉及到选择特定的算 法，用于揭示数据集的聚类结构。 5 ) 结果验证一旦用聚类算法得到结果，就必须验证其正确性。 6 ) 结果判定在许多情况下，应用领域的专家必须用其他实验证据和分析 判定聚类结果，最后做出正确的结论。 聚类分析有很多算法，每种算法都是优化了某方面的数据特性，比如：最 小化类内距、最大化类间距等。聚类方法的优劣标准本身就是一个值得研究的问 题，对于聚类的评价有不同的标准，聚类方法的性能很大程度上取决于聚类的类 型。现在通用的聚类标准都是从几个方面来衡量，而没有完全使用量化的客观标 准。下面给出了六条关于聚类的主要标准： 1 ) 处理大的数据集合的能力； 2 ) 处理任意形状，包括有间隙的嵌套的数据的能力； 3 ) 算法处理的结果与数据输入的顺序是否相关，也就是说算法是否独立于 数据输入顺序； 4 ) 处理数据噪声的能力； 5 ) 是否需要预先知道聚类个数，是否需要用户给出领域知识； 6 ) 算法处理有很多属性数据的能力，也就是对数据维数是否敏感。 对于一个聚类算法可以从以上几个方面综合考虑。 o 2 2 聚类分析技术的分类 目前，聚类的分析技术有很多，大致可以区分为以下几类1 2 0 m ： i ) 划分方法( p a r t i t i o n i n gm e t h o d ) ，对于一个包含n 个数据对象的数据 集，构建k ( k n ) 个分组( 类) ，使得每一个类中至少包含一个对象，每一个对象 属于且仅属于一个类，并且要求同一个类中的对象越接近越好、不同类中的对象 越远越好。对于给定的k ，算法首先给出一个初始的分组方法，以后通过反复迭 代来改变分组，使得每一次迭代后的分组方案都较前一次好。分组方案的好坏用 6 第零章绪论 一个目标函数来衡量，算法进行反复迭代的过程就是最优化目标函数的过程因此 划分方法也称为最优化方法。此类算法有k - m e a n s 算法、p a m 算法、i s o d a t a 算 法、g k a 算法、c l a r a 算法、c l a r a n s 算法、s t i r r 算法。 2 ) 层次方法( h i e r a r c h i c a lm e t h o d ) ，对给定的数据集进行层次的分解，直 到满足终止条件为止。根据层次的形成过程，层次方法又分为合并 ( a g g l o m e r a t i v e ) 方法和分裂( d i v i s i v e ) 方法。合并方法又称为自底向上的 方法，开始时将每个对象作为单独的一个组，然后相继地合并相近的对象或组， 直到合并为一个组或达到终止条件，终止条件可以是类的数目，或者是进行合并 的阈值。由于合并方法的时间复杂度至少为o ( n2 ) ，所以需要采用适当的技术来加 速合并的过程：其一是通过预处理来减少处理的对象个数，包括使用采样技术、 划分技术；其二是使用索引技术，包括队列、堆、树，比如b i r c h 算法就是使用 了c f 树、c u r e 算法使用k - d 树和堆、r o c k 算法使用二层堆、s t i n g 算法使用类 似四叉树的索引、c h a m e l e o n 算法使用k d 树和基于堆的优先队列，另还有r o c k 算法等。 分裂方法又称自顶向下的方法，开始时假定所有的对象属于一个组，在每一 步迭代中，根据分裂具有最大相异性的对象的原则，将组分裂为更小的组，直到 每一组中只包含一个对象或达到终止条件。终止条件可以是类的数目，或者是进 行分裂的闽值。属于该类方法的聚类算法有a r h p 算法、p d d p 算法、o p t i g r i d 算法、d i a n a 算法、m o n a 算法等。 层次方法的缺点是一旦一个步骤( 合并或分裂) 完成，就不能被撤消，即不 能更正错误的步骤。对此，有两种改进方法：( a ) 在每层划分中，仔细分析对象 间的“联接”，如c u r e 、c h a m e l e o n 中的做法；( b ) 综合层次合并和迭代的重定 位方法，即首先用自底向上的层次算法，然后用迭代的重定位来改进结果，如