（计算机应用技术专业论文）基于群体智能的聚类算法研究.pdf

摘要 数据挖掘是目前数据库和信息处理技术领域的前沿研究课题，被公认为是最 具发展前景的关键技术之一。数据挖掘汇集了机器学习、数据库、模式识别、人 工智能和统计学等学科的内容，是一门新兴的交叉学科。 聚类分析是数据挖掘技术中的一个重要研究课题，是一种用于数据划分或分 组处理的重要手段。聚类分析作为数据挖掘系统中的一个模块，既可以成为一个 单独的工具以发现数据库中数据分布的深层信息，也可以作为其他数据挖掘算法 的个预处理步骤。因此，研究如何提高聚类算法的性能具有重要的意义。 群体智能利用群体优势，在没有集中控制，不提供全局模型的前提下，为寻 找复杂问题解决方案提供了新的思路，是“简单智能体通过合作表现出智能行为 的特性”。作为群体智能的典型实现模式，模拟生物蚁群智能寻优的蚁群算法和模 拟鸟群运动模式的粒子群优化算法正在受到学术界的广泛关注。 本文的主要研究工作包括以下几个方面： ( 1 ) 分析了聚类的定义及其数据类型，研究了聚类分析中的主要算法。 ( 2 ) 研究了群体智能的基本概念、原理和主要应用等。 ( 3 ) 分析了基本蚁群算法和l f 聚类分析模型的基本原理及其优缺点，针对 l f 模型中一些不足，提出了一些改进方法，其中包括群体相似度和概率转换函数 的定义，参数的自适应调整等。通过实验证明，改进算法较好地解决了收敛速度 和聚类质量之间的矛盾。 ( 4 ) 分析了基本粒子群优化算法的基本原理及其研究现状，提出了一种带变 异操作的粒子群聚类算法，该算法解决了基本粒子群算法当中存在的早熟收敛和 收敛较慢的问题，实验结果表明，算法具有很好的全局收敛性和较快的收敛速度。 关键词：数据挖掘；聚类分析；群体智能；蚁群优化算法；粒子群优化算法 a bs t r a c t d a t am i n i n gi sas u p e r i o ra r e ai nt h ed a t a b a s ea n di n f o r m a t i o nt e c h n o l o g y ，a n di s c o m m o n l y c o n s i d e r e da so n eo ft h e k e yt e c h n o l o g y w i t hw i l d d e v e l o p i n g p e r s p e c t i v e d a t am i n i n gr e l a t e st om a c h i n el e a r n i n g ，d a t a b a s e ，p a t t e r nr e c o g n i t i o n ，a i a n ds t a t i s t i c st e c h n o l o g ye t c i ti san e wi n t e r d i s c i p l i n e c l u s t e r i n gi sa ni m p o r t a n tr e s e a r c hf i e l di nd a t am i n i n g ，a n da l s oa ni m p o r t a n t m e t h o di nd a t ap a r t i t i o no rd a t ag r o u p i n g c l u s t e ra n a l y s i sa sam o d u l ei nt h es y s t e r m o fd a t am i n i n gc a nb eu s e dn o to n l ya sas e p a r a t et e c h n i q u et od i s c o v e rt h ei n f o r m a t i o n a b o u td a t ad i s t r i b u t i o n ，b u ta l s oa st h e p r e p r o c e s s i n g o fo t h e rd a t a m i n i n g o p e r a t i o n s t h e r e f o r ei ti sv e r ym e a n i n g f u lt or e s e a r c hh o w t oi m p r o v et h ep e r f o r m a n c e o fc l u s t e r i n ga l g o r i t h m s i n t e l l i g e n tu s eo fc o l l e c t i v ee d g eg r o u p s ，i nt h ea b s e n c eo fc e n t r a l i z e dc o n t r o l ，a p r e r e q u i s i t ef o rt h eo v e r a l lm o d e l i no r d e r t of i n ds o l u t i o n st oc o m p l e xp r o b l e m sw i t h an e ww a yo ft h i n k i n g ，i sa “c h a r a c t e r i s t i c so fn ow i s d o mm a i ns m a r ts h o w ni n t e l l i g e n t b e h a v i o r b y t h em a i nc o o p e r a t i o n s m a r ta st h et y p i c a lm o d e so ft h em a i n g r o u p s ，i n t e l l i g e n ts i m u l a t i o no fb i o l o g i c a l a n tc o l o n ya l g o r i t h mo p t i m i z a t i o na n d s i m u l a t i o ne x e r c i s eh a b i t so ft h ep s oa l g o r i t h mm o d e li s b e i n gw i d e l ya c a d e m i a c o n c e r n t h em a i nr e s e a r c ho ft h i sp a p e ri sa sf o l l o w s ： ( 1 ) d e s c r i p t i o no fc l u s t e r i n ga n a l y s i s t h ed e f i n i t i o n ，d a t at y p e ，p r i m a r ya l g o r i t h s a r er e v i e w e d ( 2 ) i n v e s t i g a t e dt h eb a s i cc o n c e p to fs w a r mi n t e l l i g e n c e ，a n di t sp r i n c i p l ea n d m a i na p p l i c a t i o n sa n ds oo n ( 3 ) t h eb a s i ca n tc o l o n ya l g o r i t h ma n dl fm o d e la r ei n t r o d u c e d i ta n a l y z e st h e i r a d v a n t a g e sa n dd i s a d v a n t a g e s a i m i n ga tt h ed r a w b a c k so fl fm o d e la ni m p r o v e dl f a l g o r i t h m i s p r e s e n t e d t h e d e f i n i t i o n so fs w a r m s i m i l a r i t y a n d p r o b a b i l i t y t r a n s f o r m a t i o nf u n c t i o na r e s i m p l i f i e d t h ep a r a m e t e r s a r ea d j u s t e da d a p t i v e l y t h e e x p e r i m e n t a lr e s u l t ss h o wt h a t t h ec o n t r a d i c t i o nb e t w e e nc o n v e r g e n c es p e e da n d c l u s t e r i n gr e s u l ti sr e s o l v e di nt h i si m p r o v e da l g o r i t h m ( 4 ) t h ep a r t i c l e s w a r m o p t i m i z a t i o na l g o r i t h m i si n t r o d u c e d t h ec l u s t e r i n g i i a l g o r i t h m b a s e do n p a r t i c l e s w a r m o p t i m i z a t i o na l g o r i t h m w i t hm u t a t i o ni s p r o p o s e d t h ep r o b l e m so fp r e m a t u r ec o n v e r g e n c ea n dc o n v e r g e n c es p e e di nb a s i c p 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 mi sr e s o l v e d 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 t t h ea l g o r i t h mn o to n l ya v o i d sl o c a lo p t i m a ，b u ta l s oi n c r e a s e st h ec o n v e r g e n c es p e e d k e yw o r d s ：d a t am i n i n g ；c l u s t e r i n ga n a l y s i s ；s w a r mi n t e l l i g e n c e ；a n tc o l o n y o p t i m i z a t i o na l g o r i t h m s ；p 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 m s i i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名： 多7 稼 j 日期：2 0f 6 年6 月2 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ) 作者虢s 】凉 导师签名：、罗歹 日期：如一年1 5 1 月上日 日期：2 - 1 年b 月乞日 1 1 研究的背景和意义 第一章绪论弟一早z 百t 匕 近年来，随着科学技术的飞速发展，社会取得了极大的进步。与此同时，各 个领域中都产生了大量的数据，面对不断增加的数据，人们已经不仅仅满足于数 据库的查询功能，于是提出了深层次问题：能不能从数据中提取信息或者知识为 决策服务。于是，提出了数据挖掘t2 ( d a t am i l 3 in g ，d m ) 技术来解决这一难题。 聚类分析。6 1 是数据挖掘中的一个很活跃的研究领域。与分类不同，聚类的目 的是在没有任何先验知识的前提下，根据数据之间的相似性将它们聚合成不同的 簇，使得相同簇中的对象相似性尽可能大，不同簇间的对象相似性尽可能小。作 为一种强有力的信息处理方法，聚类分析在众多工程领域都扮演着重要角色，其 中包括数据挖掘、图像处理、模式识别及信号压缩等，其基本算法在诸如社会学、 医学、地理学、生命学等学科领域当中都有不俗的表现。聚类分析既可以作为独 立的数据挖掘工具，以此来获得数据的分布状况；也可以作为其他数据挖掘算法 ( 如特征分析和分类等) 的预处理步骤。因此研究如何提高聚类算法的性能具有 重要的意义。 群体智能, ( s w a r mi n t e l l i g e n c e ，s i ) 盯9 1 的概念源于2 0 世纪8 0 年代，研究人员通 过模拟蜜蜂、蚂蚁、大雁等自然界生物群体行为，提出了一些用于解决计算机传 统问题和实际应用问题的智能计算或优化方法，即群体智能。它是受到自然界生 物群体所表现出的智能现象的启发而提出的一种人工智能模式。目前，越来越多 的学者和研究人员陆续加入到群体智能的研究和探索队伍当中，使得群体智能逐 渐成为一个重要的、前景广阔的研究领域。 由于数据集往往呈现高维、多样的特点，从现有文献来看，仍然没有任何一 种聚类算法具有普适性。聚类分析过程中待聚类对象和领域知识本身表现形式多 样，而且将其用于解决实际问题时往往受到各种约束条件的制约，这就需要根据 各自应用领域对算法提出的要求和领域特点来选择聚类算法。将群体智能理论用 于聚类分析时，会继承生物系统良好的处理机制和特性；具备良好的自组织性； 对处理对象有很好的适应能力；具有一定的智能特性，这样可以获得一定的智能 行为能力；生物系统复杂多变的特点，使得处理目标也同样具备多样性；生物系 统客观存在于大自然中，便于我们去观察和分析，所有具有良好的开放性。 通过以上分析，进行聚类分析时，我们可以采用群体智能的方法来对聚类过 程进行优化处理，这样，不仅能够得到更有效、高质量的聚类分析结果，同时也 完善了群体智能理论，使之更加成熟，以便取得更好的实际应用效果。 1 2 数据挖掘概述 1 2 1 数据挖掘的发展背景 随着经济的发展和社会的进步，无论是科学研究还是社会生活的各个领域中 都积累了大量的数据。数据库技术的出现帮助我们实现了数据的录入、查询、统 计计算等简单功能，不但减少了数据存储冗余，实现了数据共享，还可以保障数 据安全，但它却无法从数据中提取其间已经存在的联系和规则。数据的迅速增加 与数据分析方法相对滞后之间的矛盾日益突出。负责从海量数据中提取知识的数 据挖掘技术正是在这种背景下应运而生的。 数据挖掘技术诞生于2 0 世纪8 0 年代后期，在2 1 世纪不断繁荣。数据挖掘是 数据库技术和人工智能中机器学习技术相结合的产物，它是用数据库提供的技术 来管理数据，用机器学习提供的技术来分析数据，自动发现隐含在大量数据中的 有价值的信息。数据挖掘是信息技术最有发展前途的交叉学科之一，它涉及了数 据库和数据仓库技术、机器学习、模式识别、统计学、高性能计算、神经网络、 图像与信号处理等多个领域，集中探讨如何能够更高效地、准确地从大型数据库 中发现知识。将这些知识从数据库中挖掘出来以后可以用在信息管理、过程控制、 查询处理、生物工程以及决策支持等诸多方面。 1 2 2 数据挖掘的研究现状 数据挖掘通俗地讲就是从数据库中发现知识。1 9 8 9 年8 月，第十一届国际人 工智能联合学术会议在美国底特律召开，在这次会议上首次提出了从数据库中发 现知识( k d d ，k n o w l e d g ed i s e o v e r yd a t a b a s e ) 一词。1 9 8 9 年到1 9 9 4 年的这随 后几年举行了四次k d d 和d m 专题讨论会，聚集了来自包括数据库、机器学习、 人工智能等各个研究领域的学者和应用开发人员，他们集中讨论了数据统计、海 量数据分析算法、知识表示、知识运用等问题。l9 9 5 年，该会议被提升为国际性 学术大会。随后“数据挖掘 开始流行。随着更多研究人员的加入，k d d 会议研 究重点也逐渐从单纯的方法提出转向更为复杂的实际系统的应用，从实验原型走 向商品化阶段，强调多种挖掘方法和技术的集成，以及多种学科的相互渗透。数 据挖掘方法的提出，让人们能够探究蕴藏在数据中的信息和知识，从而能够真正 认识到数据的潜在价值。国外己有很多专门工作组，从事数据挖掘领域的研究。 他们提出了一大批性能良好的数据挖掘算法，为该领域的发展奠定了深厚的理论 基础，促进了数据挖掘算法在诸多领域中的应用。数据挖掘技术应用前景广阔， 因此吸引了众多的研究人员和商业机构投入到这项研究当中，开发出了很多各种 各样的数据挖掘系统，并在经济生活、金融监管、企业管理和商业等领域都取得 了不错的应用性成果。数据挖掘是目前国际上数据库和信息决策的最前沿研究方 向之一，引起了学术界和工业界的广泛关注。 与国外相比，国内虽然对数据挖掘的研究起步稍晚，始于2 0 世纪9 0 年代中 期。不过目前已有相当一部分人员和单位从事数据挖掘方面的研究。到了9 0 年代 2 后期，初步形成了知识发现和数据挖掘的基本框架。北京大学、中国科技大学、 南京大学、华中科技大学、吉林大学、上海交通大学、复旦大学、浙江大学和中 科院数学研究所等国内高校以及科研院所都开展了数据挖掘及其相关方面的研 究。 “数据挖掘”的概念自从l9 9 5 年提出以来，得到了大幅度的发展。研究重点 也由单纯的方法发现转向具体的实际应用，并重点关注多种方法和技术的集成， 以及多学科问的相互渗透。我们只有从众多复杂数据中及时地、有效地发现知识， 数据才能和能源一样成为一种可贵的资源，到那时，才意味着信息时代的真正到 来。 1 3 聚类分析在数据挖掘中的应用 聚类分析可以作为一个单独的数据分析工具从而获得数据的分布状况，主要 应用在生物种群划分、目标顾客定位、业绩评估等方面。数据完成聚类操作之后， 可以获得满足数据分布特点的一些簇，通过观察其中每一个簇的特点，以便为下 一步分析处理做准备。如在客户关系管理系统中，聚类分析可以帮助企业的市场 分析人员从客户基本库中萃取消费行为模式，实现对客户进行动态区分，从而实 现企业经营的最佳化。 聚类分析也可以作为其它算法的预处理步骤。譬如作为特征分析、属性子集 选择以及分类算法的预处理步骤，或者将聚类结果用于进一步关联分析。 聚类分析还可以完成离群点检测。在某些特定应用中离群点本身可能比普通 情况更值得注意。离群点检测的应用主要包括电子商务中犯罪活动的监控以及信 用卡欺诈检测等。例如，在电子商务活动中出现的异常数据，应该作为的一种网 络欺诈行为值得引起注意。 1 4 聚类分析的研究现状 聚类分析研究有很长的历史，几十年来，其重要性及与其他研究方向的交叉特 性得到人们的肯定。聚类是数据挖掘、模式识别等研究领域中的一个非常活跃的 研究课题，在识别数据的内在结构方面具有极其重要的作用。聚类主要应用于机 器学习中的图像分割和机器视觉，模式识别中的聚类算法主要用于语音识别和字 符识别，图像处理中聚类主要用于图像压缩处理和信息检索。聚类的另一个重要 应用领域是数据挖掘( 如聚类可伸缩性、各种复杂形状类的识别、高维聚类等) 、 时空数据库应用( 如地理信息系统等) 、序列和异类数据分析等。此外，聚类分 析还常常应用于统计科学。值得关注的是，聚类分析在市场营销、生物学、心理 学、考古学以及地理学等研究领域也都发挥着重要作用。 到目前为止，传统的聚类分析方法可以分为以下几类：( 1 ) 划分方法，代表算 法有k m e a n s t l o - l2 1 、f c m 1 3 1 等；( 2 ) 层次方法，代表算法有b i r c h 1 4 】、c u r e 等； ( 3 ) 基于密度的方法，代表算法有d b s c a n l ”】、o p t i c s1 1 6 】等；( 4 ) 基于模型的 方法，通常有统计学方法和神经网络方法等；( 5 ) 基于网格的方法，代表算法有 s t i n g 【川j 、c l i q u e l 1 等。 以上提到的都是一些经典的聚类算法，这些方法在很多领域已经得到了成功的 应用。但是由于每一种方法都存在缺陷，例如k m e a n s 算法虽然对大型数据集具有 高效的聚类能力，但是也存在一些不足：容易陷入局部最优，适合数值型数据聚 类，只适用于凸型簇。另外，考虑到实际问题的复杂性和数据的多样性，使得无 论哪一种聚类方法都只能在某些方面表现突出。近年来，随着机器学习、人工智 能、模式识别和数据挖掘等相关领域中传统方法的不断发展以及各种新方法和新 技术的涌现，数据挖掘中的聚类分析方法得到了长足的发展。大致可以分为以下 几个方向：基于群体智能的聚类方法：基于粒度的聚类方法：基于模糊的聚类方 法以及多种聚类方法的融合。 1 5 本文的主要内容及组织结构 1 5 1 本文的主要内容 本文主要从以下四个方面对基于群体智能的聚类算法进行了研究： ( 1 ) 数据挖掘中聚类算法的研究：分析各类算法的优缺点，考察它们在不同 的领域针对不同的数据集，算法所体现出来的收敛性、鲁棒性和准确性。 ( 2 ) 蚁群聚类算法的研究：分析基本蚁群聚类( b a s i cm o d e l ，b m ) 模型和l f 算法所存在的缺陷，找到恰当的切入点，进一步完善蚁群聚类算法，解决l f 算法 收敛速度和聚类质量之间的矛盾。 ( 3 ) 粒子群优化算法的研究：在理解基本p s o 算法的基础之上，总结国内外 的一些研究成果，将变异机制和自适应机制引入到基本粒子群优化算法当中，对 k m e a n s 聚类算法进行优化，以解决k m e a n s 算法的早熟收敛和收敛速度过慢， 正确率偏低等问题，从而提高聚类的速度和效率。 ( 4 ) 算法的实现：以u c i 中的标准算例为测试对象，在理论上证明提出算法 的可行性后，采用v i s u a lc + + 6 0 为编程工具、a c c e s s2 0 0 0 关系数据库格式，编 程实现提出的新算法，用实验数据检验算法的有效性并与已有典型算法进行比较。 1 5 2 本文的结构 第一章阐述了本文的研究意义和背景，介绍了数据挖掘和聚类分析的国内外 研究现状，最后对本文的主要研究内容进行了介绍。 第二章介绍了聚类分析的基本概念，给出了衡量聚类算法好坏的一般标准， 然后对聚类分析过程中经常遇到的一些数据类型，重点介绍了五种常用的聚类分 析方法，并对这些方法的各方面性能做了比较。 第三章介绍了群体智能的基本概念，分析了群体智能的基本特点，重点描述 了群体智能算法包含的两种算法模式，即蚁群优化算法、蚁群聚类算法和粒子群 优化算法。 4 第四章介绍了基本蚁群算法的原理，分析了其优缺点，简单介绍了针对该算 法的一些改进策略；重点分析了基本蚁群聚类模型和l f 聚类分析模型的优缺点， 针对l f 模型的一些不足，对其提出了一些改进方法，通过实验证明，改进算法采 用了优化的概率转换函数以及数据对象放置策略，加快了聚类速度，有效改善了 聚类质量，从而较好地解决了收敛速度和聚类质量之间的矛盾。 第五章介绍了基本粒子群优化算法的算法原理，分析了算法当中的参数设置 问题，给出了算法的基本步骤；提出了一种带变异操作的粒子群聚类模型，从聚 类准则函数的选择、编码方案、适应度函数的设计、权重的非线性变化以及粒子 的变异操作这几个方面分析了模型的设计思想，并且给出了算法的具体描述；最 后通过实验证明该算法在收敛速度和j 下确率上都有了大幅提升。 第六章总结了本文的研究工作，阐明其难点和创新点，并提出进一步研究的 方向。 2 1 聚类概述 第二章聚类分析 聚类( c l u s t e r i n g ) 是一种常见的数据分析工具，它源于许多研究领域，包 括数据挖掘、统计学、生物学和机器学习。简单地说，聚类就是将物理或抽象对 象的集合分成相似的对象类的过程。这里，我们把数据对象的集合称之为簇，同 一个簇中对象之间具有高度的相似度，而不同簇中的对象则高度相异。以下给出 聚类的严格数学描述： 假如存在一个对象集合e ，将c 定义为e 的一个非空子集， 即cce ，且c f 2 j 聚类就是要使集合c l ，c ：，c 。满足以下两个条件的： ( 1 ) c luc 2u uc k = e ( 2 ) c fnc j a ，对于任意i ， 由此可见，集合e 中的每个对象必定属于某一个类而且最多只属于一个类。 聚类分析的应用非常广泛，已经涉及到我们社会生活的各个领域，其中包括 客户关系管理、图像处理、电子商务、生物种群划分等。在经济领域，市场分析 人员可以通过聚类操作将客户数据库中的客户划分成不同的客户群，并且用某种 购买模式来刻画不同客户群的特征，以此来制定相应的销售策略。在生物学中， 聚类能用来对基因序列进行分类，从而完成对种群的划分。在i n t e r n e t 的应用中， 聚类能够用于对w e b 上的文档进行分类，以发现有用信息。 2 2 聚类面临的挑战 在聚类算法的研究中，聚类算法的可伸缩性、算法的复杂性、高维聚类分析 技术以及针对大型数据库中混合数值和分类数据的聚类方法已经成为聚类分析研 究中最活跃的研究课题。在某些特定领域中的应用对聚类算法提出了各自特殊的 要求。具体如下： ( 1 ) 处理不同类型属性的能力：现实数据复杂多样的特点要求聚类算法必须 能够处理各种类型的数据。其中不仅包括最常用的数值型数据，还包括其他复杂 类型的数据，例如：序数型、布尔型、枚举型以及混合型等。 ( 2 ) 可伸缩性：随着数据量的不断增大，必然要求聚类算法能够处理上百万 条甚至包含更多对象的大规模数据库，这就要求算法的时间复杂度不能太高。值 得注意的是，当算法无法处理这些海量数据时，通常会采用抽样的方法去解决， 随之带来的便是聚类结果有一定程度的偏差，这是我们不希望看到的。 6 ( 3 ) 输入参数对领域知识的弱依赖性：许多聚类算法当中参数的设置往往是 不确定的，例如在k m e a n s 算法中，期望的簇的数目k 值在聚类前需要由用户 确定。参数通常很难确定，很多参数的取值往往需要通过实验获得。然而聚类结 果对于输入参数又十分敏感。这不仅增加了算法的复杂度，给用户带来负担，也 使得聚类的质量难以控制。 ( 4 ) 可以发现任意形状聚类：欧氏距离被作为大多数聚类算法的距离度量方 法，采用这种度量方法的聚类算法只能发现球状簇。可是，现实数据库中的数据 分布可能是多样的，因此要求算法必须能够发现像凸形、凹形簇等各种任意形状 的簇。 ( 5 ) 处理带噪声数据的能力：现实世界中的大多数数据库都存在数据不完整、 字段值缺损的情况，有些甚至含有很多异常数据和错误信息。这样就给聚类算法 提出了新的挑战：如何在不降低聚类质量的前提下，处理好这些“噪声”数据。 ( 6 ) 处理高维数据的能力：数据库或者数据仓库中数据对象的属性通常是多 维的。许多聚类算法擅长处理只涉及两到三维的低维数据。人类很难直观地判断 高维数据聚类效果的好坏，所以高维数据聚类是现在聚类算法研究的一个重要方 面。 ( 7 ) 增量聚类和输入记录的次序不敏感：数据库的更新是非常频繁的，当遇 到数据库更新时，聚类算法如果不能将新插入的数据合并到已有的聚类结构中去， 而是需要重新进行聚类，这样会增加了大量的重复性工作。而还有一些聚类算法 对同一个数据集合，当对象的顺序输入有差别时，得到的结果大相径庭。这是我 们不希望看到的。 ( 8 ) 结果的可解释性和可用性：所有的聚类结果都需要呈现给用户，因此， 聚类结果应该是可以解释的、易于理解的并且可用的。 ( 9 ) 增加限制条件后的聚类分析能力：实际应用问题通常存在一些限制条件， 聚类算法必须要在充分考虑到这些约束条件的前提下，有比较好聚类效果。 2 3 聚类分析中的数据结构和数据类型 2 3 1 聚类分析中的数据结构 ( 1 ) 数据矩阵 数据矩阵是一个对象一属性结构，是一张关系表的形式，对象的属性对应关系 表中的列，数据对象对应关系表中的元祖。则具有m 个属性的刀个对象可以看成 如下刀聊的矩阵。 7 五，z l m x | fx i m x n f x n m ( 2 ) 相异度矩阵 相异度矩阵是一个对象一对象结构。采用挖y l 维的矩阵来存储n 个对象相互之 问的相异度。 0 d ( 2 ，1 ) 0 d ( 3 ，1 ) d ( 3 ，2 ) a ( n ，1 ) d ( n ，2 ) 其中d ( f ，) 是对象f 和对象之间的相异度，通常为非负数，且c l ( i ，) = d ( j ，f ) ， d ( i ，矿= 0 。二者越相似，则d ( i ，) 越接近于0 ，反之d ( i ，j ) 则越大。 2 3 2 聚类分析中的数据类型 现实世界数据是复杂的、多样的，因此将这些数据做聚类分析时，所采用的 数据类型也是多种多样的。对于这些不同的变量类型，对象间的相异度有着不同 的度量方法。以下列出了几种常见的数据类型以及它们的度量方法： ( 1 ) 区间标度变量 区间标度变量即我们通常所说的数值型变量，是最常见的数据类型。如人们 的体重和身高，气温、价格、速度等这些都属于区间标度变量。聚类分析的结果 受变量度量单位的影响较大。一般情况下，采用的单位越小，变量的值就越大， 值域变化范围就越大，对聚类结果的影响也就越大。因此，为了尽量减小对度量 单位选择的依赖，在计算相似性之前应当对数据首先进行标准化处理。 给定一个数据集，其中包含刀个对象，每个对象具有所维属性。 平均绝对偏差s ，定义为： s ，= 吉b 一加，l ( 2 1 ) 其中，h 表示的是第f 个数据对象在属性厂上的取值，m ，表示的是所有对象 在属性厂上的平均值，即聊，= 亡h 。 o f = l 标准度量值z ，定义为： ； t ； o 0 ； 7 一x 萨一m f 乃2 专产 ( 2 2 ) 对于离群点，平均绝对偏差s f 比标准差仃，具有更好的适用性。在计算平均绝 对偏差时，没有取度量值与均值偏差( 即x i f - m ，i ) 的平方，因此，离群点的影响 被降低。 我们通常采用对象间的距离来评价属性的相似性。设有刀维向量x i 和0 ，常 用的距离度量方法包括以下几种： 欧氏距离： 曼哈顿距离： d ( x ，, x j ) = 忙- - x j i i = 。m x p x ，2 l k = l x 庸一x 业j 厂。研 1 肼 ii ( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 ) 二元变量 包括两种状态：0 或者1 ，其中0 表示该变量不出现，1 表示该变量出现。 二元变量又分为对称的和不对称的。 表2 1 二元变量的相依表 如果二元变量的两个状态的权重相同，则二元变量是对称的。两个对象间 的相异度采用如下公式来度量： pj lo c l ( i ，) = 二二= 一 ( 2 6 ) 。 g + ，+ s + ， 如果二元变量的两个状态的权重不同，则二元变量是不对称的。两个对象 间的相异度采用如下公式来度量： a ( i ，) ：旦 q + r + s ( 3 ) 序数型变量 9 ( 2 7 ) 肚 x一 腑 x 。心 = 、j ， xx ： 离 l 七巳足、，b 氏sw0 k nm，氏明 序数型变量分为离散的序数型变量和连续的序数型变量。离散的序数型变 量类似于分类变量，其处理比较简单，而对于连续的序数型变量，值的相对顺 序是必要的，实际的大小则不重要，如职称( 正教授、副教授、讲师、助教) 。 在计算相异度时，为了使每个变量的权重相同，需要把它们的值域映射到 o o ，1 0 上；然后采用距离的度量方法进行相异度的计算。 ( 4 ) 标称变量 将二元变量推广到多元就是标称变量，它可以具有多个无序的状态值。例 如，两个对象f 和，之间的相异度可以根据不匹配率来计算： d ( i ，j ) = 坐 ( 2 8 ) p 其中，m 是匹配数，即对象f 和，中匹配的属性个数，p 是全部属性个数。 ( 5 ) 比例标度型变量 比例标度变量是在非线性的刻度取正的变量值。如放射性元素的衰变。 2 4 聚类分析中的主要算法 2 4 1 划分方法 给定n 个对象或数据元组的数据库，划分方法就是将这，z 个对象划分成k 个 簇，七n 。使得每一个簇至少包含一个数据对象；每个数据对象必须只属于一个 簇。划分聚类算法的基本原理如图2 1 所示。划分方法中k 需要事先定好，并且适 用于发现球状簇。典型算法有：k m e a n s 算法、k m e d o i d s 算法、c l a r a n s 算法等。 图2 1 划分聚类算法原理框图 l o 2 4 2 层次方法 层次聚类算法将数据对象组成一棵聚类树。它可以分为凝聚的和分裂的。凝聚 的方法采用自底向上的策略，首先将每个对象作为单独的一簇，然后逐渐合并这 些原子簇，直到所有对象都在一个簇中，或者达到某个终止条件为止。分裂的方 法采用自顶向下的策略，首先将所有数据对象归于一类，通过每一步迭代中，将 这些簇不断地分裂成更小的簇，直到每个对象单独成类，或者达到某个终止条件。 层次方法不需要事先确定类的数目，但是算法运算量大，比较适用于处理小样本 数据，其中最大缺陷在于：不可逆性，即一旦一个步骤( 合并或者分裂) 完成， 就不能被撤销。典型的层次聚类算法有：b i r c h 、c u r e 、r o c k 等聚类算法。下 面描述了数据集合 a , b ，c ，d ，e ) 分别采用凝聚聚类和分裂聚类法进行聚类的处理过 程： 4 3 2 l 0 分裂 图2 2 凝聚和分裂层次聚类 凝聚 o 1 2 3 4 2 4 3 基于密度的方法 基于距离的聚类算法只能发现球状簇，而基于密度的方法由于没有采用各种 距离来度量相异度，所以可以用来发现任意形状的簇以及过滤噪声和孤立点。其 核心思想是：只要邻近区域中密度大于一个阀值，就继续聚类。代表算法有： d b s c a n 算法、o p t i c s 算法、d e n c l u e 算法等。 2 4 4 基于模型的方法 基于模型的聚类方法中，首先为每个类设定一个模型，并试图寻找给定数据 和某数学模型之间的最佳拟合。基于模型的方法主要有两类：统计学方法( 如 c o b w e b ) 和神经网络方法( 如s o m ) 。 2 4 5 基于网格的方法 基于网格的聚类方法使用一种多分辨率的网格数据结构。它将样本空间量化 为有限数目的单元，形成一个网格结构，所有聚类操作都在网格结构上进行。其 优点是处理速度快，处理时i 刚不受数据规模的影响，仅依赖于量化空间中每一维 的单元数目。代表算法有：s t i n g 算法、w a v e c l u s t e r 算法、c l i q u e 算法。 除了上述五大类方法以外，在各种文献中还提出了大量的聚类方法。如在聚 类算法中引入遗传算法的选择、交叉、变异算子、模糊聚类方法以及与各种新技 术相结合的聚类方法等。 2 4 6 聚类算法比较 下面对以上提到的一些较常用的聚类算法的性能从对数据输入顺序的敏感 性、发现聚类的形状、对“噪声 的敏感性、高维性、可伸缩性和执行效率六个 方面进行比较，结果如表2 2 所示： 表2 2 聚类算法比较 对数据输入顺发现聚类对“噪声” 序的敏感性 的形状 的敏感性 高维性可伸缩性执行效率 k m e a n s 不太敏感球形敏感一般较好一般 c l a r a n s 非常敏感凸形、球形不敏感一般 好 较低 b l r c h不太敏感凸形、球形一般好较差高 c u r e 敏感任意形状不敏感好较差较高 d b s c a n 敏感 任意形状 不敏感 一般较好一般 c o b w e b敏感任意形状一般好较好较低 s o m 敏感任意形状敏感好较好一般 s t i n g 不敏感 任意形状 不敏感好 好高 从上表可以看出，现有的聚类算法在某些方面能够表现出其特有的优势，但 仍然没有哪一种算法能够在各个方面表现出很好性能的。因此，在面对不同应用， 解决不同问题时，可以根据具体的要求选择适当的聚类算法。 2 5 本章小结 本章首先介绍了聚类分析的基本概念，给出了衡量聚类算法好坏的一般标准， 然后对聚类分析过程中经常遇到的一些数据类型做了介绍，重点分析了五种常用 的聚类分析方法的原理并对这些方法的各方面性能做了比较。 1 2 第三章群体智能 3 1 群体智能的概念和特点 3 1 1 群体智能的概念 群体智能( s w a r mi n t e l l i g e n c e ，s i ) 的概念源于2 0 世纪8 0 年代，研究人员通过 模拟蜜蜂、蚂蚁、大雁等自然界生物群体行为，提出了一些用于解决计算机传统 问题和实际应用问题的智能计算或优化方法，即群体智能。严格地讲，群体智能 是一种在自然界生物群体所表现出的智能现象启发下提出的人工智能模式，是通 过对简单生物群体的智能涌现现象的具体模式研究，即“简单智能的主体通过合 作表现出复杂智能行为的特性。这些主体必须能够在环境中表现出自主性、学习 性和自适应性等智能特性。但这并不表示群体中的每个个体都相当复杂，事实恰 恰相反，组成群体的每个个体都只具有简单的智能，它们是通过相互合作表现出 复杂的智能行为。作为群体智能的典型实现模式，模拟生物蚁群智能寻优的蚁群 算法和模拟鸟群运动模式的粒子群算法正受到学术界的广泛关注。 3 1 2 群体智能的特点 群体智能具有如下特点： ( 1 ) 鲁棒性：群体没有集中控制约束，因此，在求解过程中群体中某一个或 者几个个体出现故障不会影响到群体对这个问题的求解。同时，由于采用了并行 分布式算法模型，这样可充分利用多处理器。 ( 2 ) 扩展性：群体中的每个个体都能够影响环境。每个个体之间的通信是通 过信息素这个纽带完成的，不需要通过直接的方式进行信息的传输与合作。因此， 随着个体数目的增加，用于通信的时间开销增幅较小，算法具有较好的可扩充性。 ( 3 ) 自组织性：个体往往不具有或者只有简单智能，群体表现出来的复杂行 为是通过简单个体的交互过程表现出来的智能。 ( 4 ) 简单性：群体中每个个体的行为能力都非常简单，往往几条规则就可以 描述，不牵涉到复杂计算，因而实现起来比较简单方便。 3 2 群体智能的两种模式 群体智能普遍意义上有以下几种理解：一是由一组简单智能体涌现出来的集 体的智能，以蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 1 9 3 和蚁群聚类算法心们 等为代表；二是把群体中的成员看作粒子，而不是智能体，以粒子群优化算法 ( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 2 1 3 。3 13 为代表。 3 21 蚁群优化算法 蚁群优化算法是由意大利学者m d o r i g o 等人于1 9 9 1 年首先提出的，是从自然界 生物进化的机制中受到启发，通过模拟自然界中蚂蚁搜索路径的行为，提出的一 种新型模拟进化算法。自然界中的蚂蚁在运动过程中，在其所经过的路径上会留 下一种被称之为“信息素”的物质，而这种物质会被其他蚂蚁感知到，路径上信 息素的强度会随着经过浚条路径的蚂蚁数量的增多而逐渐加强，而且也会随着时 间的推移浓度逐渐减弱。蚂蚁倾向于朝信息素浓度较高的方向移动，因此，某一 路径上走过的蚂蚁越多，则浚路径在下一时间内被其它蚂蚁选择的概率就越太， 这样就形成了一种正反馈机制。随着r 述过程的进行，整个蚁群最终会找到从蚁 穴到食物之日j 的最短路径。图3 1 形象地描述了蚁群路径搜索的原理和机制。 封 * f o o d _ 惭铋囊嚅帮撼肇竺一“ 图3 1 蚁群觅食过程 由于蚂蚁寻食的过程与旅行商( t s p ) 问题的求解非常相似，所以蚁群算法最 早的应用就是t s p i b 题的求解。目前，蚁群算法的应用领域已经扩展到多目标优化、 数据分类、聚类、模式识别、电信管理、生物系统建模、流程规划、信号处理、 机器人控制、决黄支持以及仿真和系统辨识等方面，并且都表现出了令人满意的 性能。 3 22 蚁群聚类算法 将蚁群算法应用于聚类分析，最早的研究成果是d c n e u b o u r g 等人提出了基本 蚁群聚类模型( b a s i cm o d e l ，b m ) t 2 ”用来解释尸体堆积成蚂蚁墓的行为，如图32 所示。它的基本思想是：将待聚类的数据髓机地散布到一个二维网格结构中，然 后将虚拟蚂蚁分布到这个空间内，并随机移动。在网格上移动的蚂蚁需要计算其 所处理的数据对象与周围局部环境的相似度，然后利用概率转换函数将相似度转 换成移动该对象的概率，并且在拾起或放下对象采用这个概率进行操作。蚁群通 过这种拾起或放下对象的行为来完成聚类过程。 j 警 ，! 囊! ( c j ( d j 图32 蚂蚁尸体的聚类过程 蚁群聚类算法具有以下特点：自组织性、可扩展性、健壮性以及完全分布式 控制，因此，蚁群聚类模型更适应于实际的聚类问题。 32 3 粒子群优化算法 粒子群算法最早是j a m e s k e n n e d y 和r u s s e l l e b e r h a r t 于1 9 9 5 年提出的一种基 于种群寻优的进化计算方法。其基本概念源于对鸟群群体运动行为的研究。粒子 群算法是基于这样一个场景；鸟群在某个区域当中随机搜索食物，区域中食物只 有一块，而所有的鸟儿都不知道在那儿，它们仅仅知道自己离食物还有多远。那 么如何找到食物呢? 回答是，可以通过搜索目前离食物最近的鸟的周围区