数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
- 1 -
第 6 章 模糊关系与模糊聚类分析
在自然界中,事物之间存在着这样或那样的关系,其中有些关系是非常明确的,如“父子关系”、“兄
弟关系”等等。而更多的则是界限不明显的关系,如照片与本人的“相像”关系,信息处理中各种信息的
“相近”关系,还有“朋友关系”以及“子代身高同父代身高之间的关系”等。对于这类关系用简单的“肯
定”或“否定”,即用“1”或者“0”来刻画显然是不合适的,必须将关系的值域扩充为 [0, 1],即用模糊
理论来进行描述,这就是模糊关系。
与经典关系所处的地位一样,模糊关系是模糊理论最重要的内容之一,其应用范围十分广泛,几乎遍
及模糊数学的所有应用领域。本章主要介绍模糊关系的基本理论以及它的重要应用之一——模糊聚类分
析,主要内容包括:模糊矩阵,模糊向量,模糊关系,模糊聚类分析。
6.1 模糊矩阵
如同数值矩阵在经典数学中的作用一样,模糊矩阵是建立模糊数学
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
的重要工具之一。同时,当论
域有限时,模糊关系可以用模糊矩阵来表示。
6.1.1 模糊矩阵的定义及其运算
定义 1 设 R = (rij)m×n 是一个 m×n 的矩阵,如果 A 是论域 U 到 [0, 1]上的一个映射,即
rij ∈[0, 1],1 ≤ i ≤ m, 1 ≤ j ≤ n (6.1)
则称 R 是模糊矩阵,通常一 Mm×n 来表示所有 m×n 的模糊矩阵构成的集合。
定义 2 设 R, S∈Mm×n且 R = (rij)m×n,S = (sij)m×n,则
(1) R 与 S 相等定义为:R = S ⇔ rij = sij, ∀i, j;
(2) R 包含于 S 定义为:R⊆S ⇔ rij ≤ sij, ∀i, j;
(3) R 与 S 的交定义为:R∩S = (rij ∧ sij)m×n;
(4) R 与 S 的并定义为:R∪S = (rij ∨ sij)m×n;
(5) R 的余定义为:RC = (1− rij)m×n。
例 1 设 R, S, T∈M2×2 且
⎟⎟⎠
⎞
⎜⎜⎝
⎛=
1.05.0
7.04.0
R , ⎟⎟⎠
⎞
⎜⎜⎝
⎛=
7.02.0
4.09.0
S , ⎟⎟⎠
⎞
⎜⎜⎝
⎛=
8.04.0
6.09.0
T
则由定义 2 有:S⊆T,并且
⎟⎟⎠
⎞
⎜⎜⎝
⎛=⎟⎟⎠
⎞
⎜⎜⎝
⎛
∧∧
∧∧=∩
1.02.0
4.04.0
7.01.02.05.0
4.07.09.04.0
SR , ⎟⎟⎠
⎞
⎜⎜⎝
⎛=⎟⎟⎠
⎞
⎜⎜⎝
⎛
∨∨
∨∨=∪
7.05.0
7.09.0
7.01.02.05.0
4.07.09.04.0
SR
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 2 -
⎟⎟⎠
⎞
⎜⎜⎝
⎛=⎟⎟⎠
⎞
⎜⎜⎝
⎛
−−
−−=
9.05.0
3.06.0
1.015.01
7.014.01CR
模糊矩阵的交、并、余运算满足如下算律。
定理 1 设 R, S, T, W∈Mm×n,则有
(1) 幂等律:R∩R = R,R∪R = R;
(2) 交换律:R∩S = S∩R,R∪S = S∪R;
(3) 结合律:( R∩S )∩T = R∩ ( S∩T),( R∪S )∪T = R∪ ( S ∪T );
(4) 吸收律:( R∩S )∪R = R,( R∪S )∩R = R;
(5) 分配律:R∩ ( S∪T ) = ( R∩S )∪ ( R∩T ),R∪ ( S∩T ) = ( R∪S )∩ ( R∪T );
(6) 复原律(对合律):( RC )C = R;
(7) 对偶律(De MorgRn 律):( R∩S )C = RC∪SC,( R∪S )C = RC∩SC;
(8) 零壹律:R∩O = O,R∩E = R,R∪O = R,R∪E = E,其中
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
=
000
000
000
L
MLMM
L
L
O ,
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
=
111
111
111
L
MLMM
L
L
E
(9) 单调性:R⊆S, T⊆W ⇒ R∩T ⊆ S∩W,R∪T ⊆ S∪W;
(10) 逆序性:R⊆S ⇔ SC⊆ RC;
(11) R⊆S ⇔ R∩S = R,R∪S = S。
必须指出,一般 R∩RC ≠ O,R∪RC ≠ E,即模糊矩阵的交、并、余运算不满足互补律。
模糊矩阵的交、并运算还可以推广到任意多个模糊矩阵上去。
定义 3 设 T 是指标集,R(t) = (rij(t))m×n ∈Mm×n( t∈T),则分别称
( )
nm
t
ijTt
t
Tt
rR
×∈∈
∧= )()( I 和 ( )
nm
t
ijTt
t
Tt
rR
×∈∈
∨= )()( U
为模糊矩阵 { R(t) | t∈T }的交和并。
定理 2 设 T 是指标集,S, R(t) ∈Mm×n( t∈T),则有
(1) )( )()( t
Tt
t
Tt
RSRS IUUI
∈∈
=⎟⎠
⎞⎜⎝
⎛ , )( )()( t
Tt
t
Tt
RSRS UIIU
∈∈
=⎟⎠
⎞⎜⎝
⎛ ;
(2) Ct
Tt
C
t
Tt
RR )( )()(
∈∈
=⎟⎠
⎞⎜⎝
⎛ UI , Ct
Tt
C
t
Tt
RR )( )()(
∈∈
=⎟⎠
⎞⎜⎝
⎛ IU 。
6.1.2 模糊矩阵的截矩阵
定义 4 设 R∈Mm×n,且 R = (rij)m×n。如果 Rλ = (rij(λ))m×n 满足
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 3 -
⎩⎨
⎧
<
≥= λ
λλ
ij
ij
ij r
r
r
,0
,1
)(
则称 Rλ为模糊矩阵 R 的 λ 截矩阵。
显然,模糊矩阵的 λ 截矩阵是布尔矩阵。并且容易证明:对∀R, S∈Mm×n,
(1) (R∩S )λ = Rλ ∩Sλ,(R∪S )λ = Rλ ∪Sλ;
(2) λ ≤ α ⇒ Rα ⊆Rλ;
(3) R⊆S ⇔ Rλ ⊆Sλ,∀λ∈[0, 1]。
定理 3 (模糊矩阵的分解定理)设 R∈Mm×n,且 R = (rij)m×n。则
)(
]1,0[
λλ
λRR
∈
= U (6.2)
其中 λRλ = (rλ ij)m×n,且
⎩⎨
⎧
<
≥=∧= λ
λλλλλ
ij
ij
ijij r
r
rr
,0
,
)(
6.1.3 模糊矩阵的合成与转置
定义 5 设 R∈Mm×t,S∈Ms×n且 R = (rij)m×t,S = (sij)t×n。令 T∈Mm×n 且 T = (tij)m×n,其中
)(
1 kjik
t
kij
srt ∧= =∨ (6.3)
则称 T 为 R 与 S 的合成(模糊乘积),记为 T = R °S。
例 2 设 R∈M2×3,S∈M3×2,其中
⎟⎟⎠
⎞
⎜⎜⎝
⎛=
8.01.07.0
15.02.0
R ,
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=
9.01.0
14.0
5.06.0
S
则
⎟⎟⎠
⎞
⎜⎜⎝
⎛
∧∨∧∨∧∧∨∧∨∧
∧∨∧∨∧∧∨∧∨∧=
)9.08.0()11.0()5.07.0()1.08.0()4.01.0()6.07.0(
)9.01()15.0()5.02.0()1.01()4.05.0()6.02.0(
SR o ⎟⎟⎠
⎞
⎜⎜⎝
⎛=
8.06.0
9.04.0
模糊矩阵的合成运算满足如下算律。
定理 4 设 R, S, T 为满足相应运算的模糊矩阵,则有
(1) 结合律:(R °S ) °T = R ° (S °T );特别地,Rm °Rn = Rm+n,(Rm)n = Rmn;
(2) 分配律:(R∪S ) °T = (R °T )∪(S °T ),R ° (S∪T ) = (R °S )∪(R °T );
(3) 弱分配律:(R∩S ) °T ⊆ (R °T )∩ (S °T ),R ° (S∩T ) ⊆ (R °S )∩ (R °T );
(4) 单调性:R⊆S ⇒ R °T⊆S °T,T °R⊆T °S。
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 4 -
(5) (R °S )λ = Rλ °Sλ。
一般来讲,模糊矩阵的合成不满足交换律。例如,考虑例 1 中的模糊矩阵 R 和 S,显然有
⎟⎟⎠
⎞
⎜⎜⎝
⎛=
4.05.0
7.07.0
SR o , ⎟⎟⎠
⎞
⎜⎜⎝
⎛=
2.05.0
7.04.0
RS o
即 R °S ≠ S °R。
定义 6 设 R∈Mm×n 且 R = (rij)m×n,则称 RT = (rji)n×m为 R 的转置。
模糊矩阵的转置矩阵与普通数值矩阵的转置矩阵概念是相同的,即把相应的行变为列,列变为行,并
且满足如下的性质。
定理 5 设 R 和 S 为满足相应运算的模糊矩阵,则有
(1) (RT)T = R;
(2) (R∩S )T = RT ∩ST,(R∪S )T = RT ∪ST;
(3) R⊆S ⇔ RT ⊆ST;
(4) (RT)λ = (Rλ )T;
(5) (R °S )T = RT°ST,(Rn )T = (RT)n;
(6) (RC)T = (RT)C。
6.2 模糊关系
模糊关系是经典关系的推广。经典关系描述元素之间是否适合某种关系,而模糊关系则是描述元素之
间适合某种关系的程度大小。在模糊集合理论中,模糊关系占有相当重要的地位。
6.2.1 模糊关系的定义及其运算
由第一章知道,经典关系是论域直积的经典子集。事实上,模糊关系是论域直积的模糊子集,因而模
糊关系可由模糊集合及其隶属函数来刻画。
定义 7 给定非空集合 X 和 Y。如果 R∈F (X×Y ),则称 R 为从 X 到 Y 的一个模糊(二元)关系,而 R 的
隶属函数 R(x, y)表示 X 中的元素 x 与 Y 中的元素 y 适合这种关系的程度。特别地,当 X = Y 时,从 X 到 Y
的模糊(二元)关系 R 称为 X 上的模糊(二元)关系。
给定非空集合 X1, X2, ..., Xn。如果 R∈F (X1×X 2× ... ×Xn),则称 R 为 X1, X2, ..., Xn 的一个模糊 n元关系。
特别地,X n 的模糊关系 R 称为 X 上的模糊 n 元关系。
在此我们仅讨论模糊二元关系,也常常简称为模糊关系。
由定义 7 可见,模糊关系本质上就是模糊集合,完全由其隶属函数来刻画。因此,当 R(x, y)仅取 1 或
者 0 时,R 退化为经典二元关系,即经典关系是模糊关系的特例。
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 5 -
与经典二元关系类似,在有限论域的情况下,模糊二元关系 R 可以直观地用模糊矩阵或者赋权图来表
示。设 X = {x1, x2, …, xm},Y = {y1, y2, …, yn}为两个非空的有限集合,R∈F (X×Y ),则模糊二元关系 R 可
由一个 m×n 的模糊矩阵 R = (rij)表示,其中
rij = R(xi, yj),1 ≤ i ≤ m, 1 ≤ j ≤ n
模糊二元关系 R 也可用关系图(赋权图)来描述,特别是同一论域上的模糊二元关系,如图 1 所示。
(a) 有限集到有限集的模糊二元关系 (b) 有限集上的模糊二元关系
图 1 有限集到有限集的模糊二元关系图
例 3 职场中的职员,工作行为可分为三个方面:X = {工作差 (x1), 表现好 (x2), 效率高 (x3)},人际关
系可分为两种:Y = {获得周围同事的认同 (y1), 得到老板的好感 (y2)},可获得的奖励方式也有两种:Z = {得
到物质奖励 (z1), 得到提升 (z2)}。如果用 R 表示工作行为与人际关系之间的关系,则它是一个从 X 到 Y 的
模糊二元关系,如果用 S 来表示人际关系与奖励之间的关系,则它是一个从 Y 到 Z 的模糊二元关系。经过
调查评估,这两个模糊二元关系可用如下的模糊矩阵来表达
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=
8.07.0
5.08.0
4.02.0
R , ⎟⎟⎠
⎞
⎜⎜⎝
⎛=
8.09.0
7.05.0
S
例 4 某夫妇有一子一女,X = {x1, x2, x3, x4, x5}为父、子、女、邻居、母 5 人的照片集合。请陌生人
根据照片对 5 人相貌的“相像”程度两两打分,得到 X 上的一个模糊二元关系 R,可用模糊矩阵表示如下
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
11.09.085.02.0
1.0102.01.0
9.0018.06.0
85.02.08.018.0
2.01.06.08.01
R
例 5 设 X×Y 为实数集 R 的直积,如果用 R 上的一个模糊二元关系 R 描述“x 接近 y”,则 R 的隶属
函数可规定为
R(x, y) = e− | x− y |,∀x, y∈U
例 6 设 X×Y 为实数集 R 的直积,如果用 R 上的一个模糊二元关系 R 描述“x 远大于 y”的关系,则
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 6 -
R 的隶属函数可规定为
⎩⎨
⎧
>−+
≤= −− yxyx
yx
yxR
,])(1001[
,0
),( 12
当然,也可用 R 上的另一个模糊二元关系 S 来描述“x 远大于 y”的关系,其隶属函数为
⎪⎪⎩
⎪⎪⎨
⎧
>
≤<−
≤
=
yx
yxy
y
yx
yx
yxS
10,1
10,
9
,0
),( 或
⎪⎩
⎪⎨
⎧
>⎭⎬
⎫
⎩⎨
⎧ −
≤
= yx
y
yx
yx
yxS ,
9
,1min
,0
),(
由于从 X 到 Y 的模糊二元关系是 X×Y 的模糊子集,因此可按模糊集合的运算及性质来定义和讨论模
糊二元关系的运算和性质。
定义 8 设 R 与 S 为从论域 U 到论域 V 的两个模糊二元关系,即 R, S∈F (U×V ),则
(1) R 与 S 相等定义为:R = S ⇔ R(x, y) = S(x, y), ∀(x, y)∈U×V;
(2) R 包含于 S 定义为:R⊆S ⇔ R(x, y) ≤ S(x, y), ∀(x, y)∈U×V;
(3) R 与 S 的交仍为从 U 到 V 的模糊二元关系,隶属函数定义为:
(R∩S )(x, y) = min{R(x, y), S(x, y)},∀(x, y)∈U×V;
(4) R 与 S 的并仍为从 U 到 V 的模糊二元关系,隶属函数定义为:
(R∪S )(x, y) = max{R(x, y), S(x, y)},∀(x, y)∈U×V;
(5) R 的余仍为从 U 到 V 的模糊二元关系,隶属函数定义为:
RC(x, y) = 1−R(x, y),∀(x, y)∈U×V;
(6) R 的逆关系为从 V 到 U 的模糊二元关系,隶属函数定义为:
R−1(y, x) = R(x, y),∀(y, x)∈V×U。
定义 9 设 R 为从论域 U 到论域 V 的模糊二元关系,即 R∈F (U×V )。令
Rλ = {(x, y) | R(x, y) ≥ λ, (x, y)∈U×V }
则称 Rλ为模糊关系 R 的 λ 截关系。
显然,Rλ是从 U 到 V 的经典二元关系,并且∀(x, y)∈U×V,有
Rλ(x, y) = 1 ⇔ R(x, y) ≥ λ,Rλ(x, y) = 0 ⇔ R(x, y) < λ
即 x、y 在 λ 水平上才有关系,否则无关系。
模糊二元关系及其截关系具有模糊集合及其截集所具有的一切运算性质,不再赘述,参见第二章。
6.2.2 模糊关系的合成
模糊关系的合成是常用的运算之一,许多模糊关系的性质都与合成有关。自然,模糊二元关系的合成
是经典二元关系合成的推广。
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 7 -
由定义 1 知道,模糊关系是经典关系的推广且完全由它的隶属函数来描述,因而模糊二元关系的合成
也应是经典二元关系合成的推广且通过隶属函数来实施。于是,将经典二元关系合成运算的特征函数表示
形式(参见 1.2.3 节)自然地推广为隶属函数形式,即可定义模糊二元关系的合成运算。
定义 10 给定论域 X、Y、Z,且 R∈F (X×Y ),S∈F (Y×Z )。所谓 R 与 S 的合成,就是从 X 到 Z 的一
个模糊二元关系,记作 R °S,其隶属函数为
ZXzxzySyxRzxSR
Yy
×∈∀∧= ∈∨ ),( )],,(),([ ),)(( o (6.4)
当 R∈F (X×X )时,记 R2 = R °R,Rn = R n − 1 °R。
例 7 考虑例 6 中描述“x 远大于 y”的模糊二元关系 R,则可以用 R2来描述“x 远远大于 y”的模糊
二元关系。根据定义 10,我们有
)],(),([ ),)((),(
R
2 yzRzxRyxRRyxR
z
∧== ∈∨o ,∀x, y∈R
(1) 如果 x ≤ y,则对∀z∈R,有
⎩⎨
⎧
>−+
≤= −− zxzx
zx
zxR
,])(1001[
,0
),( 12 , ⎩⎨
⎧
>−+
≤= −− yzyz
yz
yzR
,])(1001[
,0
),( 12
于是当 x ≤ y 时有 0)],(),([ ),(
R
2 =∧= ∈∨ yzRzxRyxR z ,如图 4(a)所示。
0
1
R(x,z) R(z,y)
Rx y
(a) 当 x ≤ y 时的情形
0
1
R(x,z) R(z,y)
Rxy z0
(a) 当 x > y 时的情形
图 4 模糊关系“x 远远大于 y”的构造
(2) 如果 x > y,则对∀z∈R,有
⎩⎨
⎧
>−+
≤= −− zxzx
zx
zxR
,])(1001[
,0
),( 12 , ⎩⎨
⎧
>−+
≤= −− yzyz
yz
yzR
,])(1001[
,0
),( 12
令 z0 为 R(x, z)与 R(z, y)的交点坐标,如图 4(b)所示,则
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 8 -
)],(),([ ),(
R
2 yzRzxRyxR
z
∧= ∈∨
⎥⎦
⎤⎢⎣
⎡ ∧⎥⎦
⎤⎢⎣
⎡ ∧⎥⎦
⎤⎢⎣
⎡ ∧= <<≤<<≤ ∨∨∨∨∨ )],(),([ )],(),([ )],(),([ yzRzxRyzRzxRyzRzxR zxyxzyxyz
),(),(0)],(),([ 0 00 yzRzxRyzRzxRxzy ==⎥⎦
⎤⎢⎣
⎡ ∧= ∨∨∨ ≤<
令 R(x, z) = R(z, y),则有
1
2
1
2 )(
1001
)(
1001
−−
⎥⎦
⎤⎢⎣
⎡
−+=⎥⎦
⎤⎢⎣
⎡
−+ yzzx ⇒ |x−z | = |z−y | ⇒ z − x = y − z(考虑到 y ≤ z ≤ x)
解得 z0 = (x+y)/2,于是当 x > y 时有
12
2
2
1001),(
−
⎥⎥⎦
⎤
⎢⎢⎣
⎡ ⎟⎠
⎞⎜⎝
⎛ ++= yxyxR
综上,我们有
⎪⎩
⎪⎨
⎧
>⎥⎥⎦
⎤
⎢⎢⎣
⎡ ⎟⎠
⎞⎜⎝
⎛ ++
≤
= −
yxyx
yx
yxR
122
2
1001
,0
),(
在有限论域的情形下,由于模糊二元关系可以用模糊矩阵来表示,因此模糊二元关系的合成也可转化
为模糊矩阵的合成运算。
例 8 考虑例 3 中的两个模糊关系 R 和 S:
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=
8.07.0
5.08.0
4.02.0
R , ⎟⎟⎠
⎞
⎜⎜⎝
⎛=
8.09.0
7.05.0
S
则工作行为与奖励之间的关系可由 R 与 S 的合成来描述,并且通过模糊矩阵的合成运算获得:
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=⎟⎟⎠
⎞
⎜⎜⎝
⎛
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=
8.08.0
7.05.0
4.04.0
8.09.0
7.05.0
8.07.0
5.08.0
4.02.0
oo SR
模糊关系的合成运算满足如下算律。
定理 6 设 R, S, T 为满足相应运算的模糊二元关系,则有
(1) 结合律:(R °S ) °T = R ° (S °T );特别地,Rm °Rn = Rm+n,(Rm)n = Rmn;
(2) 分配律:(R∪S ) °T = (R °T )∪(S °T ),R ° (S∪T ) = (R °S )∪(R °T );
(3) 弱分配律:(R∩S ) °T⊆ (R °T )∩ (S °T ),R ° (S∩T )⊆ (R °S )∩ (R °T );
(4) 单调性:R⊆S ⇒ R °T⊆S °T,T °R⊆T °S。
(5) (R °S )λ = Rλ °Sλ。
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 9 -
6.2.3 模糊等价关系
经典的等价关系是具有自反性、对称性、传递性的二元关系,利用等价关系可以对一个集合进行划分
(分类)。同样地,当模糊二元关系具有自反性、对称性和传递性时,就成为一个模糊等价关系。模糊等价
关系也是某些模糊聚类方法的理论基础。
定义 11 设 R 是论域 U 上的一个模糊二元关系,即 R∈F (U×U )。
(1) 如果∀x∈U,都有 R(x, x) = 1,则称 R 具有自反性;
(2) 如果∀x, y∈U,都有 R(x, y) = R(y, x),则称 R 具有对称性;
(3) 如果 R⊇R2,则称 R 具有传递性。
定理 7 设论域 U 上的模糊二元关系 R∈F (U×U )具有自反性,则
(1) Rn 也具有自反性;
(2) Rn+1 ⊇Rn(n ≥ 1)。
证明 略。
定理 8 设 R∈F (U×U )是论域 U 上的模糊二元关系,则
(1) R 具有对称性当且仅当 R = R−1;
(2) 若 R 具有对称性,则 Rn 也具有对称性(n ≥ 1);
(3) R °R−1 是 U 上的对称模糊关系。
证明 略。
定理 9 设 R, R1, R2∈F (U×U )是论域 U 上的模糊二元关系,则
(1) 若 R 具有自反性,则 R 具有传递性当且仅当 R = R2;
(2) 若 R 具有传递性,则 Rn 也具有传递性(n ≥ 1);
证明 (1) 由于 R = R2 是 R⊇R2 的特例,故充分性成立。
下面证必要性。若 R 具有传递性,因为 R 具有自反性,故∀x, y∈U
),(),(),()],(),([ ),(),( 2 yxRyyRyxRyzRzxRyxRyxR
Uz
=∧≥∧=≥ ∈∨
即 R = R2 成立。
(2) 因为 R 具有传递性,故 R⊇R2,于是由定理 6(3):Rn⊇ (R2)n。而 (R2)n = (Rn)2,故 Rn⊇ (Rn)2,即
Rn 也具有传递性。
定义 12 设 R 是论域 U 上的一个模糊二元关系,即 R∈F (U×U )。如果 R 具有自反性和对称性,则称
R 为模糊相似关系,且称隶属度 R(x, y)为 x 与 y 关于 R 的相似程度;如果 R 具有自反性、对称性和传递性,
则称 R 为模糊等价关系。
如果论域 U 有限,则描述模糊相似关系和模糊等价关系的模糊矩阵分别称为模糊相似矩阵和模糊等价
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 10 -
矩阵。显然,如果一个模糊矩阵 R 满足
(1) R⊇ I(I 为单位矩阵)
(2) R = RT
则 R 是模糊相似矩阵;如果还满足
(3) R⊇R2
则 R 是模糊等价矩阵。
满足 R = R2的模糊相似矩阵一定是模糊等价矩阵。
定义 12 设 R 是一个 n 阶模糊矩阵,即 R∈Mn×n。
(1) 如果 R 满足 R⊇R2,则称 R 为模糊传递矩阵;
(2) 在 Mn×n中包含 R 的最小的模糊传递矩阵称为 R 的传递闭包,记为 t(R)。
一个模糊矩阵 R 的传递闭包 t(R)满足
(1) 传递性:t(R) ° t(R)⊆ t(R);
(2) 包含性:R⊆ t(R);
(3) 最小性:R⊆S 且 S °S⊆S ⇒ t(R)⊆S。
定理 10 设 R∈Mn×n 是 n 阶模糊相似矩阵。则存在一个最小自然数 k(k ≤ n),使得传递闭包 t(R) =Rk,
且对一切大于 k 的自然数 l,恒有 Rl = Rk。
证明参见[7]。
结合定理 7~10,我们可以得到将模糊相似矩阵 R 改造为模糊等价矩阵的方法:通过“平方法”依次
计算 R, R2, R4, R8, … 当第一次出现(Rk)2 = Rk时,Rk就是 R 的传递闭包 t(R),而 t(R)就是由 R 经过改造后
获得的模糊等价矩阵。
这也表明,对于任何模糊相似关系,通过至多 n − 1 次复合就可以重新组合成一个模糊等价关系。
在实际应用中,往往需要根据具体情况建立一个模糊等价矩阵,它需要同时满足自反性、对称性和传
递性,这在技术上常常会遇到困难。因而,我们可以暂不考虑传递性,建立一个具有自反性和对称性的模
糊相似矩阵,然后再将它进行改造,使它满足传递性而且保留原有的自反性和对称性。
例 9 考虑例 4 中描述相貌“相像”关系的模糊矩阵
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
11.09.085.02.0
1.0102.01.0
9.0018.06.0
85.02.08.018.0
2.01.06.08.01
R
由于 R⊇ I 且 R = RT,故 R 是模糊相似矩阵。因为
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 11 -
RR ≠
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
12.09.085.08.0
2.012.02.02.0
9.02.0185.08.0
85.02.085.018.0
8.02.08.08.01
2 , 24
12.09.085.08.0
2.012.02.02.0
9.02.0185.08.0
85.02.085.018.0
8.02.08.08.01
RR =
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
于是 R 的传递闭包为 t(R) = R4 = R2。从而 t(R)是由 R 经过改造后得到的模糊等价矩阵。
6.2.4 模糊关系的广义合成运算
在 6.2.2 中给出的模糊关系的合成运算,是通过对关系程度逐点取小再取大来实现的(称之为最大−最
小合成或 max−min 合成),它是经典二元关系合成运算的特征函数表示形式的自然推广。
然而,当用特征函数来表达经典二元关系的合成运算时,除了采用对关系程度逐点取小再取大的形式
之外,也可以采用对关系程度逐点做 T 模运算再取大。
于是,类似于模糊集合的广义运算,我们也可以引入模糊关系的广义合成运算。
定义 13 给定论域 X、Y、Z,且 R∈F (X×Y ),S∈F (Y×Z )。所谓 R 与 S 的广义合成,就是从 X 到 Z
的一个模糊二元关系,记作 R °S,其隶属函数为
ZXzxzySyxRTzxSR
Yy
×∈∀= ∈∨ ),( )),,(),,(( ),)(( o (6.5)
其中 T 为三角模。
特别地,当取 T = min 时,就得到最大−最小合成运算;当取 T 为代数积时,就得到最大−代数积合成
运算;等等。
6.3 模糊聚类分析
聚类分析就是将一个没有类别标记的样本集按照某种准则划分成若干个子集(类),使相似的样本尽可
能归为一类,而不相似的样本尽可能划分到不同的类中。由于在对样本集进行聚类的过程中,没有任何关
于类别的先验知识,所以聚类分析属于无监督分类的范畴。
传统的聚类分析是一种硬划分,它将每个待识别的对象严格地划分到某个类中,类别划分的界限是分
明的,具有“非此即彼”的性质。而现实世界中,一组对象根据其亲疏程度和相似性是否形成一个类群,
或一个对象是否属于一个类别,其界限往往是不分明的,具有“亦此亦彼”的性质。对于这种带有不确定
性的聚类问题,模糊聚类分析提供了有力的分析工具。
模糊聚类分析能够建立样本对于类别的不确定性描述,表达样本类属的中介性,已经成为聚类分析研
究的主流。粗略来讲,模糊聚类分析方法可分为两类:基于模糊等价关系的聚类方法和基于目标函数的聚
类方法。有时,这两类方法也结合起来使用。
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 12 -
6.3.1 数据与处理
在模糊聚类分析中,我们称待分类的对象为样本。要对样本进行合理的分类,首先应考虑样本的各种
特性指标(观测数据)。设有 n 个被分类对象,即样本集为
X = {x1, x2, …, xn}
每一个 xi 有 m 个特性指标,即 xi 可表示为特性指标向量
xi = {xi1, xi2, …, xim}
其中 xij 表示第 i 个样本的第 j 个特性指标。于是,n 个样本的特性指标矩阵为
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
nmnn
m
m
xxx
xxx
xxx
L
MLMM
L
L
21
22221
11211
通常,我们也将样本集记为特性指标矩阵的形式,即 X = (xij)n×m。
如果 m 个特性指标的量纲和数量级都不相同,在运算过程中就可能会因为突出某些数量级特别大的特
性指标对分类的作用,而降低甚至排除某些数量级很小的特性指标的作用,致使对各特性指标的分类缺乏
一个统一的尺度。所以,为了消除特性指标单位的差别和数量级不同的影响,当特性指标的量纲和数量级
不相同时,通常事先对各种指标值实施数据标准化(规格化),从而使得各个指标值都统一于某种共同的数
值特性范围。我们称之为数据预处理。
常用的数据标准化方法有两种:均值方差标准化和极大极小标准化。
(1) 均值方差标准化
设给定的样本集为 X = (xij)n×m,标准化之后的样本集为 X = (x′ij)n×m,则
j
jij
ij
xx
x σ
−=′ ,i = 1, 2, …, n,j = 1, 2, …, m
式中
∑
=
=
n
i
ijj xn
x
1
1 , ∑
=
−−=
n
i
jijj xxn 1
)(
1
1σ ,j = 1, 2, …, m
(2) 极大极小标准化
设给定的样本集为 X = (xij)n×m,标准化之后的样本集为 X = (x′ij)n×m,则
minmax
min
jj
jij
ij xx
xx
x −
−=′ ,i = 1, 2, …, n,j = 1, 2, …, m
式中
}{min
1min ijnij
xx ≤≤= , }{max1max ijnij xx ≤≤= ,j = 1, 2, …, m
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 13 -
显然,实施数据标准化之后,每个指标值均在区间 [0, 1]中。
6.3.2 基于模糊等价关系的聚类方法
(一)模糊等价矩阵聚类方法
模糊等价矩阵聚类方法是典型的基于模糊等价关系的聚类方法之一。其主要思想就是从计算各个样本
之间的相似性统计量出发,建立样本集 X 上的模糊相似矩阵(关系);通过改造模糊相似矩阵为模糊等价
矩阵,达到对样本集 X 进行模糊聚类的目的。
模糊等价矩阵聚类法
1° 选择适当的相似性统计量;
2° 构造样本集上的模糊相似矩阵;
3° 将模糊相似矩阵改造为模糊等价矩阵;
4° 聚类;画出聚类的谱系图。
1. 建立模糊相似矩阵
设待分类的样本集为 X = {x1, x2, …, xn} 或 X = (xij)n×m,并已经标准化。如果能够计算出衡量样本 xi与
xj 之间相似程度的相似性统计量 rij,使得
0 ≤ rij ≤ 1,,i, j = 1, 2, …, n
其中,rij = 0 表示样本 xi与 xj 之间毫不相似,rij = 1 表示样本 xi 与 xj 之间完全相似或者等同,rii 表示样本
xi 自己与自己的相似程度,恒取为 1,即 rii = 1,i = 1, 2, …, n,那么,描述样本之间的模糊相似关系、建
立在样本集 X 上的模糊相似矩阵为
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
=
nnnn
n
n
rrr
rrr
rrr
R
L
MLMM
L
L
21
22221
11211
常用的计算样本的相似性统计量的方法有如下几种:
(1) 相关系数法
∑∑
∑
==
=
−⋅−
−⋅−
=
m
k
jik
m
k
iik
m
k
jjkiik
ij
xxxx
xxxx
r
1
2
1
2
1
)()(
||||
其中
∑
=
=
m
k
iki xm
x
1
1 , ∑
=
=
m
k
jkj xm
x
1
1
(2) 夹角余弦法
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 14 -
jk
m
k
ik
m
k
jkik
ij
xx
xx
r
2
1
2
1
⋅
⋅
=
∑
∑
=
=
(3) 数量积法
,1
,1
1
⎪⎩
⎪⎨
⎧
≠⋅
=
= ∑
=
jixx
M
ji
r m
k
jkik
ij
其中 M 为一适当选取的正数,满足
⎭⎬
⎫
⎩⎨
⎧ ⋅≥ ∑
=
m
k
jkikji
xxM
1 ,
max
(4) 最大最小法
∑
∑
=
== m
k
jkik
m
k
jkik
ij
xx
xx
r
1
1
),max(
),min(
(5) 算术平均最小法
∑
∑
=
=
+
= m
k
jkik
m
k
jkik
ij
xx
xx
r
1
1
)(
2
1
),min(
(6) 几何平均最小法
∑
∑
=
=
⋅
= m
k
jkik
m
k
jkik
ij
xx
xx
r
1
1
),min(
(7) 指数相似系数法
∑
=
−⋅−=
m
k
S
xx
ij
k
jkik
e
m
r
1
)(
3
4
2
2
1
其中 Sk是第 k 个特征的标准差:
2
1
2 )(1 k
m
k
ikk xxn
S −= ∑
=
(8) 绝对值指数法
∑= = −−
m
k
jkik xx
ij er 1
||
(9) 绝对值减数法
⎪⎩
⎪⎨
⎧
≠−−
=
= ∑
=
jixxc
ji
r m
k
jkik
ij ,||1
,1
1
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 15 -
其中,c 是一个适当选取的数,使得 0 ≤ rij ≤ 1。
(10) 绝对值倒数法
⎪⎪⎩
⎪⎪⎨
⎧
≠
−
=
= ∑
=
ji
xx
M
ji
r m
k
jkik
ij ,
||
,1
1
其中 M 为适当选取的正数,使得 0 ≤ rij ≤ 1。
2.改造模糊相似矩阵为模糊等价矩阵
根据计算相似性统计量得到的模糊矩阵 R,一般只满足自反性和对称性,即 R 是相似矩阵。为了进行
模糊聚类,需将 R 改造成模糊等价矩阵。为此采用平方法求出 R 的传递闭包 t(R),t(R) 便是所求的模糊等
价矩阵。
3.聚类
根据得到的模糊等价矩阵 t(R),我们就可以利用不同水平下的截矩阵得到该水平下的聚类结果。所有
不同水平的聚类结果形成聚类的谱系图。
例 环境单元分类
每个环境单元包括空气、水分、土壤、作物四个要素。环境单元的污染状况由污染物在四要素中含量
的超限度来描述。现有五个环境单元,它们的污染数据如下:
I = (5, 5, 3, 2),II = (2, 3, 4, 5),III = (5, 5, 2, 3),IV = (1, 5, 3, 1),V = (2, 4, 5, 1)
设 U = {I, II, III, IV, V},试对 U 进行分类。
解 样本集的特性指标矩阵为
⎟⎟
⎟⎟
⎟⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎝
⎛
1542
1351
3255
5432
2355
由于数据不存在量纲和数量级的差异,故不需进行数据标准化,直接进入构造模糊相似矩阵步骤。按
照绝对值减数法建立模糊相似关系,取 c = 0.1,得模糊相似矩阵
⎟⎟
⎟⎟
⎟⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎝
⎛
=
16.03.04.03.0
6.015.02.05.0
3.05.011.08.0
4.02.01.011.0
3.05.08.01.01
R
用平方法求传递闭包,以便将模糊相似矩阵改造成模糊等价矩阵,我们有:
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 16 -
⎟⎟
⎟⎟
⎟⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎝
⎛
=
16.05.04.05.0
6.015.04.05.0
5.05.013.08.0
4.04.03.013.0
5.05.08.03.01
2R ,
⎟⎟
⎟⎟
⎟⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎝
⎛
=
16.05.04.05.0
6.015.04.05.0
5.05.014.08.0
4.04.04.014.0
5.05.08.04.01
4R ,
⎟⎟
⎟⎟
⎟⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎝
⎛
=
16.05.04.05.0
6.015.04.05.0
5.05.014.08.0
4.04.04.014.0
5.05.08.04.01
8R =
4R
于是,传递闭包 t(R) = R4 就是所求的模糊等价矩阵。根据得到的模糊等价矩阵 t(R),利用不同水平下的截
矩阵得到各个水平下的聚类结果如下:
当 0.0 ≤ λ ≤ 0.4 时,U 分为一类:{I, II, III, IV, V};
当 0.4 < λ ≤ 0.5 时,U 分为二类:{I, III, IV, V},{II};
当 0.5 < λ ≤ 0.6 时,U 分为三类:{I, III},{IV, V},{II};
当 0.6 < λ ≤ 0.8 时,U 分为四类:{I, III},{II},{IV},{V};
当 0.8 < λ ≤ 1.0 时,U 分为五类:{I},{II},{III},{IV},{V}。
最后,将所有不同水平下的聚类结果形成聚类的谱系图如下:
不同水平下聚类结果的谱系图
(二)模糊最大支撑树聚类方法
模糊最大支撑树聚类方法是另一个典型的基于模糊等价关系的聚类方法。它首先构造一个完全赋权图
K|X| ,K|X| 中的顶点为待分类的样本点,边权为相应的两个样本之间的相似性统计量值;然后通过寻找完全
赋权图 K|X| 的最大支撑树,来进行聚类。
模糊最大支撑树聚类法
1° 选择适当的相似性统计量;
2° 构造样本集上的模糊相似矩阵;
3° 根据模糊相似关系矩阵构造完全赋权图;
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 17 -
4° 寻找完全赋权图的最大支撑树;
5° 由最大支撑树进行聚类分析。
1.建立模糊相似矩阵
设待分类的样本集为 X = {x1, x2, …, xn} 或 X = (xij)n×m,并已经标准化。如果能够计算出衡量样本 xi与
xj 之间相似程度的相似性统计量 rij,使得
0 ≤ rij ≤ 1,,i, j = 1, 2, …, n
其中,rij = 0 表示样本 xi与 xj 之间毫不相似,rij = 1 表示样本 xi 与 xj 之间完全相似或者等同,rii 表示样本
xi 自己与自己的相似程度,恒取为 1,即 rii = 1,i = 1, 2, …, n,那么,描述样本之间的模糊相似关系、建
立在样本集 X 上的模糊相似矩阵为
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
=
nnnn
n
n
rrr
rrr
rrr
R
L
MLMM
L
L
21
22221
11211
建立模糊相似矩阵的方法与模糊等价矩阵聚类法完全相同。
2.构造完全赋权图
构造一个完全赋权图 K|X| ,K|X| 中顶点集为 X = {x1, x2, …, xn},每条边 xixj的权值为 xi与 xj之间的相关
系数(模糊相似关系矩阵中的元素)rij。
3.寻找 K|X| 的最大支撑树
用 Kruskal 算法或者 Prim 算法,求完全赋权图 K|X| 的最大支撑树(生成树)T。
Kruskal 算法和 Prim 算法可参见相关的图论著作。
4.聚类
适当选取阈值 λ,砍去最大支撑树 T 中权值小于 λ 的边,相互连通的顶点(样本点)归为同一类。
例如,设 X = {1,…,6},已知求得的模糊相似关系矩阵为:
⎟⎟
⎟⎟
⎟⎟
⎟⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎜⎜
⎝
⎛
=
159.055.053.038.060.0
145.038.053.064.0
138.045.045.0
138.038.0
153.0
1
R
利用图论中的 Prim 算法,可求得矩阵
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=
53.053.055.060.064.0
32465
61611
T
数学系 • 张运杰 • 模糊数学课程教案 第 6 章 • 模糊关系与模糊聚类分析
- 18 -
其中,矩阵 T 中的第一、第二行表示构成最大支撑树 T 的边的端点标号,第三行表示对应的边权值,如图。
最大支撑树 T
根据最大支撑树 T,可以得到不同水平下的聚类结果如下:
当 0.00 ≤ λ ≤ 0.53 时,X 分为一类:{1, 2, 3, 4, 5, 6};
当 0.53 < λ ≤ 0.55 时,X 分为三类:{1, 4, 5, 6},{2},{3};
当 0.55 < λ ≤ 0.60 时,X 分为四类:{1, 5, 6},{2},{3},{4};
当 0.60 < λ ≤ 0.64 时,X 分为五类:{1, 5},{2},{3},{4},{6};
当 0.64 < λ ≤ 1.00 时,X 分为六类:{1},{2},{3},{4},{5},{6}。
最后,将所有不同水平下的聚类结果形成聚类的谱系图如下:
不同水平下聚类结果的谱系图
(三)最佳阈值的确定