1 3.6.4 模糊傳遞閉包和等價閉包 通常的模糊關(guān)系，不一定有傳遞性，因而不是模糊等價關(guān)系，對這種模糊關(guān)系直接進(jìn)行上述分類顯然是不合理的。為此，我們希望尋求一種方法，能將不是等價的模糊關(guān)系進(jìn)行改造，以便分類使用 2 定義 3.6.13 設(shè) RF ( X X )， 稱 t(R) 為 R 的傳遞閉包 ，如果 t(R) 滿足 : (1) 傳遞性： (t(R)2 t(R) ； (2) 包容性： R t(R) ； (3) 最小性：若 R是 X 上的模糊傳遞關(guān)系，且 R R t(R) R， 即 R 的傳遞閉包是包含 R 的最小的傳遞關(guān)系。 3 定理 3.6.2 設(shè) 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 的傳遞關(guān)系中。 綜上所述， 是包含 R 的最小傳遞關(guān)系，因而是 R 的傳遞閉包，即 1nnR。1)(nnRRt1nnR7 在論域為有限集的情況下，傳遞閉包的計算變得很簡捷。 命題 3.6.8 設(shè) | X | = n， RF ( X X ) ， 則 證明略。 23.6.3.1nmmRRt8 推論 設(shè) | X | = n， RF ( X X ) ， 且 R 是 自反關(guān)系 ，則存在 正整數(shù) m ( n ) ， 使 t(R) = Rm， 且 l m 有 Rl = t(R) 。 證明 因為 | X | = n， 所以 又因為 R 是自反的，由命題 3.6.5 (2) 知 R R2 R3 , .1nkkRRt9 因而 在做上述合成運算時，若做到 m ( n ) 次時，出現(xiàn)了 Rm+1 = Rm， 則有 Rm+2 = Rm，進(jìn)而， t(R) = Rm。這時，若我們?nèi)?正整數(shù) l m， 則有 .1nnkk RRRt .1RtRRRRtkklm 10 即有 Rl = t(R) 。 上述推論說明，在計算有限論域上自反的模糊關(guān)系 R 的傳遞閉包時，可以從 R 開始，反復(fù)自乘，依次計算出 R， R2， R4， ， ， ，當(dāng)?shù)谝淮纬霈F(xiàn) RkRk = Rk 時，就有 t(R) = Rk 。 iR211 命題 3.6.9 模糊關(guān)系的傳遞閉包 t(R) 有以下性質(zhì)： (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) 說明 自反關(guān)系的傳遞閉包還是自反的 ， (3) 表明 對稱關(guān)系的傳遞閉包還是對稱的 。 13 定義 3.6.14 設(shè) RF ( X X )， 稱 e(R) 為 R 的 等價閉包 ，若 e(R) 滿足下述條件： (1) 等價性： e(R) 是 X 上的模糊等價關(guān)系。 (2) 包容性： R e(R)。 (3) 最小性：若 R 是 X 上的模糊等價關(guān)系，且 R R e(R) R 。 顯然， R 的等價閉包是包含 R 的最小的等價關(guān)系。 14 定理 3.6.3 設(shè) RF ( X X ) 是相似關(guān)系 ( 即 R 是自反、對稱模糊關(guān)系 ) ，則 e(R) = t(R) , 即模糊相似關(guān)系的傳遞閉包就是它的等價閉包。 證明 因為 R 是自反和對稱的，由命題 3.6.9 知，R 的傳遞閉包 t(R) 也是自反和對稱的。又 t(R) 作為傳遞閉包本身是傳遞的，且包含 R， 因此 t(R) 是 15 包含 R 的模糊等價關(guān)系。 若 R 也是模糊等價關(guān)系，且包含 R。 由于 R 是傳遞的， t(R) 是最小傳遞閉關(guān)系，故有 t(R) R 。 綜上所述， 當(dāng) R 是相似關(guān)系時， t(R) 是包含 R 的最小等價關(guān)系 ， 因而 t(R) 是 R 的等價閉包，即 e(R) = t(R) 。 16 引理 設(shè) 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 。 推論 設(shè) | X | = n， R 是 X 上的模糊相似關(guān)系，則 (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 上的相似關(guān)系， 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 在實際問題中建立的模糊關(guān)系，多數(shù)情況下都是相似關(guān)系，定理 3.6.3 給我們提供了一個求相似關(guān)系的等價閉包的方法。當(dāng)論域為有限集時，此法很簡便，即對相似矩陣 R ，求 R2， R4， ， 當(dāng) 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 進(jìn)行動態(tài)聚類，其結(jié)果如圖 3.39 所示 x1 x6 x2 x4 x7 x5 x3 1 0.9 0.8 0.7 圖 3.39 動態(tài)聚類圖 25 從上例中可以看出， (1) 對于相似矩陣每作一次平方合成運算，模糊矩陣中的元素值便增大一次，也就是 R R2 R4 。 (2) 我們還可以看到，若對原來的相似矩陣 R，先作其 截集，則我們便得到一個經(jīng)典的相似矩陣 R，由于從定理 3.6.3 的推論 (2)可知 ( e(R) ) = e( R ) ，這樣要對 e(R) 作 動 態(tài)聚類時，可以先對相似矩陣作 26 截集，得到經(jīng)典的相似矩陣，然后再求經(jīng)典相似矩陣的等價閉包 e(R )。 由于經(jīng)典相似矩陣中的元素僅有 1 與 0（即非此即彼）兩種，找出所有元素相關(guān)值為 1 的元素，加以歸并，就可以找出該元素的等價類，從而可以用簡單的方法來求 e(R )。 以上所述的理論，在以下的定理中詳細(xì)說明。 27 若 R 不是相似關(guān)系， R 的等價閉包是否存在？又如何求得其傳遞閉包？下面的定理回答了這個問題。 定理 3.6.4 設(shè) R F ( X X )， 則 R 的等價閉包 e (R) 必存在，且 e (R) = t (R*) ， 式中 R* = R R-1 I。 證明 先證 R* 是包含 R 的相似關(guān)系。因為 R R*， 28 I R*， 故 R* 是包含 R 的自反關(guān)系。又有 (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 的相似關(guān)系。又由定理 3.6.3， t (R*) 是模糊等價關(guān)系，且 29 R R* t (R*)。 次證 t (R*) 是 X 上包含 R 的最小等價關(guān)系。 設(shè) RF ( X X )， R 是等價關(guān)系，且 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 的最小等價關(guān)系，故 t (R*) 是 R 的等價閉包。當(dāng)然 R 的等價閉包是存在的。 。1* RRRtnn 31 3.6.5 求相似矩陣的等價類的直接方法 定理 3.6.5 設(shè) | X | = n， R 是 X 上的經(jīng)典相似關(guān)系，x X 時，記 R x = y X | (x, y) R， 并稱 Rx 為 X 的 相似類 。 記 = e (R) = t ( R) 。 設(shè) x0 X， 于是 (1) 令 P1(x0) = Rx | Rx Rx0 （相交不空的相似類之集），則 R 。0010 xRxPxR 32 (2) 令 P2(x0) = Rx | Rx P1(x0) ， 則 (3) 設(shè) 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 表明：對于一個經(jīng)典相似關(guān)系，可以通過歸并相似類的辦法，得到它的等價類，所有等價類的并就是它的等價閉包。這樣，我們就得到一個求等價類的直接方法，即先用不同的 值作相似矩陣 R 的截矩陣 R ， 因 R 是一個經(jīng)典相似陣，于是便可用本定理的方法通過歸并相似類來求等價類。 34 例 3.6.11 設(shè) X = x1, x2, , x7， R 是 X 上的模糊相似關(guān)系 試 以 R 為依據(jù)將 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， 依次取 截關(guān)系 R， R 是經(jīng)典等價關(guān)系，它誘導(dǎo)出 X 上的一個劃分 X/R , 將 X 分成一些等價類 ,15.0115.0115.0115.07.05.05.015.08.05.05.07.0115.0115.05.014R37 當(dāng) =1 時，有 e(R)1 誘導(dǎo)的分類為 x1, x4, x5, x7, x2, x3, x6。 10110010100000101100110110010000100000001010110011Re38 當(dāng) = 0.8 時，有 e(R)0.8 誘導(dǎo)的分類為 x1, x4, x5, x7, x2 , x6, x3。 10110010100010101100110110010000100010001010110018.0Re39 當(dāng) = 0.7 時，有 e(R)0.7 誘導(dǎo)的分類為 x1, x4, x5, x7, x2, x3 , x6。 10110010100110101100110110010100110010011010110017.0Re40 當(dāng) = 0.5 時，有 e(R)0.5 = E ， 即 e(R)0.5 將 X 分成一類 x1， x2， x3， x4， x5， x6， x7。 隨 由大到小，分類由細(xì)到粗，形成一個動態(tài)的分類圖，如圖 3.40 所示 . 41 x1 x4 x5 x7 x2 x6 x3 1 0.8 0.7 0.5 圖 3.40 動態(tài)聚類圖 42 現(xiàn)在用直接法 ，由相似類的歸并而求等價類。 先求關(guān)于 e(R)1= e(R1) 的等價類，為此先列出關(guān)于 1 = 1 的相似類。由于 10110100110000100000100010011R43 故 R1 的相似類是 R1x1 = x1， x4 （ 對應(yīng)于 r14=1） R1x2 = x2 （ 對應(yīng)于 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 為代表的關(guān)于 e (R1) = e (R)1 的等 價類就是 P2(x1)。其余類似。在本例中，因其余的相似類兩兩不相交，不需歸并，它們就是相應(yīng)的等價類，因而我們最終得到關(guān)于 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 （ 對應(yīng)于 r14=1） R0.8x2 = x2 ， x6 （ 對應(yīng)于 r26=1） R0.8x3 = x3 R0.8x4 = x1， x4， x5 R0.8x5 = x5， x7 在上述相似類中尋找相交不空的類，然后歸并。 48 P2(x1) = R1x1 R1x4 R1x5 = x1， x4， x5， x7。 因其余的相似類兩兩不相交，不需歸并，它們就是相應(yīng)的等價類，因而我們最終得到關(guān)于 e (R)0.8 的等價類為 x1， x4， x5， x7， x2， x6， x3 (3.6.26) 49 或： 當(dāng) 2 = 0.8 時 ， 此時，由于 r26=0.8， 應(yīng)將 e(R)1x2（ 即 R1 x2 ） 與 e (R)1 x6 （ 即 R1 x6 ） 歸并，即將 (3.6.25) 中 x2 所在的等價類與 x6 所在的等價類歸并 （ 若還有另外的 rij = 0.8， 類似進(jìn)行 ）， 歸并后得到關(guān)于 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 在上述相似類中尋找相交不空的類，然后歸并，于是得到關(guān)于 e(R0.7) = e(R)0.7 的等價類如下 x1， x4， x5， x7， x2， x3， x6。 (3. 6. 27) 52 取 4 = 0.6， 由于 這時沒有給出新的分類結(jié)果 ， 即由 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 將上述相似類歸并后，得到關(guān)于 e(R0.5) = e(R)0.5 的等價類是將全部元素歸入一類的結(jié)果。 綜上所述，最后所得的聚類結(jié)果亦如圖 3.40 所示。 55 3.6.6 直接聚類的最大樹法 用圖形來直接進(jìn)行聚類，更為方便。 設(shè) R = (rij)nn 是 X = x1， x2， ， xn 上的模糊相似關(guān)系 ， rij= R(xi， xj) 表示 X 內(nèi)元素 xi 與 xj 的相關(guān)程度。在圖形上，用頂點表示元素 xi， xj， 連接 xi 與 xj 的線段稱為 邊 ，邊旁標(biāo)明的數(shù)字為 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 用圖形法來進(jìn)行直接聚類時，是把相似類歸并為關(guān)于 e(R) 的等 價類。歸并時，使閾值 逐步從大到小，依次把強度為 的邊連接有關(guān)的頂點，但注意 不連回路 ，也就得到若干邊的強度為 的通道。對 0, 1， 在不同 水平上將若干通道相連，就得到若干互不相連的樹。每棵樹中任意兩頂點間通道的強度大于等于 ，這些互不相連的樹就給出了分類的結(jié)果：同一棵樹的頂點歸于同一類。 從大到小，直至得到最大的樹的過程，給出論域 X 中元素的一個動態(tài)分類結(jié)果。 59 例 3.6.12 用最大樹法對例 3.6.11 直接聚類。 =1 時的圖形如圖 3.42 x1 x3 1 x2 x4 1 x6 x5 1 x7 圖 3.42 = 1 時的連通圖 對應(yīng)的分類為 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 時的連通圖 對應(yīng)的分類為 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 時的連通圖 對應(yīng)的分類為 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 時的連通圖 對應(yīng)的分類為 x1, x2, x3, x4, x5, x6， x7。 63 注： 從最大樹圖中可以看出，若去掉那些強度小于 的邊，就把最大樹截成互不相連的幾棵子樹，這就是對應(yīng) 水平上的一種分類結(jié)果，同一棵樹上的頂點屬于同一等價類。 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 我們用最大樹法給出問題的動態(tài)聚類。 當(dāng) = 1 時，由 最大樹得 對應(yīng)的分類為： x1， x6 , x2， x4， x7 , x3， x5。 當(dāng) = 0.9 時，由 最大樹得 對應(yīng)的分類為： x1， x2， x4， x6， x7 , x3， x5。 當(dāng) = 0.8 時，由 最大樹得 對應(yīng)的分類為： x1， x2， x4， x5， x6， x7 , x3。 當(dāng) = 0.7 時，由 最大樹得 對應(yīng)的分類為： x1， x2， x3， x4， x5， x6， x7 。 70 教材 P133 用歸并相似類法給出了同樣的分類。 求模糊相似關(guān)系的等價類有以下 三種 方法： 等價閉包法 (e(R) 間接法 歸并相似類法 最大樹法 直接法 71 3.6.7 模糊聚類分析 模糊聚類分析在實際問題中有廣泛的應(yīng)用，這是由于實際問題中，一組事物是否屬于某一類常帶有模糊性，也就是問題的界限不是十分清晰的。我們不能明確地回答 “是” 或 “否”， 而是只能作出 “ 在某種程度上是 ” 的回答，這就是模糊聚類分析。 本節(jié)主要討論基于模糊等價關(guān)系的動態(tài)聚類的實際應(yīng)用。 72 1. 特征抽取 假設(shè)待分類對象的集合為 X = X1, X2, , Xn ，集合中的每個元素具有 m 個特征，設(shè)第 i 個對象 Xi 的第 j ( j = 1, 2, , m ) 個特征為 xij， 則 Xi 就可以用這 m 個特征的取值來描述，記 Xi = ( xi1, xi2, , xim) ( i =1， 2， ， n ) (3.6.28) 73 為了計算簡便，并使特征僅具有相對的意義，我們要首先對特征的觀測值進(jìn)行預(yù)先處理，使各特征值的取值在單位區(qū)間 0, 1 中。 設(shè) Xi 的觀測值為 Xi 0， Xi0 = ( xi10， xi20， ， xim0 ) ( i=1, 2, n) (3.6.29) 所以用下列各公式對 Xi 0 進(jìn)行 “規(guī)格化” 的 預(yù)處理 。 74 (1) xij = cxij0 ( i =1, , n； j =1, , m) (3.6.30) c 是一個常數(shù)，選擇 c 使任何 xij 在 0, 1 中。 (2) xij = cxij0 / max(xij0) ( i =1, , n; j =1, , m) (3.6.31) 即選擇所有的特征中的最大值作分母。 (3) 當(dāng)特征值中出現(xiàn)負(fù)值時，則用下式壓縮到 0,1： 32.6.3,1;,1m i nm a xm i n0000mjnixxxxxijijijijij 75 當(dāng)特征值不是負(fù)值時，當(dāng)然也可以用上式來“規(guī)格化” 式中 是全部特征值的均值，分子是特征值與均值的距離。用此式 “規(guī)格化” 時應(yīng)注意：只要與均值的距離相等，特征值的大小的方向性就被“湮滅”。 33.6.3,1;,1m i nm a x4 000mjnixxxxxijijijij nimjijxmnx1 10176 2. 建立 X 上的模糊關(guān)系 （ 模糊相似矩陣 ） 設(shè)待分類對象的全體是 X= X1, X2, , Xn ，我們首先要鑒別 X 中的元素 Xi 與 Xj 的接近程度（相似程度）。用 0, 1 中的數(shù) rij 來表示 Xi 與 Xj 的相似程度，稱為 相似系數(shù) 。相似系數(shù)組成一個矩陣 (rij)nn 稱為 相似系數(shù)矩陣 ，它是 X 上的模糊相似關(guān)系。我們對此關(guān) 系矩陣求其等價閉包或等價類，就能對 X 中的元素進(jìn)行聚類。 77 為了確定相似系數(shù)，必須使相似系數(shù)符合自反、對稱的要求，可根據(jù)實際情況選用下列方法之一。 1） 數(shù)量積法 其中 34.6.3,1,11mijkikijjixxMjir mkjkikji xxM1m a x78 2） 夾角余弦法 3） 相關(guān)系數(shù)法 其中 35.6.312121mkjkmkikmkjkikijxxxxr 36.6.3,12121mkjikmkiikmkjjkijkijxxxxxxxxrmkjkjmkiki xmxxmx111,179 4） 指數(shù)相似系數(shù)法 其中 sk 與 m 為常數(shù)。 5） 絕對值指數(shù)法 37.6.3,e xp112 mk kjkikij sxxmr 38.6.3,e x p1 mkjkikij xxr80 6） 絕對值倒數(shù)法 其中 M 為適當(dāng)選擇的常數(shù)， M 的選擇使 rij0, 1。 39.6.3,11jixxMjirmkjkikij81 7) 非參數(shù)法 令 是 xik 與 xjk 的均值 ）， nij+= xi1 xj1, xi2 xj2, , xim xjm 中正數(shù)個數(shù)， nij = xi1 xj1, xi2 xj2, , xim xjm 中負(fù)數(shù)個數(shù)， jijjkjkiikik xxxxxxxx ,(, 40.6.3121 ijijijijij nnnnr82 8） 貼近度法 貼近度表示兩個模糊向量之間接近的程度 ， 它符合自反 、 對稱的要求 ， 所以可以用來表示相似系數(shù) 。 我們將 X 中的元素 Xi， Xj 看成是各自特征的模糊向量 ， 便可以用貼近度來表示相似系數(shù) rij， rij = ( Xi, Xj ) 83 (1) 當(dāng) 取內(nèi)外積貼近度時 或 41.6.3,1,111jixxxxjirjkikmkjkikmkij 42.6.3,21,111jixxxxjirjkikmkjkikmkij84 (2) 最大最小法，當(dāng) 取 (3.5.47) 式時 (3) 算術(shù)平均最小法，當(dāng) 取 (3.5.48) 式時 43.6.311mkjkikmkjkikijxxxxr 44.6.3211mkjkikmkjkikijxxxxr85 (4) 幾何平均最小法 ， 當(dāng) 取 (3.5.51) 式時 (5) 絕對值減數(shù)法 ， 當(dāng) 取距離貼近度時 rij = 1 c (dp ( Xi， Xj ) 式中 c， 為常數(shù)， p 為各種距離的代碼系數(shù)。 45.6.312/11mkjkikmkjkikijxxxxr86 當(dāng) p =1 時， dp 就是海明距離，此時求相似系數(shù)的方法稱絕對值減數(shù)法，其相似系數(shù)為 當(dāng) p = 2 時， dp 就是歐氏距離，此時有 46.6.311mkjkikij xxcr 47.6.3112mkjkikij xxcr87 9） 經(jīng)驗法 請有經(jīng)驗的人來分別對 Xi 與 Xj 的相似性打分，設(shè)有 s 個人參加評分，若第 k 個人 (1 k s) 認(rèn)為 Xi 與 Xj 相似的程度為 aij(k) （ 在 0， 1 中 ） ，他對自己評分的自信度也打分，若自信度分值是 bij(k) ， 則可以用下式來計算相似系數(shù) : 48.6.311kijskkijij basr 88 在以上確定相似系數(shù)的諸多方法中，究竟選用哪一種合適，需要根據(jù)問題的具體性質(zhì)來決定。 89 例 3.6.14 環(huán)境單元分類 每個環(huán)境單元可以包括空氣 、 水分 、 土壤 、 作物等四個要素 。 環(huán)境單元的污染狀況由污染物在四要素中含量的超限度來描寫 。 假設(shè)有五個單元 x1, x2, x3, x4, x5， 它們的污染數(shù)據(jù)如表 3.13 所示。 90 取論域 X = x1, x2, x3, x4, x5， 按 (3.6.30) 式 “規(guī)格化”，取 c = 0.1，再按 （ 3.6.46） 式求相似系數(shù) （ 取 c = 1)， 要素 數(shù)據(jù) 單元 空氣 水分 土壤 作物 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 污染數(shù)據(jù) 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) ， 然后求其 截關(guān)系 e(R) 。 它是經(jīng)典等價關(guān)系，讓 從 1 降至 0， 當(dāng) 變化時，它們給出一個動態(tài)的分類結(jié)果。 求 R 的傳遞閉包 t(R) 時，可以用平方法，即求 R2, R4, , Rk， 若有 Rk Rk = Rk， 則 t(R) = Rk。 93 經(jīng)計算可知 16.05.04.05.06.015.04.05.05.05.014.08.04.04.04.014.05.05.08.04.0148RR94 當(dāng) = 1 時，分成五類： x1, x2 , x3, x4, x5 當(dāng) = 0.8 時，分成四類： x1, x3, x2 , x4, x5 當(dāng) = 0.6 時，分成三類： x1, x3, x2 , x4, x5 當(dāng) = 0.5 時 ， 分成二類： x1, x3 , x4, x5, x2 當(dāng) = 0.4 時 ， 分成一類： x1, x2, x3, x4, x5 95 其動態(tài)分類如圖 3.47 所示： =1 x1 x3 x4 x5 x2 0.8 0.6 0.5 0.4 圖 3.47 動態(tài)聚類圖 96 2） 直接聚類法 根據(jù)模糊相似矩陣 (3.6.49) 來直接由相似類求等價類。 當(dāng) =1 時，該矩陣只有對角線上的元素為 1，所以不許歸并相似類，所得到的 e(R)1 的等價類為 x1， x2， x3， x4， x5。 當(dāng) = 0.8 時，先求經(jīng)典矩陣 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，也無法再進(jìn)一步歸并，于是 e(R)0.6 的等價類為： x1, x3, x2 , x4, x5。 98 當(dāng) =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。 當(dāng) = 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 之值（連通強度）。 注意不要做回路。 從原則上來說，可以選擇任一元素（ 頂點 ） 作為起始點，但一般總是選有相似類的元素開始。例如在本例中當(dāng) = 0.8 時，就有相似類 x1, x3， 于是就把 x1 選為起始頂點，先作出強度為