（应用数学专业论文）改进的蚁群聚类分析算法的研究.pdf

河南大学研究生硕士学位论文第1 页 摘要 数据聚类是重要的数据挖掘技术，是人们认识和探索事物之间内在联系的有 效手段，它既可以作为独立的数据挖掘工具，发现数据库中数据分布的一些深入 信息，也可以作为其它数据挖掘算法的预处理步骤，且在工程和技术领域具有广 泛的应用背景。近几十年来，国内外的研究者们提出了许多聚类算法，力图发现 最优方案。随着蚁群算法研究的兴起，人们发现在某些方面采用蚁群模型进行聚 类更加接近实际的聚类问题。 本文首先分析了聚类分析和蚁群算法。聚类分析是数据挖掘中的一个很 活跃的研究领域，主要用于在隐含的数据中发现有意义的数据分布和数据模式。 对聚类分析的定义、聚类的方法、数据类型以及聚类结果的度量标准作了简要的 介绍。蚁群算法模拟了群体智能，在解决优化处理方面发挥了很好的作用，研究 了蚁群聚类分析基本模型和蚁群聚类分析基本模型的l f 算法，分析了其算法的优 缺点。本文对基于蚁群算法的聚类分析方法及其应用展开了研究，主要工作如下： 1 、提出了基于信息素的改进的l f 算法( i l f b p ) 。由于l f 算法要设置很多的 参数，并且对参数设置比较敏感，同时由于定义了蚂蚁在二维网格中是任意移动 的，任意移动过程中对某些区域并没有数据对象，而且算法收敛速度过慢，所以 算法的聚类效果不好、效率不高。通过在改进l f 算法中群体相似度函数，加入参 数的自适应调整策略，利用短期记忆和网格信息素的局部分布控制蚂蚁的随机移 动，并结合蚂蚁速度动态变化、半径递增、强制放下等特性，提出了基于信息素 的改进的l f 算法。 2 、对改进的算法进行分析，并且通过测试数据和不同的算法进行了对比实验 分析，证明了改进算法的有效性，算法显示出了较高的稳定性和准确率。 3 、提出了蚁群聚类文档挖掘系统结构。在典型的文档挖掘流程基础上，分析 和设计了蚁群聚类文档挖掘总体结构和文档分词子系统、文档特征向量计算子系 第1 i 页河南大学研究生硕士学位论文 统及蚁群聚类分析了系统结构。 关键词：数据挖掘；蚁群算法；聚类分析；l f 算法 河南大学研究生硕士学位论文第1 1 1 页 a b s t r a c t d a t ac l u s t e r i n gi sa l li m p o r t a n td a t am i n i n gt e c h n o l o g y , i sae f f e c t i v em e a n st h a t p e o p l eu n d e r s t a n da n de x p l o r et h ei n t r i n s i cl i n kb e t w e e nt h i n g s i tc a nb eu s e da sa n i n d e p e n d e n t d a t am i n i n gt o o l sa n df o u n dt h e d a t a d e p t hi n f o r m a t i o no fd a t a b a s e d i s t r i b u t i o n i ta l s oc a l lb eu s e da so t h e rd a t am i n i n gp r e p r o c e s s i n ga l g o r i t h ms t e p s i n t h ef i e l do fe n g i n e e r i n ga n dt e c h n o l o g y , i ta p p l i e sw i l d l y i nr e c e n td e c a d e s ，r e s e a r c h e r s a th o m ea n da b r o a d ，p u tf o r w a r dan u m b e ro fc l u s t e r i n ga l g o r i t h m s ，t r y i n gt of i n dt h e b e s tp r o g r a m w i t ht h er i s eo fa n tc o l o n ya l g o r i t h m ，i tw a sf o u n dt h a ti nc e r t a i na s p e c t s o f t h eu s eo fa n tc o l o n yc l u s t e r i n gm o d e lo f t h ec l u s t e rc l o s e rt ot h ea c t u a lp r o b l e m t h i sp a p e rh a sa n a l y z e dt h ed o m e s t i ca n df o r e i g nr e s e a r c hp r e s e n ts i t u a t i o no ft h e c l u s t e r i n ga n a l y s i sa n da n tc o l o n ya l g o r i t h m c l u s t e ra n a l y s i si sav e r ya c t i v ea r e ao f d a t am i n i n g ，m a i n l yf o u n dt h em e a n i n g f u ld a t ai nt h ed a t ad i s t r i b u t i o na n dd a t am o d e l t h a tu s e di nt h ei m p l i e dd a t a i nt h i sp a p e r , t h ed e f i n i t i o no fc l u s t e ra n a l y s i s ，c l u s t e r i n g m e t h o d s ，d a t at y p e s ，a sw e l la st h er e s u l t so fc l u s t e r i n gm e t r i c sa r eb r i e f l yi n t r o d u c e d t h i sp a p e rh a sr e s e a r c h e do nt h ea n tc o l o n ya l g o r i t h m i ts i m u l a t e dt h es w a r m i n t e l l i g e n c ea n dp l a y e dav e r yg o o dr o l eo fs e t t l i n go p t i m i z a t i o no ft r e a t m e n ta n d s t u d i e dt h eb a s i cm o d e lo fa n tc o l o n yc l u s t e r i n ga n a l y s i sa n da n tc o l o n yc l u s t e r i n g a n a l y s i so ft h eb a s i cm o d e lo ft h el fa l g o r i t h ma n da n a l y z e dt h ea d v a n t a g e sa n d d i s a d v a n t a g e s o fi t s a l g o r i t h m t h et h e s i sm a i n l yf o c u s e so ns t u d y i n gc l u s t e r i n g a n a l y s i sb a s e do na n tc o l o n ya l g o r i t h ma n di t sa p p l i c a t i o n t h em a i nw o r ki n c l u d e s ： f i r s t ，i m p r o v e dl fa l g o r i t h mb a s e do np h e r o m o n ew a sp r e s e n t l fa l g o r i t h m d e m a n d e dt os e tu pal o to f p a r a m e t e r s ，w h i c ha r em o r es e n s i t i v e a tt h es a m et i m ea sa r e s u l to ft h ed e f i n i t i o no ft h ea n t si nt h et w o d i m e n s i o n a lg r i di sa r b i t r a r ym o v e m e n ta n d a n ym o v e m e n ti nc e r t a i na r e a si sn os i g n i f i c a n t ，f o re x a m p l e ，t h o s ef u n d a m e n t a ld a t a o b j e c ti sn o tr e g i o n a l ，s ot h ee f f e c to fc l u s t e r i n ga l g o r i t h m si sp o o ra n de f f i c i e n c yi sn o t h i 曲b ym o d i f y i n gt h ea l g o r i t h mt oi m p r o v et h el fg r o u p s ，t h es i m i l a r i t yf u n c t i o nb y a d d i n gp a r a m e t e r st oa d j u s tt h ea d a p t i v es t r a t e g y , t h eu s eo fs h o r t t e r mm e m o r ya n dg r i d o ft h el o c a lp h e r o m o n ed i s t r i b u t i o no ft h er a n d o mm o v e m e n tc o n 9 0 1a n t s c o m b i n e d 第1 v 页河南大学研究生硕士学位论文 w i t ht h es p e e do ft h ed y n a m i cc h a n g e sa n t s ，t h er a d i u si n c r e a s e ，s u c ha sm a n d a t o r y d o w nc h a r a c t e r i s t i c so fap h e r o m o n e - b a s e da l g o r i t h mt oi m p r o v et h el e s e c o n d ，t h i sp a p e rd e s i g n e da n di m p l e m e n t e das i m p l ea n tc o l o n ya l g o r i t h m p l a t f o r mb a s e do nc l u s t e ra n a l y s i s a l s ov i ac o m p a r ee x p e r i m e n td a t at e s t i n ga n dv a r y a l g o r i t h ma n a l y s i s ，t h ea l g o r i t h m ss h o w sp r e f e r a b l ep e r f o r m a n c e t h i r d ，t h i sp a p e rp r o p o s e dt h ea n tc o l o n yc l u s t e r i n gs t r u c t u r eo ft h ed o c u m e n t m i n i n gs y s t e m i nat y p i c a lp r o c e s st h ed o c u m e n tb a s e do nt h ee x c a v a t i o n ，w ea n a l y z e d a n dd e s i g n e do ft h ea n tc o l o n yc l u s t e r i n gm i n i n gt h eo v e r a l ls t r u c t u r eo fd o c u m e n t sa n d d o c u m e n ts e g m e n t a t i o ns u b s y s t e m ，t h ed o c u m e n tf e a t u r ev e c t o rc o m p u t i n gs u b s y s t e m a n ds u b s y s t e ms t r u c t u r eo fc l u s t e ra n a l y s i so fa n tc o l o n y k e y w o r d s ：d a t am i n i n g ；a n tc o l o n ya l g o r i t h m ；c l u s t e ra n a l y s i s ；l fa l g o r i t h m 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 丈中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 1蔓罩 学位申请人( 学位论文作者) 荟名：竺 2 0 o i 卑6 月日 关于学位论文著作权使用授权书 本人经河南大学审核 比准授干硕士学住。作为学位论文酷作者，本人完全 了解并同意河南大学有关保留i 使用擘谊论文的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电子文本) 以供公众检索、查阅。本入：授枳河彘大学出于宣扬、展览学校 学术发展和进行学术交流等目的。可塔采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) z努 学1 ：立获得者( 学位论文作者) 鍪名：竖物 2 0 学位论文指导教师签名 河南大学研究生硕士学位论文第1 页 1 1 研究背景 第一章绪论弟一早三百t 匕 数据收集和存储技术的快速发展使得各组织机构可以用来存储所产生的海量 数据，比如金融行业每天的巨额交易数据，企业运作和销售的详细情况，地球轨 道卫星发送回地球的遥感数据和高分辨率图象，人类对于越来越多的有机体所做 的基因组实验产生的结构、序列和机能数据。但是，有用的信息在减少，人们被 大量的数据所包围着，而这些数据却往往隐含着丰富的信息，怎样在这些数据集 中寻找模式、异常值和趋势，并且用简单的数据模型进行归纳，即把数据转化为 信息、将信息转换成知识，就成为了当今信息时代的巨大挑战之一。鉴于此，人 们进行了有意义的探索，通过有机的结合统计学、数据库技术、机器学习、信息 理论以及计算科学，开发出了一种新的方法一数据挖掘来解决这一难题。数据挖 掘1 1 叫是一种将传统的数据分析方法与处理复杂数据的算法相结合的技术，它能将 隐含的、尚不为人所知的，同时又是潜在有用的信息从数据中提取出来，建立了 计算机程序自动遍历数据集，来发现有意义的模式和规则。数据挖掘的目标是从 数据中发现隐含的、有意义的知识，功能包括：分类、趋势预测、关联分析、聚 类、概念描述和异常检测，它为探查和分析新的数据类型以及用新方法分析原有 数据类型提供了很好的机会，并且显示出了前所未有的强大生命力。 从2 0 世纪8 0 年代末期开始，数据挖掘技术逐步发展起来了。19 8 9 年8 月在美国 底特律召开的第1 1 届国际人工智能联合会议的专题讨论会上，首次提出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 ) 的概念，续而在19 9 1 、19 9 3 和19 9 4 年又接着 举行了k d d 专题讨论会。1 9 9 5 年美国计算机学会a c m 会议提出了数据挖掘( d a t a m i n i n g ) 的概念，自1 9 9 7 年起，数据挖掘专题杂志( ( d a mm i n i n ga n dk n o w l e d g e d i s c o v e r y ) ) 开始出版。当前，国内外在这方面已经发表了众多的研究成果和论文， 并且开发了一大批数据挖掘软件，建立了大批的相关网站，对k d d 和数据挖掘的 第2 页河南大学研究生硕士学位论文 研究已成为相关领域的一个热i 、_ j 课题，吸引了很多学术界和工业界的研究人员参 与其中。而作为数据挖掘技术之一的聚类分析也越来越受到研究者的关注。 1 2 蚁群聚类算法的研究现状 蚁群算测踊】最初由意大利学者d o r i g o m 等人于19 9 1 年首次提出，根据蚂蚁 “寻找食物”的群体行为，d o r i g o m ( e u r o p e a nc o n f e r e n c eo n a r t i f i c i a ll i f e ，e c a l ) 上最早提出了蚁群算法的基本模型，1 9 9 2 年d o r i g o m 又在其博士学位论文中进一 步阐述了蚁群算法的核心思想。在1 9 9 6 年，其又一篇奠基性文章“a n ts y s t e m ： o p t i m i z a t i o nb yac o l o n yo fc o o p e r a t i o na g e n t s ”在( ( i e e et r a n s a c t i o n so ns y s t e m s ，m a n ， a n dc y b e r n e t i c s p a r tb 上发表【引，在该文中，d o r i g o m 等不仅对蚁群算法的基本原 理和数学模型作了更加系统地阐述，还将其与遗传算法、禁忌搜索算法、模拟退 火算法、爬山法等进行了仿真实验比较，并把算法拓展到解决非对称旅行商问题 ( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 、指派问题( q u a d r a t i ca s s i g n m e n tp r o b l e m ，q a p ) 以及车间作业调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ，j s p ) ，并且对算法中初始参 数对性能的影响做了初步探讨。自1 9 9 6 年起，蚁群算法作为一种新颖的、处于前 沿的问题优化求解算法，在算法的改进、算法收敛性的证明以及应用领域方面逐 渐得到了世界许多国家研究者的关注。进入2 1 世纪，国际著名的顶级学术刊物 ( ( n a t u r e ) ) 多次报道了蚁群算法的研究成果，f u t u r eg e n e r a t i o nc o m p u t e rs y s t e m s ) ) 和( ( i e e et r a n s a c t i o no ne v o l u t i o n a r yc o m p u t a t i o n ) ) 分别出版了蚁群算法专刊。目 前，对蚁群算法及其应用的研究已经成为了国内外许多学术期刊和会议上的一个 研究热点和前沿性课题。随着蚁群算法研究的兴起，人们发现在某些方面采用 蚁群模型进行聚类更加接近实际聚类问题， 文献 7 最早提出了基于蚁堆的聚类模型，文献 8 改进了文献 7 模型，提出 了l f 算法，并首次应用于数据分析：文献 9 1 2 1 在l f 算法上，模拟了真实蚂蚁的移 动方式，减少了人工蚂蚁在无数据区域的搜索。文 1 3 模仿多蚁群的协作性能， 将运动速度类型各异的多个蚁群，独立而并行地进行聚类分析，然后组合其聚类 结果为超图，再用蚁群算法对超图进行2 次划分：文 1 4 在l f 算法中引入信息熵，改 河南大学研究生硕士学位论文第3 页 变了拾起放下规则，加快了聚类速度，减少了参数设置。 随着蚁群聚类算法研究的进一步发展，其他类型的蚁群聚类算法被相继提出。 文献 1 5 1 7 】提出了一种基于蚂蚁化学识别系统的蚁群聚类模型，该模型模拟蚂蚁 的生理机制，依靠神经元模板和气味来识别另外的蚂蚁是否和自己是同一个群体 的：文 1 8 】提出一种基于蚂蚁自我聚集行为的聚类模型，该模型用蚂蚁表示数据并 代表该树的节点。蚂蚁在这棵树上或己经固定在树上的蚂蚁身上移动，来寻找适 合自己的位置，最终形成一棵蚂蚁树：文 1 9 】提出了一种基于蚂蚁觅食原理的蚁群 聚类模型，该模型假设数据为具有不同属性的蚂蚁，聚类中心是蚂蚁所要寻找的 “食物源 ，那么数据聚类过程就可以看作蚂蚁寻找食物源的过程。 在这些蚁群聚类模型中，蚁堆聚类模型提出最早，应用也最广泛，其他的蚁 群聚类模型由于提出较晚，处于理论完善和初步应用阶段。 1 3 本文研究的主要内容及组织结构 本文主要研究的是数据挖掘核心之一的聚类分析技术及其应用。在深入研究 经典聚类分析模型和算法、基于蚁群算法的聚类分析模型的基础上，通过使用信 息素和信息熵的策略对蚁群聚类分析算法进行改进，提出了基于信息素的改进l f 算法和基于信息素和信息熵的蚁群聚类分析算法。针对客户细分和文档挖掘的特 点，研究了基于蚁群算法的聚类分析在这两个领域的具体应用，并分别给出了蚁 群聚类客户细分系统和文档挖掘系统的结构设计。本文的内容按章节组织如下： 第一章：绪论。介绍了本文的研究背景、蚁群聚类分析算法的研究现状等。 第二章：聚类分析模型及其算法设计研究。分析了经典聚类分析模型和基于 蚁群算法的聚类模型以及根据模型设计的聚类分析算法。 第三章：蚁群聚类分析算法研究。通过在蚁群聚类模型中，引入信息素的策 略，提出了基于信息素的改进的l f 算法并设计和实现了一个简单的蚁群聚类分析 平台。 第四章：基于蚁群算法的聚类分析应用研究。研究基于蚁群算法的聚类分析 文档挖掘领域的具体应用。 第4 页河南大学研究生硕士学位论文 总结和展望。对全文的内容进行概括总结，提出对未来工作的展望。 河南大学研究生硕士学位论文第5 页 第二章聚类分析模型及其算法研究 聚类分析是数据分析中的一种重要技术，它在应用方面非常广泛。在很多的领 域中都会涉及到聚类分析方法的应用和研究工作，例如数据挖掘、统计学、生物 学、空间数据库、电子商务等。 2 1 聚类分析的概念 聚类分析作为数据挖掘和知识发现的一种非常重要的方法，与分类规则所不 同的是，聚类所要求划分的类是未知的，它是典型的无指导学习算法【2 0 1 。聚类 分析即将物理的或抽象的对象集合分组成，有相似的对象组成的多个类的分析的 过程，它输入的是一组未分类的对象，而且事先不知道如何分类，也不知道要分 成几类，其输出是通过分析数据，按照某个特定标准( 通常是某种距离) 合理划 分数据集，确定每个对象所属的类别，把相似性大的对象聚集为一个类。聚类过 程本身就是一个发现知识的过程，聚类结果可以用来解释数据分布的本质的特征。 2 2 数据对象的表示和相似度计算 聚类分析往往都是针对具体问题所进行处理，要进行聚类的数据集的数据类 型也是各种各样的，这就需要对这些经常出现的数据类型进行了预处理，不同数 据类型的聚类处理的方法也有差别。因此，聚类分析模型的建立和算法的设计往 往都是针对不同的数据类型，许多聚类分析算法的设计是针对处理连续型的数据 集，如k 均值算法、c l a s s i t 算法，有些算法的设计是针对处理离散型的数据集， 如c o b w e b 算法。 假设数据集合中有甩个数据对象，这些数据对象可能表示人、房子、文档、国 家等。数据矩阵或称为对象与变量结构( d a t a m a t r i x ) 用厂个变量来表现，z 个对象， 这种数据结构可看成，2 p 的矩阵，如图2 - 1 所示，其中每个行向量代表一个数据 对象。相异度矩阵或称为对象与对象结构( d i s s i m i l a r i t ym a t r i x ) ，保存，2 个对象两 第6 页河南大学研究生硕士学位论文 两之间的相似性，表示形式是一个玎门维的矩阵，如图2 - 2 所示，其中d ( f ，) 是 对象i 和对象j 之间相似性的量化表示，通常为一个非负数，当对象i 和对象越 相似，其值越接近0 ，反之，其值越大，而且d ( i ，) = d ( ，i ) ，d ( i ，i ) = o 。 五i x l f x l p x i i x 口x l p x h l x n f 图2 1 数据矩阵 o d ( 2 ，1 ) 0 d ( 3 ，1 ) d ( 3 ，2 ) 0 ： d ( n ，1 ) d ( n ，2 ) 0 图2 - 2 相异度矩阵 聚类就是根据对象之间的相似性将数据集划分成为若干类或簇的过程，使用 相异度矩阵中的数据来进行对象的聚类计算。当数据对象的属性的取值类型不同 时，计算相似度时也采用了不同的计算方法f 2 2 1 。通常要进行聚类的数据集的数据 类型包括区间标度变量、二元变量、标称变量、序数变量和混合类型的变量。其 中区间标度变量是连续型的，二元变量、标称变量和序数变量是离散型的。 对于区间标度变量，假设有f 个对象，描述第i 个对象的p 个属性值分别对应 于区间变量值x t 。，薯：，描述第个对象的p 个属性值分别对应于区间变量值 工1 ，z 2 ，z 加，其中f ，j 1 ，2 ，z ，那么对象i 与之间的差异度一般以它们之间 的距离d ( i ，) 来表示。距离越近，表明对象f 与，之间越相似，差异越小；距离越 远，表明对象f 与7 之间越不相似，差异越大。最常用的相似度度量是欧几里德距 离( 也称欧氏距离) ，其定义如下： 河南大学研究生硕士学位论文第7 页 d ( i ，) = 如一_ ，| 2 + | 一：，：| 2 + - + l 一1 2 ( 2 - 1 ) 这里的f = ( z ”：，) 和= ( x j ，：，x 归) 是两个p 维的数据对象。另一个著名 的度量方法是曼哈坦距离，其定义如下： d ( i ，) = i t ，一_ 。l + i 一：一t ：l + + x i p - - x m l ( 2 - 2 ) 明考斯基距离是上述两种距离的概化，它的定义如下： d ( f ，) = i x , ，一_ 。1 9 + i x i ：一_ ：1 9 + + i 一1 9 ) “9 ( 2 - 3 ) 这里的g 是一个正整数。当q = l 时，它表示曼哈坦距离；当q = 2 时，它表示欧氏 距离。若根据每个属性变量的重要性对其给予一个权重，就可得加权的距离度量 【2 4 1 ，例如加权的明考斯基距离定义如下： 棚= 矿。l q + “2 2 i t ：一。：卜+ u p 卜) 9 ( 2 - 4 ) 其中咄。表示第k 个属性变量的权重，k 1 ，2 ，p ) 。 由于区间标度变量所采用的度量单位将会对聚类分析的结果产生直接的影 响。为了避免属性对度量单位选择的依赖，首先要对数据进行标准化，对于给定 的一个变量厂的度量值，可以用标准化的度量值z s c d ，p 进行标准化： z 矿：垃 ( 2 5 ) ! s f 其中s f 是平均绝对偏差。= ( x l f - - m ：l + t x 2 f - - m f l + + l x n y - - m f f ) ， 五，j c 2 ，勺是f 的，z 个度量值，朋，是厂的平均值，且口m f - - i i ( _ ，+ j c 2 ，+ + ) 。 2 3 经典聚类分析模型及其算法设计研究 聚类分析都是以数据为基础的，因而聚类模型要按照不同的数据类型来建立。 据聚类分析对数据的不同的表述思想，通常的聚类模型可划分为两大类，基于层 次的模型和基于划分的模型，前者是从树状图的角度来描述数据，而后者是采用 第8 页河南大学研究生硕士学位论文 类原型来进行数据的描述。有了聚类模型就可以做聚类算法的设计，但是通常会 由于具体的优化或求解算法策略的不同，针对同一个聚类模型所设计出来的算法 差别就比较大。针对这两类模型的聚类算法设计中通常包括三个方面的内容：数 据对象和类之间距离即相似度的定义，聚类形成过程中的调整策略和聚类结束所 需满足的条件。 目前存在着许多的聚类分析模型和算法，算法的选择取决于数据的类型、聚 类的目的和应用。如果聚类分析被用作描述或探查的工具，可以对同样的数据尝 试多种算法，以发现数据可能揭示的结果【2 3 1 。主要的聚类分析算法如图2 3 所示， 主要分为以下几类：层次的方法、划分的方法、基于密度的方法、基于网格的方 法和基于模型的方法。基于具体的实现技术，层次的聚类可分为凝聚算法和分裂 算法，基于模型的方法主要有统计学方法和神经网络方法。 2 3 1 层次的方法 图2 3 聚类分析算法的分类 层次的聚类方法是发展的比较早、应用非常广泛的一大类聚类分析方法，它 将数据对象组成一棵聚类的树，采用自底向上或自顶向下的策略在不同的层次上 对对象进行了分组，形成的一种树形的聚类结构。凝聚的层次聚类采用自底向上 的策略，这种方法首先将每个对象看作为一个类，然后不断地合并最接近的对象 或类，直到所有的类合并为一个，或者是满足某个终止条件。该方法包括绝大多 河南大学研究生硕士学位论文第9 页 数层次聚类的方法，只是不同的方法在类之间相似度的定义上有所差异。下面就 表述了基本凝聚层次聚类算法的过程。分裂的层次聚类采用了自顶向下的方法， 这种策略就是从包含的所有对象的一个类开始，每一步就分裂成一个类，直至仅 仅剩下了有单个对象组成的类。但在这种情况下要确定每一步都分裂哪个类以及 如何进行分裂。 基本凝聚层次聚类算法： 1 计算了邻近度的矩阵。 2 r e p e a t 3 把最近的两个类进行合并。 4 更新了邻近度矩阵，反映了新的类与原来的类之间的邻近度。 5 u n t i l 仅剩一个类。 常用的度量类之间距离的四种方法为： l 最小距离，d 嘶( c ，c ，) = m i n 雕一吒l p p 。i ； 2 最大距离，( e ，c t ) = m a x ，c i p p i ； 3 平均值的距离，k ( c ，q ) = k ，- m 小 4 平均距离，( c ，q ) 2 去，。c ，tp - p l 这里 p - p 。i 是两个对象p 和p 7 之间的距离，m 。是类c 1 的平均值，而_ 是类c i ； 中对象的数目。 传统的层次聚类方法有凝聚的方法a g n e s ( a g g l o m e r a t i v en e s t i n g ) 和分裂的 方法d i a n a ( d i v i s i v ea n a l y s i s ) 。其优点是算法思想比较直观、简单，易于理解和 应用。缺点是要面对的一个非常重要的问题是如何选择合并点( 自底向上) 或者分 裂点( 自顶向下) ，在每次合并或分裂之后，下一步的聚类过程要在新生成的类上 继续进行，而且已做的处理不能撤消，无法返回到合并或分裂前的状态重新开始， 类之间也不能进行对象的交换，如果某一步的合并点或分裂点选取的不是很合理， 就可能导致形成低质量的聚类结果；其它的不足主要有缺乏全局目标函数和处理 第1o 页河南大学研究生硕士学位论文 不同大小的聚类的能力，各个类的大小和其中对象分布形状都会影响聚类结果， 在某些有比较特殊的对象分布形状的情况下，可能会产生错误的聚类结果【z 5 1 。 针对传统层次聚类方法的不足，近年来，出现了一些采用凝聚的层次聚类策 略的改进算法，通过将其它的聚类分析技术和层次的聚类方法进行集成，形成多 阶段聚类。例如，c u r e ( c l u s t e r i n gu s i n gr e p r e s e n t a t i v e s ) 算法，r o c k 算法， b i r c h ( b a l a n c e di t e r a t i v er e d u c i n ga n d c l u s t e r i n gu s i n gh i e r a r c h i e s ) 算法， c h a m e l e o n 算法。 2 3 2 划分的方法 划分的聚类方法也是发展比较早、也是比较基本的一大类聚类分析方法，不 像层次的聚类方法那样需要几个步骤，而是在一步中产生所有的类。它是一种基 于原型的聚类方法，算法的基本思路是：首先从数据集中随机地选择几个对象作 为聚类的原型，然后，对于其它对象，根据其与原型所代表的类之间的相似度， 分别分配到由原型所代表的最相似( 也就是距离最近) 的类中。对于划分的聚类 方法，一般需要一种迭代控制策略，对原型不断地进行调整，从而使得整个聚类 得到优化，例如使得各对象到其原型的欧氏距离最小。存在许多划分的聚类方法， 但是k 均值算法和k 中心点算法是最为突出的两个。k 均值算法定义原型为质心 ( 一组点的均值) ，常用于”维连续空间中的对象。k 中心点算法定义原型为中心 点( 一组点中最有代表性的点) ，由于它只需要对象之间的邻近性度量，故可以应 用的数据较为广泛。 1 、k 均值算法 k 均值算法是聚类分析中一种最古老的、使用最广泛的迭代聚类算法。假设有 n 个对象需要分成k 类，那么在足。均值算法中，首先随机地选择k 个对象代表k 个 类，每一个对象作为一个类的初始质心，然后将其它对象分配到距离其最近的质 心中。在完成首次对象的分配之后，以每一个类中所有对象的各属性均值作为该 类的新的质心，进行对象的再分配，重复该过程直到类不发生变化或者质心不发 河南大学研究生硕士学位论文第11 页 生变化为止，从而得到最终的k 个类。 k 均值算法中，聚类的个数k 是必须预先指定的参数。下面描述了基本k 均值 算法的过程。 基本k 均值算法： 1 、随机的选择k 个对象最为初始质心。 2 、r e p e a t 3 、将每个点指派到最近的质心，形成k 个类。 4 、重新计算每个类的质心。 5 、u n t i l 质心不发生变化 为了克服随机选择初始质心存在的局限性，一种有效的方法是使用其它聚类 方法对数据集进行初始聚类，并用这些初始结果类的质心作为初始质心。另一种 选择初始质心的方法是随机地选择第一个点，第二个选取点为离第一个选取点最 远的点，依次选取每个初始质心，使之为距离所有已经选取的初始质心最远的点， 这样就得到一个随机和分散的初始质心集合。 k 均值算法的优点是不仅简单有效，而且可以用于多种数据类型，其很多变种 都能克服随机选择初始质心的局限性，如二分k 均值算法。其缺点是k 均值算法并 不能很好的处理具有非球形形状、不同尺寸和不同密度的类；对包含异常点的数 据进行聚类时，也存在问题；并且常常会收敛于局部最优解，而不是全局最优解； 最后k 均值算法仅限于具有质心概念的数据。 2 、k 中心点算法 为了克服k 均值算法中的多种局限性，一种改进的方法是使用中心点作为一个 参考点代替k 均值算法中各类的质心作为聚类中心。并根据所有数据对象与各参考 点之间的相似度之和最小化的原则，继续应用划分方法。 k 中心点算法的基本策略是：首先为每个类任意的找到一个代表对象作为各个 类的中心点；再根据剩余对象与中心点之间距离最近的原则确定每个数据对象所 归属的类；接下来，反复地用非代表点来替换类中心点，如果替换后可以改善聚 第12 页河南大学研究生硕士学位论文 类质量，就用一个新数据对象替换老数据对象作为类代表点，并重新对各个数据 对象进行分配，直至收敛。聚类结果的质量可用一个度量对象与其参照对象之间 平均相似度的代价函数来估算。比较著名的k 中心点算法有p a m ( p a r t i t i o n i n g a r o u n d m e d o i d s ) 算法c l a r a ( c l u s t e r i n g l a r g ea p p l i c a t i o n ) 算法及 c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o n sb a s e du p o nr a n d o m i z e ds e a r c h ) 算法。 基本k 中心点算法 l 、随机选择k 个对象作为各个类的初始中心点。 2 、 r e p e a t 3 、根据距离类中心点最近的原则分配每个剩余的对象。 4 、随机的选择一个非代表对象0r a n d o m 5 、计算用0 ，口行a t o m 代替回的总代价s 。 6 、如果s ( 2 - d e cm a x d i a m ( e ) 7 ) c ， p 印 其中，c 是所有聚类的集合，聚类c 的直径d i a m ( e ) 是该类内部的最大距 离，6 ( 心，心) 是聚类c 和d 的中点之间的距离。 通常，在数据集的类结构比较明显的情况下，大部分评价方法都能做出较好 的评价。而在数据集的类结构比较特别的情况下，这些聚类有效性的评价方法并 不能都能做出合适的评价。 2 5 基于蚁群算法的聚类分析模型研究 随着蚁群算法研究的发展，人们发现在某些方面采用了蚁群模型进行聚类分 河南大学研究生硕士学位论文第15 页 析就会更加接近于实际的聚类问题。通过模拟了自然界中蚂蚁的群体的行为，人 们提出了很多基于蚁群的聚类分析模型【2 8 】。这些模型按照其所借鉴的蚂蚁群体行 为上的差别，从原理上可以分为基于蚂蚁构造墓地和分类幼体的聚类分析模型( 蚁 群聚类分析模型) 、基于蚂蚁觅食行为和信息素的聚类分析模型等。 与经典的聚类分析模型相比较，基于蚁群的聚类分析模型具有许多的优点： 该类模型往往是独立于所要处理的聚类分析的问题，能够按照数据对象的本身特 征自动的产生聚类的数量，而且能够较好的处理噪声数据和异常值，能够用来处 理不同维度的数据集，能够非常容易的实现了数据可视化等。但是许多经典的聚 类分析模型不仅要求用户事先设定结果聚类的个数，然后通过数据来适应它，往 往还是针对某一类特定的聚类分析问题的模式。另外，基于蚁群的聚类分析模型 还具有蚁群算法的灵活性、优良的分布式控制、自组织、自学习和较强的鲁棒性 等特征，在进行聚类分析时更加的接近实际的聚类问题，非常容易的发现数据集 中真实的内部的结构信息。 2 。5 1 基于蚂蚁构造墓地和分类幼体的聚类分析模型 蚁群构造墓地行为和分类幼体行为统称之为蚁群聚类行为。生物学家经过长 期的观察发现，在蚂蚁群体中存在一种本能的聚集行为。蚂蚁往往能在没有关于 蚂蚁整体的任何指导性信息情况下，将其死去的同伴的尸体安放在一个固定的场 所。c h r 6 t i e nl 用l a s i u sn i g e r 蚂蚁做了大量试验研究蚂蚁的这种构造墓地行为， 发现工蚁能在几小时内将分散在蚁穴内各处的任意分布、大小不同的蚂蚁尸体聚 成几类；d e n e u b o u r g 儿等人也用p h e i d o l ep a l l i d u l a 蚂蚁做了类似的实验。另外观 ，察还发现，蚁群会根据蚂蚁幼体的大小将其放置在不同的位置，分别把其堆放在 蚁穴周围和中央的位置。真实的蚁群聚类行为的实验结果如图2 - 4 所示，四张照 片分别对应为实验初始状态、3 小时、6 小时和3 6 小时的蚁群聚类情况。这种蚁 群聚集现象的基本机制是小的聚类通过已聚集的蚂蚁尸体发出的信息素来吸引工 蚁存放更多的同类对象，由此变成更大的聚类。在这种情况下，蚁穴环境中的聚 类分布特性起到了间接通信( s t i g r n e r g y ) 的作用。 第16 页河南大学研究生硕士学位论文 图2 - 4 真实蚁群的聚类行为 引对蚂蚁构造墓地和分类幼体的本能所表现出来的聚类行为现象，d e n e u b o u r g 儿等人提出了蚁群聚类的基本模型( b m ) ”慵来解释这种现象，指出了单个的对 象会比较容易被拾起而且移动到其它具有很多这类对象的地方。 基本模型经过利用个体与个体和个体与环境之间的交互作用，实现了自组织 聚类，并成功的应用于机器人的控制中( 一群类似于蚂蚁的机器人在二维网格中 随意移动并可以搬运基本物体，最终把它们聚集在一起) 。该模型成功的应用引起 了各国学者的广泛关注和研究的热潮。l u m e r e 和f a i e t a b 通过在d e n u r b o u r g 的基 本分类模型中引入数据对象之间相似度的概念，提出了l f 聚类分析算法，并成功 的将其应用到数据分析中。 252 基于蚂蚁觅食行为和信息素的聚类分析模型 蚂蚁在觅食的过程中，能够分为搜索食物和搬运食物两个环节。每个蚂蚁在 运动过程中都将会在其所经过的路径上留下信息索，而且能够感知到信息素的存 在及其强度，比较倾向于向信息素强度高的方向移动，同样信息素自身也会随着 时间的流逝而挥发，显然某一路径上经过的蚂蚁数目越多，那么其信息素就越强， 以后的蚂蚁选择该路径的可能性就比较高，整个蚁群的行为表现出了信息正反馈 河南大学研究生硕士学位论文第17 页 现象。 通过借鉴这一蚁群生态原理，基于蚂蚁觅食行为和信息素的聚类分析模型的 基本思想是将数据看作是具有不同属性的蚂蚁，聚类中心就被视为蚂蚁所要寻找 的“食物源”，所以，数据聚类过程就能看作是蚂蚁进行找寻食物源的过程。该模 型的算法流