（应用数学专业论文）图论在聚类分析中的应用.pdf

独创声明 篝5 , 9 8 4 3 0 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 ( 注：如没有其他需要特别声明的，本栏可空) 或其他教 育机构的学位或证书使用过的材料。- 9 我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：强春明 导师签字： 签字日期：2 0 0 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 ) = 肘_ 。，( 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 = ( 墨互约的一棵支撑树，则以下陈述等价： ( 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 = ( 五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 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 五r e m o v e d i sac l u s t e ro fx o n t h e l e v e l 旯，s t o p o t h e r w i s e ，l e t k ：= k + 1a n dr e r u n t o ( 2 ) t h ec o m p l e x i t yo ft h e a l g o r i t h m i s o n l yo ( n 2 ) w ec h e c kt h ea l g o r i t h mb ya n e x a m p l ef m a l l y i n c h a p t e r f o u rw ed i s c u s s g r e y c o r r e l a t i o n c l u s t e r i n ga n a l y s i s a n dt h e t r a d i t i o n a ll i n e b y l i n ec h e c k - u p m e t h o d ，p o i n t o u tt h a tt h ec o m p l e x i t yo ft h em e t h o d i s o ( m 4 ) ，b yi m i t a t i n g t h ed e f i n i t i o n so f t h ec o n n e c t e di n t e n s i t ya n d r e l a t e dr e s u l t s i nt h em a x i m u m s p a n n i n gt r e ea l g o r i t h mo ff u z z yc l u s t e r i n ga n a l y s i s ，w eg i v et h e d e f i n i t i o no fc o n n e c t e d i n t e n s i t y i na w e i g h t e dg r a p hg 号( 矿，e ，d ) a n dj p r o p e r t yo f i t sm a x i m u m s p a n n i n gt r e e f u r t h e r m o r ew e d e f i n et h e 旯一c r o s sg r a p h q a n dt h ec o n n e c t e dc l o s u r ego fg = ( v ，e ，d ) ，o b t a i na p r o p e r t y o fq a n d 否： t h e o r e m4 2i f g = ( y ，e ，d ) i s aw e i g h t e dg r a p h ，t h e nf o ra n y 2 峨1 】， g 。= g ， b y w h i c hw e1 n d i c a t et l l a tv e r t i c e sua n dvi n 爿c l u s t e r e d t o g e t h e r i nl e v e i 五 i fa n d o n l y i ft h e ya r ec o n n e c t e di nt h ea c r o s s g r a p h 五o f am a x i m u m s p a n n i n gt r e e t o f t h ec o r r e l a t i o ng r a p hg = e 爿) f r o mt h i s v ed e v e l o pt h e m a x i m u ms p a n n i n gt r e ea l g o r i t h mo fg r e yc o r r e l a t i o nc l u s t e r i n ga n a l y s i sw i t ht h e c o m p l e x i t y i s o n l yo ( m 2 ) ，w h i c hr e d u c et h ea m o u n to fo p e r a t i o ne f f e c t i v e l y f i n a l l yw e c h e c kt h ea l g o r i t h mb ya n e x a m p l e 7 k e y w o r d s ：h i e r a r c h i c a l c l u s t e r ；f u z z yc l u s t e r ；g r e y c o r r e l a t i o n c l u s t e r ； m i n i m u m s p a n n i n gt r e e ；m a x i m u ms p a n n i n g t r e e s u b j e c t c i a s s i f i c a t i o r ：0 1 5 7 6 8 第一章聚类分析基本知识 聚类分析是数理统计中研究“物以类聚”的一种方法数值分类可分为两 大类问题，一类问题是当前研究的对象已知其分类情况，将某些未知分类个体 正确地归属于其中某一类，这是判别分析所要解决的问题；另一类是不存在一 个事前分类的情况下，进行数据结构的分类，这就是聚类分析所要解决的问题 聚类分析的职能是要建立一种分类方法，将一批样品或变量按照其亲疏程 度进行分类，使得同类样品相似，而且( 或者) 类与类之间分离性良好 刻划样品或变量之间亲疏程度的数量指标通常有两种，一种叫相似系数， 性质越接近的样品，它们之间的相似系数越接近于1 ( 或一1 ) ，而彼此无关的样 品，它们之间的相似系数则接近于0 ，在进行聚类处理时，比较相似的样品归为 一类，不怎么相似的样品归为不同的类；另一种是距离，它是把每个样品看成 是m 维空间中的一个点，在m 维空问中定义点与点之间的某种距离，距离较近 的点归为同一类，距离较远的点归为不同的类 聚类分析中常用的相似系数和距离的定义见【l ，2 ，3 1 ，本文不再赘述 在实际问题中，不同的变量一般取的量纲不同，为了使不同的量纲也能放 到起比较，通常需要对数据作一些变换：有时，即使变量用的是同一量纲， 为了使数据更适合某种数学模型，也需要将数据变换常用的变换有： ( 1 ) 平移变换：将某一指标的数据同减去一数，一般是减去均值 ( 2 ) 极差变换：将某一指标的数据除以该指标的极差 ( 3 ) 标准差变换：将某一指标的数据除以该指标的标准差 ( 4 ) 主成分变换：将数据用它们的主成分代替，有时为了简化，只取前几个 主成分，舍去次要的主成分 ( 5 1 对数变换：将数据取对数当数据间数量级相差较大时常采用这一变换 以上变换有时同时采用多个，例如常说的将数据标准化，就是先作变换( 1 b 后作变换( 3 ) 确定了样品或变量之间的距离( 或相似系数) 之后，就要对样品或变量进行归 9 类，归类的方法主要有以下几种： ( 1 ) 系统聚类法：在样品距离的基础上定义类与类之间的距离，首先令”个 样品各自成一类，然后每次将具有最小距离的两类合并，合并后重新计算类与 类之间的距离，直到所有样品归为一类为止 ( 2 ) 动态聚类法：先将样品初步分类，然后根据分类函数尽可能小的原则， 对已分类别进行调整，直到分类合理为止 ( 3 ) 模糊聚类法【4 】：利用模糊集的理论来处理分类问题，它对各领域中具有 模糊特征的数据具有明显的分类效果 ( 4 ) 聚类预报：利用聚类方法来处理预报问题，主要是处理一些异常数据， 如气象中灾害性天气的预报用聚类预报方法处理可以弥补回归分析和判别分 析的不足 ( 5 ) 灰色聚类法【5 】：依据灰色系统理论将一些观测指标或观测对象聚集成若 干个可定义类别的方法对于现实问题中“灰”性较大的数据，用灰色聚类法处 理效果较好 本文将讨论系统聚类法，模糊聚类法和灰色聚类法，着重探讨其中的图论方 法 1 0 第二章图论在系统聚类分析中的应用 系统聚类分析【1 】是目前在实际中使用最多的一种聚类方法其基本思想是： 首先定义样品之间的距离和类与类之间的距离，一开始令, v 个样品各自成一类， ， 这时类与类之间的距离与样品之间的距离是等价的，然后将距离最近的两类合 并，合并后重新计算新类与其它类的距离，再按最小距离归类这样每次减少 一类，直到所有的样品归为一类为止其整个归类过程可用聚类谱系图形象地 表达出来，再按聚类图进行归类 常用的系统聚类法有八种，分别为最短距离法、最长距离法、中间距离法、 重心法、类平均法、可变类平均法、可变法及离差平方和法，它们的不同之处 仅在于类与类之间距离的定义方法不同，而且每一种方法均有不同的优缺点， 其中最短距离法在数学理论上有许多优点下面仅介绍最短距离法，并探讨它 与图论中最小支撑树的联系 2 1 最短距离法 设样品集合x = ，毛，靠 ，则对聚类就是研究如何将x 剖分成埘个 非空不交的子集( 类) c l ，c 2 ，c _ ，使得同类样品相似，而且( 或者) 类与 类之间分离性良好若已知样品间的距离矩阵d = ( 磊) 。，则此聚类问题可记 为( ，d ) 设只，只_ l ，最各为x 的门一剖分，0 1 ) 一剖分，1 一剖分，显然有 只= x ， ：i = l 州2 一，行) ，鼻= z ) 若对每一m = 艴，n - i ，2 ，己一l 是通过合并己中某两类得到，则称只，只_ 1 ，弓 形成一个系统，这便是系统聚类法的由来不难看出，任一系统都恰好含有2 n 一1 个爿的( 非空) 子集，它们两两之间或者不交，或者一个完全包含另一个 最短距离法 1 , 6 j 也称单联算法，它是把两个类之间的距离定义为一个类的所 有个体与另一个类的所有个体之间距离的最小者，即最短距离法聚类定义类c 。 与类q 之间的距离为 = l l i l l 毛：x s q ，弓g ， 习惯上也称为类q 与类q 的分离量，而称 s 心) = 疵 ：l g s 鸭g p ) = 曲向：x f c p ，弓烈q j 为类q 的分离量，称 s ( 只) = i i l i n s ( q ) ：p = l ，2 ，嘲= r 1 1 i n 呜：玉c p ，_ q ，1 p ，z = 抽，屯，毛) ，d = f a v ) 。，可令其自然对应 一个赋权完全图g = ( x ，e ，d ) ，即令其边t 赋权略，则此聚类变为剖分g 之 顶点集 易见最短距离法是求g 的最小支撑树的k r u s k a l 算法的变形【6 】：将后者执行 过程中构造出的g 的支撑森林的分支各看作x 的一类，加边看作合并其端点所 在的两类即可设丁为g 的一棵最小支撑树， e ( r ) = e l , e 2 ，一，e n 1 ) ，d ( 巳一1 ) d ( 乞) d ( q ) ， 其中d ( 岛) 表示边p i 的权设诸d ( 乌) 形成的多重集为不同元素形成集 合 见。= 吐 d 2 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 算法说明，最短距离法的复杂性 为d ( 2 ) ，是一个好算法 第三章图论在模糊聚类分析中的应用 聚类分析原是数理统计多元分析的一个分支，然而由于现实的分类问题往往具 有一定的模糊性，因此这样的聚类用模糊数学的方法来处理可能更为恰当，分类的 结果也更符合客观实际，效果也更好，于是便产生了模糊聚类分析 3 1 模糊集理论简介 对于一个经典集合爿与空间中任一元素x ，要么x a ，要么x 茌a ，二者必 居其一，这一特征用函数表示为 彳c x ，= ：三三 通常称a ( x ) 为集合a 的特征函数为了描述模糊概念，1 9 6 5 年，美国加利福尼亚 大学教授查德( z a d e h ) 第一次提出了“模糊集合”的概念，他仿照用特征函数表 示经典集合的方法，用隶属函数表示模糊集合，并据其定义模糊集合的关系及运箕 以下定义可参见 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 显然，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 ) * 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 ) ，则称三为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 ) 联日) 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 间的惟一路是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 渺( 知) = 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 = 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 ，) _ 。咆v ，吨， v ) ，则记v + v k + 。，e k = ( ，v k + 。) f 4 ) ，钿= 4 u ) ，磊= 巨。u 咏) ( 4 ) 若k = 胛一1 ，得最大支撑树t ：t 中去掉w 0 ) ，( v ) ，则，# ，( v ，v ) ，p ( v ) ；矿 ( 3 ) 若k = n 一1 ，据指针p ( ) 倒向追踪得最大支撑树丁；t 中去掉w ( 口) 五的所 有边e 后的各连通分支即为x 在 水平上的一个分类，停否则，令 k - - k + l ，回( 2 ) 这里( 1 ) 、( 2 ) 确定第一条边，须作n - 2 次比较：( 3 ) 须作一妨+ k 一1 ) = 2 ( n - k ) 一1 次比较，所以共须作 ( n 一2 ) + z 2 ( - 一妨一1 】= 0 2 x n - 1 ) 次比较即该算法的复杂性为o ( n 2 例3 3 仍以例3 1 给出的尽为例，设其对应的模糊关系图为g = ( x ，e ，墨) ( 如 图3 2 ) ，按上述算法求出g 的最大支撑树丁见图3 3 若取旯= o 9 ，将w ( o o - 9 的边去掉，得分类结果为： x l ， 吃) ， 知) 墨，) 若取五= o 8 ，将w ( o o 8 的边去掉，得分类结果为： x i ，x 2 ，x 3 ，砖 ， h ) 得到的结果与例3 2 相同 最后需要说明的是，一个赋权连通图的最大支撑树可能不唯一，但这并不影响 x i ，0 两点间的连通强度，即最大支撑树模糊聚类方法与最大支撑树的选择无关 图3 3 此外，从集合x 上的模糊相似关系霉出发作模糊聚类分析( 等同予最大支撵 树模糊聚类分析) ，是通过对霎的合成运算获得它的传递闭包f ( 尽) 来进行的，然而 由于的元素间真正关系是尽而非f ( 尽) ，这样以f ( 尽) 代替墨对x 作模糊聚类可能 会导致“失真”为了使失真性达到最小，文 1 8 j 提出了一种最优模糊聚类法， 其基本思路如下： 设墨= ( 勺) 。是x = 玉，而，而) 上的模糊相似关系，s = ( ) 。是x 上 的模糊等价关系若对x 上的任意模糊等价关系s = ( 吩) 。，都有 n - | ni 而, 一勺) 2 艺窆( 勺一勺) 2 i = 1 j = + l 、 i = 1 = i “ 成立，则按s + 对x 进行聚类，称为尽对x 的最优模糊聚类 据此，文【9 】给出了一个最优模糊聚类算法，只是其复杂性为指数级的所以有关模 糊聚类分析分类的合理性问题及可行性算法的探讨，还有待于人们作进步的研 究 第四章图论在灰色聚类分析中的应用 4 1 灰色系统理论简介 灰色系统理论是我国著名学者邓聚龙教授于1 9 8 2 年创立的门新兴横断 学科，它以“部分信息己知，部分信息未知”的“小样本”、“贫信息”不确定 性系统为研究对象，主要通过对“部分”已知信息的生成、开发，提取有价值 的信息，实现对系统运行行为的正确认识和有效控制目前，灰色系统理论已 广泛应用于工业、农业、经济、交通、能源等各个领域本节我们简要介绍这 一理论，较详细的情况请阅 5 ，1 9 - 2 2 。 4 1 1 灰色系统的基本概念 灰色系统理论用“黑”表示信息未知，用“白”表示信息完全明确，用“灰” 表示部分信息明确、部分信息不明确，即信息不完全通常，“灰”的基本含义 包括： ( 1 ) 系统元素信息不完全； ( 2 ) 系统结构信息不完全； ( 3 ) 系统边界信息不完全； ( 4 ) 系统运行行为信息不完全 相应地，信息完全明确的系统称为白色系统，信息未知的系统称为黑色系统，部 分信息明确、部分信息不明确的系统称为灰色系统 定义4 1只知道其大概范围而不知道其确切值的数称为灰数灰数通常 用记号“ ”表示，其可能的取值范围称为其灰域 灰数是灰色系统的基本“单元”，在应用中，灰数实际上是指在某一个区间 或某个一般的数集内取值的不确定数 定义4 2 灰数。之灰域内的任一特定值称为该灰数的一个白化值( 或表 现值) 一个灰数对其不同表现值的认同程度常常是不同的例如，1 9 与2 0 相比 较，“1 8 左右”这个灰数对1 9 似乎更“偏爱”一些 定义4 3 灰数固的白化权函数( 认同度函数) 是表示。对其白化值( 表 现值) 的认同程度从其灰域到区间 o ，l 】的一个函数，用，( ) 表示 4 1 2 灰色系统的基本原理 在灰色系统理论的创立和发展过程中，邓聚龙教授发现并提炼出灰色系统 的基本原理 公理4 1( 差异信息原理)“差异”是信息，凡信息必有差异 公理4 2 ( 解的非惟一性原理) 信息不完全、不确定的解是非惟一的 公理4 3 ( 最少信息原理) 灰色系统理论的特点是充分开发利用已有的 “最少信息” 公理4 4 ( 认知根据原理) 信息是认知的根据 公理4 5 ( 新信息优先原理) 新信息对认知的作用大于老信息 公理4 6 ( 灰性不灭原理)“信息不完全”( 灰) 是绝对的 4 1 3 三种不确定性方法的比较 概率统计、模糊数学和灰色系统理论是三种最常用的不确定性系统的研究 方法，其研究对象都具有某种不确定性，这是三者的共同点然而由于它们所 研究对象在不确定性上的区别，使得它们成为- - - t _ 】各具特色的不确定性学科 概率统计研究的是“随机不确定”现象，着重于考察“随机不确定”现象 的历史统计规律，考察具有多种可能发生的结果之“随机不确定”现象中每一 种结果发生的可能性大小其出发点是大样本，并要求研究对象服从某种典型 分布 模糊数学着重研究“认知不确定”问题，其研究对象具有“内涵明确、外 延不明确”的特征比如“年轻人”就是一个模糊概念，因为每一个人都十分 清楚年轻人的内涵，但要让你划定一个确切的范围，在这个范围之内的都是年 轻人，范围之外的都不是年轻人，则很难办到，因为年轻人这个概念外延不明 确对于这类内涵明确、外延不明确的“认知不确定”问题，模糊数学主要是 凭经验借助于隶属函数进行处理 灰色系统着重研究概率统计、模糊数学所不能解决的“小样本、贫信息不 确定”问题，并依据信息覆盖，通过序列生成寻求现实规律，其特点是“少数 据建模”与模糊数学所不同的是，灰色系统理论着重研究“外延明确、内涵 不明确”的对象比如说，他的年龄在2 0 岁到2 5 岁之间，这里的“2 0 岁到2 5 岁之间”就是一个灰概念，其外延是非常明确的，但如果进一步要问是哪个具 体值，则不清楚 综上所述，三者之间的异同可归纳如表4 1 所示 表4 1 三种不确定性方法的异同 项目灰色系统概率统计模糊数学 研究对象贫信息不确定随机不确定认知不确定 基础集合灰色朦胧集康托集模糊集 方法依据信息覆盖映射映射 途径手段灰序列生成频率统计截集 数据要求任意分布典型分布隶属度可知 侧重内涵内涵外延 目标现实规律历史统计规律认知表达 特色小样本大样本凭经验 4 。2 灰色关联聚类 灰色聚类【5 川是根据灰色关联矩阵或灰数的白化权函数将一些观测指标或 观测对象聚集成若干个可定义类别的方法 灰色聚类按聚类对象划分，可分为灰色关联聚类和灰类白化权函数聚类芡 色关联聚类主要用于同类因素的归并，以使复杂系统简化通过灰色关联聚类， 可以检查许多因素中是否有若干个因素关系十分密切，使我们既能够运用这些 因素的综合平均指标或其中的某一个因素来代表这几个因素，又使信息不受严 重损失，这是属于系统变量删简的问题在进行大面积调研之前，通过典型抽 样数据的灰色关联聚类，可以减少不必要变量的收集，以节省经费灰类白化 权函数聚类主要用于检查观测对象是否属于事先设定的不同类别，以便区别对 待因此严格地说，灰类白化权函数聚类并非普通意义上的“聚类”，称为“灰 色判别”也许更贴切一些 下面仅研究灰色关联聚类，着重探讨其聚类的图论方法本节我们简单介 绍一下灰色关联聚类，详细情况可见 5 ，1 9 ，2 3 3 0 灰色关联聚类的基本思想 是由观测对象的特征数据计算出各指标间的灰色关联度，建立特征变量关联矩 阵，再依据一定的临界值水平得到聚类结果 4 2 1 灰色关联度 灰色关联度是刻划因素间关联程度的一种度量，它可以看作是统计范畴内 的相关系数的满意解或近似解 定义4 4 设x = ( x ( 1 ) ，x ( 2 ) ，z 0 ) ) 为系统行为数据序列，d 为作用于x 的算子，x 经算子d 作用后所得序列记为 d 6 d = ( x ( 1 ) d , x ( 2 ) d ，x ( n ) d ) ， 称d 为序列算子，称x d 为一阶算子作用序列 类似可定义高阶序列算子及高阶算子作用序列 定义4 5 设置为系统因素，其在序号k 上的观测数据为玉( 功( 尼= l 2 ，j 叻， 则称= ( 一( 1 ) ，薯( 2 ) ，( 功) 为因素鼍的行为序列 ；g k 为时问序号，则称z = ( 薯( 1 ) ( 2 ) ，五( 哟) 为因素五的行为时间序 列； 若七为指标序号，则称置= “( 1 ) ，薯( 2 ) ，薯0 ) ) 为因素x i 的行为指标序 列； 若七为观测对象序号，则称五= ( 薯( 1 ) ，五( 2 ) ，薯( ，2 ) ) 为因素五的行为横 向序列 采用原始数据计算灰色关联度的方法，称为直接法，为了能够把不同量纲 的序列数据放在一起比较和处理，并且消除计算中“大数吃小数”的影响，通 常要对原始数据作无量纲化处理，这种计算关联度的方法称为间接法对数据 无量纲化处理的方法主要有：初值化、均值化、归一化和平移，现简要介绍如 下： 定义4 6 设置= ( 毛( 1 ) ，t ( 2 ) ，薯( 胛) ) 为因素置的行为序列，d 为序 列算子，r x ，d = ( x ( 1 ) d ，x ( 2 ) d ，x ( n ) d ) ( 1 ) 初值化 若 而( 例= 哿( k = 1 , 2 , - - - , 功， 则称d 为初值化算子，五为原像，蜀d 为五在初值化算子d 下的像，简称初 值像 ( 2 ) 均值化 若 相d = 警睁1 ，2 ，石= 击言榔 则称d 为均值化算子，x , d 蔓s 五在均值化算子d 下的像，简称均值像 ( 3 ) 归一化 若鼍( 七) d ：地，c 为非零常数( ：1 ，2 ，”) ， 则称d 为归一化算子，置d 为x f 在归一化算子d 下的像，简称归一像 ( 4 ) 平移 若五( 七) d = 薯( 七) + c ，c 为常数伍= l ，2 ，一) 则称d 为平移算子，x i d 为x i 在平移算子d 下的像，简称平移像 定义4 7 设瓦；( 而( 1 ) ，x o ( 2 ) ，x o ( n ) ) 为系统特征序列，且 墨= ( 毛( 1 ) ，葺( 2 ) ，而( 玎) ) ，i = 1 ，2 ，柳 为相关因素序列给定实数y ( ) ，而( 七) ) ，若实数 y ( x o = 去耋r ( x o ( k ) 烈砌 满足 ( 】) 规范性o “d 刚，( v ) # ，( v ，v ) ，p ( v ) # 矿 ( 3 ) 若j = m 一1 ，据指针p ( ) 倒向追踪得最大支撑树丁，te p 去掉_ w ( e ) 2 的所有边e 后的各连通分支即为x 在五水平上的一个分类，停否则， 令k ；k + l ，回( 2 ) 据前知，该算法的复杂性为o ( m 2 ) 仍以例4 1 为例，按照上述算法得到其关联图的最大支撑树r 如图4 1 若取五= o 8 0 ，把丁中边权小于o 8 0 的边去掉，得到一个不连通的子图( 如 图4 2 ) ，它的各连通分支所包含的顶点集分别为 墨，五，五，五，五，墨，_ 乞，j ，4 ) ， 五，冯) ， 葛) ， 葛，局，讫 即为指标集在临界值0 8 0 水平上的一个分类，此分类结果与例4 1 给出的相 同 此外，据最大支撑树，同样可以作出一个动态的聚类谱系图( 如图4 3 ) ，由 谱系图可以得到x 对应于各临界值水平的一个分类如取五= o 5 8 ，从谱系图 可以得到指标集被分为两类 墨，五，五，墨，五，墨，蜀，墨：，五，五。) ， 五，马，五，五。，五5 ) 也得到与例4 1 相同的结果 图4 1 z o 棠 ，“罄。# 以 耄广 托 图4 2 x lx tx nx “x ix ，x 好x x nx sx 、x ，x ux nx 1 图4 - 3 耄堇缀堇誊 主要参考文献 1 张尧庭，方开泰，多元统计分析引论 m 北京：科学出版社，1 9 9 9 2 方开泰，聚类分析 j 数学的实践与认识，1 9 7 8 ，( 1 ) ，( 2 ) 3 罗积玉，邢瑛，经济统计分析方法及预测 m 北京：清华大学出版社，1 9 8 7 4 肖位枢，模糊数学基础及应用 m 北京：航空工业出版社，1 9 8 7 5 刘思峰，郭天榜，党耀国等，灰色系统理论及其应用 m 北京：科学出版 社1 9 9 9 6 高敬振，图论在聚类分析中的应用 j 数学的实践与认识，1 9 9 1 ，( 3 ) 7 美 j a 邦迪，u s r 默蒂著，吴望名等译，图论及其应用 m 北京：科 学出版社，1 9 8 4 8 美 c h p a p a d i m i t r i o u ，k s t e i g l i t z 著，刘振宏，蔡茂诚译，组合最优 化 m 北京：清华大学出版社，1 9 8 8 9 彭祖赠，孙韫玉，模糊( f u z z y ) 数学及其应用 m 武汉：武汉大学出版社， 2 0 0 2 1 0 李相缟，李洪兴，陈世权，汪培庄，模糊聚类分析及其应用 m 贵阳：贵 州科学技术出版社，1 9 9 4 1 1 杨留记，f u z z y 关系传递