（计算机应用技术专业论文）基于智能计算的数据聚类方法的研究.pdf

摘要 两姜本文以数据聚类技术为主要研究对象，在分析原有聚类算法存在的不完善之处的基础上，采用了计算智能中一些先进的算法对模糊聚类问题进行了优化研究，提出了多种混合聚类算法，取得了良好的效果。研究内容主要包括：( 1 ) 为了克服现有算法对初始化敏感，提出了一种基于免疫遗传的模糊聚类算法，实验证明，它能够使聚类结果收敛到全局最优，比标准遗传算法具有更快的收敛速度和更强的搜索能力。( 2 ) 将克隆原理应用于进化计算中，提出了抗体克隆策略与模糊c 均值聚类结合的混合算法。此算法在时间和精度上都有很大的提高。( 3 ) 提出了利用量子进化算法的量子并行性来处理聚类问题的一种新算法q f c m ，将其用于模糊聚类，显著地减小了算法的迭代次数从而大大缩短了运行时间。( 4 ) 在应用方面，采用免疫遗传模糊聚类算法挖掘基于语义距离的多维关联规则，它不仅充分紧扣区间数据的语义，更能反映人们的直觉，克服了以往离散化方法硬性划分数据的缺点。关键词：模糊聚类免疫遗传克隆策略量子进化数据挖掘a b s t r a ( 了a b s t r a c tt h em e t h o do fd a t ac l u s t e r i n gi ss t u d i e dm a i n l yi nt h ep a p e r o nt h eb a s i so fa n g l i c i z i n gt h ed e f e c to ft h ee x i s t i n ga l g o r i t h m ，as t u d yo no p t i m i z i n gf u z z yc l u s t e r i n gp r o b l e mi sm a d eb ya d o p t i n gs o m ea d v a n c e di n t e l l i g e n tc o m p u t i n gt e c h n i q u e ss u c ha si i n i n u n eg e n e t i c ，c l o n ee v o l u t i o n a r ys t r a t e g ya n dq u a n t u me v o l u t i o n a r ya l g o r i t h m a n da n a l y s i sa n dc o m p a r eo fp e r f o r m a n c ea n df i t n e s so fd i f f e r e n td a t as e t si sm a d eo nt h e s eh y b r i d c l u s t e r i n ga l g o r i t h m s w ep r o p o s et h es e r i e so fn e wi d e a s ，r e a l i z es e v e r a lh y b r i d c l u s t e r i n ga l g o r i t h m sa n da c h i e v ef a v o r a b l er e s u l t t h em a i nr e s e a r c hw o r k sa r ef o l l o w s ：( 1 ) t h ef u z z yc l u s t e r i n ga l g o r i t h mb a s e do ni m m u n eg e n e t i ci sp r o p o s e d ，w h i c ho v e r c o m e st h es e n s i t i v i t yo fi n i t i a l i z a t i o no ft h ec l u s t e rm e t h o d t h ee x p e r i m e n t a lr e s u l t ss h o wi tc a l lc o n v e r g eg l o b a lo p t i m i z a t i o ns o l u t i o n c o n t r a s tt oc o n v e n t i o n a lg e n e t i ca l g o r i t h m ，t h ea l g o r i t h mh a sq u i c k e rc o n v e r g e n c es p e e da n ds t r o n g e rc a p a b i l i t yo fs e a r c h ( 2 ) c l o n ep r i n c i p l ei sl e di n t oe v o l u t i o n a r yc o m p u t i n g ，a n dah y b r i da l g o r i t h mo fc o m b i n i n ga n t i b o d yc l o n es t r a t e g yw i t hf u z z yc - m e a nc l u s t e r i n gm e t h o di sp r e s e n t e d t h ea l g o r i t h mn e e dn o ta n yp r e e x i s t i n gk n o w l e d g ea n do m i t sc r o s s o v e ro p e r a t i o no fc o n d i t i o n a le v o l u t i o n a r ya l g o r i t h m s t h ep e r f o r m a n c eo ft h i sh y b r i da l g o r i t h mi si m p r o v e dr e m a r k a b l yo ns p e e da n dp r e c i s i o n ( 3 ) b a s e do nc o n c e p ta n dt h e o r yo fq u a n t u ms u c ha sq u a n t u mb i ta n d1 i n e a rs u p e r p o s i t i o no fs t a t e s ，a , n o v e la l g o r i t h m ，q u a n t u me v o l u t i o n a r yf u z z yc l u s t e r i n ga l g o r i t h m ( q f c m ) i sp r o p o s e d t h ea l g o r i t h mh a sg o o dd i v e r s i t yo fp o p u l a t i o n i th a sq u i c k e rc o n v e r g e n c es p e e da n ds t r o n g e rc a p a b i l i t yo fs e a r c hi ns o l v eo p t i m i z i n gp r o b l e m s ot h a t ，w ee m p l o yt h eq u a n t u me v o l u t i o ns t r a t e g i e st or e d u c ee v i d e n t l yo v e r l a pn u m b e r so ft h ea l g o r i t h ms ot h a tr u n n i n gt i m ei ss h o r t e n e dg r e a t l y ( 4 ) i na p p l i c a t i o n ，o nt h eb a s i so fa n a l y z i n ga n ds t u d y i n ga v a i l a b l et e c h n i q u eo fd a t am i n i n g ，w ea d o p tt h ef u z z yc l u s t e r i n ga l g o r i t h mb a s e do ni m m u n eg e n e t i ct om i n em u l t i d i m e n s i o n a la s s o c i a t i o nr u l e sb a s e do ns e m a n t i cd i s t a n c e t h ef u z z yc l u s t e r i n ga l g o r i t h mb a s e do ni m m u n eg e n e t i ci sad y n a m i cc l u s t e r i n gm e t h o da n di ti sr o b u s t d a t as e t sa r ed e a l tw i t ht h em e t h o d ，a n di tc o n s i d e r sc o m p a r a t i v ed i s t a n c eo fa m o n gd a t aa sw e l la sp e r m i t sv a l u eo fd a t at oa p p r o x i m a t ee n o u g h t h ee x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h ep r o p o s e dm e t h o dn o to n l yc a t c hh o l do ft h es e m a n t i co fi n t e r v a ld a t ab u ta l s or e f l e c tw e l l i n t u i t i v eo ft h em a n i na d d i t i o n ，t h i sm e t h o do v e r c o m e st h ed e f e c t so f h a r dp a r t i t i o nd a t at o o k e y w o r d ：d a t am i n i n gf u z z yc l u s t e r i n gi m m u n eg e n e t i cc l o n es t r a t e g i e sq u a n t u me v o l u t i o n创新性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名缎坚垒日期：硼；、i 、他关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文( 与学位论文相关) 工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵守此规定)本人签名导师签名缎丞星茎羞日期训工i j 工日期：丝! 兰，! ! 殷第一章绪论第一章绪论1 1 研究背景和意义数据的机器学习( m a c h i n el e a r n i n g ) 【1 ) 【2 】问题是现代智能技术中十分重要的一个方面，主要研究如何从一些观测数据( 样本) 出发得到目前尚不能通过原理分析得到的规律，利用这些规律去分析客观现象，对未来数据或无法观测的数据进行预测。现实世界中存在大量我们尚无法准确认识但却可以进行观测的事物。因此这种机器学习在从现代科学、技术到社会、经济等各领域都有着十分重要的应用。有三类基本的机器学习问题，它们是模式识别、函数逼近和概率密度估计。从上世纪5 0 年代开始机器学习的研究以来，到目前为止，人们已经提出和发展了许许多多的学习算法，从有监督学习算法到无监督学习算法，从硬计算方法到软计算方法。所谓软计算( s o f tc o m p u t i n g ) 方法，是以人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 、模糊逻辑( f u z z yl o g i c ，f l ) 、进化计算( e v o l u t i o n a r ya l g o r i t h m ，e a ) 、概率推理( p r o b a b i l i s t i cr e a s o n i n g ，p r ) 、粗糙集( r o u g hs e t ，r s )等为代表，同传统的硬计算方法比较，可以处理信息中的不精确性、不确定性和部分准确的学习方法。软计算的概念最早是由模糊集理论的创始人，伯克利大学教授提出来的【3 l ，也称之为“智能计算”( i n t e l l i g e n tc o m p u t i n g ) 。一方面入们在不断地提出新的学习方法，另一方面也对已有的各种不同学习方法进行结合，提出许多混合学习算法。特别是近几年，混合智能计算方法的研究受到广泛重视，并在决策支持、图像处理、过程控制、机械电子学、机器人技术和复杂自动化人物等众多应用领域显示出其优良的性能。众所周知，智能系统对于处理实际的计算问题是很重要的，因为它能够提供给我们人类诸如领域知识，不确定性推理和对噪声及时变环境具有自适应性等类似专家经验的知识。而要实现智能度高的系统，对各种计算方法之间的结合或融合是必不可少的。同只能处理精确性、确定性和严密性信息的传统的人工智能方法相比，混合智能计算方法的指导原则是利用对不精确、不确定、部分准确的容忍性以及低的求解费用和鲁棒性来得到对现实问题的易处理性和更好的和谐性1 3 】。因为各种软计算方法之间是相互补充，相互完善的，而不是相互竞争，相互排斥的，在许多情况下，把这些方法结合起来使用比单独使用某一种方法更能有效地解决问题。结合的目的在于通过各种方法的混合，相互取长补短，以克服单个方法的局限性。_ 般来说。混合智能系统主要包括三个基本方法：神经网络( a n n ) 、模糊基于智能计算的数据聚类方法的研究逻辑( f l ) 、和全局优化算法( g o a ，包括进化算法、模拟退火等方法) ，这是因为早期的软计算方法，即智能计算方法主要就包括这三种方法。随着其它新型计算方法的不断提出，混合智能系统研究的内容和范围也得到了不断的扩充，目前主要集中在神经模糊系统( n e u r o f u z z ys y s t e m s ) 1 4 1 - 1 7 1 、进化神经计算( e v o l u t i o n a r y n e u r oc o m p u t i n g ) t 8 1 。1 1 2 】、进化模糊系统( e v o l u t i o n a r y f u z z ys y s t e m s )( 1 3 j 、进化模糊神经计算( e v o l u t i o n a r y - f u z z y ，n e u r oc o m p u t i n g ) 1 1 6 - i 、混合进化计算( h y b r i de v o l u t i o n a r yc o m p u t i n g ) 【l 剐1 2 0 1 等。本文主要研究的是枧器学习中基本问题之一模式识别中的数据聚类技术，聚类分析已经被广泛的研究了许多年，主要集中在基于距离的聚类分析。传统的聚类分析是一种硬划分。它把每个待辨识的对象严格的划分到某类中。具有非此即彼的性质，而实际上大多数对象并没有严格的属性，它们在性态和类属方面存在着中介性，具有亦此亦彼的性质，因此需要进行软划分，模糊集理论【2 l 】的提出为这种软划分提供了有力的分析工具，人们开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析。模糊聚类能更客观地反映现实世界，从而成为聚类分析研究的主流1 2 2 i 。基于此本文将一些智能计算方法结合到模糊聚类中来，使得聚类结果更加精确和可靠。在数据挖掘领域，模糊聚类分析技术有着十分广泛的应用，比如，空间数据库技术、生物学、医学诊断、市场营销、地质数据分析、天气预报、图像处理等等。因此，模糊聚类方法的研究便有着十分重要的科研价值。1 2 目前研究现状及发展方向伴随着模糊集理论的发展和深化，用模糊的手段处理聚类分析问题成为该领域研究的主流，最早系统地表述和研究模糊聚类问题的著名学者r u s p i n i t 2 3 l 【2 4 1 1 2 5 】，他率先定义了模糊划分的概念。随后人们提出了多种模糊聚类分析方法，比较典型的有：基于相似性关系和模糊关系的方法1 2 6 】【2 7 】【2 8 1 、基于模糊图论的最大树方法 2 9 1 3 0 j 、基于模糊等价关系的传递闭包方t h ( 3 2 鹏i 等等。然而，上述这些方法均不能适用于大数据量的情况，难以满足实时性要求较高的场合。因此，实际中受到普遍欢迎的是基于目标函数的模糊聚类方法，也就是说把聚类归结成一个带约束的非线性规划问题，通过优化求解获得数据集的模糊划分和聚类。我们的兴趣主要集中在模糊聚类算法实现途径的研究上。现有的实现途径主要分为：基于交替优化、神经网络和进化计算等方法。基于交替优化的实现在优化目标函数的过程中，人们曾试探过动态规划、分支定界和凸切割等方法，然而大量的存储空问和运行时简限制了其应用。实际中应用最为广泛第一章绪论3的是d u n n 和b e z d e k 提出的迭代优化算法一模糊c 一均值类型的算法【3 4 】【3 5 j ，到目前为止，对它的研究主要集中在收敛性证明、算法停止准则的设立以及原型初始化等方面。值得注意的是，由于算法本质上属于局部搜索的爬山法，很容易陷入局部极值点，因此对初始化较敏感。为了获得全局最优解或满意解，人们希望通过建立良好的原型模式初始化，其中比较有名的方法有y a n g 和f i l e v 提出的山函数或势函数法【3 “。随后，c h i u 提出改进算法1 3 7 使计算量只与样本数日有关而与特征维数无关，解决了计算精度与复杂度之间的矛盾。基于神经网络的实现神经网络在聚类分析中的应用首先源于k o h o n e n 的两项工作一学习矢量量化( l v q ) 和自组织特征映射( s o f m ) f 3 8 1 ，以及o r o s s b e r g 的自适应共振( a r t )理论【3 9 】。用神经网络实现聚类分析显著的优势在于神经网络的并行处理，然而，以上两种聚类网络仍存在应用的局限性一只能实现球形的硬聚类。从总体上看，模糊聚类网络的研究可分为两类：一类是从目标函数法演变而来的，其基础是模糊竞争学习算法，比较有代表性的有，p a l 和b e z d e k 提出的基于竞争学习的模糊聚类网络【4 0 】；x u 提出的带有惩罚项的竞争学习算法【4 1 】；z h a n g 提出的基于高斯非线性的竞争学习算法【4 2 j ；另一类模糊聚类网络由模糊逻辑操作构成，比如c a r p e n t e r 等在a r t 基础上发展的模糊a r t l 4 3 1 ，比a r t 在性能上有较大的改善；s i m p s o n 提出的模糊m i n m a x 网络 4 4 1 实现了超盒子形状的模糊聚类。基于进化计算的实现进化计算是建立在生物进化基础之上基于自然选择和群体遗传机理的随机搜索算法。由于该算法能够全局并行搜索，所以能以较高概率获得全局最优解，此外，进化计算具有简单、通用性好、鲁棒性强等优点。因此，它被引入到模糊聚类中来，形成了一系列基于进化计算的聚类算法。大致可分为以下几种类型：一是基于模拟退火的方法，包括对划分矩阵a s u l t a n 4 5 1 和聚类原型r o s e 4 6 的退火处理两种，然而该算法只有在温度下降足够慢时才能达到全局收敛，极大的运算时问限制了它的实用性h 7 】；二是基于遗传算法h 3 】f 4 9 1 和进化策略 5 0 1 5 1 】的方法，这方面的研究主要集中在解的编码方案、适应度函数构造、遗传算子的引入以及操作参数的自适应调整等方面垆“。以上三种模糊聚类的实现途径各有优缺点，这就启发我们能否集成三者的优点构造速度快、精度高并且全局收敛的模糊聚类算法。而聚类分析技术在数据挖掘领域l ，研究工作已经集中在为大型数据库的有效和实际的聚类分析寻找适当的方法，活跃的研究主题集中在聚类方法的可伸缩性，方法对聚类复杂形状和类型的数据的有效性，高维聚类分析技术，以及针对大型数据库中混合数值和分类数据的聚类方法。基于智能计算的数据聚类方法的研究1 3 论文研究的意义和所做的主要工作最典型的基于目标函数的聚类算法包括硬c 一均值算法和模糊c 均值算法，由于聚类的目标函数是高度非线性和多峰的函数，因此基于爬山法( h i l l c l i m b i n g )或迭代的c 均值、i s o d a t a 等都很难找到全局最有解。用梯度法优化目标函数时，搜索方向总是沿着能量减小的方向，使得算法很容易陷入局部极小值，只有当初始化较好时算法才能得到全局最优解，这样基于目标函数的聚类算法对初始化比较敏感是这类算法一个较为严重的缺点。针对经典算法对初始化敏感、容易陷入局部优由此丽产生各种错误分类的缺点，可以利用现有的模拟退火、遗传算法、进化策略等先进的优化算法对目标函数优化，从而使聚类算法得到全局最优解的概率大大增加。但现有的进化算法也存在耗时以及波动性大等问题，因此，研究聚类新算法是有针对性的，是迫切需要的，也是可行的。聚类是一个富有挑战性的研究领域，数据挖掘中聚类作为一个独立的工具来获得数据的分布情况，观察每个簇的特点，集中对特定的某些簇作进一步的分析。它不但可以作为数据挖掘中规则提取算法的数据预处理步骤，而且还可以直接对聚类结果给予概念解释，即规则挖掘。从国内外目前的研究进展来看，各学科的研究自成一派。没有突破各个领域的技术界限；未将并行优化的诸方法集成用于数据库中的数据挖掘，从而提高实时性，并解决随机的、不完全的以及混沌数据的数据挖掘，即所谓智能数据挖掘。就此本文系统地研究了数据挖掘中模糊聚类算法的理论、实现方法及应用，改进和提高了原有算法的性能。在课题研究中，对基于目标函数的模糊聚类算法进行了深入的研究，提出了将免疫理论和克隆策略等智能计算方法引入至模糊聚类中用于优化目标函数的改进算法，通过对算法的实现，并在来自不同领域的数据集上进行仿真试验，结果表明改进后的算法具有更快的收敛速度和更强的搜索能力。最后，我们还把提出的聚类新算法应用于数据挖掘领域中关联规则的挖掘，实验证明这种方法特别适合数据分离不好的大型数据库上多维关联规则的挖掘，结果切实可靠。1 。4 本文内容安排全文共分为六章。分别如下：第一章绪论介绍了智能系统及其应用的主要软计算方法，聚类算法的发展概况，新算法研究的意义和方向以及本文所完成的主要工作；第一章绪论5第二章数据聚类中的智能计算方法简述模糊聚类算法的相关概念、原理和实现方法。着重介绍计算智能方法在聚类中的应用与研究，进一步分析和讨论了数据挖掘中一些基本技术。第三章基于免疫遗传的模糊c 。均值聚类算法提出了将免疫遗传算法与模糊c 均值聚类算法相结合的混合聚类算法，并在来自不同领域的数据集上进行仿真实验，结合实验结果对几个相关模糊聚类算法进行了对比和分析。第四章抗体克隆策略结合模糊c 均值的混合聚类算法提出了将免疫克隆策略算法川与模糊c 均值聚类算法【2 】相结合的混合聚类算法该算法既克服了基于梯度下降方法优化目标函数的经典模糊c 均值聚类算法过分依赖初始优的缺点，同时它能够使聚类结果收敛到全局最优，实验证明，相比标准进化策略算法，有效克服了早熟问题、保持了织的多样性，具有更快的收敛速度和更强的搜索能力。第五章模糊聚类算法在数据挖掘中的应用应用聚类方法研究了数量关联规则提取过程中的连续属性的离散化问题，主要针对数据挖掘中基于距离的多维关联规则进行挖掘，实验表明能够生成更加符合实际的和更容易被人们接受的关联规则。第六章量子进化算法及其在模糊聚类中的应用针对传统进化算法运行速度比较慢且容易早熟的缺点，主要分析和研究了量子进化算法的基本原理、算法实现以及在模糊聚类中如何应用等问题。采用量子编码来表征染色体，充分利用量子算法的并行性，从而使算法具有更好的种群多样性和全局寻优能力。通过仿真实验同时和第三章中的算法以及第四章的算法的性能进行比较分析。我们指出了三种算法各自的优缺点，进一步证明了q f c m 算法的高效并行性。基于智能计算的数据聚类方法的研究第二章数据聚类中的智能计算方法2 1 聚类算法聚类就是按照一定的要求和规律对事物进行区分和分类的过程，在这一过程中没有任何关于分类的先验知识，没有教师指导，仅靠事物间的相似性作为类属划分的准则，因此属于无监督分类的范畴。聚类分析则是指用数学的方法研究和处理给定对象的分类。“人以群分，物以类聚”。聚类分析是多元统计分析的一种，也是非监督模式识别的一个重要分支。它把一个没有类别标记的样本集按某种准则划分成若干子集( 类) ，使相似的样本尽可能归为一类，而不相似的样本尽量划分到不同的类中。1 聚类分析的数学模型设j ，_ 和，x 2 ，南) 是待聚类分析的对象的全体( 称为论域) 。x 中的每个对象( 称为样本) 靴( 1 sk n ) 常用有限个参数值来刻划，每个参数值刻划溉的某个特征。于是对象溉就伴随着一个向量p ( 坼) = ( x k l ，x k 2 ，抛) ，其中x 打( 1 ，s ) 是x l t 在第，个特征上的赋值，p ( x d 称为搬的特征向量或模式矢量。聚类分析就是分析论域x 中的n 个样本所对应的模式矢量问的距离的分散情况，按照各样本间的距离远近关系把x ，x 2 ，靠划分成c 个不相交的子集，局，咒，并要求满足下列条件：x i u z 2 u u k = 鼻；z 。n x i = 庐，l s f ，c( 2 - 1 )样本x k ( 1 k n ) 对子集( 类) x i ( 1 i c ) 的隶属关系可用隶属函数表示为：心巾= 从= 般剖沼2 其中，隶属函数必须满足条件。em 。也就是说，要求每一个样本能且只能隶属于某一类。同时要求每个子集都是非空的。ric一1m k = u 异“k e o ，1 ；玩= l ，v k ；o 疗，v f ( 2 3 )lli - ik s lj在模糊聚类中，样本集z 被划分成c 个模糊子集舅，j ：，兄，而且样本的隶属函数“。从 o ，1 二值扩展到【o ，1 】区间，满足条件：q m 州置) = x ；。【0 , 1 】；善, k = 1 , v k ；o 蕃以 v ( 2 - 4 )第二章数据聚类中的智能计算方法7其中s u p p 表示取模糊集合的支撑集。2 聚类算法的分类按聚类准则的不同可分为：基于模糊关系的聚类算法( 如谱系聚类法和图论聚类法) ，和基于目标函数的聚类算法( c - 均值聚类算法等) 。基于模糊关系的聚类算法的研究主要集中在六七十年代，由于它自身的缺点，到九十年代后者方面的研究逐步减少了。而基于目标函数的聚类算法把聚类问题归结为优化问题从而成为研究的主流。基于目标函数的聚类算法按聚类原型的不同可分为：c - 簇、c - 线、c 面、c 壳、c _ 函数聚类算法。这些基于不同原型的聚类算法对不同分布的数据集采用不同的距离度量方式，实现了对呈球形、椭球形、线形、平面形以及球壳、椭球壳和某种函数关系分布的数据集的聚类分析。按照分类结果的取值方式的不同聚类算法可分为：硬聚类、模糊聚类和可能性聚类三种。在硬聚类算法中样本的分类取o ，1 二值，对某一类的隶属度值取0则表示样本不属于该类，取l 则表示样本属于该类：模糊聚类中隶属度的取值为 o ，1 】整个区间，它允许样本以某一隶属度。属于第i 类，同时约束：= 1 ，即样本属于各类的隶属度之和为1 。如果没有这一约束条件，只要求“【0 ，1 】，则变成可能性聚类。按照优化目标函数的方法的不同可分为三类聚类算法：一是基于迭代爬山技术的聚类，即基于梯度下降的聚类算法，如c - 均值聚类算法、i s o d a t a 算法等：二是基于神经网络的聚类算法，其中以聚类神经网络和自组织共振神经网络最为典型，前者实现了类数给定的c - 均值算法，而后者实现了类数不定的c - 均值聚类算法；三是基于进化计算的聚类算法，如基于模拟退火算法的、基于t a b u 搜索算法的、基于遗传算法和进化策略的等等。这些算法在一定程度上克服了传统聚类算法容易陷入局部最优的缺点。本文研究的重点就是基于进化计算的模糊聚类算法，力图对原有的算法的性能进行卓有成效的改进。2 2 基于神经网络的模糊聚类算法人工神经网络是在微观层次上模仿脑神经网络的功能，其实质在于对外界刺激( 信号) 的自适应反应能力。聚类神经网络的设计方法是多种多样的，但我们仅以k o h o n e n 神经网纠5 4 1 为例，简要介绍一下神经网络在模糊聚类中的应用以及这种算法的好处。1 k o h o n e n 聚类神经网络模型基于智能计算的数据聚类方法的研究k o h o n e n 聚类神经网络是由首先提出来的，其网络结构如图2 1 所示。它是一个两层前馈神经网络，第一层为输入层，含有搠个神经元( 与聚类数据的特征维数m 相对应) ，第一层神经元为线性神经元，其相应函数为线性函数，设输入为z ，输出为y ，则其相应为：y = x ，第二层神经元为竞争输出神经元，其个数与数据集的类数c 相对应，第二层神经元的输出取f o ，1 二值，当第i 个神经元输出为1 时，表示此时输入样本溉属于第i 类。当第i 个神经元输出为0 时，表示此时输入样本溉不属于第i 类。第一层和第二层的权连接包含m x c 叶 ，即v 2 【”1 ，v 2 ，v c 。，v ，= v i l , v f 2 ，v 咖】。表示第i 类聚类中心ax b图2 1k o h o h e n 聚类神经网络拓扑结构利用这一聚类神经网络通过竞争学习调整数值v ，当网络稳定后，利用所得到的聚类中心对各个样本进行分类，从而得到聚类结果。2 竞争学习算法竞争学习规则主要用于多层前向网络，它的基本恩想是只有在竞争中获胜者保持原状态，即不学习新知识也不遗忘旧知识。个简单的竞争学习规则可表示为：”i ，t 2v i i ，t 一1 十口 ，f ” ，、t i - s i ( y i ) 【f 舡f ) 一v j ，t l 】”这里v 。是连接输入层中第_ ，个神经元和输出层中第i 个神经元的权值，- i ) 。为其时间导数，s 与厂是输出层神经元与输入层神经元的激励函数。竞争学习的收敛速度相对较快，k o s k o 证明了权矩阵以指数级速度收敛于模式的类中心。竞争学习觌则可分为由监督和无监督两种，其中无监督学习与聚类相对应，因此我们只介绍非监督竞争学习规则。竞争学习算法在聚类中最早应用是学习矢量量化( l e a r n i n gv e c t o rq u a n t i z a t i o n 。l v q ) ，l v q 在聚类中符号统一为：第二章数据聚类中的智能计算方法9f ( x k ) = x t ，s 咖j = “鼽它的算法步骤可描述如下：第一步：初始化所有权值，v i = i 2 ，a 户l ，z p i第二步：对任意一个输入样本x ( k 1 寻找获胜的输出节点i ：椒露) 一v 。( ) = m ；n6 x ( 是) 一v ，( 七) ( 2 6 )此时心= 1 ，m = 0 ，j i 。第三步：用竞争学习规则调整与获胜节点相连的权值v ( 女)1 ，( + 1 ) = v ，( t ) 十a ( x ( k ) 一v ( t ) )( 2 - ? )口为调整步长，并随迭代次数增加而减小。第四步：所有样本全部学习一遍后作为一次循环迭代，权值可每输入一个样本调整一次，也可以一次循环后总的调整一次。当一次循环后v 的变化小于阈值占，即m ( ，+ 1 ) 一v 。( f ) 8 占，则算法结束，否则转到第二步。该算法最终得出的结论是，如果样本数据分布不是很好，当随机初始化参数时，h c m 算法在绝大多数情况下都陷入了局部最优，而神经网络模糊聚类算法获得全局最优解的概率相比要大一些。因为在神经网络模糊聚类算法中，权值调整过程隐含着一定的随机性，每一步调整权值并不一定使目标函数变小，这就有可能脱离局部最小【55 1 。当然神经网络模糊聚类算法也不能真正克服局部最优，要想克服局部最优。还需借助进化计算中的一些算法，这正是我们下一节所要讨论的内容。2 3 遗传与模糊c 均值混合聚类算法2 3 1 遗传算法基本思想遗传算法是建立在生物进化基础上的算法，是一种基于自然选择和群体遗传机理的搜索算法。它模拟了自然选择和自然遗传过程中发生的繁殖、交配和突变现象。它将每个可能的解看作是群体( 所有可能解) 中的一个个体，并将每个个体编码成字符串的形式，根据预定目标函数对每个个体进行评价，给出一个适应度值。开始时总是随机地产生一些个体( 候选解) ，根据这些个体的适应度利用遗传算子对这些个体进行操作，得到一群新个体，这群新个体由于继承了上一代的一些优良性状，因而优于上一代，这样逐步朝着更优解的方向进化。遗传算法在每一代同时搜索参数空间的不同区域，然后把注意力集中到解空间中期望值最高的部分，从而使获得全局最优解的可能性大大增加。遗传算法对复杂问题无需建模和进行复杂的运算，不要求目标函数可导，仅用遗传算子操作即可寻找到优化问题的解。手沁如月一刈已经证明，在一定条件下，遗传算法可以在搜索空间中收敛基于智能计算的数据聚类方法的研究到全局最优解。同时遗传算法是一种通用性好和鲁棒性强的并行搜索算法嗣，因此，人们自然想到将遗传算法的全局搜索能力应用到经典的模糊聚类中来，以克服经典算法对初始化敏感和容易陷入局部优的缺点。2 3 2 混合聚类算法实现1 编码编码的实质是在问题的解空间与算法的搜索空间之间建立一个映射。该算法对聚类中心v = v a v j e 矗”，j = l 2 芦 进行编码，呼表示一个个体h 上的个基因。由于v ，用实数表示，所以该算法采用实数编码，即每个个体用一个s = c , 维的实向量诈= 和 v ，2 ，v ，c ) 2 r “表示，其中嘶v 请玩，6 ，啦分别表示v 清的上下界：= 1 ，2 ，n ，t = i ，2 ，c 。1 产生初始种群以向量巧何表示第f 代进化群体中第，个个体，随机产生种群规模个数( p o p s i z e ) 个矩阵形，i = l ，2 , p o p s i z e 记第f 代进化中包含”个个体的群体向量p 例= n ，呢似，船澎 7 ；群体的规模由样本的大小和样本类之间的距离来决定，样本本身不太大但类之间的距离小时，种群的规模可以适当的大一些，有利于提高样本的多样性，收敛速度也能接受；如果样本非常庞大且类之间的距离较大时，种群的规模可以小一些，以确保时间性能。3 适应度函数的构造由于优化问题是要找出满足约束条件，同时使目标函数最小的向量解，但是具体到我们模糊c 均值算法，目标函数厶( 彰玢越小，聚类效果越好，因此我们可以如下来构造： 5 烈枋2 砭万1 西i协8 )其中盯为足够小的正数4 选种算子选种( s e l e c t i o n ) 是依据每个个体的适应度值，：来选择双亲产生新个体的过程。适应度越大，便赋予更大的选种概率凡，则其子代在下一代中的个体数目就越多。在此我们采用最佳个体保存法，在群体交叉之前，先选出最佳个体直接遗传到子代群体中，剩下个体的选择采用比例选择法第j 个个体选择概率为：第二章数据聚类中的智能计算方法巴= 丽争，其中p o p 为种群规模大小，j = l5 交叉算子交叉( c r o s s o v e r ) 算子是将选种操作中选取的双亲基因进行重新组合。交叉操作是按一定的概率( 称之为交叉概率) 进行的。交叉的效果是使来自父代的遗传物质组合在一起产生更优良的个体，我们采用单点交叉，交叉点的位置如下进行，随机选取 ，同之间的两个随机数，厶，对于选种得到的两个配对基因串蚱和嵋，以概率只交换两个矩阵中的第- ，列和第厶列元素，得到下一代该过程重复( p o p 一，) 磐次。一般只( 0 4 ，0 8 ) 效果较好6 变异算子复制和交叉尽管可以产生新的基因串，但不能产生新的基因，每个基因只能是被复制和死亡，如果所有基因串某一位置的基因都相同，则这一基因所表征的性状就永远不会改变。变异( m u t a t i o n ) 算子的引入则打破了僵局，从而保证了生物继续进化。变异以一个很小的概率( 称之为变异概率届) 进行。首先进行概率测试，符合条件的则对所选种取得的个体的随机选取一列比，进行突变。只一般取( 0 卜0 3 ) 。7 算法终止准则当进化代数达到最大进化代数g 或结果没有明显改进使算法终止，即i 厂( ，) 一f ( t 1 ) 占( 占为一小的正数) 或t = g 时，算法终止。2 ，3 3 算法具体计算步骤初始化：设定一较小正数e ，交叉概率p 。，变异概率p 卅，每代中c 一均值算法的迭代次数l 随机产生仃个个体，形成初始种群，设置遗传代数t = l ，算法终止条件。通过计算适应度函数厍，求出当前群体中的最佳个体。f o rk = lt onf 对每个个体迭代运算三次：再计算第x 个个体的目标函数厶f j j 及适应度五计算厂( f ) = 吨筝厶，如果l ( f ) 一厂。一1 ) l s ，确定当前种群中的最佳个体作为算法最终所找的解。否则，置t = t + l 。对t 1 代群体进行选择操作，随机选出两条基因串配对，以概率p 。进行交叉基于智能计算的鼗据聚类方法的研究对每条基因串以概率p 。进行变异操作，形成第f 代p ( o 。如果终止条件不满足，群体更新，返回；如果满足，则保存最优解。2 3 。4 实验结果及分析下面我们通过三组不同的样本进行聚类，比较基于遗传算法的聚类和经典f c m 算法的性能：样本l 仿真采用样本个数为1 0 ，特征维数为2 ，簇之间分离较好的点集x 1 ，其中遗传算法的种群规模为6 ，模糊迭代次数l 为1 ，交叉概率为p c = o 6 ，变异概率为尹_ = o 2 。x 1 = 4 17 1 ；5 18 4 ：6 27 1 ；5 16 1 15 17 2 ：1 8 92 0 5 ：1 8 01 9 6 ：1 9 01 9 6 ；1 8 91 9 6 ：1 9 91 9 6 样本2 某柴油机不同活塞裙部一缸套间隙时的机身加速度样本。这是一个具有5 维特征、类数是4 ，容量为2 4 的样本。遗传算法中采用种群规模为i o ，迭代次数为2 ，交又概率为p c = o 7 ，变异概率为p 。- - o ，1 。表2 t 柴油机数据样本样本特征功率谱总功率平均功牟潜最大振幅振幅均方根nm g ： h z9 2m 9 2 h z2gl3 934 0 87 9 4 61 5 72 0 2 524 0 b4 0 47 5 3 41 7 8z 2 1 034 i74l z7 8 5 31 6 42 0 1 043 9 53 9 77 4 8 71 5 92 0 3 453 7 44o l7 2 5 31 6 420 1 363 8 64l l74 6 l1 6 32 1 4 175 4 54 5 48 1 2 39 7 92 0 5 085 3 042 382 3 89 3 l2 ，l l l95 5 14 6 68 2 3 7l o 5i 9 9 91 05 9 74 8 48 8 7 61 0 7 62 3 2 2l l6 9 64 7 6b 7 4 59 5 42 1 3 21 25 7 74 7 68 9 4 288 92 1 6 61 35 8 54 7 99 6 6 78 8 82 1 3 21 46 2 84 8 39 0 1 29 2 l2 0 3 51 53 9 42 5 14 9 34 94 8 71 63 9 82 4 54 7 84 54 91 74 0 22 65 1 94 94 8 1 71 84 0 72 6 14 74 44 。9 1 71 94 0 32 5 。35 3 35 l4 8 82 04 0 l2 5 54 4 t 64 8 5 12 i1 3 l 06 4 51 3 2 3 66 18 82 21 3 2 16 5 ，71 3 8 76 38 92 31 3 3 0醴21 4 1 7 5黼8 72 41 3 2 76 7 51 3 6 76 2 88 6 5第二章数据聚类中的智鸵计算方法样本3 仿真采用样本个数为2 0 ，特征维数为2 ，簇之间分离不好的点集x 2 ，其中遗传算法的种群规模为2 0 ，模糊迭代次数l 为1 ，交叉概率为尸。= 0 5 ，变异概率为p 。= o 2 。1 1 1 61 1 47 03 33 98 01 2 81 2 21 4 i1 8 92 1 62 0 61 6 91 6 77 29 41 8 99 21 4 35 4 l1 1 4 51 9 62 1 61 9 815 i1 3 51 0 97 03 8 3 26 21 0 9 1 1 77 51 7 42 0 08 91 6 17 71 6 8 1三组数据的分布情况如图2 1 、2 4 和图2 7 所示，相应的f c m 算法和遗传算法聚类结果见图2 2 、2 3 以及图2 5 、2 6 和图2 8 、2 9 。01 0 02 0 03 遗传算法聚类结果图2 4 样本2 空间分布图图2 5f c m 聚类结果图2 6 遗传算法聚类结果图2 7 样本3 空间分布圈圈2 8 f c m 聚类结果图2 9 遗传算法聚类结果对数据集l 。两种算法都运行2 0 次，结果是两种算法都能获得2 0 次正确分类，实验中发现对于小样本时f c m 算法收敛时间明显少于遗传算法。在对数据集2 进行同样的2 0 次试验，结果f c m 算法只获得9 次正确分类，而基于遗传算法地聚类算法则获得了1 6 次正确分类。最后再对分离不好的样本3 运行2 0 次，结果是f c m 算法仅获得5 次正确分基于智能计算的数据聚类方法的研究类，露基予遮传算法趣聚类舞法获褥了1 8 次歪确分类。从上述实验结果可以得出，数据分布较好时，两种算法聚类效聚区别不大；假是，当数据分布不好时，f c m 算法聚炎效果明显下降，很容易陷入局部最优瓤蘩于遗传