模糊数学精品讲义3.6模糊关系与聚类分析1.ppt

1,3.6 模糊关系与聚类分析,3.6.1 经典关系“关系”是一个普遍使用的，又是很重要的概念。例如父子关系、兄弟关系、朋友关系、大小关系、从属关系、买卖关系、供求关系、合作关系等等，他表示了事务之间的某种联系。在数学上，关系有严格的定义。,2,定义 3.6.1 设 X、Y 为两个非空集合，XY 为 X 与Y 的笛氏积，即 XY=(x,y)|x X，y Y。若有 R XY（即 RP(XY)，则称 R 为 X 到 Y 的二元关系，简称关系。对于任何一个(x,y)X Y，若(x,y)R，则称 x 与 y 具有关系 R，记作 xRy；若(x,y)R，则称 x 与 y 不具有关系 R，记作。若 X=Y，R 是从 X 到 Y 的关系，则可称 R 是 X 上的关系。,3,例 3.6.1 设 X、Y 是实数集，R 是 X 上的“大于”关系，即 xRy x y或R=(x，y)x，y 为实数，且 x y，亦即 R 是坐标平面上直线 y=x 下方（不含直线上的点）那部分平面的点集（图3.34）,4,5,从 X 到 Y 的关系 R 是论域 X Y 的经典子集。所以经典集的并、交、补运算及其性质，以及经典集的特征函数表示法，对 R 当然适用。,6,若 X 与 Y 之间有一规则 R，使得 xX，按规则 R 唯一地与 yY 对应，则 R 决定了从 X 到 Y 的映射R:XYx|R(x)=y，(x,y)R由此可见，映射中的规则 R，就是 X 到 Y 的关系 R。,7,例 3.6.2 设有四个学生甲、乙、丙、丁，用优、良、差来衡量他们的学习成绩。若作出两个集合 X=甲，乙，丙，丁，Y=优，良，差，再作其直积（笛氏积）X Y=(甲，优)，(甲，良)，(甲，差)，(乙，优)，(乙，良)，(乙，差)，(丙，优)，(丙，良)，(丙，差)，(丁，优)，(丁，良)，(丁，差),8,如果已知甲的成绩是优，乙和丙的成绩是良，丁的成绩是差，则R=(甲，优)，(乙，良)，(丙，良)，(丁，差)就是 X 与 Y 之间的一个关系，即 R XY，它表示了甲、乙、丙、丁四个学生与其成绩的对应关系，所以这个关系也是一个映射。如图 3.35 所示,9,10,关系也可以用表格表示，如表 3.8,表 3.8 学习成绩关系表,11,表中“1”表示(x,y)R，“0”表示(x,y)R。如(甲，优)R，则在相应的位置上写上“1”；又如(甲，良)R，则在相应的位置上写上“0”。表 3.8 的形式可以更简洁地用矩阵形式表示：,12,称为关系矩阵。它的一般形式为,其中 rij=0 或 1，i=1，2，n，j=1，2，m。,13,经典关系可以用特征函数来表示。定义 3.6.2 若 RP(XY),则其特征函数表示如下 当 X=x1,x2,xn，Y=y1,y2,ym，则二元关系 R 的特征函数组成一个布尔矩阵（矩阵中的元素或者为 0，或者为1），如（3.6.1）式所示。但,14,其中的元素 rij 如下选取：定义 3.6.3 设 R 是 X 到 Y 的关系，令 R-1=(y，x)Y X|(x，y)R,(3.6.2)则 R-1 是 Y 到 X 的关系，称 R-1 为 R 的逆关系。,15,定义 3.6.4 设 R 是 X 到 Y 的关系，Q 是 Y 到 Z 的关系，令（3.6.3）则 RQ 是 X 到 Z 的关系，称为 R 与 Q 的合成（或复合）关系（参见图3.36）。,16,若用特征函数来表示合成运算，则有因而有,17,例3.6.3 图 3.36 所示之例，用特征矩阵写出有,18,从图 3.36 直接可以看出由(3.6.4)式也可以计算出(RQ)(x,z)。这里和普通矩阵的乘法运算类似，只要用“”代替“”，用“”代替“+”便可。易知，计算的结果与直接观察的结果是相同的。,19,定义 3.6.5 设 R 是 X 上的经典关系，则有如下定义：称 R 是自反的 xX，(x,x)R。称 R 是对称的 若(x,y)R，则(y,x)R。称 R 是传递的 若(x,y)R，(y,z)R 则(x,z)R。称 R 是 X 上的等价关系 R 是 X 上的一个自反、对称和传递的关系。,20,若 R 是 X 上的一个等价关系，xX，称 Rx=y X|(x，y)R(3.6.5)为以 x 为代表的 R 的等价类。显然，等价类满足：(1)X=xX Rx；(2)若 RxRy，则 RxRy=。,21,我们将全体等价类的集合 X/R=Rx|xX(3.6.6)称为 X 的关于 R 的商集。显然，X/R 是集合的集合。,22,例 3.6.4 设 X 为整数集，令R=(x，y)X X|(xy)可被 3 整除,则 R 是 X 上的等价关系，且xX，R0=R3=R3x=,-6,-3,0,3,6,R1=R3x+1=,-5,-2,1,4,7,R2=R3x+2=,-4,-1,2,5,8,即 X 的（模）R 的等价类只有三个：,23,一个是所有 3 的倍数的整数集；一个是所有形如 3 的倍数+1 的整数组成的集；再一个就是所有形如 3 的倍数+2 的整数组成的集。因此，X 的（模）R 的商集只有三个元素：X/R=R0，R1，R2。,24,定义 3.6.6 设 A=At|tT 是 X 上的一个子集族，若它满足以下三个条件，则称 At|tT 为 X 的一个划分(分类)：At A，At，即每类不空；(2)若 At，As A,At As 则 At As=，即不同类不相交；(3)，即 X 的每一元素必属于一类而且只属于一类。,25,命题 3.6.1 设 R 是 X 上的等价关系，则 X/R 构成 X 的一个划分，并称为由等价关系 R 诱导的划分。证明(1)先证每类不空。因 R 具有自反性，故有 xRx，从 而 xR x=At，即 At。(2)次证不同类不相交。设 At=R x，As=R y,且At As，若 At As，取 zAt As，则 xRz 且 yRz则由传递性可知，有 xRy。由于 x、y 是任意的，于是有 R x=R y，与假设矛盾，故 At As=。,26,(3)最后证。一方面，xX,xRx，即 另一方面，显然有 因此有综上所述，X/R 构成 X 的一个划分。命题3.6.2 设 A=At|tT 为 X 上的一个划分，则A 决定了 X 上的一个等价关系 R，并且 X/R=A。,27,证明 在 X 上规定一个关系 R：xRy tT,x,y At,可证 R 是 X 上的一个等价关系。xX,因 A 是划分，故 tT，使xAt，故 xRx。(2)x，yX，若 xRy，则 tT，使 x，y At，即 y,x At，从而 yRx。(3)若 xRy、yRz，则 t,sT，使 x，y At，y，z As，因此 yAt As，故 At As。由定义 3.6.6 可知 At=As，这意味着 x，z At，即 xRz。,28,例 设 X=某校全体学生，R1 是同年级关系，R2 是同性别关系。显然，R1，R2 都是 X 上的等价关系。R1 把 X 划分为各个不同的年级：X=X1，X2，X3，X4，其中 Xi 表示 i 年级（i=1，2，3，4）。R2 把 X 划分成男生集合与女生集合：X=男生集合，女生集合。,29,定义 设 R 是 X 上的一个经典关系，如果 R 是自反的和对称的，则称 R 是 X 上的相似关系。例如，合作关系、朋友关系都是相似关系。若 R 是 X 上的一个相似关系，xX，称Rx=y X|(x，y)R 为以 x 为代表的 R 的相似类。,30,显然，相似类满足：X=xX Rx。但是，当 RxRy 时，可能有RxRy。这是因为相似关系可能不满足传递性。,31,例 设 X=1244，157，287，456，690。定义在 X 上的关系 R=(x，y)X X|x 与 y 有相同的数字,则 R 是 X 上的相似关系，其对应的相似矩阵为,32,R1244=1244，157，287，456，R157=1244，157，287，456，R287=1244，157，287，R456=1244，157，456，690，R690=456，690。可以看出，虽然 R287R456，但是R287R456=1244，157。,33,3.6.2 模糊关系的基本概念 经典关系只能说明元素之间关系的有无。现实世界的关系不是简单的有无，而是有不同程度的相关性质。例如家庭成员之间相貌相似的关系，就不是简单的相似或不相似，而是有不同的相似程度。反映这种性质的关系就是模糊关系。,34,定义 3.6.7 设 X、Y 为两个论域。X Y 中的任何一个模糊集 RF(XY)都称为 X 与 Y 之间的模糊关系，即R:X Y 0，1,(x，y)|R(x，y),其中 R(x，y)称为 x 与 y 关于 R 的关系强(程)度。当 X=Y 时，称 R 为 X 上的模糊关系。,35,例 3.6.5 医学上常用体重(kg)=身高(cm)100描述标准体重。这实际上给出了身高(论域 X)与体重(论域 Y)的普通关系。若 X=140,150,160,170,180，Y=40，50，60，70，80，则普通关系由表 3.9 给出。它的关系矩阵是个布尔矩阵,36,表 3.9 体重与身高的普通关系,37,人有胖瘦不同，所以大部分人并非严格是标准情况，而是与标准情况有不同的接近程度，显然这更能完整、全面地描述身高与体重的关系，如表 3.10 所示,表 3.10 体重与身高的模糊关系,38,当(x，y)=(170，60)时，R(x，y)=0.8；当(x，y)=(180，50)时，R(x，y)=0.1。这说明身高 1.7 m 与体重 60 kg 的人与标准情况接近的程度为 0.8，或其关系强度为 0.8；身高 1.8 m 与体重 50 kg 的人与标准情况接近的程度为 0.1 或其关系强度为 0.1。,39,这个模糊关系的矩阵形式如下：,40,一般地，对于有限论域 X=x1,x2,xn，Y=y1,y2,ym 之间的模糊关系 R 可用 n 行 m 列（简称 nm 阶）的模糊矩阵来表示：R=(rij)nm,其中 rij=R(xi,yj)，0 rij 1，或,41,例 3.6.6 设有一组学生 X=甲、乙、丙，他们可以选学 Y=英、法、德、日 中任意几门外语，他们的结业成绩见表 3.11。,表 3.11 外语成绩表,42,若把他们的分数除以 100，则得 X 与 Y 之间的一个模糊关系 R，见表 3.12.它的矩阵形式为,表 3.12 模糊关系表,43,有限论域上的模糊关系除了可以用矩阵表示外，还可以用模糊关系图来表示，如图 3.37 所示,44,由于模糊关系是一种特殊的模糊集，即 X Y 上的模糊集，故其运算与模糊集的运算完全一致，即包含关系，恒等关系，并、交、补的运算都有相同的定义。模糊关系的运算符合幂等、交换、结合、吸收、分配、两极、复原、对偶等规律，但不符合排中律。R 的 截集 R 是 X 与 Y 之间的普通关系，前述的截集的性质也完全适用于截关系。,45,它们分别称为零矩阵、单位矩阵和全矩阵。,记,46,R 的截关系 R 称为 截矩阵，记为其中类似地，也有强截矩阵的概念。,47,正如普通关系的合成运算一样，模糊关系也有合成运算。定义 3.6.8 设 X、Y、Z 是三个论域，QF(XY),RF(YZ)，由 Q 与 R 作出一个新的模糊关系 Q R F(XZ)，称为 Q 与 R 的合成模糊关系，它的隶属函数规定为,48,若 R 是 X 上的模糊关系，则 R 与 R 也可以合成为 RR，记作 R2，即 R2=RR。显然 R2 还是 X 上的模糊关系。R2 与 R 还可合成 R2R，记作 R3，R3=R2R，一般地，有 Rn=Rn-1R,n=2,3,。,49,当 X、Y、Z 为有限论域时，即 X=x1,x2,xn,Y=y1,y2,ym，Z=z1,z2,zl，则 Q、R、S（=Q R）均可表示为矩阵形式：Q=(qij)nm,R=(rjk)ml,S=(sik)nl 其中S 称为模糊矩阵 Q 与 R 的乘积。,50,注：若将“”换为“+”，将“”换为“”，则模糊 矩阵的乘积与普通矩阵的乘积完全相同。,51,例 3.6.7 设则,52,命题 3.6.3 模糊关系的合成运算具有下列性质：(1)合成运算满足结合律(Q R)S=Q(R S)，(3.6.12)特别地 Rm Rn=Rm+n。(3.6.13)(2)合成运算关于并“”满足分配律(Q R)S=(Q S)(R S),(3.6.14)S(Q R)=(S Q)(S R)。(3.6.15),53,证明 只证(3.6.14)。设 Q，RF(XY),SF(YZ),故有(Q R)S=(Q S)(R S)。,54,第二式证明相似。应注意的是，1)合成运算不满足交换律，即 Q R R Q。如设则因此，Q R R Q。,55,2)合成运算对交“”不满足分配律，即有下列二式：(Q R)S(Q S)(R S),S(Q R)(S Q)(S R)。例如，设 则,56,因此(Q R)S(Q S)(R S)。同样可以举出反例来说明第二个式子。R=R=,(XY)R=R(XY)=R。(3.6.16)(4)若 Q R，则 Q S R S，P Q P R,Q n R n(3.6.17),57,定义 3.6.9 设 RF(XY)，定义 R-1F(Y X)的隶属函数为R-1(y，x)=R(x，y)(y，x)Y X),称 Y 到 X 的模糊关系 R-1 为 R 的逆关系。命题 3.6.4 逆关系有下述性质：设 R，R1，R2 F(XY)，Rt|tT F(XY),S F(YZ),则(1)若 R1 R2 R1-1 R2-1。(2)(R-1)-1=R。,58,推论(1)设 R F(X X)，则(Rn)-1=(R-1)n。(2)设 R，QF(X X)且 R Q,则 R-n Q-n(n 为正整数)。（参（3.6.17）式）,59,3.6.3 模糊等价关系定义 3.6.10 设 R F(X X)(1)称 R 是自反的 xX，R(x,x)=1。(2)称 R 是对称的 x,y X，R(x,y)=R(y,x)。(3)若 R 是 X 上的自反、对称关系，则称 R 是 X 上的模糊相似关系，简称相似关系。,60,命题 3.6.5 设 R F(X X)，则(1)R 是自反的 I R。(2)R 是自反的 Rn Rn+1(n 1)且 Rn 也是自反的。证明(1)显然。,61,(2)用归纳法证明包含式 Rn Rn+1。(x,y)XX,有故 R R2。设 Rn-1 Rn，由（3.6.17）式可得Rn-1 R Rn R,即 Rn Rn+1。(3.6.18)因 I R Rn(n 1)，由(1)知 Rn 是自反的。,62,命题 3.6.6 设 R，R1，R2 F(X X)，则有(1)R 是对称的 R=R-1。(2)若 R1、R2 都是对称的，则 R1 R2 对称 R1 R2=R2 R1(即 R1、R2 是可以交换的）。(3)R 是对称的 Rn 是对称的(n 1)。证明(1)由对称关系的定义可得。,63,(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 对称，则由命题 3.6.4 推论(1)有(Rn)-1=(R-1)n=Rn。由(1)知，Rn 是对称的。,64,推论(1)若 R 是 X 上的相似关系，则 Rn 也是 X 上的相似关系。(2)设 RF(XX)是任一模糊关系，则 R R-1 是 X 上的对称关系。证明 因(R R-1)-1=(R-1)-1 R-1=R R-1，由命题 3.6.6(1)知，R R-1 是对称的。,65,定义 3.6.11 设 R F(X X)，称 R 为传递的 0，1，x，y，z X，若 R(x,y)，R(y,z)，则 R(x,z)。命题 3.6.7 设 R，R1，R2 F(X X)，则(1)R 是传递的 R2 R。(2)若 R 是传递的 Rn 是传递的(n 1)。(3)R1、R2 是传递的 R1 R2 是传递的。,66,证明(1)先证()：设 x，yX，tX，令t=R(x,t)R(t,y)，则 R(x，t)t，R(t，y)t。由于 R 是传递的,故R(x,y)t(tX)，于是,67,由 x，y 的任意性知 R2 R(3.6.19)再证()：若 R2 R 且 R(x，y)，R(y，z)于是由定义 3.6.11 知 R 是传递的。,68,(2)若 R 是传递的，则由(1)有 R2 R，进一步由(3.6.17)右边一式得(R2)n Rn 又由(3.6.13)有(Rn)2=(R2)n，联合上面两式，得(Rn)2=(R2)n Rn，最后由(1)知 Rn 是传递的。,69,(3)我们可以用(3.6.17)式证明(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),70,R12 R22。因为，R1、R2 是传递的，即 R12 R1、R22 R2，则有(R1 R2)2 R1 R2，所以，R1 R2 是传递的。,71,例 3.6.8 给定有限论域上的模糊关系 R 如下：则由于模糊矩阵 R2 的元素不超过 R 对应位置上的元素,72,因而模糊关系 R2 R，故 R 是传递的。命题 设 R 是 X 上的一个自反的和传递的模糊关系，则有R=R2。证明 因为 R 是自反的，则由命题 3.6.5(2)有，R R2。又因为 R 是传递的，则由命题 3.6.7(1)有，R2 R，故有 R=R2。,73,定义 3.6.12 设 RF(X X)，若 R 满足下列三个条件，则称 R 是 X 上的一个模糊等价关系：(1)自反性：x X，R(x，x)=1。(2)对称性：x，y X，R(x，y)=R(y，x)。(3)传递性：R2 R，即 x，z X X，有,74,若 X=x1,x2,xn 为有限论域时，X 上的模糊等价关系 R 是一个矩阵（称为模糊等价矩阵），它满足下述三个条件：(1)自反性：rii=1,i=1,2,n。(2)对称性：rij=rji，i，j=1,2,n。(3)传递性：R R R，即,75,条件(1)说明模糊矩阵的对角线元素都是 1；条件(2)意味着模糊等价矩阵是对称矩阵。,76,定理 3.6.1 设 R F(X X)，则 R 是模糊等价关系 0，1，R 是经典等价关系，这里 R=(x,y)X X|R(x,y)为 R 的 截关系。且对于，0，1，有等价类 R x R x(x X)。证明略。,77,本定理说明，若 R 是 X 上的模糊等价关系，则其 截关系是经典等价关系，它们都可将 X 作一个划分，当 从 1 下降到 0 时，就得到一个划分族，而且由于 时，R x R x，即 R 给出的分类结果中的每类，是 R 给出的分类结果的子类，所以 R 给出的分类结果比 R 给出的分类结果更细。随着的下降，R 给出的分类越来越粗，这样就得到一个动态的聚类图，我们可以根据实际情况的需要，选择某个水平上的分类结果。这是模糊聚类分析的一大优越性,78,例 3.6.9 设 X=x1，x2，x3，x4，x5，R 是 X 上的一个模糊关系，其对应的模糊矩阵为 在上面的矩阵中，对角线元素为 1，即 rii=1，所以 R 是自反的。又因 R 与其转置矩阵相同，故,79,rij=rji，R=R-1，即 R 是对称的。由于即 RR=R2 R，R是传递的，故R是模糊等价关系。,80,依次取 截关系 R，R 是经典等价关系，它诱导出 X 上的一个划分 X/R，将 X 分成一些等价类。当=1 时，R1 诱导的分类为五类：x1,x2,x3,x4,x5。,81,当=0.8 时，R0.8 诱导的分类为四类：x1，x3,x2,x4,x5。,82,当=0.6 时，R0.6 诱导的分类为三类：x1,x3,x2,x4,x5。,83,当=0.5 时，R0.5 诱导的分类为两类：x1,x3,x4,x5,x2。,84,最后，当=0.4 时，R0.4 将 X 分成一类：x1,x2,x3,x4,x5。,85,随 由大到小，分类由细到粗，形成一个动态的分类图，如图 3.38 所示：x1 x3 x4 x5 x2=1 0.8 0.6 0.5 0.4 图 3.38 动态聚类图,