（计算机应用技术专业论文）蚁群聚类算法的优化研究.pdf

蚁群聚类算法的优化研究 摘要 数据挖掘是从海量数据中获取潜在有用信息的重要手段。聚类分析 是数据挖掘中的一项重要内容，是人们认识和探索事物间联系的有效手 段，它既可作为独立的数据挖掘工具，又可作为其他数据挖掘算法的预 处理步骤，在各领域均得到了广泛应用，已成为数据挖掘研究领域中一 个非常活跃的研究课题。随着数据挖掘技术的深入研究，群体智能也越 来越受到研究人员的关注，作为其重要分支的蚁群聚类算法也备受学者 们的青睐。蚁群聚类算法是受到蚂蚁群居生活的集体行为启示而设计的 智能算法，体现了群体智能的分布式、鲁棒性、简单性、易扩展性、广 泛的适应性等特点，而且其最大的优点是在聚类过程中无需设置聚类个 数。 本文着重研究蚁群聚类算法，总结了现今蚁群聚类算法的主要分类， 重点分析了基于蚂蚁化学识别系统的蚁群聚类算法( a n t c l u s t ) 的基本思 想、算法步骤及其优缺点。针对a n t c l u s t 的不足，本文首先提出了一种 基于k m e a n s 的蚁群聚类算法k m a n t c l u s t 。该算法将k m e a n s 算法思想 引入到a n t c l u s t 聚类算法中，改进a n t c l u s t 算法聚类判断规则，不再使 用m 和m + 作为归类依据，而是计算蚂蚁与巢中心的距离，从距离的角度 判断蚂蚁是否应被踢出巢( 即是否隶属于该簇) 。在u c i 数据集上的实验 结果表明，k m a n t c l u s t 算法比a n t c l u s t 算法聚类效果好。接着，针对蚁 群聚类算法大量采用随机搜索机制和k m e a n s 算法均会使聚类结果陷入 l 局部最优的缺点，本文第二个工作就是提出应用s v m 增强k m a n t c l u s t 的全局搜索能力，从而得到全局最优的聚类结果。s v m 是有导师且学习 能力较强的机器学习方法，它能在给定有限样本的条件下取得问题的最 优解。为了获得高质量的聚类结果，在k m a n t c l u s t 聚类结果基础上，取 类中心附近一定比例的数据作为训练集训练s v m ，然后利用已训练得到 的模型对数据集进行重新分类，使得聚类结果达到给定条件下的最优解。 实验结果表明，该方法进一步提高了聚类质量。 本文提出将k m e a n s 和a n t c l u s t 算法结合，利用k m e a n s 算法的高 效性、直观明了性改进a n t c l u s t 的聚类规则，并在此基础上引入分类方法 s v m 对聚类结果进行优化，使得聚类和分类算法得到有效结合，改善聚 类效果；同时为聚类、分类算法的应用研究提供了新的思路。 关键词：数据挖掘聚类蚁群算法支持向量机 u o p t i m i z a t i o nr e a s e a r c ho fa n tc o l o n y c l u s t e r i n ga l o g o r i t h m a bs t r a c t d a t a m i n i n g i sam o s tu s e f u l l t e c h n i q u e o fa c h i e v i n g p o t e n t i a l i n f o r m a t i o nf r o ml a r g ed a t a s e t s c l u s t e r i n gi sa ni m p o r t a n tc o n t e n to fd a t a m i n i n g ，a n da l s oa ne f f i c i e n tm e t h o df o rp e o p l eu n d e r s t a n d i n ga n ds e e k i n gt h e i n t e r n a lr e l a t i o n sa m o n g t h i n g s i tc a nb eu s e da st h ei n d e p e n d e n td a t am i n i n g t 0 0 1 o rt r e a t e da st h ep r e t r e a t m e n tp r o c e s so fo t h e rd a t am i n i n ga l g o r i t h m s c l u s t e ra n a l y s i si sw i d e l yu s e di ne v e r yf i e l d s ，a n db e c o m i n gt h em o s ta c t i v e s u b j e c ti nd a t am i n i n g a l o n gw i t ht h ed e e p l yr e s e a r c ho fd a t am i n i n g ，n o t o n l ys w a r mi n t e l l i g e n c eb u ta l s oi t si m p o r t a n tb r a n c h ，a n tc o l o n yc l u s t e r i n g a l g o r i t h mq u i c k l yc a t c h e st h ee y e so fr e s e a r c h e r s a n tc o l o n yc l u s t e r i n g a l g o r i t h mi sa ni n t e l l i g e n ta l g o r i t h mi n s p i r e df r o mt h ec o l l e c t i v eb e h a v i o ro f s o c i a la n t sl i f e ，i n h e r i t i n gd i s t r i b u t i o n ， r o b u s t n e s s ，s i m p l i c i t y , s c a l a b i l i t y , a p p l i c a b i l i t yo fs w a r mi n t e l l i g e n c e ，a n di t sm o s ta d v a n t a g ei sw en e e d n tt o s e tt h en u m b e ro fc l u s t e ri nt h ep r o c e s so f c l u s t e r i n g t h i sp a p e rf o c u s e so ns t u d y i n gt h eb a s i cp r i n c i p l ea n dc a p a b i l i t yo ft h e e x i s t i n ga n tc o l o n yc l u s t e r i n ga l g o r i t h m s ，e s p e c i a l l yt h eo n eb a s e do n c h e m i c a lr e c o g n i t i o ns y s t e m ，a n t c l u s t a g a i n s tw i t ht h ed e f i c i e n c i e so f a n t c l u s t ，f i r s t l yt h i sp a p e rp r o p o s e sa ni m p r o v e da n t c l u s ta l g o r i t h mb a s e d i l l o nk - m e a n s a l g o r i t h m ，n a m e dk m a n t c l u s t i nt h i sn e wa l g o r i t h m ，t h er u l e s o f c l u s t e r i n ga r em o d i f i e df o l l o w i n gt h ei d e ao fk m e a n s 。m i a n d m ：w i l l b ei n s t e a d e dw i t ht h ed i s t a n c eb e t w e e na n ta n dc l u s t e r s c e n t e r e x p e r i m e n t a l r e s u l t so nu c id a t a s e t sd e m o n s t r a t et h a tt h ei m p r o v e dm e t h o dh a sb e u e r e f f e c ta n dp e r f o r m a n c et h a na n t c l u s t i nf a c t ，t h er a n d o m l ys e a r c h m e c h a n i s mb o t hi na n t c l u s ta n dk - m e a n sa l g o r i t h mw i l lm a k e c l u s t e r i n g r e s u l t sg e ti n t ol o c a lo p t i m i z a t i o n a g a i n s tt h i s ，s e c o n d l y ，t h i sp a p e ro p t i m i z e s c l u s t e r i n gr e s u l t su s i n gs v m s v m i sam a c h i n el e a r n i n gm e t h o du n d e rt h e s u p e r v i s o r , i tc a na c h i e v eg l o b a lo p t i m a lr e s u l t su n d e rt h eg i v e nc o n d i t i o n f o rab e t t e rc l u s t e r i n gr e s u l t ，w ec h o o s es o m eo b je c t sa r o u n dt h ec l u s t e r s c e n t e ro b t a i n e db yk m a n t c l u s ta st r a i n i n gd a t a s e tt ot r a i ns v m ，t h e ng a i n i n g t h eg l o b a lo p t i m a lc l u s t e r sw h e ns v mi su t i l i z e dt or e c l a s s i f yt h eo r i g i n a l d a t a s e t s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sm e t h o dc a nf u r t h e ri m p r o v et h e c l u s t e r i n gq u a l i t y t h i sp a p e rp r o p o s e st oc o m b i n ek - m e a n sa l g o r i t h mw i t ha n t c l u s t ， m o d i f yt h er u l e so fa n t c l u s tb yk - m e a n s ，c l u s t e r i n ga n dc l a s s i f i c a t i o n a l g o r i t h m sh a v eb e e ne f f e c t i v e l yc o m b i n e d a f t e rs v mi si n t r o d u c e d ，a l s og i v e t h e man e wm e t h o dt os t u d y 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 g ；a n tc o l o n y ；s u p p o r tv e c t o r m a c h i n e i v 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和 相关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的 研究成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过 重要帮助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名： 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 口即时发布口解密后发布 论文 肆俨6 月节日 广西大掌硕士掌位论文 蚁群聚类算法的优化研究 1 1 引言 第1 章绪论 近年来，随着i n t e r n e t 技术的飞速发展，网络资源越来越丰富，人们可以更为方 便、快捷、廉价地从网络中获取各自感兴趣的资源。但是，随着i n t e r n e t 在全球范围 的迅速普及和应用，网络上的数据和信息量呈指数级增长，据统计目前网络已经拥有 超过3 亿个页面，而这种趋势将持续保持。各领域都会产生大量的数据，面对如潮般 涌现的数据，人们感到网络不再像过去那样易于“驾驽 ，常常花了很大力气，最后 发现找到的资源却不是自己想要的，形成数据资源丰富而无法享受这一“美味佳肴 的局面。然而这些数据中却蕴藏着大量有潜在价值的信息，如何快速、有效地获取有 益信息，满足自己的信息需求，已成为一个亟待解决的问题。传统的信息处理技术已 经不能很好的解决这些问题，在实际应用中人们迫切需要更加有效的数据分析技术对 海量数据进行智能处理，甚至可以在资源中发现决策信息，指导人们进行有效的知识 发现和应用，数据挖掘就是在这种背景下应运而生。 数据挖掘( d a t am i n i n g ) ，也称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，k d d ) ，就是从大量数据中获取有效、新颖、最终可以被理解的信息模式的 过程，简而言之数据挖掘就是从海量数据中提取知识。数据挖掘技术在近年的发展中 显示出前所未有的强大生命力，并且逐渐成为研究的热点，吸引了众多学者。 数据挖掘方法很多，主要分为以下几类：传统的统计方法、关联规则、决策树、 神经网络、遗传算法、粗糙集等几种。 聚类是数据挖掘中的一个重要方法，是人们认识和探索事物间内在联系的有效 手段。它既可以作为独立的分析工具，挖掘出海量数据中的隐含信息，也可作为其 他算法的预处理步骤，为后续工作做准备。聚类分析研究由来已久，已经在机器学 习、数据探测、模式识别、文本检索、生物学和统计学等众多领域得到了广泛应用。 但是随着网络技术的发展，数据量也急剧增加，使用传统聚类分析技术进行有效的 分析仍然是一个具有挑战性的研究课题。 蚁群聚类算法的优化研究 1 2 国内外研究现状 1 2 1 聚类算法研究现状 随着网络和数据库技术的不断发展，数据挖掘也逐渐成为科学领域研究的热点。 从数据库中知识发现( k d d ) 首次在第1 1 届国际联合人工智能学术会议上提出以来， 至今，总共举办了8 次k d d 国际研讨会【6 1 】，会议的规模逐渐壮大，由起初的专题 讨论会不断地发展成为国际型的学术大会，研究重点不再是方法的简单发现，而是慢 慢过渡到系统应用，注重发现策略、技术以及学科间的结合与渗透。1 9 9 9 年第三届 p a k d d 会议备受各研究学者的关注，此次会议总共收到了1 5 8 篇论文。继k n o w l e d g e a n d d a t a e n g i n e e r i n g 会刊率先出版k d d 技术专刊后，其他重要国际学会、学刊也将 数据挖掘和知识发现列为专题和专刊讨论。 目前在国外理论研究不断深入，在实际的应用方法也不断的增加，已经有一些实 用价值的数据挖掘系统，比如 6 1 】r u l e q u e s tr e s e a r c h 公司的s e e 5 ，s g i 公司的 s e t m i n e r ，i b m 公司的i n t e l l i g e n tm i n e r ，还有c o v e r s t o r y ，e x p l o r a ，k n o w l e d g e d i s c o v e r yw o r k b e n c h ，d b m i n e r ，q u e s t 等。与国外相比，国内在数据挖掘和知识发 现这一领域整体的力量比较弱，还属于刚刚起步阶段。目前主要的聚类算法大体上分 为： 划分方法( k - m e a l l s 【1 1 、k m e d i o d 2 1 、c l a r a n s t 3 】) ；层次方法( 如c h a n m e l e o n l 4 1 、 b r i c h t 5 】) ；基于网格的方法( 如w a v e c l u s t e r 6 、s t i n g 7 】) ；基于密度方法( 如 d b s c a n t 、o p t i c s 9 1 ) 等。文【2 6 】对各聚类算法进行了性能分析并说明其使用范围。 文 1 9 】提出使用s o m 进行聚类解决k m e a n s 选取初始中心向量难的问题。文 2 0 1 q b 宋凌等人提出用粒群优化算法指导k m e a n s 算法选取初始值；文 2 1 】中针对符号属性， 作者提出了新聚类算法r n g a d h c a ，该算法将基于共享机制的小生境遗传算法运用 到分裂式层次聚类算法中，并用粗糙集的思想来定义遗传算法的适应度函数，使得对 符号属性进行聚类时能获得较好的聚类效果。文 2 2 将网格聚类应用于数据流多事件 检测中。文 2 3 】结合微粒群算法，提出了一种基于密度的微粒群混合聚类算法，文 2 4 】 则将密度聚类应用于文本挖掘中，文 2 5 】对d b s c a n 算法进行改进并用于实际的公 交站点聚类中。文【2 7 】通过使用遗传算法处理用户反馈信息来改善聚类结果；文 2 8 】 2 广西大掌硕士掌位论文 蚁群聚类算法的优化研究 则是结合了人工免疫系统和聚类技术提高用户信息的获取。 总体来说，目前已经有各种形式的聚类方法，并且一些算法无论在计算效率还是 在准确性方法都非常出色，并且得到了广泛的应用。但是其中有些聚类算法要求用户 提供先验知识，比如期望产生的聚类个数( k 均值聚类算法) ，使得聚类结果对输入的 参数十分的敏感，大大降低了算法的适应性；一些算法对孤立点比较敏感，对有噪音 的数据处理结果也不理想，同时也很难聚出形状不规则的类；另外上面提到的层次聚 类算法则对原始划分比较敏感，结果容易受到前期划分结果的影响：基于划分的聚类 算法和层次聚类算法在大规模数据集上的聚类效果不佳；基于模型的聚类方法对高维 数据的聚类不理想。 1 2 2 蚁群聚类算法研究现状 1 9 9 1 年意大利学者a d o r i g o 等提出的蚁群算法是一种新型的优化算法【1 1 1 ，它不 依赖于具体的数学描述。随后他和其他学者又提出了一系列相关蚁群算法并应用于各 领域，例如求解组合优化问题中的旅行商问题( t s p ) 、调度问题等。后来其他科学家 根据自然界真实蚂蚁群的分工行为，提出了基于蚂蚁的聚类算法，利用简单智能体使 蚂蚁在给定的条件下随意移动，这些算法的基本原理简单易懂，在实际问题已得到应 用，如大规模集成电路综合布线、电路设计、文本挖掘及网络数据包的路由等等。随 着蚁群算法的研究，人们发现在某些方面采蚁群模型进行聚类更加接近于实际聚类， 其应用正逐步引起们的关注。d e n e u b o u r g 等人受蚂蚁堆积尸体和分类幼体的启发， 最早将蚁群算法应用于聚类分析，从此开始了蚁群聚类算法的研究。 蚁群聚类算法改进及应用很广 6 0 】，从d e n e u b o u r g 提出基本的蚂蚁聚类模型n 们之 后，l u m e r 和f a i e t a 在此分析了基本的蚂蚁聚类模型的基础上对该算法进行了改进， 提出l f 算法【1 2 ，3 3 1 ，并用于聚类分析中。m o n m a r c h e n 3 1 引入a n t c l a s s 系统，交替使用蚁 群聚类算法和k 均值算法修正误差，获得更好的聚类效果。其他应用方面有r a m o s n 制、 h a n d l 等人n 5 1 使用l f 算法对文本进行聚类。 文 1 6 1 改进了基于蚂蚁觅食原理的蚁群聚类算法，加快了算法的收敛速度，但还 存在问题：最突出的就是不能将数据都视为蚂蚁，需要确定蚂蚁数。基于蚂蚁觅食原 理的聚类算法是研究应用得较多的蚁群聚类算法。文【6 0 】指出，高尚等人 1 7 1 8 1 使用 新的方法更新信息素，提出首先使用k m e a n s 算法对数据进行分类，然后据此更新信 3 广西大掌硕士掌位论文 蚁群聚类算法的优化研究 息素以达到指导蚂蚁选择操作的目的。算法虽然有一定的改进，但也存在不足，最大 的缺点就是聚类数需要预先设置。文 2 9 】提出了一种基于方向相似性的蚁群聚类算法 a c c a d s ，同时使用两个反应阈值决定人工蚂蚁的聚类动作，避免了l f 算法中由于 计算平均相似度而出现的不足。文 3 0 】利用信息素控制蚂蚁随机移动，提出一种新颖 策略来解决无人监督的层次化蚁群聚类方法。文 3 l 】将动态自组织映射和蚁群聚类算 法相结合，提出了一种新的聚类算法并应用于网络入侵检测中。 随着蚁群系统的广泛深入研究，其他基于蚁群系统的各种聚类算法被相继被提 出。文 3 2 】提出一种基于蚂蚁自我聚集行为的聚类算法，该算法用蚂蚁表示数据，并 代表该树的节点。蚂蚁在树上或已固定在树上的蚂蚁身上移动，寻找适合自己的位置， 最终形成一棵蚂蚁树；文 3 3 】提出了一种基于蚂蚁觅食原理的蚁群聚类算法，算法中 数据被看成具有不同属性的蚂蚁，聚类中心就是蚂蚁所要寻找的“食物源”，数据聚 类就可以看作蚂蚁寻找食物源的过程。文 3 4 】提出了一种基于蚂蚁化学识别系统的蚁 群聚类算法a n t c l u s t ，该算法模拟蚂蚁的化学识别机制，依靠神经元模板和气味来识 别种群蚂蚁。文 3 5 3 6 将a n t c l u s t 聚类算法应用于w e b 使用挖掘中。 虽然蚁群聚类算法得到了广泛的研究和应用，但是这些算法还是存在一些问题。 比如基于蚂蚁化学识别系统的聚类算法虽适用于各类型的数据聚类，但采用了大量的 随机策略使聚类达到稳定的效率不高，算法时间复杂度难以估计。存在的问题还值得 进一步的研究。 1 3 本文主要工作 1 3 1 研究内容 本文首先介绍了主要的几种蚁群聚类算法，分析每种算法的基本思想、聚类原理， 总结每种算法的优缺点；同时详细介绍本文重点研究的基于蚂蚁化学识别系统的蚁群 聚类算法( a n t c l u s t ) ，为后面进一步研究做准备。针对a n t c l u s t 中聚类判断条件不合 理影响聚类效果这一缺点，本文提出了一种基于k m e a n s 的蚁群聚类算法( k - m e a n s a n t c l u s t ，k m a n t c l u s t ) 。因为在a n t c l u s t 算法中是根据m ，、m ? 这两个参数来判断 一只蚂蚁在相遇过程中是否被踢出巢。经分析发现，这两个参数值的大小并不能反应 蚂蚁与巢的关系，根据算法规则求得的参数值大不一定说明蚂蚁被该巢接受的概率就 4 广西大掌硕士掌位论文 蚁群聚类算法的优化研究 大，由此得到的聚类结果势必受到影响。为此本文采用k m e r e s 算法思想改进a n t c l u s t 聚类判断规则，通过计算蚂蚁与巢中心的距离，从距离角度衡量蚂蚁是否被踢出巢将 更为合理。实验结果表明，k m a n t c l u s t 算法聚类结果优于a n t c l u s t 。 然而k m a n t c l u s t 也存在不足：聚类过程采用的随机搜索策略容易使聚类结果 陷入局部最优，同时中心的重复计算及k m e a i l s 算法自身的缺点，均有可能使得其 聚类结果陷入局部最优。为获得给定条件下的全局最优聚类结果，本文在k m a m c l u s t 算法的基础上引入s v m 对其作进一步改进。s v m 是一种有坚实理论基础的新颖的小 样本学习方法，能在给定信息条件下通过学习得到问题的全局最优解，而且算法的复 杂度与样本维数没有关系，特别适合维数较大的数据集。本文的第二个工作就是利用 s v m 的这些优点对k m a n t c l u s t 聚类结果进行优化的。 1 3 2 本文创新点 本文的创新点如下： ( 1 ) k m e a l l s 聚类算法和蚁群聚类算法相结合。针对a n t c l u s t 算法聚类判断条件 不合理，提出一种基于k m e a i l s 的蚁群聚类算法k m a n t c l u s t 。该算法利用k m e r e s 算法思想改进a n t c l u s t 算法聚类判断规则，不再使用m ，、m ? 作为聚类判断依据， 而是借鉴k m e a l l s 算法思想，为每个巢设一中心并在聚类过程中不断更新，计算蚂 蚁与巢中心的距离，依此距离判断蚂蚁是否被踢出巢簇。实验结果表明新提出的 k m a n t c l u s t 算法比原a n t c l u s t 算法聚类效果好。 ( 2 ) 分类、聚类方法相结合。k m a n t c l u s t 也存在不足：算法采用的随机搜索机制 和k m e r e s 算法均会使得聚类结果陷入局部最优的缺点，本文第二步提出使用s v m 优化k m a n t c l u s t 聚类结果。k m a n t c l u s t 聚类后各蚂蚁均有了巢，但是由于蚁群聚类 算法大量采用随机搜索机制和k m e 绷算法思想重复计算中心，会将少量属于a 巢 簇的蚂蚁归到巢簇b 中，使聚类结果陷入局部最优。s v m 是有导师指导且学习能力 较强的机器学习方法，它能在有限样本给定条件下取得问题的最优解。为了获得高质 量的聚类效果，在第一步的基础上引入s v m 进行重新归类。实验结果表明，该方法 能进一步提高聚类质量。 5 广西大掌硕士掌位论文蚁群聚类算法的优化研究 1 4 论文的组织结构 本文余下部分组织如下： 第二章，首先概述数据挖掘中聚类分析及主要的聚类方法，然后详细介绍现今主 要的各种蚁群聚类算法，分析算法基本思想、主要步骤，总结各算法的优缺点。其中 重点分析基于蚂蚁化学识别系统的蚁群聚类算法( a n t c l u s t ) 的思想、聚类过程以及总 结该算法的优缺点，为下一章的研究做准备。 第三章，首先简单介绍k m e a r l s 算法的基本思想，算法的执行过程及其优缺点。 然后详细分析了a n t c l u s t 算法的缺点，针对提出的问题本文引入k m e a n s 算法思想 对其进行改进，并设计实验验证算法。 第四章，针对聚类过程采用大量的随机搜索机制和k m e a l l s 算法容易使聚类结 果陷入局部最优，为获得给定条件下的全局最优解，引入s v m 进行进一步优化，并 给出实验及结果分析。 第五章，总结全文，指出本文的后续研究工作与方向。 6 广西大掌硕士掌位论文 蚁群聚类：算法的优化研l ；巴 第2 章蚁群聚类算法概述 聚类分析是数据挖掘的一个重要分支，蚁群算法是一种新兴的启发式搜索算法。 蚂蚁群体是一种社会性昆虫，他们有组织、有分工，还有通讯系统，它们相互协作， 能完成复杂任务。群体智能是通过模拟自然界生物群体行为来实现人工智能的一种方 法，它利用群体优势，为寻找复杂问题解决方案提供了新的思路。群体智能作为一个 新兴领域，引起众多研究人员的关注。蚁群聚类算法是一种新近发展起来的群体智能 的重要分支，具有自组织、可扩展性、健壮性等特性。受到自然界中真实蚂蚁群体行 为的启发，科学家及研究人员从不同角度对蚂蚁的群体行为进行模拟，提出了不同的 蚁群聚类算法。 2 1 聚类概述 聚类是当前数据挖掘领域的一个重要分支，主要用于在数据中发掘有价值的数据 信息模式。聚类可以定义为将物理或抽象对象的集合分成为由类似对象组成的多个类 的过程。聚类的目标是使簇中的对象彼此相似性较大，而簇间的对象相似性较小。 聚类是根据数据本身的特性，对被聚类对象进行类别划分的一种方法。它是一种 无监督学习方法，实现在没有先验知识的前提下得到满足要求的类簇聚合。随着科技 的发展，聚类分析内容多元化发展，已经深入应用到各个领域。 目前在文献 6 2 】中涌现出大量的聚类算法，主要可以分为以下几大类： ( 1 ) 划分方法( p a r t i o n i n gm e t h o d ) ：对于一有n 个对象的数据集，划分方法通过其 聚类规则将此数据集分成k 个分组，每个分组为一个类，并且k ， ( 2 - 2 ) 对象五合并到x j 的概率表示为： 桫端 ， 其中s = 置i 巩，j = 1 ，2 ，j + l ，n ) 。p 七为权值，p o 为设置的一个阈值， 当计算得到的p u ( t ) 超过岛，那么说明置、相似，应将墨合并到x j 领域内。为 能见度，其值为或的倒数。蚂蚁有向相同路径走的倾向，这样会产生聚类结果相同 而导致停止搜索的现象。为防止这一现象的出现，我们用口和调节信息素的设置， 从而对蚂蚁的路径选择产生影响，也再现了经典的贪心算法思想。 算法分析：该算法不需要预先设置聚类个数，但由于簇半径r 已给出，换言之聚 类的规模受到了限制，这是其比较突出的局限性；算法中口和的选择也很重要，选 择不当将影响算法执行效率和结果【4 2 1 。参数m 对运行效率和聚类结果影响比较大， 若选择不当将会使聚类结果陷入局部最优。当数据量比较大时，算法执行速度比较慢， 为缩短算法时间，也有文献提出了改进，如在文 3 0 1 中作者提出在空载时可以让蚂蚁 搜索数据对象，而在负载的时候就让蚂蚁搜索簇，这样扫描数据元素的同时又能利用 广西大掌硕士学位论文蚁群聚类算法的优化研究 信息素痕迹引导蚂蚁快速返回到簇，算法的收敛速度加快了。但也存在不足：数据不 能都视为蚂蚁，这就需要确定蚂蚁数。实际计算中，迭代次数一定的时想获得最佳结 果也不容易。同时，各参数的设置均带有经验性和直觉性，比如信息素分配策略、路 径搜索策略以及最优解保留策略等，影响算法的求解效率。虽然它是目前用得较多的 蚁群聚类算法，但仍然存在如上所述的问题，因此还有待进一步改进。 2 2 2 基于蚂蚁自我聚集行为的聚类算法 a n t t r e e 算法【3 刁是根据生物学中蚂蚁的自我聚集行为而衍化的一种新聚类算法， 已经得到成功应用，如人类皮肤分析、面向w e b 的数据挖掘、图像分割等。 蚂蚁能够通过自我聚集行为构建一个树状结构，称之为蚂蚁树( a n t t r e e ) 。树中的 节点是蚂蚁所表示的数据，蚂蚁能到达并粘在树的任何地方。初始时蚂蚁被放在一个 相当于树根的固定点上，蚂蚁在这棵树上或已经固定在树上的蚂蚁身上移动来寻找合 适的位置，由于受到对象间的作用，蚂蚁更趋于固定在树枝的末端。树的结构和蚂蚁 表示的数据之间的相似性引导其移动，当所有蚂蚁都固定在树上后，数据集的划分就 出来了。 树的局部结构及节点之间的相似性用欧氏距离s i m ( i ，j ) 表示： j i m ( i , 舻1 一层兰。( 一) 2 ( 2 - 4 ) 其中m 表示每个数据对象的属性值个数，屹表示数据对象f 的第k 个属性。每对 数据( 巧，d ，) ，f ，【1 ，n 】的相似度值s i m ( i ，) 在【o ，l 】之间( 表示数据集内的对象数) ， 此数越多说明对象越相似，o 说明谚和d ，完全不同，1 表示它们相同。在寻找自身位 置的蚂蚁a ，则是根据s i m ( i ，j ) 值和它的局部邻居决定其位置的。对每只蚂蚁q 我们做 一些设置：a i 只能有一个父亲结点，最多有k 戤个孩子结点。同时还为每只蚂a j 都 定义相似性阈值( q ) 和相异性阈值乃船拥( q ) ，用来表示蚂蚁q 与其它蚂蚁的相似或相 异度。 构造蚂蚁树的过程为：第一只蚂蚁直接连接到一个相当于树根的固定点a o 上。 1 - 西大掌硕士掌位论文 蚁群聚类算法的优化研究 对后来的蚂蚁q 要考虑两种情况： 第一种情况是q 在支点上。设口，是在支点上且与q 最相似的蚂蚁。如果 s i m ( a , ，吩) z 砌( 岛) ，即口f 和吩比较相似，那么将q 移向a j ，尽可能使它们聚在同一 子树上，即在同一簇内。否则( 如q 和口，不相似) 如果s 砌( q ，乃) k ( q ) ，那么就 重新创建一棵新子树，并将该节点固定上。如果已经有k 个孩子结点，那么q 向 口，移动。假如q 向a j 既不足够相似也不足够相异，则用以下公式计算： k ( 吗) 卜k ( 口 ) 口 ( 2 - 5 ) 。协加( q ) 卜互) 砸砌( q ) + ( 2 - 6 ) 来更新阈值，增加a ，下次连接的概率，其中口和夕为调节因子，均小于1 。由于分布 的相似性，相似性阈值的减少速度明显高于相异性阈值的增加速度。 第二种情况蚂蚁口f 枞a p o , 上移动，q 表示口p 上与q 最相似的蚂蚁。如果 a p o s 的孩子结点少于k 且口f 与a 胛足够相似o i m ( a 。，口胛) 乙( q ) ) ，与口p 上其他蚂 蚁足够相异( s 砌( q ，口胛) 瓦一( q ) ) ，那么将q 连在口胛上，否则蚂蚁q 随机地向a p o s 的邻居移动，寻找合适的位置。当所有蚂蚁找到合适的位置时算法结束。 1 4 广西大学硕士掌位论文 蚁群聚类算法的优化研究 算法：蚂蚁在支点上的情况算法：蚂蚁不在支点上的情况 1 f 无蚂蚁连到支点a o 上t h e n 连q 到嘞上； 1 设q 在口胛上，a k 为口胛邻域内随机选择的蚂 2e l s e蚁； ( a ) 设吩为连与q 最相似的蚂蚁： 2i fs i m ( a , ，a j ) r s i m ( a t ) t h e n ( b ) 矿s i m ( a , ，q ) ( 口j ) t h e na i 向a j 移动； ( a ) 设q 为连口p 邻域内与q 最相似的蚂蚁： (