《模糊数学精品讲义3.6_模糊关系与聚类分析2》由会员分享，可在线阅读，更多相关《模糊数学精品讲义3.6_模糊关系与聚类分析2（136页珍藏版）》请在金锄头文库上搜索。
1、1,3.6.4 模糊传递闭包和等价闭包通常的模糊关系，不一定有传递性，因而不是模糊等价关系，对这种模糊关系直接进行上述分类显然是不合理的。为此，我们希望寻求一种方法，能将不是等价的模糊关系进行改造，以便分类使用,2,定义 3.6.13 设 RF ( X X )，称 t(R) 为 R 的传递闭包，如果 t(R) 满足: (1) 传递性：(t(R)2 t(R) ； (2) 包容性：R t(R) ； (3) 最小性：若 R是 X 上的模糊传递关系，且R R t(R) R， 即 R 的传递闭包是包含 R 的最小的传递关系。,3,定理 3.6.2 设 RF ( X X )，则证明：(1) 首先证明 是传
2、递的，即要证明,4,由传递性定义知， 是传递的。,5,(2) 显然有 (3) 若有 R 使 R R且 R是传递的，则由 R R 有R2 (R)2 R,R3 = R R2 R R (R)2 R, 一般有 Rn R, 从而,6,即 含于任一包含 R 的传递关系中。综上所述， 是包含 R 的最小传递关系，因而是 R 的传递闭包，即,7,在论域为有限集的情况下，传递闭包的计算变得很简捷。 命题 3.6.8 设 | X | = n，RF ( X X ) ，则证明略。,8,推论 设 | X | = n， RF ( X X ) ，且 R 是自反关系，则存在正整数 m ( n ) ，使 t(R) = Rm，且
3、 l m 有 Rl = t(R) 。 证明 因为 | X | = n，所以又因为 R 是自反的，由命题 3.6.5 (2) 知 R R2 R3 ,9,因而在做上述合成运算时，若做到 m ( n ) 次时，出现了 Rm+1 = Rm，则有 Rm+2 = Rm，进而，t(R) = Rm。这时，若我们取正整数 l m，则有,10,即有 Rl = t(R) 。上述推论说明，在计算有限论域上自反的模糊关系 R 的传递闭包时，可以从 R 开始，反复自乘，依次计算出 R， R2，R4， ，当第一次出现 RkRk = Rk 时，就有 t(R) = Rk 。,11,命题 3.6.9 模糊关系的传递闭包 t(R)
4、 有以下性质： (1) 若 I R，则 I t(R) 。 (2) ( t(R) )-1 = t(R -1 ) 。 (3) 若 R -1 = R，则 ( t(R) )-1 = t(R) 。 证明 (1) 由定理 3.6.2 可得。(2) 由定理 3.6.2 、命题 3.6.4 (3) 及推论 (1)，有,12,(3) 由 (2) 即得。 上述命题中的 (1) 说明自反关系的传递闭包还是自反的， (3) 表明对称关系的传递闭包还是对称的。,13,定义 3.6.14 设 RF ( X X )，称 e(R) 为 R 的等价闭包，若 e(R) 满足下述条件： (1) 等价性：e(R) 是 X 上的模糊等
5、价关系。 (2) 包容性：R e(R)。 (3) 最小性：若 R 是 X 上的模糊等价关系，且R R e(R) R 。显然，R 的等价闭包是包含 R 的最小的等价关系。,14,定理 3.6.3 设 RF ( X X ) 是相似关系 ( 即 R 是自反、对称模糊关系 ) ，则 e(R) = t(R) , 即模糊相似关系的传递闭包就是它的等价闭包。证明 因为 R 是自反和对称的，由命题 3.6.9 知，R 的传递闭包 t(R) 也是自反和对称的。又 t(R) 作为传递闭包本身是传递的，且包含 R，因此 t(R) 是,15,包含 R 的模糊等价关系。若 R 也是模糊等价关系，且包含 R。由于 R 是
6、传递的，t(R) 是最小传递闭关系，故有 t(R) R 。综上所述，当 R 是相似关系时， t(R) 是包含 R 的最小等价关系，因而 t(R) 是 R 的等价闭包，即 e(R) = t(R) 。,16,引理 设 Rnm，Qml 是两个模糊矩阵，则对 0，1 有 ( RQ )= RQ 。 证明 记 R = ( rij )、Q = ( qij )、RQ = Snl = ( sij ) ，类似地，又记 R = (rij )、Q = (qij ) 、S = (sij ) 。由于,17,sij = 1 sij t1，2，m，使 rit qtj t1，2，m，使 rit ，qtj t1，2，m，使 ri
7、t=1，qtj=1又注意到rik、qkj、sij只取0和1，故(RQ)=RQ。,18,由此引理可得， ( Rl ) = ( R ) l 。 推论 设 | X | = n， R 是 X 上的模糊相似关系，则 (1) m n，使 e(R) = Rm，且 l m 时有 e(R) = Rl。 0, 1，( e(R) ) = e(R) 。 证明 (1) 由命题 3.6.8 的推论及定理 3.6.3 可得。(2) 0, 1，由于 R 也是 X 上的相似关系，,19,则由(1)， m2 n，使 e(R ) = ，且 l m2 有 e(R) = (R )l 。 又由(1)， m1 n，使 e(R) = ，且
8、l m1 有 e(R) = Rl 。 令 l = max (m1，m2)，则 e(R) = Rl ，从而 ( e(R) ) = (Rl ) ，且 e(R) = (R )l 。由引理可知 (Rl ) = (R )l，从而 ( e(R) ) = e( R )。,20,在实际问题中建立的模糊关系，多数情况下都是相似关系，定理 3.6.3 给我们提供了一个求相似关系的等价闭包的方法。当论域为有限集时，此法很简便，即对相似矩阵 R ，求 R2， R4， 当 RkRk = Rk 时，便有 e(R) = t(R) = Rk 。,21,例 3.6.10 已知一个模糊相似矩阵 R求 e (R) 。,22,解：,
9、23,R8= R4 R4= R4， 故 e(R) = t(R) = R4。,24,对等价矩阵 e (R) = R4 进行动态聚类，其结果如图 3.39 所示 x1 x6 x2 x4 x7 x5 x310.90.80.7图 3.39 动态聚类图,25,从上例中可以看出， (1) 对于相似矩阵每作一次平方合成运算，模糊矩阵中的元素值便增大一次，也就是 R R2 R4。 (2) 我们还可以看到，若对原来的相似矩阵 R，先作其 截集，则我们便得到一个经典的相似矩阵 R，由于从定理 3.6.3 的推论(2)可知 ( e(R) ) = e( R ) ，这样要对 e(R) 作动态聚类时，可以先对相似矩阵作,
10、26, 截集，得到经典的相似矩阵，然后再求经典相似矩阵的等价闭包 e(R )。由于经典相似矩阵中的元素仅有 1 与 0（即非此即彼）两种，找出所有元素相关值为 1 的元素，加以归并，就可以找出该元素的等价类，从而可以用简单的方法来求 e(R )。以上所述的理论，在以下的定理中详细说明。,27,若 R 不是相似关系，R 的等价闭包是否存在？又如何求得其传递闭包？下面的定理回答了这个问题。 定理 3.6.4 设 R F ( X X )，则 R 的等价闭包 e (R) 必存在，且 e (R) = t (R*) ，式中 R* = R R-1 I。 证明先证 R* 是包含 R 的相似关系。因为 R R*
11、，,28,I R*，故 R* 是包含 R 的自反关系。又有(R*)-1 = ( R R-1 I )-1= R-1 (R-1)-1 I 1= R-1 R I = R R-1 I = R* （对称性得证）， 故 R* 是包含 R 的相似关系。又由定理 3.6.3， t (R*) 是模糊等价关系，且,29,R R* t (R*)。次证 t (R*) 是 X 上包含 R 的最小等价关系。设 RF ( X X )，R 是等价关系，且 R R，R-1 (R )-1 = R，从而 R*= R R-1 I R。 于是 (R*)2 (R)2 R， (R*)3 = (R*)2 R* R R R。,30,一般地 (
12、R*)n R， 从而综上所述， t (R*) 是包含 R 的最小等价关系，故 t (R*) 是 R 的等价闭包。当然 R 的等价闭包是存在的。,31,3.6.5 求相似矩阵的等价类的直接方法 定理 3.6.5 设 | X | = n，R 是 X 上的经典相似关系，x X 时，记 R x = y X | (x, y) R，并称 Rx 为 X 的相似类。记 = e (R) = t ( R) 。设 x0 X，于是 (1) 令 P1(x0) = Rx | Rx Rx0 （相交不空的相似类之集），则,32,(2) 令 P2(x0) = Rx | Rx P1(x0) ，则(3) 设 P1(x0) P2(x
13、0) Pm(x0) , 且 Pm(x0) 满足条件：若 Rx Pm(x0) Rx Pm(x0) = (3.6.24) 则 证明略。,33,定理 3.6.5 表明：对于一个经典相似关系，可以通过归并相似类的办法，得到它的等价类，所有等价类的并就是它的等价闭包。这样，我们就得到一个求等价类的直接方法，即先用不同的 值作相似矩阵 R 的截矩阵 R ，因 R 是一个经典相似阵，于是便可用本定理的方法通过归并相似类来求等价类。,34,例 3.6.11 设 X = x1, x2, , x7，R 是 X 上的模糊相似关系试以 R 为依据将 X 中的元素分类。,35,解: 先用平方法，求 R 的等价闭包 e (R) 。,36,再平方再平方，得 R8= R4。由命题 3.6.8 及定理 3.6.3 知 e(R) = R4，依次取 截关系 R，R 是经典等价关系，它诱导出 X 上的一个划分 X/R , 将 X 分成一些等价类,37,当 =1 时，有e(R)1 诱导的分类为 x1, x4, x5, x7, x2, x3, x6。,38,当 = 0.8 时，有e(R)0.8 诱导的分类为 x1, x4, x5, x7, x2 , x6, x3。,39,当 = 0.7 时，有e(R)0.7 诱导的分类为 x1, x4, x5, x7, x2, x3 , x6。,
