（计算机系统结构专业论文）afcm算法的模型设计与研究.pdf

| | i l ll li ll l l l li l li lllli y 18 9 9 4 11 t h e d e s i g na n ds t u d y o fa f c m a l g o r i t h m m o d e l at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t f o rt h em sd e g r e ei nc o m p u t e rs c i e n c e b y s u nz h i y e p o s t g r a d u a t ep r o g r a m c o m p u t e r s c i e n c ed e p a r t m e n t c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：g a ol i a c a d e m i ct i t l e ：p r o f e s s o r s i g n a t u r e 彘彬如 a p p r o v e d m a y , 2 0 1 1 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：- 3 0 ，怎叶 日期：p o l l 年厂月，日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中师范 大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 作者签名：们，玺叶 日期：加f 年y 月了1 日 导师签名： 南函 日期：别，年b 月2 - 日 本人已经认真阅读“c a l l s 高校学位论文全文数据库发布章程”，同意将本人 的学位论文提交“c a l l s 高校学位论文全文数据库 中全文发布，并可按“章程 中的规定享受相关权益。回童途塞握童卮溢卮! 旦圭生；旦二生；旦三釜蕉查! 作者签名：们，志叶 日期：知l 年f 月；1 日 导师签名：南历 日期：必7j 年易月p 日 7 、 ： 硕士学位论文 m a s t e r st h e s i s 摘要 f c m ( f u z z yc m e a n s ，f c m ) 算法是一种基于目标函数优化的模糊聚类方法， 其收敛结果依赖于聚类原型参数的先验知识( 即聚类中心和聚类数) 。目前f c m 算法已经被广泛地应用于模式识别、数据挖掘、模糊控制、图像处理、图像分割、 矢量量化、模糊逻辑等众多领域。但由于大部分的f c m 算法及其改进算法的初始 聚类中心和聚类数几乎都是随机给定的，需要经过多次试验才能得到较好的聚类结 果。因此，给出合理的聚类中心和聚类数目十分重要。随着计算机科学技术的应用 和发展，基于目标函数的模糊聚类算法( 即f c m 算法) 成为新的研究热点。 经过国内外众多学者多年的努力，f c m 算法已经获得了很大的改进。但是，到 目前为止该算法存在的一些问题和不足依然没有得到的较好的解决，使得该算法的 优势不能充分的得到发挥。针对传统的f c m 算法存在的不足提出一些具体的改进 办法，不仅能够提高算法的执行效率，而且对实验的过程和结果也能够产生很多积 极的影响。 本文针对f c m 算法的不足并围绕如何提高算法的执行效率这一问题，对传统 的f c m 算法进行了改进，并提出了一种新的聚类算法( a d v a n c e df u z z yc l u s t e r i n g m e a n s ，a f c m ) ，本文的主要研究工作及创新之处主要体现在以下两个方面： ( 1 ) 本文对传统的f c m 算法中的权指数选取进行了改进，即根据实际问题计算 权值的大小。由于权指数m 的选择对f c m 算法聚类分析影响很大，通过这种方法 我们不仅能够得到更为合理的权指数m 值，而且能够减少因为人为选取权值带来的 失误。实验证明，使用通过计算得到的m 值得到的实验结果也更为理想。 ( 2 ) 本文提出了对f c m 算法中的隶属度进行了修正，通过对隶属度的不断修正 可以提高聚类的收敛速度和影响聚类的分类效果，减少算法执行的时间花费，可以 从整体上提高算法的性能。 另外，f c m 算法具有自身的优点，尤其是对海量信息进行加工处理时，它的优 势就表现的更加明显了。同时，在一些的著名的科学计算软件( 如m a t l a b 等) 中也包 含了f c m 算法，这些都给人们的研究工作带来了极大的方便。 最后，利用m a t l a b 仿真工具通过对应用传统的f c m 算法得到的实验结果与应 用本文改进后的a f c m 算法得到的结果做比较。仿真结果表明，本文提出的a - f c m 算法能更有效地提高了算法的性能和效率，得到更加合理的结果。 关键词：f c m 算法，权重系数，隶属度，聚类有效性 i l f 入 ： ： 硕士学位论文 m a s t e r st h e s i s a b s t r a c t f u z z yc m e a n sa l g o r i t h mi sab a s e do no b j e c t i v ef u n c t i o ni st h ev a g u ea n dc l a s s m e t h o d sa n dt h er e s u l ti sd e p e n d e n to nt h ec l u s t e r i n go fap a r a m e t e rp r e v i o u se x p e r i e n c e k n o w l e d g e ( c l u s t e r i n gc e n t e ra n dc l u s t e r i n gn u m b e r ) a tp r e s e n t ，f c ma l g o r i t h mi su s e d t on u m e r o u sf i e l d s ：m o d e li d e n t i f i c a t i o n , d a t am i i l i n v a g u ec o n t r o l ，i m a g ep r o c e s s i n g a n di m a g e sc u t ，v e c t o rq u a n t i z i n ga n df u z z yl o g i ca n ds oo n h o w e v e r , a sm o s to ff c m a l g o r i t h m a n di m p r o v e da l g o r i t h m sw h i c hi n i t i a l c l u s t e r i n gc e n t e r sa n dc l u s t e r i n g n u m b e r sa l m o s ta r eg i v e na tr a n d o ma n dn e e dm a n yt e s t sw i l lg e tb e t t e rc l u s t e r i n gr e s u l t s t h e r e f o r e ，g i v et h er e a s o n a b l ec l u s t e r i n gc e n t e r sa n dc l u s t e r i n gn u m b e ri sv e r yi m p o r t a n t w i t ht h ec o m p u t e rs c i e n c ea n dt e c h n o l o g ya p p l i c a t i o na n dd e v e l o p m e n t ，t h ev a g u e c l u s t e r i n ga l g o r i t h mw h i c hi sb a s e do no b j e c t i v ef u n c t i o n ( f c ma l g o r i t h m ) b e c o m e sa n e w s t u d yh o t a f t e rt h ed o m e s t i ca n df o r e i g ns c h o l a r se f f o r tf o rm a n yy e a r s ，f c ma l g o r i t h mh a s h a dag r e a ti m p r o v e m e n t b u t ，s of a rt h ea l g o r i t h m ss o m ep r o b l e m si ss t i l ln o tg e ta b e t t e rs o l u t i o na n da d v a n t a g eo ft h ea l g o r i t h mc a n tg e taf u l ld i s p l a y s o m es p e c i f i c i m p r o v e m e n tm e a s u r e sa r ep r o p o s e df o rt h et r a d i t i o n a lf c ma l g o r i t h mn o to n l yt o e n h a n c et h ee f f i c i e n c yo ft h ea l g o r i t h m ，b u tc o u l dc r e a t em a n yp o s i t i v ei m p a c t so nt h e e x p e r i m e n tp r o c e s sa n dt h er e s u l t i nt h i sp a p e r , f o rt h ei n a d e q u a t eo ff c ma l g o r i t h ma n dh o wt o i m p r o v et h e e f f i c i e n c yo ft h em e t h o de x e c u t i v e ，w em o d i f i e dt h et r a d i t i o n a lf c ma l g o r i t h ma n d p r o p o s e da na d v a n c e df u z z yc l u s t e r i n gm e a n sa l g r o t h m ( a - f c m ) ，m a j o rr e s e a r c hw o r k a n di n n o v a t i o no ft h ep a p e ri nt h ef o l l o w i n gt w oa s p a c t s ： ( 1 ) i nt h i sp a p e r , t h em e t h o d sw h i c hs e l e c tt h er i g h ti n d e xh a v eb e e ni m p r o v e df o r t r a d i t i o n a lf c ma l g o r i t h m ，t h a ti s ，t oc a l c u l a t er i g h tv a l u ea c c o r d i n gt ot h ep r a c t i c a l p r o b l e m s b e c a u s eo ft h er i g h ti n d e xmt of c ma l g o r i t h mc l u s t e r i n ga n a l y s i sh a v ea g r e a ti n f l u e n c e ，i nt h i sw a yw en o to n l yc a ng a i nm o r er e a s o n a b l emv a l u e ，b u tc a l l r e d u c et h ee r r o r sb e c a u s eo fa r t i f i c i a lc h o o s er i g h tv a l u e s e x p e r i m e n t sp r o v e ，t h r o u g h t h eu s eo ft h emv a l u ew h i c hi sg a i n e db yc a c u l a t e d ，i t se x p e r i m e n t a lr e s u l ti sm o r ei d e a l ( 2 ) t h ea m e n d m e n to fd e g r e eo fm e m b e r s h i pi nf c ma l g o r i t h m ，t h r o u g ht h e a m e n d m e n td e g r e eo fm e m b e r s h i pc o n s t a n t l yw h i c hc o n v e r g e n c es p e e dc a l lb er a i s e d i i i 硕士学位论文 m a s t e r st h e s i s a n di m p a c to ft h ec l a s s i f i c a t i o ne f f e c to fc l u s t e r i n g ，r e d u c e t h et i m e o fa l g o r i t h m i m p l e m e n t a t i o n t h i sc a l li m p r o v et h eo v e r a l lp e r f o r m a n c eo ft h ea l g o r i t h m i na d d i t i o n , f c ma l g o r i t h mh a si t s e l fm e r i t s e s p e c i a l l y ，w h e nl a r g ei n f o r m a t i o nb e p r o c e s s e d ，i t st h ea d v a n t a g ei sm o r eo b v i o u s a tt h es a m et i m e ，i ns o m ef a m o u ss c i e n c e c a c u l a t es o f t w a r e s ( a sm a t l a b ) a l s oc o n t a i n s f c ma l g o r i t h m t h e s eo f f e r g r e a t c o n v e n i e n c ef o rt h er e s e a r c hw o r k f i n a l l y , i nm a t l a bs i m u l a t i o nt o o lu s et r a d i t i o n a lf c ma l g o r i t h ma n du s ea f c m a l g o r i t h m sg e tt h ee x p e r i m e n t a lr e s u l t st oc o m p a r e ，s i m u l a t i o nr e s u l t sp r o v e ，t h i st e x t p r o p o s e da f c ma l g o r i t h m sc a l lb em o r ee f f e c t i v e l yi m p r o v e d p e f f o r m a n c ea n d e f f i c i e n c yo ft h em e t h o d ，t h er e s u l t sa l s eb em o r er e a s o n a b l e k e yw o r d s ：f c ma l g o r i t h m ，w e i g h te x p o n e n t m e m b e r s h i pd e g r e e ，c l u s t e rv a l i d i t y i v 摘要 a b s t r a c t 。 第1 章绪论 目录 川川川川川 i i l l 1 1f c m 算法简介1 1 2 发展现状及选题背景2 1 - 3 本文的研究意义3 1 4 本文所做的工作4 1 5 论文的组织结构4 第2 章传统的f c m 算法。6 2 1 传统f c m 算法：。6 2 1 1k 均值聚类算法6 2 1 2 传统f c m 算法的介绍o 7 2 2 当前f c m 算法的研究现状。1 0 2 3f c m 算法研究的关键技术1 2 2 4 本章小结1 3 第3 章a f c m 算法。1 4 3 1a f c m 算法概述1 4 3 1 1 权指数概述。1 4 3 1 2 隶属度概述15 3 2a f c m 算法。1 7 3 2 1 权指数的计算1 7 3 2 2 隶属度的修正。18 3 2 3a f c m 算法公式表示1 9 3 2 4a f c m 算法描述2 0 3 2 5a f c m 算法流程图2 0 3 3a f c m 算法有效性检验2 2 3 4 本章小结2 3 第4 章实验与分析 ：1 4 4 1 实验仿真2 5 4 2 传统f c m 算法和a f c m 算法实验结果的对比分析2 6 4 3 本章小结3 0 第5 章总结和展望3 2 5 1 总结3 2 5 2 展望3 3 参考文献”3 4 硕士期间发表的论文和参与科研项目”3 7 致谢”3 8 1 1 f c m 算法简介 第1 章绪论 聚类分析既是数学研究中一种非常重要的方法，也是模式分析领域的一个重要 方向。根据某一种准则，聚类分析能够把一些原本彼此区别很小的数据点分割成若 干个集合，它把相似的数据点放在一组中，把差别很大的点放在不相同的组中。作 为一种重要的分类方法，它在目前已经广泛应用于图像识别、图像分割等方面。 最初，聚类分析实际上只是一种硬划分，它只能简单的把一些样本点依据某种 规则进行划分，从而得到相应的结果。而在实际应用中，情况要复杂的多，主要体 现在我们面对的研究对象大多数都是一些非常相似的样本，显然这时候使用软划分 更具有合理性。这时模糊集理论的产生给我们的研究带来了有利的条件和奠定了相 应的理论基础，于是人们开始用模糊的方法来解决实际生活中的相关聚类问题，最 后把它称之为模糊聚类分析。 目前，基于目标函数的模糊聚类方法在实际中的应用最为普遍，这种方法的核 心思想就是把相关的聚类问题变成一个数学的问题进行求解，利用数学工具来求得 最终的模糊划分。该方法具有实用性较强，易于操作等优点，还可以通过转化而利 用数学的方法求解，且易于在机器上运行实现。因此，随着相关领域技术的不断发 展进步，模糊聚类算法的研究变得越来越普遍重要。 在基于目标函数的聚类算法中，模糊c 均值算法的理论最为成熟，应用最为广 泛。因为f c m 算法把聚类问题转化为一个数学的问题，然后利用交替优化策略求解 分类问题【l 】，因此它是目前最为常用的一种模糊聚类算法。 l a z a d e h 在1 9 6 5 年提出模糊集概念后，模糊集最初是应用在模式识别的领域【2 j 1 3 】。后来经过e h r u s p i n i d 的努力，将数据的硬划分概念加以改进和推广，最终引入 了数据的模糊划分【4 】，1 9 7 4 年d u n n ，v 将硬c 均值聚类算法推广到模糊情形1 5 j ，7 0 年代 年后期b e z d e k 从物理学的角度 6 1 ，对m = 2 时的隶属度进行了解释。详细地对模糊c 均 值聚类算法的收敛性和聚类有效性等问题进行了研究，并写成了著作【7 j 。模糊聚类 分析就是应用模糊数学的方法把具有相似性质的事物区分开，并加以分类。模糊c 均值聚类算法有一个重要的概念是隶属度，它的意思是每个数据点属于某个聚类的 程度，而这也是模糊c 均值聚类算法的核心思想。f c m 算法是目前最重要也是最流 行的模糊聚类算法之一。f c m 算法是h c m ( h a r dc m e a n s ) 算法的一种改进，f c m 石舞士学位论文 m a s t e r st h e s l s 把n 个向量x ，( ，= 1 ，2 ，以) 分为c 个模糊组，计算非相似性指标的价值函数使得其变 为最小并，求出每组的聚类中心。在日常的应用当中人们也经常用n k 均值算法， 它们两者的差别主要体现在f c m 算法使用的是模糊划分且每个数据点用值在o 和l 之间的隶属度来表示它们属于哪个类。f c m 作为非监督机器学习的主要技术之一， 建立了样本类属的不确定性的描述，能够比较客观地反映现实世界【8 j 。f c m 算法在 数据挖掘、图像处理、模式识别、模糊逻辑等领域被广泛采用。近年来对于f c m 算 法已经有很多学者提出了改进的算法，本文是在对传统的f c m 算法研究的基础上1 9 】 【1 0 】，并对该算法进行相关的改进最终得到a f c m 算法，并通过实验数据证明该算法 是有效的。 1 2 发展现状及选题背景 随着计算机科学技术的快速发展以及对人们生活中各种实际应用的需求不断 增强，数据挖掘技术逐渐产生并发挥越来越重要的作用。由于数据挖掘技术的应用 广泛、成本低、功能强大等特点，它能够很大程度的提高我们对问题的解决效率， 数据挖掘在电信、零售、农业、网络日志、银行、电力、生物、天体、化工、 医药等方面都具有广阔的应用前景。 在数据挖掘技术中，f c m 算法是当前研究的热门课题之一，同时也是一个非常 重要的课题。国内外对目前f c m 算法正在进行广泛的应用与研究，主要体现在两 个方面：一方面从理论上对f c m 算法进行不断地改进；另一方面就是将改进后的 f c m 算法应用于实际问题的解决。 在众多的聚类算法中，其中人们对f c m 算法的研究比较多且它的应用范围也 较广，在实际应用中是一种十分重要的聚类算法。它主要的优点是能够把聚类的问 题转化为相关的数学问题，具有其他聚类算法没有的优点。目前，即使就是这样的 一种优秀的算法也存在着一些不足之处，比如加权指数与聚类数目大小的确定，如 果这两个问题得不到很好的解决，很可能会影响f c m 算法的分类效果和降低f c m 算法的执行效率。本文就将对这两个问题的确定方法进行讨论。 f c m 算法是目前最常使用的聚类算法之一，其中该算法的两个关键问题分别是 对权指数的选择和隶属度的修正。由于这两个问题的解决对f c m 算法的结果影响 很大，因此，目前国内外学者对该算法的研究大多是围绕如下问题进行研究的，一 个是权指数m 值，另一个是隶属度的问题，并将有关的研究成果应用到相关的实际 问题当中。 2 1 3 本文的研究意义 数据挖掘( d m ，d a t a m i n i n g ) 就是从大量的，有噪声的，模糊的，不完全的，随 机的数据中提取隐藏在其中的，人们事先不可知的，但又是确实存在的有价值信息 和知识的过程。在实际中与这一概念相近的概念还有很多，例如数据库中数据分析， 知识提取，模式分析，数据采集，发现知识，信息收集，数据考古以及数据捕捞等。 原始数据通常被认为是人们形成知识的源泉，就像从矿石中采矿一样。如在数 据库的数据中，源数据可被当作是结构化的；然而文本和图形等则是被认为是半结 构化的；甚至还有的是异构型数据，如分布在网络上的。发现知识的方法和途径有 很多，可以是分析的，也可以是综合的。所以，我们有时候把数据挖掘看成是- f - j 广义的交叉学科，它聚集了不同领域的研究者，特别是研究数据库领域的相关学者。 需要强调的是，数据挖掘技术最初是面向应用的。例如，某国家的一个省电话 公司要求该国的某个大学的数据挖掘研究组，根据客户电话的相关数据信息进行研 究，并提出新的电话收费标准和管理办法供政府相关部门参考，制定能够使得公司 和客户双赢的有利政策。另外，在美国n b a 联赛中，一些著名篮球队的教练利用 i b m 公司提供的数据挖掘技术，对每个队员的场上表现进行统计分析并临场决定替 换队员，一度在数据库界引起不小的轰动。这样来，数据挖掘技术就把人们对数 据的应用，从低层次的末端查询操作，提高到为各级经营决策者提供决策支持。总 之，数据挖掘技术是一门在当今社会中十分有用的科学，人们可以利用相关的模型 和关系可以对未来做出预测。 在数据挖掘技术中，聚类分析是很重要的内容之一，而在聚类分析中，聚类算 法是最为关键的部分之一。f c m 算法是目前应用最为广泛的一种模糊聚类算法，也 是种基于目标函数优化的模糊聚类方法。该算法的收敛结果依赖于聚类原型参数 的先验知识( 即聚类中心和聚类数) 。f c m 算法的主要思想也是使得各个样本点用o 和l 之间的值来表示各点属于各个类的程度。它作为非监督机器学习的主要技术之 一，它的优点是能够较好的反映客观事实。f c m 算法在数据挖掘、图像处理、语音 识别、模式识别、模糊逻辑、空间导航系统等领域被广泛应用。 本文研究的f c m 算法是在对权指数和隶属度进行改进基础上的算法，该算法不 仅继承传统f c m 算法的优点，而且又对传统的f c m 算法做了相关的改进。传统 f c m 算法最基本的要求就是满足划分后同一簇内元素之间的距离尽可能地小，不同 簇的元素之间的距离尽可能地大。而本文将要研究的f c m 算法是通过对权指数的 计算和隶属度的修正进而使得算法在运行的效率上比传统的f c m 算法更高，在实 3 ： 硕士学位论文 m a s t e r st h e s i s 验得出的最终结果上也更加合理。 f c m 算法的应用领域非常广泛，在实际生活当中有很多重要的应用。如：对气 象数据的分析判断。通过f c m 算法对降水和气温数据进行仿真实验分析，进而可 以判断某地区( 如我国的黑龙江省地区) 降水和气温的变化与当地气候特征的关系。 在其他方面如对遥感图像处理，医学图像，基因数据的处理等都有着广泛地应用。 最后，通过众多学者对f c m 算法多年的研究，许多关于f c m 算法的研究成果 在实际生活当中已经得到了很好的应用，许多好的研究方法和手段也值得我们学习 和借鉴，这些都给我们进一步的研究工作提供了有利的条件和极大的帮助。因此， 本文作者有必要对该算法再进行更进一步的研究和学习，同时也认为对f c m 算法 的进一步研究一定是一件有意义的工作。 1 4 本文所做的工作 本文针对传统f c m 算法的不足围绕提高算法执行效率，减少算法执行的时间 花费和提高算法的稳定性，可靠性等几个问题，对传统f c m 算法中权指数m 值和 隶属度进行改进。具体包括对权值的计算和对隶属度的不断修正，以使得f c m 算 法得到进一步的改进，最终提出了a f c m 算法。 本文主要问题分为如下三个主要部分： ( 1 ) 对权指数的改进：由于多数学者对f c m 算法的研究中是基于事先指定权值 m 的大小，这样的m 值有很大的随机性和不确定性，因此根据这样的m 值经过实 验得到的结果也并非是合理的。而本文的研究是根据我们实际当中问题具体的去计 算m 值这样可以提高实验结果的可信度、保证实验的质量。 ( 2 ) 对隶属度的修正：在本文的a f c m 算法中，通过对隶属度的不断修正，逐 渐对各个数据点进行分类，不仅可以提高算法的执行效率、减少算法执行的时间花 费，而且可以提高分类的正确性，避免错误的分类。 ( 3 ) 实验与分析：通过对权指数的计算和隶属度的修正，最后得到本文提出的 a f c m 算法，通过对我国黑龙江省地区2 0 0 0 年全年的降水和气温数据的实验仿真， 在多方面对比传统的f c m 算法和本文提出的a f c m 算法可以得出：本文提出的 a f c m 算法不论在执行效率和时间花费方面，还是实验结果可行性、客观性、合 理性方面都比传统的f c m 算法有较大的改进。 1 5 论文的组织结构 本文针对f c m 算法中权指数和隶属度问题的研究，在仔细分析权指数和隶属 4 ： ： 硕士学位论文 m a s t e r st h e s i s 度等相关问题的基础上，提出了a f c m 算法，a f c m 算法的特点和优点就是同时 对权指数和隶属度进行了改进。在本文中，用m a t l a b 作为仿真工具将对传统的f c m 算法和a f c m 算法进行了仿真，主要在算法的执行效率、时间花费、算法的稳定 性能和聚类的聚类等几个方面进行深入研究，最后对仿真结果进行了对比和分析。 论文的结构安排如下： 第一章绪论，简单介绍了f c m 算法的简介，发展现状和选题背景，本文的研 究意义以及本文所做的工作。 第二章传统的f c m 算法，主要介绍了k 均值算法和传统f c m 算法，当前f c m 算法研究现状，f c m 算法研究的关键技术。 第三章a f c m 算法，主要介绍了权指数和隶属度，权指数的计算，隶属度的 修正，a f c m 算法的公式表示，算法描述，流程图以及a f c m 算法的有效性检验 等问题。 第四章实验与分析，介绍了实验数据的选取，分析和处理，仿真实验及对两 种算法实验结果的对比分析。 第五章总结和展望，对论文目前所作的工作进行了总结，并对接下来要开展 的工作进行了展望。 ： 硕士学位论文 m a s t e r st h e s i s 2 1 传统f c m 算法 第2 章传统的f c m 算法 聚类分析中的模糊聚类算法经过许多年的发展，因为其应用十分广泛，实用性 很强，今天已经成为人们非常得力的分析工具之一。但由于f c m 算法是最初是由k 均值算法经过修改而得到的，两种算法在诸多方面都有着相似的性质。所以在介绍 f c m 算法之前，我们有必要先了解一下k 均值聚类算法。 2 1 1k 均值聚类算法 k 均值聚类，就是大家都已经知道的c 均值聚类，现如今已经广泛应用到各种方 面。其工作的流程具体描述为：首先在n 个数据中任意挑选k 个数据作为刚开始的聚 类中心，对剩下的数据点则根据它们与这些聚类中心的长度，分别将这些点分到相 应的类中，然后再重新计算各个新的类中心，一直重复进行这种计算，直到满足函 数( 2 1 ) 为止。 对于相似度我们可以通过相关的函数来进行求得，人们常用的有m i n k o s k i 距离， m a h a l a n o i s l 瓦_ 离等，本文中我们以欧式距离作为距离公式，如( 2 2 ) ： e = 肛一m 川2 ( 2 1 ) j = lt = l r 一 d ( t ，x j ) = 、脚矗一如1 1 2 ( 2 2 ) r = l p 为样本点，聊i 为c 类的平均值。 d ( 墨，x ，) 为点x j 和x ，的长度，m 为数据点的维数。 k 均值算法执行的步骤如下【1 4 】： ( 1 ) 从n 个样本点中任意挑选k 个样本点作为算法开始的类中心； ( 2 ) 循环执行步骤( 3 ) 和( 4 ) ，直到每个类中心变得稳定； ( 3 ) 由计算得到的每个平均值，再次计算每个数据与这些中心的距离，并根据 前面的方法对相应对象进行重新分类； ( 4 ) 重新计算类的平均值。 尽管k 均值聚类算法在实际应用中已经十分普遍，但k 均值聚类算法也有许多不 6 足之处【1 5 1 1 16 1o t i ，主要包括以下几点： ( 1 ) 类的数目必须事先确定； ( 2 ) 在实际应用中均值对于类别属性多数情况下不太适合； ( 3 ) 初始类中心的随意性可能会导致聚类结果的不确定性，且有可能造成错误 分类： ( 4 ) 对非正常的数据点和单个的数据点反应较为灵敏。 2 1 2 传统f c m 算法的介绍 f c m 算法是一种基于划分的聚类算法，该算法的主要思想就是使得被划分到同 一簇的数据点之间相像度最大，而不同簇之间的数据点相像度最小。模糊c 均值算 法是普通c 均值算法经过改造得到的的，c 均值与f c m 这两个算法的区别在于前者对 数据的划分是生硬的，后边这种算法则是一种柔软的划分。因此，在介绍f c m 具体 算法之前我们先介绍一些模糊集合的简单知识。 在数学当中，最常用的距离函数是欧式距离1 8 】0 9 1 ，这此我们也将使用这个函数。 另外，在我们求聚类对象之间的长度时，由于数据点属性的量纲有时候存在不一致， 所以在进行运算之前我们应先对相关的数据进行规范化处理，人们习惯上把数据放 在 0 ，1 之间。使用的方法如式( 2 3 ) 所示： x ：_ 2 生一二翌l( 2 3 ) x m h x m i i l 空间聚类也是一种对数据划分或分组的重要方法。它是将研究对象按照某种准 则划分到多个集合中，让处于同一个集合中的各数据间差别最小，而位于不同的子 集中各元素间差别最大。一般的空间聚类算法是建立在各种距离基础上的，其中， 欧式距离是目前最为广泛的度量方法【2 0 1 。描述如下： ( 1 ) 确定聚类的数目c ； ( 2 ) 随机挑选c 个样本代表类的中心； ( 3 ) 对剩余的每个样本，将它赋给离它最近的类； ( 4 ) 重新计算每个类内对象的平均值，形成新的聚类中心； ( 5 ) 判断新的聚类中心和上一次的是否完全相同，若相同，算法停止，否则， 返回到( 3 ) 。 传统模糊聚类问题可以看成是数学规划问题，即 mi nj 历( u ，y ) ：兰妻( 甜墙) mi i x 七一v ，1 1 2 ( 2 4 ) k = i ，= l 7 其中 甜请= 1 ， i = l 1 u 政0 ， i = l ，2 ，c k = l ，2 ，1 1 这里x = 伟，x 2 ，毛) 是点的集合，n 代表元素的个数，c 代表聚类中心的个数，m 是模糊系数( n l 1 ) ，扰腩是第k 个点属于第i 个中心的隶属度， 8 一v , 1 1 2 = ( 毪一v ，一v ) 。 文献中的定理证明， ，) 是厶( “，1 ，) 局部极小值的必要条件为： ( 纠，七) 朋x 七 v f - - 丘 一 ( 甜肚) 研 ( 2 5 ) 其中兹= l l x , 一训， ( k _ 1 2 ，n ) ( 2 6 ) f c m 算法的执行流程是用来回循环的方法求解式( 2 5 ) 和式( 2 6 ) ，直至满足终 止条件，描述如下： ( 1 ) 确定c ，m 和算法的停止条件。 ( 2 ) 选择v = “，v 2 ，k ) 。 ( 3 ) 进行如下过程，直到满足给出的要求： 计算隶属度函数，根据式( 2 6 ) 。 更新计算各类聚类中心，根据式( 2 5 ) 。 当算法终止时即完成了聚类划分。 传统的f c m 算法执行的流程图如下： 8 o 膳 甜 刀心 ，、 ： 硕士学位论文 m a s t e r st h e s i s 图2 1 传统的f c m 算法执行的流程图 l = l + i n 以前的f c m 算法受初始聚类中心和聚类数的影响较大，最基本的要求就是要 使得处于同一类内的元素之间的间距尽可能地近，不同类的元素之间的间距尽可能 地远。这一目标过于不清晰，在实际应用中也难以做到，一些经常用到的聚类有效 性函数，由于其自身存在的诸多不足，如函数的非线性特征，单调性问题以及复杂 度问题等【2 2 1 ，它们对于聚类有效性检验的效果并不乐观，很难得到最佳聚类数c 。 以前的f c m 算法也存在着聚类数目难以确定，如何确定聚类中心和初始隶属度矩 阵，迭代容易陷入局部极值等等。 9 2 2 当前f g m 算法的研究现状 经过无数学者多年的研究，f c m 算法尽管已经获得了很大的改进。但是，到目 前为止该算法存在的一些问题和不足依然没有得到较好的解决，使得该算法的优势 的发挥受到很大的约束。针对传统的f c m 算法存在的不足如果能够提出一些具体 的改进办法，这不仅能够提高算法的有效性，而且对实验的过程和结果也能够产生 很多积极的影响。 由于f c m 算法拥有广阔的应用前景，也是当前的研究热点课题之一。目前的 许多研究有的是针对f c m 算法中聚类数目的；有的是针对f c m 算法中初始聚类中 心问题；有的针对聚类数目确定的问题，提出一种基于平均信息熵的方法，采用密 度函数法确定初始聚类中心；有的使用最近邻聚类算法来初始f c m 算法的聚类中 心和聚类数进而达到改进f c m 算法的目的；还有的通过构造费用函数通过使费用 最小进而达到改进f c m 算法的目的等等。 目前利用f c m 算法进行数据挖掘的应用领域十分广泛，如生物、金融、销售、 通信、电力、医药和其他商业领域的应用。f c m 算法作为目前一种重要的挖掘 技术，具有很广泛的应用前景睇引。 ( 1 ) 生物医学 在过去的几十年里，医学研究的发展突飞猛进，从新药物品种的研发和攻克 各种各样的疑难疾病，到找到为数众多的序列模式和基因功能，进行人类基因的识 别与研究。由于目前的许多学者都把学习的重点放在对d n a 数据的分析上，今天我 们在这里也好好看一下该应用的情况。近年来人类对d n a 的一系列研究成果已经极 大推进了医学的发展，并给无数的病人带去了希望。这里我们简单介绍f c m 算法在 d n a 分析中的重要作用。 关联分析：即在同一时刻出现的基因序列的识别。今天，许多学者把学习的 重点转移到对这个基因与那个基因的对比上。然而，实际上疾病发生的原因是多个 基因一起引发的。此时利用关联分析能够帮助我们确定解决这方面的相关问题。它 不仅有助于研究人员找到基因组，而且也有利于对基因间的相关研究。 可视化工具：基因的构造和序列模式一般能够使用图形等一些可视化工具的形 式表示。这样的结构和模式能够给知识发现和数据交互等提供便利。因此，我们认 为可视化在生物医学的研究当中起着重要的作用。 ( 2 ) 金融领域 如今，大多数银行和金融机构都能同时为客户提供种类多样的便利服务和信用 l o 服务。我们知道，有关的金融数据一般都比较整齐，有规则和可靠性强。这有利于 研究人员对其进行挖掘方面的研究。下面给出一些具体的应用： 数据挖掘设计和构造数据仓库：与在其它领域的应用十分相近，首先要为这些 数据建立一个相应的模型并对其属性进行必要的分析。如，有时人们按月份，按区 域或者依据另外的因素，查询支出和收入的变化情况，同时人们也期待能得到极值， 总数及平均值等相关的信息。数据仓库，数据立方体和对单个数据点分析等在数据 分析和挖掘中都同样发挥着十分重要的作用。 目标市场的分组：利用分组的方法能够方便人们对于客户的识别和市场的研 判。比如说利用多维的聚类分析金融机构能够将有相似存款和贷款行为的一组群众 分到一块。恰当的分类方法有助于信用社识别客户，把新的客户分类到相应的组当 中，最终推动目标市场的不断发展。 ( 3 ) 零售业领域 数据挖掘技术在零售业这方面的应用极其广泛，由于零售业中拥有极其丰富商 品数据，消费者的购物品类，购物清单，进货清单等。所有这些信息为人们的相关 研究提供了丰富的资源。下面列举两个在应用当中的例子： 数据仓库的设计与构造：由于商品的数据种类十分丰富