第三章模糊关系与聚类

13.F关系与聚类分析

3.1F关系的定义和性质

3.2F矩阵

3.3F关系的自反性与对称性

3.4λ截集

3.5F关系合成

23.F关系与聚类分析

3.6F关系的传递性

3.7F等价关系及聚类图

3.8F相似关系

3.9F聚类分析

3三、

模糊关系合成运算性质：(1)合成运算满足结合律

(Q◦R)◦S=

Q◦(R◦S)，

特别地

Rm

◦Rn=Rm+n。(2)合成运算关于并“⋃”满足分配律

(Q⋃

R)◦S=(Q◦S)⋃(R◦S),(1)S◦(Q⋃

R)=(S◦Q)⋃(S◦R)。

(2)4证明只证(1)。设Q，RF

(UV),SF(VW),故有(Q⋃

R)◦S=(Q◦S)⋃(R◦S)。

5第二式证明相似。应注意的是，1)

合成运算不满足交换律，即Q◦RR◦Q。如设则因此，Q◦RR◦Q。62)合成运算对交“”不满足分配律，即有下列二式：(Q

R)◦S(Q◦S)

(R◦S),S◦(Q

R)(S◦Q)(S◦R)。

(Q

R)◦S

(Q◦S)

(R◦S),S◦(Q

R)

(S◦Q)(S◦R)。

例如：则

7因此(Q

R)◦S(Q◦S)

(R◦S)。

同样可以举出反例来说明第二个式子。◦R=R◦=,(UV)◦R=R◦(UV)=R

。

(4)

若QR，则

Q◦SR◦S

，P◦Q

P◦R,Qn

Rn8定义9:设RF

(UV

)，定义R-1F

(VU

)的隶属函数为R-1(v，u)=R(u，v)

((v，u)V

U),称V

到U

的模糊关系RT

为R的转置关系。命题4:转置关系有下述性质：设R，R1，R2

F

(UV)，{Rt|tT}F

(UV),SF

(VW

),则(1)

若R1

R2

R1T

R2T

。(2)(RT)T=R。9推论(1)设R

F

(UU

)，则

(Rn

)T=(RT)n。(2)设R，QF

(UU)且RQ,则RnQn(n为正整数)。103.6

F等价关系定义10:设R

F

(U

U

)(1)

称R是自反的

uU，R(u,u)=1。(2)

称R是对称的

u,vX

，R(u,v)=R(v,u)。(3)若R是U

上的自反、对称关系，则称R是U

上的模糊相似关系，简称相似关系。11命题5

设R

F

(UU)，则(1)

R是自反的

IR。(2)R是自反的

RnRn+1(n1)

且Rn也是自反的。证明(1)

显然。12(2)

用归纳法证明包含式RnRn+1。(u,v)UU,有故R

R2。设Rn-1

Rn，由（7）式可得Rn-1

◦R

Rn◦R,即RnRn+1。因

IR

Rn(n1)，由(1)知Rn是自反的。13命题6

设R，R1，R2

F

(UU

)，则有(1)R是对称的R=RT。(2)

若R1、R2都是对称的，则R1

◦R2对称

R1

◦R2=

R2

◦R1(即

R1、R2是可以交换的）。(3)R是对称的Rn是对称的(n1)。证明(1)由对称关系的定义可得。14(2)先证()：若R1

◦R2

是对称的，因R1、R2也对称，故R1

◦R2=(R1

◦R2)-1=R2-1

◦R1-1=R2

◦R1。再证()：若R1

◦R2=

R2

◦R1，则

(R1

◦R2)-1=R2-1

◦R1-1=R2

◦R1=R1

◦R2由(1)知，R1

◦R2是对称的。

(3)若R对称，则有(Rn

)-1=(R-1)n

=Rn。由(1)知，Rn是对称的。15推论

(1)若R是U上的相似关系，则Rn也是U上的相似关系。

(2)设RF

(UU)是任一模糊关系，则R

◦RT是U上的对称关系。证明因(R

◦RT)T=(RT

)T◦RT=R

◦RT，由命题

(1)知，R

◦RT是对称的。16定义11

设R

F

(U

U

)，

R为传递的

[0，1]，u，v，wU，

R(u,v)，R(v,w)，则R(u,w)。命题7

设R，R1，R2

F

(U

U

)，则(1)R是传递的

R2R。(2)若

R是传递的

Rn是传递的(n1)。(3)R1、R2

是传递的

R1

R2

是传递的。17证明(1)

先证()：设u，vU，tU，令t=R(u,t)R(t,v)，则R(u，t)t，R(t，v)t

。由于R是传递的,故R(u,v)t(tU)，于是18由u，v

的任意性知

R2R再证()：若R2R且R(u，v)，R(v，w)

于是由定义11知

R是传递的。19(2)

若R是传递的，则由(1)有R2R，进一步由(7)右边一式得(R2)n

Rn又由

(Rn)2=(R2)n

，联合上面两式，得

(Rn)2=(R2)n

Rn，最后由(1)知Rn是传递的。20(3)我们可以用两

式证明(Q⋂

R)◦S(Q◦S)

(R◦S),S◦(Q⋂

R)

(S◦Q)(S◦R)。应用上面两式，得(R1

R2)2=(R1

R2)◦(R1

R2)(R1◦(R1

R2))

(

R2◦(R1

R2))

(R1◦

R1)

(R1◦

R2)

(R2◦

R1)(R2◦

R2)21R12

R22。因为，R1、R2是传递的，即R12

R1、R22

R2，则有

(R1

R2)2R1

R2

，所以，R1

⋂R2是传递的。22

模糊传递闭包和等价闭包

通常的模糊关系，不一定具有传递性，因而不是模糊等价关系。对这种模糊关系直接进行分类显然是不合理的。为此，我们希望寻求一种方法，能将不是等价的模糊关系进行改造，以便分类使用。23

定义13

设RF

(UU

)，称t(R)

为R

的传递闭包，如果t(R)

满足:(1)传递性：(t(R))2

t(R)；(2)包容性：Rt(R)；(3)最小性：若R′是U

上的模糊传递关系，且

RR′t(R)

R′，即R的传递闭包是包含R的最小的传递关系。24定理2:设RF

(UU

)，则证明：(1)首先证明是传递的，即要证明25由传递性定义知，是传递的。26(2)显然有(3)

若有R’

使RR’且R’是传递的，则由RR’

有

R2(R’)2R’,

R3=R◦R2R◦R’(R’)2R’,

……一般有RnR’,从而27即含于任一包含R的传递关系中。综上所述，是包含R的最小传递关系，因而是R的传递闭包，即28

在论域为有限集的情况下，传递闭包的计算变得很简捷。命题8

设|U|=n，RF

(U

U

)

，则证明略。29推论设|U

|=n，RF

(UU

)

，且R是自反关系，则存在正整数m(n)

，使t(R)=Rm，且

l>m有Rl=t(R)。证明因为|U|=n，所以又因为R是自反的，由命题(2)知R

R2

R3……,

30因而在做上述合成运算时，若做到

m(n)

次时，出现了Rm+1

=Rm，则有Rm+2

=Rm，进而，t(R)=Rm。这时，若我们取正整数

l>m，则有31即有Rl=t(R)。上述推论说明，在计算有限论域上自反的模糊关系R的传递闭包时，可以从R开始，反复自乘，依次计算出R，R2，R4，…，

，…，当第一次出现Rk◦Rk=Rk时，就有t(R)=Rk。32命题9

模糊关系的传递闭包t(R)

有以下性质：(1)

若IR，则It(R)

。(2)

(

t(R))T=t(R

T)。(3)若R

T=R，则(

t(R))T=t(R)

。证明

(1)由定理2可得。

(2)由定理2、命题4(3)及推论(1)，有

33(3)由(2)即得。上述命题中的(1)说明自反关系的传递闭包还是自反的，(3)表明对称关系的传递闭包还是对称的。34定义14:

设RF

(U

U)，称e(R)

为R的等价闭包，若e(R)

满足下述条件：(1)等价性：e(R)

是X上的模糊等价关系。(2)包容性：Re(R)。(3)最小性：若R’

是X上的模糊等价关系，且

RR’e(R)R’

。显然，R的等价闭包是包含R的最小的等价关系。35例8

给定有限论域上的模糊关系R如下：则由于模糊矩阵R2的元素不超过R对应位置上的元素36因而模糊关系R2R，故R是传递的。命题:

设R是U

上的一个自反的和传递的模糊关系，则有R=R2。证明因为R是自反的，则有，RR2。又因为R是传递的，则

有，R2R，故有R=R2。37定义12

设RF

(U

U

)，若R满足下列三个条件，则称R是U上的一个模糊等价关系：(1)

自反性：uU，R(u，u)=1。(2)

对称性：u，vU，R(u，v)=R(v，u)。(3)

传递性：

R2R，即u，wU

U，有38

若U={u1,u2,…,un}为有限论域时，U上的模糊等价关系R是一个矩阵（称为模糊等价矩阵），它满足下述三个条件：(1)

自反性：rii=1,i=1,2,…,n。(2)

对称性：rij=rji，i，j=1,2,…,n。(3)传递性：

R

◦RR，即

39

条件(1)说明模糊矩阵的对角线元素都是1；条件(2)意味着模糊等价矩阵是对称矩阵。40定理3:

设R

F

(UU

)，则R是模糊等价关系[0，1]，R是经典等价关系，这里R={(u,v)U

U

|R(u,v)}为R的截关系。且对于，[0，1]，>，有等价类

R[u]R[u](uU

)。证明略。41

本定理说明，若R是U

上的模糊等价关系，则其截关系是经典等价关系，它们都可将U

作一个划分，当从1下降到0时，就得到一个划分族，而且由于>时，

R[u]R[u]，即R给出的分类结果中的每类，是R给出的分类结果的子类，所以R给出的分类结果比R给出的分类结果更细。随着的下降，

R给出的分类越来越粗，这样就得到一个动态的聚类图，我们可以根据实际情况的需要，选择某个水平上的分类结果。这是模糊聚类分析的一大优越性42例:

设U={x1，x2，x3，x4，x5}，R是U上的一个模糊关系，其对应的模糊矩阵为在上面的矩阵中，对角线元素为1，即rii=1，所以R是自反的。又因R与其转置矩阵相同，故3.7F动态聚类图43rij=rji，R

=R-1，即R是对称的。由于即R◦R=R2R，R是传递的，故R是模糊等价关系。44

依次取截关系R，R是经典等价关系，它诱导出U

上的一个划分U/R，将U

分成一些等价类。当=1时，R1诱导的分类为五类：{x1},{x2},{x3},{x4},{x5}。45当=0.8时，R0.8诱导的分类为四类：{x1，x3},{x2},{x4},{x5}。46当=0.6时，R0.6诱导的分类为三类：{x1,x3},{x2},{x4,x5}。47当=0.5时，R0.5诱导的分类为两类：{x1,

x3,

x4,x5},{x2}。48最后，当=0.4时，R0.4将X分成一类：{x1,

x2,

x3,

x4,x5}。49

随由大到小，分类由细到粗，形成一个动态的分类图，如图

所示：

x1x3x4x5x2=1

0.80.60.50.4

图

动态聚类图50

教材

P75

用归并相似类法给出了同样的分类。求模糊相似关系的等价类有以下三种方法：等价闭包法(e(R))——间接法归并相似类法最大树法直接法513.9

模糊聚类分析模糊聚类分析在实际问题中有广泛的应用，这是由于实际问题中，一组事物是否属于某一类常带有模糊性，也就是问题的界限不是十分清晰的。我们不能明确地回答“是”或“否”，而是只能作出“在某种程度上“是”或“否””的回答，这就是模糊聚类分析。本节主要讨论基于模糊等价关系的动态聚类的实际应用。521.特征抽取假设待分类对象的集合为U={U1,U2,…,Un}，集合中的每个元素具有m个特征，设第i个对象Ui

的第j(j=1,2,…,m)个特征为xij，则Ui就可以用这m个特征的取值来描述，记Ui=(xi1,xi2,…,xim)

(i=1，2，…，n)53

为了计算简便，并使特征仅具有相对的意义，我们要首先对特征的观测值进行预先处理，使各特征值的取值在单位区间[0,1]中。设

Ui的观测值为Xi0，Ui0=(xi10，xi20，…，xim0)(i=1,2,…,n)所以用下列各公式对Ui0进行“规格化”的预处理。54(1)

xij=cxij0(i=1,…,n；

j=1,…,m)c是一个常数，选择

c

使任何

xij在[0,1]中。(2)

xij=cxij0/max(xij0)(i=1,…,n;j=1,…,m)即选择所有的特征中的最大值作分母。(3)

当特征值中出现负值时，则用下式压缩到[0,1]：55当特征值不是负值时，当然也可以用上式来“规格化”式中

是全部特征值的均值，分子是特征值与均值的距离。用此式“规格化”时应注意：只要与均值的距离相等，特征值的大小的方向性就被“湮灭”。

562.建立U上的模糊关系（模糊相似矩阵）设待分类对象的全体是U={U1,U2,…,Un}，我们首先要鉴别U中的元素Ui与Uj的接近程度（相似程度）。用[0,1]中的数rij来表示Ui与Uj的相似程度，称为相似系数。相似系数组成一个矩阵(rij)nn称为相似系数矩阵，它是U上的模糊相似关系。我们对此关系矩阵求其等价闭包或等价类，就能对

U中的元素进行聚类。57

为了确定相似系数，必须使相似系数符合自反、对称的要求，可根据实际情况选用下列方法之一。1）数量积法其中582）夹角余弦法3）相关系数法其中594）指数相似系数法其中sk与

m为常数。5）绝对值指数法606）绝对值倒数法其中M

为适当选择的常数，M

的选择使rij[0,1]。617)非参数法令是xik

与xjk的均值），nij+={x’i1x’j1,x’i2x’j2,…,x’im

x’jm}中正数个数，nij－={x’i1x’j1,x’i2x’j2,…,x’im

x’jm}中负数个数，628）贴近度法贴近度表示两个模糊向量之间接近的程度，它符合自反、对称的要求，所以可以用来表示相似系数。我们将

U中的元素Ui，Uj

看成是各自特征的模糊向量，便可以用贴近度来表示相似系数rij，rij=(Ui,Uj)63(1)当取内外积贴近度时或64(2)最大最小法，当取上式时(3)算术平均最小法，当取前式时65(4)几何平均最小法，当取前式时(5)绝对值减数法，当取距离贴近度时rij=1－c(dp

(Xi，Xj))式中c，为常数，p为各种距离的代码系数。66

当

p=1时，dp

就是海明距离，此时求相似系数的方法称绝对值减数法，其相似系数为

当p=2时，dp

就是欧氏距离，此时有679）经验法请有经验的人来分别对Ui与

Uj的相似性打分，设有s个人参加评分，若第k个人(1ks)认为Ui与

Uj相似的程度为aij(k)

（在[0，1]中），他对自己评分的自信度也打分，若自信度分值是bij(k)

，则可以用下式来计算相似系数:68

在以上确定相似系数的诸多方法中，究竟选用哪一种合适，需要根据问题的具体性质来决定。693、例举

环境单元分类每个环境单元可以包括空气、水分、土壤、作物等四个要素。环境单元的污染状况由污染物在四要素中含量的超限度来描写。假设有五个单元x1,x2,x3,x4,x5，它们的污染数据如表3.13所示。70

取论域

U={x1,x2,x3,x4,x5}，按上式“规格化”，取

c=0.1，再按前式求相似系数（取

c=1)，

要素数据单元空气水分土壤作物x1x2x3x4

x552512535543423525311表13污染数据71得到模糊相似矩阵72

聚类方法可以有三种方法来对模糊相似矩阵聚类。1）传递闭包法（平方法）求出模糊相似矩阵的传递闭包t(R)，它就是R的等价闭包

e(R)=t(R)，然后求其

截关系

e(R)。它是经典等价关系，让

从1降至0，当变化时，它们给出一个动态的分类结果。求R

的传递闭包

t(R)时，可以用平方法，即求R2,R4,…,Rk，若有Rk

Rk=Rk，则t(R)=Rk。73经计算可知74当=1时，分成五类：{x1},

{x2}

,{x3},{x4},{x5}当=0.8时，分成四类：{x1,x3},

{x2}

,{x4},{x5}当=0.6时，分成三类：{x1,x3},

{x2}

,{x4,x5}当=0.5时，分成二类：{x1,x3,x4,x5},

{x2}当=0.4时，分成一类：{x1,x2,x3,x4,x5}75其动态分类如下图

所示：=1x1x3

x4

x5

x20.80.60.50.4图

动态聚类图762）直接聚类法根据模糊相似矩阵

来直接由相似类求等价类。当=1时，该矩阵只有对角线上的元素为1，所以不许归并相似类，所得到的e(R)1

的等价类为{x1}，{x2}，{x3}，{x4}，{x5}。当=0.8时，先求经典矩阵R0.8，有此求得它的相似类是77R0.8[x1]={x1,x3}，R0.8[x2]={x2}

，R0.8[x4]={x4}，R0.8[x5]={x5}。在归并时，找不到与{x1,x3}相交的其它等价类，于是e(R)0.8的等价类为：

{x1,x3},

{x2}

,{x4},{x5}。同样=0.6时，相似类为R0.6[x1]={x1,x3},R0.6[x2]={x2},R0.6[x4]={x4,x5}，也无法再进一步归并，于是e(R)0.6的等价类为：

{x1,x3},

{x2}

,{x4,x5}。78

当=0.5时，相似类为R0.5[x1]={x1,x3,x4}，R0.5[x2]={x2},R0.5[x4]={x1,x4,x5}，因此可以把相似类R0.5[x1]与

R0.5[x4]归并，得

P1(x1)=R0.5[x1]R0.5[x4]={x1,x3,x4,x5}，最终得到的e(R)0.5的等价类为{x1,x3,x4,x5},

{x2}。当=0.4时，得到R0.4[x2]={x2，x5}，于是可以和P1(x1)归并，即P2(x1)={x1,x2,x3,x4,x5}，这就是e(R)0.4的等价类。

793）最大树法（Kruskal）

在模糊相似矩阵

中，从=1开始逐步做连通图，直到=0时为止，每作一条边，就在边上写出

rij

之值（连通强度）。注意不要做回路。从原则上来说，可以选择任一元素（顶点）作为起始点，但一般总是选有相似类的元素开始。例如在本例中当=0.8时，就有相似类{x1,x3}，于是就把

x1选为起始顶点，先作出强度为800.8的边，然后再作强度为0.6的边及强度为0.5和0.4的边，这样就得到最大树，如下图所示。

图

3最大树x1x4x5

x2x30.80.50.60.481

在不同

水平上的分类，就是在最大树中砍去那些强度小于的边，再分类。例如=0.8时，砍掉最大树右边的各枝，就得到分类：{x1,x3},

{x2}

,{x4},{x5}；而在=0.6时，只砍掉强度为0.5和0.4的边，于是得到的分类就是：{x1,x3},