（计算机软件与理论专业论文）蚁群算法研究及其在聚类中的应用.pdf

摘要 蚁群算法是一种近年发展的模拟蚂蚁群体觅食行为的仿生优化算法。该算法采用了 正反馈并行自催化机制，具有较强的鲁棒性、优良的分布式计算机制、易于与其它方法 结合等优点，在解决许多复杂优化问题方面已经展现出其优异的性能和巨大的发展潜 力，近几年吸引了国内矫许多学者的兴趣，并对其进行了多方面的研究。 聚类分析也称聚类，是多元统计分析的种，冈时也是数据挖掘中的重要职究领域， 是数据允组和划分处理的重要手段。聚类的聪标是在没有任何先验知识的前提下，根据 样本自身的相似性划分成若干个子集，使相似的样本尽可能归为一类，而不相似的尽量 划分到不同的类中，因此，聚类又称无监督分类，在图像分割、医学诊断、天气预报、 矿藏识别及商务领域等有着广泛的应用。 本文首先介绍了聚类分析的定义、聚类的方法、数据类型及聚类结构的度量标准， 并列举了每种基本聚类算法中的几个经典算法。其次分绍了基本的蚁群算法，同时介缁 了几种蚁群算法在聚类中的应用。文章重点讨论了基于蚁群算法改进的蚁群聚类算法， 并试图从几方面改进蚁群聚类算法：算法执行效率、聚类质量、蚂蚁聚类过程中的移动 方向选择以及降低算法对参数的输入量，并提出了两种改进的蚁群聚类算法方案。实验 采用一组二维数据及聚类中常用的i r i s 数据集分别测试和验证改进算法，并和k - m e a n s 算法及基本的蚊群聚类算法进行比较，证实算法改进的有效性。最后，总结了当前工作， 分析了相关闷题，给出了在该方萄的进一步研究工作，并对蚁群聚类算法进行了展望。 关键词：聚类分析，蚁群算法，遗传算法，蚁群聚类算法 r e s e a r c ha n da p p l i c a t i o ni nc l u s t e r i n go fa n tc o l o n y a l g o r i t hm l ih u a ( c o m p u t e rs o f t w a r ea n dt h e o r y ) d i r e c t e db ya s s o c i a t ep m p e iz h e n k u i a b s t r a c t a n tc o l o n ya l g o r i t h m ( a c a ) i san e wt y p eb i o n i ca l g o r i t h mw h i c hs i m u l a t e sa n t s b e h a v i o ro ff i n d i n gf o o d s t h ea l g o r i t h mh a ss e v e r a lv i r t u e ss u c ha sp o s i t i v ef e e d b a c ka n d p a r a l l e lm e c h a n i s m ，p r e f e r a b l er o b u s t i c i t y , d i s t r i b u t e dc o m p u t i n g , a n de a s yc o m b i n a t i o n 诚氇 a n o t h e rm e t h o d s t h ea l g o r i t h mw h i c hr e p r e s e n t so u t s t a n d i n gp e r f o r m a n c ea n dt r e m e n d o u s d e v e l o p i n gp o t e n t i a la t t r a c t sl o t so fs c h o l a r sa r o u n dw o r l d t os t u d yi t s e l fp r e s e n t l y c l u s t e r i n ga n a l y s i sc o m m o n l y c a l l e dc l u s t e r i n gi sak i n do f m u l t i s t a t i s t i ca n a l y s i sa n di s ap a r to fi m p o r t a n td a t am i n i n g 。i ti sa l s oa l li m p o r t a n tm e t h o do fd a t ap a r t i t i o na n dg r o u p i n g 。 t h eg o a lo fc l u s t e r i n gi st op a r t i t i o ns a m p l e ss e ti n t os u c hc l u s t e r st h a ti n t r a - c l u s t e rs a m p l e s a r es i m i l a ra n di n t e r - c l u s t e rs a m p l e sa r ed i s s i m i l a rw i t ho u ta n yp r i o rk n o w l e d g e ，w h i c hb a s e s o ns a m p l e s c o m p a r a b i l i 啦s oc l u s t e r i n gi sa l s ok n o w na s u n s u p e r v i s e dc l a s s i f i c a t i o n c l u s t e r i n gh a sw i d e l ya p p l i c a t i o ns u c ha si m a g es e g m e n t a t i o n , m e d i c i n ed i a g n o s i s , w e a t h e r f o r e c a s t ，m i n e r a lr e s o u r c e si d e n t i f ya n db u s i n e s sa f f a i r s i nt h i sp a p e r , w ef i r s ti n t r o d u c ed e f i n i t i o n ，m e t h o d sa n dd a t at y p eo fc l u s t e r i n ga n a l y s i s a n dm e a s u r e m e n to fc l u s t e r i n gc o n f i g u r a t i o n m e a n w h i l e , w ep a r t i c u l a r i z es e v e r a lc l a s s i c a l a l g o r i t h mo fe v e r yb a s i cc l u s t e r i n ga l g o r i t h m + t h e nw ei n t r o d u c et h eb a s i ca n tc o l o n y a l g o r i t h ma n ds e v e r a la p p l i c a t i o n so fi t i nc l u s t e r i n g f i n a l l y , w eh a v er e s e a r c h e da n d i m p r o v e dt h em e t h o do fa n tc o l o n ya l g o r i t h m ，a n da p p l i e di tt oc l u s t e r i n ga n a l y s i s w eh a v e i m p r o v e da n tc o l o n ) , c l u s t e r i n ga l g o r i t h ma sf o l l o w s ：e f f i c i e n c yo f t h ea l g o r i t h m ，q u a l i 移o f t h ea l g o r i t h m ，d i r e c t i o nc h o i c eo fa n t s m o v ea n dr e d u c i n gp a r a m e t e ra n dp r e s e n tt w oa n t c o l o n yc l u s t e r i n ga l g o r i t h m s d a t ao ft h ee x p e r i m e n ta d o p t e da s e to ft w o d i m e n s i o nd a t aa n d i r i st ot e s ta n dv a l i d a t et h ea l g o r i t h m s i no r d e rt ot e s tv a l i d i t yo ft h ea l g o r i t h m s ，t h e y c o m p a r e dw i t hk - m e a n sa n dt h eb a s i ca n tc o l o n yc l u s t e r i n ga tt h es a m et i m e a tl a s t ，w e c o n c l u d ea n da n a l y z ec u r r e n tr e s e a r c hw o r k ，d i s c u s so u ri n t e n d i n gr e s e a r c hw o r ki nt h i sa r e a a n dp r o s p e c tt h ea n tc o l o n yc l u s t e r i n ga l g o r i t h m k e y w o r d s ：c l u s t e r i n ga n a l y s i s ，a n tc o l o n ya l g o r i t h m ，g e n e t i ca l g o r i t h m ，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 m l l 关于学位论文的独创性声明 本人郑重声明：所里交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他入已经发表或撰写的研究成果，也不包含本入或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书丽使用过的材料。与我一同工作的同志 对研究所傲的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名： 壅缝日期：搠g 年r 月彤日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使焉授权同上。 学位论文作者签 指导教师签名： 网期：溯8 年毒月“1 7 1 固期：p d 萍弓月日 孛邈蠢涟夫攀( 华东) 硕学链论文 第一章绪论 1 1课题研究的背景、目的及意义 随着社会静进步，生产和获取数据的能力快速增长，大量的数据被广泛使用，这就 迫切需要将这些数据转换成有用的信息和知识。戈其是，医特网的飞速发展，在方便交 流的同时，也为我们带来了海量数据和信息。在缺乏强有力的工具下，这些海量数据已 远远的超出了人们的理解和概括，人们淹没在数据的海洋中却感到信息的贫乏。许多数 据库中的数据很少被访问，数据不能充分利用，拥有这些数据库的决策者们，在做决策 时只是基于决策者的直觉。这就迫切需要一种新的技术来解决以上的问题，使得消耗了 大量财力与物力掰收集、整理的宝贵资源数据得以利用。数据挖掘就是从大量的、 不完全的、有噪声的、模糊的、随机的数据集中识别有效的、新颖的、潜在有焉的以及 最终可理解的模式的过程。因此，数据挖掘技术蛇研究成为学者们争相研究的热点。 聚类作为数据挖掘领域中的一个重要分支，是人们认识和探索事物之间内在联系的 有效手段。它既可以作为独立的数据挖掘工具来发现数据库中数据分布的一些深入信 息，也可以作为其它数据挖掘算法的预处理步骤，聚类在数据挖掘中的地位不言而喻。 聚类源予许多研究领域，除数据挖掘之外还包括统计学、机器学习、空间数据库、生物 学和市场营销等。现今的数据库中收集了大量的数据，聚类分析已经成为数据挖掘领域 一个非常活跃的研究课题。 蚁群算法是一种新型的算法，具有的较强的鲁棒性，分布式计算机制，易于与其它 算法相结合等特点，使得它成为众学者研究的对象。目前已有的各种形式的数据聚类方 法中，在计算效率、准确性方面都很好，但其中相当一部分算法要求提供一定的聚类先 验信息，如聚类簇数，从而导致聚类结采对输入参数十分敏感，在很大程度上降低了算 法的适应性，而基于蚁群的聚类算法最大的优点就是无需先验信息的设置，麸丽减轻了 用户的负担，并改善了聚类结果。另外，许多聚类方法都是以窟发式机制算法为基础的， 此类方法求解效率高，但也容易陷入局部最优，难保算法的准确性和一致性。解决这种 问题的一种有效途径就是在启发式机制中引入随机搜索过程，蚁群聚类方法的本质就是 一种非常有效的随机搜索机制，而且这种方法非常容易实施并行化处理。聚类是无监督 学习，这与蚁群本身存在的聚类现象的本质基本上一致，利用蚁群进行聚类不但算法结 构和操作比较简单，而且易于实现。因此，将蚁群算法应用予聚类中，成为研究改进聚 类算法的圭要方向。僵是，鳝前的蚁群聚类算法的应用还存在一些润题，如聚类速度和 繁一章绪论 聚类质量等还不是很理想，因此，蚁群算法在聚类分析中豹应用还有待进一步研究。 为了得到更好的聚类算法，本文主要研究了现有的蚁群算法的特点及现存聚类算法 局限性的因素。根据蚁群算法的特点，将其应用于聚类算法中，使得聚类算法在聚类效 率、聚类质量及聚类适应性上有所提高，并且克服了聚类算法的部分局限性。随着数据 挖掘技术的不断发展，本文研究的蚁群聚类算法将有着十分重要的意义。 1 2 国内外研究现状 1 2 1 聚类算法研究现状 聚类分析伴随着人类社会的产生和发展两不断深化瓣翻，最初，聚类是统计学的一个 分支，随后，提出了依据对象滔性值的相似度实现聚类的相似聚类法。相似聚类法有着 广泛的应用，但同时也存在一些不足之处，如对于一些“静念 数据的聚类是可行的， 但对于“动态 数据，则聚类结果无法令人满意，因此，提出了环境聚类法。尽管所得 到的类提供了更多的信息，但环境聚类同相似性聚类一样，所得的聚类结果不易理解。 为了克服上述的局限性，出现了概念聚类，使聚类的演化过程发生了质的变化。但搜索 生往采用穷尽法或爬由法，因此还存在着提高搜索效率、避免局部极小值等阀题。 上述的聚类方法均没有考虑到聚类的磊标，实际中普遍使用酶是旨标聚类法。这类 方法设计简单、应用范圈广，并且可以转化为优化问题，借助于经典的非线性规划方法 求解，便于计算机实现。同时，现实世界中许多事物间并无明显划分，彼此之间的关系 具有一定的模糊性和不确定性，还需要将模糊集合论引入聚类，即所谓的模糊聚类。按 照划分的结果，聚类可分为硬聚类和软聚类两种f 3 】。硬聚类是指每个对象仅属于距离最 近的聚类中心所属的类，即菲此郎彼，如硬c 均值( h a r dc - m e a n s ，h c m ) 等；软聚类 是指每个对象以不同的隶属丞数或概率属于一个或多个类，如模糨c 。均值( f u z z y c - m e a n s 。f c m ) 聚类。 按照使用模型的不同，聚类可以分为基于静态模型和动态模型两种，现有的多数聚 类算法都使用静态聚类模型，仅考虑互连性或紧密性两种因素之一。虽然某些情况下， 这类算法是有效的，但是当用户没有给出合适的静态模型参数时，算法可能会失败，尤 其是当数据对象中包含多种不同的分布形状、密度和大小的类时，更是如此。由于现实 中有太多需要进行聚类分析，同时聚类算法的广泛应用，如图像分割阔、医学诊断、天 气预报、矿藏识别及客户分类1 5 】等的应用，推动了聚类算法的研究1 6 , 7 ，如与基于免疫规 划的聚类算法 8 , 9 j ，与遗传算法【1 0 , 1 1 j 与蚁群算法【1 2 , 1 3 j 及微粒群算法f 1 4 】结合的聚类算法。 目前聚类算法研究的热点主要集中在以下几点【 j ： 2 孛匿露油大学( 华东) 硕士学位论文 f 1 ) 聚类结果的有效性。 聚类结果的有效性是聚类算法最基本也是最重要的一个要求，目前存在的一些传统 聚类方法对识别凸的、球体的簇聚类效果很好，但很多的聚类样本为凹的，形状较复杂， 因此对于复杂聚类的准确识别是研究的这点之一。同时，随着聚类样本量的的不断增加， 聚类样本中存在大小不同、密度不同、形状不同的簇，如何更有效的识别这些簇也是研 究的闻题。 ( 2 ) 聚类的性熊。 聚类性能是评价算法好坏的一个标准，随着聚类数据库规模的不断增大，对于复杂 数据结构如何在保证较好的聚类性能下进行聚类成为一个重要问题。 ( 3 ) 复杂数据聚类。 在现实应用中，聚类的对象不再是在数据库中具有同一模式的数据。聚类的对象很 多时候都是高维的，同时也可能存在本身还具有结构的样本。如何不降维或建立数据空 闻的情况下进行聚类仍是我们面临的值得研究的问题。 ( 4 ) 聚类方法结合索引结构。 由于聚类的对象很多情况下都是高维数据，研究聚类研究和索引相结合，把聚类方 法建立在有效索引结构的基础上成为我们研究的问题。 ( 5 ) 聚类的簇结构发现。 现实应用中，聚类中的很多簇不是平面的，很多聚类方法只能识别单一粒度的簇， 因此研究能够识别不同精度的簇成为必要。 1 2 2 蚁群算法的研究现状 蚁群算法是近年来懑现的一种新的优化算法，对它的研究最早开始于1 9 9 1 年，毒 意大利学者m 。d o r i g o 1 6 】等人提出，被称为蚂蚁系统( a n ts y s t e m ，篙称a s ) ，是利用 蚂蚁觅食行为与t s p ( 旅行商问题) 的相似性进行模拟产生的一种仿生算法。1 9 9 6 年， d o r i g o 1 7 】等人又提出了a s 的改进算法蚁群系统( a n tc o l o n ys y s t e m ，简称a c s ) ， 此后蚁群算法逐渐得到了相关学者的广泛关注。我国在蚁群算法领域的研究起步较晚， 就公开发表的论文的收稿时闻来看，从1 9 9 7 年开始，最先研究蚁群算法的是东北大学 控制仿真研究中心的张纪会博与徐心和教授，当时主要奔绍了这种新的进化算法一 一蚁群算法。随后在1 9 9 9 年，吴庆洪f 1 9 】等人又提出了具有变异特征的蚁群算法，随着 蚁群算法研究的深入，蚁群算法不断得到改进，引入了遗传算法的蚁群算法【2 0 ，2 ，与免 疫算法融合的蚁群算法【2 2 ，2 3 1 。 3 第一章绪论 蚁群算法不依赖具体数学问题的描述，其有全局优化能力，本质并行性且易予并行 实现的特点，鲁捧性较强易于与其它算法结合【2 4 1 等，与遗传算法、模拟退火算法等早期 进化算法相比具备更好的鲁棒性、求解时间短、易于计算机实现的优点。研究蚁群算法 的原因除上述该算法所具有的特点外，更重要的是蚁群本身存在的聚类现象和数据聚类 的本质基本上一致，因此利用蚁群进行聚类不但算法结构和操作比较简单，而且易于实 现。由于其自身的特点，蚁群算法的应用领域不断得到了推广，在作业调度问题、网络 路壶闻题【2 弱、车辆路径问题、机器入领域、故障诊断、化学工韭、图像处理瑟键，等都有 所应用，并取得了很好的结果。 。2 。3 蚁群聚类算法的研究现状 由于现实中的蚁群运动过程更加接近于实际的聚类问题，所以近年来涌现出大量不 同的蚁群聚类模型。根据蚂蚁个体的非直接通信方式s t i g m e r g y 机制的不同，可将 现有的蚁群聚类模型大致分为两类：一类是基于蚁堆形成原理，另一类是基于蚁群觅食 原理。 ( 1 ) 基于蚁堆形成原理 基于蚁堆形成原理的基本模型，最早毒d e n e u b o u r g f 2 7 1 提出。通过实验，他发现某些 种类的蚂蚁能将分散在蚁穴各处的蚂蚁尸体按一定规律堆积起来。由此发现出发， d e n e u b o u r g 设计人工蚂蚁根据数据对象与周围对象的相似性，随机地拾起和放下数据对 象，最终达到了聚类数据的目的。之后，l u m e r 和f a i e t a 2 8 1 在此基础上提出了用于聚类 分析的l f 算法。在该模型中对象在环境中的分布状况成为蚂蚁之间进行非直接通信的 变量。蚂蚁通过感知周围对象的空闻分布状况执行拾起或放下操作，使得小的簇通过吸 弓| 蚂蚁积攒更多的对象来逐渐变大。n m o n m a r c h e l 2 9 1 等入提毒的a n t c l a s s 算法在蚁堆聚 类的基础上，交替使用蚁群聚类和k 均值算法修正误差以获雯妒高质量”的聚类。r a m o s 等人口0 1 、h a n d l 等人f 3 1 】又将l f 算法应用于文本聚类。吴斌f 3 2 1 等人根据蚁堆聚类模型提 出了一种基于群智能的聚类算法，并应用于客户关系管理中的客户行为分析以及w e b 文档聚类。 这种算法由于是随机的拾起、移动和放下对象，因此算法的收敛速度很慢，且存在 熊否搜索到全部聚类对象的问题。 ( 2 ) 基于蚁群觅食原理 基于蚁群觅食原理的蚁群聚类算法【3 引，即蚂蚁通过其移动时在所经路径留下的信息 素进行非直接通信，形成正反馈加强搜索。基于蚂蚁觅食原理的数据聚类中，大部分将 4 中国程浊大学( 华寒) 矮七学位论文 数据视为具有不同属性的蚂蚁，聚类中心即是蚂蚁所要寻找的“食物源，那么数据聚 类过程则被看作是蚂蚁寻找食物源的过程。 意大利学者m d o r i g o 等人根据蚁群觅食原理提出了蚁群优化算法并用于解决n p 等经典优化问题。杨新斌【3 4 】提出的进化聚类学习的新方法以及s h e l o k a r 3 5 1 提出的蚁群聚 类算法都是基于蚁群优化算法，将聚类作为优化问题加以解决。翁怀荣f 3 6 等人引入随机 扰动和感觉知觉特征以指导信息素的更新，并将改进后的蚁群聚类算法应用到企业入力 资源管理( 毯膦) 中。 除上述两类蚁群聚类模型外，n i c o l a sl a b r o c h e 3 7 1 提出了一种新的基于蚂蚁化学识别 系统的a n t c l u s t 聚类模型，h a z z a g 3 8 1 提出了基于蚂蚁自组织行为的a n t t r e e 聚类算法。 目前蚁群聚类算法，多以蚂蚁觅食原理为研究的基础。虽然这种方法取得了较好的 聚类结果，但是也存在一些缺陷：如蚂蚁数目的大小影响聚类的性能和收敛速度；其次， 蚂蚁的转移是以信息素的多少作为转移依据，算法容易陷入局部最优解；同时，很多蚁 群聚类算法还对聚类数瞬进行了初始设遥。因此，针对蚁群聚类算法的缺陷提出了很多 蚁群聚类算法的改进算法，如基前结合较多与k 。m e 雒s 算法l 捌、遗传算法结合的蚁群 聚类算法 2 0 , 4 0 1 等。 1 。3 研究内容与思路 本文主要研究蚁群算法在聚类分析中的应用，从目前存在的一些流行的蚁群聚类算 法的分析来看，蚁群聚类算法主要存在的问题是算法的执行效率不够理想，算法的参数 过多增加了算法对参数知识领域的依赖性，尤其是大数据集的聚类还存在数据不被选择 的问题，主要研究内容如下： f 1 ) 针对大数据集进行蚁群聚类时收敛速度慢的特点，将蚁群聚类算法分为两部分， 酃聚类翦先进行数据预处理。利用谣元素越相似，则属于阕一类簇的可能性越大的思想， 先将样本集中的样本量缩小，减少下一步的数据、样本的处理量，这种思想还保证了算 法在初始数据预处理时聚类结果的准确性。 ( 2 ) 路径选择。根据聚类过程中的信息素浓度以及“蚂蚁 与“蚂蚁 之间的相似 度控制蚂蚁路径的选择，通过自适应的调整两个参数的侧重点，来决定每一阶段选择的 合并的类与方向。 ( 3 为避免在传统於蚁群聚类算法中的蚂蚁没有走过的路径上的数据一直没有被选 择的机会，将每个数据视为一个蚂蚁，采用睡眠状态和活跃状态相结合，根据蚂蚁的餍 围环境来控制蚂蚁活动的数量，同时采用与遗传算法结合的思想，更改蚂蚁状态控制蚂 气 第一搴续论 蚁进行聚类活动，不仅避免了待聚类样本存在不被选择的可能，圈时控制了在同一时闻 “活跃”蚂蚁的数量。 ( 4 ) 基于以上研究，构建蚁群聚类算法模型，在数据预处理及参数相关分析的基础 上，将该模型首先应用于标准数据i r i s 中进行验证，并应用于大数据集的聚类分析当 中，实验结果表明算法的有效性，同时应用于现实的聚类样本集中。 1 4 论文的组织结构 第一章绪论，主要介绍课题研究的背景、目的及意义和国内外研究现状、文章研 究内容、思路及文章的组织结构。 第二章聚类算法及蚁群算法简介，介绍了聚类的基本原理，隧翦聚类算法的分类； 蚁群算法原理。 第三章蚁群聚类算法的分析与研究，分析当前蚁群聚类算法的种类以及存在的问 题。 第四章一种改进的蚁群聚类算法，介绍了该算法产生的背景、基本思想、原理及 算法步骤，并利用测试数据进行有效性测试，总结算法的提国意义。 第五章a g a c a 蚁群聚类算法及瘦用，主要提出了对上一章算法的改进算法，并 将该算法与k - m e a n s 算法、基本蚁群聚类算法的在i r i s 数据上侔了对毖实验，进一步 测试算法的有效性及性能，并应用到随机产生的两个数据集a n t ( 5 0 0 ，2 ，4 ) 与 a n t ( 1 0 0 0 ，2 ，8 ) ，比较了算法的最优解的迭代次数、平均错误归类数及算法的平均正确率。 最后，总结与展望，对本文主要研究的内容和创新点作了总结，并给出了算法进一 步的改进方向。 6 中国露油大学( 华客) 硕l ：学位论文 第二章聚类算法及蚁群算法简介 2 。聚类算法简介 2 。l 。1 聚类的基本原理 1 聚类的概念及数学模型f 4 1 】 ( 1 ) 聚类分析的概念 聚类分析，又称为聚类，是把一组个体按照相似性归为若干类或簇，其目的是使得 属于同一类或簇的个体之闻的差别尽可能的小，而不同类或簇的个体间的差剐尽可能的 大。聚类与分类不同，聚类个体在划分类前是并不骥确的知道划分的规则，对予划分的 规则要通过对聚类结果的分析蠢能最终得出的。 ( 2 ) 聚类的数学模型【4 2 】 设样本集x = z ，i = 1 ，2 ，i ) ，其中z 表示d 维模式向量，其聚类问题就是找到一 - f - 2 j j 分c = c , ，c 2 ，q ) ，满足= oc ；，c ，m ，c fnc = ，z ，y = 1 ，2 ，脚， ；l ic y ，且乏使得总的类内离数度和了= 羔d i s ( x ，z 。) 最小。其中乏为g 的聚类中 七。lx f c t 心，k = l ，2 ，m ；d i s ( x ，z 。) 为样本置到其聚类中心的距离，即d i s ( x ，乙) = l 墨- z , i i 。 聚类目标函数歹为各样本到对应聚类中心的距离总和。聚类中心z 。：土yx ，其中 4 1 7l - 一 l 。lx t e c t l 乞l 为c k 的样本数目。 2 聚类分析的数据类型及相异度 ( 1 ) 聚类分析的数据类型 聚类质量是用对象的相弄度来评估的，假设要聚类的数据集合包括糟个数据对象， 黉游许多聚类算法采用下列两种数据结构团l ： 数据矩阵结构，又称为对象与变量结构。它用罗个变量( 也称为度量或属性) 柬 表示对象。例如：用姓名、年龄、身高、体重、性别、种族等属性来表示对象“人 。 这种数据结构是关系表的形式，或者看成刀p ( 珂个对象p 个属性) 的矩阵。 j c l l墨2 麓p x 2 1x 2 2恐p 1 黾2 砩 7 第二搴聚类雾法及毁群算法楚奔 相异度矩阵结构，或称d 对象结构。它存储露个对象两两之闰的相异度，表现形 式是一个r t x t 维的矩阵。 o d ( 2 ，1 ) 0 d ( 3 ，1 ) d ( 3 ，2 ) 0 d ( n ，1 ) d ( n ，2 ) 0 其中吠切为对象拜口对匆之间相异度的量化表示，通常是一个非负值，当对象f 和对匆 越相似，其值越接近0 ，否则越大。 数据矩阵经常被称为二模矩阵，相异度矩阵被称为单模矩阵。这是因为前者的行和 列代表不同的实体，而后者的行和列代表相同的实体。聚类算法大多以相异度矩阵为基 础。如果数据是用数据矩阵形式表现的，在使用聚类算法之前遥常要将箕转化为相异度 矩阵。 ( 2 ) 几种聚类分析的相异度计算方法 不问类型变量的相异度的计算方法是不同的。变量的类型可能是区间标度变量、对 称二元变量、不对称二元变量、标称变量或比例标度型变量。下面分别讨论不同变量相 异度的计算方法。 区闻标度变量 区间标度变量是一个粗略线性标度的连续度量，比如高度、重量等。对象间的相异 度大多采用基于对象间的距离来计算的。距离的度量包括欧几里德距离、曼哈顿距离和 明考斯基距离等【5 ，2 5 1 。 ( a ) 欧几星得距离，它是最常用的一种方法，其定义如下： d ( “) = 如一t 。1 2 十l t ：一一：1 2 + 十k 一1 2 ( b ) 曼哈担距离( m a n h a t t a n ) ，其定义如下： d ( i ，) = l t ，一_ 。l + l t ：一t ：l 十+ 1 一勃l ( c ) 明考斯基距( m i n k o w s k i ) ，其定义如下： l d ( i ，) = ( 1 簟，一埘+ l t ：一对+ + k b r ) i ( d ) 余弦距离，其定义如下： d ( i ，) = l s i m ( i ，) 8 孛匿蠢油丈学( 华系) 硕上学位论文 其中，s 加( 屯歹) ：1 亨薹兰这里江( 鼍。，薯：，) 和= ( x j l , x j 2 , , x j n ) 是 、7 ( ) 2 ( “) 2 两个r l 维的数据对象。 二元变量 一个二元变量只有两个状态：o 或l ，0 表示该变量为空，1 表示该变量存在。如果这 两个状态是同等价值，并有相同的权重，那么该二元变量是对称的。否则，称为不对称 的。通常，将比较重要的结果编码为l ，另一结果编码为0 。如果假设所有的二元变量有 相同的权重，可以得到一个两行两列的可能性表。在表中，g 是对象f 和对匆的值都为1 的变量的数目，厂是对象f 的值为1 而对象，的值为。的变量的数目，s 是对象z 的值为0 而对象 歹的值为l 的变量的数目，是对象f 和对匆的值都为0 的变量的数目。 基于对称二元变量的相似度称为恒定的相似度，即当一些或全部的：元变量编码改 变时，计算结果不会发生变化。对于对称的二元变量，评价两个对象之闻相异度的最著 名系数是简单匹配系数，定义为：d ( i ，j ) ：二羔一。 譬十，- 十s + f 基于不对称二元变量的相似度称为非恒定的相似度。对予不对称的二元变量，评价 两个对象之间相异度的最著名系数是j a c c a r d 系数，定义为：d ( i ，) ：型兰一。 q 专￥s 标称变量 标称变量是二元变最的推广，它可以具有多于两个的状态值。标称变量对象j 和对象 歹之间的相异度可以用简单匹配方法来计算：d ( i ，) = 型。 p 其中m 是匹配数目，即对象f 和对匆取值相同的变量的数目，p 是全部变量的数目。 序数型变量 一个离散的序数型变量类似于标称变量，此外，序数型变量的m 个状态是以有意 义的序列排序的。序列型变量对记录那些客观度量的主观评价是非常有用的。一个连续 的序数型变量类似个未知标度的连续数据的集合，即值的相对顺穿是重要的，焉其实 际的大小则不是那么重要。例如，在比赛中的相对排名比实际的度量值更重要。 序数型变量的相异度计算方法与区间标度变量非常相似。假谢是用于描述露个对象 的组序数型变量之一，厂的相异度计算步骤如下： ( a ) 第，个对象盼值为勤，变量厂有吩个有序的状态，对应于序列l ，2 ，哆。用 9 第二零聚类算法及蚁群算法麓余 对应的秩勺代替x i f ，影芒 l ，2 ，m ，。 ) 由于每个痔数型变量可以有不弼数嚣的状态，通常要将每个变量的值域影射到 0 ，1 眺上，以便每个变量有相同的权重。它可以通过黑知代替寒实现，其中， z 矿= 若。 ( c ) 采用与计算区间标度变量相异度相同的方法计算对象之间的距离。用缸作为第 f 个对象的厂值。 比例标度型变量 沈例标度型变量在非线性的标度取正的度量值。例如指数标度，近似遵循如下公式g 么移摩或么e 一，其中么和艿是委的常数。典型的例子包括细菌数露的增长，或者放射性元 素的衰变。 目前，有三种方法计算用比例标度型变量描述的对象之间的相异度。 ( a ) 采用与处理区间标度变量相同的方法。 ( b ) 先将比标度变量进行对数变换，例如对象f 彬变量的值被变换为蜥， y 扩= l o g ( x 矿) ，然后将蜥用与处理区间标度变量相同的方法进行处理。 ( c ) 将勤看作连续的序数型数据，将其秩作为区间标度的值来对待。 然而，在许多实际的数据库中，对象可能是被混合类型数据描述的。也就是说，数 据库中包含了上述多种类型变量的部分或全部。一种可取的方法是将所有的变量一起处 理，只进行一次聚类分析，将不弱类型的变量组合在单个相异度矩阵中，把所有有意义 的变量转换到共同的值域区间，l 】。 3 聚类分板类与类之间的相似性测量 根据聚类分析的概念，聚类不仅是希望同一类的类间距尽可能的小，也希望类间的 距离尽可能大，因此类与类之间的相似性测量成为评价聚类算法的一种手段。设有两类 样本点g l 和g 2 ，d ( ，) 是从g lxg 2 峥r + 的一个函数，这成为聚合指数，通常有以下几种 方法f 4 2 j ： ( 1 ) 最短距离法，即两类中最近两点闻的距离，其定义如下： 勿( g ，皱) = m i n d ( x , ，t ) 而q 巧e g 2 ( 2 ) 最长距离法，即两个类中最远两点间的距离，其定义如下： 1 0 中国蠢涟大学( 华东) 鹾土学位论文 d ( q ，q ) = m a x d ( x , ，0 ) x - j 6 e g u 2 ( 3 ) 重心法，即d ( g 1 ，g 2 ) = d 西_ ) ，式中，；，罗分别为重心的g l 和g 2 。 ( 4 ) 类平均法，即d ( g l ，g 2 ) = 丽d ( t ，t ) 它等于g l 和g 2 中两两样本点距离的 qx j e g 2 平均，式中的靠j 和蚴分鬟为g l 与g 2 中的样本点个数。 ( 5 ) 离差平方和法。若逸 d l = 瓴一i ) ( 麓一i ) q 砬= ( x y - - _ ) x 弓一动 d l + ：= ( x k - x ) ( 一- ) 露e 娲吗 式中i = 去荟而；i 2 丢歪。；夏2 百告。黾 则定义d ( g 1 ，q ) = q + ：一d l 一皱。 2 1 2 聚类分析的常用方法 聚类分析的方法很多，这罩主要介绍一下凡种常用的方法弹髑： ( 1 _ 基于分割的方法 分割法( p a r t i t i o n i n gm e t h o d s ) 的基本思想是：给定一个有个对象的数据库或数 据元组，分割的方法为数据创建足个分割，每一个分割代表一个聚类，k 来记录蚂蚁k 当前所走过的城市，集合随着t a b u 。进化过程 馋动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的寤发信息来诗算状 态转移概率。尹：( f ) 表示在f 时刻蚂蚁k 出元素( 城市) i 转移到元素( 城市) 歹的状态转 移概率： p ：( f ) = 鸶雩，若歹刊加嘁 _ 雩主_ ：_ 1 i = ：i j 了亍丽猫歹蜒露2 。移w g 蔽2 i r 2 1 ) 0 ，否则 式中，a l l o w e d k = c t a b u k ) 表示蚂蚁忌下一步允许选择的城市；髓为信息启发式 因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所 起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间协作性越 强；芦为期望启发式因子，表示麓见度的相瓣重要性，反映了蚂蚁在运动过程中启发信 息在蚂蚁选择路径中的受重视程度，其值越大，剡该状态转移概率越接近予贪心规则； 臻为启发函数，其表达式为： l 穆扩。方( 2 - 2 ) 式中，吒表示相邻两个城市之间的距离。对蚂蚁七而言，吒越小，则巩( f ) 越大，p ：( f ) 也就越大。显然，该启发函数表示蚂蚁从元素( 城市) z 转移到元素( 城市) ，的期望程 度。 为了避免残留信息素过多弓| 超残留信息淹没启发信息，在每只蚂蚁走完一部或者完 成对所有嚣个城市的遍历( 也即一个循环结束) 屠，要对残餐信息进行更新处理。这种 更新策略模仿了人类大脑记忆的特点，在信息不断存入大脑的同时，存储在大脑中的旧 信息随着时间的推移逐渐淡化，甚至忘记。由此，t + n 时刻在路径( i j 3 a ：的信息量可按 如下规则进行调整。 f ，( f + 行) = ( 1 一p ) r 护( f ) + a r 口( f ) ( 2 - 3 ) a r 章( f ) = r ；( f ) 量端i ( 2 4 ) 式中，p 表示信息素挥发系数，则l p 表示信息素残留缀子，为了防止信息的无限 积累，p 的取值范围为：pc 【o ，1 ) ；a 勺9 ) 表示本次循环中路径( f 力上的信息素增量， 1 5 第二寒聚类算法及蚊群簿法麓分 初始时刻勺( o ) = 0 ，鑫弓( f ) 表示第蠡只蚂蚁在本次循环中留在路径纸芬上的信息量。 根据信息素更新策略的不同，d o r i g om 提出t - - 种不震的基本蚁群算法模型f 1 7 删， 分别称之为a n t - c y c l e 模型、a n t - q u a n t i t y 模型、a n t - d e n s i t y 模型，其中的差别在于露 求法的不同。 在a n t c y c l e 模型中 礤) 悟若第职燃在奉次循环中经过( f ，力 ( 2 - 5 ) 1 0 ， 否则 。 式中，q 表示信息素强度，它在一定程度上影响算法的收敛速度，厶表示第k 只蚂 蚁在本次循环中所走路径的总长度。 在a n t q u a n t i t y 模型中 瑚轳导若第职蚂蚁机机+ 1 之间经过( f 力 ( 2 - 6 ) 【0 ，否则 在a n t d e n s i t y 模型中 蚴= 倦嚣职嗽稚栅+ 1 捌黜o ( 2 - 7 ) 区别：式( 2 6 ) 和式( 2 7 ) 椰l j 用的是局部信息，即蚂蚁完成一步后更新路径上的信息 素；而式( 2 - 5 ) e e 利用的是整体信息，即蚂蚁完成一个循环后更新所有路径上的信息素， 在求解t s p 时性能较好，因此通常采用式( 2 5 ) 作为蚁群算法的基本模型。 2 2 3 基本蚁群算法的实现步骤 仍以t s p 为例，基本蚁群算法的具体实现步骤： ( 1 ) 参数初始化。令时间= 0 和循环次数犯= o ，设置最大循环次数k ，将槐蚂 蚁置于栉个元素( 城市) 上，令有向图上每条边( 奶的初始化信息量f “( t ) 拳c o n s t ， 其中c o n s t 表示常数，且初始时刻af ，( o ) = 0 。 0 ) 循环次数琏卜魁+ l 。 ( 3 ) 蚂蚁的禁忌表索孳| 号k = l 。 ( 4 ) 蚂蚁数量k 卜鼢l 。 ( 5 ) 蚂蚁个体根据状态转移概率公式( 2 - 1 ) 计算的概率选择元素( 城市) 歹并前进， j e c t a b u 女 。 孛晷繇浊大学( 华东) 硕上擘位论文 回修改禁忌表指针，鄂选择好之震将蚂蚁移到新的元素( 城市) ，并把该元素移到 该蚂蚁个体的禁忌表中。 ( 7 ) 若集合c 中元素未遍历完，即意 硕士学垃论文 法蕾先进行初始化，将设置各个路径的信息素靠( 0 ) = 0 ，半径r ，统计误差s ，代表对象 m 等参数。计算对象石到再之间的加权欧氏距离办= 、f 仇( 一h ) 2 及各路径上的 信患素玲= 1 。1 , ，d 矗q 。_ _ r r ，将对象置合并到髯的概率为： 魏= 东象 ( 3 - 5 ) 魏5 萎灞 p 6 其中，s = 五| 蟊r ，s = l ，2 ，j ，j + l ， ，搿，芦为控制参数的常量，p k 为权值。如 果p v ( t ) p o ，p o 为阂值常数，剡将五合并到置的领域。 上述方法优缺点：聚类数不需要预先设置，僵由于簇半径已经绘出所以聚类规模受 到了限制；代表对象掰对运行效率及聚类结果影响较大，选择不当将陷入局部最傀解； 若待聚类数据大时，算法的执行速度慢。为了缩短算法时间，文献 1 2 , 1 3 , 3 4 j 改进了算法， 使蚂蚁在空载时搜索数据对象，负载时搜索簇结合起来，既能扫描所有数据元素，又能 利用信息素痕迹引导蚂蚁快速返回到簇，加速算法收敛。但这种方法存在一定的问题： 不再将数据都视为蚂蚁，这就需要确定蚂蚁数。蚂蚁数目的大小影响聚类的性能和收敛 速度，蚂蚁太少，收敛速度可能变慢，蚂蚁太多，可使聚类性能变坏。其次，蚂蚁的转 移是以信息素的大小作为转移依据，因此算法也容易陷入局部最优解。翟前，基于蚂蚁 觅食原理的聚类算法是用的较多的蚁群聚类算法，但仍然存在如上所述的一些问题，因 此还有待进一步的改进。 ( 3 ) 蚂蚁自我聚集行为又叫自我组织行为( a n t t r e e ) 蚂蚁通过自我聚集行为构建的树状结构，称为蚂蚁树【3