第七章模糊聚類分析

第七章模糊聚類分析第1頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月一、模糊聚類分析聚類分析：按照一定要求和原則對(duì)事物進(jìn)行分類。聚類：普通分類——清晰事物模糊分類——帶有模糊性的事物三種模糊聚類方法：傳遞閉包法——基于模糊等價(jià)關(guān)系；直接聚類法——基于模糊相似關(guān)系；模糊聚類法——基于模糊劃分.第2頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月二、模糊聚類分析的步驟1.選取特征指標(biāo)特征要有明確的意義，要有較強(qiáng)的分辨力，有代表性，并確定描述特征的變量。分類事物的特征指標(biāo)選擇的如何，對(duì)分類結(jié)果有直接的影響。

第3頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月2.數(shù)據(jù)標(biāo)準(zhǔn)化（正規(guī)化）令其中，xi為原始數(shù)據(jù)；是原始數(shù)據(jù)的均值；是原始數(shù)據(jù)的標(biāo)準(zhǔn)差；是數(shù)據(jù)處理后的數(shù)據(jù)。第4頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月3.標(biāo)定

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

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

第k

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

為對(duì)應(yīng)于λ

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

i

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

i

類元素記為記為第i

類元素的第k

個(gè)特征的平均值,而稱為第i類的聚類中心向量；為全體元素的中心向量，而第14頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月于是，稱為F-統(tǒng)計(jì)量，其中為第i類中元素與中心的距離.

可見(jiàn)，F(xiàn)-統(tǒng)計(jì)量的分子表征類與類間的距離，分母表征類內(nèi)元素間的距離.因此，F(xiàn)值越大，說(shuō)明分類越合理，與此分類相對(duì)應(yīng)的F-統(tǒng)計(jì)量最大的閾值λ為最佳值.第15頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月求傳遞閉包的簡(jiǎn)便方法設(shè)為模糊相似矩陣，求t(A).(1)求,假定,把A中的a1m,am1,a11,amm用圓圈圈起來(lái)，并記(2)在A中第一行、第m行中剩下的元素中找最大元素,即.且設(shè)在第p列.用即分別代替a1p與amp以及它們的對(duì)稱元素，最后用圓圈將它們及圈起來(lái).第16頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月(3)假定A中有圈的k行是行.而所在的列是ij列，在這些行中剩下的元素中找最大元并設(shè)在第l行，用分別代替繼續(xù)此過(guò)程，到k=n-1,得到t(A).還有逐步平方法：及其對(duì)稱矩陣，并把a(bǔ)ll圈起來(lái)第17頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月四、基于模糊相似關(guān)系的直接聚類法1.最大樹(shù)法

聚類原則是：ui與uj在λ水平同類當(dāng)且僅當(dāng)在相似矩陣R的圖中，存在一條權(quán)重不低于λ的路聯(lián)結(jié)ui與uj.畫出以被分類元素為結(jié)點(diǎn)，以相似矩陣R的元素rij為權(quán)重的一顆最大樹(shù)；(2)取定，砍斷權(quán)重低于λ的枝，得到一個(gè)不連通圖，各連通分支變構(gòu)成了在λ水平上的分類.第18頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月2.編網(wǎng)法對(duì)給定的模糊相似矩陣R，取定水平,作截矩陣Rλ

，在Rλ

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

中全體元素到中心距離平方和為而V中所有元素到其所在類中心距離平方和為最理想的c-劃分顯然是使J(A,V)取極小的A.第27頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月(2)硬c-均值算法步驟1：假設(shè)給出n個(gè)數(shù)據(jù)點(diǎn),其中.取定并初始化步驟2：當(dāng)?shù)螖?shù)為時(shí),計(jì)算聚類中心向量其中,步驟3：用下式將A(l)更新為第28頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月步驟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)時(shí)，停止算法（步驟4）.第29頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月3.模糊c-均值算法定義目標(biāo)函數(shù)其中是一個(gè)加權(quán)指數(shù).模糊c-均值算法的目標(biāo)在于找到和,使得Jm(A,V)最小下面，首先建立這個(gè)最小化問(wèn)題的必要條件，然后根據(jù)此條件提出模糊c-均值算法.第30頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月定理令為一給定數(shù)據(jù)集.設(shè)定，假設(shè)對(duì)所有，則僅當(dāng)和時(shí)，才是Jm(A,V)的局部最小值.第31頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月模糊c-均值算法(ISODATA方法)步驟：步驟1：給定數(shù)據(jù)集設(shè)定,并初始化步驟2：當(dāng)?shù)螖?shù)為時(shí),計(jì)算聚類中心向量步驟3：用下式將

，更新為第32頁(yè)，課件共34頁(yè)，創(chuàng)作于2023年2月步驟4：若,則停止算法；否則令l=l+1，返回步驟2.注意：本方法要求