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

基于群智能算法的聚类分析方法研究摘要针对现有的聚类分析方法在数据挖掘应用中存在的不足，本文结合群智能算法，对传统的聚类方法加以改进，提出了一些新的基于群智能算法的聚类分析方法；并分析了其方法的性能。通过实验验证了本文提出的基于群智能算法的聚类分析方法的有效性。归纳起来，研究成果主有以下4 个方面：1 ) 提出了基于人口迁移算法的聚类分析方法。该方法首先将待聚类的对象随机放置在一个二维平面上，每一个对象有一个随机初始位置，每一个对象能够在平面上移动，并测量对象在局部环境的群体相似度。通过转换函数将群体相似度转化成收入吸引力函数，根据收入吸引力函数来实现自组织聚类过程。2 、) 提出了一种新的基于人工鱼群的混合聚类算法。人工鱼群算法不需要先验知识，利用随机遍历的原则进行聚类分析。k 平均算法需要一个初始分割，运用确定启发式原贝廿进行聚类分析。首先对单个的数据对象运用人工鱼群算法进行聚类分析：然后考察聚类结果，根据结果选出供k 平均算法进行聚类分析的输入点；最后用k 平均算法进行聚类分析。3 ) 提出了一种新的基于人工鱼群算法的动态模糊聚类。通过引入模糊等价矩阵来表示高维样本之间的相似程度，并将高维样本映射n - 维平面。然后利用人工鱼群算法不断优化二维样本的坐标值，使样本之间的欧氏距离向样本间的模糊等价矩阵趋近，最终实现模糊聚类。4 ) 提出了一种基于差分进化算法的空间聚类算法。结合空间数据所特有的特点采用了一种基于差分进化的变异、交叉、选择操作，使得变异、交叉、选择过程能不断产生有意义的新个体，保证种群的多样性。对进化产生的新个体，即对变异交叉选择之后的个体插入了一次k 均值聚类计算，这样可以加快收敛速度。同时文中还在操作中作了一些灵活变动，实验证明效果较好。关键词：数据挖掘聚类分析群智能算法人工鱼群算法人口迁移算法差分进化算法c l u s t e r i n ga n a l y s i sm e t h o d sb a s e do ns w a r mi n t e l l i g e n ta l g o r i t h ma b s t r a c tt oo v e r c o m et h ef a u l t i n e s so ft h ea v a i l a b l ec l u s t e r i n ga l g o r i t h m sf o ra p p l i c a t i o n si nd a t am i n i n g ，b yc o m b i n i n gw i t ht h es w a r mi n t e l l i g e n ta l g o r i t h m s ，t h et r a d i t i o n a lc l u s t e ra n a l y s i sa l g o r i t h m sa r es y s t e m a t i c a l l yi m p r o v e da n di n n o v a t e di nt h i st h e s i s a n dt h en e wc l u s t e r i n ga n a l y s i sm e t h o d sb a s e do ns w a r mi n t e l l i g e n ta lg o r i t h m sa r ep r o p o s e d ，t h e na n a l y s i st h ep e r f o r m a n c eo ft h em e t h o d s t h ee x p e r i m e n t a lr e s u l t si l t u s t r a t et h ee f f e c t i v e n e s sa n dg o o dp e r f o r m a n c eo ft h ep r o p o s e dn e wi d e a sa n dn e wm e t h o d so nc l u s t e ra n a l y s i s i ns u m ，t h em a i nr e s e a r c h e si nt h i st h e s i sa r eg i v e na sf o l l o w s ：1 ) c l u s t e r i n ga n a l y s i sm e t h o db a s e do np o p u l a t i o nm i g r a t i o na l g o r i t h mw a sp r o p o s e d f i r s t l yp u tt h eo b j e c t si nt w o - d i m e n s i o n a ls u r f a c es t o c h a s t i c a l l y , e a c ho b j e c th a sas t o c h a s t i ci n i t i a lp o i n t ；e a c ho b je c tc a nm o v ei nt h es u r f a c e ，a n dt h e ns u r v e yt h el o c a le n v i r o n m e n tc o m m u n i t ys i m i l a r i t yo ft h eo b je c t t r a n s f o r m e dt h ec o m m u n i t ys i m i l 撕t yi n t ot h ei n c o m e a t t r a c t i o nf u n c t i o nt h r o u g ht h et r a n s f e rf u n c t i o n ，a n dt h e nr e a l i z e dt h eo r g a n i z a t i o nc l u s t e r i n gp r o c e s sa c c o r d i n gt ot h ei n c o m e a t t r a c t i o nf u n c t i o n 2 、lan e wm i xc l u s t e r i n ga l g o r i t h mb a s e do na r t i f i c i a lf i s hs c h 0 0 1a l g o r i t h mw a sp r o p o s e d a r t i f i c i a lf i s hs c h o o la l g o r i t h md o e s n tn e e dt h ep r i o rk n o w l e d g e ；i tu s e ss t o c h a s t i ct r a v e r s a lp r i n c i p l ef o rc l u s t e r i n ga n a l y s i s k m e a n sa l g o r i t h mn e e d si n i t i a ld i v i s i o n ，u s e sd e t e r m i n e d h e u r i s t i cp r i n c i p l ef o rc l u s t e r i n ga n a l y s i s f i r s t l yu s e st h ea r t i f i c i a lf i s hs c h o o la l g o r i t h mf o re a c hd a t ao b je c t ；t h e ni n s p e c t st h ec l u s t e rr e s u l t s ，s e l e c t st h er e s u l t sa se n t r a n c ep o i n to ft h ek - m e a n sa l g o r i t h m ；f i n a l l yu s e sk m e a n sa l g o r i t h mt oc l u s t e r i n ga n a l y s e s 3 、) ad y n a m i cf u z z yc l u s t e r i n gm e t h o db a s e do na r t i f i c i a lf i s hs c h o o ta l g o r i t h mi sp r e s e n t e d b yi m p o r t i n gaf u z z ye q u i v a l e n c em a t r i xt oe x p r e s st h ed i s s i m i l a rd e g r e eb e t w e e na n yt w od a t a ，a n dm a p p i n gt h eh i g hd i m e n s i o n a ls a m p l e st ot w od i m e n s i o n a lp l a n e s a n dt h e nu s i n gl ia r t i f i c i a lf is hs c h o o la l g o r i t h mt oo p t i m i z et h ec o o r d i n a t ev a l u e s ，m a k i n gt h ee u c l i d e a nd i s t a n c eo ft h es a m p l e sa p p r o x i m a t et ot h ef u z z ye q u i v a l e n c em a t r i xg r a d u a l l y ，f i n a l l yr e a l i z e dt h ef u z z yc l u s t e r i n g 4 ) as p a t i a lc l u s t e r i n ga n a l y s i sm e t h o db a s e do nd i f f e r e n t i a le v o l u t i o na l g o r i t h mw a sp r o p o s e d u s e sm u t a t i o n ，c r o s s o v e ra n ds e l e c t i n go p e r a t o ro fd i f f e r e n t i a le v o l u t i o n ，a n dc o m b i n ew i t ht h es p a t i a ld a t au n i q u ec h a r a c t e r i s t i c s ，t h e nt h en e wi n d i v i d u a l sa r ep r o d u c e du n c e a s i n g l yf r o mt h ep r o c e s s e s ，g u a r a n t e et h em u l t i p l i c i t y n e wi n d i v i d u a l sw h op r o d u c ef r o mt h ee v o l u t i o n ，n a m e l yt h ei n d i v i d u a l sf r o mt h ev a r i a t i o na n dc r o s s i n go p e r a t o r si n s e r tk m e a n sa l g o r i t h m ，t h u sm i g h ts p e e du pt h ec o n v e r g e n c er a t e s i m u l t a n e o u s l yi n c r e a s es o m ef l e x i b l ec h a n g e si no p e r a t i o n ；t h ee x p e r i m e n t a lr e s u l t sp r o v e dt h ee f f e c tw a sg o o d k e y w 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 ；s w a r mi n t e l l i g e n ta l g o r i t h m ；a r t i f i c i a lf i s hs c h o o la l g o r i t h m ；p o p u l a t i o nm i g r a t i o na l g o r i t h m ；d i f f e r e n t i a le v o l u t i o na l g o r i t h m1 1 1论文独创性声明本人郑重声明：所提交的学位论文，是本人在导师的指导下，独立撰写完成的。除文中已经注明引用的内容外，本论文不含其他个人或其他机构已经发表或撰写过的研究成果，也没有剽窃、抄袭等违反学术道德规范的侵权行为。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人愿意承担由本声明而引起的法律责任。研究生签名叫百日期：汐7 年二月2 尹日论文使用授权声明本人完全了解广西民族大学有关保留、使用学位论文的规定。学校有权保留并向国家有关部门或机构送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存、汇编学位论文。除在保密期内的保密论文外，允许学位论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。研究生签名面1 互导师签名：c 即轧吼伽7 年易月妒日期：加t i 年6 月矸日1 1 研究背景及意义1 绪论在过去的几十年，随着计算机硬件软件、数据库技术和i n t e m e t 的飞速发展以及人们获取数据手段的多样化，人类所拥有的数据量急剧增加，大量的数据被描述为“数据丰富，但信息贫乏 。快速增长的海量数据收集、存放在较大和较多的数据库里，在没有比较有力的分析工具的状况下，已经大大地超过了人们的理解能力和概括能力。在这种情况下，这种海量的原始数据和对功能强大的数据分析工具的需求共存的情况，被大家描述为“胖数据，瘦信息。很多的数据库也就成为了“数据坟墓”换句话来说，这些数据将很少被再用到。于是，人们结合统计学、机器学习、数据库等技术，提出了运用数据挖掘技术来解决这一大难题，数据挖掘技术就应运而生了，它显示出了超前的强大的生命力，从而慢慢成为了研究的热点和难点问题之一，吸引了非常多的专家学者进行研究。数据挖掘【l 】( d a t a m i n i n g ) ，简单地说，就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道盼、但又是潜在有用的信息和知识的过程。然而或许有人会问什么是知识呢? 我们可以从广义上理解：其实数据、信息是知识的表现形式，但人们更习惯地把模式、概念、规则、规律和约束等看作是知识。而把数据却看作是知识的源泉，就像是从矿石中采矿一样的。原始数据既可是半结构化的，比如图形、文本、图像数据甚至是分布在网络上的异构型的数据等；也可是结构化的，比如关系数据库中的数据。发现知识的方法既可是非数学的，也可是数学的；既可是归纳的，也可是演绎的。发现的知识既可用于数据自身的维护，还可用于信息管理、查询优化、决策支持和过程控制等。因此，数据挖掘技术就是一门交叉的学科，它涉及到了机器学习、知识获取、智能数据库、数据可视化、高性能计算、统计学等多个领域。数据挖掘把人们对数据的应用从低层次的简单查询，提高到从数据中挖掘知识，提供决策支持【2 1 。在这种需求情况下，各个领域的研究者，尤其是像可视化技术、数据库技术、数理统计、并行计算、人工智能技术等这些方面的学者和技术人员，投入到数据挖掘这一前沿的研究领域，现在已经形成新的研究热点。一个较典型的数据挖掘系统的结构如下图1 1 所示f l 】。其中，像数据库和数据仓库及其他的一些信息知识库都是数据挖掘技术工作的对象，都可以在数据上进行有效的数据集成和数据清理：服务器其实主要是用来回应数据挖掘的请求的，以此来提取有关的数据的；知识库最主要的任务就是用来指导数据挖掘的过程的，是用来评价挖掘出来的候选模式的；而模式评估的最主要的任务却是根据一定的度量标准来与数据挖掘模块进行交互的，用以使搜索向着我们感兴趣的模式发展；图形用户界面的主要任务主要是为了方便用户与数据挖掘系统的进行交互的，通过用户提出挖掘任务、给出重要的挖掘参数以及由当前返回结果指导下一步的挖掘工作。数据清理图1 1 一个典型的数据挖掘系统f i g u r e1 1at y p i c a ls y s t e mo fd a t am i n i n g数据挖掘功能是用来指定数据挖掘任务中要找出的模式类型的。数据挖掘的重要任务可分为下面几类【1 l 【3 4 1 ：类概念描述( c l a s s c o n c e p td e s c r i p t i o n ) 、关联分析( a s s o c i a t i o na n a l y s i s ) 、分类( c l a s s i f i c a t i o n ) 和聚类分析( c l u s t e r i n ga n a l y s i s ) 等。聚类分析作为数据挖掘中的一种有效的工具，它已经引起了人们的非常广泛的关注，近年来得到了迅速的发展和很多成功的应用。通过聚类，人们能够识别稀疏和密集的区域，发现全局的分布模式和数据属性之间的相互关系。聚类分析在客户分类、入侵分析、w w w 文本分类、基因识别、空间数据处理、卫星照片分析、医疗图象自动识别等领域有着相当广泛的应用，而其自身的研究也是一个蓬勃发展的领域，数据挖掘、空间数据库技术、机器学习、统计学、计算智能和市场学等的发展推动着聚类分析研究的进程，使它已成为数据分析和应用研究中的一个较热的话题。聚类分析中聚类分析方法的选择与聚类分析的具体任务是密不可分的，这是2因为应用领域对聚类分析的约束条件是不同的、各种各样的，同时作为聚类分析一部分的目标数据和领域知识自身也有着很多不同的表达方式，这就需要根据实际的聚类目的和各个领域特点来选择其具体的聚类算法。选择聚类算法的前提就是对它们进行比较的研究，择其优而用之。智能计算( i n t e l l i g e n c ec o m p u t a t i o n ) 1 5 1 就是通过模拟自然界中生物体和生物活动的自然现象发展而来的，用计算机描述和重现生物体中的某些个体行为，并同时用来改造自然的工程实践的新型人工智能研究领域。智能计算也被大家称之为“软计算 ，它是人们通过自然界和生物界动物活动规律的启发，根据自然界和生物界的原理，模仿它们的规律而设计出的求解问题的方法，在这里，我们就称它为智能算法。智能计算的研究领域是非常广泛，比如如果我们从方法上去看的话，现在的智能计算一般包括像d n a 计算、模糊控制、进化计算、神经网络、免疫算法和群体智能等等；然而目前正受到人们广泛关注的人工生命也是智能计算的研究领域。和传统算法相比智能计算的最大的特点就是不需要建立精确的模型，较适合于解决那些因为难以建立有效的模型而用传统人工智能技术又难以解决的甚至根本无法解决的问题。智能计算理论是受生物体系的一些机制启发而得到的，用于数据分析时，会继承生物系统的良好处理机制和特征，即：对模型有着自然的描述能力，并不需要建立精确的数学模型：对处理目标的特性有着比较良好的适应能力；具有良好的自组织特征；处理结果的可视化效果较好，便于理解和学习；具有一定的智能特征，从而可以获得一定的智能行为能力；大自然生物系统的多变性和多样性，也带来了处理目标的多样性；生物系统是大自然的一种客观存在，便于观察和分析，因此具有良好的开放性。通过以上分析，将智能计算用于数据分析是切实可行和有效的，有重要冉栅究意义和实际工程价值。同时另一方面，将智能计算理论用于数据分析时不仅能够提高处理数据分析的能力，同时也会使得智能计算理论自身得到不断的完善和发展，从而可以取得较好的实际应用效果。因此，将智能计算应用在数据分析中的研究实际上是一个双赢的研究方向。智能计算技术中蕴含了各种分支理论及方法，在论文中有针对性的选择了几种常见的智能算法用于数据挖掘中的聚类分析，并同时开展了一系列的研究，提出了一些新的相对较高效的聚类分析方法以适应不同问题的具体要求。1 2 聚类分析技术与研究现状1 2 1 聚类分析的定义及相关概念3聚类( c l u s t e r i n g ) 【l 是一种常见的数据分析工具，到目前为止，聚类还没有一个公认的定义。这里我们给出的是e v e r i t t t q 在1 9 7 4 年下的定义：一个类内的实体是相似的，不同类的实体是不相似的：一个类是测试空间中点的会聚，同一类的任意两个点间的距离小于不同类的任意两个点间的距离；类可以描述为一个包含密度相对较高的点集的多维空间中的连通区域，它们借助包含密度相对较低的点集的区域与其他区域( 类簇) 相分离。定义1 1 假设一个数据对象是由d 个属性所描述，则d 维数据空间九时由若干个具有d 个属性的数据对象所构成。在d 维数据空间中，数据对象通常被称作d 维数据点，则d 维数据点x 可表示为石= ( 玉，而) ，其中毛表示第f 个属性的值，d 表示空问的维数。定义1 2 由1 7 个d 维数据点组成的集合s 可表示为s = ( s ”，s 。 ，其中s ，= ( s n ，s 耐) ，且表示第i 个数据点的第个属性的值。定义1 3 根据数据点之间的相似性的测量，聚类分析就是将d 维数据集v 划分成 q ，g ，q 的过程，其中k 甩，e 矽，c v ( i = 1 , 2 ，七) ，并且ku e = y 。通常，g 一般被称做类或簇，这里我们统一称之为“类 。f = l1 2 2 聚类算法的类别没有任何一种聚类技术或方法是可以普遍适合于揭示各种多维数据集所呈现出来的多种多样的结构【7 1 。根据数据在聚类中的积聚规则以及应用这些规则的方法，有很多种聚类算法。聚类算法有很多种分类的方法，目前在文献中存在的很多的聚类分析算法，具体算法的选择主要取决于数据的类型、聚类的目的及应用。以下是在数据挖掘领域中得到广泛应用的主要聚类分析算法，主要包括层次方法( h i e r a r c h i c a lm e t h o d ) 、划分方法( p a r t i t i o n i n gm e t h o d ) 、基于密度的方法( d e n s i t y - b a s e dm e t h o d ) 、基于网格的方法( g r i d b a s e dm e t h o d ) 和其他聚类算法，如图1 2 所示的5 个类别。4图1 2 聚类算法分类图f i g u r e1 2t h ec l a s s i f i c a t i o nm a po fc l u s t e r i n ga l g o r i t h m1 2 2 1 层次方法层次聚类算法同时又称为树聚类算法9 1 ，它是使用数据的联接规则，通过一种层次架构方式，反反复复地将数据进行分裂或者聚合，来形成一个层次序列的聚类问题解。如果按自底向上进行层次分解，则称为凝聚的层次聚类方法；如果按自顶向下进行层次分解，则称为分裂的层次聚类。凝聚的层次聚类方法首先将每个对象作为一个类，逐渐合并这些类然后形成较大的类，一直至l j 所有的对象都在同一个类中，或者满足了某个终止条件时停止。分裂的层次聚类与之恰好相反，它则是首先将所有的对象置于一个类中，然后逐渐划分为越来越小的类，直到每个对象都自成一类，或者达到了某个终止条件时停止，例如达到了某个希望的类数目的个数，或者两个最近的类问的距离超过了某个阀值时停止。在解决具体实际聚类问题的时侯，我们通常会将其他聚类方法和其层次聚类方法进行集成，形成多阶段聚类。像这类聚类算法包括较早的b i r c h ，c u r e ，r o c k 和c h a m e l e o n 算法以及近几年提出的r c o s d 、b i n a r yp o s i t i v e 、b i r c h 等算法。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 dc l u s t e r i n gu s i n gh i e r a r c h i e s ) 廉类算法1 1 0 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 ) 聚类算法【 ，采用了一种较新的层次聚类算法。这种方法一般是采用了划分与随机抽样相结合的方法来提高效率，对于大型的数据库系统有比较好的伸缩性。c h a m e l e o n 聚类算法【1 3 】是一个采用动态模型的层次聚类算法。它是采用连接图g 的k 最近邻居模型来稀疏化连接矩阵的，所有顶点之间k 个最相似的点之间是用边相连，其余的均被剪枝。与前面的c u r e 等算法相比，c h a m e l e o n 聚类算法在发现高质量的任意形状的类方面有较强的能力。r o c k ( r o b u s tc l u s t e r i n ga l g o r i t h mf o rc a t e g o r i c a ld a t a )聚类算法( 1 2 1 ，是在c u r e 基础上发展而来的，一般适用于布尔和分类数据可选的凝聚层次聚类新算法。这种算法是把两个类的聚集互连性与用户定义的静态互连性模型进行比较，进而来度量两个类之间的相似度的。近几年，正二进s o ( b i n a r y - p o s i t i v e ) 方法在文献 1 4 中被提出：这种方法是把待分类数据以正的二进制形式存储在一个二维矩阵中，其中，行表示的是记录，列表示的是其属性的可能取值。记录对应的取值是为1 或者0 ，分别表示此记录有对应的属性值或者不存在对应的属性值的情况。文献 1 5 提出了连续数据的粗聚类算法( r o u g hc l u s t e r i n go fs e q u e n t i a ld a t a ，简称r c o s d ) 。粗聚类算法r c o s d 的关键思想就是寻找能够捕捉数据序歹i j 的连续信息及内容的特征集，并把这些特征集映射到一个上近似空间中，同时应用约束相似性上近似技术来获取粗类簇的上近似，其中一个元素可以属于多个类。2 0 0 8 年周兵等人i 2 q 提出了一种基于g i s t的层次聚类算法，该方法利用通用搜索树实现了一种新的层次聚类算法，可以把整个聚类过程中形成的树型结构都保存在硬盘上，支持从宏观到细微的分析过程，便于用户发现各个聚类之间的相互联系。1 2 2 2 划分方法1 9 6 7 年，m a c q u e e n 首次提出了k 一均值聚类算法( k m e a n s 算法) 。到目前为止，许多聚类任务都是选择了这个经典的算法。这个算法的核心思想是找出k 个聚类中心q ，乞，q ，使每一个数据点一和与其最近的聚类中心c 。的平方距离和达到最小( 该平方距离和被称为偏差d ) 。k 一均值聚类算法( k m e a n s ) 【8 l ( 对n 个样本进行聚类) ，给定一个包含疗个数据对象的数据集，及要生成的簇类的数目的个数k ，该划分方法就是将数据划分成k 个划分他刀) ，其中每个划分表示一个类。k 均值聚类算法能够对大型数据集进行有效的分类，其中计算复杂性为o ( t k m n ) ，通常k ，m ，t 0 ；i = 1 ，2 ，n ；j = l ，2 ，玎) ，得到一区域n兀【z 乙一万：，x 1 + 万：】。因为人口流动的规律性较差，所以我们将人口流动处理j = 1jjji成随机的。另外将人口流动进一步处理成均匀随机的变动。初始化时可以在每一个区域内随机生成若干个点，然后随机移动这些点。1 52 ) 人口迁移其它区域的人口被优惠区域吸引过来，这里将迁移过程简化处理，就是迁移时所有人都向优惠区域迁移。模拟时在优惠区域内随机生成个点，替换掉其他非优惠区域内的点。优惠区域是以当前最大的收入吸引力函数f ( x ) 值所在的点为中心重新划定的。3 ) 人口流动人们在优惠区域内进行人口流动。优惠区域内的个点每完成一次随机变动，就要找出收入吸引力函数的最高点，并重新划定区域。4 ) 人口扩散当优惠区域人口压力增加到一定程度后，就会出现人口向外扩散的现象，这时人口迁出优惠区域到人口密度低的区域。5 ) 信息传媒最后是模拟优惠区域信息传媒。将媒体广告、亲友、劳务市场等传媒抽象为最优点记录单元。2 2 基于人口迁移算法的聚类分析把人口迁移算法运用到聚类分析中是对人们迁移行为进行研究发现的启发式算法。其主要思想是：将待聚类的对象随机放置在一个二维平面上，每一个对象有一个随机初始位置，每一个对象能够在平面上移动，并测量对象在局部环境的群体相似度。通过转换函数将群体相似度转化成收入吸引力函数，根据收入吸引力函数将实现自组织聚类过程，即在平面上形成若干由同一类别的对象聚成的集簇。2 2 1 群体相似度定义群体相似度是一个待聚类对象与其所在局部环境中所有其它对象的综合相似度。群体相似度的基本测量公式是：】，= 1 社n 壹i = id ( d j ，q ) )( 2 1 )用欧式距离表示嗍。a ( o ，口，) 表示对象属性空间中对象d ，与d _ ，之间的距离。2 2 2 各点收入吸引力函数各点收入吸引力函数是人们即待聚类对象移动的标准。各点收入吸引力函数制定的主要原则是群体相似度，群体相似度越大各点收j k 吸引力f ( x ) 函1 6数越大，群体相似度越小各点收入吸引力f ( x ) 函数就越小。公式如下：i厂( x ) = t r y i ( - 吉i 以一厶1 )( 2 2 )“j = n ，刊其中：口为收入吸引力系数，】，为群体相似度，k 为人口迁移聚类过程中所形成的聚类中心个数，x x 一为聚类中心位置。需要说明的是人口迁移算法是一个比较复杂的过程，在本文聚类算法中，并不是与文献 9 4 完全对应起来，而是根据人口迁移算法的思想提取人口迁移过程中有用的要素来实现聚类分析。整个人口迁移聚类算法的过程如下：在该算法中，人及其所在地用点表示，= ( x ，x i 。) 表示第f 个点，一r ”，x i ，表示第f 个点的第j f 个分量；艿= ( 一，万。) ，r ”，表示的第个分量， 0 ，i = 1 ，2 ，n ，j = 1 ，2 ，n ，n 表示人口规模。s t e pl初始化二维平面大小、循环次数等各参数，在二维平面内均匀随机产生个点x i 工2 ，。对每一个f ，令第f 个区域的中心c e n t e r = ，确定第f个区域的上下界c e n t e r + - 5 ，其中取8 ，= ( 6 ，一a ) ( 2 n ) ，i = l ，2 ，n ，j = 1 , 2 ，n ，( ，的上述取法使得各是相等的，因此下面的步骤中取消艿的上标) 。s t e p2计算各点的收入吸引力f ( x ) 。s t e p3按步s t e p2 所得的计算值，初始化最优记录值和最优记录点。& 印4在各自区域内进行人口流动。均匀随机变动每一个点：一= 2 8 r a n d ( 毒) + ( c e n t e r - 8 ) ，其中r a n d ( 木) 为随机数函数。若x 7 _ ， 屯，贝l j 令x j = 岛；若x ， 口- ，则令戈，= a j 。孵印5计算各点的收入吸引力f ( x 7 ) 。& 印6记录最优值，记录最优点。s t e p7人口流动次数n u m 若小于预先指定的次数则转衙印4 。s t e p8人口迁移：以各个吸引力最大点( 即最优记录点) 为中心，按万各分量的大小确定优惠区域，在该区域内均匀随机产生1 个点，替换原来的点。s t e p9计算各点的收入吸引力f ( x ) 。s t e p1 0记录最优值，记录最优点。s t e p1 1在优惠区域内进行人口流动且人口随经济重心转移：以吸引力最大点( 即最优记录点) 为中心，按万各分量的大小确定优惠区域，在该区域内均匀随机产生1 个点，替换原来的点。s t e p1 2计算各点的收入吸引力f ( x ) 。& 印1 3记录最优值，记录最优点。s t e p1 4人口流动次数n u n 若小于预先指定的次数，转步骤s t e p1 1 。1 7s t e p1 5报告结果。脚1 6记录最优值，记录最优点。s t e p l 7迭代次数m 加1 ，若迭代次数小于指定次数财转s t e p 4 。s t e p l 8结束。2 3 实验结果及分析程序的实现是基于m a t l a b6 5 ，我们通过对2 组数据的聚类分析来验证本文算法的性能，第1 组数据d a t a l h 5 0 0 个二维点组成，它们可划分为5 个集合。d a t a l用以下方式生成：首先选择5 个点qo = 1 2 ，5 ) 作为5 个聚类的中心点，然后按人1 3 迁移算法进行聚类生成以。为中心的聚类。第2 组数据d a t a 2 是使用i r i s 植物样本数据，i r i s 样本数据由分别属于三种植物的1 5 0 个样本组成，每个样本埒有4种属性特征。对算法进行3 次测试，每次对算法的正确率和所用时问进行考察。实验中人口迁移聚类算法的参数选取如下：总循环次数2 0 ，人口在各自空间内流动次数1 0 ，城市规模d a t a l 取5 ，d a t a 2 取3 ，二维平面大小o 一2 5 。该算法的聚类结果选取各实验中任意一个聚类结果图如下国所示；图置l 为本文算法d a t a l 的聚类结果图，图2 2 为文献 9 8 中算法d a t a l 的聚类结果图，图2 3 为本文算法d a t a 2的聚类结果固。表2 1 为本文提出的基于人口迁移的聚类算法的d a t a 2 仿真实验结果；表22 是文献 9 7 基于蚁群的聚类算法的铡试结果。，。嶙芝。? ，一j 。j 擘?j ，+ ：、，一l-、：q _ *图21 本算法d 血1 的聚类结果图f i g m 2 i t h e c l u s t e fr e s u l t o f d a t a lf o r u m g t h e n e w a l g o d t h m二”，簿尊图22 文献 9 8 的聚类效果图i r c 22 t h ec l u s t e rr e s u l t o f d a t a li n l i t e r a t u r e 【9 9 1从图1 实验结果可看出结果是令人比较满意的，它与文献 9 8 的聚类结果图22 相比：聚类结果远远优于文献 9 8 中算法的聚类结果。，i。”jl| ：卜_ ”喈f _ 鑫# i # 1 r 名图23d a t a 2 的聚类结果圈f i g u r e 2 ：；t h ec l u n e fr e s u l t o f d a t a 2表2l 本文测试结果t a b l e 2 1 t e s t l l g $ e l t s o f t h e n e wa l g o r i t h m考察项时间正确率l7 6 9 s9 127 3 0 m s9 0 637 9 0 m s9 2 4表2 2 文献 9 7 结果t a b l e 2 2 t h e i 龆脚t s o f l i l e r a h l l f 9 7 1考察项时间正确瓤17 2 5 0 m s8 927 2 6 6 m s7 537 2 3 5 m s8 9相比文献 9 7 基于蚁群的混合聚类算法，实验结果比较表明，基于人口迁移的聚类算法得到的结果，在时间效率和正确率上都能达到较好的聚类效果，优于文献 9 7 的算法。实验表明基于人口迁移的聚类算法同样达到较好的聚类效果。2 4 本章小结本章给出了一种基于人口迁移算法的聚类分析方法。人口迁移算法是模拟人们迁移的过程，具有很好的自组织、自适应和自学习能力，在求解优化问题的全局最优解方面具有很好的应用。本文我们主要的工作是将人口迁移算法应用到聚类分析中，并进行了对比仿真实验，实验结果表明，基于人口迁移算法的聚类分析能达到较好的聚类效果。3 基于人工鱼群的混合聚类算法本章主要研究了基于人工鱼群的混合聚类算法。首先分析了k - 平均算法的优缺点，然后根据人工鱼群算法的特点，提出了一种基于人工鱼群算法的聚类分析算法，并把它与传统的k - 平均算法结合得到一种新的混合聚类算法。3 1 人工鱼群算法简介人工鱼群算法( a r t i f i c i a lf i s hs w a r ma l g o r i t h m ，a f s a ) 是李晓磊【1 0 7 1 删等人提出的一种基于动物自治体的优化方法，它是模仿鱼类的行为方式，是集群智能思想的一个具体应用。因此，本文算法就运用鱼群的聚群行为而实现聚类的，通过对鱼类生活习性的观察，给出了适用于本算法的几种典型的行为：随机行为：鱼在水中随机、自由的游动寻找食物的过程。聚群行为：这是为了保证群体的生存和躲避危害而形成的一种生活习性，鱼群的形成是一种突现的生动示例。觅食行为：我们平时会看到鱼儿在水中自由自在的游来游去，然而当它们发现食物的时候，就会向着食物多的方向快速游去。追尾行为：当某条鱼发现食物时，其附近的鱼会尾随其临近的伙伴快速至i j 达食物点。本节在探讨基于人工鱼群算法的聚类分析算法之前，首先，对以上鱼群的行为分别建立数学模型，详细如下：3 1 1 行为描述在这里，我们记当前人工鱼所在位置的食物浓度为厂( 置) ，d ( o i ，0 ，) 表示为人工鱼个体间的距离；v i s u a l 表示人工鱼的感知距离；s t e p 表示人工鱼移动的步长：万表示拥挤度因子。随机行为：我们假设人工鱼当前的状态为x ；，在它的感知范围内随机选择一个状态x ；进行移动。觅食行为：人工鱼当前状态假设为x 在它的感知范围内随机地选择一个状态x ，如果当前位置的食物浓度函数值小于j ，状态下食物浓度函数则向该方向前进一步；否则，再重新选择状态x ，继而判断是否满足前进条件；反复几次后，如果仍不能满足前进的条件时，则随机地移动一步。聚群行为：假设人工鱼当前状态为置，探索当前邻域内即( d ( o ，0 ，) a f ( 五) 时表明伙伴中心有较多的食2 1物，则朝伙伴的中心位置方向前进一步；否则执行觅食行为。追尾行为：假设人工鱼的当前状态是x ，探索当前邻域内即( d ( o f ，o y ) 8 f ( x f ) 表明伙伴中心有较多的食物，则朝伙伴x ；方向前进一步；否则执行觅食行为。约束行为：在聚类过程中，由于聚群行为、随机行为等操作的随机性，容易使人工鱼的状态变得不可行，这时就需要加入相应的约束策略来对其进行规整化，使它们由无效状态或不可行状态转变成可行的。3 2 基于工鱼群算法的聚类思想把人工鱼群算法运用到聚类分析中，其最主要思想是：将待聚类的对象随机放置在二维平面上，每一个对象都赋予一个随机初始位置，每一个数据对象( 人工鱼) 都能够在平面上移动，并同时测量数据对象( 人工鱼) 在局部环境的群体相似度。根据群体相似度来实现自组织聚类的过程。定义1 群体相似度群体相似度是将要聚类的对象与它所在位置局部环境中其它对象的综合相似度。群体相似度的定义公式是】，= 言j ( 巳)( 3 1 )式中a ( o ，0 ，) 表示对象属性空间中对象0 ，与0 ，之问的距离。定义2 食物浓度函数食物浓度函数是待聚类的数据对象( 人工鱼) 移动的标准。食物浓度函数的来源是根据群体相似度，群体相似度越小食物浓度就越大，群体相似度越大食物浓度越小。公式如下：厂( t ) = 三( 昙，毫，k k l + 争( 3 2 )其中：y 为群体相似度，k 为人工鱼聚类过程中所形成的聚类中心个数，以、为聚类中心位置。3 2 1 人工鱼群聚类算法描述人工鱼群算法聚类的过程如下：s t e p1 初始化可视域大小、人工鱼个数、移动步长、循环次数、二维平面大小等各参数；s t e p2 把待聚类数据对象随机放置于一个二维平面上，即随机赋给每个对象一对b ，j ，) 坐标；& 印3 循环次数加1 ；s t e p4 人工鱼开始进行聚类循环；s t e p5 计算每条人工鱼的群体相似度用式( 3 1 ) ；s t e p 6 探索当前位置的人工鱼周围的聚类中心位置x ，并同时测量它的群体相似度；s t e p 7 根据当前数据对象( 人工鱼) 与周围聚类中心位置的群体相似度的大小并进行聚群行为和追尾行为，如果不满足前进条件则执行觅食行为；s t e p8 如果一组内所有的人工鱼都结束了移动，就继续向下执行，否则就转s t e p 4 ：s t e p9 如果还没达到最大循环次数，则转s t e p3 ，否则，就输出结果，结束程序。3 3k 平均算法k 平均聚类算法是一种基于划分的聚类分析方法，假设给定有刀个对象的数据库和k ( k 为要形成的聚类的个数) 。一个划分的方法就是构建数据对象的k 个划分( k 甩) ，每一个划分就代表了一个聚类。聚类的依据是对象之间的相似度，我们常常是用距离来衡量的，如曼哈坦距离和欧几里得距离。聚类分析的结果就是达到类内的对象尽可能相似，而类间的对象却尽可能的不回。最常用的划分方法是k - 中心点算法和k - 平均算法。3 3 1k - 平均算法的工作原理从数据集的，? 个对象中随机的选取k 个，当做初始的聚类中心；然后，对其他的每一个数据对象，计算这些数据对象到这k 个聚类中心的距离，来比较得封这些数据距离哪一个聚类中心是最近的，则相应的对象就被指定到相应的类中；接着，计算新形成的每个类的数据对象的平均值，然后把这个平均值当作新的聚类中心，仍然用前面的步骤把数据按照距离最近的原则聚到相应的类中；这个过程不断迭代，直到准则函数收敛。准则函数定义为平方误差，公式如下：ke - - ee l 一朋，1 2i = lp e c i( 3 3 e 是数据库中数据对象的平方误差的和，尸表示给定的数据对象，是空间中的点；m ，是聚类c ，的平均值。这个准则使形成的k 个聚类类间的数据尽量不同，类中数据尽量相似。3 3 2k 平均算法的步骤k 平均聚类算法的过程大概描述如下：输入：一个具有刀个对象的数据库及聚类的数目k 。输出：k 个聚类，