第七章模糊聚類分析課件

一、模糊聚類分析聚類分析：按照一定要求和原則對事物進行分類。聚類：普通分類——清晰事物模糊分類——帶有模糊性的事物三種模糊聚類方法：傳遞閉包法——基于模糊等價關系；直接聚類法——基于模糊相似關系；模糊聚類法——基于模糊劃分.一、模糊聚類分析聚類分析：按照一定要求和原則對事物進行分類。1二、模糊聚類分析的步驟1.選取特征指標

特征要有明確的意義，要有較強的分辨力，有代表性，并確定描述特征的變量。分類事物的特征指標選擇的如何，對分類結果有直接的影響。

二、模糊聚類分析的步驟1.選取特征指標22.數(shù)據(jù)標準化（正規(guī)化）令其中，xi為原始數(shù)據(jù)；是原始數(shù)據(jù)的均值；是原始數(shù)據(jù)的標準差；是數(shù)據(jù)處理后的數(shù)據(jù)。2.數(shù)據(jù)標準化（正規(guī)化）令其中，xi為原始數(shù)據(jù)；是原始數(shù)據(jù)33.標定

設為待分類的對象，uj有m個刻劃其特征的數(shù)據(jù)，就是根據(jù)實際情況，按一個準則或某一種方法，給論域U中的元素兩兩之間都賦以區(qū)間[0,1]內的一個數(shù)，叫做相似系數(shù)。它的大小表征兩個元素彼此接近或相似的程度。，然后對于ui與uj，用rij表示ui與uj的當rij＝0時，表示ui與uj截然不同；當rij＝1時，表示ui與uj可以等同(不能說是完全相同);rij可根據(jù)具體問題來選取。方法有：的相似程度，要求3.標定設為待分類的對象，uj有m個刻劃其特征4（1）數(shù)量積法，其中顯然．如果rij中出現(xiàn)負值，可采用下面方法將全體rij進行重新調整．方法1令，則方法2令其中于是（1）數(shù)量積法，其中顯然．如果rij中出現(xiàn)負值，可采用下5（2）夾角余弦法如果rij中出現(xiàn)負值，也可采用上面方法調整．（3）相關系數(shù)法其中（2）夾角余弦法如果rij中出現(xiàn)負值，也可采用上面方法調整．6（4）最大最小法（5）算術平均最小法（6）幾何平均最小法（4）最大最小法（5）算術平均最小法（6）幾何平均最小法7（8）指數(shù)相似系數(shù)法其中sk適當選擇.（9）絕對值倒數(shù)法M適當選取使rij在[0,1]中且分散開（7）絕對值指數(shù)法（8）指數(shù)相似系數(shù)法其中sk適當選擇.（9）絕對值倒數(shù)法8（11）非參數(shù)法中正數(shù)個數(shù)，中負數(shù)個數(shù)，令則（10）絕對值減數(shù)法（11）非參數(shù)法中正數(shù)個數(shù)，中負數(shù)個數(shù)，令則（10）絕對值減9（12）貼近度法如果特征則ui,uj

可看作模糊向量,以它們的貼近度D(ui,uj)為其相似程度.i)格貼近度,其中ii)距離貼近度其中c,a為適當選擇參數(shù)值，d(ui,uj)為模糊集各種距離.iii)算術平均最小貼近度（12）貼近度法如果特征則ui,uj可看作模糊向量,10（13）主觀評定法請有實際經(jīng)驗者直接對ui，uj的相似程度評分，作為rij的值.通過標定求出相似系數(shù)后，便可得到以rij為元素的模糊相似矩陣R(rij).4.聚類選擇一種合適的聚類方法，便可得到分類結果.（13）主觀評定法請有實際經(jīng)驗者直接對ui，uj11三、傳遞閉包法1.傳遞閉包法根據(jù)標定所得模糊矩陣R，求出其傳遞閉包為模糊等價矩陣，對，令λ從1降到0得到，根據(jù)進行分類：歸為一類.2.最佳閾值λ的選取聚類圖給出各λ值對應的分類，形成一種動態(tài)聚類，便于全面了解元素聚類，然后根據(jù)實際需要選擇其閾值λ，便可確定元素的一種分類，至于如何選擇閾值λ，使分類更加合理，除了憑經(jīng)驗外，還可用F-統(tǒng)計量來選取.三、傳遞閉包法1.傳遞閉包法根據(jù)標定所得模糊矩陣R，求出其12F-統(tǒng)計量：為待分類事物的全體，設xjk為描述元素uj

第k

個特征的數(shù)據(jù).設c

為對應于λ

值的類數(shù)，ni為第

i

類元素的個數(shù)，第

i

類元素記為記為第i

類元素的第k

個特征的平均值,而稱為第i類的聚類中心向量；為全體元素的中心向量，而F-統(tǒng)計量：為待分類事物的全體，設xjk為描述元素uj13于是，稱為F-統(tǒng)計量，其中為第i類中元素與中心的距離.

可見，F(xiàn)-統(tǒng)計量的分子表征類與類間的距離，分母表征類內元素間的距離.因此，F(xiàn)值越大，說明分類越合理，與此分類相對應的F-統(tǒng)計量最大的閾值λ為最佳值.于是，稱為F-統(tǒng)計量，其中為第i類中元素與中心的距離.14求傳遞閉包的簡便方法設為模糊相似矩陣，求t(A).(1)求,假定,把A中的a1m,am1,a11,amm用圓圈圈起來，并記(2)在A中第一行、第m行中剩下的元素中找最大元素,即.且設在第p列.用即分別代替a1p與amp以及它們的對稱元素，最后用圓圈將它們及圈起來.求傳遞閉包的簡便方法設為模糊相似矩陣，求t(A).(1)15(3)假定A中有圈的k行是行.而所在的列是ij列，在這些行中剩下的元素中找最大元并設在第l行，用分別代替繼續(xù)此過程，到k=n-1,得到t(A).還有逐步平方法：及其對稱矩陣，并把all圈起來(3)假定A中有圈的k行是行.而所在的列是i16四、基于模糊相似關系的直接聚類法1.最大樹法

聚類原則是：ui與uj在λ水平同類當且僅當在相似矩陣R的圖中，存在一條權重不低于λ的路聯(lián)結ui與uj.畫出以被分類元素為結點，以相似矩陣R的元素rij為權重的一顆最大樹；(2)取定，砍斷權重低于λ的枝，得到一個不連通圖，各連通分支變構成了在λ水平上的分類.四、基于模糊相似關系的直接聚類法1.最大樹法聚類原則172.編網(wǎng)法對給定的模糊相似矩陣R，取定水平,作截矩陣Rλ

，在Rλ

的主對角線上填入元素的符號，在對角線下方以結點號“*”代替1，而“0”則略去不寫，由結點向主對角線上引經(jīng)線和緯線，稱之為編網(wǎng)，通過經(jīng)線和緯線能互相連接起來的元素，屬于同類，從而實現(xiàn)了分類.2.編網(wǎng)法對給定的模糊相似矩陣R，取定水平,作截矩陣Rλ18五、基于模糊劃分的模糊聚類法1.c-劃分(1)普通c-劃分如果劃分把普通集合分成c類，則此劃分就叫普通c-劃分，即：若設的特征可表為，那么U的普通c-劃分是指U的c個子集滿足:(1)(2)五、基于模糊劃分的模糊聚類法1.c-劃分(1)普通19其中且滿足(1)(2)(表示每個uj必屬于且僅屬于一類)；(表示每類Ai至少有一個元素)；反過來，任一滿足條件(1)、(2)、(3)的矩陣對應著U的一個分類.(1)(2)(3)這樣的分類結果可以用一個c×n矩陣(稱為c-劃分)來表示.其中且滿足(1)(2)(表示每個uj必屬于且僅屬于一類)20例如，設U={u1,u2,u3,u4},若分類結果為{u1},{u2,u3},{u4},則對應的分類矩陣為如果分類矩陣為則對應著U的分類為{u1},{u2,u3},{u4}.例如，設U={u1,u2,u3,u4},若分類結21記V為c×n實矩陣的集合，且顯然，對于給定的U及分類數(shù)c，類的分法不是唯一的.Mc包含了U的所有可能c類劃分的結果，Mc稱為將U分成c類的分類空間.這樣的分類是通常的分類，稱為硬分類.記V為c×n實矩陣的集合，且顯然，22(2)模糊c-劃分設,一個c×n模糊矩陣若滿足(1)(2)(表示每個uj屬于c個模糊子集Ai的程度總和為1)；(表示每類Ai不等于空集或U)；則稱A稱為U的模糊c-劃分矩陣.(2)模糊c-劃分設,一個c×n模糊矩陣若滿足23記Mfc稱為U的c類軟分類空間.顯然若將Mc和Mfc定義中的條件：放寬為則這樣的分類空間分別稱為退化的硬分類空間和退化的軟分類空間.分別記為Mco和Mfco,顯然記Mfc稱為U的c類軟分類空間.顯然若將Mc242.目標函數(shù)聚類法和硬c-均值算法劃分(1)目標函數(shù)法目標函數(shù)是對給定的c的所有候選類進行度量，最優(yōu)的類就是使目標函數(shù)達到局部最小值的類.對于硬分類情形，通常所選取的目標函數(shù)是總體組內誤差平方和，其定義為這里將每類Ai中元素各特征分別取平均值，所得的聚類中心向量記為vi，也稱為Ai的聚類中心.由于Ai類中元素個數(shù),Ai類中元素向量和為,因此聚類中心向量2.目標函數(shù)聚類法和硬c-均值算法劃分(1)目標函數(shù)25記V稱為聚類中心矩陣.若,則uj到聚類中心vi的距離為Ai

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

，更新為模糊c-均值算法(ISODATA方法)步驟：步驟131步驟4：若,則停止算法；否則令l=l+1，返回步驟2.注意：本方法要求,因此取初