模糊集理论及其应用第三章

1模糊集理论及其应用陈水利第三章模糊关系与模糊聚类分析2第三章模糊关系与模糊聚类分析3.1模糊关系及其运算(P3~10)3.2模糊等价关系及其性质(P11~18)3.4基于模糊等价矩阵的模糊聚类分析

(P19~33)3.5基于目标函数的模糊ISODATA聚类分析

(P34~39)31119343§3.1模糊关系及其运算3.1.1普通关系与Boole矩阵定义3.1.1

设U,V

为两个论域,若R∈P(U×V),则称R为U到V的一个普通关系.

若(u,v)∈R,则称u对v有关系R,记作uRv;

若(u,v)

R,则称u对v没有关系R,记作

;

若U=V,且R∈P(U×V),则称R为U上的普通关系.

例如设U表示某校全体学生的集合,

R={(u,v)|v是u的同学}.则R表示U上的“同学”关系

目录4

定义3.1.2

设U={u1,u2,…,um},V={v1,v2,…,vn},R∈P(U×V),令rij=R(ui,vj)(i=1,2,…,m;j=1,2,…,n),则R=(rij)m×n

为一个m×n

矩阵,由于故R=(rij)m×n是一个布尔矩阵

.

这说明:有限论域间的普通关系可由Boole矩阵来表示.53.1.2模糊关系与模糊矩阵定义3.1.3

设U,V

为两个论域,若R∈F(U×V)则称R为U到V的一个模糊关系.对(u,v)∈U×V,称R(u,v)为u对v具有模糊关系R的相关程度.特别地

(1)称R∈F(U×U)为U上的模糊关系;(2)若

(u,v)∈U×U,有则称R为U上的恒等关系

,这时记R=I;(3)若

(u,v)∈U×V,

有R(u,v)=0,则称R为U到V的零关系

,这时记R=0;(4)若

(u,v)∈U×V,有R(u,v)=1,则称R为全称关系

,这时记R=E.目录6

由定义可见,R(u,v)反映了u对于v的相关程度,若R(u,v)越接近于1,则u与v对R的关系越密切;若R(u,v)越接近于0,则u与v对R的关系越稀疏.特别地,当R(u,v)∈{0,1}时,与u与v对R具有明确关系.因此,模糊关系是普通关系的推广,它能从更深刻的意义上表现出事物的更广泛的联系.

定义3.1.4

设U={u1,u2,…,um},V={v1,v2,…,vn},R∈F(U×V),则可以用一个m×n阶矩阵来表示,即R=(rij)m×n

,其中rij=R(ui,vj)(i=1,2,…,m;j=1,2,…,n),

由于R(ui,vj)∈[0,1],故称R=(rij)m×n为模糊矩阵

.

由于{0,1}[0,1],故模糊矩阵是Boole矩阵的推广.73.1.3模糊关系的运算

由于模糊关系R∈F(U×V),故模糊关系的运算其实就是模糊集合的运算,有关模糊集合的一切性质对模糊关系来说都成立.

定义3.1.5

设R,Q

为U到V的两个模糊关系,则

(1)称R∪Q为R与Q的并,其相关函数为(R∪Q)(u,v)=R(u,v)∨Q(u,v),

(u,v)∈U×V.(2)称R∩Q为R与Q的交,其相关函数为(R∩Q)(u,v)=R(u,v)∧Q(u,v),

(u,v)∈U×V.(3)称R

为R的补,其相关函数为R

(u,v)=1－R(u,v),

(u,v)∈U×V.

目录8(4)称RT∈F(V×U)为R的转置,其相关函数为RT(v,u)=R(u,v),

(u,v)∈U×V.(5)对

∈[0,1],,称R

={(u,v)∈U×V|R(u,v)≥

}.为R的

截关系

;而称RS

={(u,v)∈U×V|R(u,v)>

}.为R的

强截关系

.(6)对

∈[0,1],称

R为数

与模糊关系R的模糊截积关系,其相关函数为

(

R)(u,v)=

∧R(u,v),

(u,v)∈U×V.93.1.2模糊关系与模糊矩阵下面介绍模糊转置关系的运算定理3.1.1

设R,Q∈F(U×V)则有

(1)复原律:(RT)T=R;(2)交换律:(R∪Q)T=RT∪QT,(R∩Q)T=RT∩QT;(3)单调性:R

Q

RT

QT;(4)

∈[0,1],(RT)

=(R

)T,(RT)S

=(RS

)T

;(5)(RT)

=(R

)T.目录10

例3.1.1

设U={u1,u2,u3},R,Q∈F(U×U),且目录11

定义3.1.6

设R∈F(U×V),Q∈F(V×W),则对R,Q的合成R◦Q∈F(U×W),定义为

R◦Q(u,w)=∨v∈V

[R

(u,v)∧Q(v,w)](1)若R∈F(U×U),则记R0=I,Rn=Rn-1◦

R(n=1,2,…);(2)若R=(rij)m×n,Q=(qjk)n×l,则R◦Q=(pik)m×l,其中即pik为R中第i行的元素与Q中第j列的元素对应取小后再取大而得到.目录12

例3.1.2

设U={u1,u2,u3,u4}为生产资料商品集,V={v1,v2}为两种消费品的集合,W={w1,w2,w3}为三个市场的细分,以R表示U到V的原料供应关系,以Q表示V到W的市场占有关系.若取试求生产资料对市场的间接占有关系R◦Q.13解:

由定义3.1.6(2)知14

下面介绍模糊合成运算的一些基本性质

定理3.1.2

设P,Q,R为三个模糊关系,且可进行合成运算,则有

(1)结合律:R◦(Q◦P)=(R◦

Q)

◦

P(2)分配律:(R∪Q)

◦P=(R◦P)

∪(Q◦P),

P◦(R∪Q)

=(P

◦R

)∪(P

◦Q);(3)单调性:R

Q

R◦P

Q◦P(4)(R∩Q)

◦P

(R◦P)

∩(Q◦P),P◦(R∩

Q)

(P

◦R

)∩(P

◦Q).

注3.1.1:定理3.1.2(4)中两个式子的等号一般不成立.

目录15

例如:

取则故(R∩Q)

◦P

≠(R◦P)

∩(Q◦P)

注3.1.2

对于合成运算来说,不满足交换律.

例如取故R◦Q≠

Q◦R.目录16定理3.1.3

设R∈F(U×V),Q∈F(V×W),则(1)(R◦Q)T=

QT

◦RT;

(2)若R∈F(U×U),则(Rn)T=(RT)n

,

n∈

N.定理3.1.4

设R∈F(U×V),Q∈F(V×W),

∈[0,1],有(1)(R◦

Q)S

=RS

◦

QS

;(2)R

◦

Q

(R◦

Q)

(3)若V为有限论域,则(R◦

Q)

=R

◦

Q

.定理3.1.5

设R∈F(U×V),Q∈F(V×W),则

R◦

Q=∪

∈[0,1](R

◦

Q

).17§3.2模糊等价关系及其性质

3.2.1模糊关系的自反性定义3.2.1

设R∈F(U×U),则

(1)R称为自反的,如果I

R,即

u∈U,R(u,u)=1;(2)称包含R的最小的自反模糊关系为R的自反闭包,记作r(R).

例3.2.1

设U={u1,u2,u3},R∈F(U×U),

且则R为自反模糊矩阵.

目录18

定理3.2.1

设R∈F(U×U),,则下列结论成立;(1)若R是自反的,则

n∈N,Rn

Rn+1

且Rn也是自反的;(2)R是自反的当且仅当

∈[0,1],R

是自反的;(3)r(R)=R

∪

I.

3.2.2模糊关系的对称性定义3.2.2

设R∈F(U×U),则

(1)R称为对称的,如果RT=

R

;(2)称包含R的最小的对称模糊关系为R的对称闭包,记作S(R).19

例3.2.2

设U=(－∞,＋∞),R∈F(U×U),且

R

(u,v)=e－|u+v|,

(u,v)∈U×U,则R为U上的对称模糊关系.

显然,有限论域上的对称模糊关系可用对称模糊矩阵来表示.

例如设U={u1,u2,u3},R∈F(U×U),

且则R为U上的对称模糊矩阵.目录20

定理3.2.2

设R,Q∈F(U×U),则下列结论成立:(1)R是对称的当且仅当

∈[0,1],R

是对称的

(2)若R是对称的,则

n∈N,Rn也是对称的

(3)若R,Q是对称的,则

R◦

Q为对称的当且仅当R◦

Q

=

Q

◦

R(4)S(R)=R∪RT213.2.3模糊关系的传递性定义3.2.3

设R∈F(U×U),则

(1)R称为传递的,如果R◦

R

R(2)称包含R的最小的传递模糊关系为R的传递闭包,记作t(R).

例3.2.3

设U={u1,u2,u3},R∈F(U×U),且则R2=

R,故R是传递的模糊矩阵.目录22定理3.2.3

设R∈F(U×U),

则下列结论成立:(1)R为传递的当且仅当

∈[0,1],R

为传递的(2)若R为传递的,则

n∈N,Rn也为传递的;(3)23因对任意固定的k,有目录24

定理3.2.4

设U={u1,u2,…,un},R∈F(U×U),

则有

(1)(2)若R是自反的,则

m≥n,有t(R)=Rm

由此可见,当R为自反模糊关系时,必有自然数m≥n,使t(R)=Rm

下面介绍一种快速求m的方法------平方自合成法

:

第一步:

R◦

R=R2

R,则t(R)=R;否则,进行如下第二步.

第二步:

R2

◦

R2=R4

R2

,则t(R)=R2

;否则,进行如下第三步.

第三步:

R4

◦

R4=R8

R4

,则t(R)=R4

;否则,进行如下一步,如此继续下去,必有自然数k,使2k-1

<n

≤2k且

R

R2

R4

…

R2k=t(R)即对于n阶自反模糊矩阵,至多只需进行k=[log2n]+1步平方合成运算就可达到t(R),因此,可取m=2k

,k=[log2n]+1这里[log2n]表示不超过log2n的最大整数.

例如当n=30时,至多只需平方合成5次便可达到目的.目录25

例3.2.4

设目录26

解:27下面介绍传递闭包的一些基本性质定理3.2.5

设I,R,Q∈F(U×U),则有(1)t(I)=I;(2)R

Q

t(R)=t(Q)(3)(t(R))T=t(RT)(4)RT=R

(t(R))T=t(R)283.2.4模糊关系的相似性定义3.2.4

设R∈F(U×U),

则(1)R称为相似的,如果R是自反和对称的;(2)称包含R的最小的相似模糊关系为相似闭包,记作a(R).例3.2.5

设U={u1,u2,u3},R∈F(U×U),且则R是自反且对称的,故R为相似模糊矩阵.定理3.2.6

设R∈F(U×U),则有(1)R为相似的当且仅当

∈[0,1],R

为相似的;(2)若R为相似的,则

n∈N,Rn也是相似的.目录293.2.5模糊关系的等价性定义3.2.5

设R∈F(U×U),

则

(1)R称为等价的,如果R是自反、对称和传递的

(2)称包含R的最小的模糊等价关系为R的等价闭包,记作e(R).

由定理3.2.1~定理3.2.3立即可证如下结论定理3.2.7

设R∈F(U×U),则

(1)R为等价的当且仅当

∈[0,1],R

为等价的

(2)若R为等价的,则

n∈N,Rn也是等价的

(3)R为等价的当且仅当R为传递的模糊相似关系

(4)若R为模糊相似关系,则t(R)=e(R)目录30§3.4基于模糊等价矩阵的模糊聚类分析

设被分类对象的集合为U={u1,u2,…,un},每一个对象ui有m个特性指标(即反映对象特征的主要指标),并记ui

=(ui1,ui2,…,uim),i=1,2,…,n其中uij表示第i个对象的第j个特性指标,则n个对象的所有特性指标构成一个矩阵,记作称U*为U的特性指标矩阵.目录313.4.1数据规格化常用的数据规格化方法有如下几种:

1.数据标准化

(i)对特性指标矩阵U*的第j列,计算

(ii)作变换则以u

ij作为元素的特性指标矩阵就是数据规格化的特性指标矩阵,记作U*

=(u

ij)n×m目录322.均值规格化(i)对U*的第j列,计算(ii)作变换则U*

=(u

ij)n×m为规格化后的特性指标矩阵.

还有中心规格化、最大规格化、极差规格化、对数规格化等,这些方法参见教材.333.4.2构造模糊相似矩阵设数据u

ij(i=1,2,…,n;j=1,2,…,m)均已规格化,下面用多元分析的方法来确定对象ui=(u

i1,u

i2,…,u

im)和uj=(u

j1,u

j2,…,u

jm)之间的相似程度rij

=R(ui,uj)[0,1],(i=1,2,…,n;j=1,2,…,m)从而构造出一个对象与对象之间的模糊相似矩阵目录34下面介绍几种确定的常用方法.1.相似系数法相似系数法包括:数量积法、夹角余弦法、相关系数法、指数相似系数法、非参数相似程度法等等,例如,(2)夹角余弦法(3)相关系数法352.距离法设d(ui,uj)表示对象ui和uj的距离,则d(ui,uj)越大,rij就越小,而d(ui,uj)越小,rij就越大。一般地,可取rij=1－c(d(ui,uj))

其中c和

是两个适当选取的正数,使rij∈[0,1]。在实际应用中,常采用如下距离来确定rij目录36373.贴近度法当对象ui=(ui1,ui2,…,uim)为模糊向量(即uik∈[0,1])时,ui与uj的相似程度rij可由如下方法确定(1)最大最小法(2)算术平均最小法(3)几何平均最小法目录384.主观评定法在一些实际问题中,被分类对象的特性指标是定性指标,这是可请有关专家和有实际经验的人员用评分的办法来主观评定被分类对象间的相似程度。3.4.3模糊分类下面我们介绍四种常用的模糊分类方法.1.模糊传递闭包法(1)利用平方自合成方法求(2)对t(R)中的元素从大到小进行排序,设为1=

1>

2>

>

m39(3)

对

=

i(i=1,2,…,m),求出t(R)的

-截矩阵然后按t(R)

进行分类,所得到的分类就是在

水平上的等价分类,具体聚类原则为:若,则在

水平上将对象ui和对象uj归为同一类.(4)

画动态聚类图为了能直观地看到被分类对象之间的相关程度,通常将t(R)中所有互不相同的元素

=

i(i=1,2,…,m)水平上的等价分类画在同一个图上,即得动态聚类图.目录40

例3.4.1

考虑某环保部门对该地区五个环境区域U={u1,u2,u3,u4,u5},按污染情况进行分类,设每个区域包含空气、水分、土壤、作物四个要素,环境区域的污染情况有污染物在四个要素中的含量超过的程度来衡量。设这五个环境区域的污染数据为

u1=(80,10,6,2),u2=(50,1,6,4),u3=(90,6,4,5),

u4=(40,5,7,3),u5=(10,1,2,4)试用模糊传递闭包法对U进行分类。41

解:由题设知特性指标为污染物在空气、水分、土壤、作物这四个要素中的含量.其特性指标矩阵为

(1)数据规格化采用最大值规格化,作变换把U*规格化为目录42(2)构造模糊相似矩阵R=(rij)5×5

采用最大最小法,即确定模糊相似矩阵为43(3)利用平方合成法求t(R)

因为而R8=R4,所以(4)选取适当的置信水平值

∈[0,1],按

截矩阵进行t(R)

动态聚类首先把t(R)中的元素从大到小排序为1>0.70>0.63>0.62>0.53目录44①取

=1,得根据分类原则,U被分成五类:{u1},{u2},{u3},{u4},{u5}.

②取=0.70,得因为根据分类原则,U被分成四类:{u1},{u2,u4},{u3},{u5}.③取

=0.63,得因为根据分类原则,被分成三类:{u1,u2,u4},{u3},{u5}.同理可得,取

=0.62,可得U被分成二类:{u1,u2,u3,u4},{u5}.取

=0.53,可得U被分成一类:{u1,u2,u3,u4,u5}.

目录45(5)画动态聚类图目录462.直接聚类法(1)将模糊相似矩阵中的所有不同的元素从大到小排序,设为1=

1>

2>

>

m(2)选取

=

k(k=1,2,…m)

直接在R上找出

k水平上的相似类.并进行归并,即得到

k水平上的等价分类.

寻找相似类和归并的原则:若rij≥

k,则将ui与uj分为同一类,设B1,B2是

k水平上的两个类,若B1∩B2≠

,则称它们为相似的,将所有相似类的类合成一类,最后得到的分类就是

k水平上的等价分类.(3)画动态聚类图47

例3.4.2

利用直接聚类法对例3.4.1中给出的环境区域

U={u1,u2,u3,u4,u5},进行等价分类.

解:由例3.4.1知模糊相似矩阵为

(1)将R中的元素进行排序为

1>0.70>0.63>0.62>0.56>0.55>0.54>0.53>0.38>0.37>0.24(2)取

=1,因相似程度为1的元素只有自己,故U被分成五类:{u1},{u2},{u3},{u4},{u5}.

取

=0.70,因r24=r42=0.70,故得相似类为{u2,u4},{u1},{u2},{u3},{u4},{u5}.48将所有相似的类合并成一类,即得等价类为:{u2,u4},{u1},{u3},{u5}.

取

=0.63,因r14=r41=0.63,故得相似类为{u2,u4},{u1,u4},{u1},{u3},{u5}.将所有相似的类合并成一类,即得等价类为:{u1,u2,u4},{u3},{u5}.

取

=0.62,因r13=r31=0.62,故得相似类为{u1,u3},{u1,u2,u4},{u3},{u5}.将所有相似的类合并成一类,即得等价类为:{u1,u2,u3,u4},{u5}.

同理可得,当

=0.56,0.55,0.54时所有的等价类与

=0.62的等价类相同.

取

=0.53,

因r25=r52=0.53,故得相似类为{u2,u5},{u1,u2,u3,u4},{u5}.将所有相似的类合并成一类,即得等价类为:{u1,u2,u3,u4,u5}.目录49

由此可见,利用模糊传递闭包法和利用直接聚类法所得到的等价类是一致的。3.最大树法

(1)以所有被分类的对象为顶点。

(2)当rij≠0时,将顶点ui与顶点uj用一条线连接起来,并在线段上注明相关程度rij,具体画法如下:

首先画出顶点集中处的某个顶点ui,然后按rij从大到小的顺序依次连边,并在线段上注明相关程度rij,在连边时要求不产生回路,不出现相交线,直到所有对象连通为止。这样就得到一棵最大树(注:由于连边方法不唯一,从而这种最大树不是唯一的)。

(3)适当选取

∈[0,1],砍去线段上值小于

的连线,剩下互相连通的对象归为同一类。这样就可得到在水平上的一种等价分类。

(4)画出动态聚类图。目录50

例3.4.3

利用最大树法对例3.4.1中给出的环境区域U={u1,u2,u3,u4,u5},进行等价分类解:(i)构造一棵最大树首先将例3.4.1中的模糊相似矩阵R中的元素从大到小进行排序为1>0.70>0.63>0.62>0.56>0.55>0.54>0.53>0.38>0.37>0.24

然后根据构造最大树的方法可得一棵最大树为51(ii)进行等价分类取

=1,切掉线段上值小于1的连线,得到图3.4.3,这时U被分为五类:{u1},{u2},{u3},{u4},{u5}.取

=0.70,切掉线段上值小于0.70的连线,得到图3.4.4,这时U被分为四类:{u2,u4},{u1},{u3},{u5}.

取

=0.63,切掉线段上值小于0.63的连线,得到图3.4.5,这时U被分为三类:{u1,u2,u4},{u3},{u5}.目录52

取

=0.62,切掉线段上值小于0.62的连线,得到图3.4.6,这时U被分为二类:{u1,u2,u3,u4},{u5}.

取

=0.53,切掉线段上值小于0.53的连线,得到图3.4.7,这时U被分为一类:{u1,u2,u3,u4,u5}.

由此可见,利用最大树法进行等价分类与利用模糊闭包法是一致的。

(iii)画动态聚类图(与图3.4.1一致)目录534.编网法

(1)适当选取

∈[0,1],求出

截矩阵R

,且去掉R

的主对角线右上半部分的所有元素;(2)将主对角线上的”1”对应地用其对象ui的标号i来代替；

(3)将主对角线左下方的”0”去掉,而用”

”代替”1”,而称

所在的位置为结点;(4)用竖直线与横直线将结点与对角线上的序号连接,即编网。通过如此打结而连接的对象归为同一类,从而实现了等价分类；

(5)画动态聚类图。54

例3.4.4

利用编网法对例3.4.1中给出的U={u1,u2,u3,u4,u5},进行分类.

解见教材.

注:在应用模糊等价矩阵聚类分析方法解决实际问题时,有两点是值得注意的:

1.

如何选择计算相关程度rij=R(ui,uj)的合运算子?因为一般来说,当选择不同的算子计算rij时,所得到的模糊分类可能也不同。

2.

如何选择最佳的置信水平

i进行等价分类?因为应用模糊等价矩阵进行分类的类数取决于

i的选择。在教材中,我们介绍了利用传递偏差选择最佳计算相关程度rij的算法,以及利用

-偏差度选择最佳置信水平

i的算法.目录55§3.5基于目标函数的模糊ISODATA聚类分析3.5.1普通分类设被分类对象集为U={u1,u2,…,un},其中每个对象有m个特性指标,设为ui=(ui1,ui2,…,uim)如果要把U分成c类(2≤c≤n),则分法不唯一,且每种分法都对应一个c×n阶的Boole矩阵,这里R=(rij)c×n,

例如:设U={u1,u2,u3,u4,u5},把U分成如下三类{u1,u4},{u2,u5},{u3}则对应的分类矩阵为目录56此矩阵有如下特性

反之,任一满足上述三条特性的Boole矩阵R都对应着一种分类.

例如:

对应的分类为:{u2,u4},{u3,u5},{u1}573.5.2模糊分类在实际问题中，对象ui∈U往往不是严格地归属于某一类,而是以一定的隶属度隶属于某一类,因此,每一类可认为是U上的一个模糊子集.如果对象集U被分成c类,则每一种分类结果对应的矩阵是一个模糊矩阵,即R=(rij)c×n其中rij(i=1,2,…,c;j=1,2,…,n)满足下列三条性质反之,任一满足上述三条性质的矩阵R都对应着U的一种模糊分类.于是,研究模糊分类问题可归结为研究满足上述三条性质的模糊矩阵问题.

目录58记Mfc为所有满足上诉三条性质的模糊矩阵的集合,即Mfc

={R

Vc×n

|R满足