（管理科学与工程专业论文）基于视觉的聚类算法研究及应用.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示谢意。 学位论文作者签名： 槭谚 导师签字 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解 密后适用本授权书) 学位论文作者签名：锐釜岁参 导师签字 签字日期：2 0 0 妒日签字日期：2 0 0 易年妒泊 山东师范大学硕士学位论文 基于视觉的聚类算法研究及应用 摘要 聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽可能小， 类内相似性尽可能大。聚类是一个无监督的学习过程，它同分类的根本区别在于： 分类是需要事先知道所依据的数据特征，而聚类是要找到这个数据特征，因此， 在很多应用中，聚类分析作为一种数据预处理过程，是进一步分析和处理数据的 基础。 聚类分析是一种重要的人类行为。聚类分析算法取决于数据的类型、聚类的 目的和应用领域。在当今飞速发展的数据采掘和探查性数据分析中，聚类分析技 术已广泛应用于模式识别和图像处理、生物、心理、计算机视觉和遥感等领域。 在实际问题中，传统的聚类分析技术普遍存在的不足之处主要表现在以下几个方 面：聚类结果对初始化参数的敏感性和强依赖性；很难定义聚类的有效性问题， 合理的聚类数目难以确定；直接的物理可解释性较差。 近年来，神经生理学的发展和计算机辅助解剖学的研究提出了几个相当精确 的初级视觉系统计算模型，它们分别建模于视觉系统的不同部分的不同层次。尺 度空间理论便是其中之一，它定量地描述由视网膜侧向联接所造成的图像模糊化 效应。 本文通过视觉原理与尺度空间算法结合，提出视觉系统的结构显著性假设和 稳定性假设，利用尺度空间聚类算法，得到不同层次的有效聚类。 主要工作： 1 、聚类算法比较 聚类算法有很多种，需要根据应用所涉及的数据类型、聚类的目的以及具体 应用要求来选择合适的聚类算法。聚类算法大体可以划分为以下几类：划分方法、 层次方法、基于密度的方法、基于网格的方法和基于模型的方法。然后对各种聚 类具体算法进行比较，得出不同方法之间在性能上的不同。 2 、视觉系统的结构假设 通过介绍视觉系统、w e b e r 定律、视觉系统的结构显著性假设和稳定性假设， 为下一章尺度空间聚类算法做好铺垫。视觉系统的结构显著性假设：那些引起较 多神经细胞兴奋的结构要比那些引起较少神经细胞兴奋的结构更为重要。视觉系 统的结构稳定性假设：那些在较大尺度范围内可观察到的物体结构较之那些在较 小尺度范围内可观察到的物体结构更为重要。 2 山东师范大学硕士学位论文 3 、尺度空间聚类算法 首先介绍尺度空间概念，介绍视网膜生物模型，视觉前端系统的尺度空间模 型，重点介绍尺度空间聚类算法。尺度空间原理：当尺度参数充分小时，每一数 据点是一个类，而当尺度参数逐渐变大时，小的数据类逐渐溶合形成大的数据类。 这分类方式所产生的结果构成一树形图，结点代表不同尺度聚类的类，父亲结 点所表示的类由儿子结点所代表的类溶合而成。这一聚类算法属逐级聚类算法， 它包含了数据的一系列分类。 4 、聚类有效性的问题 聚类有效性是聚类分析中一个较为困难的问题，它涉及算法产生的数据结构 的意义及解释，诸如数据中存在多少个类、由算法得到的类是真实的吗、哪一种 划分更有效等一系列问题。通过四个方面的解释，对聚类有效性作出判断。 5 、举例说明 通过模拟数值试验，用以说明尺度聚类算法可得到不同层次的有效聚类。 关键词：聚类算法，视觉系统，尺度空问聚类算法 分类号：t p 3 0 1 6 山东师范大学硕士学位论文 v i s i o n - b a s e dc l u s t e r i n ga l g o r i t h mr e s e a r c ha n da p p l i c a t i o n a b s t r a c t c l u s t e r i n gi st h et h i n g si na c c o r d a n c ew i t hc e r t a i na t t r i b u t e s ，t h e t h i n g sg a t h e r e di n t oc a t e g o r i e s ，s ot h a tt h es i m i l a r i t yb e t w e e nt h ec l a s s a ss m a l la sp o s s i b l e ， w i t h i nt h es a m ec a t e g o r yo ft h eg r e a t e s tp o s s i b l e c l u s t e r i n gi sa nu n s u p e r v i s e dl e a r n i n gp r o c e s s ，t h es a m ec l a s s i f i c a t i o n i tist h ef u n d a m e n t a ld is ti n c ti o n ：t h en e e dt ok n o wi na d v a n c et h a t c l a s s i f i c a t i o ni sb a s e do nt h ed a t af e a t u r e s ，a n dc l u s t e r i n gi st of i n d t h i sd a t ac h a r a c t e r i s t i a s ，t h e r e f o r e ，i nm a n ya p p l i c a t i o n s ，a sac l u s t e r a n a l y s i sad a t ap r e t r e a t m e n tp r o c e s si sf u r t h e ra n a l y s i sa n dp r o c e s s i n g d a t ab a s e c l u s t e ra n a l y s i si sa n i m p o r t a n th u m a nb e h a v i o r c l u s t e ra n a l y s i s a l g o r it h md e p e n d so nt h et y p eo fd a t a ，t h ep u r p o s ea n d c l u s t e r a p p li c a t i o n s i nt o d a y sr a p i d l yd e v e l o p i n gd a t am i n i n ga n de x p l o r a t i o n d a t aa n a l y s i s ，c l u s t e ra n a l y s i st e c h n i q u eh a sb e e nw i d e l yu s e di np a t t e r n r e c o g n i t i o na n di m a g ep r o c e s s i n g ，b i o l o g i c a l ，p s y c h o l o g i c a l ，c o m p u t e r v i s i o na n dr e m o t es e n s i n g ，a n do t h e rf i e l d s i np r a c t i c a lp r o b l e m s ，t h e t r a d i t i o n a lt e c h n i q u eo fc l u s t e ra n a l y s i sp r e v a i l i n gi n a d e q u a c i e so ft h e m e i np e r f o r m a n c ei nt h ef o l l o w i n ga r e a s ： c l u s t e r i n gr e s u l t so ft h e s e n s i t i v i t ya n di n i t i a l i z a t i o np a r a m e t e r ss t r o n gd e p e n d e n c e ；d i f f i c u l t i s s u eo ft h ev a li d i t yo ft h ed e f i n i t i o nc l u s t e r i n ga n dr e a s o n a b l ei ti s d i f f i c u l tt od e t e r m i n et h en u m b e ro fc l u s t e r i n g ；d i r e c tp h y s i c a l e x p l a n a tio nc a nb ep o o r i nr e c e n ty e a r s ，t h ed e v e l o p m e n to fn e u r a lp h y s i o l o g ya n da n a t o m yo f c o m p u t e ra i d e db ys e v e r a lh i g h l ya c c u r a t ec a l c u l a t i o no ft h ep r i m a r y v i s u a ls y s t e mm o d e l ，n a m e l yt h ev i s u a ls y s t e mm o d e li n go ft h ev a r i o u s p a r t so fd i f f e r e n tl e v e l s s c a l es p a c et h e o r yi so n eo ft h e m ， i td e s c r i b e s q u a n t i t a t i v e l yc o n n e c t e db yl a t e r a lr e t i n a li m a g ec a u s e db yt h ef u z z y e f f e c t t h r o u g hv i s u a lp r i n c i p l ea n da l g o r it h mc o m b i n i n gs c a l es p a c e ，t h e v i s u a ls y s t e mt ot h es t r u c t u r ew a ss i g n i f i c a n ta s s u m p t i o n sa n ds t a b i li t y o fa s s u m p t i o n s ， u s i n gs c a l es p a c ec l u s t e r i n ga l g o r i t h m ，h a v ed i f f e r e n t l e v e l s o fe f f e c t i v ec l u s t e r i n g m a j o rw o r k ： 1 ， c l u s t e r i n ga l g o r i t h mc o m p a r i s o n t h e r ea r em a n yk i n d so fc l u s t e r i n ga l g o r i t h m ，t h ea p p l i c a t i o nn e e d s t ob ei n v o l v e di nd a t at y p e s ，t h ep u r p o s eo f c l u s t e r i n gs p e c i f i c a p p li c a t i o nr e q u i r e m e n t s a n dt os e l e c tt h e a p p r o p r i a t ec l u s t e r i n g a l g o r i t h m c l u s t e r i n g a l g o r i t h m s c a nb e r o u g h l y d i v i d e di n t ot h e f o l l o w i n gc a t e g o r i e s ：p a r t i t i o nm e t h o d ， h i e r a r c h i c a lm e t h o d s ，t h e 3 山东师范大学硕士学位论文 m e t h o d sb a s e do nt h ed e n s i t y ，g r i d - b a s e dm e t h o d sa n dm o d e l b a s e dm e t h o d s t h e nv a r i o u sc l u s t e r i n ga l g o r i t h m ss p e c i f i cc o m p a r i s o n sd r a w nb e t w e e nt h e p e r f o r m a n c eo fd if f e r e n tm e t h o d so nd if f e r e n t 2 ，t h ea s s u m p tio nt h a tt h es t r u c t u r eo fv is u a ls y s t e m b yi n t r o d u c i n gv i s u a ls y s t e m ，w e b e r sl a w ，t h es t r u c t u r eo ft h ev i s u a l s y s t e mw a ss i g n i f i c a n ta s s u m p t i o n sa n ds t a b i l i t ya s s u m p t i o n sf o rt h en e x t c h a p t e rs c a l es p a c ec l u s t e r i n ga l g o r i t h mt op a v et h ew a y t h es t r u c t u r e o ft h ev i s u a ls y s t e mw a ss i g n i f i c a n ta s s u m p t i o n s ：t h o s en e r v ee e l l s c a u s e dm o r ee x c i t e m e n tt h a nt h es t r u c t u r eo fn e r v ee e l l st h a tc a u s el e s s e x c i t i n gs t r u c t u r ei sm o r ei m p o r t a n t t h es t r u c t u r a l s t a b i li t yo ft h e v i s u a ls y s t e ma s s u m p t i o n s ：t h o s ei nt h el a r g e rs c a l ec a nb eo b s e r v e d w it h i nt h ef r a m e w o r ko ft h es t r u c t u r eo fo b j e c t ss m a ll e rs c a l et h a nt h o s e i nt h er a n g eo f o bj e c t sc a nb eo b s e r v e dt h a tt h es t r u c t u r ei sm o r e i m p o r t a n t 3 ， s c a l es p a c ec l u s t e r i n ga l g o r it h m f i r s ti n t r o d u c e ds c a l es p a c ec o n c e p t ，i n t r o d u c e dr e t i n a lb i o l o g i c a l m o d e l ，t h ev is u a lf r o n t - e n ds y s t e ms e a l e s p a c em o d e l ，t h ef o c u so ns c a l e s p a c ec l u s t e r i n ga l g o r i t h m s c a l es p a c ep r i n c i p l e ： w h e nt h ef u l ls c a l e p a r a m e t e r sh o u r s ， e a c hd a t ap o i n ti sac a t e g o r y ，a n dw h e nl a r g e rs c a l e p a r a m e t e rg r a d u a l l y ，g r a d u a l l ys m a l lc a t e g o r yo fd a t al e v e r a g i n go nt h e l a t e s ta d v a n c e sb e c o m eag e n e r a lc a t e g o r yo fd a t a t h i sc l a s s i f i c a t i o n o ft h er e s u l t sg e n e r a t e db yt h ec o m p o s i t i o no fat r e e ，t h en o d e r e p r e s e n ti n gd i f f e r e n ts c a l ec l u s t e r i n go fc a t e g o r i e s ，t h ef a t h e rn o d e c a t e g o r ye x p r e s s e db yt h es o nr e p r e s e n t e db y t h en o d ec l a s sf r o m l e v e r a g i n go nt h el a t e s ta d v a n c e s t h i sc l u s t e r i n ga l g o r i t h mi sag r a d u a l c l u s t e r i n ga l g o r i t h m ， w h i c hc o n t a i n sas e r i e so fd a t ac l a s s i f i c a t i o n 4 ，t h ee f f e c ti v e n e s so ft h ec l u s t e r i n gp r o b l e m c l u s t e r i n gv a l i d i t yo fc l u s t e ra n a l y s i si sam o r ed i f f i c u l ti s s u e ， w h i c hi n v o l v e st h ea l g o r i t h md a t as t r u c t u r ea n de x p l a i nt h es i g n i f i c a n c e ， s u c ha st h en u m b e ro fd a t ai nt h ec a t e g o r y ， o b t a i n e db yt h ea l g o r i t h m s o ft h i st y p ei st r u e ，w h a tk i n do fm o r eas e r i e so fi s s u e ss u c ha se f f e c t i v e t h r o u g hf o u r se x p l a n a t i o n ，t oj u d g et h ee f f e c t i v e n e s so fc l u s t e r i n g 5 ，i l l u s t r a t e d t h r o u g hn u m e r i c a l s i m u l a t i o n e x p e r i m e n t s t oi l l u s t r a t es c a l e c l u s t e r i n ga l g o r i t h mc a nb ee f f e c t i v ea td i f f e r e n tl e v e l so fc l u s t e r i n g k e yw o r d s ： c l u s t e r i n ga l g o r i t h m ， v i s u a ls y s t e m s ， s c a l es p a c e c l u s t e r i n ga l g o r it h m k e yw o r d s ：t p 3 0 1 6 4 山东师范大学硕士学位论文 1 1 问题的提出 第一章绪论 “物以类聚，人以群分 ，在自然科学和社会科学中，存在着大量的分类问 题。所谓类，通俗地说，就是指相似元素的集合。聚类，即物以类聚，能够帮助 人们更为有效的观察和理解数据。它是人类最原始的精神活动，用于处理他们每 天接收到得的大量信息。将每个信息片作为一个单独的实体进行处理是不可能 的，因此，人们试图将实体( 如对象、个人、事件) 分类，每一类由它所包含的实 体的共同特征来标识。将物理或抽象对象的集合分组成为由类似的对象组成的多 个类的过程被称为聚类。 聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽可能小， 类内相似性尽可能大。聚类是一个无监督的学习过程，它同分类的根本区别在于： 分类是需要事先知道所依据的数据特征，而聚类是要找到这个数据特征，因此， 在很多应用中，聚类分析作为一种数据预处理过程，是进一步分析和处理数据的 基础。例如在商务中，聚类分析能够帮助市场分析人员从客户基本库中发现不同 的客户群，并且用购买模式来刻画不同的客户群的特征。聚类分析也能用于分类 w e b 文档来获得信息。作为数据挖掘的功能，聚类分析可以作为一个获得数据分 布情况、观察每个类的特征和对特定类进一步分析的独立工具。通过聚类，能够 识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。 聚类分析( c l u s t e r i n ga n a l y s i s ) 与分类预测方法明显不同之处在于，后者 学习获取分类预测模型所使用的数据是己知类别归属( c l a s s l a b e l e dd a t a ) ，属 于有监督的学习方法，而聚类分析( 无论是在学习还是在归类预测时) 所分析处 理的数据均是无( 事先确定) 类别归属，类别归属标志在聚类分析处理的数据集中 是不存在的。因此聚类分析属于无监督的学习方法。 聚类分析是一种重要的人类行为。在孩提时代，一个人就可以通过不断改进 下意识的聚类模式来学会如何区分动物和植物。聚类分析既能作为一个独立的工 具来进行数据分析，也可以作为其他算法的预处理步骤。目前，聚类分析已经广 泛地用在许多应用中，如模式识别、数据分析、图像处理、市场研究等。通过聚 类，人们能够识别密集的和稀疏的区域，从而发现全局的分布模式，以及数据属 性之间的有趣的相互关系。 聚类分析算法取决于数据的类型、聚类的目的和应用领域。自二十世纪六十 年代以来，在聚类算法的研究上，国内外的学者投入了大量的精力，并且提出了 山东师范大学硕士学位论文 很多新颖有效的聚类算法。在当今飞速发展的数据采掘和探查性数据分析中，聚 类分析技术已广泛应用于模式识别和图像处理、生物、心理、计算机视觉和遥感 等领域。在实际问题中，传统的聚类分析技术普遍存在的不足之处主要表现在以 下几个方面：聚类结果对初始化参数的敏感性和强依赖性；很难定义聚类的有效 性问题，合理的聚类数目难以确定；直接的物理可解释性较差。 如何降低聚类算法对初始化的敏感度以及如何针对不同的问题域、不同的数 据集寻找最优聚类，并给出合理的物理解释，成为众多学者正致力于研究并解决 的问题。 在我们的日常经验中，我们也体会到眼睛所具有的将物体进行分类并找到它 们之间重要结构的神秘功能。在数据分析中，我们通常以各种手段将数据表示在 图片上( 如直方图、散点图、主成份分量图、由s a m m o n 映射或自组织特征映射所 得到的可视化数据图形) ，然后凭直觉对该图像所传递的信息进行视觉解码。但 这一直觉的视觉处理既无任何理论基础，也不能进行计算操作，因而难以用于机 器视觉以进行自动分类和识别，从而极大地限制了视觉处理强大功能的进一步使 用。 因此，我们需要研究一种更好的聚类方法模拟人类视觉原理，以达到更好的 聚类效果。 1 2 国内外研究现状 随着研究者在聚类技术上的不断改进与创新，许多新颖而高效的聚类算法层 出不穷，针对特定的问题及用户，众多学者也研究出了很多具有代表性的聚类算 法，并广泛的应用于模式识别、生物信息、图像处理以及数据挖掘等领域。 当前聚类算法研究的主流是模糊聚类技术，许多学者在原有算法的基础上加 以改进和发展，因为其更能客观地反映现实世界，从而得到了较为广泛的应用。 如f c m ( f u z z yc m e a n s ) ，最早由d u n n 提出，并由b e z d e k 将之推广，目前已经 在模式识别、图像处理、模糊建模等领域得到了广泛研究与应用，现有的很多模 糊聚类算法的理论基础就是在f c m 基础上的推广和改进，如s c a d 算法、g f c 算 法等等。然而，许多模糊聚类算法的局限性在于聚类前必须需要专家领域知识对 聚类类别数进行估计，一旦类别数的估计不合理，将对最终的聚类效果造成极大 的影响。 自2 0 世纪6 0 年代以来，聚类方法及应用方面的文章大量出现在模式识别和 图像处理等领域。尽管已有算法被广泛应用于众多领域，但它们普遍存在以下缺 陷： ( 1 ) 对初始化参数敏感，最终结果强烈地依赖初始化参数。 6 山东师范大学硕士学位论文 ( 2 ) 难以找到最优聚类，因为通常情况下，最优聚类是一n p 完全的整体优 化问题。 除了这些数学上或算法上的困难外，聚类问题本身还存在着一个更为困难的 问题聚类有效性问题，聚类有效性涉及算法产生的数据结构的意义及解释， 诸如数据是否有类可聚? 数据中存在多少个类? 由算法得到的类是真实的吗? 哪一种划分更有效等，企图在一般框架下回答这些问题显然是不现实的，一方面 是因为聚类数据的结构只有在特定物理背景下才有意义，因而聚类的意义也只能 根据具体的应用背景予以解释，另一方面，聚类的主要目标是帮助人更好地观察 和理解数据，因此，在许多情况下，聚类的最终结果需要人的感知分析来检验。 根据以上两点，可以认为，聚类的意义不能由算法本身来解释，它只能由产 生数据的物理系统的原理和人类感知数据结构的方式来确定。 眼睛是人类感知外部世界的最主要信息，人所感知的外界信息有8 0 来自视 觉，迄今为止人们对眼睛的工作机理的研究也最为深入，获得了很多成果。自从 8 0 年代初，m a r r 提出视觉计算理论的概念后，其视觉计算理论在计算机视觉研 究领域得到了广泛的研究，特别是在计算机图像处理领域取得了令人瞩目的成 就，如计算机视觉的三维感知、运动视觉的建模、检测与估计等。随着生理学和 心理学的发展，以及人们对视觉系统的研究日益深入，可以通过模拟视觉系统的 机理进行聚类分析，从而克服传统聚类分析中存在的一些问题。 近年来，神经生理学的发展和计算机辅助解剖学的研究提出了几个相当精确 的初级视觉系统计算模型，它们分别建模于视觉系统的不同部分的不同层次。尺 度空间理论便是其中之一，它定量地描述由视网膜侧向联接所造成的图像模糊化 效应。 回顾e v e r i t tb 对聚类的定义，可以认为视觉原理在聚类算法中的应用，具 有天然的自适应性，而且所得到的聚类结果也具有更好的可解释性，也为聚类技 术的研究开辟了一个新思路和切入点。 1 3 研究意义 传统的聚类分析方法只强调其对产生数据的物理系统的依赖，而忽略了人类 感知数据结构的方式对聚类分析的影响。可以认为，这二者就聚类算法的构造和 聚类结果的分析而言，具有同等的重要程度。根据这一观点，本文使用了一种基 于视觉前端系统尺度空间模型的聚类算法。由于尺度空间表示并未明显地指出哪 些结构是重要的，进而提出了显著性假设。根据这一假设，利用心理物理学的 w e b e r 定律，就可得到了一个刻画结构重要程度的度量，并将其用于尺度空间聚 类分析。 7 8 山东师范大学硕士学位论文 以这样的方式将描述视觉系统不同层面的研究结果整合起来所形成的聚类 方法不仅克服了传统算法运行中所具有的一些缺陷，而且可用于解决聚类有效性 方面与人类感知方式有关的问题。 本文的中心目的便是表明这一理论为聚类分析提供了一种新颖的生物观点， 并可真正地将聚类置于视觉感知理论的基础之上。 1 4 本文组织 本文组织如下： 第一章绪论，介绍国内外研究现状以及研究意义。 第二章聚类算法简介，介绍聚类算法分类，目前比较流行的各种聚类分析算 法，以及各种算法之间在性能上的比较结果。 第三章介绍视觉系统结构的结构假设，主要对视觉理论、w e b e r 定律、视觉 系统结构显著性假设和稳定性假设进行解释。 第四章介绍尺度空问概念，视网膜的生物模型，视觉前端系统的尺度空间模 型，尺度空间聚类原理，尺度空间聚类算法等。 第五章介绍聚类有效性的问题。 第六章通过尺度空间聚类算法举例进行运用。 第七章总结。 山东师范大学硕士学位论文 2 1 引言 第二章聚类算法简介 聚类和分类这两个概念在一定程度上有着相似性和易混淆性，它们的根本区 别在于：分类需要事先知道所依据的数据特征，而聚类是从数据的分布中发现规 律、找出数据特征。聚类是人类一项最基本的认知活动，它是按照事物的某些属 性特征，将事物分成不同的类的过程，目标是使得类问相似性尽可能小，类内相 似性尽可能大。在很多应用中，聚类分析作为一种数据预处理过程，是进一步分 析和处理数据的基础。通过适当的聚类算法，对事物的属性数据进行预处理，事 物才便于研究，事物的内部规律才可能为人类所掌握。 聚类分析起源于分类学，在古老的分类学中，人们主要依靠经验和专业知识 来实现分类，很少利用数学工具进行定量的分类。随着人类科学技术的发展，对 分类的要求越来越高，以致有时仅凭经验和专业知识难以确切地进行分类，于是 人们逐渐地把数学工具引用到了分类学中，形成了数值分类学，之后又将多元分 析的技术引入到数值分类学形成了聚类分析。 作为多元数理统计分析的一个分支，聚类分析已经被广泛研究了多年，主要 集中在基于样本距离的聚类分析。在机器学习领域，聚类属于无监督学习；在模 式识别领域，聚类也是非监督模式识别的一个重要分支；由于数据挖掘技术是在 数据库，机器学习，数理统计等技术的基础上发展而来，聚类分析也成为数据挖 掘领域中一个非常活跃的研究课题；在图像处理领域，基于模糊聚类的方法在边 缘检测、图像增强、图像压缩、曲线拟合等众多方面的研究同样成为众多学者研 究的课题。 定义2 1 簇( c l u s t e r ) ：一个数据对象的集合。在同一簇中，对象具有相似性， 不同簇中，对象之间是相异的。 定义2 2 聚类分析( c l u s t e r i n ga n a l y s i s ) ：把一个给定的数据对象集合分成不 同的簇，即在空间x 中给定一个有限的取样点集或从数据库中取得有限个例子 的集合， xi n i ：l 。聚类的目标是将数据聚集成类，使得类间的相似性最小，而 类内的相似性尽可能得大。 一个完整的聚类任务，必须遵循以下步骤： 1 ) 特征选择在数据分析中，使信息冗余减少和最小化是主要目标，必 须适当的选择特征，尽可能夺得包含数据分析任务所关注的信息。 2 ) 近邻测度对两个特征向量的“相似”或者“不相似 进行定量测量， 9 山东师范大学硕士学位论文 保证所有选中的特征聚有相同的近邻性，并且没有占支配地位的特征。 3 ) 聚类准则聚类准则以蕴涵在数据集中类的类型为基准，如数据集的 代价函数、数据在高维空间的致密度准则，或者其他规则。 4 ) 聚类算法选择合理的近邻测度和聚类准则，构造特定的聚类算法， 用于揭示数据集的聚类结构。 5 ) 结果验证对聚类算法的得到的聚类结果进行验证，常用逼近检验的 方法验证聚类结果的正确性。 6 ) 结果判定在许多情况下，应用领域的专家必须用其他实验数据和分 析判定聚类结果，最后做出正确的聚类结果判定。 2 2 聚类分析数据类型 数据挖掘的一个重要步骤是数据准备，这包括对选定的数据进行规范化、整 合和预处理等等，这是进行数据挖掘的前提，也同样是聚类算法能正常实施的必 要前提。要对数据对象进行聚类，基于统计方法，其最重要的前提是要计算各个 数据对象之间的距离一即相异度，针对不同的数据类型有不同的相异度计算方 法。许多基于内存的聚类算法常使用以下两种有代表性的数据结构：数据矩阵和 相异度矩阵。 2 2 1 数据矩阵 数据矩阵是一个对象一属性结构。它是由n 个对象组成，例如：人的对象是 利用p 个属性来进行描述的，如：年龄、高度、重量等。数据矩阵采用关系表 形式或n xp 矩阵来表示，如下式所示。 xl1 。x i f x1p x i l 一x i t 一。x i t , x n l 一x 时一x n p 2 2 2 相异度矩阵 相异度矩阵是一个对象一对象结构。它存放所有n 个对象两两之间所形成 1 0 山东师范大学硕士学位论文 的差异。它一般采用n n 矩阵来表示。 其中，d ( i ，j ) g t 示对象i 和对象j 之间的差异( 或不相似程度) 。通常d ( i ，j ) 为一个非负数，当对象i 和对象j 非常或彼此“接近”时，该数据接近0 ，该数 值越大，就表示对象i 和对象j 越不相似。由于有d ( i ，j ) = 叫，i ) 且d ( i ，i ) = o ， 因此就有如下矩阵。 o a ( 2 ，1 ) 0 d ( 3 ，1 ) a ( 3 ，2 ) 0 a ( n ，1 ) a ( n ，2 ) 0 数据矩阵通常又称为双模式矩阵，相异度矩阵则称为是单模式矩阵。因为前 者行和列分别表示不同的实体，而后者行和列则表示的是同一实体。许多聚类算 法都是基于相异度矩阵进行聚类分析的。如果数据是以数据矩阵形式给出的，就 需要先转换为相异度矩阵，然后再利用聚类算法进行处理。 2 2 3 聚类分析数据类型 区间标度变量：一个粗略线性标度的连续变量，典型的例子包括重量、高度， 经度和纬度坐标( 如聚类房屋) 以及大气温度。选用的度量单位将直接影响聚类分 析的结果。假如将高度的度量单位由“米”改为“英寸”，或者将重量的单位由 “千克 改为“斤”可能会产生非常不同的聚类结果。一般而言，所用的度量单 位越小，变量可能的值域就越大，对聚类结果的影响也越大。为了避免对度量单 位选择的依赖，数据应当首先进行标准化。标准化度量值试图给所有的变量相等 的权重。当没有关于数据的先验知识时，这样做很有用。但是在一些应用中用户 可能想给某些变量较大的权重。 二元变量：一个二元变量只有两个状态：0 或l ，其中，o 表示变量不存在 ( 该变量为空) ，而l 表示该变量存在。例如，给出一个描述病人的变量s m o k e r ， 它用来描述病人的抽烟情况，s m o k e r 为1 表示病人抽烟，而s m o k e r 为0 表示 病人不抽烟。如果按照处理区间标度变量一样来处理二元变量，通常会导致错误 的聚类结果，所以必须采用特定的方法来计算其相异度。 标称变量：标称变量是二元变量的一个推广。它可以具有多于两个的状态值。 例如：地图颜色m a p变量就是一个标称变量，它可以表示五种状态，即红、color 绿、蓝、粉红和黄色。 序数型变量：一个离散的序数型变量与一个标称型变量相似，只不过序数型 变量的m 个状态是以有意义的序列排序的。序数型变量在描述无法用客观方法 山东师范大学硕士学位论文 表示的主观质量评估时是非常有用的。例如：专业等级就是一个序数型变量，它 是按照助教、讲师、副教授、教授的顺序进行排列的。一个连续序数型变量看上 去就像一组未知范围的连续数据，但它的相对位置要比它的实际数值有意义得 多。例如，在足球比赛中，一个球队排列名次常常要比它的实际得分更为重要。 序数型变量的数值常常是通过对间隔数值( 变量) 的离散化而获得的，也就是通过 将取值范围划分为有限个区间而得到的。一个序数型变量可以映射为一个秩。如： 若一个序数型变量f 包含m f 个状态，那么这些有序的状态就定义了一个排列1 ， 2 ， m f 。 比例标度型变量：一个比例标度型变量就是在非线性尺度上所获得的正的度 量值，如：指数标度，可以用以下公式近似描述： a e b t 或a e b t 其中，a 和b 为正常数。 2 3 聚类算法分类 聚类算法有很多种，需要根据应用所涉及的数据类型、聚类的目的以及具体 应用要求来选择合适的聚类算法。如果利用聚类分析作为描述性或探索性的工 具，那么就可以使用若干聚类算法对同一个数据集进行处理以观察可能获得的有 关( 数据特征) 描述。 聚类质量的高低通常取决于聚类算法所使用的相似性测量的方法、聚类准则 和实现方式，同时也取决于该算法能否发现部分或全部隐藏的模式。 2 3 1 聚类算法分类 聚类算法大体可以划分为以下几类：划分方法、层次方法、基于密度的方法、 基于网格的方法和基于模型的方法。 1 、划分方法( p a r t i t i o n i n gm e t h o d ) 给定一个包含n 个数据对象或元组的数据库，一个划分方法构建数据的k 个划分，每个划分表示一个聚簇，且k 1 1 。也就是说，它将数据划分为k 个组， 同时满足如下的要求：( i ) 每个组至少包含一个对象；( ii ) 每个对象必须属于 且只属于一个组，同时某些模糊划分技术中第二个要求可以放宽。 给定要构建的划分的数目k ，划分方法首先创建一个初始划分。然后采用一 种迭代的重定位技术，尝试通过对象在划分间移动来该进划分。一个好的划分准 则是：在同一个类中的对象之间尽可能接近或相关，而不同类中的对象尽可能远 1 2 山东师范大学硕士学位论文 离或不同。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上， 绝大多数应用采用以下比较流行的启发式方法： ( 1 ) k 平均法 在该算法中，每个簇用该簇中对象的平均值来表示。 ( 2 ) k 一中心点算法 在该算法中，每个簇用接近聚类中心的一个对象来表示。 这些启发式聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大 规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步 的扩展。 2 、层次方法( h i e r a r c h ic a lm e t h o d ) 层次方法对给定数据对象集合进行层次的分解。根据层次分解是自底向上还 是自顶向下形成，层次聚类的方法可以进一步分为凝聚的和分裂的。凝聚的方法， 也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后相继合并相 近的对象和组，直到所有的组合并成一个( 层次的最上层) ，或者达到一个终止 条件。分裂的方法，也称为自顶向下的方法，一开始将所有对象置于一个簇中。 在迭代的每一步中，一个簇被分解成为更小的簇，直到最终每个对象在单独的一 个簇中，或者达到一个终止条件。 对于聚合聚类算法来讲，根据度量两个子类的相似度时所依据的距离不同， 又可将其分为基于s i n g l e - l i n k ，c o m p l e t e - l i n k 和a v e r a g e l i n k 的聚合聚类。 s i n g l e - l i n k 在这三者中应用最为广泛，它根据两个聚类中相隔最近的两个点之 间的距离来评价这两个类之间的相似程度，而后两者则分别依据两类中数据点之 间的最远距离和平均距离来进行相似度评价。 层次聚类方法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能被 撤消，因此而不能更正错误的决定。改进层次方法的聚类质量的一个有希望的方 向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。有两种方法可以改 进层次聚类的结果： ( 1 ) 在每层划分中，仔细分析对象间的“联接”，例如c u r e 和c h a m e l e o n 中的做法。 ( 2 ) 综合层次凝聚和迭代的重定位方法。首先采用自底向上的层次算法， 然后用迭代的重定位来改进结果，如b i r c h 中的做法。 3 、基于密度的方法( d e n s i t y 喃a s e dm e t h o d ) 基于密度的聚类方法是为了发现任意形状的聚类结果。其主要思想是：只要 临近区域的密度超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据 点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来 山东师 菡大学硕士学位论文 过滤“噪声 孤立点数据，发现任意形状的簇。 d b s c a n 是一个典型的基于密度的聚类方法，它将聚类定义为一组密度连接 的点集，然后通过不断生长足够高密度的区域来进行聚类。d e n c l u e 则根据数据 点在属性空间中的密度来进行聚类。从本质上讲，d e n c l u e 是基于密度的聚类算 法与基于网格的预处理的结合，它受目标数据的维度影响