蚁群聚类算法研究

中南大学 硕士学位论文 蚁群聚类算法研究 姓名：曾海群 申请学位级别：硕士 专业：概率论与数理统计 指导教师：武坤 20081101 摘要 蚁群算法( A C A ) 是一种新兴的智能优化算法，具有分布式计 算、信息正反馈和启发式搜索的特征，在解决许多复杂优化问题 上已经展示出其优异的性能和巨大的发展潜力。将蚁群算法应用 于数据挖掘领域的聚类分析，开始成为信息时代应对“数据爆炸 但知识贫乏“ 现象的一种智能方式。由于蚁群算法本身还处于发 展的阶段，还需要很多的验证工作，因此对蚁群聚类算法( A C C A ) 进行全面的、深入的研究具有重要的意义。 本文对蚁群聚类算法进行了较为深入的研究与分析，并提出 了一种改进的算法，做的主要工作如下。 1 总结近年来有代表性的蚁群聚类算法。首先对蚁群聚类算 法的两种基本模型及其典型算法进行简单的介绍和比较分析，然 后概述其中一些具有代表性的蚁群聚类组合算法的改进思路。 2 提出改进的基于类连通的蚁群聚类组合算法( I A C C H A ) ， 利用蚁群算法的分布式搜索避免陷入局部最优，利用K m e a n s 算法的简单高效和类的连通性，提高算法效率。 算法的改进主要表现在：通过设定阈值，减少了伪孤立类的 产生；利用最邻近法则对初始聚类结果进行修正，再对聚类中心 进行聚类；算法测试前，对数据采用不同的数据预处理技术：信 息熵法确定属性权重和主成分分析法降维；算法测试中，通过变 动半径的取值区间来检验算法的稳定性，通过变动步长来得到最 优聚类结果。 对改进算法进行的数据测试和性能分析表明，改进算法具有 计算效率高、聚类能力强、稳定性好等优点，可以用来获得全局 最优解。 关键字数据挖掘，聚类，蚁群算法，基于类连通的蚁群聚类组 合算法 A BS T R A C T A san e wk i n do fi n t e l l i g e n to p t i m i z a t i o nm e t h o d ，a n tc o l o n y a l g o r i t h m ( A C A ) h a st h ef e a t u r e so fd i s t r i b u t e dp a r a l l e lc a l c u l a t i o n ， i n f o r m a t i o np o s i t i v ef e e d b a c ka n dh e u r i s t i cs e a r c h a b i l i t y , a n dh a s d e m o n s t r a t e di t s o u t s t a n d i n gp e r f o r m a n c e a n d g r e a tp o t e n t i a l f o r d e v e l o p m e n ti ns o l v i n gm a n yc o m p l e xo p t i m i z a t i o np r o b l e m s A p p l i e d A C Ai n t ot h ea r e ao fc l u s t e r i n ga n a l y s i s ，h a sb e c o m ea ni n t e l l i g e n tw a y t od e a lw i t ht h ep h e n o m e n o no f ”i n f o r m a t i o ne x p l o d i n gb u tk n o w l e d g e p o o r ”i nt h ei n f o r m a t i o na g e A st h eA C Ai t s e l fi ss t i l li nt h ed e v e l o p m e n t s t a g e ，a n dr e q u i r e sal o to fv e r i f yw o r k ，S Oi ti so fg r e a ts i g n i f i c a n c et o c o n d u c tac o m p r e h e n s i v e ，i n d e p t hs t u d yo nt h ea n tc o l o n yc l u s t e r i n g a l g o r i t h m ( A C C A ) T h i sd i s s e r t a t i o ns t u d i e da n da n a l y z e dA C C Ad e e p l ya n dp r o p o s e d a ni m p r o v e da l g o r i t h m T h em a i nw o r ki sa sf o l l o w s 1 S u m m a r i z e ds o m e r e p r e s e n t a t i v e a n t c o l o n yc l u s t e r i n g a l g o r i t h m si nr e c e n ty e a r s F i r s to fa l l ，g a v eab r i e fi n t r o d u c t i o na n d c o m p a r a t i v ea n a l y s i so ft w ob a s i cm o d e l so fA C C Aa n dt y p i c a l a l g o r i t h m s b a s e do nt h e m T h e n ，o u t l i n e dt h ei d e a so fs o m e i m p r o v e d a n t c o l o n yc l u s t e r i n gh y b r i da l g o r i t h m s w i t h r e p r e s e n t a t i V e 2 P r o p o s e da ni m p r o v e da n tc o l o n yc l u s t e r i n gh y b r i da l g o r i t h m b a s e do nc l a s s c o n n e c t i v i t y ( I A C C H A ) I A C C H Au s e dt h ed i s t r i b u t e d s e a r c h a b i l i t y o fA C At oa v o i dl o c a l o p t i m u m ，a n du s e d t h e s i m p l i c i t y a n d h i g he f f i c i e n c y o fK m e a n s a l g o r i t h m ，t h e c l a s s - c o n n e c t i v i t yt oe n h a n c et h ep e r f o r m a n c ee f f i c i e n c y T h ei m p r o v e m e n to ft h e a l g o r i t h mm a i n l yc o n t a i n e d t h e f o l l o w i n ga s p e c t s ：s e t at h r e s h o l dt or e d u c et h e i s o l a t i o no f p s e u d o c l a s s e s ；a d o p t e dt h en e a r e s tn e i g h b o rr u l et oa m e n dt h e i n i t i a lc l u s t e r i n gr e s u l t s ，a n dt h e nc o n d u c t e das e c o n dc l u s t e r i n gt o t h ec l u s t e rc e n t e r s ；b e f o r et e s t i n go ft h ei m p r o v e da l g o r i t h m ，u s e d d i f f e r e n td a t a p r e p r o c e s s i n gt e c h n o l o g i e s ：i n f o r m a t i o ne n t r o p y m e t h o dt od e t e r m i n ea t t r i b u t e sw e i g h t sa n dp r i n c i p a lc o m p o n e n t a n a l y s i st or e d u c ed i m e n s i o n s ；w h e nt e s t i n ga l g o r i t h m ，c h a n g e dt h e l I i n t e r v a lo fr a d i u st ot e s ts t a b i l i t yo ft h ea l g o r i t h m ，a n dv a r i e dt h e s t e pt og e tt h eb e s tr e s u l t so fc l u s t e r i n g T h eI A C C H At e s to ff u n c t i o n a l i t i e sa n dp e r f o r m a n c er e v e a l v e r ye n c o u r a g i n g r e s u l t si nt e r m so fp r o c e s s i n ge f f i c i e n c y ， c l u s t e r i n ga b i l i t ya n ds t a b i l i t y ，a n di n d i c a t et h a tt h ea l g o r i t h mc a n b eu s e dt oo b t a i ng l o b a lo p t i m a ls o l u t i o n K E YW O R D Sd 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 ya l g o r i t h m ，a n t c o l o n yc l u s t e r i n gh y b r i da l g o r i t h mb a s e do nc l a s s - c o n n e c t i v i t y I I I 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：望望壁日期：兰生年业月生日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者