模糊数学精品讲义-模糊关系与聚类分析2

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) 首先证明 是传递的 ， 即要证明 1. 3 . 6 . 2 2nnt R R U1nnR.121nnnn RR4 由传递性定义知 ， 是传递的。 1nnR.)2()(1121 11 11 111 nnkkkkn mmnn mmnn mmnmmnnRRRkkmnRRRRRRR起须从，则令5 (2) 显然有 (3) 若有 R 使 R R且 R是传递的，则由 R R 有 R2 (R)2 R, R3 = R R2 R R (R)2 R, 一般有 Rn R, 从而 。1nnRR,1RRnn 6 即 含于任一包含 R 的传递关系中。 综上所述， 是包含 R 的最小传递关系，因而是 R 的传递闭包，即 1nnR。1)(nnRRt1nnR7 在论域为有限集的情况下，传递闭包的计算变得很简捷。 命题 3.6.8 设 | X | = n， RF ( X X ) ， 则 证明略。 23.6.3.1nmmRRt8 推论 设 | X | = n， RF ( X X ) ， 且 R 是 自反关系 ，则存在 正整数 m ( n ) ， 使 t(R) = Rm， 且 l m 有 Rl = t(R) 。 证明 因为 | X | = n， 所以 又因为 R 是自反的，由命题 3.6.5 (2) 知 R R2 R3 , .1nkkRRt9 因而 在做上述合成运算时，若做到 m ( n ) 次时，出现了 Rm+1 = Rm， 则有 Rm+2 = Rm，进而， t(R) = Rm。这时，若我们取 正整数 l m， 则有 .1nnkk RRRt .1RtRRRRtkklm 10 即有 Rl = t(R) 。 上述推论说明，在计算有限论域上自反的模糊关系 R 的传递闭包时，可以从 R 开始，反复自乘，依次计算出 R， R2， R4， ， ， ，当第一次出现 RkRk = Rk 时，就有 t(R) = Rk 。 iR211 命题 3.6.9 模糊关系的传递闭包 t(R) 有以下性质： (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 .)()()()( 11111111 RtRRRRtnnnnnn (3) 由 (2) 即得。 上述命题中的 (1) 说明 自反关系的传递闭包还是自反的 ， (3) 表明 对称关系的传递闭包还是对称的 。 13 定义 3.6.14 设 RF ( X X )， 称 e(R) 为 R 的 等价闭包 ，若 e(R) 满足下述条件： (1) 等价性： e(R) 是 X 上的模糊等价关系。 (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 是传递的， t(R) 是最小传递闭关系，故有 t(R) R 。 综上所述， 当 R 是相似关系时， t(R) 是包含 R 的最小等价关系 ， 因而 t(R) 是 R 的等价闭包，即 e(R) = t(R) 。 16 引理 设 Rn m， Qm l 是两个模糊矩阵，则对 0， 1 有 ( RQ )= RQ 。 证明 记 R = ( rij )、 Q = ( qij )、 RQ = Sn l = ( sij ) ，类似地，又记 R = (rij )、 Q = (qij ) 、 S = (sij ) 。由于 ,)(1 kjikmkijqrs 17 sij = 1 sij t 1， 2， ， m， 使 rit qtj t 1， 2， ， m， 使 rit ， qtj t 1， 2， ， m， 使 rit=1， qtj=1 又注意到 rik、 qkj、 sij只取 0和 1， 故 (RQ)=RQ。 .1)(1 kjikmkqr 18 由此引理可得， ( Rl ) = ( R ) l 。 推论 设 | X | = n， R 是 X 上的模糊相似关系，则 (1) m n， 使 e(R) = Rm， 且 l m 时有 e(R) = Rl。 (2) 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) = ， 且 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 )。 2)( mR 1mR20 在实际问题中建立的模糊关系，多数情况下都是相似关系，定理 3.6.3 给我们提供了一个求相似关系的等价闭包的方法。当论域为有限集时，此法很简便，即对相似矩阵 R ，求 R2， R4， ， 当 RkRk = Rk 时，便有 e(R) = t(R) = Rk 。 21 例 3.6.10 已知一个模糊相似矩阵 R 求 e (R) 。 14.05.001.016.04.017.09.008.015.07.0106.008.009.0017.0101.006.07.0101.018.0010106.018.001.001R22 解： 14.05.001.016.04.017.09.008.016.08.017.06.07.08.019.07.017.019.05.07.06.07.017.06.019.07.017.018.06.018.09.06.08.012RRR 23 R8= R4 R4= R4， 故 e(R) = t(R) = R4。 19.08.017.019.09.018.09.07.09.018.08.018.07.08.08.019.08.017.019.07.07.07.07.017.07.019.08.017.019.09.018.09.07.09.01224RRR 24 对等价矩阵 e (R) = R4 进行动态聚类，其结果如图 3.39 所示 x1 x6 x2 x4 x7 x5 x3 1 0.9 0.8 0.7 图 3.39 动态聚类图 25 从上例中可以看出， (1) 对于相似矩阵每作一次平方合成运算，模糊矩阵中的元素值便增大一次，也就是 R R2 R4 。 (2) 我们还可以看到，若对原来的相似矩阵 R，先作其 截集，则我们便得到一个经典的相似矩阵 R，由于从定理 3.6.3 的推论 (2)可知 ( e(R) ) = e( R ) ，这样要对 e(R) 作 动 态聚类时，可以先对相似矩阵作 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*， 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 一般地 (R*)n R， 从而 综上所述， t (R*) 是包含 R 的最小等价关系，故 t (R*) 是 R 的等价闭包。当然 R 的等价闭包是存在的。 。1* RRRtnn 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 （相交不空的相似类之集），则 R 。0010 xRxPxR 32 (2) 令 P2(x0) = Rx | Rx P1(x0) ， 则 (3) 设 P1(x0) P2(x0) Pm(x0) , 且 Pm(x0) 满足条件：若 Rx Pm(x0) Rx Pm(x0) = (3.6.24) 则 证明略。 。00201 xRxPxP 0xR 。00 xRxP m 33 定理 3.6.5 表明：对于一个经典相似关系，可以通过归并相似类的办法，得到它的等价类，所有等价类的并就是它的等价闭包。这样，我们就得到一个求等价类的直接方法，即先用不同的 值作相似矩阵 R 的截矩阵 R ， 因 R 是一个经典相似阵，于是便可用本定理的方法通过归并相似类来求等价类。 34 例 3.6.11 设 X = x1, x2, , x7， R 是 X 上的模糊相似关系 试 以 R 为依据将 X 中的元素分类 。 14.0111.013.02.0112.07.01.02.011.08.001.07.016.01.06.015.001R35 解 : 先用平方法 ，求 R 的等价闭包 e (R) 。 ,14.0114.0113.0115.07.05.05.014.08.01.02.07.016.05.0115.05.012R36 再平方 再平方，得 R8= R4。 由命题 3.6.8 及定理 3.6.3 知 e(R) = R4， 依次取 截关系 R， R 是经典等价关系，它诱导出 X 上的一个划分 X/R , 将 X 分成一些等价类 ,15.0115.0115.0115.07.05.05.015.08.05.05.07.0115.0115.05.014R37 当 =1 时，有 e(R)1 诱导的分类为 x1, x4, x5, x7, x2, x3, x6。 10110010100000101100110110010000100000001010110011Re38 当 = 0.8 时，有 e(R)0.8 诱导的分类为 x1, x4, x5, x7, x2 , x6, x3。 10110010100010101100110110010000100010001010110018.0Re39 当 = 0.7 时，有 e(R)0.7 诱导的分类为 x1, x4, x5, x7, x2, x3 , x6。 10110010100110101100110110010100110010011010110017.0Re40 当 = 0.5 时，有 e(R)0.5 = E ， 即 e(R)0.5 将 X 分成一类 x1， x2， x3， x4， x5， x6， x7。 随 由大到小，分类由细到粗，形成一个动态的分类图，如图 3.40 所示 . 41 x1 x4 x5 x7 x2 x6 x3 1 0.8 0.7 0.5 图 3.40 动态聚类图 42 现在用直接法 ，由相似类的归并而求等价类。 先求关于 e(R)1= e(R1) 的等价类，为此先列出关于 1 = 1 的相似类。由于 10110100110000100000100010011R43 故 R1 的相似类是 R1x1 = x1， x4 （ 对应于 r14=1） R1x2 = x2 （ 对应于 r22=1） R1x3 = x3 R1x4 = x1， x4， x5 R1x5 = x5， x7 R1x6 = x6。 在上述相似类中寻找相交不空的类，然后归并。 44 因为 x1， x4 R1 x1 R1 x4 ， 于是归并得到 P1(x1) = R1 x1 R1 x4 = x1， x4， x5， 又因为有 x5 P1 (x1) R1 x5 ， 再次归并得到 P2(x1) = R1x1 R1x4 R1x5 = x1， x4， x5， x7。 45 由于不含于 P2(x1) 的 R1 的相似类 (在本例中即 R1x2 , R1 x3 , R1 x6 ) 与 P2(x1) 不相交，所以以 x1 为代表的关于 e (R1) = e (R)1 的等 价类就是 P2(x1)。其余类似。在本例中，因其余的相似类两两不相交，不需归并，它们就是相应的等价类，因而我们最终得到关于 e (R)1 的等价类为 x1， x4， x5， x7 ， x2， x3， x6 （ 3. 6. 25） 46 其次，取 2 = 0.8。 由于 10110100110000101000100010018.0R47 故 R0.8 的相似类是 R0.8x1 = x1， x4 （ 对应于 r14=1） R0.8x2 = x2 ， x6 （ 对应于 r26=1） R0.8x3 = x3 R0.8x4 = x1， x4， x5 R0.8x5 = x5， x7 在上述相似类中寻找相交不空的类，然后归并。 48 P2(x1) = R1x1 R1x4 R1x5 = x1， x4， x5， x7。 因其余的相似类两两不相交，不需归并，它们就是相应的等价类，因而我们最终得到关于 e (R)0.8 的等价类为 x1， x4， x5， x7， x2， x6， x3 (3.6.26) 49 或： 当 2 = 0.8 时 ， 此时，由于 r26=0.8， 应将 e(R)1x2（ 即 R1 x2 ） 与 e (R)1 x6 （ 即 R1 x6 ） 归并，即将 (3.6.25) 中 x2 所在的等价类与 x6 所在的等价类归并 （ 若还有另外的 rij = 0.8， 类似进行 ）， 归并后得到关于 e (R) 的等价类为 x1， x4， x5， x7， x2， x6， x3 (3.6.26) 50 再次，取 3=0.7， 由于 10110100110100101001100010017.0R51 故 R0.7 的相似类是 R0.7x1 = x1， x4 R0.7x2 = x2， x3， x6 R0.7x4 = x1， x4， x5 R0.7x5 = x5， x7 在上述相似类中寻找相交不空的类，然后归并，于是得到关于 e(R0.7) = e(R)0.7 的等价类如下 x1， x4， x5， x7， x2， x3， x6。 (3. 6. 27) 52 取 4 = 0.6， 由于 这时没有给出新的分类结果 ， 即由 e(R)0.6 得到的等价类与 e(R)0.7 的等价类相同。 10110100110100101001100010017.06.0RR53 取 5 = 0.5， 由于 10110100110100101001111110015.0R54 故 R0.5 的相似类是 R0.5x1 = x1， x4， x5， x6， x7 R0.5x2 = x2， x3， x6 将上述相似类归并后，得到关于 e(R0.5) = e(R)0.5 的等价类是将全部元素归入一类的结果。 综上所述，最后所得的聚类结果亦如图 3.40 所示。 55 3.6.6 直接聚类的最大树法 用图形来直接进行聚类，更为方便。 设 R = (rij)nn 是 X = x1， x2， ， xn 上的模糊相似关系 ， rij= R(xi， xj) 表示 X 内元素 xi 与 xj 的相关程度。在图形上，用顶点表示元素 xi， xj， 连接 xi 与 xj 的线段称为 边 ，边旁标明的数字为 rij， 称为该边的强度 ，由边依次连接 k 个顶点 ： xi1, xi2, , xik 56 称为 链 。顶点不相同的链称为 通道 ，记为 L (xi1, , xik )。 通道中各边强度的最小值为该 通道的强度 ，即 通道 L (xi1, , xik ) 的强度 = ri1i2 rik-1ik 任意点间都有通道的图形称为 连通图 ，起点与终点重合的链称为 回路 ，无回路的连通图称为 树（参见图 3.41） 57 xi rij xj rjk xk 图 3.41 通道与链 58 用图形法来进行直接聚类时，是把相似类归并为关于 e(R) 的等 价类。归并时，使阈值 逐步从大到小，依次把强度为 的边连接有关的顶点，但注意 不连回路 ，也就得到若干边的强度为 的通道。对 0, 1， 在不同 水平上将若干通道相连，就得到若干互不相连的树。每棵树中任意两顶点间通道的强度大于等于 ，这些互不相连的树就给出了分类的结果：同一棵树的顶点归于同一类。 从大到小，直至得到最大的树的过程，给出论域 X 中元素的一个动态分类结果。 59 例 3.6.12 用最大树法对例 3.6.11 直接聚类。 =1 时的图形如图 3.42 x1 x3 1 x2 x4 1 x6 x5 1 x7 图 3.42 = 1 时的连通图 对应的分类为 x1, x4 , x5, x7, x2, x3, x6 。 60 = 0.8 时的图形如图 3.43 x1 x3 1 x2 x4 0.8 1 x6 x5 1 x7 图 3.43 = 0.8 时的连通图 对应的分类为 x1, x4 , x5, x7, x2, x6, x3。 61 = 0.7 时的图形如图 3.44 x1 x3 0.7 1 x2 x4 0.8 1 x6 x5 1 x7 图 3.44 = 0.7 时的连通图 对应的分类为 x1, x4 , x5, x7, x2, x6， x3。 62 = 0.5 时的图形如图 3.45， 是最大树， 0.5 x1 x3 1 0.7 x2 x4 0.8 1 x6 x5 1 x7 图 3.45 = 0.5 时的连通图 对应的分类为 x1, x2, x3, x4, x5, x6， x7。 63 注： 从最大树图中可以看出，若去掉那些强度小于 的边，就把最大树截成互不相连的几棵子树，这就是对应 水平上的一种分类结果，同一棵树上的顶点属于同一等价类。 64 例 3.6.13 用直接法求例 3.6.10 给出的模糊相似矩阵 R 的等价类，并作出最大树图。即 求 R 的等价类 。 14.05.001.016.04.017.09.008.015.07.0106.008.009.0017.0101.006.07.0101.018.0010106.018.001.001R65 解 = 1 时的图形如 下： x6 x5 x2 x7 x3 x4 x1 1 1 1 66 解 = 0.9 时的图形如 下： x5 x2 x7 x3 x4 x1 x6 1 1 1 0.9 67 解 = 0.8 时的图形如 下： x5 x2 x7 x3 x4 x1 x6 0.8 1 1 1 0.9 68 解 = 0.7 时的图形如 下： x5 x2 x7 x3 x4 x1 x6 0.8 1 1 1 0.7 0.9 69 我们用最大树法给出问题的动态聚类。 当 = 1 时，由 最大树得 对应的分类为： x1， x6 , x2， x4， x7 , x3， x5。 当 = 0.9 时，由 最大树得 对应的分类为： x1， x2， x4， x6， x7 , x3， x5。 当 = 0.8 时，由 最大树得 对应的分类为： x1， x2， x4， x5， x6， x7 , x3。 当 = 0.7 时，由 最大树得 对应的分类为： x1， x2， x3， x4， x5， x6， x7 。 70 教材 P133 用归并相似类法给出了同样的分类。 求模糊相似关系的等价类有以下 三种 方法： 等价闭包法 (e(R) 间接法 归并相似类法 最大树法 直接法 71 3.6.7 模糊聚类分析 模糊聚类分析在实际问题中有广泛的应用，这是由于实际问题中，一组事物是否属于某一类常带有模糊性，也就是问题的界限不是十分清晰的。我们不能明确地回答 “是” 或 “否”， 而是只能作出 “ 在某种程度上是 ” 的回答，这就是模糊聚类分析。 本节主要讨论基于模糊等价关系的动态聚类的实际应用。 72 1. 特征抽取 假设待分类对象的集合为 X = X1, X2, , Xn ，集合中的每个元素具有 m 个特征，设第 i 个对象 Xi 的第 j ( j = 1, 2, , m ) 个特征为 xij， 则 Xi 就可以用这 m 个特征的取值来描述，记 Xi = ( xi1, xi2, , xim) ( i =1， 2， ， n ) (3.6.28) 73 为了计算简便，并使特征仅具有相对的意义，我们要首先对特征的观测值进行预先处理，使各特征值的取值在单位区间 0, 1 中。 设 Xi 的观测值为 Xi 0， Xi0 = ( xi10， xi20， ， xim0 ) ( i=1, 2, n) (3.6.29) 所以用下列各公式对 Xi 0 进行 “规格化” 的 预处理 。 74 (1) xij = cxij0 ( i =1, , n； j =1, , m) (3.6.30) c 是一个常数，选择 c 使任何 xij 在 0, 1 中。 (2) xij = cxij0 / max(xij0) ( i =1, , n; j =1, , m) (3.6.31) 即选择所有的特征中的最大值作分母。 (3) 当特征值中出现负值时，则用下式压缩到 0,1： 32.6.3,1;,1m i nm a xm i n0000mjnixxxxxijijijijij 75 当特征值不是负值时，当然也可以用上式来“规格化” 式中 是全部特征值的均值，分子是特征值与均值的距离。用此式 “规格化” 时应注意：只要与均值的距离相等，特征值的大小的方向性就被“湮灭”。 33.6.3,1;,1m i nm a x4 000mjnixxxxxijijijij nimjijxmnx1 10176 2. 建立 X 上的模糊关系 （ 模糊相似矩阵 ） 设待分类对象的全体是 X= X1, X2, , Xn ，我们首先要鉴别 X 中的元素 Xi 与 Xj 的接近程度（相似程度）。用 0, 1 中的数 rij 来表示 Xi 与 Xj 的相似程度，称为 相似系数 。相似系数组成一个矩阵 (rij)nn 称为 相似系数矩阵 ，它是 X 上的模糊相似关系。我们对此关 系矩阵求其等价闭包或等价类，就能对 X 中的元素进行聚类。 77 为了确定相似系数，必须使相似系数符合自反、对称的要求，可根据实际情况选用下列方法之一。 1） 数量积法 其中 34.6.3,1,11mijkikijjixxMjir mkjkikji xxM1m a x78 2） 夹角余弦法 3） 相关系数法 其中 35.6.312121mkjkmkikmkjkikijxxxxr 36.6.3,12121mkjikmkiikmkjjkijkijxxxxxxxxrmkjkjmkiki xmxxmx111,179 4） 指数相似系数法 其中 sk 与 m 为常数。 5） 绝对值指数法 37.6.3,e xp112 mk kjkikij sxxmr 38.6.3,e x p1 mkjkikij xxr80 6） 绝对值倒数法 其中 M 为适当选择的常数， M 的选择使 rij0, 1。 39.6.3,11jixxMjirmkjkikij81 7) 非参数法 令 是 xik 与 xjk 的均值 ）， nij+= xi1 xj1, xi2 xj2, , xim xjm 中正数个数， nij = xi1 xj1, xi2 xj2, , xim xjm 中负数个数， jijjkjkiikik xxxxxxxx ,(, 40.6.3121 ijijijijij nnnnr82 8） 贴近度法 贴近度表示两个模糊向量之间接近的程度 ， 它符合自反 、 对称的要求 ， 所以可以用来表示相似系数 。 我们将 X 中的元素 Xi， Xj 看成是各自特征的模糊向量 ， 便可以用贴近度来表示相似系数 rij， rij = ( Xi, Xj ) 83 (1) 当 取内外积贴近度时 或 41.6.3,1,111jixxxxjirjkikmkjkikmkij 42.6.3,21,111jixxxxjirjkikmkjkikmkij84 (2) 最大最小法，当 取 (3.5.47) 式时 (3) 算术平均最小法，当 取 (3.5.48) 式时 43.6.311mkjkikmkjkikijxxxxr 44.6.3211mkjkikmkjkikijxxxxr85 (4) 几何平均最小法 ， 当 取 (3.5.51) 式时 (5) 绝对值减数法 ， 当 取距离贴近度时 rij = 1 c (dp ( Xi， Xj ) 式中 c， 为常数， p 为各种距离的代码系数。 45.6.312/11mkjkikmkjkikijxxxxr86 当 p =1 时， dp 就是海明距离，此时求相似系数的方法称绝对值减数法，其相似系数为 当 p = 2 时， dp 就是欧氏距离，此时有 46.6.311mkjkikij xxcr 47.6.3112mkjkikij xxcr87 9） 经验法 请有经验的人来分别对 Xi 与 Xj 的相似性打分，设有 s 个人参加评分，若第 k 个人 (1 k s) 认为 Xi 与 Xj 相似的程度为 aij(k) （ 在 0， 1 中 ） ，他对自己评分的自信度也打分，若自信度分值是 bij(k) ， 则可以用下式来计算相似系数 : 48.6.311kijskkijij basr 88 在以上确定相似系数的诸多方法中，究竟选用哪一种合适，需要根据问题的具体性质来决定。 89 例 3.6.14 环境单元分类 每个环境单元可以包括空气 、 水分 、 土壤 、 作物等四个要素 。 环境单元的污染状况由污染物在四要素中含量的超限度来描写 。 假设有五个单元 x1, x2, x3, x4, x5， 它们的污染数据如表 3.13 所示。 90 取论域 X = x1, x2, x3, x4, x5， 按 (3.6.30) 式 “规格化”，取 c = 0.1，再按 （ 3.6.46） 式求相似系数 （ 取 c = 1)， 要素 数据 单元 空气 水分 土壤 作物 x1 x2 x3 x4 x5 5 2 5 1 2 5 3 5 5 4 3 4 2 3 5 2 5 3 1 1 表 3.13 污染数据 91 得到模糊相似矩阵 49.6.316.01.04.03.06.013.02.05.01.03.011.08.04.02.01.011.03.05.08.01.0155ijrR92 3. 聚类 可以有三种方法来对模糊相似矩阵聚类 。 1） 传递闭包法 （ 平方法 ） 求出模糊相似矩阵的传递闭包 t (R) ， 它就是 R 的等价闭包 e (R) = t (R) ， 然后求其 截关系 e(R) 。 它是经典等价关系，让 从 1 降至 0， 当 变化时，它们给出一个动态的分类结果。 求 R 的传递闭包 t(R) 时，可以用平方法，即求 R2, R4, , Rk， 若有 Rk Rk = Rk， 则 t(R) = Rk。 93 经计算可知 16.05.04.05.06.015.04.05.05.05.014.08.04.04.04.014.05.05.08.04.0148RR94 当 = 1 时，分成五类： x1, x2 , x3, x4, x5 当 = 0.8 时，分成四类： x1, x3, x2 , x4, x5 当 = 0.6 时，分成三类： x1, x3, x2 , x4, x5 当 = 0.5 时 ， 分成二类： x1, x3 , x4, x5, x2 当 = 0.4 时 ， 分成一类： x1, x2, x3, x4, x5 95 其动态分类如图 3.47 所示： =1 x1 x3 x4 x5 x2 0.8 0.6 0.5 0.4 图 3.47 动态聚类图 96 2） 直接聚类法 根据模糊相似矩阵 (3.6.49) 来直接由相似类求等价类。 当 =1 时，该矩阵只有对角线上的元素为 1，所以不许归并相似类，所得到的 e(R)1 的等价类为 x1， x2， x3， x4， x5。 当 = 0.8 时，先求经典矩阵 R0.8， 有此求得它的相似类是 97 R0.8x1 = x1, x3， R0.8x2 = x2 ， R0.8x4 = x4， R0.8x5 = x5。 在归并时，找不到与 x1, x3 相交的其它等价类，于是 e(R)0.8 的等价类为： x1, x3, x2 , x4, x5。 同样 = 0.6 时，相似类为 R0.6x1 = x1, x3, R0.6x2 = x2, R0.6x4 = x4, x5，也无法再进一步归并，于是 e(R)0.6 的等价类为： x1, x3, x2 , x4, x5。 98 当 =0.5 时，相似类为 R0.5x1 =x1, x3 , x4，R0.5x2 = x2, R0.5x4 = x1, x4, x5， 因此可以把相似类 R0.5x1 与 R0.5x4 归并，得 P1(x1) = R0.5x1 R0.5x4 = x1, x3 , x4, x5， 最终得到的 e(R)0.5 的等价类为 x1, x3 , x4, x5, x2。 当 = 0.4 时，得到 R0.4x2 = x2， x5，于是可以和 P1(x1) 归并，即 P2(x1) = x1, x2, x3, x4, x5，这就是 e(R)0.4 的等价类。 99 3） 最大树法 （ Kruskal） 在模糊相似矩阵 (3.6.49) 中，从 =1 开始逐步做连通图，直到 = 0 时为止，每作一条边，就在边上写出 rij 之值（连通强度）。 注意不要做回路。 从原则上来说，可以选择任一元素（ 顶点 ） 作为起始点，但一般总是选有相似类的元素开始。例如在本例中当 = 0.8 时，就有相似类 x1, x3， 于是就把 x1 选为起始顶点，先作出强度为