论文部分内容阅读
该文讨论聚类分析中的系统聚类法、模糊聚类法和灰色聚类法,着重探讨其聚类的图论方法.第一章介绍聚类分析的基本知识.第二章讨论系统聚类分析及其中著名的最短距离法,指出了最短距离法即为图论中求赋权连通图最小支撑树Kruskal算法的变形,得到了最短距离法的优良性质:定理2.1 max{s(p′<,k+1>):p′<,k+1>∈ <,k+1>}=s(P<,k+1>)=M<,mst>(C<,s> ∪ C<,t>)=M<,mst>(P<,k>)=min{M<,mst>(P′<,k>):P′<,k>∈( )<,k>}对最短距离法和k=n-1,n-2,…,1成立.它说明最短距离法得到的系统H=(P<,n>,P<,n-1>…,P<,1>)对每个m=n-1,n-2,…2,P<,m>既是分离性最好的m-剖分,又是相似性最好的m-剖分.第三章讨论模糊聚类分析及其常用的传递闭包法,指出这种聚类方法的复杂性,定义了模糊关系图G=(X,E,R)及其中两点u,v间的连通强度S(u,v),证明了S是X上的模糊等价关系、G=(X,E,R)的最大支撑树具有如下性质:定理3.2设T是模糊关系图G=(X,E,R)的一棵支撑树,则以下陈述等价:(1)T是G的最大支撑树;(2)对于任意的e′∈E(T),从T中移出e′得T<,1>,T<,2>,则w(e′)=<,e∈[T<,1>,T<,2>]G>Vw(e);(3)对任意的u,vv∈X(u≠v),T中u,v之间的惟一路是G中最优(u,v)路.并建立了G=(X,E,R)中任两点的连通强度和R的传递闭包t(R)之间的关系:定理3.3设X={x<,1>,x<,2>,…,x<,n>},R=(r<,ij>)<,nxn>是X上的模糊相似关系,R的传递闭包t(R)=R=(r<,ij><(n)>)<,nxn>,G=(X,E,R)是与〈X,R〉相对应的模糊关系图,则t(R)(x<,i>,x<,j>)=r<,ij><(n)>=S(x<,i>,x<,j>).由此仿照图论中求赋权连通图最小支撑树的Dijkstra算法,给出了模糊聚类的最大支撑树算法如下:设模糊相似矩阵R=(r<,ij>)<,nxn>,聚类水平为λ,令A<,k>表示树的结点集,记r<,ij>=r(x<,i>,x<,j>).(1)任选一点v<,1>∈X,记A<,1>={v<,1>},令l(v<,1>)=0,p(v<,1>)=φ,l(v):=r(v<,1>,v),p(v):=v<,1>(Vv∈XA<,1>),k:=1.(2)算max<,v∈XA<,k>> l(v)设=l(v<*>),令A<,k+1>=A<,k> ∪{v<*>},对每个v∈XA<,k+1>,若r(v<*>,v)>l(v),则l(v)=r(v<*>,v),p(v)=v<*>.(3)若k=n-1,据指针p(·)倒向追踪得最大支撑树T;T去掉w(e)<λ的所有边e后的各连通分支即为X在λ水平上的一个分类,停.否则,令k:=k+1,回(2).而且其复杂性仅为O(n<2>),最后通过实例进行了验证.第四章讨论灰色关联聚类分析及其传统的逐行检查法,分析用这种方法进行灰色关联聚类的复杂性为O(m<4>).仿照模糊聚类分析的最大支撑树方法中连通强度的定义和相关结论,给出了赋权图G=(V,E,D)中两点u,v间的连通强度S(u,v)及其最大支撑树的一个性质.定义了G=(V,E,D)的λ-截图G<,λ>和连通闭包G两个概念,得到了如下结论:定理4.2设赋权图G=(V,E,D),则任取λ∈[0,1],G<,λ>=G<,λ>.由此分析说明了指标集X中两点u,v在λ水平上能够归为一类,等价于它们在关联图G=(X,E,A)的最大支撑树T的λ-截图T<,λ>中连通.据此建立了灰色关联聚类的最大支撑树方法,其复杂性仅为O(m<2>),有效降低了运算的复杂性,最后通过实例进行了验证.