（概率论与数理统计专业论文）蚁群聚类算法研究.pdf

摘要 蚁群算法( 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 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：望望壁日期：兰生年业月生日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：望盗壁导师签名期：丛年丛 日 中南大学硕士学位论文 第一章绪论 1 1 课题背景 第一章绪论弟一早珀下匕 近年来，数据挖掘的研究是信息产业界的一个热点问题，已经引起人们的广 泛关注，其主要原因在于计算机技术、信息技术和互联网技术的迅猛发展，提高 了人们生产、获取各种数据的能力。大量数据的广泛使用，一方面促进了数据库 技术的发展，另一方面也出现了“数据爆炸但知识贫乏”的现象。面对大规模的 海量数据，人们不再满足于数据的查询和统计，而是迫切希望对这些数据进行进 一步分析，找出数据之间的关联性，并从中提出有用的知识和信息，以帮助人们 进行决策分析和科学研究等。要达到这些要求，传统的数据库技术无能为力，而 数据挖掘作为一种交叉学科，它包括机器学习、数理统计、神经网络、数据库、 模式识别、粗糙集、模糊数学等相关技术，能够智能自动地把数据转换成有用的 知识和信息。聚类分析作为数据挖掘技术中的一个重要课题，近年来也越来越受 到研究学者的关注，它是将数据区分为自然的群体，并给出每个群体特征描述的 一种数据挖掘方法，是数据挖掘和知识发现的一种基本方法。 虽然数据挖掘中有很多经典算法【l 】可以用于聚类分析，但是由于数据挖掘本 身具有海量数据，大量信息的复杂性、对于效率的追求，迫使人们寻找一种更加 有效的算法来优化数据挖掘算法。蚁群算法【2 。4 】是近几年出现的一种有效的启发 式随机优化算法，具有较强的鲁棒性、优良的分布式计算、易于与其他算法融合 的优点【5 】，可以很好的应用于数据挖掘算法中。基于蚁群算法的聚类分析算法可 以使数据更容易可视化，突显出人们感兴趣的特征：聚类中心的个数从数据中自 动产生，而传统的方法通常要预先设定聚类中心个数，然后由数据来适应它；蚁 群算法易于并行化，可以提高算法的效率和对大数据的适应性。尽管这种基于群 体智能的聚类算法还只是处于验证阶段，但是已经逐渐显示其生命力，与其他经 典聚类算法相比，有自己独特的优势。 1 2 国内外研究概况 1 2 1 数据挖掘研究现状及其发展趋势 半个世纪以来，人们利用信息技术生产和搜集数据的能力不断提高，特别由 于近年来i n t e m e t 迅速发展成为一个巨大的、分布广泛的和全球性的信息服务中 中南大学硕+ 学位论文第一章绪论 心，信息过量几乎成为人人需要面对的问题。计算机人工智能为从海量信息中发 现有用的知识、提高信息的利用率、开拓高层次的数据决策分析思路，作出了巨 大贡献。进入机器学习阶段的人工智能，利用数据库技术来存储管理数据，利用 机器学习的方法来分析数据，挖掘出大量的隐藏在数据背后的知识，这两种思想 的结合形成了现在深受人们关注的热门研究领域：数据库中的知识发现( k d d ： k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 。其中，数据挖掘技术便是k d d 中的一个最 为关键的环节。 自1 9 8 9 年以来，伴随网络和数据库技术的发展，数据挖掘逐渐成为计算机 学科的热点研究领域。k d d 在第十一届国际联合人工智能学术会议上首次提出， 随后美国人工智能协会开始主办k d d 专题研讨会，汇集了各个领域的研究人员 和应用开发者，集中讨论数据统计、海量数据分析算法、知识表示以及知识运用 等问题。随着研究的深入，专题研讨会的规模发展到国际学术大会，研究重点也 逐渐从发现方法转向到系统应用，注重多种发现策略和技术的集成，以及多种学 科之间的相互渗透。与此同时，市场上也出现了不少的数据挖掘系统软件产品， 并且在北美、欧洲等国得到了应用，其中比较成功的是i b m 开发的i n t e l l i g e n t m i n e r 系统【6 j 、s i l i c o ng r a p h i c s t n c ( s g i ) 开发的m i n e r s e t 系统【6 】、d b m i n e r t e c h n o l o g y 公司开发的d b m i n e r 系统以及m i c r o s o f t 于2 0 0 2 年推出的o l ed b f o rd m 技术体系。目前，数据挖掘技术在零售业的货篮数据( b a s k e td a t a ) 分 析、金融风险预测、产品产量、质量分析、分子生物学、基因工程研究、i n t e m e t 站点访问模式发现以及信息搜索和分类等许多领域得到了成功应用。 与国外相比，国内对d m k d ( d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ) 的研 究稍晚，没有形成整体力量，不过经过十多年的发展，在理论和应用技术方面已 经得到了长足的发展。目前，国内的许多科研单位和高等院校竞相开展知识发现 的基础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究所、空 军第三研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊方法在 知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的 研究，华中科技大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、 吉林大学等单位开展了对关联规则开采算法的优化和改进；南京大学、四川联合 大学和上海交通科技大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘。但上述研究多限于理论方面，尚未有成功的数据挖掘产品实现。 虽然数据挖掘的前景很好，但就目前来看这一热门技术还处于初级探索阶 段，更多地停留在理论研究上，而且这种研究是漫长且不可完全预知的，在应用 方面还不是很完善。以下几个方面将是未来比较重要的数据挖掘研究方向【j 7 】： ( 1 ) 应用探索，即研究数据挖掘系统将向特定应用发展，如反恐数据挖掘、 2 中南大学硕士学位论文第一章绪论 移动数据挖掘等； ( 2 ) 可伸缩的和交互的数据挖掘方法，其中一个重要的方向是基于约束的挖 掘： ( 3 ) 数据库系统、数据仓库系统和w e b 数据库系统的数据挖掘集成，主要是 加强数据挖掘与数据仓库一体化的研究； ( 4 ) 数据挖掘语言的标准化； ( 5 ) 可视数据挖掘，即寻求数据挖掘过程中的可视化方法，使知识发现的过 程能够被用户理解，也便于在知识发现的过程中进行人机交互； ( 6 ) 挖掘复杂数据类型的新方法，如加强对数据流、序列、图、时间空间、 文本、多媒体等数据的开采； ( 7 ) w e b 挖掘，特别是在因特网上建立数据挖掘服务器，并且与数据库服务 器配合，实现w 曲挖掘； ( 8 ) 数据挖掘中的隐私保护和信息安全。 1 2 2 蚁群算法研究现状及其发展趋势 群体智能的研究在国外进行的比较早，目前主要是对蚁群算法的研究。自 1 9 9 1 年d o r i g o 首次提出蚁群算法以来，蚁群算法已经在组合优化、路由、数据 挖掘等多个领域取得了非常突出的成就，显示出该算法具有较强的鲁棒性、优良 的分布式计算、易于与其他方法结合的优点。国际著名的顶级学术刊物( ( n a t u r e ) ) 曾多次对蚁群算法的研究成果进行报道 8 - 1 0 】，f u t u r eg e n e r a t i o nc o m p u t e r s y s t e m s ) ) 和( ( i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ) ) 分别于2 0 0 0 年和 2 0 0 2 年出版了蚁群算法特刊，在比利时布鲁塞尔大学每两年召开一次的蚂蚁优 化国际研讨会进一步促进了这一智能计算领域的学术交流，从而使这种新兴的仿 生优化算法展现出勃勃生机，其应用范围完全可与遗传算法相媲美。目前研究和 应用的区域主要集中在比利时、意大利、英国、法国、德国等欧洲国家，日本和 美国也开始启动对蚁群算法的研究和应用。 目前国内也开始有关于蚁群算法的公开报道，但是相关研究很多还只是停留 在试验探索阶段，尚未能提出一个完善的理论分析，对它的有效性也没有给出严 格的数学解释。但是，从目前模糊控制所碰到的情况看，理论上的不完善并不妨 碍应用，有时应用还会超前于理论，并推动理论的研究，蚁群算法也是如此。 蚁群算法作为一种新兴的仿生优化算法，在多个应用领域已经取得了巨大的 成功，展现出前所未有的勃勃生机，但是任何事物都有两面性，蚁群算法也不例 外。蚁群算法在理论上尚不完善，如：算法收敛性的证明只是针对于一些特定的 算法，参数设定尚无严格的理论依据，至今还没有确定最优参数的一般方法，大 3 中南大学硕士学位论文 第一章绪论 多数情况是针对不同的蚁群算法模型依据经验而定等等。在应用方面，蚁群算法 也有待进一步拓广、深入。关于蚁群算法在今后的研究方向，主要涉及以下几个 方面1 1 】： ( 1 ) 蚁群算法的模型改进：目前人们针对具体问题提出的改进蚁群算法普适 性不强，自然界中的真实蚂蚁还有许多其它的智能行为有待进一步研究，所以蚁 群算法模型还有很大的改进空间； ( 2 ) 蚁群算法的理论分析：作为一种概率搜索算法，蚁群算法从数学上对其 正确性和可靠性进行证明比较困难，并且在其理论研究中，有关参数选择、信息 素分配、收敛速度等问题仍需要大量的研究分析工作； ( 3 ) 蚁群算法的并行实现：蚁群算法在本质上以分布式的协同优化计算方式 为特征，但在串行计算机上对蚁群算法进行的模拟并不能真正体现蚁群算法的本 质特征，因此，开展蚁群算法的并行研究也是一个研究方向； ( 4 ) 蚁群算法的硬件实现：仿生硬件是并行计算环境下的产物，蚁群算法的 硬件实现是仿生硬件研究领域中的一个新的分支，但是蚁群算法仿生硬件在电路 设计、可靠性、可测试性、普适性、硬件规范等方面还需要进一步研究； ( 5 ) 蚁群算法的智能融合：进一步研究蚁群算法与遗传算法、人工神经网络、 微粒群算法、人工免疫算法等算法的融合，努力探索蚁群算法与一种或者几种仿 生算法相融合的统一机制； ( 6 ) 蚁群算法在更多领域以及更深领域的应用：纵向而言，蚁群算法的应用 深度还不够，横向而言，蚁群算法的应用领域还需要进一步的拓展，所以不管是 蚁群算法的应用领域还是应用深度，都有很广阔的研究前景。 1 3 论文研究的内容和组织 本文的主要内容是研究作为数据挖掘技术重要组成部分的聚类分析技术，适 用于求解复杂的组合优化问题的蚁群算法以及蚁群算法在聚类分析领域中的应 用。 本文的结构按以下方式进行组织。 第1 章介绍了数据挖掘技术以及蚁群算法的国内外研究现状及发展趋势，同 时提出本文的主要研究内容。 第2 章概述了聚类分析的基础知识以及蚁群聚类算法的两种基本模型。在有 关聚类分析基础知识的介绍中，包括了聚类分析的数学模型、聚类的过程、数据 变换方法、相似度的度量以及常用的聚类算法。在蚁群聚类算法两种模型的介绍 中，重点介绍了每种模型的基础算法，并对两种模型进行简单的分析与比较，为 下文算法的改进做了铺垫。 4 中南大学硕士学位论文第一章绪论 第3 章首先总结了一些具有代表性的改进的蚁群聚类组合算法的基本思路， 然后提出了一种基于类连通的蚁群聚类组合算法，重点阐述了改进算法的基本思 想、算法的步骤和流程。这是全文的核心部分，是下章仿真实验的理论来源。 第4 章是对改进算法进行仿真实验。本章针对数据预处理的不同设计了两组 实验：基于信息熵权重的蚁群聚类组合算法实验和基于主成分分析的蚁群聚类组 合算法实验，其中重点对第一组实验的结果进行分析。实验结果分析表明改进算 法具有较高的聚类精度和较好的算法稳定性。 第5 章总结了本文主要研究和创新的内容，同时给出了进一步的研究方向。 5 中南大学硕士学位论文 第二章蚁群聚类相关技术分析 第二章蚁群聚类相关技术分析 聚类分析是数据挖掘的一个重要领域，也是当前研究的热点问题之一。它是 一种研究数据间逻辑上或物理上的相互关系的技术，通过一定的规则将数据集划 分为在性质上相似的数据点构成的若干个类。聚类分析的结果不仅可以揭示数据 间的内在联系与区别，同时也为进一步的数据分析与知识发现提供重要的依据， 如数据间的关联规则、分类模式【1 2 , 1 3 以及数据的变化趋势等。 蚁群算法是一种群智能优化算法，具有良好的搜索全局解的能力，在解决许 多复杂优化问题方面已经展现出优异的性能和巨大的发展潜力，成为一个备受关 注的前沿课题。将蚁群算法应用于聚类分析领域，对海量数据进行处理，是信息 时代知识发现的一种新的智能方式，在与其他经典聚类算法的比较分析中，逐渐 显示出其生命力，突显自己独特的优势。 2 1 聚类分析理论基础 2 1 1 聚类问题模型 所谓聚类( c l u s t e r i n g ) ，就是将数据对象分成类或簇的过程，使同一个簇中的 对象之间具有很高的相似度，而不同簇中的对象高度相异。相异度根据描述对象 的属性来计算，通常使用距离度量。聚类作为数据挖掘中一种重要的挖掘任务和 挖掘方法，从数据库中寻找数据间的相似性，并依此对数据进行分类，使得同一 类的个体之间的相异度尽可能小，而不同类的个体问的相异度尽可能的大，从而 优化大规模数据库的查询和发现数据中隐含的有用信息或知识。 假设待聚类的数据集合包含n 个数据对象，通用的数据表示方法是矢量表示 法，即通过一个多维空间中的矢量，来描述一个对象多方面的特征。矢量的每个 维度描述对象的一个特征，多个对象的矢量构成一个模式矩阵( p a t t e r nm a t r i x ) ， 矩阵中每一行描述一个对象，每一列描述一个特征。 在此基础上，聚类问题可以简单描述为：给定m 维空间r ”的n 个向量( 数据 集) ，把每个向量归属到k 个聚类中的某一个，使得每个向量与其聚类中心的距 离最小。其数学模型1 1 4 , 1 5 】具体描述如下： 已知模式样本集 x ) 有n 个样本和k 个模式分类爷，j = 1 ，2 ，k ) ，每个样 本有m 个特征指标，由此得到一个样本矩阵x 如下： 6 中南大学硕士学位论文第二章蚁群聚类相关技术分析 x = l五2 。 x 2 1而2 恐m l 吒2 ( 2 1 ) 矩阵x 中，每一行为一个样本，如矩阵x 的第i 行表不第i 个样本置，其中 x u ( i = i ，n ；j = 1 ，所) 为第i 个样本的第j 个指标的观测值。以每个模式样本到 各自聚类中心的距离之和达到最小为标准，定义目标函数为： j f t = 确：。x i 。$ j 嘞0 五一己i | ，( 2 - 2 ) 满足 ：。w u = 1 ，i = l ，刀， ( 2 - 3 ) 二。l ，j = l ，k ， ( 2 4 ) 其中k 为聚类数目，0 ，表示_ ，类样本( s ，) 的均值向量，( 2 3 ) 式表示模式样本f 只 能分配给一个聚类中心，( 2 4 ) 式表示每一个类中至少有一个样本。的设置规 则为： 嘞=n蒹?(2-5lo ， 嘞2 ，否妣。 _ ) 确定嘞之后，就可以计算每个类别的聚类中心，己计算如下： 弓= 击二。五，j = 1 ，2 ，k ( 2 - 6 ) 乙瑚 聚类是数据挖掘、模式识别等研究方向的重要研究内容之一，在识别数据的 内在结构方面具有极其重要的作用，已经广泛应用于许多领域。如，模式识别中 的语音识别、字符识别；机器学习中的图像分割、机器视觉；图像处理中的数据 压缩、信息检索；数据分析中的多关系数据挖掘、时空数据库应用( g i s 等) 、序 列和异常数据分析；市场研究中的市场营销、客户关系管理；w e b 上的文档分 类、相似访问模式的发现【1 6 - 2 2 。此外，聚类还可应用于离群点检测【2 3 】( 信用卡欺 诈、电子商务中的犯罪等) 。 2 1 2 聚类过程 典型的聚类过程主要包括数据( 或称为样本或模式) 准备、特征选择和特征提 7 中南大学硕士学位论文第二章蚁群聚类相关技术分析 取、接近度计算、聚类( 或分组) 、对聚类结果进行有效性评估等步骤【l 】。 ( 1 ) 数据准备：包括特征规范化和降维。 由于不同的属性变量即特征变量可能具有不同的量纲和量纲单位，为了消除 量纲和量纲单位不同所带来的不可公度性，需要对原始数据进行规范化处理。 降维主要是为了减少高维数据分析的复杂性，采用维度归约技术可以得到数 据集的归约表示，它小得多但是仍接近保持原始数据的完整。这样对降维后的数 据集进行聚类分析将更有效并产生相同的分析效果。常用的维度归约方法有小波 变换和主成分分析( p r i n c i p a lc o m p o n e n t sa n a l y s i s ，简称p c a ) 2 4 ，2 5 1 。 ( 2 ) 特征选择：从最初的特征中选择最有效的特征，并将其存储于向量中。 ( 3 ) 特征提取：通过对所选择的特征进行转换形成新的突出特征。 ( 4 ) 聚类( 分组) ：首先选择合适特征类型的某种距离函数( 或构造新的距离函 数) 进行接近程度的度量，然后选择合适的聚类算法，并根据具体的应用领域设 定合理的参数执行聚类( 分组) 。 ( 5 ) 聚类结果评估：主要采用外部有效性评估、内部有效性评估和相关性测 试评估等方式对聚类结果进行评估。 前3 个步骤可以统称为数据准备阶段，是数据挖掘中数据预处理的重要内 容，它能提高聚类的质量，使得聚类更加有效、容易。聚类( 分组) 阶段是聚类的 关键步骤，尤其是聚类算法的选择，直接影响聚类的效果。下面三节将具体介绍 数据规范化变换的方法、相似性度量方法和常用的聚类分析算法。 2 。1 3 数据规范化变换方法 在聚类之前，往往需要对原始数据进行规范化处理，使得不同量纲、不同量 纲单位的数据能够一起进行比较，并使算法性能得到最有效的发挥。常用的规范 化变换方法有以下几种。 ( 1 ) 中心化变换 称变换 菇= -xj(ixu x j ( i = 1 ，2 ，n ；j 。= 1 ，2 ，垅) 嘞2 5 l ，z ，2 l ，z ，垅) 为中心化变换。变换后数据均值为0 ，而协方差阵不变，即协方差阵为 s = s = ( 岛) 。川 ( 2 7 ) ( 2 - 8 ) 其中， 西= i 与：。( 矗一；，) ( 吻一x ，) = i j l ：。巧( 2 - 9 ) ( 2 ) 标准化变换 8 中南大学硕士学位论文 第二章蚁群聚类相关技术分析 称变换 = ( 嘞一x ，) s ( f = 1 ，2 ，n ；j = l ，2 ，1 ) ， s ：压面鬲泸啦， q 。1 为标准化变换。变换后的数据每个变量的样本均值为0 ，标准差为1 ，而且标准 化后的数据 巧 与变量的量纲无关。 ( 3 ) 极差正规化变换 称变换 为极差正规化变换。变换后的数据0 1 ；极差为1 ，也是无量纲的量。 ( 4 ) 归一化变换 称变换 弓= 吻：。x u ( j = l ，2 ，m ) ( 2 - 1 2 ) 为归一化变换，变换后的数据模式矩阵的每列的和为l 。 规范化处理倾向于给所有的变量赋予相等的权重，但是在一些应用中，用户 可能想赋予某些变量比其它变量大的权重，或者不同变量对判断不同实体的相异 度的影响程度不一样。这时往往需要用户对不同属性变量给出不同的权重，或者 在属性权重不确定时，需要根据观测数据本身的结构来确定属性的权重。 2 1 4 相似度度量方法 对象间的相似性是聚类的核心要素，对相似性进行度量是区别对象的基础。 在聚类分析中，每个数据对象由不同的属性构成，这些属性主要分为数值属性 ( n u m e r i c a la t t r i b u t e s ) 和类属性( c a t e g o r i c a la t t r i b u t e s ) 。 数值属性的相似性测量方法大多直接或间接依赖欧几里德距离。对于m 维样 本空间中的n 个数据对象构成的如式( 2 1 ) 所示的模式矩阵，任意两个数据对象五 和x ，之间的距离以的计算方法一般有如下几种。 1 闵科夫斯基距离： 毛( g ) = f ：。i 一1 9 l l q ( f ，j f = 1 ，2 ，”) ( 2 1 3 ) 9 d j 但 x m 乙b = 哪叫 一 ， 乙0 沪q 为 y m wm 乩 m 如 一 m 垃而 旷黔 = = 。而吩 中南大学硕士学位论文第二章蚁群聚类相关技术分析 这是距离最通常的形式，如果q = 1 , 2 、，可以分别得到以下的距离： ( 1 ) 绝对值距离，即各属性之差的绝对值的和： 4 0 ) - - z ：。l 黾一屯j = l ，2 ，刀) ( 2 - 1 4 ) ( 2 ) 欧式距离，即各属性之差的平方和的平方根： 吒( 2 ) = 三，1 一1 2 ( f ，j = l ，2 ，咒) ( 2 1 5 ) ( 3 ) 切比雪夫距离，即各属性之差的绝对值的最大值： 略( ) - m 脚a ：x 。i x r , 一x ，, l i i ，j = 1 ，2 ，z ) ( 2 - 1 6 ) 在以上的几种距离中，最常用的是欧式距离，其特点是对坐标系进行平移或 旋转之后，欧式距离保持不变，对象仍然保持原来的相似结构。 闵科夫斯基距离要求属性的量纲相同，当各属性的值相差悬殊时，要求进行 标准化。另外，闵科夫斯基距离没有考虑变量的多重相关性。当变量之间存在明 显的相关性时，采用闵科夫斯基距离会造成有些变量被过度强调。有时为了突出 一些数据的关键属性对聚类分析的重要作用，常采用加权形式的距离，以避免某 些属性的值过大而屏蔽其它取值较小的属性对数据相似性测量的影响。 2 马氏距离： 露( m ) = ( 置一一) r 。1 ( 置一) ， ( 2 - 1 7 ) 其中为样本协方差阵。马氏距离克服了闵科夫斯基距离受量纲和多重相关性影 响的缺点，但马氏距离的计算量比较大，不适合大规模的数据量。 3 余弦距离： 如= 1 一s i m ( x i ，z ，) ， ( 2 1 8 ) 式中， x x 。 豇m ( 墨，- ) 2 而硒寿蒜丽。( 2 - 1 9 ) 针对上述几种距离不能直接应用于类属性数据的特点，r a l a m b o n d r a m y 提出 一种将类属性转换成二进制属性的方法，用0 或1 表示一个类属性值存在或者不 存在，并在算法里把这些二进制属性当成数值来处理，该方法需要一个转换过程， 如果类属性值很多，那么转换后的空间会很大。由这种方法容易得出描述类属性 的海明距离公式( 工，为具有几个类属性的数据对象，垓，虼是对应的属性值) ： 办= 辨= 。万( ，) ， ( 2 2 0 ) 式中， 1 0 中南大学硕士学位论文 第二章蚁群聚类相关技术分析 万( ，) _ 0 , x i k = y k , 2 1 5 聚类分析的主要方法 ( 2 - 2 1 ) 聚类方法是一个活跃的研究领域，已经有大量经典的算法涌现。这些算法可 以归纳为以下几类：层次法、划分法、基于密度的方法、基于网格的方法和基于 模型的方法。为了方便下文的算法描述，这里只介绍划分法中的一种代表算法一 - - k - m e a n s 算法。 k - m e a n s 算法以k 为参数，把拧个对象分为k 个类，使类内具有较高的相似度， 而类间的相似度较低。算法首先随机的选择k 个对象，每个对象初始地代表一个 类的平均值或中心。对剩余的每个对象根据其与各个类中心的距离，将它归并到 最近的类。然后重新计算每个类的聚类中心。这个过程不断重复，直到准则函数 收敛。准则函数如下： e = ：。艇c ( x i ) 2 ( 2 - 2 2 ) e 是所有数据对象的误差平方的总和，x 是空间中的点，表示给定的数据对象， i 是类g 的聚类中心。这个准则试图使生成的结果类尽可能的紧凑和独立。 2 2 蚁群聚类算法的基本模型 蚁群算法是最近几年才提出来的一种新型的模拟进化算法，最初由意大利学 者d o r i g o 等人提出来的，利用蚁群在搜索食物源的过程中所体现出来的寻优能 力来解决某些离散系统优化问题。随后的研究表明，蚁群算法本质上是一个复杂 的智能系统，具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法结合 等优点，逐渐成为人工智能领域的一个研究的热点，目前对其研究己渗透到多个 应用领域，近几年来它在聚类分析领域的应用也取得了很大的研究进展。 基于蚁群算法的聚类方法从原理上可以分为两种：一种是基于蚁堆形成原理 来实现数据聚类，它起源于对蚁群墓地、蚁卵的分类研究：另一种是运用蚂蚁觅 食原理，利用信息素来实现聚类分析【2 6 】。 2 2 1 基于蚁堆原理的蚁群聚类算法一模型1 以死蚂蚁堆积为例，蚁堆聚类现象的基本机制是蚁堆对工蚁搬运死蚂蚁具有 吸引。蚁堆规模的大小决定着对工蚁的吸引大小：蚁堆越大，越能吸引工蚁将死 中南大学硕士学位论文第二章蚁群聚类相关技术分析 蚂蚁堆积到该堆，使得蚁堆的规模越来越大，由此形成一个正反馈。最早提出这 种聚类分析方法的是d e n e u b o u r gjl 于1 9 9 1 年在文献 2 7 】中提出的，而后l u m e r e 和f a i e t ab 将该模型推广到了数据分析范畴 2 引，提出著名的l f 算法。其主要 思想是先将待聚类的数据对象随机地散布在一个二维平面内，然后在该平面上产 生一些虚拟的蚂蚁对其进行聚类分析。这些蚂蚁在平面中随机地选择一个数据对 象，依据该数据对象在局部区域的相似性决定自己的行为，随机地对该数据对象 执行搬运，移动，放下或者不理会这样几种行为中的一种。经过这个过程的不断 迭代，平面上随机分布的数据就按照其相似性而聚集成几个大堆。 l f 算法的伪代码如下： * i n p u t n _ a n t ，m a x _ o n ，r ，口，岛和幸岛 * i n i t i a l i z a t i o n * f o r e v e r y i t e mqd o p l a c eq r a n d o m l yo n 鲥d e n d f o r f o r a l la n t sd o p l a c ea n ta tr a n d o m l ys e l e c t e ds i t e e n d f o r * m a i nl o o p f o rc i l 2 lt om a x c 1 1d o f o r a l la n t sd o i f ( ( a n t su n l o a d e d ) a n d ( s i t eo c c u p i e db yi t e mq ) ) t h e n c o m p u t e r ( q ) a n de ( q ) d r a wr a n d o mr e a lrb e t w e e n0a n dl i f ( r 乞( q ) ) t h e n p i c k u pi t e mq 拾起规则 e n d i f e l s ei f ( ( a n tc a r r y i n gi t e m0 ：) a n d ( s i t ee m p t y ) ) t h e n c o m p u t e ( q ) a n d 只( q ) d r a wr a n d o mr e a lrb e t w e e n0a n dl i f ( r 只( q ) ) t h e n d r o pi t e mq 放下规则 e n d i f e n di f 1 2 中南大学硕士学位论文第二章蚁群聚类相关技术分析 m o v et or a n d o m l ys e l e c t e dn e i g h b o r i n gs i t ew h i c hn o t o c c u p i e db yo t h e ra n t e n d f o r e n d f o r p r i n tl o c a t i o no fi t e m s 以上算法考虑的是：在一个z x z 的网格中，蚂蚁在地点，可以观察到周围 s x s 的区域中的物体( 或者称为对象) 。对象p 在地点，与周围对象的相似度按 照下面公式来进行计算： 肥) _ m a x 愕q 1 _ 掣】 ( 2 - 2 3 ) 其中口是一个衡量相异度的参数，d ( q ，0 ，) 是两个对象q 和d ，的距离。 在l f 算法中，蚂蚁拾起或者放下一个对象d 的可能性按照如下两个公式来 计算： o ( q ) = 右高2 ，( 2 - 2 4 ) c q ，= y 昙。韶害 ( 2 。2 7 ) 桫筹蔫， ( 2 2 8 ) 其中p = ( p 。，p 2 ，p m ) 是加权因子，可以根据各个分量在聚类中的贡献不同而设 定；，为聚类半径；s = dl 如，s = l ，2 ，且j ) ，表示蚂蚁x ，可供选择的 路径；为期望启发因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中 启发信息在蚂蚁选择路径中的受重视程度；r 1 ( t ) 是指t 时刻模式样本f 分配给第 _ ，个聚类中心c ，的启发信息的数值，一般定义为两者之间距离的倒数。 五是否归并到x ，由式( 2 2 8 ) 给出，若既( f ) e o ，则五归并到x ，邻域。 当所有的蚂蚁都经过“移动”操作之后，每个类中所包含的数据对象发生了 变化，这意味着各个类的聚类中心点要重新计算，同一类内部的相异度也需要重 新计算。用c ，表示归并到x ，领域的所有数据集，新的聚类中心香，与相异度函数 值d 计算如下： 1 ， q = 专：。五，= s = l ，2 ，k ， ( 2 - 2 9 ) d = ：，：。：。( 一) 2 ， ( 2 3 0 ) 其中，j 表示c ，的元素个数，c 。表示否，的第i 个分量。 如果所有类的相异度之和小于参数g ，则聚类结束，给出分析结果；否则需 要重新进行分析，直至结束条件满足为止。 基于信息素的k - m e a n s 算法的伪代码如下： * i n p u tk , r ，p o ，s 和 * i n i t i a l i z a t i o n * 初始化聚类中心 f o r e v e r y c j d o c h o o s eu n m a r k e dx i r a n d o m l ya n ds e tc j 2 t xj 、a n dm a r kxj 1 4 中南大学硕士学位论文第二章蚁群聚类相关技术分析 e n d f o r * m a i nl o o p 幸 f o re v e r y 五( u n m a r k e da n dd i f f e