（运筹学与控制论专业论文）基于改进粒子群算法的c均值聚类算法研究.pdf

南京师范大学顾i ：学位论文摘要 摘要 聚类是一个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认识世界 就必须区别不同的事物并认识事物间的相似性，而每个概念的最初形成无不借助于事物的聚 类分析。因此，聚类分析的研究不仅具有重要的理论意义，也具有重要的工程应用价值和人 文价值。传统的c ，均值聚类算法思想简单，易于实现。而且运行速度快，内存消耗小，能有 效地处理人数据集。是目前最常用的聚类算法之一。但是它们存在两个主要的缺点：对初始 划分矩阵敏感和容易陷入局部极小值。 为了解决上述问题，本文研究了基于改进粒子群算法的c 一均值聚类算法。首先对粒子群 算法做了部分改进，将加速系数的取值和惯性权重结合起来提出了一种具有沿折线先增后 减惯性权重的粒子群算法可以从理论上保证该粒子群算法的收敛性。然后将这一改进的粒 子群算法引入到c 均值聚类算法中，以增加隶属度矩阵的初始化多样性，解决c - 均值聚类 算法对初值的敏感问题，避免算法容易陷入局部极小值。仿真实验验证了该算法的有效性， 实验比较结果表明，该算法比单一使用c 一均值聚类算法的聚类效果更好。 关键词：粒子群算法、聚类、c - 均值、模糊c 一均值 堕塞堑蔓盔竺堡主堂竺堡苎 苎! 苎! ! 竺 a b s t r a c t c l u s t e r i n gi sa na n c i e n tp r o b l e ma n d i ta c c o m p a n i e sw i t ht h eh u m a ns o c i e t y se m e r g e n c ea n d d e v e l o p m e n ta n dg o e sd e e p e em a n k i n d sw a n t i n gt ok n o ww o r l dh a st od i s t i n g u i s hd i f f e r e n tt h i n g s a n dk n o ws i m i l a r i t yb e t w e e nt h i n g s ，b u te v e r ye a r l i e s ts t a g eo fc o n c e p tf o r m a t i o na s k sf o rh e l pf r o m c l u s t e r i n ga n a l y s i so ft h i n g s t h e r e f o r er e s e a r c ho nc l u s t e r i n ga n a l y s i sh a sn o to n l yi m p o r t a n l t h e o r e t i c a | s i g n i f i c a n c e b u ta l s oi m p o r t a n te n g i n e e r i n ga p p l i c a t i o nv a l u ea n dh u m a n i t i e sv a l u e t r a d i t i o h a lm m e a n sc l u s t e r i n ga l g o r i t h mw h i c hc a np r o c e s sb i gd a t as e te f f e c t i v e l yi ss i m p l ea n dr u n r a p i d l yw i t h o u tc o n s u m i n gm e m o r yo v e d y , a l t h o u g hc - m e a n s i so n eo ft h em o s tc o m m o na l g o r i t h m s i th a st w om a i nd i s a d v a n t a g e s ：i t ss e n s i t i v i t yt oi n i t i a lp a r t i t i o nm a t d xa n di t sb e i n gp r o n et ob e t r e p p e di nl o c a lm i 川m a l t h i st h e s i sp r e s e n t sa ni m p r o v e da l g o r i t h mc a l l e dc - m e a n sb a s e do nm o d i f i e dp a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h mt oo v e r c o m et h et r a d i t i o n a lm m e a n s ls h o r t c o m i n g sf i r s t l y , an o v e lp a r t i c l e s w a r mo p t i m i z a t i o na l g o r i t h mi ss t u d i e dt h ea l g o r i t h mw h i c hi n c o r p o r a t e sa c c e l e r a t e df a c t o ra n d n e r t i aw e i g h ta n di n c r e a s e st h ei n e r t i aw e i g h tl i n e a r l yi nt h eb e g i n n i n ga n dr e d u c ei _ ti nas t r a i g h tl i n e a tl a s t w h i c hc a nb ep r o v e dc o n v e r g e n ts e c o n d l y , t h ei m p r o v e dp a r t i c l es w a r mi sa p p l i e dt o c - m e a n sa l g o r i t h mt oo v e r c o m ei t ss h o r t c o m i n g s a tl a s t c o m p u t e rs i m u l a t i o ni si m p l e m e n t e da n d e x p e r i m e n t s lr e s u l t sp r o v ei t sv a l i d i t y k e y w o r d s ：p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m 。c l u s t e r i n g ，c m e a n s ，f u z z yc 。m e a n s n 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 、本论文除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文除引文和致谢的内容外，不包含其他人或其它机构已经发表或撰写过 的研究成果。 5 、其他同志对本研究所做的贡献均己在论文中作了声明并表示了谢意。 作者签名 日期 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版；有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅；有权将学 位论文的内容编入有关数据库进行检索；有权将学位论文的标题和摘要汇编出 版。保密的学位论文在解密后适用本规定。 作者签名： 日期 南京师范人学硕j ：学位论文第一章序论 1 1 引言 第一章序论 随着计算机硬件技术和软件技术的飞速发展，尤其是数据库技术的日益普及，人们面l 瞄 着快速扩张的数据海洋，获取各种数据的能力提高很快，大量的数据被广泛使用。如何有效 地利用这些数据。已成为一个焦点问题之一模式聚类是一种处理大量的、繁杂的，属性众 多的数据的有效方法。 聚类就是将一个对象的集合分割成几个类，每个类内的对象之间是相似的，但与其他类 的对象之间是不相似的传统的聚类分析只能用来分类具有清晰界限的对象，它把每个对象 严格划分到某个类别中，具有“非此即彼”的性质，如。对错”、“男女”、“有无”等，是一 种硬化分。而实际上大多数对象并没有严格的属性，它们在性态和类属方面存在着中介性， 具有“亦此亦彼”的性质，如。许多”、“很少”，“经常”、。有时”等等，属于软化分模糊 集理论的提出为这种软划分提供了有力的分析工具。人们开始用模糊的方法来处理聚类问 题，并称之为模糊聚类分析。 模糊集是于1 9 6 5 年引入的，其目的是作为描述与处理广泛的不精确性、模糊的事件的 基础理论该理论的发展己形成了有关纯数学与应用数学的许多分支，其中包括拓扑学、图 论、映射、自动控制和模式识别等，它可以表示语言信息，并可度量某种模式( 事物) 出现 的程度由于模糊聚类得到了样本属于各个类别的不确定性程度表达了样本类属的中介性， 即建立起了样本对于类别的不确定性描述，更能客观地反映现实世界从而成为聚类分析研 究的主流 d 均值和模糊口均值聚类算法是一种普遍采用的聚类方法o 均值聚类算法以点为原 型，是最早的目标聚类算法能够实现球形数据的聚类该算法思想简单，易于实现，而且 运行速度快，内存消耗小，能有效地处理大数据集，是目前最常用的聚类算法之一目前该 算法的研究主要集中在以下几个方面：距离定义的扩展、数据类型与聚类空间的扩展、聚类 准则的发展、抑制噪声能力的提高、初始化方法的发展，算法收敛性的研究及极值点的检测、 寻优能力的提高、聚类有效性研究、收敛速度的提高、与先验知识或其它算法相结合f 1 】等等。 鉴于模糊。均值聚类算法的高效性和广泛应用，人们在此基础上对其进行了发展和深化。提 南京师范大学硕仁学位论文 第一章序论 出了许多模糊d 均值类型的算法。文献【2 】从目标函数的演化、算法的实现途径和有效性度量 方式等三个方面综述了这类方法的研究进展及现状。 但是d 均值聚类算法和模糊d 均值聚类算法存在着两个主要的缺点：对初始划分矩阵 非常敏感，只有在初值确定的情况下，聚类结果才是唯一确定的：两种算法都是局部搜索寻 优算法，容易追寻目标函数而陷入局部极小值，而且算法在很大程度上依赖丁初始分类的选 择，如果初始分类严重地偏离全局最优分类时，算法很可能陷入局部极小值得到一个局部 最优解。 为了解决上述问题，有学者将遗传算法引入到d 均值聚类算法中嗍，通过变异、交叉 等措施来提高算法的自适应能力，能够提高收敛速度，解决局部极小值问题，在处理多样本、 多属性、多类别问题时，可以得到很好的聚类结果；也有文献报导了基于蚁群算法的聚类方 法嘲，利用蚁群算法的全局搜索性、并行计算性等特点可以避免聚类陷入局部最优解而 且能够自动决定聚类的数目，明显改善聚类质量。 以上研究表明，用智能算法实现d 均值聚类是一种发展趋势。粒子群算法是近些年才提 出的较新的仿生算法，用其解决聚类问题是一种新思路。近年来，也有学者尝试用粒子群算 法解决聚类问题嘲1 9 1 【”，有的将k - m e a n s 的聚类结果作为一个粒子和利用新的分类中心调撬 粒子位置，或者将粒子群算法应用到k - m e a n s 聚类算法中，提出了g b e s tp s o 聚类算法和 p s o - k - m e a n s 混合聚类算法，以提高k - m e a n s 聚类算法的收敛速度，克服k 均值聚类算法 容易陷入局部极小值的缺点；或者在传统的聚类算法中引入粒子群算法，能克服传统聚类算 法存在的问题，全局寻优能力优于现有的基于遗传算法的k - m e a n s 聚类算法，而且具有较 快的收敛速度。本文从另一个角度，对粒子群算法进行了改进用该改进的算法实现d 均值 聚类算法和模糊c 一均值聚类算法。该算法首先将加速系数的取值和惯性权重结合起来，使用 一种沿折线先增后减的惯性权重因子，这样可以从理论上保证改进的粒子群算法收敛。然后 将这一改进的粒子群算法引入到d 均值聚类算法中，通过使用粒子群算法对样本数据进行初 始划分，增加隶属度矩阵的初始化多样性，因为粒子群算法在解空间中不是局限于一点而 是同时处理一群点的特点，可以避免或降低对初值敏感和局部极小问题。因此，该算法可以 有效克服d 均值聚类算法初始化的单一性，减慢局部搜索，促进在全局范围丙的寻优搜索， 有效地克服了d 均值聚类算法过分依赖聚类参数的初始值和容易陷入局部极小的缺点。仿真 实验表明，该算法比单一使用c 一均值聚类算法或模糊d 均值聚类算法的聚类效果更好。 南京师范人学硕仁学位论文 第一章序论 1 2 本文的主要研究内容 针对d 均值聚类算法和模糊c 均值聚类算法的初值敏感和局部极小值问题，本文首先 对粒子群算法进行改进，将加速系数的取值和惯性权重结合起来，使用一种沿折线先增后减 的惯性权重因子，从理论上保证改进的粒子群算法收敛。然后将这一改进的粒子群算法引入 到聚类算法中，提出了基于粒子群算法的口均值聚类算法( p s o h c m ) 和基于粒子群算法 的模糊c 均值聚类算法( p s o f c m ) ，并给出了算法的详细步骤。仿真实验表明，这两种算 法的聚类效果都比单一使用d 均值或模糊。均值的聚类效果要好 概括起来，本文的主要研究内容如下： 1 ) 分析已有粒子群算法的优越性、收敛性及不足t 据此研究改进方法和算法； # 2 ) 对改进的粒子群算法进行计算机仿真实验，验证其有效挂并与其它算法进行仿真实验 比较； 3 ) 研究用改进的粒子群算法实现d 均值聚类算法( p s o h c m ) 并通过计算机仿真实验 验证其有效性： 4 ) 研究用改进的粒子群算法实现模糊d 均值聚类算法( p s o f c m ) 并通过计算机仿真 实验验证其有效性 t 3 本文的组织结构 本文的组织结构如下： 第一章序论：初步介绍聚类的概念及常用的d 均值聚类算法的研究现状，指出该算法 的优缺点。以及针对其缺点目前已有的解决方法然后介绍本文的研究目的和 要解决的问题，介绍本文的士要研究内容以及本文的组织结构； 第二章基本粒子群算法的原理及应用：详细介绍基本粒子群算法的思想、算法流程、 特点及应用以及粒子群算法存在的问题，为后续章节莫定基础 第三章聚类及d 均值聚类算法：为了研究基于粒子群的d 均值聚类算法，本章简单 介绍了聚类的概念及其好坏的判断标准，给出了聚类分析的概念、分类及其数 学模型，详细介绍了c 一均值和模糊c 均值聚类算法的原理以及它们之间的芙 ， 南京师范大学硕士学位论文第一章序论 系及各自的特点； 第四章基于改进粒子群算法的d 均值算法：针对c 均值聚类算法的缺点，引入本文 的核心内容之一，提出了基于改进粒子群算法的。均值聚类算法( p s o h c m ) 。 首先对粒子群算法作了改进，然后将改进的粒子群算法和。均值聚类算法相结 合而得到该算法，并详细介绍了该算法的思想及其算法流程。并通过实验验证 了该算法的有效性； 第五章基于改进粒子群算法的模糊d 均值算法：本章作为本文的核心内容之一，将改 进粒子群算法和模糊d 均值聚类算法相结合，提出了基于改进粒子群算法的模 糊。均值聚类算法( p s o f c m ) ，详细介绍了算法的思想及其算法流程，并通 过实验验证了该算法的有效性； 第六章总结与展望：对本文进行了总结，并对以后的工作作出进一步展望。 南京师范夫学硕1 学位论文第_ 二章基本粒了群算法的原理发戍用 第二章基本粒子群算法的原理及应用 本文研究基于改进粒子群算法的。均值聚类算法，因此，本章先简要介绍了基本粒子 群算法的思想，算法流程、特点及粒子群算法存在的问题等，为后续章节奠定基础。 2 1 基本粒子群算法介绍 众所周知，群居动物的群体聚集行为可以使它们有效的觅食和逃避追捕。我们经常能够 看到成群的鸟、鱼或者浮游生物聚集在一起进行觅食，当某个个体发现食物之后，它将通过 接触或者发出某种化学信号来招募同伴，使整个群落找到食源。观察鸟群的飞行也可以发现： 鸟群中的每只鸟在初始状态是处于随机位置向各个随机方向飞行，但是随着时间的推移，这 些初始处于随机状态的鸟通过自组织逐步聚集成一个个小的群落，并且以相同速度朝着相同 的方向飞行，然后几个小的群落又聚集成大的群落，大的群落也可能又分散为一个个小的群 落，但最终的结果是整个群落聚集到同一个位置一食源。自然界中的生物通常也具有类似于 鸟群和鱼群的上述特点。根据对人类群体行为的观察，每个个体的行为也是建立在群体行为 的基础之上的，比如习惯和一些根据其他个体经验而做出的行为，也就是说：在整个群体中 信息是共享的，而且在群体中的个体之间存在着信息的交流与相互协作强调群体中的每个 个体的特性，更强调个体之间的相互交互作用，这就是粒子群算法( p a r t i c l es w a r m o p t i m i z a t i o n 。p s o ) 算法的前提和原则u “ p s o 算法是1 9 9 5 年由美国社会心理学家j a m e sk e n n e d y 和电气工程师r u s s e l e b e r h a r t 基于对群聚行为生物的研究而提出的一种模拟社会行为的进化计算方法他们在 1 9 9 5 年的i e e e 国际神经网络学术会议上正式发表了韪为。p a r t i c l es w a r mo p t i m i z a t i o n 的文章| 1 2 1 ，标志着p s o 算法的诞生。最初p s o 算法是为解决连续变量的非线性优化问题提 出的现在己经很方便地扩展到离散变量的求解中它以一个简单的概念为基础，实现简单， 计算量和占有的内存小，算法的性能却可以和遗传算法相媲美，因而近年来己经在工程领域 中得铆广泛的应用。 粒子群算法的基本思想是【1 两：优化问题的候选解都是搜索空间中的一个粒子。所有的粒 子都对应一个由被优化函数决定的适应值，每个粒子的速度决定它们的飞行方向和距离然 后所有粒子就在解空间中追随最优粒子。粒子群优化算法初始化为一群随机粒子，然后通过 多次迭代找到最优解。在每一次迭代中，粒子通过跟踪两伞极值来更新自己，其中一个极值 5 南京师范犬学硕 j 学位论文 第二二章桀奉粒了群算法的原理发应用 是粒子本身所找到的最优解，这个解称为个体极值；另一个极值是整个粒子群目前找到的最 优解，这个解称为全局极值。迭代一定次数后。该算法将收敛，收敛性证明已由l o a nc r i s t i a n t r e l e a l l 4 1 给出这里不再给出。 粒子群算法和遗传算法有很多共同之处【1 目：两者都采用“群体”与“进化”的概念，都 是随机初始化种群，同样也都是依据个体的适应值来评价系统，而且都根据适应值来进行一 定的随机搜索。两个系统都不是保证一定能找到最优解。所不同的是粒子群算法不像其它 进化算法那样对个体使用进化算子而是将每个个体看作是在以维空间中的一个没有重量和 体积的粒子并在搜索空间中以一定的速度飞行。该飞行速度由个体的飞行经验和群体的飞 行经验进行动态调整。而且粒子群算法没有遗传算怯的交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 操作而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆与遗传算 法比较，粒子群算法的信息共享机制是很不同的在遗传算法中，染色体( c h r o m o s o m e s ) 互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动。而在粒子群算法中。只 有将全局最优和个体最优的信息给其它的粒子，这是单向的信息流动。整个搜索更新过程是 跟随当前最优解的过程。与遗传算法比较，在大多数情况下。所有的粒子可能更快地收敛于 最优解。 在p s o 算法中，粒子群体在搜索空间中进行飞行搜索，每个粒子表示优化问题的一个 候选解，每个粒子的位置受它的局部最优位置和全局最优位置的影响对一个y 维问题，设 x j = ( 工，t 2 ，x 。) 为第j 个粒子的当前位置； = ( v l ，v 2 ，) 为第f 个粒子的当前飞行速度 只= ( p m p 2 ，p 。) 5 , j ；g i 个粒子所经历过的具有最好适应值的位置，称为个体最优 位置。对于最小化问题，目标函数值越小，对应的适应值越好 为了讨论方便，设，( x ) 为最小化目标函数，则第i 个粒子的当前最优位置由下式确定： 聊驴船圳 ；酊( 置( f + 1 ) ) j r ( p ( ，” ；酊( 置( f 十1 ) ) ，则 返回步骤2 。 p s o 算法的流程图如图2 - 1 所示： 图2 1 基本p s o 算法流程 2 3 粒子群算法的特点及应用 2 3 1 粒子群算法的特点l 刀 1 基本p s o 算法最初是处理连续优化问题的； 2 ) 类似于遗传算法，p s o 也是多点搜索； 3 ) 式( 2 - 3 ) 的第一项对应多样化( d i v e r s i f i c a t i o n ) 的特点，第二项、第三项对应于搜 索过程的集中化( i n t e n s i f i c a t i o n ) 特点，因此这个方法可以在多样化和集中化之间 建立均衡。 2 3 2 粒子群算法的应用 粒子群算法的优势在于算法的简洁性、易于实现，没有很多参数需要调整，而且不需要 梯度信息，是1 线性连续优化问题、组合优化问题和混合整数非线性优化问题的有效优化工 具。目前已经广泛应用r 函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用 s 南京师范人学顾 ：学位论文第二章基奉粒了群算法的原理成应用 领域。还可以将粒子群算法用于解决多目标优化问题、最小最大化问题、整数规划阿题和定 位等全局极值问题。一般来说，粒子群算法比较有潜力的应用包括系统设计、多目标优化、 分类、模式识别、调度，信号处理、决策、机器人应用等 2 4 粒子群算法存在的问题 粒子群优化算法作为一种新兴的有潜力的演化算法，还存在一些问题【1 m ： 1 1p s o 算法在实际应用中被证明是有效的，但是对于算法的性能、收敛性、收敛速度、 参数选择及参数的鲁棒性等理论研究很少，且理论分析的内容和深度都很浅，很多 研究都仅局限在对算法的参数、状态及概念等方面，其理论和数学基础的研究还很 不够，理论研究大大滞后于p s o 算法在工程中的实际应用； 2 )粒子群算法存在着问题依赖的缺点，导致不同的问题需要不同的参数设置，应该能 够针对具体应用问题的特点设计出相应有效的算法； 3 ) 应该致力于增加群体中解的多样性研究，补充和扩展p s o 算法与其他算法或技术 的结合，解决p s o 算法容易陷入局部极小值的问题。 2 5 本章小结 粒子群算法作为一个较新的全局优化算法，具有很强的寻优能力。本章详细介绍了粒子 群算法的思想、算法流程，然后又简单介绍了粒子群算法的特点及应用以及粒子群算法存在 的问题，为后续章节奠定基础。 9 南京师范大学硕卜学位论文第三章聚类及d 均值聚类算法 第三章聚类及c 均值聚类算法 为了研究基于粒子群算法的d 均值聚类算法，本章首先对聚类的概念以及评价聚类的 标准傲一简单介绍，然后给出聚类分析的概念、分类及其数学模璎，然后又详细介绍了c ； 均值聚类和模糊d 均值聚类的理论基础、二者之间的关系以及它们各自的特点 3 1 聚类及判断聚类好坏的标准 聚类是按照一定的要求和规律对事物进行区分和分类的过程，在这一过程中没有任何关 于分类的先验知识，没有教师的指导，仅靠事物问的相似性( s i m i l a r i t y ) 作为类属划分的准 则，就是将一个对象的集合分割成几个类，每个类内的对象之闻是相似的，但与其它类的对 象之间是不相似的因此属于无监督分类( u n s u p e r v i s e dc l a s s i f i c a t i o n ) 的范畴i 。 判断聚类好坏的标准刚； 能够适用于大数据量； 能应付不同的数据类型； 能够发现不同类型的聚类； 使对专业知识的要求降到最低 能应付脏数据； 对于数据不同的顺序不敏感； 能应付很多类型的数据； 模型可解释，可使用 3 2 聚类分析及其数学模型 聚类分析是指用数学的方法研究和处理给定对象的分类，是多元统计分析的一种。也是 无监督模式识别的一个重要分支它把一个没有类别标记的样本集合按照某种准则划分成若 干个子集( 类) ( c l a s s ) ，使相似的样本尽可能地归为一类而不相似的样本尽量划分到不 同的类别中田。 传统的聚类分析是一种硬化分( h a r dp a r t i t i o n ) ，它把每个待识别的对象严格划分到某 个类别中，具有“非此即彼”的性质，如“对错”、“男女”，“有无”等，因此这种类别划分 1 0 1 2 3 4 5 6 7 8 南京师范大学硕匕学位论文 第三章聚类及c 均值聚炎算法 的界限是分明的，属丁：硬划分( h a r dp a r t i t i o n ) 。而实际上大多数对象并没有严格的属性 它们在性态和类属方面存在着中介性，具有“亦此亦彼”的性质，如“许多”、“很少”、“经 常”、“有时”等等，闪此适合进行软划分( f u z z yp a r t i t i o n ) 。模糊集理论的提出为这种软划 分提供了有力的分析工具人们开始j j 模糊的方法来处理聚类问题，并称之为模糊聚类分析。 由于模糊聚类得到了样本属于各个类别的不确定性程度。表达了样本类属的中介性，即建立 起了样本对于类别的不确定性描述，更能客观她反映现实世界，从而成为聚类分析研究的主 流刖 从数学角度来刻画聚类分析问题，可以得到如下的数学模型饼： 设x = 而，x 2 ， 是待分析的对象的全体( 称为论域) ，其中的每个对象( 称为样本) x i ( i = 1 , 2 ，哟常用有限个参数值来刻画，每个参数值刻画屯的一个特征。于是对象孔就 伴随着一个向量p ( 坼) = ( 砟l ，屯2 ，) ，其中u = l ，2 ，s ) 是在第，个特征上的赋 值，( 以) 称为屯的特征向量或模式矢量聚类分析就是分析论域z 中的样本所对应的模 式矢量间的分散情况，按照各样本间的亲疏关系把而，而，划分成多个不相交的子集 ( 类) ：五，x 2 ，丘，并要求满足下列条件： i x l u x 2 u u 以= x j 置n 一2 d l f ，s c f 置a i = 1 , 2 ，c 【z x i = 1 , 2 ，c 样本 ( 1 s k 疗) 对子集墨( 1 i s c ) 的隶属关系可用隶属函数表示为： 帅m = 嚣耋：主 其中，隶属函数必须满足条件te 毛，其中 ( 3 - 1 ) ( 孓2 ) c 口 l 邑= t ke o ，l ；地= l ，v k ；o 心 n , v i ( 3 - 3 ) ls - it l j 也就是说，要求每一个样本能且只能隶属于某一类。同时要求每个子集都是非空的。因 南京师范夫学顾 ：学位论文第三章聚类及。均值聚类算法 此，通常称这样的聚类分析为硬划分( h a r dp a r t i t i o n 或c r i s pp a r t i t i o n ) 。 在模糊划分( f u z z yp a r t i t i o n ) 中，样本集x 被划分成c 个模糊子集置， 2 ，z 。 而且样本的隶属函数从o 1 二值扩展到【o ，1 】区间，满足条件： lf 月 i = 似k o ，l 】；* = 1 ，v k ；o * n , v i ( 3 - 4 ) l- - ii - ij 3 3 聚类分析的分类 从实现方法上分，粗略说来，聚类分析方法可大致分为四种类型嘲：谱系聚类法、基于 等价关系的聚类方法，图论聚类法和基于目标函数的聚类方法等。对于前三种方法由于不能 适用于大量数据的情况，难以满足实时性要求较高的场合，因此在实际中应用并不广泛。实 际中受到酱遍欢迎的是第四种方法一基于目标函数的聚类方法。该方法把聚类分析归结成一 个带约束的1 # 线性规划问题，通过优化求解获得数据集的最优模糊划分和聚类。该方法设计 简单、解决问题的范围广，还可以转化为优化问题而借助经典数学的1 f 线性规划理论求解 并易于计算机实现。因此，随着计算机技术的应用和发展，基于目标函数的模糊聚类算法成 为新的研究热点 在基y - i ；l 标函数的聚类算法中，模糊d 均值( f c m ，f u z z yc - m e a n s ) 类型算法的理论 最为完善、应用最为广泛。模糊d 均值类型的算法最早是从硬聚类目标函数的优化中导出的。 为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函 数，从此类内误差平方和( w g s s ，w d h i n - g r o u p s s u m o f s q u a r e de r r o r ) j i 成为聚类目标 函数的普遍形式为极小化该目标函数而采取的p i k a r d 迭代优化方案就是著名的硬c - 均值 ( h c m ) 算法和i s o d a t a ( i t e r a t i v es e l f - o r g a n i z i n gd a t aa n a l y s i st e c h n i q u ea l g o r i t h m ) 算法模糊划分概念提出后，d u n n 首先把w g s s 函数，i 扩展到，2 一类内加权平均误差 和函数，后来b e z d e k 又引入了一个参数m ，把以推广到一个目标函数的无限族，并给 出了交替优化( a o 。a l t e m a t i v eo p t i m i z a t i o n ) 算法，印为人们所熟知的e c m 算法渊。从此 奠定了f c m 算法在模糊聚类中的地位。 南京师范人学硕j 学位论文 第三章聚类及c 均值聚类算法 3 4c - 均值聚类算法 3 4 1 数据集的c 划分 给定数据集x = x i ) x 2 ，x 。 c r 。为模式空间中疗个模式的一组有限观测样本集， 以= ( x “，以2 ，) 7 r 5 为观测样本扎的特征矢量或模式矢量，对应特征空间中的一个 点，为特征矢量的第_ ，维特征上的赋值。对给定样本集x 的聚类分析就是要产生x 的 c 划分阁。 由有关聚类分析的数学模型可知，数据集x 的c 划分得到的0 个子集x i ，五，k ， 若满足( 3 - 1 ) 的条件，则称之为x 的硬c 划分 如果用隶属函数m = 置( x k ) 表示样本以与子集工，( 1 s i 0 的隶属关系，则硬c 划 分中以为子集z 的特征函数，显然有心( 0 , 1 。这样工的硬c 划分也可以用隶属函数来 表示，即用0 个子集的特征函数值构成的矩阵u = 阻m 】。来表示。矩阵c ，中的第j 行是第f 个子集的特征函数，而第七列为样本以相对于0 个子集的隶属函数。于是x 的硬c 划分空 问为： 肘* = u e 足。卜t ，朋 喜儿= ，v 邶 否n 舰 v f ) c s s ， 由于模糊划分可以得到样本分属于各个类别的不确定性程度，建立了对于类别的不确定 描述，因此更能客观地反映现实世界。 以下分别给出硬d 均值( h c m ) 和模糊。均值( f c m ) 的原理及各自的特点 3 4 。2 硬c 均值聚类算法 在目标函数法中。目标函数是对每个c 的所有候选类的可取度的度量，最优的类就是使 目标函数达到局部最小值的类。研究得最多的目标函数是总体组内误差平方和( o v e r a l l w i t h i n - g r o u ps u mo f s q u a r e de r r o r s ) ，其定义为： 南京师范大学硕叶i 学位论文 第三章聚类及c 均值聚类算法 厶( u ，e ) = 圭妻。i l x k - e , u 2 t - l ，- l 式中u = 阻】m 。或m 归，占= ( q ，岛，) ，其中q 是类一，的中心，其定义为： 鲰靠 q = 生卜 心 女- l 显然p 。是类4 中所有点的平均值( 磋气划分) 或加权平均值( 模糊c 划分) ( 3 6 ) ( 3 - 7 ) 寻找使j wt , j 、的( u ，d 并不容易，这是因为村。的容量虽然有限但非常大最常见的 寻找逼近厶最小值的方法就是硬d 均值算法( h c m 算法) ，文献【2 4 】给出了硬d 均值算法 的详细步骤，这里不再给出 c 一均值算法的优点网闭： 。1 )d 均值算法思想简单，易于实现； 2 )c 一均值算法运行速度快，收敛速度快，内存消耗小，能有效地处理大数据集 是目前最常用的聚类算法之一 但是，d 均值算法也有不少缺点： 1 ) 须预先指定类别数。在类别数未知的情况下，只能假设类别数c 是逐步增加的，显 然准则函数j 0 是随c 的增加而单调减少的，如图3 - 1 所示。如果作一条j w c 曲线， 其拐点对应的类别数就比较接近于最优的类别数。如图中4 点所对应的c = 3 就是 较合适的聚类类射数但是并非所有的情况都能找到这样的转折点4 。当无明显的 转折点时，这种选择最佳分类数的方法将失效伫7 】 2 ) 依赖于初始条件，可能导致算法收敛于次优解对于随机的初始值选取可能会导致 不同的聚类结果，甚至存在无解的情况； 3 ) 产生类的大小相差不会很大，每个数据点的影响一样，没有考虑噪音数据的影响， 1 4 南京师范大学硕 ：学位论文 第三章聚类及c 均值聚类算法 对于脏数据很敏绉： 4 )该算法是基于梯度下降的笄法，因此不可避免地常常陷入局部晟优。 j 123456 789 1 0 图3 - 1 ：确定类别数的一种实验方法 3 4 3 模糊c 均值聚类算法 模糊聚类分析的思想首先是由b e l l m a n 和z a d e h 等人于1 9 6 6 年提出来的。为了优化聚 类分析的目标函数，1 9 8 1 年，b e z d e k 提出了现在相当流行和广泛使用的模糊c 均值( f c m 。 f u z z y c - m e a n s ) 聚类算法该算法是从硬d 均值( h c m ) 聚类算法发展而来的。模糊聚类 算法是一种被广泛应用的聚类算法自从八十年代以来，由于聚类目标函数法具有设计简单， 解决问题范围广，并且最终可以归结为优化问题等优点，所以对模糊聚类算法的研究和改进 一直被许多研究人员所青睐 在这一章首先简单介绍经典模糊d 均值聚类算法的原理，然后在第五章中，提出了一种 基于改进粒子群算法的模糊c 一均值聚类算法( p s o f c m ) 模糊d 均值算法的目标在于找到u = 纨】和e = l ，e 2 ，p 。) ( e ，r 9 ) ，使 得以( u ，d ：窆窆o 。) m k q 1 2 最小，其中m ( 1 ，o o ) 是加权指数。 下面的定理3 1 描述了这个最小化问题的必要条件伫町： ( 3 - 8 ) 南京师范大学硕 ：学位论文第三章聚类及c 均值聚类算法 定理3 1 ：令石= x i , x 2 ，x 。) ( x 。r e ) 为一给定数据集，设定c 2 , 3 ，n - l 和 l f i e ( 1 ，。o ) ，假设对所有1 k n 和1 s i c ：f f l l x , 一e ，1 1 , e o ，则仅当 和 止= 窆一fu x 。, 一- e , l f i 厂 ，1 f c ，l k 一 ( ) 。瓢 岛= = - 一，1 s i s c ( ) 。 时，u = 【地】和e = ( e l ，p 2 ，e c ) 才是厶( u ，d 的局部最小值 ( 3 9 ) ( 3 - 1 0 ) 模糊d 均值算法是建立在上述必要条件( 3 - 9 ) 和( 3 - 1 0 ) 基础上的。文献【2 4 】给出了定 理3 1 的证明过程以及模糊g 均值算法的详细步骤，这里不再给出。 对于加权指数搬 1 ，o d ) 对f c m 算法性能的影响，有如下定理田： 定理3 2 ：对于m “1 , o o ) 对f c m 算法，存在以下情况： 当m = 1 时，f c m 算法变成h c m 算法； 当辨_ l + 时，f c m 算法以概率1 退化成h c m 算法 当m 一- 旧时。f c m 算法失去划分特性，有u = 陋n 】= 【1 c 】。 f c m 算法是目前比较流行的一种模糊聚类算法，不仅在许多领域获得了成功的应用，而 且以该算法为基础。人们又提出了基于其它原型的模糊聚类算法，形成了一大批f c m 类型 的聚类算法，如模糊c 线( f c l ) 、模糊c 面( f c p ) 、模糊c 壳( f c s ) 等聚类算法，分 别实现了对呈线状、超平面状以及“薄壳”状结构模式子集( 或聚类) 的检测。但是，f c m 算法还存在如下弱点翩： 1 6 南京师范大学预 学位论文第三章聚类及c 均值聚类算法 1 ) f c m 聚类算法是一种划分方法，不管数据集在特征空间中是否存在1 3 然结构，给定 一个分类数c ，就能得到数据集的一个c 划分。即算法存在一个不合理的假设，待 分析的数据集是可聚的；因此，要避免不适当或无意义地使用f c m 聚类算法。必 须检验给定数据集有没有聚类趋势； 2 ) f c m 聚类算法中，聚类类别数c 要求事先给定，这一要求也限制了f c m 聚类算法 的实际应用； 3 )f c m 聚类算法对初始矩阵敏感，只有在初值确定的情况下。聚类结果才是唯一确定 的。算法在很大程度上依赖于初始隶属度矩阵或初始聚类中心的选择，如果初始分 类严重地偏离全局最优分类时，f c m 算法很可能陷入局部极小值，得到一个局部最 优解。 4 )f c m 聚类算法是一种局部搜索寻优技术，容易追寻目标函数而陷入局部极小 为解决f c m 聚类算法的初值敏感和局部极小问题，一些作者提出了不同的解决办法， 一类方法集中在对初始矩阵的预处理，这类方法中有的对初值进行基于形态的预处理，有 的利用样本的统计信息，转变为特征集，再进行f c m 运算。另一类方法以多个样本比较寻 优，例如有的利用交叉的并行算法，在一群随机样本中，最优解的生存几率要大有的借用 模拟退火中系统温度的概念，对样本中心震荡后，和原来比较寻优，再进行迭代1 2 8 1 。本文则 将粒子群算法引入到f c m 聚类算法中，利用粒子群算法的全局寻优能力来解决f c m 聚类算 法的初值敏感和局部极小问题。 3 5 本章小结 本章首先简单介绍了聚类及判断聚类好坏的标准、聚类分析的概念、分类及其数学模型， 接着详细介绍了h c m 聚类算法和f c m 聚类算法的原理以及二者之间的关系，并分析它们各 自的特点、存在的问题及解决办法。 1 7 南京师范人学硕f 二学位论文第四章幕十改进粒了：群算法的。均值算法 第四章基于改进粒子群算法的c - 均值算法 d 均值聚类算法是一种局部搜索算法，对初始值很敏感，如果初始值选择不当，很可 能导致算法收敛到局部极值点上。而粒子群算法在解空间中不是局限于一点，而是同时处理 一群点，可以避免陷入局部解。因此本章将粒子群算法引入到d 均值聚类算法中，可以增加 。均值聚类算法隶属度矩阵初始化的多样性，减慢局部搜索，促进在全局范围内的寻优搜索， 可以有效克服d 均值聚类算法过分依赖初始值和容易陷入局部极小值的缺点 为了较好的实现基于粒子群算法的d 均值聚类算法，本章首先分析了已有粒子群算法 的收敛性和参数选择的关系，在此基础上，提出了一种加速系数识、九的取值与惯性权重w 相结合而且惯性权重w 沿折线先增后减的改进粒子群算法，可以从理论上保证粒子群算法 收敛。然后将这一改进的粒子群算法与d 均值聚类算法相结合，提出了基于改进的粒子群算 法的d 均值聚类算法，并通过计算机仿真实验表明该算法比单一使用d 均值聚类算法的聚 类效果更好，验证了该算法的有效性 4 1 粒子群算法的参数选择及改进 为了改善基本粒子群算法的收敛性能，y s h i 和r c e b e r h a r t 在1 9 9 8 年的i e e e 国际 进化计算学术会议上发表了题为“am o d i f i e dp a r t i c l es w a r mo p t i m i z e r ”的论文，首次在 速度进化方程中引入惯性权重即 ( f + 1 ) = n 0 ( f ) + c 1 1 ( p 口o ) 一而o ) ) + c 2 ，2 ( p 掣( f ) 一( f ) ) 毛( ，+ 1 ) = 勃( f ) + 吃( f + 1 ) ( 4 1 ) ( 4 2 ) 其中0 wsl 称为惯性权重。因此基本粒子群算法是惯性权重w = 1 的特殊情况。惯性 权重w 使得粒子保持运动惯性，具有扩展空间的趋势。有能力探索新的区域，用来平衡全局 搜索能力和局部搜索能力。 p s o 算法中需要调节的参数并不多，下面列出了这些参数以及经验设置： 1 ) 粒子数：一般取2 0 - 4 0 。其实对于多数问题1 0 个粒子已经足够可以取得好的结果， 不过对于比较难的问题或者特定类别的问题，粒子数可以取到1 0 0 或2 0 0 ； 1 8 南京师范人学顾j j 学位论文 第p q 章甚于改j 2 粒了群算法的c 均值算法 2 ) 粒子的k 度：由优化问题决定就是问题解的长度； 3 )粒子的范围：由优化问题决定，每一维可以设定不同的范嗣； 4 ) 惯性权重：较大的w 具有较好的全局搜索能力，而较小的w 则具有较强的局部搜索 能力，一般0 w s l 。 5 ) v 。：最大速度，决定粒子在一次循环中的最大移动距离，每一维的大小可以不同 通常设定为粒子的范同宽度； 6 ) 加速系数：c 1 和乞一般取c