（计算机应用技术专业论文）基于免疫遗传算法和粒子群算法的聚类研究.pdf

摘要 随着信息科学技术的发展，人们越来越倾向于选择用计算机来统计和管理数据， 数据库的规模也随之不断地扩大。当人们积累了大量的商业数据以后，如何从汪洋 大海般的数据中发现有价值的信息成为一个急需解决的重要问题。由此数据挖掘技 术应运而生，它是目前数据库和信息决策领域最前沿的研究方向之一。聚类分析作 为数据挖掘的一个重要分支，是通过分析数据的相似性把大型数据集合划分成组， 使得同一个组罩面的数据彼此最为相似，而不同组中的数据彼此相异。聚类是发现 有用信息的一种有效手段。目前，聚类分析已经广泛地应用于模式识别，数据分析， 图像处理以及市场研究等领域。 目前在文献中存在大量的聚类算法。算法的选择取决于数据的类型、聚类的目的 和应用。本文探讨了基于免疫遗传算法和基于粒子群算法的c - 一均值聚类方法。所做 的主要工作如下： 1 用免疫遗传算法完成聚类工作。首先，分析现有遗传算法的优缺点，将免疫机 制引入遗传算法，用来克服了标准遗传算法的早熟现象；其次，将c 一均值算法和免 疫遗传算法有机结合，形成一种混合算法；最后，根据聚类问题的实际情况设计遗 传选择、交叉和变异算子，使得混合算法更快、更有效地收敛到全局最优解。 2 用改进后的粒子群算法实现聚类。首先，分析现有粒子群算法的优缺点；其次， 将局部搜索能力强的c _ 一均值算法和基于遗传算法的交叉、变异操作同时结合到粒子 群算法中；最后，通过适当调节，发挥各自的优点。既提高了p s o 算法的局部搜索 能力，又因为增加了种群的多样性，防止了算法的早熟。 3 将改进后的算法选择一些数据集用m a t l a b 编程做聚类实验，并与其他算法结 果进行对比，分析试验结果。 关键词：聚类算法；c 均值算法；免疫遗传算法；免疫遗传c 均值算法；粒子群算法； 粒子群聚类算法 a bs t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y , p e o p l eh a v ei n c l i n e dt o c o l l e c t i n ga n do r g a n i z i n ga l lk i n d so fd a t ab yc o m p u t e r s ，t h e nt h es i z eo fd a t ah a s e x p e n d e da sw e l l w h e np e o p l eh a v ea c c u m u l a t e dm a s s i v ea m o u n to f b u s i n e s sd a t a , h o w t of i n dt h ev a l u a b l ei n f o r m a t i o ni nt h ev a s to c e a n l i k ed a t ah a v eb e c o m ea nu r g e n tn e e dt o b es o l v e d f o rt h i sd a t am i n i n gt e c h n i q u e sh a v ee m e r g e d ，w h i c hi so n eo ft h em o s t c u t t i n g - e d g er e s e a r c ho ft h ed a t a b a s ea n di n f o r m a t i o nd e c i s i o n m a k i n g c l u s t e ra n a l y s i sa s a l li m p o r t a n tb r a n c ho fd a t am i n i n gi st h ea n a l y s i so fd a t a ss i m i l a r i t y , a n dd i v i d e dt h e l a r g ed a t as e t si n t og r o u p s ，i nw h i c ht h ed a t ai n s i d et h es a m eg r o u pw a sm o s ts i m i l a rt o e a c ho t h e ra n dt h ed a t ai nd i f f e r e n tg r o u p sw a sd i f f e rf r o me a c ho t h e r c l u s t e r i n gi sa n e f f e c t i v em e a n so ff i n d i n gu s e f u li n f o r m a t i o n a tp r e s e n t ，c l u s t e ra n a l y s i sh a sb e e nw i d e l y u s e di np a t t e r nr e c o g n i t i o n ，d a t aa n a l y s i s ，i m a g ep r o c e s s i n g ，m a r k e tr e s e a r c ha n dm a n y o t h e rf i e l d s t h e r ei sal a r g en u m b e ro fc l u s t e r i n ga l g o r i t h m si nt h el i t e r a t u r e t h ec h o i c eo f a l g o r i t 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 da p p l i c a t i o n so fc l u s t e r i n g t h i s p a p e rd i s c u s s e dc m e a n sc l u s t e r i n gm e t h o dw h i c hb a s e do nt h ei m m u n eg e n e t i ca l g o r i t h m a n dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h ms e p a r a t e l y f o l l o w i n gi st h em a i nw o r kh a s b e e nd o n e ： 1 c o m p l e m e n t e dc l u s t e r i n ga l g o r i t h mw i t hi m m u n eg e n e t i ca l g o r i t h m f i r s t ，a n a l y z e d t h es t r e n g t h sa n dw e a k n e s s e so ft h ee x i s t i n gg e n e t i ca l g o r i t h m ，t h ei m m u n em e c h a n i s m w a si n t r o d u c e di n t ot h es t a n d a r d g e n e t i ca l g o r i t h m t oo v e r c o m et h ep r e m a t u r e p h e n o m e n o n ；s e c o n d ，t h ec - m e a n sa l g o r i t h ma n dt h ei m m u n eg e n e t i ca l g o r i t h mw e r e c o m b i n e dt of o r mah y b r i da l g o r i t h m ；f i n a l l y , b a s e do nt h e a c t u a ls i t u a t i o no ft h e c l u s t e r i n gp r o b l e md e s i g n e dt h eg e n e t i cs e l e c t i o n ，c r o s s o v e ra n dm u t a t i o no p e r a t o r s ，m a d e t h eh y b r i da l g o r i t h mc o n v e r g et ot h e g l o b a lo p t i m a ls o l u t i o nm u c hf a s t e ra n dm o r e e f f i c i e n t l y 2 c l u s t e r i n gw i t ht h ei m p r o v e dp a r t i c l es w a r ma l g o r i t h m f i r s t ，t h ea d v a n t a g e sa n d d i s a d v a n t a g e so ft h ee x i s t i n gp a r t i c l es w a r mo p t i m i z a t i o nw e r ea n a l y z e d ；s e c o n d ，t h e i l c - m e a n sa l g o r i t h mw h i c hh a ss t r o n gl o c a ls e a r c ha b i l i t ya n dt h eg e n e t i ca l g o r i t h m - b a s e d c r o s s o v e ra n dm u t a t i o no p e r a t i o n sw e r em i x e di n t ot h ep a r t i c l es w a r ma l g o r i t h m ；f i n a l l y , t h e mh a v ep l a y e dt h e i ra d v a n t a g e sr e s p e c t i v e l yt h r o u g ha p p r o p r i a t er e g u l a t i o n n o to n l y t h ep s oa l g o r i t h m sa b i l i t yo fl o c a ls e a r c hi si m p r o v e d ，b u ta l s ot h ed i v e r s i t yo ft h e p o p u l a t i o nw a si n c r e a s e d ，a tl a s ta c h i e v e dt h ep u r p o s eo fp r e v e n tp r e m a t u r ep r o b l e mo ft h e a l g o r i t h m 3 s e l e c t e ds o m ed a t as e t sa n dt h ec l u s t e r i n ge x p e r i m e n t sw e r ei m p l e m e n t e dt h r o u g h m a t l a bp r o g r a m m i n gb yt h ei m p r o v e da l g o r i t h m s ，a n dr e s u l t sw e r ec o m p a r e dw i t h o t h e ra l g o r i t h m s ，a n da n a l y z e dt h er e s u l to ft h ee x p e r i m e n t 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 s ；cm e a nc l u s t e r ；i m m u n eg e n e t i ca l g o r i t h m ；i m m u n e g e n e t i ccm e a nc l u s t e ra l g o r i t h m ；p a r t i c l es w a r mo p t i m a la l g o r i t h m i i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名： 翻许 日期：为，o 年多月媚 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密冈。 ( 请在以上相应方框内打“) 作者签名： 导师签名： 初埤 i 写丁 日期：加，口年月2e 1 日期：二d 年c ) 月z 日 1 1 研究的背景和意义 第一章绪论 随着信息技术的发展和计算机的广泛使用，人们越来越倾向于选择计算机上来统计 和管理数据，这样数据的规模也随之不断增大。当人们积累了大量的数据之后，譬如商 品交易数据、客户服务数据和销售记录数据等，逐渐发现这些数据中有可能蕴含着大量 有价值的商业信息。就目前被广泛应用的数据库管理系统而言，虽然它能够实现高效的 将数据的录入、查询和统计等功能，但却不能发现这些数据中可能存在的关系或规则， 更不可能根据现有的数据去预测未来的发展趋势，这使得我们处在了一个“数据丰富， 知识贫乏”【l 】的尴尬境界。因此，从汪洋大海般的数据中挖掘出潜藏的有价值的商业信息 成为大家的一个共同的难题。例如：超市经理想知道哪些商品经常被同时购买，从而通 过改变商品摆放的位置来增加销售量；保险公司的促销员想知道怎样的客户会更愿意购 买保险，或者说他们一般都有哪些共同点，从而使得以后的工作更有针对性；医生则希 望知道他所研究的某种疾病的患者一般都具有什么样的特征，从而为预防或者治愈这种 疾病提供一些帮助。数据挖掘技术( d a t am i n i n g ，简称d m ) 就是在类似于这样的各种应 用需求的驱动下诞生了。 数据挖掘中包含了许多重要的技术，聚类分析便是其中的一个。因此，聚类分析也 是分析数据并从中发现有价值信息的有效手段之一。在人类的章年时代，大家就已经学 会了如何通过修改聚类模式来学习了，比如如何区分动物和植物，或者鸭和鹅等。目前， 聚类分析已经被广泛地应用在包括模式识别、市场研究、图像处理和数据分析等许多应 用领域【1 1 。在生物学中，聚类分析能够根据植物的生长特性及体态特征等信息来推导出 其所属科目，从而更容易得获得对该物种的本质认识。在商业中，聚类分析能够帮助市 场销售人员根据购买信息从产品中发现有销售前途的产品或者发现不同的顾客群体，为 以后的生产和销售给出指导性的意见。在电子商务上，聚类分析可以帮助店主对浏览相 似网页的客户进行聚类，分别分析这些网站和客户的所具有的共同特征，从而为店主提 高销售业绩和为客户提供更好的服务带来帮助。在i n t e m e t 应用上，聚类分析可以通过 搜集相似内容的文档来对缺少的信息进行修复。 聚类分析还可以用于离群点检n ( o u t l i e rd e t e c t i o n ) 。离群点又称孤立点，是指那些貌 似不属于任何一个簇的点。因为离群点一般都会对聚类效果有或大或小的影响，所以在 一般的聚类分析中总是希望能够去掉它们。但是在实际应用当中，正是这些离群点可能 比那些簇内点存在着更高的实用价值。目前离群点检测的主要应用有各种诈骗行为的监 控和检测。 聚类分析作为数据挖掘的一项功能也可以作为其他算法的预处理步骤，比如分类、 特征化以及属性子集选择等。首先将待处理的数据作一次聚类，然后再用后续的算法对 检测到的簇、特征或者选择的属性进行进一步的处理。在有的算法中，这样的预处理可 以极大地简化后续算法或者提高它的执行效率。比如首先用聚类分析获得数据的分布情 况，接着通过观察每个簇的特征最后可以决定对哪些特定的数据需要做进一步的分析和 处理。 由于数据库中收集了大量的数据，这给数据聚类技术的提供了良好的发展机会。目 前聚类分析主要对包括数据挖掘、空间数据库技术、机器学习、统计学、市场营销和生 物学等研究领域都有较明显的贡献【。聚类分析已经成为数据挖掘研究领域中一个非常 活跃的研究方向。 1 2 国内外研究现状 1 2 1 数据挖掘的研究现状 数据挖掘( d a t am i n i n g ，也称数据开采) 的实质就是从数据库中发现知识( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) ，因此也被常常简称为k d d 或者d m 。该词首次出现于1 9 8 9 年8 月在美国底特律召开的第1 1 届人工智能联合会议的专题讨论会上。随后在2 0 世纪9 0 年代初期几乎每年都举行了有关知识发现和数据挖掘的专题讨论会。会议聚集了来自各 个领域的应用开发者和研究人员，集中讨论了知识表示、知识运用、海量数据分析算法 和数据统计等问题。1 9 9 5 年在加拿大召开了第一届知识发现和数据挖掘的国际性学术会 议，从此这种专题讨论会被提升为国际性的学术大会( i n t e r n a t i o n a lc o n f e r e n c eo nd a t a m i n i n g & k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) ， “数据挖掘”一词也流行开来。 “数据挖掘”是对“知识发现”概念的深化，它们都是数据库技术与机器学习、人工智 能技术相结和的产物。知识发现会议也随着从事数据挖掘领域研究的人员越来越多，将 工作的重心逐渐从方法发现转向了系统的实际应用，并且开始注重多种学科的相互渗透 以及多种技术和策略的相互继承。此外，含有这一主题的地区性国际大会也不断召开。 2 其中1 9 9 9 年，在北京召开的亚太地区的第三届p a k d d 会议空前热烈，会议共收到1 5 8 篇论文【2 1 。 知识发现的专题或专刊也纷纷在信息处理、数据库、知识工程和人工智能等领域的 国际性学术刊物开辟了领域，其中比较著名的有( ( a c m 数据库系统汇刊、( ( i e e e 知识 与数据工程汇刊、( ( a c m 杂志、智能信息系统国际杂志、信息系统、v l d b 杂 志以及数据与知识工程等。也有不少的有关知识发现的电子出版物在网络上开始 发行，k n o w l e d g ed i s c o v e r yn u g g e t ( h t t p ：w w w k d n u g g e t s c o m s u b s c r i b e h t m l ) 就是其中最 为权威的是半月刊之一。还有在网上开辟了许多自由论坛，如中文的数据挖掘研究院 ( h t t p ：w w w d m r e s e a r c h n e t ) 、d me m a i lc l u b 等。此外，知识发现和数据挖掘被计算机 网络、并行计算和信息工程等领域的国际学刊、学会列为专题或者专刊进行讨论。 自从提出数据挖掘方法之后，人们开始认识到数据的真正价值，即蕴藏在数据中的 有用信息。国外已有许多个人或者专门的工作组从事着数据挖掘领域的相关研究工作。 其中为大家多熟知的有加拿大s i m o nf r a s t e r 大学的，国际知识发现研究的知名学者h a n j i a w e i 教授所领导的课题组，以及r a g g r a w a l 领导的i b ma l m a d e n 实验室等。他们 为数据挖掘的发展做出了巨大的贡献，为该领域的发展奠定了深厚的基础。 众多的商业机构和研究人员被数据挖掘技术所表现出的广阔应用前景所深深吸引。 一批应用在经济、商业、金融和管理等领域的数据挖掘系统已经被开发出来，并取得了 应用性的成果。其中，世界上比较著名的产品有i n t e l l i g e n tm i n e r ，w a r e h o u s es t d i o ， e n t e r p r i s em i n e r ，c l e m e n t i n e ，s e e 5 ，s e t m i n e r 等。它们分别是由i b m ，s y b a s e ，s a s ， s p s s ，r u l e q u e s tr e s e a r c h ，s g i 这些世界知名的公司所开发的数据挖掘系统。在 h t t p ：w w w d a t a m i n i n g l a b c o m 站上也提供了许多数据挖掘系统和工具的性能测试报 告。2 0 世纪9 0 年代以来数据挖掘技术的发展的总体状况可以用上面这些系统来说明， 因为它们代表了模式识别、机器学习、数据库、统计学、专家系统、科学发现和数据分 析等许多领域的最新研究成果。但总体来说，这些系统在系统效率、适用性等方面还不 尽人意，目前基本上还停留在实验室阶段。 虽然国内对数据挖掘的研究起步较晚，但是在1 9 9 3 年国家自然科学基金开始首次 支持对该领域项目研究的前后，就已经有相当一部分的单位和研究人员从事着数据挖掘 方面的研究工作了。比如对数据挖掘的研究处于比较前沿位置的有北京系统工程研究所 和南京大学计算机软件新技术国家重点实验室。他们分别对知识发现的实际应用和数据 挖掘系统进行了较深入研究【3 】；数据立方体代数也被北京大学纳入研究范围，这对数据 挖掘的发展也有理论指导的作用；另外，数据挖掘方面的研究也纷纷在国内诸如复旦大 学、华中科技大学、中国科技大学、浙江大学等知名的大学都开展开了。 自从“数据挖掘”的概念在1 9 9 5 年提出以来，在这1 5 年内得到了很大发展。人们也 逐渐认识到，只有有效地从数据中提取信息，及时地从信息中发现知识，数据才能为人 类的战略发展和思维决策提供服务，也才能更好更快的推动人类的发展。也只有当数据 成为与能源、物质一样重要的资源的时候我们才步入真j 下的信息时代【2 】。 1 2 2 聚类的研究现状 聚类分析作为数据挖掘中的一项重要技术，已经进行了较深入的研究，但主要还是 集中在基于距离的聚类分析。基于c 均值，c 中心点和其他一些算法的聚类分析工具已 经被加入到许多统计分析软件包或系统中，例如s - p l u s ，s p s s 以及s a s 1 1 。在数据挖掘 领域，研究的工作已经主要集中在怎样为大型数据库提供有效的聚类分析方法。活跃的 研究课题主要集中在聚类方法的可伸缩性，对复杂形状和类型数据聚类的有效性，高纬 数据的聚类，以及针对大型数据库中混合数据和分类数据的聚类方法的研究上。 目前的文献中也存在着大量的其他聚类算法，这些聚类算法的选取由聚类的目的和 应用以及所操作的数据类型所决定。如果聚类分析是被用作探查或描述的工具，来发现 数据中可能包含的有用信息，那么可以对同样的数据同时尝试多种算法，这样得到的结 果可能会更好。大体上，将现有的主要聚类算法按照一种大家都比较认可的划分方法【1 】 可以分为：基于划分的方法( p a r t i t i o n i n gm e t h o d s ) 、基于层次的方法( h i e r a r c h i c a l m e t h o d s ) 、基于密度的方法( d e n s i t y - b a s e dm e t h o d s ) 、基于网格的方法( g r i d b a s e dm e t h o d s ) 和基于模型的方法( m o d e l b a s e dm e t h o d s ) 。近年来，随着人工智能技术的发展，也出现 了许多用人工智能中的优化方法来做聚类的例子，如：运用遗传算法，基于群智能思想 的蚁群算法和粒子群算法，以及支持向量机的方法等方法来聚类。 1 3 本文所做的工作 本文主要从以下三个方面来完成基于免疫遗传算法和粒子群算法的聚类研究工作： ( 1 ) 用免疫遗传算法完成聚类设计 首先，分析现有遗传算法的优缺点，在充分学习人工免疫机制的基础上将其引 入遗传算法，用来克服了标准遗传算法的早熟现象；其次，将c 一均值算法和免疫遗 4 传算法有机结合，形成一种混合算法；最后，根据聚类问题的实际情况设计遗传选 择、交叉和变异算子，使得混合算法更快、更有效地收敛到全局最优解。 ( 2 ) 用改进后的粒子群算法完成聚类设计 首先，分析现有粒子群算法的优缺点；其次，将局部搜索能力强的c 一均值算法 和基于遗传算法的交叉、变异操作同时结合到粒子群算法中；最后，通过适当调节， 发挥各自的优点。既提高了p s o 算法的局部搜索能力，又因为加入了交叉、变异操 作达到了增加种群的多样性，防止了算法早熟的目的。 ( 3 ) 完成聚类算法的实现 在该部分主要是将改进后的算法选择一些数据集用m a t l a b 编程来实现，并与其他 论文中提出的算法结果进行对比，并分析实验结果，评价所做的工作。 1 4 本文的内容组织 本文主要对基于免疫遗传算法和基于粒子群算法的两类聚类算法分别进行了研究， 其组成如下： 第一章主要介绍了本课题的研究背景及意义，以及数据挖掘和数据挖掘中聚类的 国内外研究现状。 第二章主要介绍了与聚类相关的一些知识，包括聚类的概念、评价标准、常见的 聚类算法，以及这些方法的比较，最后阐述了聚类的作用和意义。 第三章首先介绍了遗传算法的概念，包括遗传算法的基本概念、操作步骤等，并 分析了遗传算法的优缺点，紧接着介绍了人工免疫系统的概念、结构及应用，最后提 出了一种用人工免疫机制改进的遗传算法一免疫遗传算法，用该算法实现聚类，并 且用实验证明了算法的可行性。 第四章介绍了粒子群算法的基本概念、操作步骤以及研究现状等，提出了一种改 进的粒子群算法。最后分析并评价所作的算法结果。 第五章主要总结并且客观的评价了本文所作的工作，并且展望了在本文基础可以 进行的下一步工作。 2 1 聚类概述 2 1 1 聚类的概念 第二童聚类 聚类( c l u s t e r i n g ) ，通俗的讲就是将物理或抽象的集合分成相似对象簇的过程。而 这里的簇是数据对象的集合，并且这些集合必须满足以下两个条件：在同一个簇中的对 象彼此相似，而与其他簇中的对象相异【i 】。 虽然聚类和分类有些类似，但是两者还是有不同之处：分类是一种有监督的学习方 式，即首先需要用大量的训练数据对分类模式进行训练，然后再用训练好的模式对剩余 的数据进行分组；而聚类是一种无监督的学习，即它不需要训练数据和训练模式，因此 也会省去收集和标记大量的训练数据集或模式所需要付出的高昂代价，因此聚类在一定 程度上优于分类。 但是为什么既有聚类又分类昵? 原因很简单，看下面的一个情景：假设有一箩筐水 果，里面有梨、苹果、桃子、李子、桔子共5 种，如何将它们分成五组各自不同的水果 呢? 人们通常的做法就是先从箩筐总取出一部分水果，将它们分为五组，然后将剩下的 水果一个一个地放入各自应该属于的组中。即，首先基于数据的相似性( 比如使用聚类 的方法) 把数据集合中的一部分数据划分成组，然后给各个组指定各自的标号，然后将 剩下的数据再分配到自己所属的组中。 2 1 2 聚类的步骤 聚类的基本步骤 4 1 可以用下面的图2 1 来说明： 回馈循环 图2 1 聚类的步骤 6 首先是输入，聚类分析中的输入就是待聚类的数据集合，紧接着就是对输入的数据 集合进行预处理，即根据聚类分析对数据类型的要求，通过属性约简等方式形成样本表 示，然后根据具体的相似度度量准则计算样本i 、日j 的相似性，之后根据数据之间的相似性 将数据集合进行分组。一般来说，为了使得同组中的数据对象更加相似，而与其它组的 数据对象更加相异，聚类分析是一个循序渐进的过程，需要反复不断地对数据间的相似 性进行比较，来改善不同的分组情况。最后，返回聚类分析的最终结果不同的簇。 2 2 聚类的相似度度量 随着聚类技术的发展和应用越来越广泛，人们越来越发现，评价数据对象问的相似 性和评价数据集合聚类结果的好坏成为聚类中的关键问题。j 下是根据这两个关键问题， 现在出现了各种各样的聚类算法。这一小节主要讨论聚类的相似度的度量方法，2 3 节 中讨论聚类算法好坏的评价准则，在2 4 节中将讨论常用的聚类算法。 2 2 1 聚类分析中的数据类型 在讨论聚类分析相似度的度量方法之前，我们先了解下在聚类分析中通常所选择的 数据结构类型。 1 数据矩阵( d a t am a t r i x ，或称为对象一变量结构) 假设有m 个数据对象，每个数据对象又有n 个属性，那么要表示这m 个数据对象 的话就可以用一个m x n 矩阵来表示，即数据矩阵。这个矩阵的每一列可以表示数据对 象的一个属性，而每一行可以表示一个具体的数据对象。例如，人脸识别的数据可以由 鼻子、眼睛、耳朵、眉毛、嘴巴等组成。 x i j ： x u ： x , n j 其中表示第i 个对象的第j 个属性的值。 2 相异度矩阵( d i s s i m i l a r i t ym a t r i x ，或称为对象一对象结构) 假设要计算两个均有n 个属性的数据对象之间的相似性，这个问题同样可以用矩阵 理论来解决，即用一个n x n 的三角矩阵表示其相似性，如下： 7 n 川 ； ； 一 l l i；h ； 0 d ( x 2 ，x 1 ) 0 d ( x 3 ，x 1 ) d ( x 3 ，x 2 ) 0 d ( x 。，x i ) d ( x 。，x 2 ) 0 数据对象x ，和一的相似性可以用d ( 置，x j ) 表示，通常d ( 置，) 为非负数，其值 越小，则表明数据对象置和一越相似，反之，其值越大，则表明数据对象置和x j 越 相异。且容易得到：j ( t ，置) = d ( z ，一) ，d ( z ，置) = 0 。 相异度矩阵中的具体d ( 墨，) 值通常可以用距离公式计算得到。具体计算方法见 下节的介绍。 2 2 2 样本间距离的计算 假设有两个数据对象x ，和一，它们分别都有n 个属性。x i 和x 可以用数学语言 表示为：五= ( 置，x i n ) 和彳j = ( t ”，x j n ) ，那么，这两个数据对象问的距 离d ( 置，x ) 可以用多种方法计算得到，具体选哪种都是随意的，但是现在最常用的距 离度量是欧氏距离( 即欧几里德距离) 和曼哈顿距离。本文也列举出了一些其它的常用度 量方法【5 1 ，其具体计算公式如下： ( 1 ) 曼哈顿距离 d ( x ，彳，) = z ”x 护一x 少l ( r = 1 ，2 ，3 n ) r = l 其中r 表示样本的第r 个属性，下面的公式中r 具有相同的意思和取值。 ( 2 ) 欧几里得距离 d ( x ；，x ，) ：( d ( 瓦一) z ) ； ( 3 ) 马氏距离 d ( x f ，工，) 2 = ( x f x ，) r v 叫( x f - x ，) 其中v j 为样本协方差的逆矩阵，t 表示求矩阵的转置。 ( 4 ) 切氏距离 ( 2 1 ) ( 2 2 ) ( 2 3 ) d ( 置，z ) = 1 ，d i 义。一x 少l ( 5 ) 斜交距离 蚍圳= 瘊私圳c k - - x j r ) r r i 在数据标准化处理后，r , i 为置与之间的相关系数。 ( 6 ) 兰氏距离 慨= 喜掣 2 3 评价标准 ( 2 4 ) ( 2 5 ) ( 2 6 ) 随着聚类分析的应用越来越广泛，在不同领域的人们也对聚类提出了各种各样的要 求，因此也就有了各种各样的评价标准。这也使得聚类分析成为数据挖掘技术中一个富 有挑战性的研究领域。根据目前存在的各项潜在应用，对聚类的典型要求( 即评价准则) 主要有以下9 个方面【1 】： ( 1 ) 可解释性和可用性 首先，所有的工程应用都是为人类服务的，聚类也不例外，它的结果最终还是要面 向用户的，因此所有的聚类结果应该是人类可理解和可应用的。 ( 2 ) 能够处理噪声数据 现实世界的数据库当中的数据并不是我们想象的那样完整和一致，而是常常包含了 一些未知的、空缺的或者错误的数据，这样的数据我们称之为噪声数据。因此一个好的 聚类算法应该能够处理噪声数据对它的影响。 ( 3 ) 能够处理不同的数据类型 随着聚类分析的应用扩大到各种不同的领域，因此来自不同领域的不同数据对象类 型需要被处理，这就对聚类算法提出了一种新的要求。 ( 4 ) 能处理高维数据 假设气象局要对一年中的天气情况进行聚类分析，而影响天气的包含许多因素，比 如温度、湿度、紫外线强度、风速、可见度等等，这就对聚类算法提出了一种新的要求 处理高维数据的能力。虽然上面的例子可能不是很恰当，但是类似的这样的应用随 处可见，因此对于不同应用领域的聚类算法而言，不能只要求其能聚类低维的数据对象， 9 而且要能够处理高维的数据对象。 ( 5 ) 能够发现任意形状的簇 正如前面相似度度量一节中介绍的一样，在目前的算法中绝大部分是采用基于欧氏 距离和曼哈顿距离的度量方法来进行相似性判断的。这种度量方法的一个明显缺陷就是 适合于发现球状簇，而在现实中有些类型可能具有规则的形状，如正方形、椭圆或者球 形，而更一般地情况是类型的形状可能是任意的。因此我们需要设计出能够发现任意形 状簇的聚类算法。 ( 6 ) 可伸缩性 假如一个聚类算法对于较小的数据对象集合有较好的聚类效果，而当遇到稍微大点 的数据对象集合时要么计算时间变的非常长，要么聚类的结果很不理想，那么我们称这 个聚类算法具有不好的伸缩性。因此，伸缩性是指算法的效果不会随着数据对象集合的 大小而有太大的浮动，一般来说，如果算法的计算时间随着数据序的大小呈线性变化的 话，我们称其具有较好的伸缩性。 ( 7 ) 输入的参数越少越好 在许多聚类算法执行之前会要求用户输入一些参数，比如期望聚类能够得到的簇数 目或者一些控制参数。毫无疑问，这些参数对聚类结果是有极大影响的，一旦用户输入 了错误的参数将会导致不可预料的聚类结果，这也就加重了用户的负担，因此，一个较 好的聚类算法应该是具有较少或者没有输入参数。 ( 8 ) 记录的输入顺序与结果无关 在有些聚类算法中，如果将同一个数据对象的集合以不同的顺序输入将会得到不同 的聚类结果，对于这样的算法我们称之为对输入数据的顺序是敏感的。但是在实际的应 用当中，谁也无法保证每次聚类之前的数据都以最好的顺序输入，这也就不能保证得到 最好的聚类结果，因此，我们需要设计出对输入数据的顺序没要求的聚类算法。 ( 9 ) 基于约束的聚类 在实际应用中，许多聚类是需要在人的指导下进行的，而不同人会有不同的要求， 从而就有了不同的约束条件。因此一个好的聚类算法应该能够满足不同的约束条件，并 且在这些约束条件下都要有较好的聚类效果。 2 4 常用的聚类算法 随着聚类分析的广泛使用，目前的文献中存在着大量的聚类算法。因为这些方法可 1 0 能互相重叠，使得一个算法同时具有几种特征，所以很难对它们进行一个明确的划分。 不过用现在大家比较认同的一种划分方法i l l 可以将聚类算法大致分为：划分的方法 ( p a r t i t i o n i n gm e t h o d s ) 、层次的方法( h i e r a r c h i c a lm e t h o d s ) 、密度的方法( d e n s i t y - b a s e d m e t h o d s ) 、模型的方法( m o d e l - b a s e dm e t h o d s ) 、网格的方法( g r i d - b a s e dm e t h o d s ) 这么五 种。本节除了介绍这几种算法之间的关系和对比之外，将重点介绍与本课题相关的基于 划分的方法。 2 4 1 常见的聚类算法间的关系 常见的聚类算法之间的关系【6 】，可以用下图表示： 图2 2 常见聚类算法问的关系 2 4 2 几种常用的聚类算法的比较 基于上述分析，本节主要对传统的常用的聚类算法按照2 3 节提到的聚类算法评 价标准中的六个方面( 算法的效率、对噪声的敏感性、对数据输入顺序的敏感性、 发现聚类的形状、高维性和可伸缩性) 进行比较 7 1 ，结果如表2 1 所示。 表2 1 常用聚类算法的比较 算法的对噪卢对数据输入顺发现聚类高维性可伸 效率的敏感序的敏感性的形状缩性 性 c - m e a n s较高敏感不太敏感球形好较好 c l a r a n s较低 不敏感非常敏感凸形或球形一般好 b i r c h 高般不太敏感凸形或球形好较差 c u r e 较高不敏感敏感任意形状好较差 d b s c a n 一般不敏感敏感任意形状一般较好 c o b w e b较低一般敏感 任意形状 好 较好 s t i n g高不敏感不敏感任意形状好好 s o m 一般敏感敏感任意形状好较好 由表2 1 可以看出，传统的这些聚类算法中的大多算法都只是在某些方面能够接 近或者达到聚类算法的评价标准，却没有哪一种算法在各个方面都表现良好。但是 聚类算法的评价标准是针对不同的应用领域提出的，所以我们完全可以根据具体领 域的要求选择恰当的聚类算法，而较少的考虑对该领域的应用影响不大的标准，或 者我们还可以结合多种聚类算法，使它们互补自己的缺点，来达到我们的要求。 另外，通过大量的应用实践表明如果数据对象集合的数据量规模中等或者中等 以下，数据分布又比较匀称的话，基于划分的方法就能很好的解决问题。而且划分 方法具有通用、容易理解和容易实施的优点。下一小节中我们将重点介绍基于划分 的方法。 2 4 3 聚类算法中的划分方法 对于r “空间中的基于划分的聚类问题可以用具体的数学语言描述为：对于r “ 中给定的n 个点x 。，x ：，x n ，按照相似性将它们分成k 个( k 事先给定) 集合 s l ，s 2 ，s k 且这k 各集合满足： ( 1 ) s i 0 ，i = l ，2 ，k ； ( 2 ) s ir 、s j = ( b ，i j 2 1 ，2 ，k ；i j ； ( 3 ) g ks 。= x i , x 2 , x n ) 。 1 2 基于划分的聚类方法的通俗描述为：对于给定的含有n 个数据对象的数据集合， 要求将其分为k ( k - - n ) 个小集合，每个小集合就代表着一个簇，这些簇之间满足以下 关系： ( 1 ) 每个小集合至少包含一个数据对象； ( 2 ) 每个数据对象仅且只能属于一个集合。 在该方法中最常用也是最著名的算法是k 均值算法和k 中心点算法( 也称c 均 值和c 中心点算法) ，下面对其进行分别介绍。 1 k 均值算法 k 均值算法在满足划分方法的基础上，还要将k 作为输入参数，以确定需 要聚类的具体簇数目，然后按照以下的步骤来进行聚类： 首先，在待聚类的数据对象集合中随机的选取k 个数据对象作为这k 个簇 的初始化均值或中心。然后根据每个对象与这个k 个簇中心的距离，将剩下的 每个对象分别指派到相似度最高的簇中，最后计算每个簇的新均值。这个过程不 断重复迭代，直到准则函数收敛或者类中心不再变化为止。平方误差准则就是其 中的一个较常用的准则函数，具体的定义见( 2 7 ) 式。 e ：壹 p - c i 2 f = l p g c ( 2 7 ) ( 2 7 ) 式中p 代表数据对象集合中的具体的数据对象，而q 是簇c f 的均值 ( q 和p 都是多维的) ，e 则代表数据对象集合中所有数据对象的平方误差和， 这个式子的意思就是，对于簇中每个数据对象，求数据对象到其所在簇中心的距 离的平方和。这样便达到了聚类的最初定义簇中数据尽可能的紧凑( 即相似) 簇问数据对象尽可能的独立( 即相异) 。 若用具体的算法描述k 均值聚类算法，具体的操作步骤如下： ( 1 ) 任选k 个初始簇中心c l ，c 2 ，g k ； ( 2 ) 将数据对象集合 x ) 中的所有的数据对象按最小距离原则分配给某个簇 中心c ； ( 3 ) 用公式c t k 毒荟x ，计算新的簇中心c i ( i = 1 ，2 ，k ) ，其中n i 为第i 个聚类 域s 。包含的数据对象个数； ( 4 ) 若c i c ；( i = 1 ，2 ，k ) 或者e s ( s 为任意给定的一个很小的值) ，转步骤 ( 2 ) ；否则算法收敛，计算结束。 2 k 中心点算法 假设有在一个数据对象集合中的一个数据对象的值与其它所有的数据对象的值 相差非常的大( 称为离群点或者孤立点) ，那么k 均值算法的结果将很大的会被该 点影响，因为k 均值算法是以数据对象的均值作为簇中心的，这也是k 均值算法的 一个致命缺点。如果再使用平方误差函数作为收敛准则那么更是使聚类结果雪上加 霜。为了降低k 均值算法对初值的敏感性，又提出了k 中心点算法一用每个簇中 的某个实际数据对象来代表该簇的中心而不是用该簇的均值。其余算法操作步骤和 k 均值算法类似。当然准则函数也需要修改一下，这早我们用绝对误差作为度量准 则，其定义见( 2 8 ) 式： e ：圭| p - - 0 i 1 2 i = 1 p g ( 2 8 ) ( 2 8 ) 式中，p 代表簇c f 中的任意的一个数据对象，0 i 代表了簇g 中的簇中心，即 代表对象。e 则是数据对象集合中所有数据对象与所在簇中心间的绝对误差之和。 2 5 聚类的应用 聚类分析作为数据挖掘的一项功能也可以作为其他算法的预处理步骤