模式識(shí)別-聚類的算法課件

12·4聚類的算法2.4.1聚類的技術(shù)方案聚類分析有很多具體的算法,有的比較簡(jiǎn)單,有的相對(duì)復(fù)雜和完善,但歸納起來(lái)就是三大類:1、按最小距離原則簡(jiǎn)單聚類方法2、按最小距離原則進(jìn)行兩類合并的方法3、依據(jù)準(zhǔn)則函數(shù)動(dòng)態(tài)聚類方法12·4聚類的算法2.4.1聚類的技術(shù)方案聚類分析22·4聚類的算法(1)簡(jiǎn)單聚類方法

針對(duì)具體問(wèn)題確定相似性閾值，將模式到各聚類中心間的距離與閾值比較，當(dāng)大于閾值時(shí)該模式就作為另一類的類心，小于閾值時(shí)按最小距離原則將其分劃到某一類中。這類算法運(yùn)行中模式的類別及類的中心一旦確定將不會(huì)改變。22·4聚類的算法(1)簡(jiǎn)單聚類方法32·4聚類的算法首先視各模式自成一類,然后將距離最小的兩類合并成一類,不斷地重復(fù)這個(gè)過(guò)程，直到成為兩類為止。(2)按最小距離原則進(jìn)行兩類合并的方法這類算法運(yùn)行中，類心不斷地修正，但模式類別一旦指定后就不再改變，就是模式一旦劃為一類后就不再被分劃開(kāi)，這類算法也稱為譜系聚類法。32·4聚類的算法首先視各模式自成一類,然后將距離最小42·4聚類的算法(3)依據(jù)準(zhǔn)則函數(shù)動(dòng)態(tài)聚類法設(shè)定一些分類的控制參數(shù)，定義一個(gè)能表征聚類結(jié)果優(yōu)劣的準(zhǔn)則函數(shù)，聚類過(guò)程就是使準(zhǔn)則函數(shù)取極值的優(yōu)化過(guò)程。算法運(yùn)行中，類心不斷地修正，各模式的類別的指定也不斷地更改。這類方法有—C均值法、ISODATA法等。42·4聚類的算法(3)依據(jù)準(zhǔn)則函數(shù)動(dòng)態(tài)聚類法設(shè)定一52·4聚類的算法--簡(jiǎn)單聚類方法

52·4聚類的算法--簡(jiǎn)單聚類方法62·4聚類的算法--簡(jiǎn)單聚類方法

62·4聚類的算法--簡(jiǎn)單聚類方法72·4聚類的算法--簡(jiǎn)單聚類方法

72·4聚類的算法--簡(jiǎn)單聚類方法82·4聚類的算法--簡(jiǎn)單聚類方法

這類算法的突出優(yōu)點(diǎn)是算法簡(jiǎn)單。但聚類過(guò)程中，類的中心一旦確定將不會(huì)改變，模式一旦指定類后也不再改變。算法特點(diǎn):從算法的過(guò)程可以看出，該算法結(jié)果很大程度上依賴于距離門限T的選取及模式參與分類的次序。如果能有先驗(yàn)知識(shí)指導(dǎo)門限T的選取，通常可獲得較合理的效果。也可考慮設(shè)置不同的T和選擇不同的次序，最后選擇較好的結(jié)果進(jìn)行比較。82·4聚類的算法--簡(jiǎn)單聚類方法這類算法的突出優(yōu)點(diǎn)是92·4聚類的算法--簡(jiǎn)單聚類方法

簡(jiǎn)單聚類圖例92·4聚類的算法--簡(jiǎn)單聚類方法簡(jiǎn)單聚類圖例10例2.4.1：初始條件不同的簡(jiǎn)單聚類結(jié)果初始中心不同門限不同樣本順序不同

12345

12345

12345

12345

1098

1098

876

876

1167

1167

91011

9101110例2.4.1：初始條件不同的簡(jiǎn)單聚類結(jié)果初始中心不同門限112·4聚類的算法—最大最小距離法

112·4聚類的算法—最大最小距離法122·4聚類的算法--最大最小距離法

⒊算法原理步驟⑴選任一模式特征矢量作為第一個(gè)聚類中心例如，。作為第二個(gè)聚類中心。⑵從待分類矢量集中選距離最遠(yuǎn)的特征矢量122·4聚類的算法--最大最小距離法⒊算法原理步驟13⑶計(jì)算未被作為聚類中心的各模式特征矢量與、之間的距離，并求出它們之中的最小值，

為表述簡(jiǎn)潔，雖然某些模式已選做聚類中心，但上面仍將所有模式下角標(biāo)全部列寫出來(lái)，因這并不影響算法的正確性。即13⑶計(jì)算未被作為聚類中心的各模式特征矢量與、之間的距離14則相應(yīng)的特征矢量作為第三個(gè)聚類中心，然后轉(zhuǎn)至⑸；否則，轉(zhuǎn)至最后一步⑹。⑷若⑸設(shè)存在個(gè)聚類中心，計(jì)算未被作為聚類中心,并算出如果，則否則，轉(zhuǎn)至最后一步⑹。的各特征矢量到各聚類中心的距離并轉(zhuǎn)至⑸；14則相應(yīng)的特征矢量作為第三個(gè)聚類中心，然后轉(zhuǎn)至⑸；否則，轉(zhuǎn)15⑹當(dāng)判斷出不再有新的聚類中心之后，將模式特中去，即計(jì)算當(dāng)，則判。征矢量按最小距離原則分到各類這種算法的聚類結(jié)果與參數(shù)心的選取有關(guān)。如果沒(méi)有先驗(yàn)知識(shí)指導(dǎo)和取，可適當(dāng)調(diào)整和選取最合理的一種聚類。以及第一個(gè)聚類中的選，比較多次試探分類結(jié)果，15⑹當(dāng)判斷出不再有新的聚類中心之后，將模式特中去，即計(jì)161617Z1X1Z2X6Z3X7Z4X1(0,0)08045X2(1,2)15829X3(2,2)84017X4(3,8)73134X5(5,3)34261X6(4,8)80029X7(6,3)45290X8(5,4)41262X9(6,4)52201X10(7,5)74185Theta=0.217Z1X1Z2X6Z3X7Z4X1(0,0)01818192·4聚類的算法層次聚類法(HierarchicalClusteringMethod)(系統(tǒng)聚類法、譜系聚類法）按最小距離原則不斷進(jìn)行兩類合并

2.4.3譜系聚類法192·4聚類的算法層次聚類法(Hierarchica202·4聚類的算法層次聚類法(HierarchicalClusteringMethod)(系統(tǒng)聚類法、譜系聚類法）按最小距離原則不斷進(jìn)行兩類合并⒉算法思想

首先將N個(gè)模式視作各自成為一類，然后計(jì)算類與類之間的距離，選擇距離最小的一對(duì)合并成一個(gè)新類，計(jì)算在新的類別分劃下各類之間的距離，再將距離最近的兩類合并，直至所有模式聚成兩類為止。

2.4.3譜系聚類法202·4聚類的算法層次聚類法(Hierarchica212·4聚類的算法

2.4.3譜系聚類法212·4聚類的算法2.4.3譜系聚類法222·4聚類的算法

2.4.3譜系聚類法222·4聚類的算法2.4.3譜系聚類法23例2.4.3：如下圖所示1、設(shè)全部樣本分為6類，2、作距離矩陣D(0)3、求最小元素：4、把ω1,ω3合并ω7=(1,3)ω4,ω6合并ω8=(4,6)5、作距離矩陣D(1)ω1ω2ω3ω4ω5ω23ω314ω4748ω55262ω685913D(0)23例2.4.3：如下圖所示ω1ω2ω3ω4ω5ω23ω324例2.4.3：如下圖所示1、設(shè)全部樣本分為6類，2、作距離矩陣D(0)3、求最小元素：4、把ω1,ω3合并ω7=(1,3)ω4,ω6合并ω8=(4,6)5、作距離矩陣D(1)D(1)ω7ω2ω8ω23ω874ω552224例2.4.3：如下圖所示D(1)ω7ω2ω8ω23ω8256、若合并的類數(shù)沒(méi)有達(dá)到要求，轉(zhuǎn)3。否則停止。3、求最小元素：4、ω8,ω5,ω2合并,ω9=（2,5,4,6）256、若合并的類數(shù)沒(méi)有達(dá)到要求，轉(zhuǎn)3。否則停止。2626272·4聚類的算法最大距離和層次聚類算法的一個(gè)共同特點(diǎn)是某個(gè)模式一旦劃分到某一類之后，在后繼的算法過(guò)程中就不改變了，而簡(jiǎn)單聚類算法中類心一旦選定后在后繼算法過(guò)程中也不再改變了。因此，這些方法效果一般不會(huì)太理想。272·4聚類的算法最大距離和層次聚類算法的一個(gè)共同特點(diǎn)是282.確定評(píng)估聚類質(zhì)量的準(zhǔn)則函數(shù)。確定模式和聚類的距離測(cè)度。當(dāng)采用歐氏距離時(shí)，是計(jì)算此模式和該類中心的歐氏距離；為能反映出類的模式分布結(jié)構(gòu)，應(yīng)采用馬氏距離，設(shè)該類的均矢為，協(xié)方差陣為，則模式和該類的與該類均矢的馬氏距離：距離平方為3.確定模式分劃及聚類合并或分裂的規(guī)則。2·4聚類的算法——?jiǎng)討B(tài)聚類算法要點(diǎn)282.確定評(píng)估聚類質(zhì)量的準(zhǔn)則函數(shù)。確定模式和聚類的距292·4聚類的算法——?jiǎng)討B(tài)聚類的基本步驟建立初始聚類中心，進(jìn)行初始聚類；計(jì)算模式和類的距離，調(diào)整模式的類別；計(jì)算各聚類的參數(shù)，刪除、合并或分裂一些聚類；從初始聚類開(kāi)始，運(yùn)用迭代算法動(dòng)態(tài)地改變模式的類別和聚類的中心使準(zhǔn)則函數(shù)取得極值或設(shè)定的參數(shù)達(dá)到設(shè)計(jì)要求時(shí)停止。292·4聚類的算法——?jiǎng)討B(tài)聚類的基本步驟建立初始聚類中心302·4聚類的算法——?jiǎng)討B(tài)聚類的框圖產(chǎn)生初始聚類中心聚類檢驗(yàn)聚類合理性待分類模式分類結(jié)果合理再迭代/修改參數(shù)不合理302·4聚類的算法——?jiǎng)討B(tài)聚類的框圖產(chǎn)生初始聚類中心聚類31⒈條件及約定

設(shè)待分類的模式特征矢量集為：類的數(shù)目C是事先取定的。2·4聚類的算法

2.4.3動(dòng)態(tài)聚類法——C-均值法⒉算法思想

該方法取定C個(gè)類別和選取

C個(gè)初始聚類中心，按最小距離原則將各模式分配到C類中的某一類，之后不斷地計(jì)算類心和調(diào)整各模式的類別，最終使各模式到其判屬類別中心的距離平方之和最小。31⒈條件及約定2·4聚類的算法2.4.3動(dòng)態(tài)聚類322·4聚類的算法

2.4.3動(dòng)態(tài)聚類法——C-均值法322·4聚類的算法2.4.3動(dòng)態(tài)聚類法——C-均值33例2.4.2使用聚類算法實(shí)現(xiàn)圖像分割在散射圖上形成了兩個(gè)聚類，利用模式識(shí)別的方法將其分開(kāi)，就實(shí)現(xiàn)了圖象的分割。33例2.4.2使用聚類算法實(shí)現(xiàn)圖像分割在散射圖上形成了兩34

例2.4.3：已知有20個(gè)樣本，每個(gè)樣本有2個(gè)特征，數(shù)據(jù)分布如下圖,使用C－均值法實(shí)現(xiàn)樣本分類（C=2）。第一步：令C=2，選初始聚類中心為樣本序號(hào)x1x2x3x4x5x6x7x8x9x10特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x208678978989677778889934例2.4.3：已知有20個(gè)樣本，每個(gè)樣本有2個(gè)特征，數(shù)35353600第二步：000＝））－（（＝-10100＝））－（（＝-10001＝））－（（＝-所以因?yàn)?-<-3600第二步：000＝））－（（＝-10100＝））－（（370)01()01(=-=-,?->-所以因?yàn)橥?12,21?\=->-?\=-<-＝＝......20652065都屬于、、離計(jì)算出來(lái)，判斷與第二個(gè)聚類中心的距、、同樣把所有因此分為兩類：),...,,()1(),,()1(205422311==18,221==NNGG二、一、370)01()01(=-=-,?->-所以因?yàn)橥?12,3838393940第三步：更新聚類中心40第三步：更新聚類中心414142第四步：第二步：第三步：更新聚類中心42第四步：4343應(yīng)用圖像分割44應(yīng)用圖像分割4445clustering2·4聚類的算法

2.4.3動(dòng)態(tài)聚類法——C-均值法程序45clustering2·4聚類的算法2.4.3動(dòng)46作業(yè)P45:2.7,2.846作業(yè)P45:2.7,2.8472·4聚類的算法

2.4.3動(dòng)態(tài)聚類法——C-均值法關(guān)于C-均值法收斂性的分析472·4聚類的算法2.4.3動(dòng)態(tài)聚類法——C-均值482·4聚類的算法

2.4.3動(dòng)態(tài)聚類法——C-均值法當(dāng)模式分布呈現(xiàn)類內(nèi)團(tuán)聚狀，C-均值算法是能達(dá)到很好的聚類結(jié)果，故應(yīng)用較多。從算法的迭代過(guò)程看，C-均值算法是能使各模式到其所判屬的類別中心距離(平方)之和為最小的最佳聚類。482·4聚類的算法2.4.3動(dòng)態(tài)聚類法——C-均值492·4聚類的算法

2.4.3動(dòng)態(tài)聚類法——C-均值法的改進(jìn)在類別數(shù)未知的情況下，可使類數(shù)C由較小值逐步增加，對(duì)于每個(gè)選定的C分別使用該算法。顯然準(zhǔn)則函數(shù)J是隨C的增加而單調(diào)減少。⑴C的調(diào)整作一條C一J曲線，其曲率變化的最大點(diǎn)對(duì)應(yīng)的類數(shù)是比較接近最優(yōu)的類數(shù)。在增加過(guò)程中，總會(huì)出現(xiàn)使本來(lái)較密集的類再拆開(kāi)的情況，此時(shí)J雖減小，但減小速度將變緩。如果作一條C一J曲線，其曲率變化的最大點(diǎn)對(duì)應(yīng)的類數(shù)是比較接近最優(yōu)的類數(shù)。然而在許多情況下，曲線并無(wú)明顯的這樣的點(diǎn)。492·4聚類的算法2.4.3動(dòng)態(tài)聚類法——C-均值502·4聚類的算法

2.4.3動(dòng)態(tài)聚類法——C-均值法的改進(jìn)⑵初始聚類中心的選?、賾{經(jīng)驗(yàn)選擇初始類心。②將模式隨機(jī)地分成C類，計(jì)算每類中心，以其作為初始類心。③（最大密度），求以每個(gè)特征點(diǎn)為球心、某一正數(shù)d0為半徑的球形域中特征點(diǎn)個(gè)數(shù)，這個(gè)數(shù)稱為該點(diǎn)的密度。選取密度最大的特征點(diǎn)作為第一個(gè)初始類心Z1，然后在與Z1大于某個(gè)距離d的那些特征點(diǎn)中選取具有“最大”密度的特征點(diǎn)作為第二個(gè)初始類心Z2

，如此進(jìn)行，選取C個(gè)初始聚類中心。502·4聚類的算法2.4.3動(dòng)態(tài)聚類法——C-均值512·4聚類的算法

2.4.3動(dòng)態(tài)聚類法——C-均值法的改進(jìn)⑵初始聚類中心的選?、苡孟嗑嘧钸h(yuǎn)的C個(gè)特征點(diǎn)作為初始類心。具體地講，是按前述的最大最小距離算法求取C個(gè)初始聚類中心。⑤當(dāng)N較大時(shí)，先隨機(jī)地從N個(gè)模式中取出一部分模式用譜系聚類法聚成C類，以每類的重心作為初始類心。⑥設(shè)已標(biāo)準(zhǔn)化的待分類模式集為希望將它們分為C類。512·4聚類的算法2.4.3動(dòng)態(tài)聚類法——C-均值52⑥設(shè)已標(biāo)準(zhǔn)化的待分類模式集為希望將它們分為C類。設(shè):計(jì)算:顯然0≤ai≤C，若ai最接近整數(shù)j，則把xi分劃至中wj。對(duì)所有樣本都實(shí)行上述處理，就可實(shí)現(xiàn)初始分類，從而產(chǎn)生初始聚類中心。52⑥設(shè)已標(biāo)準(zhǔn)化的待分類模式集為設(shè):計(jì)算:532·4聚類的算法

2.4.3動(dòng)態(tài)聚類法——C-均值法的改進(jìn)⑶用類核代替類心前面的算法存在一個(gè)不足，即只用一個(gè)聚類中心點(diǎn)作為一類的代表，但一個(gè)點(diǎn)往往不能充分地反映該類的模式分布結(jié)構(gòu)，從而損失了很多有用的信息。當(dāng)類的分布不是球狀或近似球狀時(shí)，這種算法很難有較好的效果。此時(shí)，可用類核代替類心，類核可以是一個(gè)函數(shù)、一個(gè)點(diǎn)集或其他適當(dāng)?shù)哪Ｐ汀１热缜懊嫖覀冎v過(guò)的馬式距離。532·4聚類的算法2.4.3動(dòng)態(tài)聚類法——C-均值545455(3)動(dòng)態(tài)聚類法——ISODATA算法(IterativeSelf-OrganizingDataAnalysisTechniquesAlgorithm迭代自組織數(shù)據(jù)分析)特點(diǎn)：?jiǎn)l(fā)性推理、分析監(jiān)督、控制聚類結(jié)構(gòu)及人機(jī)交互。算法思想： 在每輪迭代過(guò)程中，樣本重新調(diào)整類別之后計(jì)算類內(nèi)及類間有關(guān)參數(shù)，并和設(shè)定的門限比較，確定是兩類合并為一類還是一類分裂為兩類，不斷地“自組織”，以達(dá)到在各參數(shù)滿足設(shè)計(jì)要求條件下，使各模式到其類心的距離平方和最小。55(3)動(dòng)態(tài)聚類法——ISODATA算法(Iterati56ISODATA算法原理步驟⑴預(yù)置①設(shè)定聚類分析控制參數(shù)：=預(yù)期的類數(shù)，=每一類中允許的最少模式數(shù)目，=初始聚類中心個(gè)數(shù)(可以不等于c)，=類內(nèi)各分量分布的距離標(biāo)準(zhǔn)差上界，(分裂用)=兩類中心間的最小距離下界，(合并用)=在每次迭代中可以合并的類的最多對(duì)數(shù)，=允許的最多迭代次數(shù)。56ISODATA算法原理步驟⑴預(yù)置=預(yù)期的類數(shù)，=每57ISODATA算法原理步驟57ISODATA算法原理步驟58ISODATA算法原理步驟58ISODATA算法原理步驟59ISODATA算法原理步驟 ①計(jì)算各類的中心⑷計(jì)算分類后的參數(shù):各類中心、類內(nèi)平均距離及總體平均距離。②計(jì)算各類中模式到類心的平均距離 ③計(jì)算各個(gè)模式到其類內(nèi)中心的總體平均距離59ISODATA算法原理步驟 ①計(jì)算各類的中心⑷60ISODATA算法原理步驟60ISODATA算法原理步驟61ISODATA算法原理步驟⑹計(jì)算各類類內(nèi)距離的標(biāo)準(zhǔn)差矢量式中，為分量編號(hào)，為類的編號(hào)，為矢量維數(shù)，是的第個(gè)分量，是的第個(gè)分量。61ISODATA算法原理步驟⑹計(jì)算各類類內(nèi)距離的標(biāo)準(zhǔn)62ISODATA算法原理步驟62ISODATA算法原理步驟63ISODATA算法原理步驟63ISODATA算法原理步驟64ISODATA算法原理步驟64ISODATA算法原理步驟65ISODATA算法原理步驟65ISODATA算法原理步驟666667ISODATA算法舉例(二維)(1)初始值設(shè)定:類間距離上限距離標(biāo)準(zhǔn)差上界最少模式數(shù)目合并的類的最多對(duì)數(shù)67ISODATA算法舉例(二維)(1)初始值設(shè)定:類間距離68ISODATA算法舉例(2)聚類(只有一個(gè)中心):68ISODATA算法舉例(2)聚類(只有一個(gè)中心):69ISODATA算法舉例(3)

因,無(wú)合并:(4)計(jì)算聚類中心、類內(nèi)平均距離和總的平均距離。69ISODATA算法舉例(3)因,70ISODATA算法舉例(5)因不是最后一步迭代，且，轉(zhuǎn)至⑹(6)求的標(biāo)準(zhǔn)差矢量70ISODATA算法舉例(5)因不是最后一步迭代，且71ISODATA算法舉例(7)

算得(6)因且將分裂成兩類，取，則且轉(zhuǎn)(2)71ISODATA算法舉例(7)算得(6)因72ISODATA算法舉例(2)聚類(兩個(gè)中心):(3)

因,無(wú)合并:72ISODATA算法舉例(2)聚類(兩個(gè)中心):(3)因73ISODATA算法舉例(4)計(jì)算聚類中心、類內(nèi)平均距離和總的平均距離。(5)因這是偶次迭代，滿足算法原理步驟⑸中④的條件，故轉(zhuǎn)⑼73ISODATA算法舉例(4)計(jì)算聚類中心、類內(nèi)平均距74ISODATA算法舉例(9)計(jì)算類間距離由，類不能合并。(11)因不是最后一次迭代(，題設(shè))，，判斷是否修改參數(shù)。由上面結(jié)果可知，已獲得所要求類別數(shù)目，類間距離大于類內(nèi)距離，每類樣本數(shù)都有樣本總數(shù)的足夠大的百分比，因此不改變參數(shù)。74ISODATA算法舉例(9)計(jì)算類間距離由75(2)～(4)計(jì)算結(jié)果與前一次迭代結(jié)果相同。(7)

,分裂條件不滿足，轉(zhuǎn)至⑼。，無(wú)新的變化，，轉(zhuǎn)至⑵。(6)計(jì)算和的標(biāo)準(zhǔn)差矢量(5)沒(méi)有任一種情況被滿足，到⑹。與前一次迭代結(jié)果相同，無(wú)合并發(fā)生。75(2)～(4)計(jì)算結(jié)果與前一次迭代結(jié)果相同。(7)(676⑵～⑷與前一次迭代結(jié)果相同。⑸因是最后一次迭代，令，轉(zhuǎn)至⑼。⑼，同前。⑽因，無(wú)合并發(fā)生。⑾因是最后一次迭代,

結(jié)束。76⑵～⑷與前一次迭代結(jié)果相同。77Start輸入樣本數(shù)據(jù)，置c;Nc;選初始類心zj

，j=1,2,..Nc(1)置控制參數(shù)：

n,

s,

D,

,L,I(3)合并判決：

nj<

n