（计算机应用技术专业论文）基于文化算法的聚类分析研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 聚类分析作为一种信息处理手段近些年来一直受到人们的关注， 而且在机器学习：模式识别、数据挖掘、信息检索等很多领域得到 了广泛的研究和应用。 聚类分析在数据挖掘研究中占有重要的位置。所谓聚类，就是将 物理或抽象对象的集合划分成为由类似的对象组成的多个类的过 程。聚类分析依据的原则是使同一类中的对象具有尽可能大的相似 性，而不同类中的对象相似性较小。 文化算法是一种新的进化计算方法，文化进化过程除了传统的进 化计算模型具有的群体空间外，增加了一个知识空间和支持这两个 空间通信的机制，将文化算法用于聚类分析中，有助于对聚类算法 的进一步优化。 。 本文以文化算法为框架，采用k m e a n s 模型为聚类模型，针对聚类 问题设计适用于该问题的知识空间、群体空间、接受函数和影响函 数。提出文化算法与k m e a n s 算法相结合的混合聚类算法。首先在混 合算法的群体空间采用遗传算法，并在知识空间采用形势知识，标 准化知识，地形知识三种知识做指导，提出k c a g a 算法；然后，在 混合算法的群体空间采用进化规划，提出k c a e p 算法，针对采用不 同的影响函数和不同的知识指导，并分别细化为以下几种算法： k c a e pi ，k c a e pi i ，k c a e pi ，k c a e pi i ，k c a e p 和k c a e p 。 对知识空间知识的研究表明，在知识空间采用形势知识，标准 化知识，地形知识三种知识做指导的方法比仅仅采用形势知识，标 准化知识两种知识指导的方法聚类效果更好，对影响函数的改进避 免聚类过早收敛于局部解。 最后，通过实验对比，表明混合算法对解决聚类问题初始化敏感 以及容易陷入局部优化取得很好的效果，并有较好的收敛性，适用于 聚类问题的解决。 关键词：数据挖掘；聚类分析；文化算法：进化规划；遗传算法； a bs t r a c t a sab a s i cm e a n so fi n f o r m a t i o n p r o c e s s i n g ，c l u s t e r i n ga n a l y s i s t e c h n o l o g yh a sb e c o m ep e o p l e sc o n c e r ni nr e c e n ty e a r s c l u s t e r i n g a n a l y s i sh a sa l s og a i n e daw i d er a n g eo fr e s e a r c ha n da p p l i c a t i o ni n m a c h i n e l e a r n i n g ，p a t t e r nr e c o g n i t i o n ，d a t a m i n i n g ，i n f o r m a t i o n r e t r i e v a la n dm a n yo t h e rf i e l d s c l u s t e r i n ga n a l y s i si sa ni m p o r t a n t p a r to ft h e d a t am i n i n g r e s e a r c h c l u s t e r i n g i st h e p r o c e s so fg r o u p i n gt h ep h y s i c a lo r t h e a b s t r a c to b j e c ts e ti n t oc l a s s e so rc l u s t e r s ，s ot h a tt h eo b j e c t sw i t h i nt h e s a m ec l u s t e rh a v eh i g hs i m i l a r i t yi nc o m p a r i s o nt oo n ea n o t h e r ，b u t1 0 w s i m i l a r i t yi nd i f f e r e n tc l u s t e r s c u l t u r a la l g o r i t h m si san e we v o l u t i o n a r ym o d e l t h ea l g o r i t h mi s d u a li n h e r i t a n c es y s t e m st h a tb e s i d e st h ep o p u l a t i o nc o m p o n e n tw h i c h t r a d i t i o n a l e v o l u t i o n a r yc o m p u t a t i o nm e t h o d sh a v e ，t h e r ei sa n a d d i t i o n a l p e e rc o m p o n e n tb e l i e f s p a c e a n da s u p p o r t i n g c o m m u n i c a t i o nm e c h a n i s mb e t w e e nt h o s et w oc o m p o n e n t s 1m sp a p e r p r o p o s e s an e wh y b r i d c l u s t e r i n ga l g o r i t h m ，t h i s a l g o r i t h mt a k e st h ec u l t u r a la l g o r i t h m sa saf r a m e ，u s e st h ek m e a n s a l g o r i t h ma sc l u s t e r i n gm o d e l ，a n dd e s i g n sb e l i e fs p a c e ，p o p u l a t i o n s p a c e ，a c c e p tf u n c t i o na n di n f l u e n c ef u n c t i o nf o r s p e c i a lc l u s t e r i n g p r o b l e m f i r s t ，g e n e t i ca l g o r i t h mw a su s e di np o p u l a t i o ns p a c e a tt h e s a m e t i m e ，s i t u a t i o n a l k n o w l e d g e ，n o r m a t i v e k n o w l e d g e a n d t o p o g r a p h i ck n o w l e d g ew e r eu s e di nb e l i e fs p a c ef o rg u i d a n c e 。s ot h e a l g o r i t h mn a m e dk c a g aw a s p r e s e n t e d t h e n ，e v o l u t i o n a r v r r o g r a m m i n gw a su s e di np o p u l a t i o ns p a c es ot h a tt h ea l g o r i t h mn a m e d k c a e pw a sp u tf o r w a r d b a s e do nd i f f e r e n t b e l i e fs p a c e ，i n f l u e n c e f u n c t i o n ，k c a e pw a sd i v i d e di n t o d i f f e r e n tv e r s i o n s ：k c a e pi ， k c a e pi i ，k c a e pi ，k c a e pi i ，k c a e p i ，a n d k c a e p i v t a k er e s e a r c ho nb e l i e fs p a c e ，e x p e r i m e n t ss h o wt h a tt h r e ek i n d so f k n o w l e d g es u c ha ss i t u a t i o n a lk n o w l e d g e ，n o r m a t i v ek n o w l e d g e a n d 西南交通大学硕士研究生学位论文第1 i i 页 t o p o g r a p h i ck n o w l e d g eu s e di nb e l i e fs p a c ef o rg u i d a n c ec a nr e s u l ti n m o r ee f f i c i e n tc l u s t e r i n gr e s u l t s ，w h i c ha r eb e t t e rt h a nb o t hs i t u a t i o n a l k n o w l e d g e a n dn o r m a t i v e k n o w l e d g e u s e d a n dt h e i m p r o v e d i n f l u e n c ef u n c t i o nc a na v o i dt h ec l u s t e r i n gr e s u l t st r a p p i n gi nl o c a l m i n i m a e x p e r i m e n t ss h o wt h a t t h i s a l g o r i t h m c a nn o to n l ya v o i dt h e d i s a d v a n t a g e so ft h ec l a s s i c a lk - m e a n sc l u s t e r i n ga l g o r i t h m ，b u ta l s o h a v eg r e a t e rs e a r c h i n gc a p a b i l i t yg l o b a l t y t h en e wa l g o r i t h ma c h i e v e d g o o dr e s u l t sa p p l yt or e s o l v et h ec l u s t e r i n gp r o b l e m k e yw o r d s ：d a t am i n i n g ；c l u s t e r i n ga n a l y s i s ；c u l t u r a la l g o r i t h m ； e v o l u t i o n a r yp r o g r a m m i n g ；g e n e t i ca l g o r i t h m 一i m西南 交通大学硕士研究生学i 位论文 一 -_l-liill-lll 西南交通大学曲南交遗大罕 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、7 使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密口，使用本授权书。 ( 请在以上方框内打吖”) 学位论文作者签名：张凉 日期：。口口8 岁i ， 指导老师签名： 褐衣 日期：跏f 岁i7 一一一一一一酉直銮重拦巫盟奎圭兰箜篮窭一一一一一 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所 得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 1 ) 将一种新进化计算的方法，文化算法用于聚类分析中，有助于对聚类算法的 进一步优化研究。本文将文化算法与k - m e a n s 算法相结合，应用于聚类分 析上。首先在文化算法与k m e a n s 算法结合算法的群体空间采用遗传算法， 并在知识空间采用形势知识，标准化知识，地形知识三种知识做指导，实验 表明，改进的算法k c a g a 能提高收敛速度，改善聚类效果。 2 ) 在文化算法与k m e a n s 算法结合算法的群体空间采用进化规划，提出 k c a e p 算法，针对采用不同的影响函数和不同的知识指导，细化为 k c a e pi ，k c a e pi i ，k c a e p i ，k c a e p i v 四种算法。在人工数据集、u c i 数据集及w e b 数据集上的多组实验表明，利用标准化知识调整变量变化步 长及变化方向的算法在收敛速度和聚类效果上要优于利用标准化知识调整 变量变化步长，形势知识调整其变化方向的方法，此外，知识空间采用形势 知识，标准化知识，地形知识三种知识做指导的方法比仅仅采用用形势知识， 标准化知识两种指导知识的方法聚类效果更好。总的来说，四种算法能改善 聚类效果，并且有较好的收敛速度，其中k c a e p i v 最优。该算法对于w e b 数据聚类有一定的改善。 3 ) 对影响函数的改进，实验表明，使用改进的影响函数的算法避免聚类过早收 敛于局部解，且能取得更好的聚类效果。 西南交通大学硕士研究生学位论文第1 页 1 1 本文研究背景 第1 章绪论 计算智能( c o m p u t a t i o n a li n t e l l i g e n c e ) 是进化计算与人工神经网 络、模糊系统理论综合形成的一个新的研究方向。计算智能是从模 拟自然界生物体系和生物智能现象发展而来，并用计算机模拟和再 现生物体的某些智能行为。计算智能领域非常广泛，从方法上讲， 目前计算智能主要包括模糊控制、神经网络、进化计算、群体智能、 免疫算法和d n a 计算等。计算智能的最大特点就是不需要建立问题 本身的精确模型，适合于解决那些因为难以建立有效的形式化模型， 而用传统智能技术难以有效解决甚至无法解决的问题。 聚类分析是数据挖掘研究领域中一个非常重要的研究课题。所谓 聚类，就是对数据集中的数据应用某种方法进行分组，使得每组内 部的数据尽可能相似而不同组之间的数据尽可能不同，即“物以类 聚”，从而发现数据集内在的结构。聚类可以帮助人们更快的找到所 需要的信息，因此，聚类在现实生活中有着很重要的意义。现在， 聚类分析己成为一个非常活跃的研究课题。 计算智能是受生物体系的某些机制启发而产生的，用于聚类分析 。时，会继承生物系统的良好处理机制和特征，对模型有自然的描述 能力，并不需要建立精确的数学模型，并且有良好的自适应能力， 此外生物系统的多变性和多样性，也带来了处理目标的多样性。 本文将计算智能中的进化计算方法，应用到聚类分析中，有助 于聚类算法的进一步优化，也对进化计算的方法的进一步研究提供 了广泛的思路。 西南交通大学硕士研究生学位论文第2 页 1 2 国内外研究现状 近年来，基于自然选择和遗传学的进化计算方法在人工智能的研 究中取得了令人瞩目的成果。进化计算的典型算法就是遗传算法。 l9 7 5 年，美国密哥根大学的心理学教授、电子工程学与计算机科学 教授j o h n h h o l l a n d 和他的同事及学生们共同研究了具有开创意义 的遗传算法理论和方法。遗传算法是一种借助自然界自然选择和进 化机制发展起来的高度并行、随机、自适应搜索算法。由于其思想 简单、易于实现以及表现出来的健壮性，遗传算法在问题求解、优 化和搜索、机器学习、智能控制、模式识别和人上生命等应用领域 都取得了许多令人鼓舞的成就。 目前的进化计算的许多研究还集中在生物自然选择这一层面上， r e y n o l d s 于1 9 9 4 年提出的文化算法【1 1 ( c u l t u r a la l g o r i t h m ) 能使种群 以一定的速度进化和适应环境，这个速度超越了单纯依靠生物自然 选择使种群进化的速度。 近年文化算法及其应用这一领域引起了国际上很多学者的关注， 该算法作为一种新的进化计算方法，在理论和应用上还处于起步阶 段，国外学者对此作了一些研究，国内研究还较少。在国外文化算 法已经成功用于解决约束单目标优化，多目标优化，图象分割等问题， 并在工程领域，工业，语意网络，作业调度中也取得较好的效果。， 1 9 9 7 年，r e y n o l d s 等【2 】对进化规划( e p ) 中的自适应使用文化算法 的框架，并应用解决函数优化问题，结果证明比自适应e p 在性能上 有很大提高。特别是使用知识指导e p 中的变异操作，不仅提高效率， 也能提高精确度。知识空间的知识影响变异操作有两种方式，一是 决定步长：二是决定变化的方向。根据知识空间知识的不同种类和 影响变异操作的方式有四种文化e p 版本，在大多数情况下，使用n 。 能产生较好的性能。( 1 ) c a e p ( n 。) ：对群体空间的个体仅使用标准化 知识决定变异的步长；( 2 ) c a e p ( n 。+ s d ) ：使用标准化知识决定变异 的步长，并使用形势知识决定变异方向；( 3 ) c a e p ( n 。) ：只使用标 准化知识决定变异的步长和方向；( 4 ) c a e p ( s 。) ：使用形势知识决定 变异的方向。 19 9 8 年，r e y n o l d s 和a 1 s h e h r 使用以文化算法为框架的进化规划 西南交通大学硕士研究生学位论文第3 页 指导决策树【3j 。 2 0 0 0 年，s a l e e m 4 】首次使用文化算法处理动态优化问题，并对文 化算法和自适应e p 的性能进行了比较，显示出文化算法在所有实验 中性能优于自适应e p 。 r e y n o l d s 和c h a n j i nc h u n g 在文化算法中使用模糊的方法【5 1 。群体 空间使用进化规划的方法，知识空间使用标准化知识和形势知识， 而接受功能的评价使用模糊推理引擎。研究表明，有两中基本种类 的信息对指导个体选择非常有效，一种是世代数，另一种是当前群 体的性能。这里用个体的成功率以及当前的世代数作为模糊推理引 擎的输入，从而决定可接收的个体数。通过3 4 个函数实例的测试证 明，使用模糊接受函数比使用其他函数作为接受函数，使得c a e p 的 性能有很大提高，并且，模糊接受函数结合c a e p ( n 。) 能产生最优 效果，但是与c a e p ( n 。) 和c a e p ( n 。+ s 。) 的结合效果一般。r e y n o l d s 和z h us h i n i n 使用完全模糊文化算法解决非线形实值函数优化问题【6 】， 即在文化算法的每个部分都使用模糊数学模型，在搜索效率上，系统 成功率和c p u 时间都有很大提高。使用模糊接受函数能使系统有较高 的成功率，并且单独使用模糊接受函数，比单独使用模糊知识空间 和模糊影响函数有更大的性能改善。 2 0 0 2 年，j i nx 和r e y n o l d sr 将文化算法框架用于数据挖掘中【7 】， 知识空间由数据库中的记录组成，群体空间的可看作约束优化过程， 知识空间处理来自群体空间的知识，相当于数据挖掘的过程。 2 0 0 3 年，r e y n o l d s ，r 和s t e f a n ，j 【8 】提出了一种扩展的文化算法框 架，并将这种框架应用到网页搜索和网络服务中去，产生语意丰富的 信息的精练查询。文化算法的框架提供了增加为特定领域设计的知 识成分的灵活性，能在知识空间容纳新成分，这种结构可以用于群 体空间中多重群体和多重进化操作。 2 0 0 6 年r e y n o l d s 等使用文化算法的框架，使用比较流行的机器学 习技术集成学习到进化过程中【9 】。集成学习天然适用于文化算法的框 架，知识空间中的五种知识源是文化算法框架中集成进化的依据。 实验证明这种方法在优化应用方面的优势。 在国内，2 0 0 5 年，杨海英等将文化算法用于解决布局优化问 题【l 引。为了提高粒子群优化( p s 0 ) 算法的计算精度和计算效率，避免 西南交通大学硕士研究生学位论文第4 页 “早熟”，将p s 0 纳入文化算法框架，组成基于p s 0 的主群体空间和 知识空间两空间，两空间具有各自群体并独立并行演化。在以卫星 舱和印刷电路板布局设计为背景的算例中进行了数值验证，结果表 明，该方法的计算精度和计算效率比遗传算法g a 和p s 0 高。艾景波等。 提出一种负载均衡的自适应机制【1 1 】，将文化算法应用到对服务器性 能权值的进化计算中，通过评价服务器的负载状况，获得优化的性 能权值，并自适应地转换到集群的分配器中，使事务在集群系统中 得到合理分配。2 0 0 6 年，刘纯青等等将文化算法用于聚类分析中【l2 1 ， 提出了两个实现版本，一是利用标准化知识调整变量变化步长，形 势知识调整其变化方向：二是利用标准化知识调整变量变化步长及 变化方向，取得了较好的聚类效果。 文化算法在国内研究尚属起步阶段，但在国际的应用研究已经 成为一个热点，特别在解决优化问题上取得了很好的效果，在数据 挖掘领域有着广泛的应用前景。将文化算法用于聚类分析中，有助 于对聚类算法的进一步优化，也有助于文化算法理论上的完善和进 一步推广。 1 3 本文主要内容 本论文的主要研究工作包括几个方面： 第1 章为本文绪论部分。首先分析了本文的选题背景和研究意义， 然后介绍了国内外研究现状。 第2 章是有关聚类分析的研究。对聚类分析的概念、产生和发展 进行了简要的归纳和总结，同时对主要聚类算法进行了详细的介绍。 第3 章对进化计算方法进行了介绍，介绍了基本的遗传算法， 遗传规划等进化计算方法。 第4 章介绍了本文采用的新的进化计算方法，文化算法，介绍 了该算法的起源，步骤，以及特点，给出了文化算法和k m e a n s 算 法相结合的混合聚类算法，在文化算法的知识空间分别采用遗传算 法和遗传规划两种方法，分别介绍了其的基本思想和算法的具体步 骤。 第5 章对本文提出的混合算法进行实验分析，分别对知识空间 西南交通大学硕士研究生学位论文第5 页 采用遗传算法和遗传规划两种方法进行实验，并且对知识空间采用 进化规划的情况，又对采用不同知识进行指导的情况以及采用不同 影响函数的情况进行实验。最后将算法应用到w e b 数据集中进行聚 类分析，将实验结果进行比较分析。 西南交通大学硕士研究生学位论文第6 页 2 1 聚类概述 第2 章聚类分析 聚类( c l u s t e r i n g ) 是一种常见的数据分析工具，是一个将数据集 划分为若干组( c l a s s ) 或类( c l u s t e r ) 的过程，并使得同一个类内的数据 对象具有较高的相似度；而不同类中的数据对象相似度较低。相似 或不相似的描述是基于数据描述属性的取值来确定的，通常是利用 ( 各对象间) 距离来进行表示的。 聚类的严格数学描述如下： 被研究的样本集为e ，类c 定义为e 的一个非空子集， 即cce ，且c o 聚类就是满足下列两个条件的类g ，g ，q 的集合： 1 ) c luc 2u uq = e 2 ) qr 、c ，= o ( 对任意i j ) 由第一个条件可知，样本集e 中的每个样本必定属于某一个类； 由第二个条件可知，样本集e 中的每个样本最多只属于一个类。 2 2 聚类算法的要求 数据聚类分析是一个正在蓬勃发展的领域。聚类分析所涉及的 领域包括：数据挖掘、统计学、机器学习、空间数据库技术、生物学 和市场学等。由于各应用数据库所包含的数据量越来越大，聚类分 析已成为数据挖掘研究中一个非常活跃的研究课题。 在机器学习中，聚类分析属于一种无( 教师) 监督的学习方法。与 分类学习不同，无( 教师) 监督学习不依靠事先确定的数据类别，以及 标有数据类别的学习训练样本集合。正因为如此，聚类分析又是一 种通过观察学习方法( 1 e a r n i n gb yo b s e r v a t i o n ) ，而不是示例学习 ( 1 e a r n i n gb ye x a m p l e ) 。在概念聚类方法中，仅当一组对象可以由一 个概念所描述时，这些对象方才能构成一个类。这与基于几何距离 表示相似程度并进行聚类的传统聚类方法有所不同。概念聚类方法 西南交通大学硕士研究生学位论文第7 页 主要包含两部分内容：( 1 ) 发现适当的类；( 2 ) 根据每个类形成相应的特 征描述，与在分类学习中的方法类似。无论如何最大程度地实现类 中对象相似度最大，类间对象相似度最小是聚类分析的基本指导思 想。 在数据挖掘中，大多数工作都集中在发现能够有效、高效地对 大数据库进行聚类分析的方法上。相关的研究课题包括：聚类方法的 可扩展性、复杂形状和复杂数据类型的聚类分析的有效高效性、高 维聚类技术，以及混合数值属性与符号属性数据库中的聚类分析方。 法等。聚类分析是一个富有挑战的研究领域，有关每一个应用都提 出了一个自己独特的要求。以下就是对数据挖掘中的聚类分析的一 些典型要求【1 3 j 。 1 可扩展性 许多聚类算法在小数据集( 少于2 0 0 个数据对象) 时可以工作 的很好；但_ 个大规模数据库可能包含几百万个对象，利用采样方 法进行聚类分析可能会导致有偏差的结果，这时需要可扩展的聚类 算法。可扩展性要求算法要能够处理大数据量的数据库。即聚类算 法对小数据集和大规模数据集要同样有效。 2 处理不同类型属性的能力 许多算法被设计用来聚类数值类型的数据，。但是在应用当中， 可能要求聚类其它类型的数据，例如布尔型、枚举型、序数型、以 及混合型等。即算法不仅要能处理数值型字段，还要有处理其它类 型字段的能力。 3 能发现任意形状的聚类 许多聚类算法基于欧氏距离或者曼哈坦距离度量来决定聚类， 基于和样的距离度量的算法趋向于发现具有相近尺寸和密度的球状 簇，但在实际应用中，一个簇可能是任意形状的。故要求算法有发 现任意形状簇的能力。 4 使决定输入参数的领域知识最小化 很多聚类算法都要求用户输入一些参数，例如期望所获聚类的 个数，而聚类分析的结果通常都与输入参数密切相关：而这些参数 常常也很难决定，特别是包含高维对象的数据集。这不仅加重了用 户的负担，也使聚类质量很难控制。聚类算法要尽可能地减少用户 西南交通大学硕士研究生学位论文第8 页 一i i l _ _ 估计参数的最佳取值所需要的领域知识。 5 能够有效地处理噪声数据 绝大多数显示世界中的数据库都包含了孤立点、空缺、未知数 据或者错误的数据。一些聚类算法可能会对这些数据很敏感，可能 导致低质量的聚类结果。聚类算法要能处理现实世界的数据库中普 遍包含的异常数据。 6 对于输入纪录的顺序不敏感 有些算法对记录的输入顺序非常敏感，比如对同一个数据集， 将它以不同的顺序输入到同一个分析算法中，可能生成差别很大的 聚类结果。我们应开发出数据输入顺序不敏感的聚类算法。 7 高维性 一个数据库或者数据仓库可能包含若干维或者属性，一些算法 在处理维数比较少的数据集时表现不错，例如两、三维的数据，人 类最多在三维的情况下能够很好的判断聚类的质量，但对于高维数 据就无能为力，所以对高维数据的聚类是很具有挑战的。聚类算法 不仅要擅长处理低维的数据集。而且要能够处理高维、数据可能非常 稀疏且高度偏斜的数据集。 8 基于约束的聚类 现实的应用中总会出现各种其它的限制，我们希望聚类算法可 以在考虑这些限制的情况下仍有较好的表现。聚类结果既要满足特 定的约束，又要具有良好的聚类特性。 9 可解释性和可用性 聚类的结果最终都要面向用户，用户希望聚类结果应该是容易 解释和理解的，并且是可用的。这就要求聚类算法必须与一定的语 义环境及语义解释相关联。 2 3 主要的聚类方法 聚类算法有许多种，需要根据应用所涉及的数据类型、聚类的 目的以及具体应用要求来选择合适的聚类算法。如果利用聚类分析 作为描述性或探索性的工具，那么就可以使用若干聚类算法对同一 个数据集进行处理以观察可能获得的有关( 数据特征) 描述。按照聚类 西南交通大学硕士研究生学位论文第9 页 的原理和方法，主要的聚类算法可以分为以下几类： 2 3 1 划分方法 划分方法的基本思想是，给定一个n 个样本的数据库，划分方 法将数据划分为k 个划分( k = n ) ，每个划分表示一个簇，同时满足： 1 ) 每个簇至少包含一个样本； 2 ) 每个样本必须属于且仅属于一个簇。 给定要创建的划分的数目k ，首先创建一个初始划分；然后利用 一个循环定位技术通过将对象从一个划分移到另一个划分来改善划 分质量。典型的划分方法包括：k m e a n s 1 4 】【15 1 ，k m e d o i d s 16 1 ， p a m 1 ”，c l a r a 1 ”，c l a r a n s 18 1 ，e m 1 9 】等。 k m e a n s 的基本思想是通过迭代把n 个数据对象划分到k 个不同 的簇中，使簇内部对象之间的相似度很大，而簇之间对象的相似度 很小，相似度的计算根据一个簇中对象的平均值来进行。 e m ( 期望最大化) 算法从多个方面对k m e a n s 算法进行了扩展。其 中包括：它根据描述聚类所属程度的概率权值，将每个对象归类为一 个聚类，不是将一个对象仅。归类为一个聚类( 所拥有) ；也就是说在各 聚类之间的边界并不是非常严格。因此可以根据概率权值计算相应 的聚类均值。 k m e d o i d s 的基本思想是为每个簇选取一个代表对象来代替聚 类中心的作用，剩余的对象根据其与代表对象的距离分配给最近的 一个簇。然后反复地用非代表对象来替换代表对象，以求最佳的聚 类效果。这种算法计算量要比k m e a n s 大，一般只适合小数据集。 p a m ( 围绕中心对象进行划分) 是最初提出的k m e d o i d s 聚类算 法之一，它对所有的对象对进行分析，把每个对中的一个对象看作 中心点，对各种可能的组合，估算聚类结果的质量。p a m 算法迭代 时间复杂度大，对大型数据集合没有良好的可扩展性。为了处理较 大的数据集合，提出了c l a r a 算法。 c l a r a 的主要思想是不考虑整个数据集合，只考虑实际数据的 一部分作为其代表。c l a r a 算法能够处理大规模数据集。为了改进 c l a r a 的聚类质量和可扩展性，提出了c l a r a n s 算法。 西南交通大学硕士研究生学位论文第1 0 页 c l a r a n s 将采样方法于p a m 方法结合起来，它与c l a r a 的 区别是它在聚类的每一步随机性的抽取一个样本，而不是一个固定 的样本。 划分算法一般要求所有的数据都装入内存，限制了它们在大觏 模数据集上的应用；它们还要求用户预先指定聚类的个数，但在大 多数实际应用中，最终的聚类个数是未知的；另外，划分算法只使 用某一固定的原则来决定聚类，这就使得当聚类的形状不规则或者 大小差别很大时，聚类的效果不是很好。 2 3 2 层次方法 层次聚类方法将数据对象组成一棵聚类的树。根据层次的分解 如何形成，层次聚类方法可分为凝聚的和分裂的两种。凝聚的层次 聚类采用自底向上策略，它从单成员聚类开始，首先将每个样本作 为一个簇，然后合并这些原子簇形成越来越大的簇，直到所有的样 本都在一个簇中，或某个终结条件被满足。分裂的层次聚类采用自 项向下策略，首先将所有样本置于一个簇中，然后逐渐细分为越来 越小的簇，直到每个样本自成一个簇，或者达到某个终结条件，例 如达到了某个希望的簇的数目或两个最近的簇之间的距离超过了某 个阈值。 典型的层次方法有b i r c h 2 0 1 、c u b e ”1 、r o c k 2 2 1 、 c h e m a l o e n 2 3 等。 2 3 3 基于密度的方法 大部分划分方法基于对象之间的距离进行聚类，只能发现球状 的簇，而不能发现任意形状的簇。基于密度的方法可用来过滤“噪 声一孤立点数据，以发现任意形状的簇。其主要思想是：只要临近 区域的密度( 对象或数据点的数目) 超过某个阈值，就继续聚类，既对 给定类中的每个数据点，在一个给定范围的区域中必须至少包含某 个数目的点。 典型的基于密度的聚类算法包括：d b s c a n 2 4 1 、o p t i c s 2 5 】等。 西南交通大学硕士研究生学位论文第1 1 页 2 3 4 基于模型的方法 基于模型的方法为每个簇假定了一个模型，寻找数据对给定模 型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间 分布的密度函数来定位聚类，它也是基于标准的统计数字自动决定 聚类的数目，考虑“噪声一数据或孤立点，从而产生健壮的聚类方 法。 一 典型的基于模型的聚类方法有统计学方法c o b w e b 2 6 1 、 c l a ss i t l 27 1 、a u t o c l a s s 2 8 1 ，神经网络方法s o m 2 9 】【3 0 1 、a r t 31 1 、l v q 3 2 】 等。 2 3 5 基于网格的方法 基于网格的聚类算法是采用一个多分辨率的网格数据结构，将 数据空间量化为若干单元，形成一个网格结构，所有的聚类操作都 在此网格上进行。 典型的基于网格的聚类方法有s t i n g 33 1 、w a v e c l u s t e r 3 4 】和 c l i q u e 3 5 】等。 西南交通大学硕士研究生学位论文第1 2 页 第3 章进化计算方法概述 3 1 进化算法 3 1 1 进化算法过程 近4 0 年来，人们从不同的角度对生物系统及其行为特征进行了 模拟，产生了一些对现代科技发展有重大影响的新兴学科。例如， 对人类模糊思维方式的模拟产生了模糊集合理论：对动物脑神经的模 拟产生了人工神经网络理论；对自然界中动、植物免疫机理的模拟产 生了免疫算法；而对自然界中生物进化机制的模拟产生了进化计算 ( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 理论。进化计算最初具有三大分支： 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、进化规划( e v o l u t i o n a r y p r o g r a m m i n g ，e p ) 和进化策略( e v o l u t i o ns t r a t e g y ，e s ) 。虽然这几个分 支在算法实现方面有一些差别，并且这些差别正逐渐缩小，它们一 个共同的特点是借助生物进化的思想和原理来解决实际问题。进化 计算是指以进化原理为仿真依据，在计算机上实现的具有进化机制 的算法和程序。目前，进化计算侧重于算法的研究，因此有时也称 之为进化算法( e v o l u t i o n a r ya l g o r i t h m s ，e a ) 。 进化计算提供了一种求解复杂系统优化问题的通用框架，其基本 着眼点是基于对生物进化过程的模拟，开发一种具有较强鲁棒性的 通用计算模型。 3 1 2 进化计算的基本特点 进化计算的三个主要分支虽然着眼于自然界中生物进化的不同 背景，是由不同的研究人员独立地开发出来的，但它们之间有很多 相似之处。这三种进化计算方法都具有下述的一些共同的基本特点： ( 1 ) 算法的操作对象都是由多个个体所组成的一个集合，即群体： ( 2 ) 每个个体都有一个对系统环境的适应度，这个适应度是算法对 每个个体优劣程度的一种度量： ( 3 ) 算法都要进行选择或复制操作，以便能够将当前群体中具有较 西南交通大学硕士研究生学位论文第1 3 页 高适应度的个体更多地保留到下一代群体中； ( 4 ) 算法都通过个体重组、变异等进化操作，以及对个体所加入的 一些微小变动，来增进群体的多样性： ( 5 ) 算法所模拟的生物进化过程都是一个反复迭代的过程。在群体 的这个迭代进化过程中，个体的适应度和群体中所有个体的平均适 应度都不断地得到改进、最终可得到一个或几个具有较高适应度的 个体，它们就对应于问题的最优解或近似最优解； ( 6 ) 算法所模拟的进化过程均受随机因素的影响，所以它们不易于 陷入局部最优点，井都能以较大的概率找到全局最优点： ( 7 ) 算法都具有一种天然的并行结构，均适合于在并行机或局域网 环境中进行大规模复杂问题的求解。 由于进化算法具备上述的这些特点，就使得它能够用于解决复杂 系统的优化问题，特别是能够解决一些利用其他方法难以解决或根 本无法解决的问题。上述特点同时也说明进化算法是一类全局优化 自适应概率。搜索技术，它们不依赖于具体问题的种类，具有广泛的 应用价值。 3 2 遗传算法 3 2 1 遗传算法概述 遗传算法是从代表问题可能潜在解集的一个种群( p o p u l a t i o n ) 开 始的。而一个种群则由经过基因( g e n e ) 编码( c o d i n g ) 的一定数目的个 体( i n d i v i d u a l ) 组成。每个个体实际上是染色体( c h r o m o s o m e ) 带有特 征的实体。染色体作为遗传物质的主要载体，即多个基因的集合， 其内部表现( 即基因型) 是某种基因组合，它决定了个体的形状的外部 表现。因此，在一开始需要实现从表现型到基因型的映射即编码工 作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进 制编码。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐 代( g e n e r a t i o n ) 演化产生出越来越好的近似解。在每一代，根据问题 域中个体的适应度( f i t n e s s ) 大小挑选( s e l e c t i o n ) 个体，并借助于自然遗 传学的遗传算子( g e n e t i co p e r a t o r s ) 进行组合交叉( c r o s s o v e r ) 和变异 ( m u t a t i o n ) ，产生出代表新的解集的种群。这个过程将导致种群像自 西南交通大学硕士研究生学位论文第1 4 页 然进化一样的后生代种群比前代更加适应于环境，末代种群中的最 优个体经过解码( d e c o d i n g ) ，可以作为问题近似最优解。 3 2 2 遗传算法的理论基础 遗传算法的理论研究包括算法搜索性能研究、收敛性能研究、 运行参数设置以及算法的改进等内容。作为遗传算法的数学基础， h o ll a n d 的模式定理( s c h e m a t at h e o r y ) 指出：在遗传算法选择、交 叉、变异的作用下，具有低阶、短定义距以及平均适应度高于种群 平均适应度的模式在子代中呈指数增长，满足了寻找最优解的必要 条件。其中，相关的定义如下： 定义1 ：模式表示一些相似的模块，它描述了在某些位置上具 有相似结构特征的个体编码串的一个子集。 定义2 ：模式的阶是指模式h 中确定位置的个数，记作0 ( i - i ) 。 例如：0 ( 1 0 l ：l c 0 木) = 4 。模式阶用来反映不同模式间确定性的差异，模 式阶数越高，模式的确定性就越高，所匹配的样本个数就越少。 定义3 ：模式h 中第一个确定位置和最后一个确定位置之间的 距离称为模式的定义距，记作6 ( h ) 。例如：，6 ( 101 奉o 木爿c ) = 4 。在遗 传算法中，即使相同阶数的模式也会有不周的性质，而模式的定义 距就反映了这种性质的差异。 模式理论是遗传算法的理论基础，保证了较优模式( 遗传算法 的较优解) 的数目呈指数增长，为解释遗传算法机理提供了一种数 学工具。 同时，遗传算法具有隐含并行性( i m p l i c i tp a r a l l e l i s m ) ，h o l l a n d 和g o l d b e r g 都指出遗传算法有效处理的模式个数为o ( 刀3 ) ，即尽管 遗传算法实际上只对n 个个体进行运算，但却隐含处理了o ( ，z 3 ) 个 模式，这说明遗传算法是一种高效率的搜索算法。 3 2 3 遗传算法的基本要素 构成基本遗传算法的要素主要有：染色体编码，个体适应度评 价，遗传操作( 选择操作，交叉操作，变异操作) 以及遗传参数的 西南交通大学硕士研究生学位论文第1 5 页 j i 一 _i_i - _ 设置等。 1 染色体编码方式 在实现对一个问题用遗传算法进行求解之前，必须先对问题的 解空间进行编码，最常用的编码方式为二进制编码，其等位基因是 由二值符号集f 0 ，1 ) 组成。对于解空间中的变量是离散变量的情况 下，对每个变量直接用相应位数的二迸制串进行编码即可。对于那 些连续变量，需要先对连续变量进行离散化，再进行编码。初始群 体中各个个体的基因值可用均匀分布的随机数来生成。遗传算法的 进化过程是建立在编码机制基础上的，编码对于算法的性能如搜索 能力和种群多样性等影响很大。 2 适应度函数 在遗传算法中，以个体的适应度的大小来确定该个体被遗传到 下一代群体中的概率。个体的适应度越大，该个体被遗传到下一代 的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代 的概率也越小。 3 遗传算法包括三个基本操作：选择、交叉和变异。这些基本操 作又有许多不同的方法。 ( 1 ) 选择 选择是用来确定重组或交叉个体，以及被选个体将产生多少个 子代个体。首先计算适应度，有按比例的适应度计算，基于排序的 适应度计算方法； 适应度计算之后是实际的选择，按照适应度进行父代个体的选