（计算机应用技术专业论文）模糊聚类算法应用研究.pdf

模糊聚类算法应用研究浙江大学硕士学位论文 摘要 聚类是数据挖掘的重要分支之一，引入模糊理论的模糊聚类分析为现实数 据提供了模糊处理能力，在许多领域被广泛应用。在本文中，总结了模糊聚类 的原则和通用的方法，讨论了常用的模糊聚类算法，讨论了这些算法的优缺点、 存在的问题以及前景展望。 模糊c 一均值聚类算法是目前广泛使用的模糊聚类算法。但它也存在一些缺 点，例如模糊c 一均值( f c m ) 聚类算法受初始化影响较大，在迭代时容易陷入 局部极小。本文从引入隶属度函数、引入消息熵和类中心的约束出发，研究了 模糊c 一均值的改进方法。 在此基础上，提出了一种改进的模糊c 一均值聚类算法。其基本思想是：通 过对数据对象的模糊隶属度增加个加权值，以及在算法中引入模糊聚类有效 性函数对聚类数目c 进行优选。为了证明改进f c m 算法的实用性，我们将该算 法应用于两个领域：网络入侵检测和w e b 日志挖掘。 入侵检测是网络安全的第二道防线。在本文中，分析了入侵检测技术的要 点，提出了一种基于改进f c m 算法的网络入侵检测方法。该方法的优点是不需 要标示或训练数据集。文中使用k d d 9 9 数据集作为实验数据，实验结果显示该 方法检测未知入侵检测是有效的，而且它提高了入侵检测系统的检测率和误警 率。 最后，我们使用改进的模糊聚类算法来分析w e b 日志数据，以实现w e b 用 户聚类，即根据用户的浏览行为，发现相似的用户组；以及w e b 页面聚类，即 根据w e b 页面被用户访问的情况，发现相关页面组。实验证明，采用该改进的 模糊聚类算法对w e b 日志挖掘效果良好。 关键字：模糊c 一均值( f c m ) 聚类算法，模糊聚类，入侵检测，w e b 目志挖掘 用户聚类，页面聚类 模糊聚类算法应用研究 浙江大学硕十学位论文 a b s t r a c t c l u s t e r i n gi so n eo ft h ei m p o r t a n tt a s k si nt h ef i e l do fd a t am i n i n g f u z z yc l u s t e r i n ga n a l y s i st h a ti n t r o d u c e st h et h e o r yo ff u z z ys e t s ， p r o v i d e st h ec a p a b i l i t yt h a tb eu s e dt od e a lw i t hr e a ld a t a a n di th a s b e e nw i d e l yu s e di nm a n yf i e l d s i nt h i st h e s i s ，p r i n c i p l e sa n dg e n e r a l m e t h o d so ff u z z yc l u s t e r i n ga r es u m m a r i z e d ，a n da n a l y z e dt h ec o r r e l a t i v e t e c h n i q u e sa n dp r e s e n tr e s e a r c ho fc l u s t e r i n ga l g o r i t h m s w ed i s c u s s e d t y p i c a if u z z yc l u s t e r i n ga l g o r i t h m s t h ea d v e n t a g e sa n dd i s a d v a n t a g e s o ft h e s ea l g o r i t h m sa n dt h ep r o b l e m s e x i s t i n gi nt h e s ea l g o r i t h m sa n d t h ep r o s p e c t so ft h ef u z z yc l u s t e r i n ga l g o r i t h ma r ed i s c u s s e d f u z z yc - m e a n s ( f c m ) c l u s t e r i n ga l g o r i t h mi so n eo ft h ew i d e l ya p p l i e d f u z z ya l g o r i t h m sa tp r e s e n t b u tf c ma l g o r i t h mh a ss o m es h o r t c o m i n g s t h ef u z z yc - m e a n s ( f c m ) c l u s t e r i n ga l g o r i t h mi ss e n s i t i v et ot h e s i t u a t i o no fi n i t i a l i z a t i o na n de a s yt of a l li n t ot h el o c a lm i n i m u mw h e n i t e r a t i n g i no r d e rt os t u d yf c ma l g o r i t h m ss y s t e m a t i c a l l ya n dd e e p l y ， t h e ya r er e v i e w e di nt h i sp a p e rb a s e do nc - m e a n sa l g o r i t h m ，f r o mm e t r i c s ， e n t r o p y ，a n dc o n s t r a i n t so nm e m b e r s h i pf u n c t i o no rc l u s t e rc e n t e r s i no r d e rt oo v e r c o m es h o r t c o m i n go ff c ma l g o r i t h m ，i nt h i sp a p e ra i m p r o v e df u z z yc - m e a n sc l u s t e r i n ga l g o r i t h mi sp u tf o r w a r d t h eb a s i c i d e ao ft h ea l g o r i t h mi sm o d i f i e ds u b j e c t i o nv a l u eb ya d d i n gw e i g h t e d v a l u ea n dt h eo p t i m a lc h o i c ef o rp a r a m e t e ro fn u m b e ro fc l u s t e r scb a s e d o nc l u s t e rv a l i d i t yf u n c t i o n t op r o v et h ea v a i l a b i l i t yo ft h i si m p r o v e df c ma l g o r i t h m ，w eu s et h e a l g o r i t h mi nt w of i e l d s ：n e t w o r ki n t r u s i o nd e t e c t i o na n dw e bl o gm i n i n g t h ei n t r u s i o nd e t e c t i o ni st h es e c o n df l o o rd e f e n c e1 i n e o ft h e n e t w o r ks e c u r i t y i nt h i sp a p e r ，w ea n a l y z et h ec h a r a c t e r i s t i co ft h e i n t r u s i o nd e t e c t i o nt e c h n i q u e ，a n db r i n gf o r w a r da p p r o a c ho fn e t w o r k 2 模糊聚类算法应用研究 浙江火学硕士学位论文 i n t r u s i o nd e t e c t i o nb a s e do nt h ei m p r o v e df u z z yc - m e a n sc l u s t e r i n g t h e b e n e f i to ft h i sa p p r o a c hi st h a ti tn e e dn o tl a b e l e dt r a i n i n gd a t as e t s u s i n gt h ed a t as e t so fk d d 9 9 ，t h ee x p e r i m e n tr e s u l ts h o w st h a tt h i s a p p r o a c h c a nd e t e c tu n k n o w ni n t r u s i o n s e f f i c i e n t l y ，a n d i n c r e a s e d e t e c t i o nr a t eo ft h ec l u s t e r i n gd e t e c t i o na n dd e c r e a s et h ef a l s ea l a r m s r a t e a tl a s t ，w ea n a l y z ew e bl o gd a t ab yu s i n gi m p r o v e df u z z yc l u s t e r i n g a l g o r i t h mt or e a l i z ew e bu s e rc l u s t e r i n gt h a ti st of i n dt h es i m i l a ru s e r g r o u p sa c c o r d i n gt ob r o w s i n gb e h a v i o r sa n dw e bp a g e sc l u s t e r i n gt h a ti s t of i n dr e l a t ep a g eg r o u p sa c c o r d i n gt ot h ew e bp a g e sv i s i t e db yt h eu s e r t h er e s u l t so fe x p e r i m e n ta r eg i v e nt op r o v et h ef e a s i b i l i t yo fu s i n g i m p r o v e df u z z yc l u s t e ra l g o r i t h mi nw e bl o gd a t am i n i n g k e yw o r d s ：f u z z yc - m e a n s ( f c m ) a l g o r i t h m ，f u z z yc l u s t e r ，i n t r u s i o n d e t e c t i o n ，w e bl o gm i n i n g ，u s e rc l u s t e r i n g ，p a g ec l u s t e r i n g 3 模糊聚类算法廊片j 研究 浙江人学硕士学位论文 1 1 研究背景 第一章绪论 “人以群分，物以类聚”，聚类是一个古老的问题，它伴随着人类社会的产 生和发展而不断深化，人类要认识世界必须区别不同的事物并认识事物问的相 似性。 将物理或抽象对象的集合分组成为由类似对象组成的多个类的过程被称为 聚类( c l u s t e r i n g ) 。1 。由聚类生成的簇是一组数据对象的集合，这些对象与 同一簇的对象彼此相似，与其它簇中的对象彼此相异。在许多应用中，可以将 一个簇中的数据对象作为一个整体来对待。 聚类按照一定的要求和规律对事物进行区分和分类，在这一过程中没有任 何关于分类的先验知识，没有教师指导，仅靠事物问的相似性作为类属划分的 准则，因此属于无监督分类的范畴。聚类分析则是指用数学的方法研究和处理 给定对象的分类。作为一种无导师的学习方法，聚类分析能够从研究对象的特 征数据中发掘出信息和规则，因而是一种强有力的信息处理方法。它在图象分 割、模式识别、计算机视觉、数据挖掘、特征提取和信号压缩中都有着广泛的 应用。 1 2 聚类与模糊理论的结合 聚类的方法可以分为基于划分的方法、基于分层的方法、基于密度的方法和 基于网格的方法。其中，基于划分的聚类算法在模式识别里是最常用的聚类算法 类型，基于划分的聚类方法有时也叫做基于目标函数的聚类算法。 传统的聚类方法把每个待处理的数据对象严格地归属于某个类。在这类方法 中，隶属度不是1 就是0 ，而现实中大多数的对象并没有严格的属性，这种硬 划分并不能真正地反应对象和类的实际关系，因此，人们就提出了要对待处理的 对象进行软划分，z e d e h 提出的模糊集理论为软划分提供了有力的分析工具，人 们开始用模糊的方法来处理聚类问题。 模糊聚类算法应用研究 浙江人学硕士学位论文 模糊聚类是将模糊集的概念应用到传统聚类分析中，让数据集的对象在分 组中的隶属用隶属函数来确定，也就是说，对象在各分组中的隶属度为连续区 间 0 ，1 之间的某个值，以不同程度隶属于多个簇，而非确定性聚类中的0 或 1 的二值逻辑。模糊聚类的优点在于能适应那些分离性不是很好的数据和类， 这允许了数据性质的模糊性为数据结构的描述提供了详细的信息。由于模糊 聚类得到了样本属于各个类别的不确定性程度，表达了样本类属的模糊性，即 建立起样本对于类别的不确定性的描述，更能客观地反映现实世界，从而成为 聚类分析研究的主流之一。 1 3 本文研究的内容 本文的主要工作和贡献包括以下几个方面： ( 1 ) 分析了当前主要模糊聚类算法的研究现状，对目标函数演化、实现途径 和有效性三个方面进行了研究； ( 2 ) 仔细研究了f c m 型模糊聚类算法，讨论了算法改进的两种思路，即引入 隶属度权重指数和在目标函数中引入信息熵； ( 3 ) 提出了一种改进的f c m 算法。针对f c m 算法的缺点，在两个方面进行了 改进：一是对数据对象的模糊隶属度增加一个加权值，来减少孤立点对 聚类中心的影响；二是通过在算法中结合模糊聚类有效性函数f p ( u ：c ) ， 对聚类数目c 进行优选； ( 4 ) 将改进的f c m 算法应用于网络入侵检测。通过此模糊聚类算法，对网络 入侵数据进行分析，实验表明，改进的f c m 算法对提高入侵检测的检测 率、误警率等都有很好的效果，具有很高的应用价值； ( 5 ) 将改进的f c m 算法应用于w e b 日志挖掘。通过此模糊聚类算法，对w e b 同志数据进行分析，实现用户聚类和页面聚类。 1 4 本文的结构 本文各章节的安排如下： 第一章介绍了本文的研究背景、聚类和模糊理论的结合以及本文研究内容 和结构。 7 模糊聚类算法麻片 研究浙门i 大学硕上学位论文 模糊聚类是将模糊集的概念应用到传统聚类分析中，让数据集的对象存分 组中的隶属用隶属函数来确定，也就是说，对象在各分组中的隶属度为连续区 间 0 ，1 之间的某个值，班不同程度隶属于多个簇，而非确定性聚类中的0 或 1 的二值逻辑。模糊聚类的优点在于能适应那些分离性不是很好的数据和类， 这允许了数据性质的模糊性，为数据结构的描述提供了详细的信息。由于模糊 集类得到了样奉属于备个类别的不确定性程度，表达了样本类属的模糊性，即 建立起样本对于类别的不确定性的描述，更能客观地反映现实世界，从而成为 聚类分析研究的土流之。 1 3 本文研究的内容 本文的主要工作和贡献包括以下几个方面： ( 1 ) 分析了当前主要模糊聚类算法的研究现状，对目标函数演化、实现途径 和有效性三个方衙进行了研究； ( 2 ) 仔细研究了f l s i 型模糊聚类算法，讨论了算法改进的两种思路，即引入 隶属度权重指数和存目标函数中引入信息熵； ( 3 ) 提出了种改进的f c m 算法。针对f c m 算法的缺点，在两个方面进行了 改进：一是对数据对象的模糊隶属度增j j u 一个加权值，米减少孤立点对 聚类中心的影响；堤通过在算法中结合模糊聚类有效性函数f p ( u ：c ) ， 对聚类数目c 进行优选； ( 4 ) 将改进的f c m 算法应用于网络入侵检测。通过此模糊聚类算= ；土，对网络 入侵数据进行分析，实验表明，改进的f c m 算法对提高入侵检测的检测 率、误警率等都有很好的效果，具有很高的应用价值； ( 5 ) 将改进的f c m 算法应用于w e b 日志挖掘。通过此模糊聚类算法，对w e b 日忐数据进行分析，实现用户聚类和页面聚类。 1 4 本文的结构 本文各章节的安排如下： 第一章介绍了本文的研究背景、聚类和模糊理论的结台以及本文研究内容 第一章介绍了本文的研究背景、聚类和模糊理论的结合以及本文研究内容 和结构。 7 模糊聚类算法应崩研究 浙江大学硕士学位论文 第二章分类介绍了一些常用的聚类算法，详细叙述了模糊c 均值聚类算法、 模糊聚类算法的研究现状、模糊聚类算法的实现途径和有效性研究。 第三章讨论了f c m 类型算法的改进方法、模糊聚类算法有效性判别的函数 以及提出了一种新的改进的f c m 算法。 第四章将上一章中提出的改进的f c m 算法应用于网络入侵检测，并对k d d c u p 9 9 提供的入侵检测数据集，进行了模糊聚类分析，得到了详细的分析对比 数据。 第五章将改进f c m 算法应用于w e b 日志挖掘，实现了用户聚类和页面聚类。 第六章对本文的研究工作和成果进行了总结，并探讨了进一步的研究内容 和方向。 模糊聚类算法应用研究 浙江大学硕士学位论文 第二章聚类算法研究 2 1 常用聚类算法分类 目前存在大量的聚类算法，算法的选择取决于数据的类型、聚类的目的和 应用。大体上，主要的聚类算法可以划分为如下几类： 2 1 1 划分的方法 给定n 个对象，一个划分的方法( p a r t i t i o n i n gm e t h o d ) 构建数据的k 个 划分，每个划分表示一个聚簇，而且k n 。也就是说，它将数据划分为k 个分 组，同时满足如下的要求：( a ) 每个分组至少包含一个对象；( b ) 每个对象必 须属于且只属于一个分组。 给定要构建的划分数目k ，划分方法首先创建一个初始划分。然后采用一 个迭代的重定位技术，尝试通过对象在划分问的移动来改进划分。一个好的划 分的一般准则是；在同一个类中的对象之间尽可能的“接近”或相关，雨不同 类中的对象之间尽可能的“远离”或不同。 为了达到全局最优，基于划分的方法会要求穷举所有可能的划分。实际上， 绝大多数应用都采用了一下两个启发式方法： ( 1 ) k 一均值( k - m e a n s ) 算法，在该算法中，每个簇用该簇中对象的平均 值来表示。首先，随机地选择k 个对象，每个对象初始地代表了一个簇的平均 值或中心。对剩余的每个对象，根据其与各个簇中心的距离将它赋给最近的簇。 然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。通常， 采用平方误差准则，其定义为：e z zi p - 研斤。其中，e 是数据集中所有对 象与相应簇中心的均方差之和，p 为代表对象空间中的一个点，m 为簇e 的均 值( p 和m ；均是多维的) 。 ( 2 ) k 一中心点( k m e d o i d s ) 算法，在该算法中，每个簇用接近聚类中一t l , 的一个对象来表示。它首先为每个簇随意选择一个代表对象：剩余的对象根据 9 模糊聚类算法应用研究浙江人学硕士学位论文 其与代表对象的距离分配给最近的一个簇，然后反复地用非代表对象来代替代 表对象，以改进聚类的质量。k - m e d o i d s 算法改善了k - m e a n s 算法对孤立点是 敏感这一缺点。 2 1 2 层次的方法 层次的方法( h i e r a r c h i c a lm e t h o d ) 对给定的数据对象集合进行层次的分 解。它通过将数据对象组织为若干组并形成一个相应的树来进行聚类的。根据 层次分解是自顶向下还是自底向上形成，层次的聚类方法进一步分为凝聚的和 分裂的层次聚类。 ( 1 ) 凝聚的( a g g l o m e r a t i v e ) 层次聚类：这种自底向上的策略首先将每个 对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一 个簇中，或者某个终结条件被满足。 ( 2 ) 分裂的( d i v i s i v e ) 层次聚类：这种自项向下的策略与聚合的层次聚 类相反，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直 到每个对象自成一簇，或者达到了某个终结条件，例如达到了某个希望的簇数 目，或者两个最近的簇之间的距离超过了某个阀值。 层次的方法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能被撤 销。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会比 较小。目前的研究都强调将自底向上层次聚类与循环再定位方法相结合。有以下 两种方法可以改进层次聚类的结果：( a ) 在每层划分中，仔细分析对象间的“联 接”，例虫u c u r e 和c h a m e l e o n 中的做法。( b ) 综合层次凝聚和迭代的重定位方法。 首先用自底向上的底层算法，然后用迭代的重定位来改进结果，例f l d 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 g i s i n gh i e r a r c h i e s ) 是一个综合的层次聚类方法。它引入了两个概念：聚类特征和聚类特征树( c f 树) ，它们用于概括聚类描述。这些结构辅助聚类方法在大型数据库中取得高的 速度和可伸缩性。b i r c h 方法对增量或动态聚类也非常有效。 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 u r e 采用了一种新颖的层次聚类法，该算 模糊聚类算法应用研究浙江大学硕士学位论文 法选择基于质心和基于代表对象方法之间的中间策略。它不用单个质心或对象来 代表一个簇，而是选择数据空间中固定数目的具有代表性的点。 c h a m e l e o n 是一个在层次聚类中采用动态模型的聚类算法。在它的聚类过 程中，如果两个簇间的互连性和近似度与簇内部对象间的互连性和近似度高度 相关，则合并这两个簇。基于动态模型的合并过程有利于自然的和同构的聚类 的发现，而且只要定义了相似度函数就可应用于所有类型的数据。 2 1 3 基于密度的方法 为了发现任意形状的聚类结果，提出了基于密度的聚类方法 ( d e n s i t y b a s e d m e t h o d ) 。这类方法将簇看作是数据空间中被低密度区域分割 开的高密对象区域。它的主要思想是：只要临近区域的密度( 对象或数据点的 数目) 超过某个闽值，就继续聚类。也就是说，对给定类中的每个数据点，在 一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤 “噪声”孤立点数据，发现任意形状的簇。 d b s c a n ( d e n s i t y b 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 ) 是个基于密度的聚类算法。该算法将具有足够高密度的区域划分为簇，并可以 在带有“噪声”的空间数据集中发现任意形状的聚类。它定义簇为密度相连点 的最大集合。d b s c a n 的缺点是仍然将选择能产生可接受的聚类结果的参数值的 责任留给了用户。 o p t i c s ( o r d e r i n gp o i n t st oi d e n t i f yt h ec l u s t e r i n gs t r u c t u r e ) 没 有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个簇次序 ( c l u s t e ro r d e r i n g ) 。这个次序代表了数据的基于密度的聚类结构。它包含的 信息，等同于从一个宽广的参数设置范围所获得的基于密度的聚类。 d e n c l i u e ( d e n s i t y b a s e dc l u s t e r i n g ) 是一个基于一组密度分布函数的 聚类算法。该算法主要基于下面的想法：( i ) 每个数据点的影响可以用一个数学 函数来形式化地模拟，它描述了一个数据点在邻域内的影响，被称为影响函数 ( i n f l u e n c ef u n c t i o n ) ；( i i ) 数据空间的整体密度可以被模型化为所有数据点 的影响函数的总和；( i i i ) 然后聚类可以通过确定密度吸引点( d e n s i t y a t t r a c t o r ) 来得到，这里的密度吸引点是全局密度函数的局部最大。 模糊聚类算法应用研究浙江大学硕十学位论文 2 1 4 基于网格的方法 基于网格的方法( g r i d b a s e dm e t h o d ) 把对象空问量化为有限数目的单元， 形成了一个网格结构。所有的聚类操作都在这个网格结构( 即量化的空间) 上 进行。这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象 的数目，只与量化空间中每一维的单元数目有关。 s t i n g ( s t a t i s t i c a li n f o r m a t i o ng r i d ) 是一种基于网格的多分辨率聚类 技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级 别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低 一层的单元。关于每个网格单元属性的统计信息( 例如平均值、最大值和最小值) 被预先计算和存储。统计参数的使用可以按照以下自顶向下的基于网格的方法。 w a v e c l u s t e r 是一种多分辨率的聚类算法，它首先通过在数据空间上强加 一个多维网格结构来汇总数据，然后采用小波变换来变换原特征空问，在变换 后的空间中找到密集区域。 2 1 5 基于模型的方法 基于模型的方法( m o d e l b a s e dm e t h o d ) 为每个簇假定了一个模型，寻找 数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空 间分布的密度函数来定位聚类。它也基于标准的统计数字自动决定聚类的数目， 考虑“噪声”数据或孤立点，从而产生健壮的聚类方法。基于模型的方法主要 有两类：统计学方法和神经网络方法。 概念聚类是机器学习中的一种聚类方法，给出一组未标记的对象，它产生对 象的一个分类模式。概念聚类的绝大数多数方法采用了统计学的途径，在决定概 念或聚类时使用概率度量。概率描述用于描述导出的概念。c o b w e b 是一种流行 的简单增量概念聚类算法，它的输入对象用分类属性一值对来描述。c o b w e b 以一 个分类树的形式创建层次聚类。c l a s s i t 是c o b w e b 的扩展，用以处理连续性数 据的增量聚类。 神经网络方法将每个簇描述为一个标本( e x e m p l a r ) 。标本作为聚类的原型， 不一定对应一个特定的数据实例或对象。根据某些距离度量，新的对象可以被 分配给标本与其最相似的簇。被分配给一个簇的对象的属性可以根据该簇的标 1 2 模糊聚类算法应用研究浙江大学硕士学位论文 本的属性来预测。在神经网络中，竞争学习( c o m p e t i t i v el e a r n i n g ) 方法和 自组织特征映射( s e l f o r g a n i z i n gf e a t u r em a p ，s o m ) 方法都是比较常用的。 2 。2 模糊聚类算法 传统的聚类分析是一种硬划分，它把每个待辨识的对象严格地划分到某个类 中，具有非此即彼的性质，因此这种分类的类别界限是分明的。而实际上大多数 对象并没有严格的属性，它们在形态和类属方面存在着中介性，适合进行软划分。 z a d e h 提出的模糊集理论为这种软划分提供了有力的分析工具，人们开始用模糊 的方法来处理聚类问题，并称之为模糊聚类分析。由于模糊聚类得到了样本属于 各个类别的不确定性程度，表达了样本类属的中介性，即建立起了样本对于类别 的不确定性的描述，能更客观地反映现实世界，从而成为聚类分析研究的主流。 模糊划分的概念最早由r u s p i n i 提出，利用这一概念人们提出了多种聚类 方法，比较典型的有：基于相似性关系和模糊关系的方法( 包括聚合法和分裂 法) ，基于模糊等价关系的传递闭包方法、基于模糊图论最大树方法，以及基于 数据集的凸分解、动态规划和难以辨识关系等方法。然而由于上述方法不适用 于大数据量情况，难以满足实时性要求高的场合，因此其实际的应用不够广泛， 故在该方面的研究也就逐步减少了。实际中受到普遍欢迎的是基于目标函数的 方法，该方法设计简单、解决问题的范围广，最终还可以转化为优化问题而借 助经典数学的非线性规划理论求解，并易于计算机实现。因此，随着计算机的 应用和发展，该类方法成为聚类研究的热点。 为了优化聚类分析的目标函数，人们提出了现在相当流行和应用广泛的模 糊c 均值( f c m ，f u z z yc m e a n s ) 聚类算法。该算法是从硬c 均值( h c m ，h a r d c m e a n s ) 聚类算法发展而来的。 2 2 1h c m 算法 初始化：给定聚类类别数c ，2 c n ，n 是数据个数，设定迭代停止阈值 ，初始化聚类原型模式p c ”，设置迭代计数器b = 0 ； 步骤一：用露= 1当露= 皿 带) ( 3 1 ) 计算或更新划分矩阵【，忙； l s r 峁 模糊聚类算法应用研究浙江人学硕士学位论文 硭= 0 其他 罗雕“h & 步骤二：用只“) ；笪_ 一，i = l ，2 ，c 3 - 2 )更新聚类原型模式 荟雄“ 矩阵p ( “1 ) ； 步骤三：如果怕“一p “0t s ，则算法停止并输出划分矩阵u 和聚类原型 p ，否则令b = b + l ，转向步骤一。其中1 1 0 为某种合适的矩阵范数。 当然，上述h c m 算法还有另一种形式，即首先初始化分类矩阵【，( 0 ) ，然后， 先用公式( 3 - 2 ) 计算聚类原型p ，再用公式( 3 1 ) 更新分类矩阵u “”，不 断迭代，直到移”一u i l cs 为止。 2 2 2f c m 算法 初始化：给定聚类类别数c ，2 c n ，n 是数据个数，设定迭代停止闽值 e ，初始化聚类原型模式p ( “，设置迭代计数器b ；0 对于v t ，t ，如果| 站，。，则有艘- 喜 ( 器) 嘉1 _ 1 c s s ， 如果j i ，r ，使得秽；0 ，则有心一1 ，且对j ，硝= o 罗( 雕“) ”吒 步骤二：用霉6 “) 。皇一，i = l ，2 ，c ( 3 4 ) 更新聚类原型 荟( ) ” 模式矩阵p “1 ) ； 步骤三：如果眵“一p 6 圳i l cs ，则算法停止并输出划分矩阵u 和聚类原型 p ，否则令b = b + l ，转向步骤一。其中j i i j 为某种合适的矩阵范数。 1 4 模糊聚类算法应用研究 浙江大学硕士学位论文 同样，该算法也具有另一种形式， 式( 3 4 ) 计算聚类原型( 中心) 矩阵， 直到满足准则为止。 2 3 模糊聚类算法研究现状 即从初始化模糊划分矩阵开始，先用公 然后用公式( 3 3 ) 更新模糊分类矩阵， 下面从模糊聚类目标函数的演化、算法实现的途径、有效性度量方式3 个 方面对模糊聚类理论进行分析，讨论模糊聚类的研究方向及其应用前景。”“。 2 3 1 模糊聚类目标函数的演化 由模糊聚类的数据模型可知，对于一组给定的样本集，模糊聚类分析可很 容易获得它的一个模糊c 划分：u 心1 1 s f s c ；1 七”，。但是，要保证划分 的有意义，则需要依据问题的需要定义合适的划分准则，比如常用的相似( 异) 性准则d ( ) 。假设每个模糊子集z ( 1 s is c ) 都形成一个模式见( 常被称作聚类 原型) ，则样本x k 与模糊子集置的相似性可以通过它的聚类原型b 间的失真度 d i k = d 瓴，b ) 来度量，从而确定模糊划分矩阵u 。不过，聚类原型事先无法得 知，需在聚类过程中逐步形成。 这样，为了保证聚类的结果的正确性，就以极小的每类样本与该模式间的 失真度构造模糊聚类的目标函数，然后通过优化该目标函数获得样本集的最佳 模糊聚类c 划分u = 和每类的模式p ； n ，l 0 应用l a g r a n g e 乘子法。可以得到类中心的迭代公式。 o z d e m i r 提出了i n t e r c l u s t e rs e p a r a t i o n ( i c s ) ，在模糊c 一均值算法的 目标函数中加入一个分裂项，形成如下的目标函数： j = i 1 刍n 刍c i ( 心) ”以一詈薹d 化川) ， 心zo ，喜= ， t i m m 和k r u s e 为了避免产生一致的类中心，在p c m 算法的目标函数中也加 入类中心的排斥项，得到如下的目标函数： 模糊聚类算法应用研究浙江人学硕士学位论文 j = 荟n 善c 肛4 叱+ 荟c 叩，羹。一，“+ 薹 善瞄o ，u 订1 ， = o ，套 。，n i 3 2f c m 算法有效性判别 尽管f c m 算法是一种无监督的机器自学习算法，但是，有二个参数在聚类 分析前必须给出合适的赋值，即模糊加权指数m 和聚类类别数c ，否则将影响 f c m 算法的分析效果，直接影响聚类分析结果的合理解释。为了能够对m 和c 进行优选，必须要有一些对聚类有效性判别的函数，来对其进行选择。 3 2 1 对聚类类别数c 的选择 在1 9 6 5 年，模糊集理论的创始入z a d e h 给出了第一个聚类有效性函数：分 离度函数，但它对模糊聚类的判别并不太理想。1 9 7 4 年，b e z d e k 提出了划分系 数“3 1 的概念，才。构成了第一个实用的聚类有效性函数f ( u ：c ) ，该函数具有良好 的数学性质和直观的几何解释。但它的主要缺点是它的单调趋势以及与数据自 身的某些特征缺少直接联系。在此基础上，很多人对模糊聚类的有效性进行了 研究，也提出了不少判别函数。下面，我们来具体看一下这些模糊聚类有效性 相关的判别函数： ( 1 ) 划分系数f u ；c ) ： 对于给定的聚类中，d 数c 和隶属度矩阵u ，划分系数定义为 f ( u ；c ) 2 砉善善露，其中，n 为待分析的样本数据的个数。 f ( u ：c ) 具有以下性质：当l c n 时，有( i ) 1 c f ( u ：c ) 1 ；( i i ) f ( u ：c ) = 1 当且仅当u 是硬划分；( i i i ) f ( u ：c ) = l c 当且仅当l i = 1 c 。 令q 。表示【厂m 。的“最优”的有限集合，若存在缈+ ，c + ) 满足 f ( u ；c ) 2 峄 n f ( u ；c ) ) ，n ( u ，c + ) 为最佳的有效性聚类，c 为最好的分 类数目。 ( 2 ) 可能性划分系数p ( u ：c ) ： 2 8 模糊聚类算法应用研究 浙江大学硕十学位论文 对于每一个样本x ，都有善心2 1 。这可看成是对9 6 m 算法的一个概率约 束。9 ( “：c ) 也可写成，；c ) 。吉荟( 善蛳27 善心) ，如果从可能性分布的角度讲， f ( u ：c ) 可解释成：每个样本点相对于c 个聚类中心都有一个可能性分布，f ( u ：c ) 是n 个可能性分布描述因子的平均值。对应的，对每一个聚类中心，n 个样本 点的隶属度构成一个可能性分布。由此，引出了可能性划分系数p ( u ：c ) 的定义。 对于给定的聚类数c 和隶属度矩阵o ，可能性划分系数p ( u ：c ) 定义成： p ( u ；c ) 。i l 刍= 刍n 如27 荟如) 。 p ( u ：c ) 具有以下性质：当l c l 。 为了衡量模糊聚类结果的模糊程度，b e z d e k 仿照s h a n n o n 信息熵的形式定 义了划分熵。其概念如下： 模糊聚类算法应用研究 浙江人学硕士学位论文 对于给定的聚类数c 和模糊划分矩阵u ，其划分熵定义为： h m ( u ；c ) = 一吉荟善l o g ( ) ，其中，n n + ) 为对数的底数，且约定 心= 0 时，有心l o ( 心) 0 。对于模糊聚类问题，我们当然不满足于数据的 硬划分，我们希望获得样本间的相似信息。对此前提下，样本集的划分越分明 就越有利于分类，因此对于给定的m 值，总希望模糊聚类的划分熵越小越好。 模糊加权指数m 对划分熵会产生影响。对于l ( c ( n ，m 1 ，+ 。) 的f c m 算法， 其划分熵有如下性质： ( 1 ) 0 s 巩；c ) s l o g 。c ； ( 2 ) 当m = l 时，以；c ) 一0 u 是硬划分； ( 3 ) 当m 一1 + 时，只，c r ；c ) 以概率1 趋近于o ； ( 4 ) 当m 一+ 时，巩( u ；c ) = l o g c u 一【1 c 】。 显然，参数m 控制着f c m 聚类结果的模糊性，而且m 越大聚类的结果越模 糊，在1 1 1 可行解的两端分别对应着划分熵的最大值和最小值。由于我们希望聚 类的结果不要太模糊，这就要求在调用f c m 算法时，m 的取值不要太大。当然 这并不意味着小的m 值就对应好的聚类结果。因为较大的加权指数m 还具有仰 制噪声的功能，在噪声污染的数据中获取模式样本的模糊聚类应用中有着重要 的作用。 3 3 改进的f c m 算法 对于v i ，t ，如果a d ，。，则有碰12 薹f ( 筹) 者 ) 1 c s s ， 模糊聚类算法应用研究 浙江大学硕士学位论文 如果j i ，r ，使得d 箩= 0 ，则有心= 1 ，且对，r ，硝= 0 罗( 硭“) “ 步骤二：用e “1 ) = 宣了一，i = l ，2 ，c ( 3 4 ) 更新聚类原型 荟( 广 模式矩阵p ( “1 ) ： 步骤三：如果怕9 一p 伸叫lc ，则算法停止并输出划分矩阵u 和聚类原型 p ，否则令b = b + l ，转向步骤一。其中| | 1 i 为某种合适的矩阵范数。 同样，该算法也具有另一种形式，即从初始化模糊划分矩阵开始，先用公 式( 3 4 ) 计算聚类原型( 中心) 矩阵，然后用公式( 3 - 3 ) 更新模糊分类矩阵， 直到满足准则为止。 f c m 算法是目前比较常用的模糊聚类算法，它有着完善的理论和深厚的数 学基础。在数据的结果簇是密集的，且簇与簇之间区分明显时，它的效果较好。 而且该算法是相对可伸缩和高效率的，因为算法的复杂度是0 ( n c b ) ，其中，y l 是数据对象的个数，c 是聚类的数目，b 是迭代的次数。 然而f c m 算法也有不少缺点：( 1 ) f c m 算法对对孤立点数据比较敏感。( 2 ) f c m 算法需要事先指定聚类数目c 和模糊加权指数m ，而c 和m 直接影响着聚类 的结果。( 3 ) 由于模糊聚类的目标函数是非凸的，而f c m 类型算法又是迭代爬 山的，因此容易陷入局部极值点或鞍点，而得不到最优解。 针对前二个缺点，我们提出了一些方法，来改善f c m 类型算法。对于最后 的一个缺点，需要引入新的技术来加以解决，比如神经网络和进化计算，这些 不是本文所涉及的重点，在以后的学习中，会进一步进行研究和分析。 3 3 1 降低孤立点的影响 在通常的f c m 算法中，数据对象的属于某个特定类的隶属度是根据这个对象 到特定类中心的距离来确定的。每个数据对象的隶属度表明了这个数据对象隶 属于这个类的程度，数据对象的隶属度的值越大，它就具有越小的不确定性； 相反，隶属度越小，则不确定性越大。同时，在聚类中心的更新中，隶属度也 显示了每个数据对象对新的聚类中心的调整中的贡献的程度。隶属度的值越高， 模糊聚类算法应用研究 浙江大学硕士学位论文 它对聚类中心的位置的影响也越大，相反，隶属度的值越小，影响也越小。 然而，由于生成的隶属度是相对数量，它们很可能在典型代表的应用中是不 适合的。因此使用这些隶属度计算得到的聚类中心很可能不是期望的聚类中心 位置。假如有一个孤立的数据对象点，它对所有的聚类中心的隶属度均为1 n ( 这里n 指聚类的数目) ，那么它就可能会引起一个不期望的聚类结果。 为了降低孤立点对检测结果的影响，我们提出了一种改进方法：针对数据对 象的模糊隶属度，对其增加一个加权值，来减少孤立点对聚类中心的影响，从 而达到改进聚类分析的结果。我们通过对输入的数据对象的隶属度的值进行加 权，使隶属度的值高的数据对象对聚类中心位置的影响增大，对于隶属度小的 数据对象则降低它们对聚类中心的影响。 我们对隶属度以给予一个加权值，将其修改为：心：心一掣鲰。 二 从上式可以看出，心与相比是在原来的基础上减去了掣这部 二 分内容。其中掣是为了使得当普通f c m 算法中的隶属度缘为1 时，新的 二 加权后的隶属度以依然为1 。而在掣后面的，则是为了保证在原