（应用数学专业论文）基于自适应遗传算法的椭圆聚类方法研究.pdf

中北大学学位论文 基于自适应遗传算法的椭圆聚类方法研究 摘要 聚类分析，是指用数学的方法研究和处理给定对象的分类，它是多元统计分析的一 种，也是非监督模式识别的一个重要分支。它把一个没有类别标记的样本集按某种准则 划分成若干个子集，使相似的样本尽可能归为一类，而不相似的样本尽量划分到不同的 类中。 遗传算法起源于对生物系统所进行的计算机模拟研究。它是现代优化技术的一种， 具有全局的，并行高效的优化性能，鲁棒性、通用性强，无需问题特殊信息等优点。其 内容涉及数学、物理学、生物学和计算机科学等方面，为解决复杂问题提供了新的思路 和手段。 本文将遗传算法应用于对聚类目标函数的优化问题。针对椭圆状数据应用自适应遗 传算法，避免了用单纯聚类方法容易陷入局部极小值的问题。实验结果表明，这种新算 法具有较好的鲁棒性。本文共分四章，主要内容如下： 第一章为绪论，阐述了聚类分析研究的基本问题，以及遗传算法在优化聚类目标函 数问题时的必然性和合理性。 第二章回顾了聚类算法的发展历程，重点介绍和推导了基于目标函数的模糊c 一均值 算法( f c m ) ，并分析了传统聚类算法各自的优缺点。最后，运用f c m 算法处理了与基 金相关的数据，验证了该算法的有效性。 第三章主要分析了模糊椭圆聚类算法( f c e ) 的缺点，以及产生这些缺点的原因所 在，即f c e 在初值确定和基于迭代法的交替寻优策略上过度依赖f c m 算法，这必然导 致f c e 算法在实践中往往得不到令人满意的聚类效果。基于此，我们将f c e 算法与遗 传算法巧妙地结合起来，提出了一种新算法一模糊自适应椭圆算法( a g a f c e ) 。数值 试验表明，文中所提出的新算法具有较好的抗噪性，并且在优化过程中避免了传统算法 易陷入局部极小值的缺点。从而证明了该方法的有效性。 最后一章是结论部分。总结了本研究的贡献，并简要叙述了以后的研究前景。 关键词：f c m 算法，自适应遗传算法，f c e 聚类算法，a g a f c e 聚类方法 中北大学学位论文 s t u d y o f e l l i p t i cr i n g - - s h a p e dc l a s t e r i n gb a s e d o n a d a p t i v eg e n e t i ca l g o r i t h m a b s t r a c t c l u s t e r i n ga n a l y s i s ，w h i c hi s o n et y p eo fm u l t i v a r i a b l es t a t i s i ca n a l y s i sa n da n s i g n i f i c a n tb r a n c ho fu n s u p e r v i s e dp a t t e r nr e c o g n i t i o n ，i sd e f i n e da st h es t u d ya n dp r o c e s s i n g o ft h ec h a r a c t e r i z a t i o no fag i v e ns e to fd a t aw i t hm a t h e m a t i ca p p r o a c h a c c o r d i n gt oc e r t a i n c r i t e r i o n ，t h i st e c h n i q u ep a r t i t i o n sas a m p l ec l u s t e rw i t h o u tg r o u pm a r k e di n t os o m eg r o u p s ， s ot h a ts i m i l a rs a m p l e sa r ea s s i g n e dt oo n eg r o u pa sp o s s i b l ea sm u c h ，w h i l ed i s s i m i l a rt o d i f f e r e n to n e s g e n e t i ca l g o r i t h m ( g a ) d e r i v e df r o mt h ec o m p u t e rs i m u l a t e ds t u d yo fb i o s y s t e m ，w h i c h i so n ek i n do fc o n t e m p o r a r yo p t i m i z a t i o nt e c h n i q u e s ，a n df e a t u r e sf u n c t i o n ss u c ha st h e o v e r a l la n de f f e c t i v ep a r a l l e lo p t i m i z a t i o n ，h i 曲r o b u s t n e s sa n dg e n e r a l i t y , a n dn od e m a n df o r s p e c i f i ci n f o r m a t i o no fp r o b l e m s ，o re l s e d i s c i p l i n e sl i k em a t h r n e t i c s ，p h y s i c s ，b i o l o g ya n d c o m p u t e rs c i e n c ea n de t c a r ea l le m b o d i e di nt h ea l g o r i t h m ，w h i c hs h e d sn e wl i g h to nt h e s o l u t i o no fc o m p l i c a t e dp r o b l e m s i nt h ep r e s e n ts t u d y , t h eg e n e t i ca l g o r i t h mi sc r e a t i v e l ye m p l o y e dt ot h eo p t i m i z a t i o no f c l u s t e r i n go b j e c t i v ef u n c t i o n t h ea p p l i c a t i o no fa d a p t i v eg e n e t i ca l g o r i t h m ( a g a ) t ot h e d e t e c t i o no f e l l i p t i cr i n g - s h a p e dc l u s t e rs u c c e s s f u l l yp r e s e n t sc o n v e r g e n c ei n t ol o c a lm i n i m a , w h i c hm i g h tr e s u l tf r o mt h et r a d i t i o n a ls i m p l ec l u s t e r i n gm e t h o d t h es t u d yr e s u l tp r o v e st h a t t h en e w l yc o n s t r u c t e da l g o r i t h mi sv e r yr o b u s t t h ed i s s e r t a t i o ni sd i v i d e di n t of o u rc h a p t e r s ，w i t hc o n t e n t sa sf o l l o w s ： c h a p t e r1 i st h ei n t r o d u c t i o n ，w h i c hi n t r o d u c e st h ef u n d a m e n t a li s s u e so fc l u s t e ra n a l y s i s a n dt h en e c e s s i t ya n dr a t i o n a l i t yo ft h ea p p l i c a t i o no fg at oc l u s t e r i n go b j e c t i v ef u n c t i o n o p t i m i z a t i o na sw e l l c h a p t e r2l o o k sb a c ko nt h ed e v e l o p m e n t a lc o u r s eo fc l u s t e r i n ga l g o r i t h m ，w h i c hm a i n l y c e n t e r so nt h ei n t r o d u c t i o na n dd e r i v a t i o no ft h ef u z z yc m e a n sa l g o r i t h m ( f c m ) a n d d i s s c u s s e sr e s p e c t i v e l yt h es t r o n ga n dw e a kp o i n t so ft h et r a d i t i o n a lc l u s t e r i n ga l g r o r i t h r n s i n 中北大学学位论文 t h ee n d ，t h ef c m a l g o r i t h mi se m p l o y e dt op r o c e s ss o m ed a t ao ff u n d s ，j u s ti no r d e rt ot e s t t h ev a l i d i t yo ft h ea l g o r i t h m c h a p t e r3 f o c u s e so na n a l y s i so ft h ed e f e c t so ft h ef u z z yc - e l l i p s o i d a ls h e l l s a l g o r i t h m ( f c e ) a n dt h ec a u s ef o rt h e s ed e f e c t s ，t h a ti s ，t h ef c ea l g o r i t h mr e l i e se x c e s s i v e l l y o nt h ef c m a l g o r i t h mf o rt h ed e f i n i t i o no ft h ei n i t i a lv a l u ea n dt h ei t e r a t i v em e t h o dr o o t e d a l t e r n a t i n go p t i m i z i n gs t r a t e g y , w h i c hi n e v i t a b l yl e a d st ot h ed i s s a t i s i f a c t o r yp a r t i t i o nr e s u l t s f o rt h ef c ea l g o r i t h mi nu s e t h e r e f o r e ，w ec r e a t i v e l yc o m b i n et h ef c ea n dg aa l g o r i t h m s ， a n dp r o p o s et h e a d a p t i v e g e n e t i c a l g o r i t h m - - - f u z z yc - e l l i p s o i d a l s h e l la l g o r i t h m ( a g a f c e ) t h en e wa l g o r i t h mi st e s t e do ns e v e r a le x a m p l e s ，w h i c hs h o wt h a tt h ea f c ea l g o r i t h m p r o p o s e dt ob er o b u s ti nt h ep r e s e n c eo fn o i s ei nt h ed a t a t h ea l g o r i t h ma l s op r e v e n t st h e w e a k n e s so fl o c a lm i n i m ac a u s e db yt h et r a d i t i o n a la l g o r i t h mi nt h eo p t i m i z a t i o ns c h e m e t h et e s t n gr e s u l t ss h o wt h es t r o n ge f f i c t i v e n e s so ft h ea l g o r i t h m t h el a s t c h a p t e rc o n c l u d e s t h ew h o l ed i s s e r t a t i o n t h ea u t h o rc o n c i s e l yl i s t st h e c o n t r o b u t i o no ft h ep r e s e n tr e s e a r c ha n ds u g g e s t st h ef o l l o w i n gr e s e a r c hp r o s p e c t i v e k e y w o r d s ：f c ma l g o r i t h m ；a d a p t i v eg e n e t i ca l g o r i t h m ；f c ea l g o r i t h m ；a g a f c e a l g o r i t h m 原创性声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：堡是煎日期： 塑z ：生：! 关于学位论文使用权的说明 本人完全了解中北大学有关保管、使用学位论文的规定，其中包括： 学校有权保管、并向有关部门送交学位论文的原件与复印件：学校可 以采用影印、缩印或其它复制手段复制并保存学位论文；学校可允许学 位论文被查阅或借阅；学校可以学术交流为目的，复制赠送和交换学位 论文；学校可以公布学位论文的全部或部分内容( 保密学位论文在解密 后遵守此规定) 。 签名仔鼬无 导师签名：垄型麴 日期：塑丕兰：! ： 中北大学学位论文 1 1 研究背景和意义 第一章绪论 数据库技术的迅速发展以及数据库管理系统的广泛应用，使得人们积累了越来越多 的数据。巨量的数据背后蕴涵着丰富的知识，目前的数据库技术虽然可以高效地实现数 据的查询，统计等功能，却无法发现数据中存在的关系和规则，无法根据现有的数据准 确预测未来的发展趋势。也就是说，数据库中存在着大量的数据，却缺乏挖掘数据背后 隐藏知识的手段。 传统的统计学在研究此类问题时，往往先建立了模型，再利用模型对抽样所得数据 做出某些推断。然而这种传统统计方法在对大规模数据进行处理时占用时间太长，无法 满足实际使用中快捷省时的要求。在此背景下，数据库知识发现及其核心技术数据 挖掘便应运而生了。数据挖掘借用成熟的数据库技术并结合人工智能，机器学习等可以 很好地解决这个问题。另外，传统的统计方法通常处理的多是一维数据，而对于现在需 要处理的高维数据，数据挖掘就有着传统的统计方法不可比拟的优势。 数据挖掘是知识发现过程中的一个特定环节，也是其最为核心的部分，它是从大量 不完全的、有噪声的、模糊和随机的实际数据中，提取出隐含在其中的、人们事先不知 道但又是潜在有用的信息和知识的过程。数据挖掘的功能在于指定数据挖掘任务中要找 的知识模式类型，其任务一般分为描述与预测两类。描述性数据挖掘任务以简洁概要的 方式描述数据，并提供数据的一般特征；预测性挖掘任务是对当前数据进行分析，建立 数据模型，并试图预测新数据的行为【i 一钉。 近十多年来，聚类分析作为数据挖掘的主要方法之一，越来越引起人们的关注。 聚类是一种非监督模式识别过程，它把一个没有类别标记的样本集按某种准则划分成若 干个子集( 类) ，使相似的样本尽可能归为一类，而不相似的样本尽量划分到不同的类 中。也就是说，形成聚类之后，同一个类中的对象之间具有较大的相似性，而不同类中 的对象具有较大的相异性。 聚类分析的输入是一组没有类别标记的记录，而且事先也不知道要分成几类，它通 过分析数据，依据一定的分类准则，合理划分记录集合，从而确定每个记录所属的类别。 中北大学学位论文 不同的聚类算法中，用于描述相似性的函数也有所不同，有的采用欧氏距离或马氏距离， 有的采用向量夹角的余弦，也有的采用其他的度量方法。聚类分析的输出是数据集的分 类结果，即各个类( 或簇) 对应的区域。聚类分析的一个附加的结果是对每个类的特征进 行综合描述，这种结果对于更进一步深入分析数据集的特性是尤其重要的。聚类方法尤 其适合用来探讨样本间的相互关联系，从而对一个样本结构做一个初步的评价。 聚类分析是进行数据分析的一个基本方法，在机器学习、数据挖掘、模式识别、生 物学、统计学和化学等许多领域都得到了广泛的研究和应用【5 1 2 1 。聚类分析可以作为一 个独立的数据挖掘工具，用来获得对数据分布情况的了解，也可以作为其他数据挖掘算 法的预处理步骤。 1 2 聚类技术研究的发展概况 “人以群分，物以类聚”，聚类是一个古老的问题，它伴随着人类社会的产生和发 展而不断深化，人类要认识世界必须区别不同的事物并认识事物间的相似性。 将具体或抽象对象的集合分成由类似对象组成的多个类的过程被称为聚类 ( c l u s t e r i n g ) d , 1 3 。由聚类生成的簇是一组数据对象的集合，这些对象与同一簇的对象彼 此相似，与其它簇中的对象彼此相异。在许多应用中，可以将一个簇中的数据对象作为 一个整体来对待。聚类就是按照一定的要求和规律对事物进行区分和分类，在这一过程 中没有任何关于分类的先验知识，没有教师指导，仅靠事物间的相似性作为类属划分的 准则，因此属于无监督分类的范畴。聚类分析则是指用数学的方法研究和处理给定对象 的分类。 传统的聚类分析数据是一种硬划分，它把每个待辨识的对象严格地划分到某类中， 具有非此即彼的性质，因此这种类别划分的界限是分明的。而实际上大多数对象并没有 严格的属性，它们在性态和类属方面存在着中介性，具有亦此亦彼的性质，因此适合进 行软划分。z e d e h 提出的模糊集理论 1 4 - 1 5 1 为软划分提供了有力的分析工具，人们开始用 模糊的方法来处理聚类问题，并称之为模糊聚类分析。由于模糊聚类得到样本属于各个 类别的不确定性程度，表达了样本类属的中介性，即建立起了样本对于类别的不确定性 ； 描述，所以更能客观地反映现实世界，从而成为聚类分析研究的主流。 2 中北大学学位论文 自从z a d e h 在1 9 6 5 年提出的模糊集理论问世后，模糊集理论率先在模式识别领域 得到应用。由于模式识别中固有的模糊性，所以将模糊集引入模式识别获得了巨大的成 功。以模糊集为基础处理聚类问题是由b e l l m a n ，k a l a b a 和z a d e h 于1 9 6 6 年首先提出 的。第一个系统地表述和研究模糊聚类的是著名学者r u s i p i n i t l 6 - 1 7 。1 9 6 9 年，r u s p i n i 定义了数据集的模糊划分概念。与此同时，z a d e h ，t a m u r a 等人提出了基于相似关系和 模糊关系的聚类方法【1 8 - 1 9 1 ，这类方法分为聚集法和分裂法，目前已提出了许多不同技巧 来应用这一思想。从七十年代到八十年代，人们对模糊关系矩阵及其传递闭包等问题进 行大量的研究。到九十年代，尽管还有人做这方面的研究，但研究热潮已逐渐退却。此 外，人们也试图同图论的方法研究模糊聚类，如1 9 7 4 年d u n n 2 0 】利用图论分析t a m u r a 等人提出的聚类方法；1 9 9 2 年丁斌f 2 1 】提出动态模糊图最大树聚类法；1 9 9 3 年，z h e n g g u w u 和r l e a h y l 2 2 1 提出最优图论方式的聚类方法。在将硬聚类方法推广到模糊聚类方法 情形方面，人们也做了许多工作，如将硬聚类中常用的k 近邻法推广到模糊聚类。1 9 8 5 年，t a og u 和b u b u i s s i o n 2 3 1 提出松弛k 最近邻法，同年k i l l e r t 2 4 】等人提出了一种模糊 k 最近邻法，1 9 9 1 年b e r e a u 和b u b u i s s i o n 提出了另一种形式的模糊k 一最近邻法。人们 也提出了其它一些模糊聚类方法，如1 9 8 5 年e s o g b u e t 2 5 】提出了动力学模糊聚类方法， 1 9 8 8 年m a n t a r a sv a l e r d e 2 6 】基于难以辨别关系提出了几种模糊聚类方法。 上面我们叙述了一些模糊聚类方法，由于各种各样的原因，这些方法的应用不是很 广泛。实际中受到普遍欢迎的方法是基于目标函数的模糊聚类方法。基于目标函数的模 糊聚类方法首先是由r u s p i n i 1 6 - 1 7 1 提出的，但真正有效的方法是由d u n n 给出的。1 9 7 4 年d u n n 将硬聚类c 均值算法推广到模糊情形【2 7 之8 1 ，同年，b e z d e k 2 9 1 将d u m a 的方法一 般化，建立了模糊c 均值算法理论，1 9 8 0 年b e z d e k 证明了模糊c 均值聚类算法的收 敛性并证明了模糊c 均值聚类算法与硬c 均值聚类算法的关系【3 们。 从此，基于目标函数的模糊聚类算法蓬勃发展起来。目前已形成了庞大的体系。人 们从不同的角度对基于目标函数的模糊聚类算法进行了研究。在所有的聚类方法中，应 用最普遍研究最多的就是著名的模糊c 一均值方法( f c m ) 以优化目标函数获得隶属度 参数和聚类中心，计算使用交替迭代方法。模糊c 均值类型算法最早是从硬聚类目标 函数的优化中导出的。为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造 了带约束的非线性规划函数，从此类内平方误差和( w g s s ，w i t h i n g r o u p ss u mo f 3 中北大学学位论文 s q u a r e de 1 t o r ) 以成为聚类目标函数的普遍形式。为极小化该目标函数而采取的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 g d a t a a n a l y s i st e c h n i q u e a ) 算法f 3 0 l 。模糊划分概念提出后，d u n n t 3 1 】首先把w g s s 函数以 扩展到了，类内加权平均误差和函数，后来b e z d e k 3 2 】又引入一个参数m ，把：推广到 一个目标函数的无限族，并给出了交替优化( a o ，a l t e r n a t i v eo p t i m i z a t i o n ) 算法，即 为人们所熟知的f c m 算法。从此，奠定了f c m 算法在模糊聚类中的地位。 。 国际和国内的学者都对聚类分析的研究非常重视，i e e e 的汇刊中模式分析与机 器智能( p a m i ，p a t t e r na n a l y s i sa n dm a c h i n ei n t e l l i g e n c e ) 、系统、入和控制( s m c ， s y s t e m s ，m a n ，a n dc y b e m e t i c s ) 、模糊系统( f s ，f u z z ys y s t e m s ) 、神经网络( n n ， n e u r a ln e t w o r k s ) 、信号处理( s p ，s i g n a lp r o c e s s i n g ) 等杂志中几乎每期都有讨论聚 类分析问题的文章。从1 9 9 2 年开始的由i e e e 和神经网络理事会共同主办的f u z z i e e e 会议，每两年召开一次，每次至少有3 到4 个专题讨论聚类和模糊聚类分析的最新研究 进展和发展现状。另外，我国作为模糊数学研究的大国，不仅在基础来理论研究上取得 了丰硕的成果，而且在模糊聚类等的应用研究上亦令世人瞩目，比如基于模糊聚类的天 气预报、矿藏识别和医学诊断等等。 那么对于f c m 算法来说，它是目前比较流行的一种模糊聚类算法，究其原因大致有 以下几个方面，首先，模糊c 一均值泛函m 乃是传统的硬c 均值泛函t 的自然推广，我 们知道，i 是一个应用十分广泛的聚类准则，对其在理论上的研究已经相当完善，这就 为m 的研究提供了良好的条件。其次，从数学上看，册与尺5 的希尔伯特空问结构( 正 交投影和均方逼近理论) 有密切的关系，因此m 比其他泛函有更深厚的数学基础。最 后，f c m 算法不仅在许多领域获得了非常成功的应用，而且以该算法为基础，人们又提 出基于其他原型的模糊聚类算法，形成了一大批f c m 类型的算法、比如模糊c 线( f c l ) 、 模糊c 面( f c p ) 、模糊c 壳( f c s ) 等聚类算法，分别实现了对呈线状、超平面状以及 “薄壳 状结构模式子集( 或聚类) 的检测。那么为了了解这方面的研究情况，第三章 从模糊目标函数的演化、算法的实现途径、有效性度量方式等三方面综述这类方法的研 4 中北大学学位论文 究进展以及现状。 10 3 本文研究的主要内容 本文以模糊信息处理技术为主线，应用遗传算法处理二维壳状模型，对椭圆形状的 聚类模型进行了深入的研究，提出了一种基于自适应遗传算法的椭圆聚类算法( a f c e ) 本课题主要做了以下几方面的工作： 1 ) 在阅读大量文献的基础上，研究了聚类技术的基本思想，原理及其实现的过程；研 究了聚类分析的各种常见的算法以及它们的应用和面临的挑战；重点研究了遗传算法的 聚类原理和参数的选择。 2 ) 将遗传算法应用于椭圆形状酌聚类中，建立综合聚类分析模型并通过大量的实验对 模型进行确认、检验以及评估和优化。 3 ) 分析研究了影响遗传算法聚类模型质量的关键因素并针对这些因素提出相应的改进 方法，同时将其应用于图象的边缘检测，验证了算法的有效性。 1 4 本论文的内容安排 本文共分四章。第一章综述了本文的主要内容以及课题的主要意义，第二章对聚类 分析的基本原理和常见几种聚类分析算法进行了比较，第三章重点用遗传算法对椭圆状 聚类的目标函数进行优化，提出改进的算法，第四章总结了课题工作中得到的主要成果， 并指出课题的研究展望。 5 中北大学学位论文 第二章聚类分析技术概述 2 1 聚类分析 2 1 1 聚类分析的概念 聚类，就是按照一定的要求和规律对事物进行区分和分类的过程在这一过程中， 没有任何关于类分的先验知识，也没有教师指导，仅靠事物间的相似性作为类属划分的 i 准则，因此属于无监督类分的范畴 聚类分析，是指用数学的方法研究和处理给定对象的分类，它是多元统计分析的一 种，也是非监督模式识别的一个重要分支它把一个没有类别标记的样本集按某种准则 划分成若干个子集( 类) ，使相似的样本尽可能归为一类，而不相似的样本尽量划分到 不同的类中。 传统的聚类分析数据是一种硬划分，它把每个待辨识的对象严格地划分到某类中， 具有非此即彼的性质，因此这种类别划分的界限是分明的。而实际上大多数对象并没有 严格的属性，它们在性态和类属方面存在着中介性，具有亦此亦彼的性质，因此适合进 行软划分。模糊集理论的提出为这种软划分提供了有力的分析工具，人们开始用模糊的 方法来处理聚类问题，并称之为模糊聚类分析。由于模糊聚类得到了样本属于各个类别 的不确定性程度，表达了样本类属的中介性，即建立起了样本对于类别的不确定性描述， 更能客观地反映现实世界，从而成为聚类分析研究的主流【3 7 1 。 2 1 2 聚类分析的数学模型 从数学的角度来刻画聚类分析问题，可以得到如下的数学模型。 设x = 瓴，x 2 ， 是待聚类分析的对象的全体( 称为论域) ，x 中的每个对象( 称为 样本) 诈( 后= 1 ，2 ，疗) 常用有限个参数值来刻画，每个参数值刻画吒的某个特征于是对 象砟就伴随着一个向量尸( ) = ( 晚。，：，) ，其中x k j ( j = l ，2 ，s ) 是的第个特征 ： 上的赋值， 尸( 以) 称为而的特征向量或模式矢量。 6 中北大学学位论文 聚类分析就是分析论域x 中的，2 个样本所对应的模式矢量间的相似性，按照各样本 间的亲疏关系把五，x 2 ，屯划分成多个不相交的子集五，五，置，并要求满足下列条 件： 五u 置u u 以= x i 置厂、t = a ， 1 f j _ c ( 2 1 ) 样本( 1 七刀) 对子集( 类) 置( 1 f c ) 的隶属关系可用隶属函数表示为 “置c 稚，= 甜琅= 三羔三乏 其中，隶属函数必须满足条件渡m 们。 ( 2 2 ) 也就是说，要求每一个样本能且只能隶属于 某一类，同时要求每个子集；( 类) 都是非空的。因t l l ，通常称这样的聚类分析为硬划分 ( h a r dp a r t i t i o n 或c r i s pp a r t i t i o d , ) 。 = u er c l o ，t 粤：薏i = l 乩v 加 窆k = l 州蛩 在模糊划分( f u z z y p a r t i t i o n ) 中，样本集被划分成c 个模糊子集墨，丘，毫， 而且样本的隶属函数从0 , 1 - 值扩展到【o ，1 区间，满足条件 蛑c = u r l u , k 】，v i ，后； i * = 1 ，v k ；0 k a ( d ，只) ，置= 厂_ 1 ( 忌) ，七k ，于是，厂就 称为x 的一个( 硬) 划分，当且仅当： 黑工= 彳， ( 2 3 ) v i ，j k ：f k 五n x ，= 囝， ( 2 4 ) v i k ：囝z 彳， ( 2 5 ) 如果用隶属函数= ( 吒) 表示样本稚( 1 k 聍) 对子集( 类) 置( 1 z c ) 的隶属关 系，则硬c 划分中，为子集五的特征函数，显然有 o ，1 。这样x 的硬c 划分也 可以用隶属函数表示，即用c 个子集的特征函数值构成的矩阵u = 】“。来表示。矩阵u 中的第行亍为第f 个子集的特征函数，而矩阵u 中的第k 列为样本垓相对于c 个子集的隶 属函数。于是x 的硬c 划分空间为 l m 昭= u 尺“”i o ，1 ) ，v i ，后；= 1 ，v k ；o 刀，v i ( 2 6 ) l，= lk 摹lj r u s p i n i u 6 1 利用模糊集理论把h c m 模型中的隶属度函数从 o ，l 二值扩展到闭区 间 0 ，l 】中，从而把原有的硬c 一划分概念推广到模糊c 一划分空问 9 中北大学学位论文 = u r lu , k “o ，l 】，v i ，七；= l ，v k ；0 0 ， 初始化聚类原型模式p ( m ，设置迭代计数器b = 0 ； 用下述公式计算或更新划分矩阵u ( 6 ) ： 1 3 中北大学学位论文 牡亿籍刚秽啦，一幺，玎 其中，彬= d ( 们，x k ) ，i = l ，2 ，c ，k = l ，2 ，刀。 用下述公式更新聚类辱型p p 圳= ( p r ，p “，反d ) 羔( 甜) ”赡 “k 骑乒1 2 ，v 用一个矩阵范数1 1 1 l 来比较尸6 与尸川，若胪6 一尸川l l 0 ， 初始化聚类原型模式尸们，设置迭代计数器b = 0 ； 用下述公式计算或更新模糊划分矩阵u ( 6 ) ： 对于v f ，k ，如果j 礤 0 ，则有罐= 蕊2 7 如果j f ，使得秽= o ，则有“= l ，且对厂，材笋= o 1 4 中北大学学位论文 用下述公式更新聚类原型p 6 + 1 ) - ( 矗n ，孝“，+ 1 ) 羔( ，) ”矗 矗61。1：=前=12，(?( 甜) ” 用一个矩阵范数 | 1 来比较尸6 与p 6 + 1 ，若i l 尸扪一p i f - 0 ，i = 1 ，1 8 8 4 ，歹= 1 ，4 4i 册 1 8 其中，吒= 忙一马0 ： 表示第i 个数据点到第j 类( 中心) 的距离；心 表示点属于 第j 类的隶属度；岛称为聚类厦型( p r o t o t y p e ) ；m 为加权指数，这里取为2 。 表2 1 各公司两种基金净收益均值 序公司名股票型基金配置型基序公司名称股票型基配置型基金 号称 净收益均值金净收益 号金净收益净收益均值 均值均值 1 嘉实 1 2 9 1 51 0 0 0 51 0 上投摩根 1 1 2 8 5 0 5 9 6 8 2 南方 1 0 4 3 41 2 5 3 81 1 泰达荷银 1 6 5 5 70 。5 7 8 5 3 华夏 1 1 7 7 70 6 8 9 01 2 大成 1 3 5 5 30 3 0 5 0 4 易方达1 4 3 1 91 3 2 1 01 3 景顺长城 1 3 8 5 2 1 3 4 8 3 5 富国 1 0 4 3 51 0 3 2 41 4 华宝兴业 1 4 4 6 21 0 2 1 0 6博时1 3 9 7 40 5 3 6 51 5国泰1 3 9 4 4 0 5 4 8 0 7 广发 1 4 5 0 31 4 3 8 01 6 海富通 1 5 6 1 7o 7 1 6 0 8 华安1 2 6 8 01 5 2 6 0 1 7 招商 1 1 6 1 61 0 9 6 3 9 银华1 1 2 8 51 2 6 9 118融通1 6 6 9 4 1 3 5 5 9 2 3 1 算法实现 初始化：给定聚类类别数c ，( 2 c 1 8 ) ，这里取c = 4 。设定迭代停止阈值g ，初始化 聚类原型模式p 0 、，设置迭代计数器6 = 0 。 1 6 中北大学学位论文 步骤一：计算或更新划分矩阵们。 一“砌一矿咖删= 胁爿 仁2 。， 如果存在，厂使得z ，6 = 0 ，则有心6 = l ，r s f j j ，鳓6 = 0 步骤二：更新聚类原型模式矩阵p 6 + 1 1 8 如“1 r 薯 所p + 1 = 号广一 ( 2 2 1 ) 鳓p “) ” j = i 步骤三：如果8 p 6 一p b + j8 1 ，并且 d 2 ：d x cj r ，( x ，( v 0v 1 ，机吁( 卜v 。i l + l l x v 1 i i - ，) 2 如果所有基于概率的可能聚类划分x 专，( k ) 被最小化，其中k = 向，局，恕) e ， ， ： 由映射厂：x 专f ( k ) 给定隶属度厂( _ ) ( t ) = ，t = ( 口，谚，；) 和z = o ，1 ，则有： 窆( ) m ( 0 _ 一p 0 0 0 一v ：1 1 ) = 兰矿二一，v i ，1 f 七 ( 3 2 ) ( 尸 i 一和”卜禹 = i l l ，f 1 ，：= 旦_ = k ( 吻) 朋 证明：最小化目标函数，即有拉格朗日乘数法，有 。2 考= 之鼢卜刑 解得 ( ) ”( 8 _ 一妒0 + 9 _ - 一1 1 ) ，；= 兰7 一，v i ，1 f 尼 ( 吻) 册 j = l 隅扯嵩= 乏扣州) + ( 1 l 州一商， 2 0 ( 3 3 ) 中北大学学位论文 锯，一扣”( 酬_ 一州训网x j - v ；) 解得= 竺- 峻1 ( ) ” 3 1 2 椭圆状数据的模糊聚类算法f c e 模糊c - 椭圆聚类算法，4 6 1 ( f ；i c e ) 是对目标函数进行优化，即聚类原型变量是目标 函数的最优解。和传统表示椭圆1 耆 ：同的是，g a t h 和h o o r y 采用三个简化变量来表示聚类 原型，即两个焦点和0 n ，以及半径= 2 q ( q 表示椭圆的长半轴) 。设球壳状分布 的数据集x = 五，恐，吒 中含有c 个椭圆状的类， 它们的聚类原型为 ( t 们，0 ，乃) ，i = l ，2 ，c 。 u 是隶属度矩阵。算法的过程是对下面目标函数进行优化的过 程： ( u ，矿们，y n ，r ) = 甜孑喏，所( 1 ，+ ) ( 3 4 ) 9 = 1 其中岛= 0 一l i + 0 t 一0 2 | l _ i = 弼u + d 0 ( 2 ) - - i ( 3 5 ) 。，：薹! ：! 二 至：三墨三茎三兰蔓塑，v u ，c 。3 6 ) ( ) 埘 t ：，：薹! ：! ： 至：三墨三蔓三茎星；塑，v 瓦，；c 。3 7 ， ( ) 册 毋和d o ( 2 是第个模式到两个焦点的欧氏距离。对于一个位于椭圆外的模型，这个 距离是正值，位于椭圆中的则取负值，而若该模型恰好位于椭圆上，则该值取为0 。 f c e 算法可描述如下： 1 ) 初始化：确定类别数c ，( 2 c ，2 ) ，模糊指数朋，迭代阈值s ，设置送代计数器 2 1 中北大学学位论文 2 ) 利用下式确定椭圆半径，： ( ) ”( 吃1 + 吃2 ) ( ) ” j = l ，v f ，1 i c( 3 8 ) 其中m yi ) 矛j ld , j ( 2 ) 分别是第个模式到第f 类的两个焦点的欧氏距离。蚴是第个模式 到第i 类的隶属度。 3 ) 利用下面式子更新焦点： 0 1 = h ( ) 历 j = l ，v i ，1 i c 型二篷盟受m 胚 ( ) 饼 4 ) 更新隶属度矩阵u ： 时唣万1 m 崩娜硝娜绝 5 ) 若一甜f + 1 0 岛 ( 3 1 2