1、第七章模糊聚類分析,一、模糊聚類分析,聚類分析：按照一定要求和原則對事物進行分類。 聚類：普通分類清晰事物 模糊分類帶有模糊性的事物 三種模糊聚類方法： 傳遞閉包法基于模糊等價關(guān)系； 直接聚類法基于模糊相似關(guān)系； 模糊聚類法基于模糊劃分.,二、模糊聚類分析的步驟,1.選取特征指標(biāo) 特征要有明確的意義，要有較強的分辨力，有代表性，并確定描述特征的變量。 分類事物的特征指標(biāo)選擇的如何，對分類結(jié)果有直接的影響。,2.數(shù)據(jù)標(biāo)準(zhǔn)化（正規(guī)化）,令,其中，xi 為原始數(shù)據(jù)；,是原始數(shù)據(jù)的均值；,是原始數(shù)據(jù)的標(biāo)準(zhǔn)差；,是數(shù)據(jù)處理后的數(shù)據(jù)。,3.標(biāo)定,設(shè),為待分類的對象，uj有m個刻劃其特征的,數(shù)據(jù)，,就是根據(jù)

2、實際情況，按一個準(zhǔn)則或某一種方法，給論域U中的元素兩兩之間都賦以區(qū)間0,1內(nèi)的一個數(shù)，叫做相似系數(shù)。它的大小表征兩個元素彼此接近或相似的程度。,，然后對于 ui與 uj ，用,rij 表示 ui 與 uj 的,當(dāng)rij0時，表示ui與uj截然不同；,當(dāng)rij1時，表示ui與uj可以等同(不能說是完全相同);,rij可根據(jù)具體問題來選取。方法有：,的相似程度，要求,（1）數(shù)量積法,，其中,顯然,如果 rij 中出現(xiàn)負值，可采用下面方法,將全體 rij 進行重新調(diào)整,方法1 令,，則,方法2 令,其中,于是,（2）夾角余弦法,如果rij中出現(xiàn)負值，也可采用上面方法調(diào)整,（3）相關(guān)系數(shù)法,其中,（4

3、）最大最小法,（5）算術(shù)平均最小法,（8）指數(shù)相似系數(shù)法,其中 sk 適當(dāng)選擇.,（9）絕對值倒數(shù)法,M 適當(dāng)選取使 rij 在 0,1 中且分散開,（7）絕對值指數(shù)法,（11）非參數(shù)法,中正數(shù)個數(shù)，,中負數(shù)個數(shù)，,令,則,（10）絕對值減數(shù)法,（12）貼近度法,如果特征,則 ui, uj 可看作模糊向量, 以它們的貼近度 D(ui,uj),為其相似程度.,i) 格貼近度, 其中,ii) 距離貼近度,其中 c,a 為適當(dāng)選擇參數(shù)值，d(ui,uj) 為模糊集各種距離.,iii) 算術(shù)平均最小貼近度,（13）主觀評定法,請有實際經(jīng)驗者直接對 ui，uj 的相似程度評分，作為 rij 的值.,通過

4、標(biāo)定求出相似系數(shù)后，便可得到以 rij 為元素的模糊相似矩陣 R(rij) .,4.聚類,選擇一種合適的聚類方法，便可得到分類結(jié)果.,三、傳遞閉包法,1. 傳遞閉包法,根據(jù)標(biāo)定所得模糊矩陣R，求出其傳遞閉包,為模糊等價矩陣，對,，令從1降到0得到,，根據(jù),進行分類：,歸為一類.,2. 最佳閾值的選取,聚類圖給出各值對應(yīng)的分類，形成一種動態(tài)聚類，便于全面了解元素聚類，然后根據(jù)實際需要選擇其閾值，便可確定元素的一種分類，至于如何選擇閾值，使分類更加合理，除了憑經(jīng)驗外，還可用 F-統(tǒng)計量來選取.,F-統(tǒng)計量：,為待分類事物的全體，,設(shè),xjk 為描述元素 uj 第 k 個特征的數(shù)據(jù),.設(shè) c 為,對

5、應(yīng)于 值的類數(shù)，ni 為第 i 類元素的個數(shù)，第 i 類元素記為,記,為第 i 類元素的第 k 個特征的平均值, 而稱,為第 i 類的聚類中心向量；,為全體元素的中,心向量，而,于是，稱,為F-統(tǒng)計量，其中,為第i類中元素,與中心,的距離.,可見，F(xiàn)-統(tǒng)計量的分子表征類與類間的距離，分母表征類內(nèi)元素間的距離. 因此，F(xiàn) 值越大，說明分類越合理，與此分類相對應(yīng)的 F-統(tǒng)計量最大的閾值為最佳值.,求傳遞閉包的簡便方法,設(shè),為模糊相似矩陣，求 t(A).,(1) 求,假定, 把 A 中的 a1m,am1,a11,amm 用圓圈,圈起來，并記,(2) 在 A 中第一行、第 m行中剩下的元素中,找最大元

6、素, 即,. 且設(shè),在第 p 列. 用,即分別代替 a1p 與 amp 以及它們的對稱元素，,最后用圓圈將它們及 圈起來.,(3) 假定 A 中有圈的 k 行,是,行. 而,所在的列是 ij 列，在這些行中剩下的元素中,找最大元,并設(shè) 在第 l 行，用,分別代替,繼續(xù)此過程，到 k = n-1,得到 t(A) . 還有逐步平方法：,及其對稱矩陣，并把 all 圈起來,四、基于模糊相似關(guān)系的直接聚類法,1.最大樹法,聚類原則是：ui與uj在水平同類當(dāng)且僅當(dāng)在相似矩陣R的圖中，存在一條權(quán)重不低于的路聯(lián)結(jié)ui與uj.,畫出以被分類元素為結(jié)點，以相似矩陣R的元素 rij 為權(quán)重的一顆最大樹； (2)取

7、定 ，砍斷權(quán)重低于的枝，得到一個不連通圖，各連通分支變構(gòu)成了在水平上的分類.,2.編網(wǎng)法,對給定的模糊相似矩陣R，取定水平, 作截矩陣,R ，在 R 的主對角線上填入元素的符號，在對角線下方以結(jié)點號 “*” 代替 1，而 “0” 則略去不寫，由結(jié)點向主對角線上引經(jīng)線和緯線，稱之為編網(wǎng)，通過經(jīng)線和緯線能互相連接起來的元素，屬于同類，從而實現(xiàn)了分類.,五、基于模糊劃分的模糊聚類法,1. c-劃分,(1) 普通 c-劃分,如果劃分把普通集合分成 c 類，則此劃分就叫普通 c-劃分，,即：若設(shè),的特征可表為,，,那么U的普通c-劃分是指U的c個子集,滿足: (1),(2),其中,且滿足 (1),(2)

8、,(表示每個uj必屬于且僅屬于一類)；,(表示每類Ai至少有一個元素)；,反過來，任一滿足條件(1)、(2)、(3)的矩陣對應(yīng)著U的一個分類.,(1),(2),(3),這樣的分類結(jié)果可以用一個 cn 矩陣(稱為 c-劃分)來表示.,例如，設(shè) U=u1,u2,u3,u4, 若分類結(jié)果為 u1, u2,u3, u4, 則對應(yīng)的分類矩陣為,如果分類矩陣為,則對應(yīng)著 U 的分類為 u1, u2,u3, u4.,記 V 為 cn 實矩陣的集合，且,顯然，對于給定的 U 及分類數(shù) c ，類的分法不是唯一的. Mc 包含了 U 的所有可能 c 類劃分的結(jié)果，Mc 稱為將 U 分成 c 類的分類空間. 這樣的

9、分類是通常的分類，稱為硬分類.,(2) 模糊 c-劃分,設(shè),一個 cn 模糊矩陣,若滿足 (1),(2),( 表示每個 uj 屬于 c 個模糊子集 Ai 的程度總和為 1 ) ；,(表示每類 Ai 不等于空集或 U ) ；,則稱 A 稱為 U 的模糊 c-劃分矩陣.,記,Mfc 稱為 U 的 c 類軟分類空間. 顯然,若將 Mc 和,Mfc 定義中的條件：,放寬為,則這樣的分類空間分別稱為退化的硬分類空間和退化的軟分類空間. 分別記為 Mco 和 Mfco , 顯然,2. 目標(biāo)函數(shù)聚類法和硬 c-均值算法劃分,(1) 目標(biāo)函數(shù)法,目標(biāo)函數(shù)是對給定的 c 的所有候選類進行度量，最優(yōu)的類就是使目標(biāo)

10、函數(shù)達到局部最小值的類. 對于硬分類情形，通常所選取的目標(biāo)函數(shù)是總體組內(nèi)誤差平方和，其定義為,這里將每類 Ai 中元素各特征分別取平均值，所得的聚類中心向量記為 vi，也稱為 Ai 的聚類中心. 由于 Ai 類中元素個數(shù), Ai類中元素向量和為, 因此聚類中心向量,記,V 稱為聚類中心矩陣. 若, 則uj到聚類中心vi的距離為,Ai 中全體元素到中心距離平方和為,而 V 中所有元素到其所在類中心距離平方和為,最理想的 c-劃分顯然是使 J(A,V) 取極小的 A .,(2) 硬 c-均值算法,步驟1：假設(shè)給出 n 個數(shù)據(jù)點, 其中,. 取定,并初始化,步驟2：當(dāng)?shù)螖?shù)為,時, 計算聚類中心向

11、量,其中,步驟3：用下式將 A(l) 更新為,步驟4：比較 A(l) 和 A(l+1) , 若, 則停止算,法；否則，令 l=l+1，返回步驟2.,直觀上看，硬 c-均值算法：猜想 c的硬分類（步驟1），尋找各分類的中心（步驟2），重新分配類的隸屬度以減少數(shù)據(jù)和當(dāng)前中心的誤差平方（步驟3），當(dāng)循環(huán)不再能顯著的降低 J(A,V) 時，停止算法（步驟4）.,3. 模糊 c-均值算法,定義目標(biāo)函數(shù),其中 是一個加權(quán)指數(shù).,模糊 c-均值算法的目標(biāo)在于找到,和, 使得 Jm(A,V)最小,下面，首先建立這個最小化問題的必要條件，然后根據(jù)此條件提出模糊 c-均值算法.,定理 令,為一給,定數(shù)據(jù)集. 設(shè)定,，假設(shè)對所有,，則僅當(dāng),和,時，,才是 Jm(A,V) 的局部最小值.,模糊 c-均值算法 ( ISODATA方法 ) 步驟：,步驟1：給定數(shù)據(jù)集,設(shè)定, 并初始化,步驟2：當(dāng)?shù)螖?shù)為,時, 計算聚類中心向量,步驟3：用下式將 ， 更新為,步驟4：若, 則停止算法；否則令 l=l+1，,返回步驟2.,注意：本方法要求,