（计算机软件与理论专业论文）蚁群聚类模型优化方法的研究.pdf

i i ii i ii i i ii i ii ii iiu l 广西大学学位论文原创性声明和学位论文使用授j i 叼3 8 9 2 2 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有。除己注明部分外，论文中不包含其他人已经发表过的研究 成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮 助的个人和集体，均己在论文中明确说明并致谢。 论文作者签名：马凯o d年6 只参b 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 口即时发布口解密后发布 做作者签名：马凯翩签名冀厂代年多月彩日 蚁群聚类模型优化方法的研究 摘要 随着数据挖掘研究的不断深入，群体智能越来越受到研究人员的关注， 作为其重要分支的蚁群聚类算法备受学者们的青睐。蚁群聚类算法是受蚂 蚁群体行为启发而设计的智能仿生算法，具有群体智能的分布式、鲁棒性、 易扩展性、简单性、广泛的适应性等特点。 本文主要研究蚁群聚类模型，分析总结了目前常见的蚁群聚类算法的 基本原理、优缺点，重点分析了最有优势的基于蚁堆形成的蚁群聚类算法 ( a c l u s t e r ) 。虽然a c l u s t e r 算法取得了较好的效果，但还存在处理不 同类型数据性能差异较大，参数设定困难，执行时间过长等问题。本文针 对a c l u s t e r 的这些不足进行了改进。 针对a c l u s t e r 算法在处理序列数据时，所使用的相似度丢失过多序 列信息的不足，将序列相似度度量方法与a c l u s t e r 算法结合，提出了基 于序列相似性的蚁群聚类算法( s e q a n t c l u s t e r ) 。序列相似度度量方法综合考 虑了序列数据的集合相似性与顺序相似性，能保留更多的序列特征，使人 工蚂蚁能更好地分辨序列数据之间的差异，获得更好的聚类结果。实验表 明，该方法能有效提高蚁群聚类算法处理序列数据的能力。 针对高维数据的稀疏性、维数灾难等问题，把核函数方法引入蚁群聚 类算法，将数据映射到高维特征空间进行聚类，提出了核函数优化的蚁群 聚类算法( k e m e l a n t c l u s t e r , k a c ) 。由于核函数能将微小的样本特征放大与 t 优化，可以提高人工蚂蚁对数据差异的感知能力，提高对不同类数据的分 辨能力，从而改善聚类效果。实验表明，该方法在改善高维数据的聚类效 果的同时也加快了算法的收敛速度。 针对a c l u s t e r 算法存在的收敛速度慢、运行时间过长、形成簇数量 过多等缺点，提出了二次快速蚁群聚类算法( d o u b l e q u i c k a n t c l u s t e r , d q a c ) 。采用新的二次聚类策略，通过使用不同参数的两次聚类过程对数 据进行聚类，使人工蚂蚁在较短时间内堆积较多的较小的簇，然后再把这 些小的簇，放在较小的空间里进行第二次聚类。由于在小空间聚类可以减 小迭代的规模，减少人工蚂蚁和聚类数据对象的个数，从而减少运行时间。 实验证明，二次快速蚁群聚类算法不但提高了算法的时间效率，而且还改 善了聚类的效果。 关键词：蚁群聚类序列相似性核函数二次聚类 i i r e s e a r c ho na n tc o l o n yc l u s t e r i n gm o d e l o p t i m i z a t l 0 n a b s t r a c t 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 ，s w a r mi n t e l l i g e n c eh a s b e e nr e c e i v e dm u c hm o r ea t t e n t i o n ，a sa ni m p o r t a n tb r a n c hi fi t ，a n tc o l o n y c l u s t e r i n ga l g o r i t h mc 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 sab i o n i ci n t e l l i g e n c ea l g o r i t h mi n s p i r e db yt h ec o l l e c t i v eb e h a v i o r o f a n t ，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 f s w a r mi n t e l l i g e n c e t h i s p a p e rf o c u s e so nt h er e s e a c ho fa n tc o l o n yc l u s t e r i n gm o d e l ， a n a l y z i n gt h eb a s i cp r i n c i p l ea n dm e r i t sa n df a u l t so ft h ee x i s t i n ga n tc o l o n y c l u s t e r i n ga l g o r i t h m s ，m i a n l ye m p h a s i z i n gt h em o s ta d v a n t a g e o u sa c l u s t e r b a s e do na n t - p i p l i n gs y s t e m ，a c l u s t e ra l g o r i t h mh a sb e e no b t a i n e dg o o d r e s u l t s ，b u t i th a sm a n ys h o r t c o m i n g s ，s u c ha s p e r f o r m a n c ed i f f e r e n c e f o r p r o c e s s i n gd i f f e r e n tt y p e so fd a t a ，d i f f i c u l t yo fp a r a m e t e r ss e t t i n ga n dt i m e c o n s u m i n ga n ds oo n t h i sp a p e ri sa i m e da ti m p r o v i n ga l lt h e s ed e f i c i e n c i e s m e n t i o n e da b o v e a i m e da tt h es h o r t c o m i n g so fa c l u s t e r a l g o r i t h mp r o c e s s i n gs e q u e n c e d a t aa n dc o m b i n e dw i t ht h es e q u e n c es i m i l a r i t ya n da c l u s t e r ，t h i sp a p e r p r o p o s e da n a n tc o l o n y c l u s t e r i n ga l g o r i t h mb a s e do ns e q u e n c es i m l a r i t y , n a m e d i i i s e q a n t c l u s t e r ，w h i c hc o m p r e h e n s i v e l yt a k e si n t oa c c o u n tt h es i m i l a r i t yo f c o l l e c t i o na n dt h es i m i l a r i t yo fs e q u e n c e ，p r e s e r v i n gm o r ef e a t u r e so ft h e s e q u e n c et om a k ea r t i f i c i a la n t st ob e t t e rd i s t i n g u i s ht h ed i f f e r e n c e sb e t w e e nt h e s e q u e n c ed a t as oa st oo b t a i nb e t t e rc l u s t e r i n gr e s u l t s e x p e r i m e n t ss h o wt h a ti t c a nc l u s t e rs e q u e n c ed a t ae f f e c t i v e l y f o rt h ep r o b l e m so fh i g hd i m e n s i o n a ld a t ac l u s t e r i n g ，k e r n e lf u n c t i o nw a s i n t r o d u c e dt oa 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 ；w ep u tf o r w a r da na n tc o l o n y c l u s t e r i n ga l g o r i t h mo p t i m i z e db yk e r n e lf u n c t i o n ，n a m e dk e r n e l a n t c l u s t e r ( k a c ) i nt h i sa l g o r i t h m ，t h ed a t as p a c ew a sp r o j e c t e dt oh i g hd i m e n s i o nf e a t u r e s p a c ew i t hk e r n e lf u n c t i o n o w i n gt ot h ek e r n e lf u n c t i o n sa b i l i t yo fa m p l i f y i n g t h et i n n yf e a t u r eo fs a m p l e ，a r t i f i c i a la n t sc o u l db ee n h a n c e dt h ea b i l i t yo f d i s c r i m i n a t i o no fd i f f e r e n c eb e t w e e nd a t at oi m p r o v et h ea b i l i t yt od i s t i n g u i s h d i f f e r e n tt y p e so fd a t a t h er e s u l ts h o w st h a tt h em e t h o di m p r o v e sc l a s s i f i c a t i o n a c c u r a c yo fh i g hd i m e n s i o n a ld a t aa n dt h ec o n v e r g e n c es p e e do fa l g o r i t h ma s w e l l i no r d e rt os o l v et h ep r o b l e m so fa c l u s t e ra l g o r i t h m ，s u c ha ss l o w c o n v e r g e n c e ，t i m ec o n s u m i n ga n do v e r a b u n d a n c eo fc l u s t e r , w ep r o p o s e dan e w c l u s t e r i n ga l g o r i t h mn a m e dd o u b l eq u i c ka n tc l u s t e r i n g ( d q a c ) b y a d o p t i n gn e wc l u s t e r i n gs t r a t e g y , u s i n gt w oc l u s t e r i n gp r o c e s so fd i f f e r e n t p a r a m e t e r s ，a r t i f i c i a la n t sp i l em o r es m a l l e rc l u s t e r si nas h o r tt i m e ，t h e np u t t h e s es m a l lc l u s t e r si n t oas m a l l e rs p a c ea n dp r o c e s st h es e c o n dc l u s t e r i n g a s c l u s t e r i n gi nt h es m a l ls p a c ec a nr e d u c ei t e r a t i v et i m e sa n dt h eq u a n t i t yo f i v a r t i f i c i a la n ta n dd a t ao b j e c t s ，t h u si tc a nb ed e c r e a s e dt h er u n n i n gt i m e t h e r e s u l to f e x p e r i m e n ts h o w st h a td q a ca l g o r i t h mn o to n l yr a i s e st h ee f f i c i e n c y , b u ta l s oi m p r o v e st h eo u t c o m eo f c l u s t e r i n g k e yw o r d s ：a n t c l u s t e r i n g ；s e q u e n c es i m l a r i t y ；k e r n e lf u n c t i o n ； d o u b l e q u i c k - a n t c l u s t e r ； v 目录 摘要i a b s t r a c t i i i 第一章绪论1 1 1 引言l 1 2 国内外研究现状2 1 2 1 聚类算法研究现状2 1 2 2 蚁群聚类算法研究现状3 1 3 本文主要工作。5 1 4 论文组织结构。5 第二章蚁群聚类算法概述7 2 1 基于蚂蚁觅食原理的聚类算法7 2 2 基于蚂蚁自我聚集行为的聚类算法8 2 3 受蚂蚁分巢行为启发的聚类算法1 0 2 4 基于蚂蚁化学识别系统的聚类算法11 2 5 基于蚁堆形成原理的聚类算法1 3 2 5 1 蚁堆聚类算法的改进l f 1 4 2 5 2 蚁堆聚类算法的改进a c l u s t e r 1 5 2 6 本章小结1 7 第三章基于序列相似性的蚁群聚类算法l8 3 1 基于序列相似性的蚁群聚类算法18 3 1 1 序列数据的相似度度量1 8 3 1 2 基于序列相似性的蚁群聚类算法描述( 算法3 1 ) 2 0 3 2 实验及结果分析。2 0 3 2 1 实验数据2 0 3 2 2 性能评价标准2 1 v i 3 2 3 实验步骤及结果分析2 2 3 3 本章小结2 3 第四章核函数优化的蚁群聚类算法2 4 4 1 核函数方法2 4 4 2 核函数优化的蚁群算法2 6 4 3 实验及结果分析2 8 4 3 1 实验数据2 8 4 3 2 性能评价标准2 8 4 3 3 实验步骤及结果分析2 9 4 4 本章小结3 0 第五章二次快速蚁群聚类算法3 2 5 1a c l u s t e r 算法分析3 2 5 2 - 次快速蚁群聚类算法3 6 5 2 1 算法基本思想3 6 5 2 2 算法流程。3 7 5 3 实验及结果分析3 7 5 3 1 实验数据3 7 5 3 2 实验步骤3 8 5 3 3 实验结果及分析3 9 5 4 本章小结4 1 第六章总结与展望4 2 6 1 总结4 2 6 2 工作展望4 3 参考文献4 4 到cj 射4 8 攻读学位期间发表的学术论文4 9 v 广西大掌硕士掌位论文蚁群聚类模型优f 七方法的研究 1 1 引言 第一章绪论 随着i n t e m e t 技术的飞速发展，互联网中的资源呈爆炸式地增长。据统计至9 2 0 0 9 年年 底，互联网已拥有超过1 8 7 亿个网站，g o o g l e 索引的网页数量已经突破1 万亿，而这种指 数级的增长趋势将继续保持。随着数据库技术的普及应用，各领域所积累的数据也越来 越多，面对如浩瀚如烟的数据，人们感觉被淹没在数据的海洋里，难以找到自己感兴趣 的资源，形成了数据资源丰富但信息贫乏的局面。如何从这些海量数据中获取蕴藏其中 的大量潜在的有价值的信息，已成为一个迫切需解决的问题。在这种情况下，数据挖掘 技术便应运而生。 数据挖掘( d a t am i n i n g ) 1 1 ，也称为数据库中的知识发现( 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 ) ，就是从大量数据中获取有效的、新颖的、潜在有用的、最终可理解的 模式的非平凡过程。简单的说，数据挖掘就是从大量数据中提取或“挖掘 知识【2 1 。数 据挖掘是计算机技术研究中的一个很有应用价值的新领域，融合了数据库、人工智能、 机器学习、统计学等多个领域的理论和技术。在它近2 0 年的发展过程中显示出强大生命 力，逐渐成为研究的热点。 数据挖掘任务依据挖掘结果的模式，一般可以分为两类：描述性和预测性。描述性 数据挖掘是对多数据的一般特性进行描述。预测性数据挖掘是通过对现有数据进行分析 推理，对未来的行为进行分析预测。具体来说可以分为概念描述，关联规则分析，分类、 聚类分析、异常分析和演化分析等。 聚类( c l u s t e r i n g ) 【l 】是将物理或抽象的集合分成由类似的对象组成的多个簇的过程。 聚类是数据挖掘的重要方法之一，也被称为无监督学习( u n s u p e r v i s e dl e a r n i n g ) 。聚类 分析已在模式识别、机器学习、文本检索、生物学以及统计学等众多领域得到了广泛的 应用。随着信息技术的不断发展和应用的普及，存储在数据库中的数据也在急剧增加， 如何使用聚类技术对这些的海量数据进行高效的分析，成为一个非常具有挑战性的研究 课题。 广西大掌硕士掌位论文蚁群聚类模型优化方法的研究 1 2 国内外研究现状 1 2 1 聚类算法研究现状 随着计算机网络和数据库技术的发展和应用的推广，数据挖掘逐渐成为计算机科学 研究领域的热点。1 9 8 9 年8 月举行的第十一届国际联合人工智能( a a a i ) 学术会议，首次 提出“从数据库中发现知识( k d d ) 一词。随后k d d 在学术界和工业界的影响不断扩大， 国际k d d 组委会于1 9 9 5 年把专题讨论会改为国际会议。到目前为止，由美国人工智能协 会主办的k d d 国际研讨会已经召丌了1 5 届。除了美国人工智能协会主办的k d d 年会以 外，其他学术机构也举办了许多的数据挖掘方面的年会，例! z l s i a m d a t am i m n g ， p a k d d ，p k d d 等。19 9 7 年召开了首届p a k d d ( p a c i f i c a s i ac o n f e r e n c eo nk n o w l e d g e d i s c o v e r ya n dd a t am i n i n g ) ，目前已经举办了1 3 届。此外，人工智能、并行计算、数据 库和信息处理等领域的国际学术机构也已开辟了相应的k d d 专题或专刊。 随着数据挖掘理论研究地不断深入，实际的应用方法也不断地增加，已经开发出许 多有实际应用价值的数据挖掘系统。典型的代表有i b m 公司的i n t e l l i g e n tm i n e r f o rd a t a ， u n i c at e c h n o l o g i e s 公司的p a t t e r nr e c o g n i t i o nw o r k b e n c h ，s p s s 公司的c l e m e n t i n e ，s a s i n s t i t u t e 的e n t e r p r i s em i n e r ，还有d a r w i n ，d b m i n e r ，q u e s t ，c o v e r s t o r y ，a d v a n c e d m i n e r 等。 目前主要的聚类算法大致可分为：层次方法( 如b r i c h 3 1 、c h a n m e l e o n 4 1 、 c u r e 5 】) ；划分方法( k m e a n s 【1 1 、k m e d i o d 6 1 、c l a r a 6 1 、c l a r a n s 7 】) ；基于网格的方 法( 如s t i n g 8 1 、w a v e c l u s t e r 9 】) ；基于密度方法( 如d b s c a n 1 0 1 、d e n c l u e 1 1 1 、 o p t i c s 1 2 1 ) 。文献对1 1 种常见的算法进行了对比实验，分析对比了各自的性能差异和 优缺点。文献 1 4 g e l b a r d 等人提出了一种新的称为正二进锘i ( b i n a r y - p o s i t i v e ) 方法的层 次聚合算法。文献 1 5 中作者提出了针对符号属性的新聚类算法r n g a d h c a 。文献 1 6 中，k u m a r 等人面向连续数据提出了一种新的基于不可分辨粗聚合的层次聚类算法 r c o s d 。在该算法中，不可分辨关系被扩展成具有不严格传递特性的容差关系。文献 1 7 d i n g 等人提出一致性保留k - m e a n s 算法( k m e a n s c p ) 。文献 1 8 】中c a i 等人结合局 部空间和灰度信息，提出快速通用f c m 聚类算法f g f c m 。文献 1 9 中b i r a n td 等人提 出一种新的基于密度的聚类算法s t - d b s c a n ( s p a t i a l t e m p o r a ld b s c a n ) 与其它的基于 密度聚类算法相比，该算法具有依据非空间值、空间值和时态值发现类簇的能力。文献 2 0 对d b s c a n 算法进行改进，并应用于实际的公交站点聚类中。文献 2 1 】结合微粒群 2 广西大掌硕士掌位论文蚁群聚类模型优化方法的研究 算法，提出了一种基于密度的微粒群混合聚类算法。文献 2 2 1 提出了量子聚类( q u a n t u m c l u s t e r i n g ，q c ) 算法，该算法采用梯度下降的方法确定聚类中心，然后再用固定的度 量标准对样本进行聚类。文献 2 3 1 提出了一种基于有限资源的模糊网络结构聚类算法。 文献 2 4 】、 2 5 把核方法引入到聚类算法中，取得了良好效果。文献 2 6 】在谱图理论基础 上提出了谱聚类算法，该算法是一种基于两点间相似关系的方法，能有效避免因特征向 量维数过高而引起的奇异性问题。 为了改善聚类的效果，许多研究者将两种或多种聚类方法组合起来。聚类组合可以 克服单一聚类方法的局限性，从而得到比单一聚类算法更好的结果，目前已成为聚类分 析研究的新热点。聚类组合方法将多个聚类算法的结果融合起来以得到更高质量和鲁棒 性的聚类结果。文献 2 7 1 将神经网络组合的思想用于聚类，提出基于自适应谐振理论 ( a r t ) 的聚类组合方法：将多样性聚类分量作为a r t 网络的输入，经a r t 2 a 模型学习后， 得到最终聚类结果。文献 2 8 提出对聚类的多样性进行度量，选择中等多样性以提高聚 类组合质量的组合方法。 总的来说，在目前已提出的聚类算法中，一些算法在计算效率和准确性方面都非常 出色，并得到了广泛应用。但是大多数聚类算法要求用户提供一定的先验知识，如执行 算法需要的各种参数，同时聚类结果对参数的设定十分的敏感，使算法的适应性受到一 定的限制；一些算法对离群点较为敏感，对有含有噪音的数据聚类结果不够理想，同时 很难发现任意形状的类；层次聚类算法对类的数目和初始类中心点集等原始划分敏感， 前期划分对聚类结果有较大的影响；层次聚类算法和基于划分的聚类算法在大规模数据 集上的聚类效果不佳。 1 2 2 蚁群聚类算法研究现状 19 9 1 年意大利学者a d o r i g o 等提出的蚁群算法是一种新型的优化算澍2 9 1 。蚁群算法 是一种仿生算法，不依赖于具体的数学描述，具有许多传统算法所不具有的优点。后来 a d o r i g o 和其他学者提出了一系列的蚁群算法并应用于求解组合优化问题中的旅行商 i h - 题_ ( t s p ) t 3 0 1 、调度问题等，取得了较好的效果。随后其他学者根据真实蚂蚁构造墓地 及分类幼虫的行为，提出了基于蚂蚁的聚类算法，利用简单的智能体( a g e n t ) 模拟真实蚂 蚁的特定群体行为。基于蚂蚁的聚类算法的原理简单，同时聚类的过程更接近实际的聚 类，引起了越来越多学者的兴趣。随着研究的不断展开，相继提出了多种不同的聚类模 型。 3 广西大学硕士掌位论文蚁群聚类模型优化方法的研究 d e n e u b o u d 3 1 等于1 9 9 1 年，根据蚂蚁堆积尸体的行为提出了基于蚂蚁的聚类基本模 型( d m ) ，首次将蚁群算法应用于聚类分析。n l m e 砰口f a i e t a 对d m 模型进行了扩展，提出 y l f 聚类算法【3 2 】【3 4 】，并将其应用到数据分析上。随后，r 锄o s 等人在l f 算法的基础上， 提出了a c l u s t e r 算法【”】，改进了l f 聚类模型中蚂蚁的拾起和放下物体的策略，并且 引入信息素模型指导人工蚂蚁的移动，有效地改善了聚类的效果，并应用于文本聚类、 图像模式识别、w e b 使用挖掘等任务。 随着蚁群系统的研究的深入，受不同的蚂蚁群体行为的启发，又提出了许多不同的 蚂蚁聚类算法。文 3 6 提出一种基于蚂蚁自我聚集行为的聚类算法，该算法用蚂蚁表示 数据并代表该树的节点。蚂蚁在这棵树上或已经固定在树上的蚂蚁身上移动，寻找适合 自己的位置，最终成一棵蚁树；文 3 3 提出了一种基于蚂蚁觅食原理的蚁群聚类算法， 在该算法中蚂蚁代表数据，聚类中心是蚂蚁所要寻找的“食物源”，数据聚类当作蚂蚁 寻找食物源的过程。文 3 7 提出了一种基于蚂蚁化学识别系统的蚁群聚类算法 ( a n t c l u s t ) ，该算法模拟蚂蚁的化学识别机制，依靠神经元模板和气味来识别不同种群的 蚂蚁，蚂蚁寻找巢穴的过程就是的聚类的过程。2 0 0 6 年，徐晓华【3 8 】等受蚂蚁分巢行为 的启发，提出了一种自适应的蚂蚁聚类算法( a d 印t i v e a n tc l u s t 甜n g ，a a c ) 。 张建华等3 9 1 等改进了基于蚂蚁觅食原理的蚁群聚类算法，加速了算法的收敛，但还 存在初始参数难以确定、聚类结果对初始的木椅数量敏感等问题。文献 4 0 提出了一种 基于方向相似性的蚁群聚类算法a c c a d s ，同时使用两个反应阈值决定人工蚂蚁的拾起 放下动作，避免y l f 算法中由于计算平均相似度而出现的不足。郭会林，苏一丹等【4 l 】 提出了一种基于混合策略的蚁群聚类算法。在该算法中，人工蚂蚁根据不同的聚类情景 而采取不同的行为策略，同时赋予蚂蚁多载功能。文献【4 2 利用信息素控制蚂蚁随机移 动，提出一种新颖策略来解决无人监督的层次化蚁群聚类方法。文献 4 3 从信息粒度的 角度出发提出了一种基于粒度原理的蚁群聚类算法。文献 4 4 将动态自组织映射和蚁群 聚类算法相结合，提出了一种新的聚类算法并应用于网络入侵检测中。莫锦萍等【4 5 1 使用 k - m e a i l s 算法改进基于化学识别的蚁群聚类规则，提出一种新的k - m e a l l s 蚁群聚类算法 ( k m a n t c l u s t ) 。 虽然蚁群聚类算法具有并行性、自组织性、鲁棒性、简单性和灵活性等优良特性， 但是该类算法还存在着一定的缺点。例如聚类需要先验知识、参数设定困难、算法对参 数敏感、易于陷入局部最优、聚类结果不稳定和执行时间过长等问题。目前现存的这些 问题，有待进一步研究解决。 4 蚁群聚类模型优化方法的研究 1 3 本文主要工作 本文的创新点如下： ( 1 ) 提出了基于序列相似性的蚁群聚类算法。针对a c l u s t e r 算法在处理序列数据 时所使用的相似度的不足，将序列相似度度量方法与a c l u s t e r 算法结合，提出了基于 序列相似性的蚁群聚类算法( s e x l a n t c l u s t e r ) 。序列相似度量方法综合考虑了序列数据的 集合相似性与顺序相似性，能保留更多的序列特征，使人工蚂蚁能更好地分辨序列数据 之间的差异，获得更好的聚类结果。实验表明，该方法能有效提高蚁群聚类算法处理序 列数据的能力。 ( 2 ) 提出核函数优化的蚁群聚类算法( k e m e l a n t c l u s t e r , k a c ) ，针对高维数据的特 性，将核函数方法引入蚁群聚类算法，将数据映射到高维特征空间进行聚类。由于核函 数能将微小的样本特征放大与优化，提高人工蚂蚁对数据差异的感知能力，从而提高对 不同类数据的分辨能力。实验表明，该方法在改善高维数据的聚类效果的同时也加快了 算法的收敛速度。 ( 3 ) 提出二次快速蚁群聚类算法( d o u b l e q u i c k a n t c l u s t e r , d q a c ) 。该算法针对 a c l u s t e r 算法收敛速度慢、形成簇过多等问题，改变了聚类的策略，通过使用不同参 数的两次聚类对数据进行聚类。实验证明，二次快速蚁群聚类算法不但提高了算法的时 间效率，而且还改善了聚类的效果。 1 4 论文组织结构 第一章，绪论。介绍了课题的研究背景和意义，阐述了论文的研究内容和创新点， 简述论文的组织结构。 第二章，探讨了数据挖掘中聚类分析及主要的聚类方法，并详细介绍了目前常见的 五种蚁群聚类算法，分析了各自的基本思想、主要过程，分析总结各算法的优缺点。重 点分析基于蚁堆形成原理的蚁群聚类算法的基本原理、聚类过程以及优缺点，为后续的 研究做准备。 第三章，针对序列数据的特点将数据的序列相似性度量引入蚁群聚类算法，提出了 种基于序列相似性度量的蚁群聚类算法( s e q a n t c l u s t e r ) ，并设计实验验证算法，然后 给出实验分析。 第四章，针对高维数据的特性，将核函数方法引入蚁群聚类，提出了核函数优化的 5 广西大掌硕士掌位论文蚁群聚类模型优化方法的研究 蚁群聚类算法( k e r n e l a n t c l u s t e r , k a c ) ，并进行实验验证及结果分析。 第五章，针对a c l u s t e r 蚁群聚类算法迭代次数过多，算法执行时间过长，形成的 簇过多等缺点，提出了二次快速蚁群聚类算法( d o u b l e q u i c k a n t c l u s t e r , d q a c ) ，然后给 出了实验及结果分析。 第六章，总结全文，指出后续的研究工作和方向。 6 广西大掌硕士学位论文蚁群聚类模型优化方法的研究 第二章蚁群聚类算法概述 群体智能( s w a r mi n t e l l e g e n t ) 是通过模拟自然界群居生物的集体行为来实现人工 智能的一种方法，从2 0 世纪木出现的以来，已经引起了众多学者的关注。蚁群聚类算法 是群体智能的一个分支，具有分布式控制、自组织性、可扩充性、鲁棒性等特性。蚂蚁 作为一种古老的社会性昆虫，虽然个体的身体结构和行为都很简单，但能通过个体的相 互协作来完成远超出单个蚂蚁能力的复杂任务。 蚁群的主要信息交流方式是化学通信，蚂蚁能分泌出一种独特的被称为信息素 ( p h e r o m o n e ) 的化学物质。不同的信息素具有不同的作用，例如有的信息素能引导蚂 蚁找到食物源，有的信息素能刺激蚂蚁进入警戒状态，蚂蚁还根据其身体散发出的气味 ( 信息素) 来分辨同伴。 受自然界蚂蚁群体行为的启发，不同的学者从不同角度对蚂蚁的群体行为进行模 拟，提出了多种基于不同原理的蚁群聚类算法。 2 1 基于蚂蚁觅食原理的聚类算法 昆虫学家在对蚂蚁进行研究的过程中发现蚂蚁个体之间通过一种称为信息素 ( p h e r o m o n e ) 的挥发性物质进行信息传递，从而能相互协作，完成复杂的任务。蚂蚁寻找 食物的过程可以分为两个步骤【4 6 】：第一步是搜索食物；第二步是搬运食物。蚂蚁在运动 的过程中会在其经过的路径上留下自身散发的信息素，在整个行进过程中它们能感知路 径上遗留的信息素的浓度，并以此指导自己行进方向。蚂蚁经过越多的路径其信息素浓 度就越高，同时信息素自身也会以某个速率挥发。蚂蚁倾向于朝着信息素浓度较高的方 向行进。因此，群体的行为就表现出信息正反馈：某条路径上走过的蚂蚁越多，蚂蚁在 行进过程中选择此路径的概率就越大。蚂蚁个体间使用这种非直接的信息交流方式进行 食物搜索。 基于觅食原理的蚂蚁聚类算法的基本思想如下：每只蚂蚁代表数据集中的一个数据 对象，聚类中心就是蚂蚁要搜索的“食物源 ，聚类过程就是蚂蚁搜索“食物源的过 程。 假设数据对象为：x = x xi 置= ( x ”x ，z 拥，) ，f = 1 ，2 ，) ，首先进行算法的初 7 广西大掌硕士掌位论文蚁群聚类模型优化方法的研究 始化，设置各路径的信息素f 、簇半径，、统计误差和代表对象m 等参数。特别地，开始 时由于路径上还没有蚂蚁走过，所以设置其信息素为o ，即乃( 0 ) = 0 。然后计算对象五 和一之间的加权欧几里德距离： 忙瓣。 各条路径上的信息素浓度乃( f ) ： 秒 三葛 对象置合并到的概率p “f ) 表示为： 蹦归黥 ( 2 1 ) ( 2 2 ) ( 2 3 ) 其中s = 置i 办，s = 1 ，2 ，j + l ，) 。p 七为权值，如果毋( f ) 的值大于，则 将置合并至屿的领域内。是能见度，其值等于如的倒数。反和为调节因子，用于防止 所有蚂蚁沿着同一路径得到相同结果而产生的停滞搜索。 算法分析：该算法对参数的设置较为敏感。代表对象m 的选择对算法的运行效率和 聚类效果都有较大影响，如果设置不当将会使算法陷入局部最优。同时，调节因子0 【和 设置不当也会对算法的效率和聚类的结果产生较大影响。此外，簇半径r 的设置与聚类 的规模有直接关系，预设的簇半径将会限制聚类的规模。 2 2 基于蚂蚁自我聚集行为的聚类算法 a n t t r e e 算法【3 6 】是受真实蚂蚁的自我聚集行为启发而提出的一种聚类算法。蚁群能 通过自我聚集行为构建一种称之为蚂蚁树( a n t t r e e ) 的树状结构。每一只蚂蚁代表一个 数据，同时蚂蚁也代表树的节点，单个蚂蚁能够在这棵树上漫游并能在任意节点上固定 下来。开始时，将蚂蚁放在树的根节点上。随后，蚂蚁在这棵树上或已经固定在树上的 蚂蚁身上移动来寻找自己的合适位置，由于受到对象间的相互作用，蚂蚁倾向于固定在 树的叶节点上。树的结构和蚂蚁表示的数据之间的相似性引导蚂蚁的移动，当所有的蚂 蚁都在树上固定后，数据集的划分也就形成了。 8 广西大掌硕士学位论文蚁群聚类模型优化方法的研3 ；已 树的局部结构及节点间的相似性用欧几里德距离s i m ( i ，j ) 表示： 嗍舻一百面 ( 2 - 4 ) 其中，m 表示每个数据对象的维数，也即属性的个数；喙表示数据对象i 的第k 个 属性。每一对数据( 谚，d j ) ，i ， 1 ，n 】之间的相似度s i m ( i ，) 0 ，1 ，n 为数据集中数据 对象的总数，当s i m ( i ，) = o 时，表示喀和d ，完全不同，当s i m ( i ，) = 1 时，表示它们完全 相同。未固定的蚂蚁q 根据s i m ( i ，歹) 的值和它的局部邻居决定自身的位置。每一只蚂 a i 有且仅有一个父结点，最多有k 个子结点。为了计算蚂蚁q 与其它蚂蚁之间的相似或 相异程度，还为每只蚂蚁定义了分别定义相似性阈值( q ) 和相异性阈值乃心拥( 口f ) 。 蚁树的构造过程如下：第一只蚂蚁直接连接到树根节点上，a o 也称为支点。对于 后面来的蚂蚁q 要分两种情况考虑： 第一种情况，蚂蚁q 恰好在支点上。设蚂蚁口，在支点上并且与q 最为相似。如果q 和乃相似程度超过了相似性阈值，即s i m ( a i ，a i ) 乃拥( q ) ，那么q 向乃移动，使它们能尽 可能