（运筹学与控制论专业论文）知识驱动的模糊聚类算法研究.pdf

中文摘要 摘要 聚类分析算法是一种用来发现数据中存在模式的有效方法，在数据分析中被 广泛应用。在本文中，我们主要讨论了一种以领域知识作为辅助手段，并将其有 效集成到所研究模式识别问题的方法。 首先，本文提出了一种新的知识驱动的聚类算法贴近度一密切关系传播 算法。该算法利用我们所设计的知识判据和由用户给出的样本问的贴近度信息来 对由数据所产生的相似度矩阵进行修正，从而将用户的知识引入聚类过程，使算 法对于问题的处理变得更加灵活。 其次，为了解决上述算法无法得到用户所需聚类数日和大样本数据集合聚类 的问题，本文将模糊c 均值算法与密切关系传播算法相结合，设计出。一种“大样 本数据聚类算法”。该算法分为两个阶段，在第一阶段，我们采用了一种分布式 计算策略，先将原始数据集合划分成若干个数据子集，并使用密切关系传播算法 分别对每个数据子集样本进行聚类，得到数据的聚类中心。在算法的第二阶段， 我们将由第一阶段产生聚类中心视为一个数据集合，利用模糊c 均值算法得到所 期望类数的聚类，并认为每个聚类中心所属的类与在第一阶段隶属于其的数据所 属的类相同。同时，为了考察划分的可靠性，在此阶段，我们还引入了模糊熵量 度来辅助完成聚类过程。 为了考察两种算法的有效性，我们对其进行了数值实验。对于贴近度一密切 关系传播算法，我们分别考察了其在含有少量样本的人工数据集，i r i s 数据集和 y a l e 人脸图像数据集上的聚类效果。对于大样本数据聚类算法，我们考察了其对 i r i s 数据集和s h u t t l e 数据集的聚类效果。实验结果表明，这两种算法策略切实可行， 并且在测试数据集上均取得了很好的聚类结果。 关键词：模糊聚类；贴近度知识；模糊c 均值算法；密切关系传播算法；大样本 数据聚类 英文摘要 a b s t r a c t c l u s t e r i n gi sab r o a d l ya c c e p t e ds y n o n y mo ff u n d a m e n t a le n d e a v o r sa i m e da t f i n d i n gp a t t e r n si nd a t a i nt h i ss t u d y ，w ed i s c u s sa ni s s u eo fe x p l o i t i n gs o m ea u x i l i a r y h i n t sb e i n ga v a i l a b l ea sap a r to fd o m a i nk n o w l e d g ea n de f f e c t i v e l yi n c o r p o r a t i n gt h e m i n t ot h ep a t t e mr e c o g n i t i o np r o b l e ma th a n d f i r s to fa l l ，an e wk n o w l e d g e - d r i v e n c l u s t e r i n ga l g o r i t h m n a m e dp r o x i m i t y a f f i n i t yp r o p a g a t i o n ( p - a p ) i si n t r o d u c e d i tm a k e su s eo ft h ep r e d e f i n e dc r i t e r i o na n d t h ep r o x i m i t yh i n t sg i v e nb yu s e r st om o d i f yt h es i m i l a r i t ym a t r i x t h i sk i n do fs t r a t e g y m a k e st h ec l u s t e r i n gp r o c e s sm o r ef l e x i b l e t os o m es p e c i f i cp r o b l e m sb e c a u s ei t i n v o l v e st h ea n a l y z e r sk n o w l e d g e s e c o n d l y ，ak i n do fl a r g es a m p l ec l u s t e r i n ga l g o r i t h m ( l s c a ) i sp r o p o s e df o r d e a l i n gw i t ht h ep r o b l e mt h a ti ti sh a r dt og e tt h ep r e s c r i b e dn u m b e ro fc l u s t e r st h r o u g h t h ea b o v ea l g o r i t h ma n dt h ep r o b l e mo fc l u s t e r i n gal a r g es a m p l ed a t as e t i tc a l lb e r e g a r d e da st h ec o m b i n a t i o no ff u z z yc - m e a n s ( f c m ) a n da f f i n i t yp r o p a g a t i o n ( a p ) t h e r ea r et w os t a g e si nt h i sa l g o r i t h m a tf i r s ts t a g e ，ad i s t r i b u t e dc o m p u t i n gs t r a t e g yi s c o n s t r u c t e db yd i v i d i n gt h eo r i g i n a ld a t as e ti n t os e v e r a ld a t as u b s e t s ，a n dt h e nt h e e x e m p l a r s ( c e n t r o i d s ) o fe a c hd a t as u b s e ta r ed i s c o v e r e dw i t ha f f i n i t yp r o p a g a t i o n a t s e c o n ds t a g eo ft h ea l g o r i t h m ，a l lt h ee x e m p l a r sd i s c o v e r e da tp e r v i o u ss t a g ea r et r e a t e d a st h ee l e m e m so fo n es i n g l es e t , a n df u z z yc - m e a n sc a nb ea p p l i e dt ot h e mt op r o d u c e s o m ec l u s t e r s ，w h o s en u m b e ri sp r e d e f m e db ya n a l y z e r a tt h a tm o m e n t ，t h es a m p l e s w h i c hb e l o n gt oa n ye x e m p l a ra tf i r s ts t a g ea r ea r r a n g e di n t ot h es a m ec l u s t e rt o g e t h e r w i t ht h e i re x e m p l a r a tt h i ss t a g e ，f u z z ye n t r o p ya sak i n do fa u x i l i a r yt o o li si n t r o d u c e d f o rm e a s u r et h er e l i a b i l i t yo ff u z z y p a r t i t i o n s o m ee x p e r i m e n t a ls t u d i e sa r er e s e a r c h e df o ri n v e s t i g a t i n gt h ee f f e c t i v e n e s so ft h e p r o p o s e da l g o r i t h m s f o rp r o x i m i t ya f f i n i t yp r o p a g a t i o n ，t h ea r t i f i c i a ld a t as e tw h i c h c o n t a i n saf e ws a m p l e s ，t h ei r i sd a t as e ta n dt h ey a l ef a c ed a t as e ta r ec l u s t e r e dw i t h p - a ps e p a r a t e l y f o rl a r g es a m p l ec l u s t e r i n ga l g o r i t h m ，t h ee x p e r i m e n t so nt h ei r i s d a t as e ta n dt h es h u t t l ed a t as e ta r es t u d i e d e x p e r i m e n t a lr e s u l t si n d i c a t et h a tb o t l lo f 英文摘要 a l g o r i t h m sa r ee a s ya n da d a p t a b l ef o re v a l u a t i o n ，a l s oh a v eg a i n e dag o o dc l u s t e r a n a l y s i se f f e c t k e yw o r d s ：f u z z yc l u s t e r i n g ；p r o x i m i t yh i n t s ；f u z z yc - m e a n s ( f c m ) ；a f f i n i t y p r o p a g a t i o n ( a p ) ；l a r g es a m p l ec l u s t e r i n g 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博硕上学位论文 = = 翅迟坚麴丝撞翅塞耋簋鎏硒宜：。除论文r f l 已经注 明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或 未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名：盘筠毛么 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有火部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密形( 请在以上方框内打“”) 论文作者签名：勰翩躲撕、 日期：训。年6 肜乡日 知识驱动的模糊聚类算法研究 引言 随着信息技术的发展，人类对数据的采集和存储能力都有了很大的提高，这 就使得数据呈爆炸式增长。而数据中所包含的信息可以反映出一个领域生产经营 活动的客观规律。凶此，无论对于任何行业，这些隐藏在数据中的信息都是一笔 无形的财富。于是，从数据中提取有用信息，进行辅助决策，进而提高劳动生产 率便成为各行业工作人员所追求的目标。 在这种社会需求下，数据分析方法得到了前所未有的发展。随着学术研究的 不断深入和相关技术的广泛应用，这种数据分析方法如今已经成为了一门独立的 学科，人们形象的称其为“数据挖掘”。数据挖掘是一门交叉学科，涉及到多个 学科技术的集成，包括数据库、统计学、机器学习、高性能计算、模式识别、神 经网络、数据可视化、信息检索、图像与信号处理和空间数据分析等技术。如今， 数据挖掘主要包含特征化，关联规则挖掘，分类和预测，聚类分析，孤立点分析 等技术。在应用方面，些较为成熟的方法已经广泛应用二j 二医疗、金融、商业、 电信业、互联网等各个领域，对社会的发展起到了巨大的推动作用【l 】。 聚类分析方法是数据挖掘算法中的一个重要组成部分，其用来发现数据中存 在的模式，是解决信号处理与数据模式识别问题的一个关键步骤。目前，已有的 聚类分析算法有很多，本文主要对模糊c 均值算法( f c m ) f 2 】和密切关系传播算法 ( a p ) 【3 1 两种聚类算法进行了研究。由b e z d e k 于1 9 8 1 年所提m 模糊c 均值算法是 一种较为经典的聚类算法，其采用z a d e h t 4 所提出的模糊集合思想，认为每一个样 本都属于所有的类，只不过隶属的程度不同。密切关系传播算法是一种近来被学 术界认为具有很高研究价值和发展潜力的聚类算法，它由加拿大学者b r e n d a a j f r e y 和d e l b e r td u e e k t 是出并发表在2 0 0 7 年2 月的( s c i e n c e ) ) 杂志上。其通过利 用数据样本间“r e s p o n s i b i l i t y ”与“a v a i l a b i l i t y ”两种消息的传递来找出聚类中心 和划分数据样本的类的归属。 模糊c 均值算法作为一种出现较早的日性能较好的聚类算法，无论在理论上还 是在应用卜都已经被研究人员进行了深入的研究，其算法的衍生版本也有很多。 引言 多年来，为了提高算法的性能或减少算法的缺陷，研究人员不断尝试对模糊c 均值 算法进行改进。为了使用户所给出的知识信息也能够参与到聚类分析中，使算法 过程由数据驱动变为知识驱动，加拿人学者w i t o l dp e d r y c z 5 刁1 设计了一种贴近度知 识判据，并很好的与模糊c 均值算法相结合，建：移了一种贴近度一模糊c 均值算法 ( p f c m ) 。其在聚类分析时不仪考虑到了数据本身的信息，还引入了用户所给 出的数据样本问的贴近度( p r o x i m i t y ) 信息，聚类过程在这两种信息的共同作用 下完成。这种方法使聚类这种无监督学习技术变为半监督学习技术，使算法对于 特定问题的处理更为灵活，也易于获得更好的聚类结果。 目前，聚类分析算法的应用研究非常活跃。如在生产领域，m g u s a i 等人【8 】将 聚类算法应用到农场特征的识别上；在医疗领域，g u ya n i t 等人【9 1 用聚类算法对心 脏声音进行分类；在生物医学领域，b r e n d a nj f r e y 等j k 3 】通过聚类分析算法对基囚 微阵列信息进行分析；在互联网领域，v l o i a 等人【5 】尝试用聚类分析算法对搜索引 擎技术进行改进等等。 与国外相比，国内对于聚类分析算法的研究起步较晚，尤其对于密切关系传 播算法和知识驱动的聚类算法研究还存在很大差距。因此，本文将着重于建立新 的知识驱动的聚类分析算法以及可用于海量数据聚类的聚类分析算法的研究工 作。 一2 一 知识驱动的模糊聚类算法研究 1 1 模糊数学理论 第1 章模糊数学及模糊熵理论 1 1 1 模糊数学简介 对模糊数学的讨论，最早可以追溯到1 9 2 3 年。2 0 世纪大哲学家罗素最初在他 的一篇名为含糊性的论文罩专l 、j 的论述了我们今人称之为“模糊性”的问题， 并明确指出：“认为模糊知识必定是靠不住的，这种看法是大错特错的。”尽管 罗素当时已经名声显赫，但这篇发表在南半球哲学杂志的文章并没有引起当时学 术界对模糊性或含糊性很大的兴趣。但是，这并不能说明这一类问题不重要，而 是因为2 0 世纪初期社会的发展，特别是科学技术的发展，还未对模糊性的研究有 所要求。 事实上，模糊性理论是随着电子计算机技术的发展而产生和发展起来的。电 子计算机这种精密机器的快速发展及其广泛应用，特别是在教育学，管理学等这 些人文学科上的应用，使人们逐渐认识到了以“精确性”为代表的经典数学的局 限性。例如，一个公司的门卫人员，通过长时间的观察，可以通过一些模糊印象 来判断进出门的是谁，是否是本公司的职员，可如果该公司想设计一个门禁系统 来管理人员的进出，以目前的计算机技术则会出现很大的问题，因为按照经典数 学的方法，若想该系统能够工作就要输入人的身高、体重、胖瘦、走路速度等大 量数据，而一旦这个人走的快了些，变得胖了些，该系统就会六亲不认了，同时 这也将耗费大量的资源。这显然不是人们所愿看到的。于是一批数学家和工程技 术人员就着眼于寻找和创造处理这类模糊性事物和模糊性问题的技术和方法。美 国自动控制论教授扎德( l a z a d e h ) 是这些人中的杰出代表。他在1 9 6 5 年发表的 题名为模糊集合的论文弥补了经典数学集合论的不足，而且其中有关模糊集 的概念奠定了模糊性理论的基础。这一理论由于在处理复杂系统特别是有人干预 的系统方面的简洁与有力，迅速的受到了广泛的罩视。4 0 多年来，这个领域从理 论到应用，从软技术到硬技术都取得了丰硕的成果，并且对些相关领域和复杂 系统的发展有着越来越大的影响【1 0 ，】。 第1 章模糊数学及模糊熵理论 1 1 2 模糊集合的定义 有一个问题是这样的，它问我们“什么样的人是秃头? ”。所有人都会认定 “有一根头发的人是秃头，有两根头发的人也是秃头”，那么由数学归纳法，假 设有k 根头发的人是秃头，按照经典的数学归纳法，则有k + l 根头发的人还是秃头， 那么我们便会得出结论：“所有人都是秃头”，这显然是十分荒谬的，这就是著 名的“秃头悖论”。分析这种推理产生谬误的原囚是不能很好的界定“秃头”与 “刁i 是秃头”的界限。的确，“秃头”与“非秃头”是两个有区别的概念，但这 种区别的产生是一个从量变到质变的过程，而经典数学的“非此即彼”的集合逻 辑则无法描述这种变化。“有一根，两根的头发的人是秃头，有一百万根头发的 人不是秃头”这是所有人都公认的，那么这两者之间的分界是多少根头发，则没 有人能说的清。类似的，“年老”，“漂亮”，“便宜”，“个予高”这些概念 都是无法用经典集合理论来界定的，而模糊数学理论为解决这类问题提供了有力 的工具。 经典集合论之所以无法处理这些问题是因为普通集合( 康托集合) 对应于二 值逻辑，表现为布尔代数。元素x 属于或不属于某一集合，清清楚楚，毫不含糊。 而在上面的问题下，“是”与“不是”、“属于 与“不属于”的界限并不是很 清楚，而是有一个边缘地带，有一个渐变过程。扎德教授正是基于此将普通集合 论的特征函数的取值范围由 o ，l 推广到闭区问 0 ，l 】，定义了模糊集合理论。下面我 们将介绍一些本文将会用到的模糊数学的简单概念。 定义1 1 【1 2 】论域x = “，而，) 上的模糊子集爿，是指对于任何x x 都有 一个数以( x ) 【0 ，1 】与之对应，即映射 以：x - - 【o ，l 】 x _ ( 工) 映射以称为a 的隶属函数，以( x ) 农示元素刊蓠于a 的程度，称为x 对a 的隶属度。 模糊子集由其隶属函数所确定。隶属函数是普通集合中特征函数的推广。 对于定义1 1 ，对于模糊集合a ，若。( x ) 仅取0 和l ，则彳就退化为普通集合。 知识驱动的模糊聚类算法研究 所以普通集合是模糊集的特殊情形。 若, u a ( x ) 兰0 ，则a 为空集o 。 若, u a ( x ) 若l ，则4 为全集x 。 定义1 21 1 3 设x 是论域，记x 上模糊集的全集为p ( x ) ，即 p ( x ) = 即专【0 ，1 】) 称h x ) 为x 上模糊幂集，尸( x ) 是一个普通集合。 1 1 3 模糊集合的运算 普通集合的运算，是由特征函数描述的。由于隶属函数是特征函数的推广， 所以模糊集合的运算自然可由隶属函数描述。 定义1 3 【1 2 ，1 3 】设彳，b ，c ，d 为论域x 上的模糊子集 ( 1 )若对任意的xe x ，有l u g ( x ) t 矗( x ) ，则称b 包含彳，记为彳b 。 显然包含关系“”是模糊幂集户( x ) 上的二元关系，具有如下性质： 1 ) 自反性：对于任意的a p ( x ) ，有a 互a ： 2 )反对称性：若a b ，b 譬a ，则a = b ； 3 ) 传递性：么b ，b c ，么c 。 ( 2 ) 若对于任意的x x ，有 心= m 觚 以( 工) ，心( x ) ) = 以( 工) v 心( x ) ( 1 1 ) 则称c 为么和b 的并集，记为c = 4 u 口。符号“v ”为“取大”运算。 ( 3 ) 若对于任意的x x ，有 u o ( 力= m i n l u , ( x ) ，心( 功) = 以( 曲 t s ( x ) ( 1 2 ) 则称d 为么和曰的交集，记为d = 彳nb 。符号“ ”为“取小”运算。 ( 4 ) 若对于任意的x x ，有 。( x ) = l 一t a ( x ) ( 1 3 ) 则称a 。为4 的补集( 或余集) 。 两个模糊集的运算也可推广到任意多个模糊集上去。 第1 章模糊数学及模糊熵理论 定义1 4 【1 3 】设4 p ( x ) ，t t ，丁为指标集，对于任意的z x ，规定： d ( 。u ，a t ) ( x ) 2 善心( x ) 2 普心( x ) h 0 4 ) ( x ) 2 会心( x ) 2 鳟心( 工 称q4 为 4 ) 时的并集，h ，a , 为 4 ) 时的交集。 t ejt e | 1 1 4 模糊集合的性质 定理1 1 【1 3 】有关模糊集合并、交、补运算，还有类似于普通集合运算的一些 性质： ( 1 ) 幂等律：a u a = a ，a n a = a ； ( 2 ) 交换律：a u b = b u a ，a n b = b n a ； ( 3 ) 结合律：au c b u c ) = ( a ub ) u c ，a n ( b n c ) = ( a n b ) n c ； ( 4 ) 分配律：( a u b ) n c = ( a n c ) u ( b n c ) ，( a n b ) u c = ( a u c ) n ( b u c ) ： ( 5 ) 吸收律：( a u b ) n a = a ，( a n b ) u a = a ； ( 6 ) 复原律：似。) 。= a ； ( 7 ) 对偶律：( a u b ) 。= a 。n b ，( a n b ) 。= a u b 。： ( 8 ) 0 一一1 律：么u x = x ，么u f 2 j = a ，彳n x = a ，彳n f 2 j = 1 2 j 。 需要注意的是，模糊集合并不满足普通集合的补余率，即a u a c = z ， a n a c = 9 。例如，模糊集合a = ( 0 7 ，0 3 ) ，则有 a u a c = ( 0 3 v 0 7 ，0 7 v o 3 ) = ( 0 7 ，0 7 ) x a n a c = ( 0 3 a 0 7 ，0 7 a 0 3 ) = ( o 3 ，0 3 ) o 特别地，当模糊集合a = ( 0 5 ，0 5 ) ，则有a c = ( 0 5 ，0 5 ) 。表明模糊集合中存在 等于自身的补集的集合。这在经典数学的康托集合论中是不可能出现的，但这恰 好反映出日常生活中“亦此亦彼”的现象。 一6 一 知识驱动的模糊聚类算法研究 1 1 5 模糊集合的表示方法 为了便于后面的义章表述，我们再来介绍一些模糊集合的表示方法【1 3 1 ： ( 1 ) 序偶法：a = ( x ，儿( x ) ) l x e x ) ； ( 2 ) z a d e h 法：若x 是有限可数集，可表示为 彳= 一兹 若x 是无限不可数集，可袭示为： 么= 严形 ( 注：“”不是通常的分数线，而是一种记号，表示论域x 上的元素x 与隶 属度以o ) 之间的对应关系。一与“，”也不是求和与积分，而是表示x 上 的元素x 与隶属度以( x ) 之间的对应关系的一个总括。) ( 3 ) 模糊向量法：a = ( 心( 五) ，以( 屯) ，以( 毛) ) 。 本文重点使用第三种表示法来表示实验中的模糊集合。 1 2 信息熵理论 1 2 1 信息熵理论简介 信息是信息论中最基本，同时也是最重要的概念，它与我们一般所讲的信息稍 有不同。一般而言，日常所讲的信息为一切可见的文字、图像、声音等数据形式， 我们也可以将这类事物称之为消息，而信息论中的“信息”一词则具有更深的涵 义。长时间以来，关于“信息”的定义并不统一，现在最为人们普遍接受的足由 信息论创始人c e s h a n n o n 于1 9 4 8 年在他的信息论奠基性论文通信的数学理论 中所给出的定义，即“信息是事物运动状态或存在方式的不确定性的描述” 1 4 1 。 1 2 2 信息熵定义 信息可以通过语言、文字、数学公式、图表符号等载体来进行表达。因此， 比较通过不同载体所表达信息的数量是很困难的。但是，信息的获得是与事物状 态( 或情况) 的不确定性( 概率不确定性) 相联系的。某一事物状态的( 概率) 第1 章模糊数学及模糊熵理论 不确定性的大小，与该事物可能出现的不同状态数目以及各形态出现的概率大小 有关。获得信息后，( 概率) 小确定性就可以减少或消除。既然小确定性的大小 能够度量，可见，信息也是可以度量的【1 5 】。 定义1 5 任意随机事件的自信息量定义为该事件发生概率的对数的负值。 设事件薯的概率为p ( x i ) ，那么，它的自信息定义为： ，( 薯) = 一l o g ) ( 1 4 ) 若知道事件已经发生，则该事件的信息量可称为自信息。信息量的单位取决 于对数所选取的底。最常用的底是2 。如果以2 为底，的单位为比特( b i t b i n a r y u n i t 的缩写) ；如果以e 为底，的单位为奈特( n a t ，n a t u r eu n i t 的缩写) ；如果 以l o 为底，的单位为哈特( h a r t ，h a r t l e y 的缩写) 。根据对数换底公式可算出：l 奈特= 1 4 4 比特，1 哈特= 3 3 2 比特。信息量单位中的比特，与计算机术语中的 “比特”的含义有所不同，计算机中的比特代表二元数字。二者的关系是每个二 元数字所能提供的最大平均信息量是l 比特。 例如，设事件为“抛掷一枚硬币，出现花纹面”。易知出现“数字面” 与出现“花纹面”的概率都为i 2 ，则由定义1 5 可计算出，这一事件的信息量为 l b i t 。 设另一事件为“抛掷一枚骰子，出现五点”，易知出现每一种点数的概率为 1 6 ，则由定义1 5 可算出，这一事件的信息量为2 5 8 5 b i t 。可以看出后一事件比前 一事件包含更大的信息景。 上而的描述都是对某一固定事件而言，通信信源发出信息的事件是不确定的， 如何来衡量这种不确定性，就要引入“信息熵”这个概念。 定义1 6 信息熵是从平均意义上来表征信源总体信息的测度，是随机变量不 确定性的量度，是信源平均不确定性的描述。它定义为自信息量的数学期望。 ( x ) = e ( 地) ) = ) - p ( x i ) l o g = 一只l o g p f ( 1 5 ) 知识驱动的模糊聚类箅泫研究 特别地，对于等概率事件 l 仍2 仍一一2 肌2 万 则有 ( x ) = - 1 1 。g 万1 + 1 l o g 万1 + + 万1l 。g 丙1 】_ 一l o g 丙1 = l 。g n 个 信息熵的单位是由自信息或信息量的单位来确定的。 信源的信息熵h 是从整个信源的统计特性来考虑的，它是从平均意义上来表 征信源的总体信息测度的，即表征信源的平均不确定程度。就是解除这不确定性 的信息量，也就是获得这样大的信息量后，信源的不确定度就被解除。因此，当 确切无误地收到一个信源符号后，就全部解除了这个符号的不确定度，获得了相 应的信息量。在等概率事件下，信息熵日与信息量，在数值上是相等的，但含义 不同。对某一信源来说，无论它是否输出信号，只要这些信号具有某些概率特性， 就必然有信源的信息熵日值。这值是在总体甲均上才有意义，因而是一个确定 值。而另一方面，信息量只有当信源输出符号而且接收者接收到后才有意义，这 就是给予接收者的信息度量，这个值本身也可以是随机量。 信息熵具有以下三种物理含义： ( 1 ) 信息熵h ( x ) 是表示信源输出后，每个 符号( 或消息) 所提供的平均信息量。( 2 ) 信息熵日( x ) 是表示信源输出前，信 源的平均不确定性。( 3 ) 用信息熵h ( x ) 米表征变量x 的随机性。 1 3 模糊熵理论 1 3 1 不确定性划分 在现实世界中，有许多事件发生的结果是不确定的，而这种不确定性贯穿于 我们的日常生活中，因此研究这种不确定性事件将有助于我们深入了解事物发展 的规律，从而更好的处理我们所遇到的问题。文献 1 6 】根据不确定事件产生的原因 将彳i 确定性分为三类，即“概率4 确定性”，“分析不确定性”和“模糊彳i 确定 性”，下文将进行简要介绍。 第1 章模糊数学及模糊熵理论 首先让我们米考虑一个游戏投一枚骰予米猜它落地后朝上的是哪一面。 参与游戏者对结果的不确定是由事件本身的随机性所引起的。处理这个问题的最 好方法可能是要以概率分靠的形式来描述骰子的六个面出现的情况，这种由于偶 然性所导致的不确定性称为“概率不确定性”( p r o b a b i l i s t i eu n c e r t a i n t y ) 。接下 来我们让计算机人工视觉系统也来参与这个游戏。基丁系统传感器所收集到的信 息，它可能给出或者为“五点”，或者为“六点”这样的结论，却再也不能进一 步给出更确切的结果。这种不确定性来源于系统所收集到的数据的有限性( 如由 于传感器等系统元件的限制) 。它反映了确定精确结果的含糊性，所以它被称为 “分析不确定性”( r e s o l u t i o n a lu n c e r t a i n t y ) 。假如把这个游戏换个玩法，不再 要求参与者说出朝上面的具体点数，而是判断骰子的点数是“大”还是“小”， 这就出现了第三种的不确定性( 因为既可以说“三点”以上就算大，也可以说“六 点”才算大) 。这种不确定性是由语义理解的偏差所产生的，我们称之为模糊不 确定性( f u z z yu n c e r t a i n t y ) 。模糊不确定性不同于概率不确定性和分析不确定性， 因为它处理的是边界没有准确界定的问题，而概率不确定性产生的原囚只与元素 是否属于一个清晰集合有关，而与集合边界无关。在现实生活中，有的事件只包 含一种不确定性，有的则可能会包含多种不确定性。例如，在上面的骰子实验中， “六点”属于模糊事件“大点数”的程度要比“三点”高，但这里边仍然有一个 投掷结果的问题，所以这个系统含有模糊不确定性和概率不确定性。 1 3 2 模糊熵的定义 通过上面的叙述我们不难得知，在1 2 节中所定义的信息熵是衡量概率不确定 性的有效工具，而如何来衡量其它两种不确定性，则需要应用其它的工具。这里 让我们来考虑模糊不确定性的衡量方法。z a d e h 的模糊集合理论是处理集合边界模 糊问题的有效工具，因此可以先将模糊事件用模糊集合的形式来表示，进而用量 化模糊集合的方法来确定模糊事件的不确定性，这种工具被称为模糊熵( f u z z y e n t r o p y ) 。需要指出，学术界关于模糊熵的定义并不统一，目前普遍为研究者所 认同的为d e l u c a 和t e r m i n i 于1 9 7 2 年所给出的定义。 知识驱动的模糊聚类算法研究 定义1 7 1 7 1 - 设x 为有限集，对于x x ，令以( x ) 为模糊集合彳的隶属函数； 模糊性量度h ( a ) 称为模糊熵，则满足以下四条公理： ( 1 )如果a 是xr f l 的清晰集合，则h ( a ) = 0 ； ( 2 ) 如果对于任意的x x ，均有鸬( x ) = 去，则( 彳) 取得最大值； ( 3 ) 如果模糊集合a 比模糊集合a “更清晰些”，如当l u g ( x ) 去， 心，o ) 以( j ) 或当以( 力i 1 ，心( j ) 以( 力，则有日( 彳) 何( 么) ； ( 4 ) h ( a c ) = h ( 彳) ，其中a c 是么的补集，即以。( j c ) = l 一以( x ) 。 通过分析以上阴条公理，我们可以很容易从直观上来看出它所表述的意义。 公理( 1 ) 表明普通集合是清晰的。公理( 2 ) ，( 3 ) 表明，越靠近0 5 就越模糊， 尤其是当心( 工) = j 1 时，最模糊。此时，( x ) = l 一心( j ) = 三1 ，模棱两可的情况最难 决策。公理( 4 ) 表明模糊集合彳与模糊集合彳c 具有同等的模糊度，因为 l 一( x ) 一三| - l 砟( j ) 一三i ，即一( x ) 和心。) 与。5 距离相等。 1 3 3 常用模糊熵公式 在上- d , 节中，我们介绍了模糊熵量度所应满足的四条公理。从这一公理出 发，不同的研究者基于不同的想法提出了许多不同的具体的模糊熵表达式，参见 【1 6 - 3 0 】。 为简洁起见，本文仅介绍同样由d e l u c a 和t e r m i n i 所提出模糊熵公式，该公 式也是目前研究者使用最为广泛的模糊熵公式之一。在后续的章节中，我们将把 其应用到我们所设计的算法中。 定义1 8 【1 7 1 设a 为论域x 上的模糊集合，即a ( x ) ，则模糊熵可定义为： ( 彳) = 一k 一l o g , u ，+ ( 1 一以) l o 双l 一一) ( 1 6 ) 第l 章模糊数学艟槿枷熵理论 其中是一标准化常数。一般的。当对数取以2 二i i 底时：三。 n 为更好地说明公式1 6 所定义的模糊不确定性量度，我们考察了仟意模糊集合 与其对应熵值( 模糊不确定性) 的关系。一维楔糊集合的熵值和二维模糊集合的 墒值与它们隶属度值的关系如刳11 所示。 1 一 弧 1 n 7 o 8 n e l 0 6 锄5j_ ；。 “ ? 02 “3 4 o 02 ：j 1 j a 1 。 ， 。 百r 占高育_ ； 图1i 模糊集台炳值与攫糊集合隶屉艘值的关系 f i g1 lt h e m l a t i o n s h i pb e t w e e n m e m b e b h l pd e g r e e 卸df u z z ye n n o p y 洼：图a = 儿古有一个元索的模糊集合，即a = 】：图b ：古有两个元常的模糊集合 即一= ( 一，如) 。 通过虬上两个图形也可以反映出模糊集合在隶属度值为05 时，模糊不确定性 虽大( 模糊熵值为1 ) ，而在隶属度值为0 或1 时，模糊性最小( 模糊熵值为o ) 。 知识驱动的模糊聚类算法研究 第2 章模糊c 均值算法与密切关系传播算法 2 1 聚类分析算法概述 在阐述“聚类分析”词的具体定义之前，让我们首先米思考一下人类对事 物进行分析的过程。为了处理问题的简便，人们常常在进行分析前对事物进行分 类，从而消除一些不相关因素的影响。如牛物学家将牛物分为植物与动物，化学 家将研究对象分为有机化学和无机化学，图书馆管理员将图书进 j ：分类摆放等等 都是这种行为的体现。随着计算机存储与计算技术的发展，如何利用计算机来模 拟人类思维来对工业与商业中出现的问题进行科学的分析，为使用者决策提供辅 助便日益成为人类社会发展的要求。与人的思维一样，为了提高计算效率和节省 计算资源，计算机在对事物进行具体分析前，也应先对事物进行适当的分类。而 如何根据数据本身的特征来使数据自动的“聚集成类”便是聚类分析算法所火心 和研究的问题。 聚类可定义为“将物理或抽象的集合分组成为南类似的对象组成的多个类的 过程”【1 1 。一般来说，聚类分析是一种由多学科交叉所产生的算法技术，其源于 许多研究领域，包括统计学，生物学，机器学爿以及数据挖掘。“聚类”这种分 类方法不同于机器学习领域中所提到的“分类”，后者在算法学习前可知晓部分 数据( 训练数据) 样本所带有的类的标签信息，而前者对于数据将要聚合成的类 的个数以及数据的标签均是未知的，是一种典型的无监督学习技术。 聚类分析近些年来发展很快，无论在学术界还是在工程界，对其的研究都有 了很大进展。有贡献的研究领域包括生物学，市场营销，空间数据库技术，统计 学，机器学习，以及数据挖掘。由于数据库中存有大量的生产生活所积累下的数 据，所以聚类分析已经成为数据挖掘研究中一个非常活跃的课题。在实际生产生 活中，聚类分析也得到了广泛的应用。在商业上，聚类能帮助市场分析人员分析 不同客户群的购买模式特征。在生物学上，聚类可帮助生物学家研究基冈组的结 构特征。在搜索引擎技术上，聚类分析也可用于识别不同w e b 网页的信息特征， 从而有助于提高搜索的效率与准确性。 第2 章模糊c 均值算法与密切关系传播算法 现有的聚类分析算法有很多种，大体可分为“划分方法”，“层次方法”， “基于密度的方法”，“基于网格的方法”和“基于模型的方法”等几类。具有 代表性的聚类分析算法主要有k 均值算法【3 1 1 、k 中心点算法【3 2 1 、f c m 算法【2 l ， d b s c a n 算法【3 3 1 、w a v e c l u s t e r 算、法【3 4 】等。本文着重于对经典算法f c m 算法和 新兴算法一密切关系传播算法的研究。 2 2 模糊c 均值算法研究 模糊c 均值( f u z z 3 , cm e a n s ，f c m ) 聚类算洲2 1 是一种通用的数据聚类算法， 其中每个样本点属于一个类的程度，以一个隶属度值来描述并通过模糊划分矩阵 来决定最终的聚类结果。在基于目标函数的模糊聚类算法中，f c m 算法的理论最 为完善，应用最为广泛。 f c m 将一个含有刀个样本的集合x = “，x 2 ，毛) 划为成c 个模糊群组，并- 月 在每个模糊群组中寻找一个聚类中心，使得一个基于距离测度的目标函数最小化。 它允许样本可以部分归属于某个类，同时兼顾了类之间的交迭。每一个样本点都 以0 和l 之问的一个隶属程度属于任何群组，聚类的结果是用下面的c 刀矩阵 u = ( 肛t ) 。= 4 i9 1 2 , u 2 1 如 雎l 以2 表示的一个模糊c 划分： 一。 鸬。 ： p c t ( 2 1 ) m y 。= r l 心【o ，l 】，v i ，k ，心= l ，v k ，以 心 o ，v f ) ( 2 2 ) i = lk = l 矩阵u 的第i 行给出了描述样本集x 中第i 个类的模糊子集鸬的隶属函数， i = l ，2 ，c ；u 的第k 列表示第k 个样本点气在c 个模糊子集中的隶属度值； 以= 鸬( ) 表示隶属于x 的第i 个类的隶属度值。 模糊c 均值算法首先确定了c 个类的中心，然后计算各个样本点到这些中心点 的距离并在赋以权值后求和( 权值为样本属于某一个类的隶属度) 通过改变这c 个 知识驱动的模糊聚类算法研究 中心点和样本隶属度的值( 改变模糊划分矩阵) 来求出最d q j n 权距离和所对应的 类的划分结果。这实际上是在求解如下的非线性规划问题 m i n j m ( u ，v ) - - 联兹 2 1 2 1 ( 2 3 ) f s j = 1 i = 1 其中，u m 蠡是模糊划分矩阵( 划分为c 个簇) ；y = “，屹，咋) ，v i r p 是 第f 个模糊群组肛的聚类中心，汪l ，2 ，c ；兹是样本点气与第f 类的中心向量_ 之 间的距离测度，定义为 以= l l x , 一训。= ( 气一h ) r 彳( 一u ) ，a 是p 阶对称正定矩阵 ( 2 4 ) 其中m e 1 ，佃】是控制最后划分的模糊性的加权指数，增大掰将增加函数的模 糊性，一般的，取m = l 。 利用l a g r a n g e 乘数法来求解上述非线性规划问题。由于模糊划分矩阵u 中各 列都是独立的，凶此目标函数可写成如下形式： 引入参数五，变有约束规划问题为无约束规划问题。令 f，f、 f = 以m 2 + 旯i 心- 1l i = li = 1 则最优化的一阶必要条件为 筹= 喜纠= 。 且 薏一删小。 ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) 、t f ， 乒 。阔 ，t 暑m 悄 = 、t ， 露 声 。蹦。h ，-i 璺m = 矿u ， 厶 ，t 口皿 第2 章模糊c 均值算法与密切关系传播算法 由式2 8 有 心= 去 磊 喜以= 喜( 鲁) 击 去 击= ( 昙) 击 喜 去 嘉 = t ( 尝) 磊2 寿 l 。，= f 窆j - l 陶l d t tj 而 ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) ( 2