《方法图论在聚类分析中的应用》由会员分享，可在线阅读，更多相关《方法图论在聚类分析中的应用（53页珍藏版）》请在金锄头文库上搜索。
1、山东师范大学 硕士学位论文 图论在聚类分析中的应用 姓名：张春明 申请学位级别：硕士 专业：应用数学 指导教师：高敬振 20040606 独创声明 篝5 , 9 8 4 3 0 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 ( 注：如没有其他需要特别声明的，本栏可空) 或其他教 育机构的学位或证书使用过的材料。- 9 我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：强春明 导师签字： 签字日期：2 0 0
2、4 年月1 日签字日期：2 0 0 4 年月7 日 束经 j F 着、导柳阀簋 细垒戈公布 图论在聚类分析中的应用 张春明 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 本文讨论聚类分析中的系统聚类法、模糊聚类法和灰色聚类法，着重探讨其 聚类的图论方法 第一章介绍聚类分析的基本知识 第二章讨论系统聚类分析及其中著名的最短距离法，指出了最短距离法即 为图论中求赋权连通图最小支撑树K r u s k a l 算法的变形，得到了最短距离法的 优良性质： 定理2 - 1 m a x p ( 只+ 1 ) ：最+ l 轨+ 1 ) _ s ( 只+ 1 ) = 肘_ 。
3、，( e uc f ) 2 M m “假) = 曲 二 ) ：最轨 对最短距离法和k = ”一l ，“ 一2 ，1 成立 它说明最短距离法得到的系统日= ( 只，只- “ ，置) X f f 每+ m = n - 1 , n - - 2 ，2 ，只 既是分离性最好的m 一剖分，又是相似性最好的m 一剖分 第三章讨论模糊聚类分析及其常用的传递闭包法，指出这种聚类方法的复 杂性，定义了模糊关系图G = ( x ，E 尽) 及其中两点甜，v 间的连通强度S ( u ，v ) ， 证明了s 是上的模糊等价关系、G = ( X ，E ，尽) 的最大支撑树具有如下性质： 定理3 2 设丁是模糊关系图G =
4、 ( 墨互约的一棵支撑树，则以下陈述等价： ( 1 ) 丁是G 的最大支撑树： ( 2 ) 对于任意的e E ( T ) ，从丁中移出e r 得五，五，则w ( e ) = ，M 、w ( e ) ； o q l l , 1 2 l G ( 3 ) 对任意的u , v e X ( u v ) ，T 中“，v 之间的惟一路是G 中最优( “，v ) 路 并建立了G = ( 置E ，尽) 中任两点的连通强度和尽的传递闭包f ( 霉) 之间的关系： 2 定理3 3 设x = 墨，x 2 ，j ，霉= ( 吩) 。是x 上的模糊相似关系，R 的传递闭包f ( 墨) = 尽“= ( 吣) 。，G = (
5、 五E 固是与 ，( v ) ，则，( D ；，功，p ( v ) ；V ( 3 ) 若k = 咒一1 ，据指针p ( ) 倒向追踪得最大支撑树T ；T 去掉w ( e ) ，( v ) ，t h e n ，( I - r ( V + ，V ) a n dp ( V ) ；V + ( 3 ) I fk = r - 1 ，u s et h ep o i n t f u n c t i o n p ( ) t o f i n do u tb a c kt r a c k i n ga m a x i m u ms p a n n i n gt r e eTo fG ；e a c hc o n n
6、e c t e dc o m p o n e n to fTw i t h a l le d g e seo fw ( 0 d ”( p = 1 ，2 ，七+ 1 ) ， 故G ：中c 二c ；，c 厶。互不连通，c o ( G ：) 七。矛盾证毕 定理2 1 说明，最短距离法得到的系统H = ( 只，只_ l ，日) 中，对每个 r r t = r 一1 ，趋一2 ，j 2 ，岛既是最大分离量掰一剖分，又是最小的嬲0 。f 一直径珑一 剖分据【6 】，几乎所有的聚类算法均不能兼顾分离性和相似性，所以最短距考 法的上述优良性质极引人注目此外，K r u s k a l 算法说明，最短距离法的复
7、杂性 为D ( “ 2 ) ，是一个好算法 第三章图论在模糊聚类分析中的应用 聚类分析原是数理统计多元分析的一个分支，然而由于现实的分类问题往往具 有一定的模糊性，因此这样的聚类用模糊数学的方法来处理可能更为恰当，分类的 结果也更符合客观实际，效果也更好，于是便产生了模糊聚类分析 3 1 模糊集理论简介 对于一个经典集合爿与空间中任一元素x ，要么x A ，要么x 茌A ，二者必 居其一，这一特征用函数表示为 彳c x ，= ：三三 通常称A ( x ) 为集合A 的特征函数为了描述模糊概念，1 9 6 5 年，美国加利福尼亚 大学教授查德( Z a d e h ) 第一次提出了“模糊集合”的
8、概念，他仿照用特征函数表 示经典集合的方法，用隶属函数表示模糊集合，并据其定义模糊集合的关系及运箕 以下定义可参见 4 ，9 定义3 1 论域u 中的模糊集合4 ，是以隶属函数心为表征的集合，即 心：U - O ，1 】 对任意的“u ，有“_ 心 ) ，心 ) o ，l 】，称心m ) 为元素“对于4 的隶属度， 它表示“属于4 的程度为了表达上的方便，模糊集4 的隶属函数心也简写为4 ， 从而心( z r ) 也就可以简写为4 ( u ) 定义3 2 设4 为论域u 上的任一模糊集，对任意的0 2 1 ，记 4 = H 4 ( x ) 五，x u ) ， 称4 为4 的五截集 1 9 显然
9、，A , t 是普通集合，而非模糊集合由于模糊集合的边界是模糊的，在把 模糊概念转化为数学语言时，需要选取不同的置信水平五( 0 五1 ) 来确定其隶属 关系，旯截集就是将模糊集合转化为经典集合的方法，它随五值的减小而增大，即 当 令其自然对应一个赋权完全图( 不妨称之为 模糊关系图) G = ( x ，E ，尽) ，其中边鼍0 赋权w G 刁) = 吩( f ，) ，这样对x 聚类， 即为剖分G 之顶点集 3 3 1 最大支撵树及其性质 定义3 9 【7 1 设丁是赋权连通图G = ( y ，E ，D ) 的一棵支撑树，若对于G 的一切 支撑树丁都有 w P ) w ( ， * E ( r
10、) * E ( r ) 则称r 是G 的一棵最大支撑树，简称最大树 定义3 1 0 在模糊关系图G = ( Z ，E ，尽) 中， ( 1 ) 路径三上边权的最小值，称为L 的连通强度，记作S ( L ) ，即 s ) _ 。氛) w ( e ) ， 其中E ( ) 表示路三的边集 ( 2 ) 两点群，y 之间所有路径厶，三：，t 连通强度的最大值，称为“，V 之问的 连通强度，记为S ( u ，v ) ，即 k s ( ”，v ) 2 当s ( 岛) ( “D 并约定S ( u ，“) = 1 ( 3 ) 设L 是G 中连接“，V 两点的路，；g S ( L ) = S ( u ，V ) ，
11、则称三为G 中连接“，V 两点的最优路 定理3 t 模糊关系图G = ( X ，E ，墨) 中，连通强度S 是X 上的模糊等价关 系 证由定义易知S 满足自反性和对称性，下面证明S 还满足传递性 因为$ 2 ( 2 ，v ) = 善岱 w ) 双呦，故任取材，y ，若“= V ，显然有 S ( u ，v ) S 2 ( “，v ) ，下设“v 任取w X ，当W = ”或w = v 时，S ，v ) = S ( “，w ) A S ( w , v ) ；当w “且W v 时，取日，只分别为G 中连接“与w 和w 与V 的最优路，则弓u 忍包含了G 中连接 甜与v 的路P ，从而以P ) 联日)
12、 u 以昱) ，于是有 S ( u ，V ) S ( 尸) s ( 置) S ( B ) = s ( u ，w ) A S ( w ，V ) ， 所以也有S ( u ，v ) S 2 ( 地v ) 证毕 模糊关系图的最大支撑树具有如下优良性质： 定理3 2 设丁是模糊关系图G = ( z ，E ，尽) 的一棵支撑树，则以下陈述等价； ( 1 ) T 是G 的最大支撑树； ( 2 ) 对于任意的e E ( T ) ，从丁中移出e 得五，五，则w ( e ) = ，X 、w ( e ) ： P 6 【0 1 ，0 2 k ( 3 ) 对于任意的u , v e X ( u v ) ，T 中“，V 间
13、的惟一路是G 中最优( “，V ) 路 证( 1 ) j ( 2 ) 设丁是G 的一棵最大支撑树，但存在e E ( T ) 使得 w ( e 7 ) 。 箍 G w ( e ) = w ( e ”) ， 设 显然e ”e 用e ”代替e ，则得到一棵新的支撑树r ，因为 喇= w + w - ys G ) = s ( 而，) 另一方面- 任取( ，屯，电。) e W ，则蕾b x A _ 。x j 是墨与0 之间的一 条通道，其中必包含从薯与0 之间的路上，且此路的强度 s ( D 锄人7 勘 人0 ， 设厶，5 2 ，厶为G 中从而到0 之间的全部路径，则 瓯薯，弓) 2 苫s 鸣) 勃X
14、渺( 知) = 7 ，鼍) 所以，f ( 墨) 岛，鼍) = S ( 而，0 ) 证毕 定理3 1 说明，S 是z 上的模糊等价关系；而定理3 3 又说明t ( R ) = S 这就 是说，X i 与X j 在旯水平上能划分为一类，等价于在模糊关系图G = ( X ，E ，尽) 上点 薯与工，之间存在一条强度不小于五的路因此可以直接从G 上进行聚类，方法是 只要在t 与乃之间找到一条强度不小于五的路，则薯与0 在旯水平上应属于一 类 然而要在模糊关系图G 两点之间的众多路径中找出一条强度不小于五的路并 非易事但是如果我们构造一个图，使任意两点誓与x ，之间只有惟一路上相连， 并使s ( o =
15、 S ( 鼍，x ，) ，这样再按五聚类就很容易了 由定理3 2 知，模糊关系图G 的最大支撑树T 中，“，v 之间唯一路L 的强度 s ( z ) = S ( u ，V ) 因此z 按尽聚类的关键是寻找模糊关系图G = ( z ，E ，垦) 的最大 支撑树r ，有了r ，对于任意给定的A ，只要将T 中w ( e ) 旯的边去掉便可以得 N - 个不连通的子图，它的各连通分支就是X 在A 水平上的一个分类这就是最 大支撑树模糊聚类法【 采用避圈法时可不须作出模糊关系图G = ( z ，E ，尽) ，直接从模糊相似矩阵尽 出发即可求出最大支撑树具体算法如下： 设模糊相似矩阵墨= 嘞k ，聚类水平为五，令4 表示树的结点集，4 , g 02 r ( I ，t ) ( 1 ) 任选一点v 1 彳，记爿1 = V 1 ( 2 ) 设V 蜀= x 、4 使得，( V v 0 - - ，。V 丑r ( v , v O ，记V + 为v 2 ，q = “，v 2 ) ， 岛= q ) ，4 = A 1u 屹) ( 3 ) 设已经取出了七个顶点僻 功，即有4 七_ v l ，v 2 ，v 七) 和后一1 条边E 女二1 = q ，岛，铀 ，若1 ，B k2 x 4 使得，F ，)
