购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

§2.2 模糊关系

客观世界中各个客体之间普遍存在着某种联系,本书第1章中提到的普通集合论中的“关系”就是这种联系的抽象结果。通常来说,普通的“关系”描述了客体间的“精确性”联系,而“模糊关系”则从更深刻的意义上表现了客体间更宽泛的内在联系。本节着重介绍模糊关系的定义、性质、运算和简单应用。

2.2.1 模糊关系的概念

一般来说,两个事物间要么存在某种关系,要么不存在这种关系,往往是泾渭分明的。然而在实际问题中,事物之间的很多关系很难用“有”或“无”来回答,如子女与父母的长相是否相像,有时就很难做出肯定或否定的判断。两者间的“相像”关系并非非此即彼,而是亦此亦彼,体现在相像程度上的差异。我们把具有程度上差异的关系叫做 F 关系。

普通关系定义为直积 U × V 的普通子集,很自然地可以考虑把 F 关系定义为 U × V F 子集。相应地有:

定义2.12 R U × V 上的一个 F 子集(简称 F 集),它的隶属函数

R U × V →[0,1]

确定了 U 中的元素 u V 中的元素 v 的关系程度(关联度),则称 R 为从 U V 的一个 F 关系。

可见, F 关系 R 由隶属函数 R U × V →[0,1]所刻画,即 U × V 上的 F 集确定了 U V F 关系。反之, F 关系也是 U × V 上的一个 F 集。因此,所有从 U × V F 关系的集合可记为 F U × V )。

由定义2.12可知, F 关系 R 的论域为 U × V

特别的, F U × U )表示从 U U F 关系,即表示 U 中的二元 F 关系,也称之为 U 上的 F 关系,如图2.6所示。若 F 关系 R 的论域为 n 个集合的笛卡尔积 U 1 × U 2 ×…× U n ,则称 R n F 关系。

图2.6 有限集到有限集的 F 关系示意

F 关系 R S 的论域都是 U × V u v )∈ U × V ,当 R u v )= S u v )时,称为 R S 相等,记为 R = S

例2.18 设论域 U 是所有人的集合, R 表示 U 上的相像关系,对 u 1 u 2 U R u 1 u 2 )表示 u 1 u 2 的相像程度。若 R u 1 u 2 )=0.7,说明 u 1 u 2 的相像程度达到70%。

例2.19 X 表示横坐标, Y 表示纵坐标,则 X × Y 构成平面 R 2 ,如果建立 X Y 上的 F 关系 R 为“ x 远远大于 y ”,其隶属函数可用下式表示。

可得 R (2,1)=1/101, R (11,1)=0.5, R (1001,1)=10000/10001。

2.2.2 模糊关系的运算与性质

由于 F 关系就是由直积构成的论域上的 F 集,所以 F 集的一些运算定义对它一样成立,在此我们不再做深入讨论,只简单叙述如下:

R R 1 R 2 都是 U V 上的 F 关系,对于 u v )∈ U × V ,若有

(1) R 1 = R 2 R 1 u v )= R 2 u v ),称之为 R 1 等于 R 2

(2) R 1 R 2 R 1 u v )≤ R 2 u v ),称之为 R 1 包含于 R 2

(3)( R 1 R 2 )( u v )= R 1 u v )∨ R 2 u v ),称之为 R 1 R 2 的并;

(4) R 1 R 2 u v )= R 1 u v )∧ R 2 u v ),称之为 R 1 R 2 的交;

(5) R c u v )=1- R u v ),称 R c R 的补关系;

(6)若 R 1 u v )=0, R 2 u v )=1,分别称之为 U V 的零关系和全称关系,本书用 O E 表示。

特别的,两个 F 关系的并与交可以推广到任意一个 F 关系的并与交。如,设 T 为指标集,则 ,其中∨表示取上确界。 ,其中∧表示取下确界。

关于 F 关系的性质,不做证明,叙述如下:

(1)( R c c = R ,表示 R 的补集的补集等于 R

(2) R E = E R E = E

(3) R O = R R O = O

(4) O R E

(5) R S R c S c

当所讨论的论域为有限集时, F 关系可用 F 矩阵来表示,下面给出 F 矩阵的具体内容。

定义2.13 设矩阵 R =( r ij m × n r ij ∈[0,1],则称 R F 矩阵, r ij F 矩阵的代表元素。

特别地,若满足 r ij ∈{0,1},则 R 退化为普通的布尔矩阵。

由定义可见, F 矩阵与普通矩阵的形状一样,唯一不同的地方是 F 矩阵的元素都要求是[0,1]中的数。

对于有限论域 U ={ u 1 u 2 ,…, u m }, V ={ v 1 v 2 ,…, v m },若定义元素 r ij = R u i v j ),表示 u i v j 具有 F 关系的程度,则 F 矩阵 R =( r ij m×n 恰好表示了从 U V 的一个 F 关系,或者说一个 F 矩阵确定一个 F 关系。

例2.20 X ={ u 1 u 2 u 3 }表示三个人构成的有限论域,在其上建立了“信任”关系 R ,可用如下 F 矩阵表示:

其中,矩阵元素 r ij = R u i u j )表示 u i u j 的信任程度,如 r 32 =0.3,表明 u 3 u 2 的信任程度为0.8,而 r 23 =1,表明 u 2 u 3 的信任程度为1,是百分百的信任。这一 F 矩阵真实地反映了人与人之间的现实信任关系。

当矩阵元素 r ij 只取0,1两个值时, R =( r ij m×n 表示从 U V 的一个普通关系。因此,普通关系是 F 关系的特殊情况。可见,一个 F 关系与一个 F 矩阵一一对应;一个普通关系与一个布尔矩阵一一对应。所以,在有限论域上, F 关系和 F 矩阵可看作一回事。如上例2.20, F 矩阵 R 也可看做 F 关系 R 。正因此,在有限论域的前提下 F 关系和 F 矩阵均可用 R 表示。

F 矩阵除了限制它的元素在闭区间[0,1]上外,它的运算与普通矩阵也有所不同。由于 F 关系是 U × V 上的 F 集,所以 F 矩阵的运算与 F 集的运算类似,因此有如下定义。

定义2.14 μ m × n 表示所有 m n 列的 F 矩阵构成的集合, R =( r ij m × n μ m × n S =( s ij m × n μ m × n ,对于 i j ,规定:

(1) R = S r ij = s ij ,表示两个 F 矩阵相等;

(2) R S r ij s ij ,表示包含关系;

(3) R S =( r ij s ij m × n μ m × n ,表示矩阵的并关系;

(4) R S =( r ij s ij m × n μ m × n ,表示矩阵的交关系;

(5) R c =(1- r ij m × n μ m × n ,表示补矩阵。

例2.21

对于 F 矩阵,可给出类似于 F 关系的并、交、余运算,具体运算律如下,其中 R S T μm × n

(1)交换律 R S = S R R S = S R

(2)结合律 ( R S )∪ T = R ∪( S T ),( R S )∩ T = R ∩( S T );

(3)分配律 ( R S )∩ T =( R T )∪( S T ),( R S )∪ T =( R T )∩( S T );

(4)幂等律 R R = R R R = R

(5)吸收律 ( R S )∩ S = S ,( R S )∪ S = S

(6)复原律 ( R c c = R

(7)对偶律 ( R S c = R c S c ,( R S c = R c S c

对于 F 矩阵,还有如下性质,其中 R S R 1 R 2 S 1 S 2 μm × n

性质1 E R = E E R = R ,0∪ R = R ,0∩ R =0,0 R E ,其中0= 分别称为零矩阵、全矩阵,这相当于有限论域上的零关系和全称关系。

性质2 R S R S = S R S R S = R R S R c S c

性质3 R 1 S 1 R 2 S 2 ,则 R 1 R 2 S 1 S 2 R 1 R 2 S 1 S 2

注意: R R c 不恒等于 E R R c 不恒等于0,即互补律不成立。

以上运算律和性质,可直接用定义给出证明。

F 矩阵的并、交运算可推广到更一般的情形。

T 是任意指示集, t T ,则可定义它们的“并与交”运算:

性质4

证明:

因为 S =( s ij m×n t T ,由定义得

性质5

证明:

因为 t T ,由定义得

2.2.3 模糊关系的合成

作为数学领域的著名猜想,六度空间理论指出:你和任何一个陌生人之间所间隔的人不会超过六个人,也就是说,最多通过五个中间人你就能够认识任何一个陌生人,这就是六度分割理论,也叫小世界理论。这一理论非常好地体现了关系的传递作用,当然 F 关系也具有这种性质,而这种传递性需要用到 F 关系的合成运算。

定义2.15 Q F U × V ), R F V × W ),所谓 Q R 的合成,是指 U W 的一个 F 关系,记作 。它具有的隶属函数为

其中, u U v V w W 也称为 Q R 的复合 F 关系。

特别的,当 R F U × U )时,记

例2.22 R 为“ x 远大于 y ”的 F 关系,其隶属函数为

则合成关系 应为“ x 远大于 y ”。求 R 2 x y )。

解:

根据定义,有 ,其中

(1)当 x y 时,对于 z R ,有 R 2 x y )=0,如图2.7所示。

图2.7 当 x y 时的情形

(2)当 x > y 时,对于 z R ,有 R 2 x y )= R x z 0 )= R z 0 y ),如图2.8所示。

实际上,当 x > y 时的合成运算就是求使 R x z )与 R z y )相等的 z 0 。令 R x z )= R z y ),即 ,解得 ,将 z = z 0 代入 R x z )中,得

图2.8 当 x > y 时的情形

由于有限论域中的 F 关系可用 F 矩阵唯一的表示,故 F 关系的合成亦可用 F 矩阵的乘积来表示。

定理2.2 Q =( qik m×l F U × V ), R =( r kj l×n F V × W ),则 Q R 的合成为

其中 i =1,2,…, m ,j=1,2,…, n )。

F 矩阵的合成也称为 F 矩阵的乘积或简称 F 乘法。它与普通矩阵乘法的运算过程基本一样,只需将矩阵元素间的先乘后加改为先取小再取大运算即可。

例2.23

其中 s 11 =(0.3∧0.8)∨(0.7∧0.1)∨(0.2∧0.5)=0.3

s 12 =(0.3∧0.3)∨(0.7∧0.8)∨(0.2∧0.6)=0.7

s 21 =(1∧0.8)∨(0∧0.1)∨(0.9∧0.5)=0.8

s 22 =(0.3∧1)∨(0∧0.8)∨(0.9∧0.6)=0.6

例2.24 F 关系 R S 分别表示某个家庭中子女与父母,父母与祖父母外貌相像的程度,可分别表示为如下 F 矩阵

则有

合成结果表示了孙子女与祖父母外貌相像的 F 关系,也就是说,在该家庭中孙子与祖父、祖母的相像程度分别为0.5和0.7,而孙女与祖父、祖母的相像程只有0.1。仔细分析例2.24,我们会发现 F 矩阵相乘时先取小后取大是有现实意义的,正因为如此,有人认为取大取小运算法则是模糊数学的“特别美妙之处”。

F 关系合成性质如下:

(1)结合律

推论:

(2)0—1律

其中 0为零关系 0( u v )=0

I 为恒等关系

(3) 或者

推论: Q R Q n R n

(4)对并运算的分配律

证明:

此处仅证明(4)

因为 u w )∈ U × W ,有

所以,

类似地, 也成立,该性质可推广到无限多个并运算上去。

请读者思考一下,(4)式中的∪可否改成∩运算?(自证)

事实上,

例2.25 F 关系 ,分别求 ,验证

解:

因为 ,则 ,所以

2.2.4 特殊的模糊关系

由于 F 关系也是一种 F 集,因此, F 集的 λ 截集的概念也可以推广到 F 关系和 F 矩阵中来。

定义2.16 R 是论域 U 上的 F 关系,记

R α ={( x y )| R x y )≥ α }  (2.36)

R α 截关系。如果 U 为有限论域,设 F 关系 R 对应的 F 矩阵为 R =( r ij m×n α ∈[0,1],记

R α =( r ij α )) m×n (2.37)

其中

则称 R α R α 截矩阵。

可见截关系满足截集的所有性质, R α 截矩阵实际为布尔矩阵。

截矩阵具有下面的性质。设 R S 为论域 U 上的 α 截矩阵,有

(1) R S α ∈[0,1], R α S α

(2)( R S α = R α S α ,( R S α = R α S α

证明略。

第1章讨论过的普通的等价关系是指具有自反性、对称性和传递性的二元关系,利用等价关系可以对一个集合进行分类。同样的,当 F 关系具有自反性、对称性和传递性时,就成为一个 F 等价关系。 F 等价关系是某些 F 聚类方法的理论基础。

定义2.17 R 是论域 U 上的一个 F 二元关系,即 R F U × U )。

(1) u U ,有 R u u )=1,则称 R 具有 F 自反性;

(2) u v U ,有 R u v )= R v u ),则称 R 具有 F 对称性;

(3)如果 R 2 R ,则称 R 具有 F 传递性。

注意: 在有限论域下,判断 F 关系 R 是否具有自反性可根据 F 关系对应的 F 矩阵主对角线元素是否为1来判定。根据 F 矩阵是否为对称矩阵可判定 F 关系 R 是否具有对称性。

例2.26 设论域 U ={150,50,2}, R 表示“大得多”的 F 关系,且 ,问 R 是具有传递性的 F 关系吗?

解:

因为 ,所以 R 是具有传递性的 F 关系。

命题2.1 F 关系 R 具有自反性 α ∈[0,1], R α 是普通的自反关系。

证明:

R 具有自反性⇒ u U R u u )=1≥ α α ∈[0,1]),即( u u )∈ R α R α 是普通的自反关系。

反之, α ∈[0,1], R α 是普通的自反关系⇒ R 的1截集 R 1 具有自反性,⇒( u u )∈ R 1 R x x )≥1,即 R x x )=1。

命题2.2 F 关系 R 具有对称性 α ∈[0,1], R α 是普通的对称关系。

证明:

R 具有对称性,且( u v )∈ R α ,则 R u v )≥ α ,故 R v u )= R u v )≥ α ,由此可知( v u )∈ R α ,因此 R α 是普通的对称关系。

反之,若 α R α 具有对称性,则对于 u v U ,令 α = R u v ),则( u v )∈ R α ,从而( v u )∈ R α ,于是 R v u )≥ α = R u v ),类似可得 R u v )≥ R v u ),故 R u v )= R v u )。

命题2.3 F 关系 R 具有传递性 u v w U R u w )≥ R u v )∧ R v w )。

证明:

R 具有传递性,有

特别的,如果 U 是有限论域, R 为其上的一个 F 传递关系, R =( r ij n×n ,此时的传递性可表述如下:

对于 u i u j u k U R u i u k )≥ R u i u j )∧ R u j u k )可转化为 i j k r ik r ij r jk

命题2.4 F 关系 R 具有传递性 α ∈[0,1], R α 是普通的传递关系。

证明:

R 具有 F 传递性,若( u v )∈ R α 且( v w )∈ R α ,则 R u v )≥ α R v w )≥ α ,有 R u w )≥ R u v )∧ R v w )≥ α ,即( u w )∈ R α R α 是普通的传递关系。

反之,设 α ∈[0,1], R α 是普通的传递关系,对于 u v w ,取 α = R u v )∧ R v w ),则 R u v )≥ α R v w )≥ α ,即( u v )∈ R α ,( v w )∈ R α ,由 R α 的传递关系得( u w )∈ R α ,于是得 R u w )≥ α = R u v )∧ R v w )。

定义2.18 R 是论域 U 上的一个 F 关系,若 R 具有 F 自反、对称、传递关系,则称 R 是一个 F 等价关系。若 R 仅具有 F 自反、对称关系,则称 R 是一个 F 相似关系。

例2.27 F 关系 ,0≤a≤1,验证R是一个F等价关系。

解:

R 是对称阵且主对角线元素全为1,故 R 具有模糊对称及自反性,又因为 R 2 = = ,从而 R F 等价关系。

定理2.3 F 关系 R F 等价关系 α ∈[0,1], R α 是普通的等价关系。

证明:

结合命题2.1、命题2.3、命题2.4,可知对于 α ∈[0,1], R α 是普通的传递关系。

定理2.3表明,在有限论域上的 F 等价关系确定后,对给定的 α ∈[0,1],便可相应得到一个普通等价关系 R α ,于是由 R α 便可决定一个 α 水平的分类。显然,不同的 α 对应着不同的分类,当 α 从1下降到0时,分类也随之变化,形成一个动态的图像。那么,由于 α 的变化而分出的类具有何种特征呢?这就是下面的定理2.4所要描绘的内容。

定理2.4 0≤ α < β ≤1,则 R β 所分出的每一个类必然是 R α 所分出的子类。

证明:

R β 分类时 u v 分为一类,则 R β u v )=1,即 R u v )≥ β ,因为 α < β ,所以有 R u v )≥ α ,从而 R α u v )=1,即( u v )∈ R α ,所以元素 u v R α 分类时也归为一类,即 R β 所分出的类是 R α 所分出的子类。

定理2.4指出, α 越大,分类结果越细。因此若要把问题分得细一些,只需增大截关系的水平 α 即可。

2.2.5 传递闭包

对于有限论域 U F 相似关系对应的 F 矩阵称之为 F 相似矩阵, F 等价关系对应的 F 矩阵称之为 F 等价矩阵。在实际应用中,通常只能获得具有自反和对称关系的相似矩阵,能否基于 F 相似矩阵对论域 U 进行分类呢?这一问题的关键点就是如何将 F 相似矩阵改造为 F 等价矩阵。下面先给出传递闭包的介绍,再利用传递闭包法完成 F 相似矩阵到 F 等价矩阵的改造。

定义2.19 R F U × U ),如果

(1) 是具有传递性的 F 关系且

(2)Q是任意具有传递性的 F 关系,并且有 Q R 同时成立。

则称 R 的传递闭包,记

易知,传递闭包是所有包含 R 的最小的 F 传递关系。

定理2.5 R F U × U ),总有

证明:

(1)因为 ,所以有 。下面证明它具有传递性。

(2)设 Q 是任意包含 R 的具有传递性 F 关系,根据 Q R F 关系合成性质(3),归纳可得

Q k R k

又由 Q 的传递性及 F 关系合成性质(3),可推得 Q Q k R k

k 的任意性知

定理2.6 若论域 U 为有限论域,则 R F U × U ), n =| U |为论域 U 中元素个数。

证明:

(1)因为

所以有

故存在 v 1 v 2 ,…, v n 使得

(2)因为

R n+ 1 u w )= R u v 1 )∧ R v 1 v 2 )∧…∧ R v n w

由于论域 U 中仅有 n 个元素,而 u v 1 ,…, v n n +1个元素,故存在 v i = v j i < j ),并且有

所以有

(3)因为

依次类推,当 m > n 时,有 ,则有 t R )= R R 2 ∪…∪ R n R n+1 ∪…=

例2.28 ,求

解:

命题2.5 R F 相似关系,则 R k 也是 F 相似关系。

证明:

利用数学归纳法,当 k =1时, R k F 相似关系。

假设 R m F 相似关系,现考虑 R m+ 1

因为 ,故 R m+ 1 F 自反关系。

又因为 ,利用假设有 ,故 R m+ 1 F 对称关系。

命题2.6 若论域 U 为有限论域, R 为其上的 F 相似关系,则 t R )= R n

证明:

因为 v ,故 R R 2 。递推可得 R m R m+1 ,因此有

例2.29 已知 ,求 t R )。

解:

,故 t R )= R 3

推论: 若论域 U 为有限论域, R 为其上的 F 相似关系,则 R m = R n m > n )。

推论: 若论域 U 为有限论域, R 为其上的 F 相似关系,则 t R )为 F 等价关系。

证明略

按照前述知识,可知求有限论域上的 F 相似关系的传递闭包可采用平方法:

令2 k n ,故 k ≥log2 n

用平方法至多需求[log2 n ]+1步,便可得到传递闭包。

利用 F 关系的传递闭包可以将 F 相似矩阵转化为 F 等价矩阵,以此为中介即可完成模糊聚类分析。这是 F 集理论的四大应用之一,关于模糊聚类分析的方法与实例将安排在本书的第四章讲述。 X7PajktlHMYqddIkNCfJbwYbTHidnazLw8ke8+yE93rBjkgRDUURzXLrVfZn8JWq

点击中间区域
呼出菜单
上一章
目录
下一章
×