（计算机软件与理论专业论文）微粒群算法在聚类分析及qos组播路由中的应用研究.pdf

山东大学硕士学位论文 摘要 随着计算机应用技术的迅速发展，人们对高效优化技术和智能计算技术提 出了更高更新的要求，并用于求解各种工程问题优化解的应用技术，在诸多工 程领域得到普遍的应用。鉴于实际工程问题的复杂性、约束性、非线性、多局 部极小和建模困难等特点，寻找各种适合于工程实践需求的新型智能优化方法 一直是许多学科的一个重要研究方向。 微粒群算法作为一种新兴的智能计算技术已成为越来越多研究者的关注焦 点。它与人工生命，特别是进化策略以及遗传算法有着特殊的联系。群智能在 没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方 案提供了基础。 本文分别阐述和分析了微粒群算法在聚类分析和多约束组播路由问题上的 应用。在聚类分析方面，提出了基于空间特性p s o 理论的混沌聚类算法，并在 其基础上扩展了对最终聚类不明确的聚类问题的一般性解决办法；在多约束组 播路由问题上，有别于传统方法，采用树形变换方法，依托于微粒群理论对组 播路由进行了求解。 ( 1 ) 目前，主要的聚类算法可以分为如下几类：划分方法、层次方法、基 于密度的方法和基于网格的方法等。很多方法需要一些条件的限制，需要设定 聚类的数目，而且聚类结果往往对初始状态及参数非常敏感。k m e a n s 聚类算 法就是这样一种代表性的聚类算法，其最后的聚类效果受到初始聚类中心的影 响很大，结果往往是局部最优解，为了得到较优的聚类结果，计算复杂度迅速 增大。而一个稳定的( 对初始中心不敏感) 且可以收敛到全局最优的算法是实 际工业中所需要的。本文在p s o 算法的基础上提出了s p a ( s p a t i a lp s oa l g o r i t h m ) 聚类算法，在p s o 算法中引入粒子的内部空间特性，以确保聚类算法中的类内 数据尽可能相似，类间数据差异尽可能明显这一特性。同时，为了解决p s o 算 法可能出现的早熟问题，本文算法也引入了混沌的思想。仿真实验也表明，算 法在数字属性的聚类问题上表现出良好的求解能力，通过引入内部空间特性和 混沌思想，算法求解的平均性能也有显著的改善。 i ji 东大学硕士学位论文 ( 2 ) 针对k m e a m 等聚类算法，初始需要指定聚类数目的问题，本文通 过引入贝叶斯信息决策的思想，提出了x s p a ( x s p a t i a lp s oa l g o r i t h m ) 聚类算 法，使得算法可以在运行的过程中，通过判断自动的进行聚类数目的调整，实 验结果也表明，算法不但给出了较准确的聚类类别数目，并且聚类的准确度也 有了一定的上升。 ( 3 ) 本文提出了一种基于树的微粒群算法p s o t r e e 。与传统组播路由算 法的先寻找路再合成树的模式不同，p s o t r e e 采用了以树生长的方式直接寻找 组播树的模式。基于树的p s o 算法简化了寻树的机制，算法的效率得到了提高。 仿真实验结果表明，跟传统算法相比，p s o t r e e 算法能以更快的速度收敛到近 似最优解，组成员数目越多，这种优点越明显，提高了算法的效率。仿真实验 结果表明，跟原算法相比，算法在仿真网络拓扑上收敛速度更快，效率更高。 关键词：微粒群；空间特性p s 0 ；聚类；组播；服务质量：树形变换 i i 山东大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e ra p p l i c a t i o nt e c h n o l o g y , e f f i c i e n t o p t i m i z a t i o nt e c h n i q u e sa n di n t e l l i g e n tc o m p u t i n gt e c h n o b g yh a sp u tf o r w a r d h i g h e rr e q u i r e m e n t st ou p d a t ea n dh a sb e e nu s e di nav a r i e t yo fe n g i n e e r i n g p r o b l e m s i nv i e wo f p r a c t i c a le n g i n e e r i n gd i f f i c u l t i e s ，s u c ha sc o m p l e x i t y , c o n s t r a i n , n o n - l i n e a r , m a n yl o c a lm i n i m aa n dd i f f i c u l t i e si nm o d e l i n gf e a t u r e s ，an e w t y p eo f i 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 sw h i c hm e e tt h ep r a c t i c a le n g i n e e r i n gn e e dh a s b e c o m ea ni m p o r t a mr e s e a r c hd i r e c t i o n p a r t i c l es w a r mo p t i m i z a t i o na sa ne m e r g i n gs m a r tc o m p u t i n gt e c h n o b g yh a s b r o u g h tm o r ea n dm o r er e s e a r c h e r s f o c u s i th a ss t r o n gr e l a t i o n s h i pw i t ha r t i f i c i a l l i f e ，e s p e c i a l l yw i t ht h ee v ol u t i o ns 仃a m g ya n dg e n e t i ca l g o r i t h m i nt h ea b s e n c eo f c e n t r a l i z e dc o n t r o la n dn e e dn o tt o p r o v i d et h eo v e r a l li n f o r m a t i o n , s w a r m i n t e r l l i g e n c eh a sp r o v i d e dt h ef o u n d a t i o nt ol o o kf o rc o m p l e xd i s t r i b u t e ds o l u t i o n s t h i sp a p e rd e s c r i b e da n da n a l y z e dt h ep a r t i c l es w a r ma l g o r i t h mi nc l u s t e r a n a l y s i sa n dm u l t i - c o n s t r a i n tm u l t i c a s tm u t i n gp r o b l e ma p p l i c a t i o n i nc l u s t e r a n a l y s i s ，t h ep a p e rp r o p o s e sp s oc l u s t e r m ga l g o r i t h mw i t hs p a c et h e o r ya n dc h a o t i c c h a r a c t e r i s t i c s ，a n db a s eo ni t s ，t h ep a p e ra l s oe x t e n d st h ea l g o r i t h mt og i v eag e n e r a l a l g o r i t h m t os o l v e c l u s t e r i n g w i t hn o s p e c i f i c c l u s t e rn u r r b e r s ；i nt h e m u l t i - c o n s t r a i n e dm u l t i c a s t r o u t i n gp r o b l e m , u n l i k et r a d i t i o n a lm e t h o d s ，t h e a l g o r i t h mu s et r e et r a n s f o r r m t i o nm e t h o d ，r e l y i n go nt h ep a r t i c l es w a r mt h e o r yt o s o l v i n gt h em u l t i c a s tr o u t i n gp r o b l e m ( 1 ) a tp r e s e n t , t h ec l u s t e r i n ga l g o r i t h mc a nb ed i v i d e di n t ot h ef o l l o w i n g c a t e g o r i e s ：p a t i t i o nm e t h o d s ，h i e r a r c h i c a lm e t h o d s ，d e n s i t y b a s e dm e t h o d sa n d g r i d - b a s e dm e t h o d s m a n yw a y sn e e dp e o p l et op r o v i d es o m ec o n s t r a i n s ，s u c ha s c o n f i g u r et h en u n 出e ro fc l u s t e r , a n dc l u s t e rr e s u l t sa r eo f t e nv e r ys e n s i t i v ew i t ht h e i n i t i a ls t a t ea n da l g o r i t h m p a r a m e t e r s k m e a n sc l u s t e r i n ga l g o r i t h mi st h e r e p r e s e n t a t i o no fs u c hac l u s t e r i n ga l g o r i t h m , t h ef i n a lc l u s t e r i n ge f f e c tb yt h ei n i t i a l 1 【j 东大学硕十学位论文 c l u s t e rc e n t e ro fg r e a ti n f l u e n c e ，t h er e s u l ti so f t e nt h el o c a lo p t i m a ls o l u t i on , i n o r d e rt oo b t a i nb e t t o rc l u s t e r i n gr e s u l t s ，c o m p u t a t i o n a lc o m p l e x i t yi n c r e a s e sr a p i d l y a n das t a b l ea n dc a nc o n v e r g et og l o b a lo p t i m a la l g o r i t h mi st h ea c t u a li n d u s t r y n e e d s t h i sp a p e rba s e do np s o a l g o r i t h mp r o p o s e st h es p a ( s p a t i a lp s oa l g o r i t h m ) a l g o r i t h m , i no r d e rt oe n s u r et h a tt h ed a t ai nt h es a m ec l u s t e ra r es i m i l a ra n dt h ed a t a i nt h ed i f f e r e n tc l u s t e r sa r eu n s i m i l a r , t h ea l g o r i t h mi n t r o d u c e ss p a t i a lt r a i t si nt h e p a r t i c l e a tt h es a 瑚et i m e ，i no r d e rt os o l v et h ep s oa l g o r i t h mp r e c o c i o u sq u e st i o n s ， i ti n v o l v e st h ec h a o t i ci d e a s i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h md o e sw e l li n d i g i t a lp r o p e r t i e sc l u s t e rp r o b l e mt h r o u g ht h ei n t r o d u c t i o no fi n t e r i o rs p a c ef e a t u r e s a n dc h a o so f t h o u g h t , t h ea v e r a g ep e r f o r m a n c eh a sa l s ob e e ns i g n i f i c a n t l yi m p r o v e d ( 2 ) a sf o rk - m e a n sc l u s t e r i n ga l g o r i t h m , t h ea l g o r i t h mn e e dt os p e c i 矽t h e n u r r b e ro fc l u s t e r i n gp r o b l e mi nt h eb e g i n i n g ，t h ep a p e ri n v o l v e st h eb a y e s i a n i n f o r m a t i o nd e c i s i o ni d e ai nt h ea l g o r i t h m , a n dp u tf o r w a r dt h ex s p a ( x - s p a t i a l p s o a l g o r i t h m ) c l u s t e r i n ga l g o r i t h mt h ex s p aa l g o r i t h mc a na d j u s ta n dc a l c u l a t e t h er e a lc l u s t e rn u m b e ri nt h ep r o c e s so f r u n n i n ga l g o r i t h mt h ee x p e r i m e n t a lr e s u l t s a l s os h o wt h a tt h ea l g o r i t h mn o to n l yg i v ean d r ea c c u r a t en u m b e ro fc l u s t e r c a t e g o r i e sa n da l s oah i 【g ha c c u r a c yo fc l u s t e r i n g ( s ) i nt h i sp a p e r , w ep r o p o s e at r e e b a s e dp a r t i c l es w a r mo p t i m i z a t i o n p s o t r e ea l g o r i t h mt os o l v em u l t i c a s tr o u t i n gp r o b l e m u n i i k i n gt r a d i t i o n a l a l g o r i t h r mw h i c hu s u a l l yf i n de v e r yr o a df r o mt h es o u r c en o d et oe v e r yd e s t i n a t i o n n o d ea n dt h e nc o n v e r tt h e mt oam u l t i c a s tt r e e ，p s o t r e ea l g o r i t h mu s eap a t t e r n w h i c hd i r e c t l yc a l c u l a t em u l t i c a s tt r e e p s o - b a s e dt r e ea l g o r i t h mh a ss i m p l i f i e dt h e s e a r c ht r e er m c h a n i s m , a n dt h ea l g o r i t h me f f i c i e n c ya l s oh a sb e e ni m p r o v e d s i m u l a t i o nr e s u l t ss h o wt h a tc o m p a r e d 、i t ht r a d i t i o n a la l g o r i t h r m , p s o t r e e a l g o r i t h mc a nf a s t e rc o n v e r g et ot h ea p p r o x i m a t eo p t i m a ls o l u t i o n , e n h a n c et h e e f f i c i e n c y , t h en l o r et h en u r r 玉e ro f g r o t pm e m b e r s ，t h em o r eo b v i o u sa d v a n t a g e s k e y w o r d ：p a r t i o l e8 w a r mo p t i m i z a t i o n ( p s o ) ：s p a t i a lo h a r a g t e r i s t i c p s o ：c i u s t e r i n g ：m u i t i o a s t ：0 0 8 ：t r e e b a s e dt r a n s p o r t i o n 原创性声明和关于论文使用授权的声明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 敝储虢堑# 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：雄聊签名：础日期：出 l j 东大学硕士学位论文 第一章绪论 1 1 课题提出的背景和意义 优化技术是一种以各种形式的数学处理方法为基础，用于求解各种工程问 题优化解的应用技术，在诸多工程领域得到了普遍的应用。微粒群优化算法【l ，2 】 是i 扫k e n n e d y 和e b e r h a r t 提出的基于群体的随机优化技术，是模仿鸟群行为，通 过个体之间的合作和竞争完成进化和寻优的过程的算法。自从算法提出后，由 于其概念简明、实现方便，在短期内迅速得到了国际演化计算领域的认可，并 且由于其在解决复杂的组合优化类问题方面所具有的优越性能，因而在工程设 计优化、电力系统领域、机器入控制和工业生产优化领域等都取得了较为成功 的应用。 聚类分析 3 ，4 】作为实际工程中迫切需要解决的组合优化问题，由于数据挖 掘所面对的数据对象趋复杂，聚类方法的研究也面临更多新的内容和挑战。 目前主要的聚类算法可以分为如下几类：划分方法、层次方法、基于密度的方 法和基于网格的方法等。很多方法需要一些条件的限制，需要设定聚类的数目， 而且聚类结果往往对初始状态及参数非常敏感。聚类算法结果往往是局部最优 解，为了得到较优的聚类结果，计算复杂度迅速增大。因此这就让微粒群算法 在聚类分析上有了应用的可能性，通过群体智能的高效性，良好的寻优能力也 会在聚类分析上找到较好的解。 q o s 5 ，6 】组播路由 7 ，8 】是网络分布式多媒体实时信息传输的关键之一， 正1 f 已经提出了多种服务模型和机制来满足各种q o s 组播的需求，在这方面 已有不少的研究成果。实时应用往往会对延时，延时抖动，带宽，丢失率，业务 代价等多个参数同时提出性能要求。这些参数相互独立时，选择满足多个参数 限制的最优组播路由就成为n p 完全问题。这种多约束的优化问题也是的微粒群 适合该问题的求解。 1 2 国内外研究现状 微粒群算法具有概念简单、实现容易等突出优点，因此，在短短的几年问， 山东大学硕十学位论文 微粒群算法获得了很大的发展，并在一些领域得到了成功的应用。目前已被国 际演化计算会议0 e c ) y u 为专题之一，标志着微粒群算法的研究得到了国际上的 支持。对于解决组合的多约束优化问题，表现出良好的求解能力和寻优能力。 聚类分析在发展过程中己经取得了丰硕的成果，但还存在许多问题，尤其 随着数据挖掘技术的广泛应用，聚类的研究对象也随之更加丰富，这就要求对 现有聚类技术进行改进，同时不断提出新的聚类理论和方法以适应新的应用。 因此，群体智能算法逐渐被运用到聚类算法当中，如神经网络【9 】，免疫算法【l o 】， 蚁群算法 1 l - 1 3 1 等群体智能算法【1 4 】及遗传算法【1 5 】等。同时，很多方法需要一 些条件的限制，需要设定聚类的数目，而且聚类结果往往对初始状态及参数非 常敏感。k m e a n s 聚类算法【1 6 】就是这样一种代表性的聚类算法，其最后的聚类 效果受到初始时聚类中心的影响很大，结果往往是局部最优解，为了得到较优 的聚类结果，计算复杂度迅速增大。而一个稳定的、对初始中心不敏感且可以 收敛到全局最优的算法是实际工业中所需要的。 目前，在q o s 组播路由的研究领域中，研究人员已经提出了一些用于解决 多约束q o s 组播路由问题的算法。这些算法大体上可分为启发式算法、近似算 法和基于某种调度策略的多约束q o s 组播路由算法这三类。近年来，国内外许多 学者利用神经网络 1 7 】、蚁群算法【1 8 】、遗传算法【1 9 】等启发式智能算法来解决 约束q o s 组播路由问题，并且取得了一定的成果。但都存在着进行大规模优化 时，初期收敛速度慢、收敛时间过长、易陷入局部最优解。针对这些缺陷，近 年来众多国内外学者在算法的改进方面做了大量的研究工作。当前的微粒群算 法被应用到组播路由算法 2 0 2 2 中，又仅限于对搜索路径或者是候选路径的选 择，并没有从直观的角度上，以树的形式对组播路由问题进行求解，并且许多 改进都是基于t s p 问题，由于网络环境的复杂特性，并不适用于多约束q o s 的组 播路由优化问题。如何利用网络现有条件对算法进行改进，用于解决多约束q o s 组播路由问题是一个值得研究的课题。 1 3 主要研究内容 目前微粒群算法运用到聚类分析和多约束q o s 组播路由等方面上并不多 见，而微粒群算法在解决多约束的优化问题上的优势是显而易见的。随着人们 2 i ij 东大学硕士学位论文 对解决优化问题的更新更快的要求，这种应用的需求将会迅速的提升。本课题 的主要研究目标是研究微粒群算法对解决聚类分析和多约束q o s 组播路由算法 及有关技术。主要研究内容包括： 一、文章在p s o 算法的基础上提出了s p a ( s p a t i a lp s oa l g o r i t h m ) 聚类算法， 通过将的内部空间特性引入p s o 算法的粒子中，确保了聚类算法中的类内数据 尽可能相似，类间数据差异尽可能明显这一特性。算法也引入了混沌的思想用 于克服p s o 算法可能出现的早熟问题。仿真实验表明，在数字属性的聚类问题 上，算法表现出良好的求解能力，求解的平均性能也有显著的改善。 二、针对k - m e a n s 等聚类算法，初始需要指定聚类数目的问题，文章中引 入贝叶斯信息决策的思想，提出了x - s p a ( x s p a t i a lp s oa l g o r i t h m ) 聚类算法。 在算法运行的过程中，通过判断自动的进行对聚类数目的调整，实验结果也表 明，算法不但给出了较准确的聚类类别数目，并且在聚类的准确度上也有不错 的表现。 三、基于树的q o s 组播路由微粒群优化算法及其改进算法。本文提出了一 种基于树形变换的微粒群算法p s o t r e e 。p s o t r e e 算法与传统组播路由算法 的先寻找路再合成树的模式不同，采用了以树生长的方式直接寻找组播树的模 式。该算法简化了寻树的机制，使得算法效率得到了提高。仿真实验结果表明， 跟传统算法相比，p s o t r e e 算法能以更快的速度收敛到近似最优解，组成员数 目越多，这种优点越明显，提高了算法的效率。跟传统算法相比，算法在仿真 网络拓扑上收敛速度更快，效率更高。 1 4 论文组织框架 本论文的其余部分可以分为六章。 第二章对微粒群算法做详细介绍。其中，2 1 阐述了微粒群算法的原型及 提出；2 2 描述微粒群算法；2 3 介绍了微粒群算法的基本流程。 第三章对聚类问题作了简单的介绍。其中，3 1 对聚类分析中距离和判断 准则进行了定义，3 2 简单介绍了目前的各类聚类算法。 第四章介绍了内部空间特性p s o 聚类算法。4 1 给出了聚类问题的数学模 型；4 。2 对内部空间特性的混沌p s o 聚类算法s p a 作了详细的描述，包括编 山东大学硕士学位论文 码形式，算法步骤以及算法复杂度分析等；4 3 给出了s p a 算法的仿真实验和 结果分析；4 4 介绍了未知类别数目下的空间特性p s o 聚类算法x - s p a ，并介 绍了对聚类问题数学模型的改造以及对聚类类别数目x 的合理估计。4 5 给出 了x s p a 的仿真实验和结果分析。 第五章介绍了q o s 组播路由问题及其解决方法。其中，5 1 介绍了传统组 播路由算法；5 2 介绍了q o s 组播路由的模型；5 3 详细介绍了q o s 组播路由 的策略等情况。 第六章介绍了树型变换的微粒群组播路由算法p s o t r e e 。其中，6 ，1 描述 了组播路由问题的数学模型；6 2 详细的描述了p s o t r e e 的算法设计及模型 改造，介绍了树型变换的思想及其实现方式，算法的详细步骤和复杂度分析等； 6 3 对p s o t r e e 算法进行了仿真实验，并对仿真结果进行了分析和评价。 最后一章是对所做工作的总结和对下一步研究工作的展望。 4 山东大学硕士学位论文 第二章微粒群算法 自然界中，鸟群的运动的模型是离散的，其排列开起来是随机的，但在整 体的运动中它们却保持着惊人的同步性，其整体运动形态非常流畅而极富美感。 这种模型关键在于个体间距离的运算操作，即群体行为的同步性在于个体努力 维持自身与邻居之间的距离为最优。受到鸟群运动模型的影响，社会心理学博 士j a m e sk e n n e d y 和电子工程学博士r u s s e l le b e r h a r t 于1 9 9 5 年提出了微粒群算 法。微粒群算法是一种演化计算技术，该算法中将鸟群运动模型中的栖息地类 比于所求问题解空间中可能解的位置，通过个体间的信息传递，引导整个群体 向可能解的方向移动，在求解过程中逐步增加发现较好解的可能性。群体中的 鸟被抽象成没有质量和体积的微粒，通过这些微粒间的相互协作和信息共享， 使其运动速度受到自身和群体的历史运动状态信息的影响，以自身和群体的历 史最优位置来对微粒的当前运动方向和运动速度加以影响，较好的协调微粒本 身和微粒运动之间的关系，以利于群体在复杂解空间中进行寻优的操作。 2 1 基本微粒群算法的提出 微粒群算法的思想来自于社会认知( s o c i o c o n g n i t i v e ) 理论。根据社会认知理 论，我们可以将微粒群算法问题求解概括为以下三个方面：评价、比较和模仿。 评价过程是对各种激励进行评估，根据正反馈或负反馈、吸引或排斥等激 励特性对其进行排序。有机生命只有通过对外界激励的评价，才能完成对环境 的学习。微粒群对环境的学习，自适应学习过程也包含这样一种评价过程。 比较过程是指微粒群中的个体对其他个体标准进行评价测量，并与自身条 件相比较，从而确立自身的学习和修正动机。 模仿的过程是微粒群中的个体根据自身判断模拟其他个体行为的过程，这 是自然界中普遍存在的一种非常有效的学习模式。通常模拟那些优于自身的个 体。 以上三个过程的有机结合即可构成一种能够适应复杂环境变化、解决困难 问题的简单社会个体，并以计算机程序形式实现。 i ii 东大学硕士学位论文 基于协作模式用社会学观点对鸟群运动进行了诠释，k e n n e d y 和f o e r h a r t 等于1 9 9 5 年发表论文p a r t i c l es w a r m o p t i m i z a t i o n 1 】，正式提出微粒群算法。微 粒群算法利用群体中的个体对信息的共享，使整个群体的运动在问题解空间中 产生从无序到有序的演化过程，从而获取最优解。 2 2 基本微粒群算法描述 微粒群算法是一种基于迭代模式的优化算法，最初被用于连续空间的优化， 在连续空间坐标系中，微粒群算法的数学描述如下： 设微粒群规模为，其中每个微粒i ( i = 1 ，2 ，朋在d 维空间中的坐标位置可 设置为x j = ( x a , x 口，芦涵芦动，微粒i ( i = - 1 ，2 ，朋的速度定义为每次迭代中微粒 移动的距离，用v 产p 玎, v i e , ，v d , 动表示。于是，微粒i ( = 1 ，2 ，朋在第d ( 出，1 ，2 ，捌维子空间中的飞行速度r i d 根据下式进行调整： = 颤o v i a + q r a n d l ( ) ( p i d 一嘞) + c 2 r a n d 2 0 ( p s a 一砀) w h e r e 2 吒“，矽砜“ 【v i a2 一。，矿1 = 0 ：距离是一个非负数值 ( i i ) d ( x t 歹t ) = 0 - 对象与自身的距离是零 ( i i i ) d ( x f ，点，户d ( 誓萨小距离函数具有对称性 ( i v ) 踯j 力卜i 踯f ，敬卜硪x 七劫：而到x j 的距离不会大于而到溉和x k 到而的 距离之和( 三角不等式) 。 3 1 。2 聚类准则的确定 有了相似性测量函数，下一步要确定的是采用的聚类准则。聚类准则是聚 类分析算法的关键，通常有两种确定方式： ( 1 ) 试探方式：凭主观和经验，针对实际问题定义一种相似性测度的阈值， 然后按最近邻规则指定某些对象属于某一聚类。例如使用欧氏距离，它反映的 是对象之间的近邻性，在将一个对象分到两个类别中的一个时，必须规定一个 距离测度的阈值作为聚类的判别准则。 ( 2 ) 聚类目标函数法：由于聚类是将对象进行组合分类以使类别可分离性最 大，因此聚类准则应是反映类别间相似性或相异性的函数。但每个类是由一个 个对象所组成，所以一般说来，类别的可分离性与对象的相异性直接有关。这 样，定义一聚类目标函数c ，应是对象集合扣) 和聚类类别 蚵= l ，2 ，c ) 的函数， 其中c 是聚类数目的个数。该过程使聚类分析转化为寻找准则函数极值的最优 化问题。一种常用的指标是误差的平方和，即： c = 壹卜1 1 2 j = ls j 其中，m l , m 2 ，用。是聚类中心，西是中心为聊，的聚类域。 朋，：i 1 _ z x m j2 i 穹 。 m 为s 中的对象个数，这里以均值向量m j 代表薄聚类域。 上式表明，c 代表了分别属于c 个类别的全部对象与其相应类中心之间的 误差平方和。使c 值极小的聚类就是我们的目的。这种类型的聚类通常称为最 iji 东大学硕士学位论文 小方差划分，它适用于各类对象密集且数目相差不多，而不同类间的对象又明 显分开的情况。当不同类中的对象数目相差很大时，采用误差平方和作为准则 函数，有时还可能把对象多的一类分拆为二，因为这样分拆其误差平方和的数 值会更小，这样就会造成错误聚类，此时就须采用别的准则函数。 3 2 聚类算法的分类 聚类分析算法取决于数据的类型、聚类的目的和应用。大体上可以分为以 下几类t 划分方法，层次方法，基于密度的方法，基于网格的方法，基于模型 的方法等。另外，根据聚类间重叠程度可分为t 硬聚类和模糊聚类。 3 2 1 划分方法 划分方法 2 4 】创建数据集的一个单层划分：给定一个包含刀个对象的数据 集和要构建的划分数目k ，划分方法首先创建一个初始划分，然后采用一种迭 代的重定位技术，尝试通过对象在划分间的移动来改进划分。也就是说，它将 数据划分为k 个组，同时满足以下的要求：每个组至少包括一个对象；并且每 个对象必须属于且只属于一个组( 硬划分) 。为了达到全局最优，基于划分的聚 类会要求穷举所有尽可能的划分。该方法的典型代表是k - m e a n s 算法 1 6 】， k - m e d o i d s 算法【2 5 】。 k 1 l 】e a n s 算法先找到k 个中心点，然后将每个点分配到离它最近的中心点所 代表的类中。基本算法如下：先随机选取k 个对象作为聚类的中心，将其余的 对象分配给离它最近的中心，然后更新各个聚类中心，重复以上过程，直到各 类的中心点不再变化。这种算法试图找到数据集的k 个划分使得一个准则函数 得到优化，即类中的每个样本点( 数据或对象) 到该类中心的聚类平方之和。 当样本数据是类球形分布，并且各个类的数据量相差不大的时候，k m e a n s 算法的效果较好。但是，k m e a n s 算法经常以局部最优结束，并且需要给出数 据的平均值，不适合处理有分类属性的数据。k t i t a n s 算法生成的聚类数是预 先给定的，不能动态的添加新的聚类，也是该算法的一个缺点。该算法对差别 很大带有孤立点数据的类的聚类效果不是很好，并且对初始值的选取敏感。 依据类中心点选取策略，聚类过程中类中心点的调整策略，以及距离函数 1 2 山东大学硕士学位论文 定义的不同，k - n 呛a m 算法有很多变种。k - m e d o i d s 算法对小的数据集合非常有 效，但对大的数据集合没有良好的可伸缩性。 3 2 2 层次方法 基于划分的聚类算法获得的是单级聚类，而层次聚类 2 6 1 是将数据集分解 成几级进行聚类，层的分解可以用树形图来表示。根据层次分解的形成方式， 层次的方法可以分为凝聚( a g g l o m e r a t i v e ) 的和分裂( d i v i s i o n ) 的。凝聚的方法，也 称为自底向上的方法，一开始将每个对象作为单独的一个组，然后不断地合并 相近的对象或组。分裂的方法，也称为自顶向下的方法，一开始将所有的对象 置于一个类中，在迭代的每一步中，一个类被不断的分裂为更小的类。相对于 划分算法，层算法不需要指定聚类数目，然而在凝聚或者分裂的层次聚类算法 中，用户可以定义希望得到的聚类数目作为一个约束条件。 在层次聚类中，类的合并和分解要按照一定的相似性或相异性度量原则。 在非单点的类进行合并或分裂时，四个广泛采用的类间度量方法如下： 最小距离： ( c ，c j ) = i i l i n p 由。p 的fp - p 。l 最大距离： ( c ，q ) = 血1 脚，p - 财lp p 平均值的距离：如绷( g ，q ) = j 竹一 平均距离： c c f ，c ：，) 2 南磊p 毛l p 叫 这里 p - p 1 是两个对象p 和p 之间的距离，m ，是类g 的平均值，而胁是类 g 中对象的数目。 b i r c h 2 7 算法是一个较为有效的综合的层次聚类方法。它引入了两个概 念：聚类特征和聚类特征树。聚类特征是一个反映类内对象信息的三元组，包 含类内数据点的个数、线性和以及平方和。聚类特征树是高度平衡树，它用来 存储聚类特征。每个非叶子节点存放的是其字节点聚类特征的和。聚类特征树 有两个参数：分支因子和阈值，前者指定每个非叶子节点的子节点最大数目， 后者指定存放在叶子节点中的聚类的最大直径，这两个参数影响树的大小。 b i r c h 算法采用一种多阶段聚类技术：数据集的单遍扫描产生了一个基本的聚 山东大学硕十学位论文 类，多遍额外扫描可以进一步改进聚类质量。该算法具有对噪声不敏感的优点， 对数据量具有线性伸缩性，并且对增量或动态聚类也非常有效。但是与经典的 划分方法聚类一样，如果数据集不是球形分布的，b i r c h 算法则不能很好的工 作，因为它用了半径或直径的概念来控制聚类的边界。 层次的方法缺陷在于，没有全局待优化的目标函数；合并或分裂点的选择 困难，往往好的局部合并选择不能保证高质量的全局聚类结果；对噪声、孤立 点敏感，不适于非凸型分布数据集；一旦一个步骤( 合并或分裂) 完成，它就不 能被取消。一些方法可以改进层次聚类的结果：( 1 ) 在每层划分中，仔细分析对 象间的联系；( 2 ) 综合层次凝聚和迭代的重定位方法，首先采用自底向上的层次 算法，然后用迭代的重定位来改进结果：( 3 ) 将层次聚类和其它的聚类技术进行 集成，形成多阶段聚类。 3 2 3 基于密度的方法 绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球 状的类，而在发现任意形状的类上遇到了困难。基于密度的聚类的主要思想是： 只要临近区域的密度( 对象或数据点的数目) 超过某个阂值就继续聚类。也就是 说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数 目的点。这样的方法可以用来过滤噪声和孤立点数据，发现任意形状的类。 d b s c a n 2 8 ( d e n s i t yb a s e ds p a t i a lc l u s t e r i n go f a p p l i c a t i o n sw i t hn o i s e ) 算 法是一个有代表性的基于密度的方法。它根据一个密度阈值来控制类的增长， 将具有足够高密度的区域划分为类，并可在带有“噪声”的空间数据库中发现任 意形状的聚类。其主要思想是：一个类中每一个点关于一个给定半径的邻域内 必须至少包含一定数量的点，即邻域的密度必须超过一个定值。 3 2 4 基于网格的方法 基于网格的方法把对象空间量化为有限数目的单元，形成一个多分辨率的 网络结构。所有的聚类都是在这个网络结构( 即量化的空间) 上进行。这种方法 的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量 化空间中每一单元的数目有关。 1 4 1jj 东大学硕士学位论文 基于网格的有代表性的算法包括：s t i n g 【2 9 ( s t a t i s t i c a li n f o r m a t i o ng r i d ) 算法，s t 玳g 将空间区域划分为不同级别分辨率的矩形单元，这些单元形成了 一个层次结构，高层的低分辨率单元被划分为多个低一层的较高分辨率单元。 从最底层的网格开始逐渐向上计算网格内数据的统计信息并存储。网格的建立 完成后，就可以用类似d b s c a n 的方法对网格进行聚类。s t i n g 算法基于网 格结构有利于并行处理和增量更新，聚类效率很高。但是该算法聚类质量取决 于网格结构的最底层的粒度。较低的粒度使得计算代价显著增加，而过粗的粒 度会降低聚类质量。而且，s t i n g 在构件一个父单元时没有考虑子单元间的关 系，导致所有聚类边界只能是水平的或竖直的，没有对角的边界，因此可能降 低聚类的质量。 3 2 5 孤立点分析 经常存在一些数据对象，它们不符合数据的一般模型，这样的数据对象被 称为孤立点( o u t l i e r ) 。孤立点可能是度量或执行错误所导致，也可能是数据突变 的结果。许多数据挖掘算法试图使孤立点的影响最小化，但由于噪声与信号的 相对性，孤立点本身有可能包含重要的信息，因此在某些情况下，如金融和商 业欺诈检测，网络入侵异常监测等，孤立点分析就显示出重要的作用， 孤立点挖掘可以描述如下：给定一组刀个数据对象的集合和预期的孤立点 数目k ，发现与其它的数据相比是显著差异的、异常的、或不一致的前k 个对 象。孤立点挖掘问题可以看作在给定的数据集合中定义孤立点并找到一个有效 的方法来挖掘这样的孤立点。 当聚类算法将孤立点作为噪声剔除时，从另一方面看，同时也进行孤立点 的探测。因此，孤立点分析也成为一类数据聚类问题。基于计算机的孤立点分 析方法分为三类：统计学方法、基于距离的方法和基于偏离的方法。 各种聚类方法在不同的问题中有不同的表现，而且一些聚类算法本身就集 成了多种聚类方法的思想，所以有时将某个给定的算法划分为某一特定的类是 很困难的。此外，某些应用可能有特定的聚类标准，要求综合多种聚类技术。 不同方法的有效结合来解决实际问题成为聚类挖掘的