第二章聚類分析學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1第二章聚類分析第二章聚類分析第一頁(yè)，共163頁(yè)。2第二章 聚類分析 (Clustering Analysis) 2.1 聚類分析的概念(ginin)2.2 模式相似性測(cè)度2.3 類的定義與類間距離2.4 聚類的算法第1頁(yè)/共163頁(yè)第二頁(yè)，共163頁(yè)。32.1 聚類分析的概念(ginin)一、聚類分析的基本思想(sxing) 相似的歸為一類。 模式相似性的度量和聚類算法。 無監(jiān)督分類（Unsupervised） 。二、特征量的類型 物理量-(重量、長(zhǎng)度、速度) 次序量-(等級(jí)、技能、學(xué)識(shí)) 名義量-(性別、狀態(tài)(zhungti)、種類)第二章 聚類分析第2頁(yè)/共163頁(yè)第三頁(yè)，共163

2、頁(yè)。4三、方法(fngf)的有效性 取決于分類算法和特征點(diǎn)分布情況的匹配。2.1 聚類分析的概念(ginin)2w2W1w1W2x1xb分類無效(wxio)時(shí)的情況1.特征選取不當(dāng)使分類無效(wxio)。第二章 聚類分析第3頁(yè)/共163頁(yè)第四頁(yè)，共163頁(yè)。5三、方法的有效性 取決于分類算法和特征點(diǎn)分布(fnb)情況的匹配。2.1 聚類分析的概念(ginin)分類無效時(shí)的情況(qngkung)2.特征選取不足可能使不同類別的模式判為一類。2w2W1w1W2x1x3w3W第二章 聚類分析第4頁(yè)/共163頁(yè)第五頁(yè)，共163頁(yè)。6三、方法(fngf)的有效性 取決于分類算法和特征點(diǎn)分布情況的匹配。2

3、.1 聚類分析的概念(ginin)分類無效時(shí)的情況3.特征選取過多可能無益反而(fn r)有害,增加分析負(fù)擔(dān)并使分析效果變差。2w2W1w1W2x1xb第二章 聚類分析第5頁(yè)/共163頁(yè)第六頁(yè)，共163頁(yè)。7三、方法(fngf)的有效性 取決于分類算法和特征點(diǎn)分布情況的匹配。2.1 聚類分析的概念(ginin)分類無效時(shí)的情況4.量綱(lin n)選取不當(dāng)。第二章 聚類分析第6頁(yè)/共163頁(yè)第七頁(yè)，共163頁(yè)。8三、方法的有效性 取決于分類算法和特征(tzhng)點(diǎn)分布情況的匹配。2.1 聚類分析的概念(ginin)分類無效時(shí)的情況4.量綱(lin n)選取不當(dāng)。第二章 聚類分析第7頁(yè)/共16

4、3頁(yè)第八頁(yè)，共163頁(yè)。9三、方法的有效性 取決于分類算法和特征點(diǎn)分布情況(qngkung)的匹配。2.1 聚類分析的概念(ginin)分類(fn li)無效時(shí)的情況4.量綱選取不當(dāng)。第二章 聚類分析第8頁(yè)/共163頁(yè)第九頁(yè)，共163頁(yè)。10下列是一些動(dòng)物的名稱：羊 （sheep）狗 （dog）藍(lán)鯊（blue shark）蜥蜴 （lizard）毒蛇（viper）貓 （cat）麻雀(mqu)（sparrow）海鷗 （seagull）金魚（gold fish）緋鯢鰹（red-mullet）蛙 （frog）要對(duì)這些動(dòng)物進(jìn)行分類，則不同的特征有不同的分法：第二章 聚類分析第9頁(yè)/共163頁(yè)第十頁(yè)，共1

5、63頁(yè)。11羊, 狗, 貓藍(lán)鯊蜥蜴(xy),毒蛇,麻雀,海鷗,金魚,緋鯢鰹, 青蛙(a) 按繁衍后代(hudi)的方式分哺乳動(dòng)物非哺乳動(dòng)物第二章 聚類分析第10頁(yè)/共163頁(yè)第十一頁(yè)，共163頁(yè)。12金魚(jny)緋鯢鰹藍(lán)鯊羊,狗,貓蜥蜴(xy),毒蛇麻雀,海鷗 青蛙(b) 按肺是否(sh fu)存在分無肺有肺特征選取不同對(duì)聚類結(jié)果的影響第二章 聚類分析第11頁(yè)/共163頁(yè)第十二頁(yè)，共163頁(yè)。13青蛙(qngw)羊,狗,貓 蜥蜴(xy),毒蛇麻雀,海鷗 金魚(jny)緋鯢鰹 藍(lán)鯊(c) 按生活環(huán)境分陸地水里兩棲特征選取不同對(duì)聚類結(jié)果的影響第二章 聚類分析第12頁(yè)/共163頁(yè)第十三頁(yè)，共163

6、頁(yè)。14藍(lán)鯊金魚(jny)緋鯢鰹蜥蜴,毒蛇(dsh)麻雀,海鷗 青蛙羊,狗,貓(d) 按繁衍后代(hudi)方式和肺是否存在分非哺乳且有肺哺乳且無肺哺乳且有肺非哺乳且無肺特征選取不同對(duì)聚類結(jié)果的影響第二章 聚類分析第13頁(yè)/共163頁(yè)第十四頁(yè)，共163頁(yè)。15數(shù)據(jù)(shj)的粗聚類是兩類,細(xì)聚類為4類第二章 聚類分析第14頁(yè)/共163頁(yè)第十五頁(yè)，共163頁(yè)。16選擇什么特征？選擇多少個(gè)特征？選擇什么樣的量綱(lin n)？選擇什么樣的距離測(cè)度？ 這些對(duì)分類結(jié)果都會(huì)產(chǎn)生極大影響。第二章 聚類分析第15頁(yè)/共163頁(yè)第十六頁(yè)，共163頁(yè)。聚類過程遵循(zn xn)的基本步驟 一、特征選擇(feat

7、ure selection) 盡可能多地包含任務(wù)(rn wu)關(guān)心的信息二、近鄰(jn ln)測(cè)度(proximity measure) 定量測(cè)定兩特征如何“相似”或“不相似”三、聚類準(zhǔn)則（clustering criterion） 以蘊(yùn)涵在數(shù)據(jù)集中類的類型為基礎(chǔ)四、聚類算法（clustering algorithm） 按近鄰測(cè)度和聚類準(zhǔn)則揭示數(shù)據(jù)集的聚類結(jié)構(gòu)五、結(jié)果驗(yàn)證（validation of the results） 常用逼近檢驗(yàn)驗(yàn)證聚類結(jié)果的正確性六、結(jié)果判定（interpretation of the results） 由專家用其他方法判定結(jié)果的正確性第16頁(yè)/共163頁(yè)第十七頁(yè)，

8、共163頁(yè)。18聚類應(yīng)用(yngyng)的四個(gè)基本方向一、減少數(shù)據(jù) 許多時(shí)候，當(dāng)數(shù)據(jù)量N很大時(shí)，會(huì)使數(shù)據(jù)處理變得很費(fèi)力。因此可使用聚類分析的方法將數(shù)據(jù)分成幾組可判斷的聚類m（mN）來處理，每一個(gè)類可當(dāng)作獨(dú)立(dl)實(shí)體來對(duì)待。從這個(gè)角度看，數(shù)據(jù)被壓縮了。第二章 聚類分析第17頁(yè)/共163頁(yè)第十八頁(yè)，共163頁(yè)。19二、假說生成 在這種情況下，為了推導(dǎo)出數(shù)據(jù)性質(zhì)的一些假說，對(duì)數(shù)據(jù)集進(jìn)行聚類分析。因此，這里使用聚類作為建立假說的方法，然后用其他(qt)數(shù)據(jù)集驗(yàn)證這些假說。聚類應(yīng)用的四個(gè)基本(jbn)方向第二章 聚類分析第18頁(yè)/共163頁(yè)第十九頁(yè)，共163頁(yè)。20聚類應(yīng)用(yngyng)的四個(gè)基本

9、方向三、假說檢驗(yàn)(jinyn) 用聚類分析來驗(yàn)證指定假說的有效性。例如：考慮這樣的假說“大公司在海外投資”。要驗(yàn)證這個(gè)假說是否正確，就要對(duì)大公司和有代表性的公司按規(guī)模(gum)、海外活躍度、成功完成項(xiàng)目的能力等進(jìn)行聚類分析。從而來支持這個(gè)假說。第二章 聚類分析第19頁(yè)/共163頁(yè)第二十頁(yè)，共163頁(yè)。21四、基于分組的預(yù)測(cè) 對(duì)現(xiàn)有數(shù)據(jù)進(jìn)行聚類分析，形成模式的特征，并用特征表示聚類，接下來，對(duì)于一個(gè)未知模式，就可以用前面(qin mian)的聚類來確定是哪一類？聚類應(yīng)用(yngyng)的四個(gè)基本方向例如：考慮被同種(tn zhn)疾病感染的病人數(shù)據(jù)集。先按聚類分析進(jìn)行分類，然后對(duì)新的病人確定他適

10、合的聚類，從而判斷他病情。第二章 聚類分析第20頁(yè)/共163頁(yè)第二十一頁(yè)，共163頁(yè)。222.2 模式(msh)相似性測(cè)度 用于描述(mio sh)各模式之間特征的相似程度 距 離 測(cè) 度 相 似 測(cè) 度 匹 配 測(cè) 度第二章 聚類分析第21頁(yè)/共163頁(yè)第二十二頁(yè)，共163頁(yè)。232.2 模式(msh)相似性測(cè)度一、距離測(cè)度(差值測(cè)度)測(cè)度基礎(chǔ)(jch)：兩個(gè)矢量矢端的距離測(cè)度數(shù)值：兩矢量各相應(yīng)分量之差的函數(shù)。時(shí)，等號(hào)成立；0),(yxd，當(dāng)且僅當(dāng)xy),(),(xydyxd),(),(),(yzdzxdyxd第二章 聚類分析第22頁(yè)/共163頁(yè)第二十三頁(yè)，共163頁(yè)。242.2 模式(ms

11、h)相似性測(cè)度常用(chn yn)的距離測(cè)度有：1.歐氏(Euclidean)距離 第二章 聚類分析第23頁(yè)/共163頁(yè)第二十四頁(yè)，共163頁(yè)。252.2 模式(msh)相似性測(cè)度4.明氏(Minkowski)距離(jl) (2-2-4)2.絕對(duì)值距離(jl)(街坊距離(jl)或Manhattan距離(jl) (2-2-2) 3.切氏(Chebyshev)距離(jl) (2-2-3) 第二章 聚類分析第24頁(yè)/共163頁(yè)第二十五頁(yè)，共163頁(yè)。262.2 模式(msh)相似性測(cè)度第二章 聚類分析第25頁(yè)/共163頁(yè)第二十六頁(yè)，共163頁(yè)。272.2 模式(msh)相似性測(cè)度5.馬氏(Mahal

12、anobis)距離(jl)注意！馬氏距離對(duì)一切非奇異線性變換都是不變的，這說明它不受特征量綱選擇的影響，并且是平移不變的。 上面的V的含義是這個(gè)矢量(shling)集的協(xié)方差陣的統(tǒng)計(jì)量，故馬氏距離加入了對(duì)特征的相關(guān)性的考慮。第二章 聚類分析第26頁(yè)/共163頁(yè)第二十七頁(yè)，共163頁(yè)。282.2 模式(msh)相似性測(cè)度第二章 聚類分析第27頁(yè)/共163頁(yè)第二十八頁(yè)，共163頁(yè)。第28頁(yè)/共163頁(yè)第二十九頁(yè)，共163頁(yè)?，F(xiàn)金識(shí)別例子(l zi)(歐氏平均距離)數(shù)據(jù)樣本介紹：10個(gè)文本文件文件名：rmb00.txt rmb09.txt每個(gè)文件有4個(gè)幣種的數(shù)據(jù)，分別是： 100圓、50圓、20圓、

13、10圓每個(gè)幣種有新舊兩種版本，4個(gè)方向(fngxing)，故有8個(gè)數(shù)據(jù)塊：如100圓的8個(gè)數(shù)據(jù)塊： data100a,data100b,data100c,data100d老版 data100e,data100f,data100g,data100h新版每個(gè)數(shù)據(jù)塊有8個(gè)傳感器數(shù)據(jù)： 傳感器1，傳感器2，傳感器8每個(gè)傳感器有60個(gè)采樣數(shù)據(jù)： 數(shù)據(jù)1，數(shù)據(jù)2，數(shù)據(jù)60第29頁(yè)/共163頁(yè)第三十頁(yè)，共163頁(yè)?，F(xiàn)金識(shí)別(shbi)例子Eucliden=15.000000Manhattan=33.000000Chebyshev=11.000000Minkowski=11.039449m=8100元A面第1

14、個(gè)樣本(yngbn)第10點(diǎn)和20點(diǎn)的距離X: (75, 76,101, 83,102, 96, 91, 82)Y: (70, 74, 90, 76, 99, 96, 90, 86)X-Y: 5, 2, 11, 7, 3, 0, 1, -4距離(jl)測(cè)度rmbdis第30頁(yè)/共163頁(yè)第三十一頁(yè)，共163頁(yè)。現(xiàn)金識(shí)別(shbi)例子歐式平均距離100a-100a:( 2.65,49.66) 24.41100a-100b:(16.37,55.87) 33.97100a-100c:( 3.87,58.34) 29.41100a-100d:( 6.86,53.74) 33.04100a-100e:

15、( 3.87,62.12) 27.51100a-100f:(13.60,67.61) 34.67100a-100g:(11.40,68.56) 32.27100a-100h:(11.27,68.61) 34.43100a- 50a:(18.76,76.20) 40.72100a- 20a:(13.23,81.28) 42.87100a- 10a:(12.45,90.91) 54.99第31頁(yè)/共163頁(yè)第三十二頁(yè)，共163頁(yè)?，F(xiàn)金(xinjn)識(shí)別例子100圓A面的馬式矩陣(j zhn)SW為: 43.5 53.9 64.8 52.7 52.7 52.3 46.8 37.9 53.9 132.

16、0 137.5 107.8 59.6 74.0 52.1 31.5 64.8 137.5 165.9 124.1 74.6 84.1 67.6 37.1 52.7 107.8 124.1 105.5 57.5 67.2 54.5 35.2 52.7 59.6 74.6 57.5 76.2 71.7 65.8 57.9 52.3 74.0 84.1 67.2 71.7 73.1 62.8 55.0 46.8 52.1 67.6 54.5 65.8 62.8 59.6 51.9 37.9 31.5 37.1 35.2 57.9 55.0 51.9 54.7第32頁(yè)/共163頁(yè)第三十三頁(yè)，共163頁(yè)

17、。現(xiàn)金(xinjn)識(shí)別例子SW的逆矩陣(j zhn)為: 0.3 -0.0 0.1 -0.1 -0.1 -0.1 -0.2 0.2 -0.0 0.3 -0.1 -0.1 0.1 -0.6 0.3 0.2 0.1 -0.1 0.3 -0.1 -0.0 -0.2 -0.3 0.4 -0.1 -0.1 -0.1 0.2 0.1 0.3 -0.1 -0.2 -0.1 0.1 -0.0 0.1 0.7 -0.7 -0.4 0.2 -0.1 -0.6 -0.2 0.3 -0.7 2.2 -0.0 -1.0 -0.2 0.3 -0.3 -0.1 -0.4 -0.0 1.2 -0.5 0.2 0.2 0.4

18、 -0.2 0.2 -1.0 -0.5 1.0第33頁(yè)/共163頁(yè)第三十四頁(yè)，共163頁(yè)?，F(xiàn)金(xinjn)識(shí)別例子馬式平均距離100a: ( 7.46, 80.05) 39.73100b: (26.75, 179.86) 91.89100c: (14.50, 231.44) 103.76100d: (11.69, 155.28) 78.58100e: ( 5.65,2968.84) 247.42100f: (39.19,2191.91) 108.10100g: (10.68,2875.99) 265.16100h: ( 9.41,2673.54) 107.56 50a: (22.78, 22

19、1.07) 101.41 20a: (22.51, 343.26) 162.90 10a: (20.93, 975.67) 256.38第34頁(yè)/共163頁(yè)第三十五頁(yè)，共163頁(yè)?，F(xiàn)金識(shí)別(shbi)例子馬式平均距離a: 39.73 101.41 162.90 256.38b: 91.89 230.25 288.69 659.47c: 103.76 135.94 257.57 724.96d: 78.58 171.10 330.97 675.90e: 247.42 443.46 333.93 218.71f: 108.10 328.11 305.19 607.51g: 265.16 956.5

20、8 818.83 348.42h: 107.56 339.64 387.10 628.88100圓 50圓 20圓 10圓其中馬式矩陣為100圓A面的，上面是各面到100圓A面的均值點(diǎn)的平均(pngjn)馬式距離。第35頁(yè)/共163頁(yè)第三十六頁(yè)，共163頁(yè)?，F(xiàn)金識(shí)別例子(l zi)100圓A面的傳感器1到其它各面?zhèn)鞲衅?的街坊距離第36頁(yè)/共163頁(yè)第三十七頁(yè)，共163頁(yè)。382.2 模式(msh)相似性測(cè)度二、相似測(cè)度測(cè)度基礎(chǔ)：以兩矢量的方向是否相近作為考慮的基礎(chǔ),矢量長(zhǎng)度并不不重要。設(shè)1.角度相似系數(shù)(夾角余弦) (2-2-11)注意：坐標(biāo)系的旋轉(zhuǎn)和尺度的縮放是不變的,但對(duì)一般的線形變換和

21、坐標(biāo)系的平移(pn y)不具有不變性。 第37頁(yè)/共163頁(yè)第三十八頁(yè)，共163頁(yè)。39現(xiàn)金識(shí)別例子(l zi)100圓A面?zhèn)鞲衅?與其它各面的相似系數(shù)第38頁(yè)/共163頁(yè)第三十九頁(yè)，共163頁(yè)。402.2 模式(msh)相似性測(cè)度二、相似測(cè)度(c du)2.相關(guān)系數(shù)它實(shí)際上是數(shù)據(jù)中心化后的矢量夾角余弦。 (2-2-12)21)( )( )()( )(),(yyyyxxxxyyxxyxr第39頁(yè)/共163頁(yè)第四十頁(yè)，共163頁(yè)。41現(xiàn)金(xinjn)識(shí)別例子100圓A面?zhèn)鞲衅?與其它各面的相關(guān)系數(shù)第40頁(yè)/共163頁(yè)第四十一頁(yè)，共163頁(yè)。422.2 模式(msh)相似性測(cè)度二、相似測(cè)度3.指

22、數(shù)(zhsh)相似系數(shù) (2-2-13)niiiiyxnyxe122)(43exp1),(式中 為相應(yīng)分量(fn ling)的協(xié)方差， 為矢量維數(shù)。它不受量綱變化的影響。 2in第41頁(yè)/共163頁(yè)第四十二頁(yè)，共163頁(yè)。43現(xiàn)金識(shí)別例子(l zi)100圓A面?zhèn)鞲衅?與其它各面的相關(guān)系數(shù)第42頁(yè)/共163頁(yè)第四十三頁(yè)，共163頁(yè)。442.2 模式(msh)相似性測(cè)度當(dāng)特征只有兩個(gè)狀態(tài)（0，1）時(shí)，常用匹配測(cè)度。0表示(biosh)無此特征 1表示(biosh)有此特征。故稱之為二值特征。 對(duì)于給定的x和y中的某兩個(gè)相應(yīng)分量xi與yj若xi=1,yj=1 ，則稱 xi與yj是 (1-1)匹配；

23、若xi=1,yj=0 ，則稱 xi與yj是 (1-0)匹配；若xi=0,yj=1 ，則稱 xi與yj是 (0-1)匹配；若xi=0,yj=0 ，則稱 xi與yj是 (0-0)匹配。二、匹配(ppi)測(cè)度第43頁(yè)/共163頁(yè)第四十四頁(yè)，共163頁(yè)。452.2 模式(msh)相似性測(cè)度第44頁(yè)/共163頁(yè)第四十五頁(yè)，共163頁(yè)。462.2 模式(msh)相似性測(cè)度 三、匹配(ppi)測(cè)度(1)Tanimoto測(cè)度(c du)yxyyxxyxcbaayxs),(第45頁(yè)/共163頁(yè)第四十六頁(yè)，共163頁(yè)。47)0, 1, 1, 0, 1, 0(x) 1, 0, 1, 1, 0, 0(y 1 , 3

24、, 3yxyyxx511331),(yxs設(shè)則2.2 模式(msh)相似性測(cè)度第46頁(yè)/共163頁(yè)第四十七頁(yè)，共163頁(yè)。48現(xiàn)金識(shí)別例子100圓A面與其它(qt)各面的匹配系數(shù)Tanimoto第47頁(yè)/共163頁(yè)第四十八頁(yè)，共163頁(yè)。492.2 模式(msh)相似性測(cè)度 三、匹配(ppi)測(cè)度(2) Rao測(cè)度(c du)注：(1-1)匹配特征數(shù)目和所選用的特征數(shù)目之比。nyxecbaayxs),(第48頁(yè)/共163頁(yè)第四十九頁(yè)，共163頁(yè)。50現(xiàn)金(xinjn)識(shí)別例子100圓A面與其它各面的匹配系數(shù)Rao第49頁(yè)/共163頁(yè)第五十頁(yè)，共163頁(yè)。512.2 模式(msh)相似性測(cè)度 三

25、、匹配(ppi)測(cè)度(3) 簡(jiǎn)單匹配(ppi)系數(shù)注：上式分子為(1-1)匹配特征數(shù)目與(0-0)匹配特征數(shù)目之和，分母為所考慮的特征數(shù)目。neayxm),(第50頁(yè)/共163頁(yè)第五十一頁(yè)，共163頁(yè)。52現(xiàn)金識(shí)別例子100圓A面與其它(qt)各面的匹配系數(shù)Simple第51頁(yè)/共163頁(yè)第五十二頁(yè)，共163頁(yè)。532.2 模式(msh)相似性測(cè)度 三、匹配(ppi)測(cè)度(4) Dice系數(shù)(xsh)(5) Kulzinsky系數(shù)的總數(shù)倆矢量中匹配個(gè)數(shù)11)-(12),(yyxxyxcbaayxm匹配個(gè)數(shù)匹配個(gè)數(shù)0)-(11)-(01)-(12),(yxyyxxyxcbayxm第52頁(yè)/共16

26、3頁(yè)第五十三頁(yè)，共163頁(yè)。54現(xiàn)金識(shí)別例子100圓A面與其它(qt)各面的匹配系數(shù)dice第53頁(yè)/共163頁(yè)第五十四頁(yè)，共163頁(yè)。55現(xiàn)金識(shí)別(shbi)例子100圓A面與其它各面的匹配系數(shù)Kulzinsky第54頁(yè)/共163頁(yè)第五十五頁(yè)，共163頁(yè)。56作業(yè)(zuy)P44: 2.1, 2.3第55頁(yè)/共163頁(yè)第五十六頁(yè)，共163頁(yè)。5723 類的定義(dngy)與類間距離類的定義(dngy)定義之1 設(shè)集合(jh)S中任意元素xi與yj間的距離dij有 dij h其中h為給定的閥值，稱S對(duì)于閥值h組成一類。 類的定義有很多種，類的劃分具有人為規(guī)定性，這反映在定義的選取及參數(shù)的選擇上

27、。一個(gè)分類結(jié)果的優(yōu)劣最后只能根據(jù)實(shí)際來評(píng)價(jià)。書中的其它定義方法請(qǐng)大家自行參考學(xué)習(xí)第56頁(yè)/共163頁(yè)第五十七頁(yè)，共163頁(yè)。5823 類的定義(dngy)與類間距離類間距離(jl)測(cè)度方法 最近距離法 最遠(yuǎn)距離法 中間距離法 重心(zhngxn)距離法 平均距離法 離差平方和法第57頁(yè)/共163頁(yè)第五十八頁(yè)，共163頁(yè)。5923 類的定義(dngy)與類間距離類間距離測(cè)度(c du)方法 最近距離法 最遠(yuǎn)距離法 中間(zhngjin)距離法 重心距離法 平均距離法 離差平方和法式中 表示 和 之間的距離。 ijjikldD,minijdkixwljxw第58頁(yè)/共163頁(yè)第五十九頁(yè)，共163頁(yè)

28、。60現(xiàn)金識(shí)別例子100圓A面與其它(qt)各面的最小距離第59頁(yè)/共163頁(yè)第六十頁(yè)，共163頁(yè)。6123 類的定義(dngy)與類間距離類間距離(jl)測(cè)度方法 最近距離法 最遠(yuǎn)距離法 中間距離法 重心(zhngxn)距離法 平均距離法 離差平方和法式中 表示 和 之間的距離。ijdkixwljxw ijjikldD,max第60頁(yè)/共163頁(yè)第六十一頁(yè)，共163頁(yè)。62現(xiàn)金(xinjn)識(shí)別例子100圓A面與其它各面的最大距離第61頁(yè)/共163頁(yè)第六十二頁(yè)，共163頁(yè)。6323 類的定義(dngy)與類間距離類間距離(jl)測(cè)度方法 最近距離法 最遠(yuǎn)距離法 中間(zhngjin)距離法

29、重心距離法 平均距離法 離差平方和法pwqwkwpqkpqDkqDklDkpDlwpqkqkpklDDDD2222412121qplwww第62頁(yè)/共163頁(yè)第六十三頁(yè)，共163頁(yè)。6423 類的定義(dngy)與類間距離類間距離(jl)測(cè)度方法 最近(zujn)距離法 最遠(yuǎn)距離法 中間距離法 重心距離法 平均距離法 離差平方和法22222)(pqqpqpkqqpqkpqppklDnnnnDnnnDnnnDnp,nq分別為類wp和wq的樣本個(gè)數(shù)第63頁(yè)/共163頁(yè)第六十四頁(yè)，共163頁(yè)。6523 類的定義(dngy)與類間距離類間距離測(cè)度(c du)方法 最近(zujn)距離法 最遠(yuǎn)距離法 中

30、間距離法 重心距離法 平均距離法 離差平方和法wwqjpixxijqppqdnnD221第64頁(yè)/共163頁(yè)第六十五頁(yè)，共163頁(yè)。66現(xiàn)金識(shí)別例子(l zi)100圓A面與其它各面的平均距離第65頁(yè)/共163頁(yè)第六十六頁(yè)，共163頁(yè)。6723 類的定義(dngy)與類間距離類間距離測(cè)度(c du)方法 最近(zujn)距離法 最遠(yuǎn)距離法 中間距離法 重心距離法 平均距離法 離差平方和法wtixtititxxxxs)()(qplwwwqplpqsssD2)()(2qpqpqpqppqxxxxnnnnDtxpxqx分別為對(duì)應(yīng)類的重心類內(nèi)離差平方和 2222pqlkkkqlkqkkplkpkklD

31、nnnDnnnnDnnnnD遞推公式為:第66頁(yè)/共163頁(yè)第六十七頁(yè)，共163頁(yè)。68222222kqkppqkqqkppklDDDDDD 最近距離法最近距離法 1/2 1/2 0 -1/2 最遠(yuǎn)距離法最遠(yuǎn)距離法 1/2 1/2 0 1/2 中間距離法中間距離法 1/2 1/2 -1/4 0 重心距離法重心距離法 0 平均距離法平均距離法 0 0 可變平均法可變平均法 0 可變法可變法 0 離差平方和法離差平方和法 0pqqppnnnqpqnnnqpqppnnnqpqnnnqppnnn )1 (qpqnnn )1 (112121lkpknnnnlkqknnnnlkknnn第67頁(yè)/共163頁(yè)

32、第六十八頁(yè)，共163頁(yè)。6923 類的定義(dngy)與類間距離聚類的準(zhǔn)則(zhnz)函數(shù)判別分類(fn li)結(jié)果好壞的一般標(biāo)準(zhǔn)：類內(nèi)距離小，類間距離大。 某些算法需要一個(gè)能對(duì)分類過程或分類結(jié)果的優(yōu)劣進(jìn)行評(píng)估的準(zhǔn)則函數(shù)。如果聚類準(zhǔn)則函數(shù)選擇得好，聚類質(zhì)量就會(huì)高。聚類準(zhǔn)則往往是和類的定義有關(guān)的，是類的定義的某種體現(xiàn)。第68頁(yè)/共163頁(yè)第六十九頁(yè)，共163頁(yè)。70聚類的準(zhǔn)則(zhnz)函數(shù)一、類內(nèi)距離準(zhǔn)則 設(shè)有待分類的模式(msh)集 在某種相似性測(cè)度基礎(chǔ)上被劃分為 類，類內(nèi)距離準(zhǔn)則函數(shù) 定義為:( 表示 類的模式(msh)均值矢量。)Nxxx,21cjjinicjx, 2 , 1;, 2 ,

33、 1)(；WJcjnijjiWjmxJ112)(2-3-20)23 類的定義(dngy)與類間距離jmjw第69頁(yè)/共163頁(yè)第七十頁(yè)，共163頁(yè)。7123 類的定義(dngy)與類間距離第70頁(yè)/共163頁(yè)第七十一頁(yè)，共163頁(yè)。72加權(quán)類內(nèi)距離(jl)準(zhǔn)則 :WWJ21jcjjWWdNnJ(2-3-22)2)()(2)()() 1(2jjijjkxxjkjijjjxxnndww(2-3-23)式中，2)()(jkjixx表示jw類內(nèi)任兩個(gè)模式距離2) 1(jjnn 個(gè)組合數(shù)，所以2jd表示類內(nèi)Nnj表示jw類先驗(yàn)概率的估計(jì)頻率。平方和，共有兩模式間的均方距離。N為待分類模式總數(shù)，第71頁(yè)/

34、共163頁(yè)第七十二頁(yè)，共163頁(yè)。7323 類的定義(dngy)與類間距離第72頁(yè)/共163頁(yè)第七十三頁(yè)，共163頁(yè)。74加權(quán)類間距離(jl)準(zhǔn)則:對(duì)于兩類問題，類間距離有時(shí)取)()(21212mmmmJB(2-3-26)2BJ和WBJ的關(guān)系是221BWBJNnNnJ(2-3-27)max)()(1cjjjjWBmmmmNnJ(2-3-25)第73頁(yè)/共163頁(yè)第七十四頁(yè)，共163頁(yè)。7523 類的定義(dngy)與類間距離第74頁(yè)/共163頁(yè)第七十五頁(yè)，共163頁(yè)。76 的類內(nèi)離差陣定義為 (2-3-28)jw), 2 , 1()(1)(1)()(cjmxmxnSjjijnijijjWj23

35、 類的定義(dngy)與類間距離mjjwjnijijjxnm1)(1), 2 , 1(cj式中 為類 的模式均值矢量 (2-3-29)第75頁(yè)/共163頁(yè)第七十六頁(yè)，共163頁(yè)。77第76頁(yè)/共163頁(yè)第七十七頁(yè)，共163頁(yè)。78例2.3 .1 證明(zhngmng)：jnijijicjjjTmxmxnNnS1)()(1)(1jnijjjjijjijcjjmmmmmxmxnNn1)()(1)()(1BWSSBWTSSS23 類的定義(dngy)與類間距離NiiiTmxmxNS1)(1jnijijicjmxmxN1)()(1)(1第77頁(yè)/共163頁(yè)第七十八頁(yè)，共163頁(yè)。79 聚類的基本目的是

36、使 或 。利用(lyng)線形代數(shù)有關(guān)矩陣的跡和行列式的性質(zhì),可以定義如下4個(gè)聚類的準(zhǔn)則函數(shù): TrmaxBS11TrWBJS SBWSSJ1213TrWTJS STWSSJ14TrminWS23 類的定義(dngy)與類間距離第78頁(yè)/共163頁(yè)第七十九頁(yè)，共163頁(yè)。8011TrWBJS SBWSSJ1213TrWTJS STWSSJ1423 類的定義(dngy)與類間距離 由它們的構(gòu)造可以看出，為得到(d do)好的聚類結(jié)果，應(yīng)該使它們盡量的大。這類準(zhǔn)則也大量用在特征提取和選擇中。 第79頁(yè)/共163頁(yè)第八十頁(yè)，共163頁(yè)。8111TrWBJS SBWSSJ1213TrWTJS STWS

37、SJ1423 類的定義(dngy)與類間距離J1= 7.60886 J2= 0.0010397J3= 15.6089 J4= 62.9116用紙幣數(shù)據(jù)計(jì)算(j sun)獲得的結(jié)果：第80頁(yè)/共163頁(yè)第八十一頁(yè)，共163頁(yè)。82作業(yè)(zuy)P44: 2.4, 2.5, 2.6第81頁(yè)/共163頁(yè)第八十二頁(yè)，共163頁(yè)。8324 聚類的算法(sun f) 聚類的技術(shù)(jsh)方案聚類分析有很多具體的算法,有的比較簡(jiǎn)單,有的相對(duì)復(fù)雜(fz)和完善,但歸納起來就是三大類:1、按最小距離原則簡(jiǎn)單聚類方法2、按最小距離原則進(jìn)行兩類合并的方法3、依據(jù)準(zhǔn)則函數(shù)動(dòng)態(tài)聚類方法第82頁(yè)/共163頁(yè)第八十三頁(yè)，共

38、163頁(yè)。8424 聚類的算法(sun f) (1) 簡(jiǎn)單(jindn)聚類方法 針對(duì)具體(jt)問題確定相似性閾值，將模式到各聚類中心間的距離與閾值比較，當(dāng)大于閾值時(shí)該模式就作為另一類的類心，小于閾值時(shí)按最小距離原則將其分劃到某一類中。這類算法運(yùn)行中模式的類別及類的中心一旦確定將不會(huì)改變。第83頁(yè)/共163頁(yè)第八十四頁(yè)，共163頁(yè)。8524 聚類的算法(sun f) 首先視各模式(msh)自成一類,然后將距離最小的兩類合并成一類,不斷地重復(fù)這個(gè)過程，直到成為兩類為止。(2) 按最小距離原則進(jìn)行兩類合并(hbng)的方法這類算法運(yùn)行中，類心不斷地修正，但模式類別一旦指定后就不再改變，就是模式一

39、旦劃為一類后就不再被分劃開，這類算法也稱為譜系聚類法。第84頁(yè)/共163頁(yè)第八十五頁(yè)，共163頁(yè)。8624 聚類的算法(sun f) (3) 依據(jù)準(zhǔn)則函數(shù)(hnsh)動(dòng)態(tài)聚類法設(shè)定一些分類的控制參數(shù)，定義一個(gè)(y )能表征聚類結(jié)果優(yōu)劣的準(zhǔn)則函數(shù)，聚類過程就是使準(zhǔn)則函數(shù)取極值的優(yōu)化過程。算法運(yùn)行中，類心不斷地修正，各模式的類別的指定也不斷地更改。這類方法有C均值法、ISODATA法等。第85頁(yè)/共163頁(yè)第八十六頁(yè)，共163頁(yè)。8724 聚類的算法-簡(jiǎn)單(jindn)聚類方法 第86頁(yè)/共163頁(yè)第八十七頁(yè)，共163頁(yè)。8824 聚類的算法-簡(jiǎn)單(jindn)聚類方法 第87頁(yè)/共163頁(yè)第八十

40、八頁(yè)，共163頁(yè)。8924 聚類的算法(sun f)-簡(jiǎn)單聚類方法 第88頁(yè)/共163頁(yè)第八十九頁(yè)，共163頁(yè)。9024 聚類的算法(sun f)-簡(jiǎn)單聚類方法 這類算法的突出優(yōu)點(diǎn)是算法簡(jiǎn)單。但聚類過程中，類的中心一旦確定將不會(huì)改變，模式一旦指定(zhdng)類后也不再改變。算法(sun f)特點(diǎn):從算法的過程可以看出，該算法結(jié)果很大程度上依賴于距離門限T的選取及模式參與分類的次序。如果能有先驗(yàn)知識(shí)指導(dǎo)門限T的選取，通?？色@得較合理的效果。也可考慮設(shè)置不同的T和選擇不同的次序，最后選擇較好的結(jié)果進(jìn)行比較。第89頁(yè)/共163頁(yè)第九十頁(yè)，共163頁(yè)。9124 聚類的算法-簡(jiǎn)單(jindn)聚類方法

41、 簡(jiǎn)單(jindn)聚類圖例第90頁(yè)/共163頁(yè)第九十一頁(yè)，共163頁(yè)。92例：初始條件不同(b tn)的簡(jiǎn)單聚類結(jié)果初始(ch sh)中心不同門限不同樣本順序不同 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 10 9 8 10 9 8 8 7 6 8 7 6 11 6 7 11 6 7 9 10 11 9 10 11第91頁(yè)/共163頁(yè)第九十二頁(yè)，共163頁(yè)。9324 聚類的算法簡(jiǎn)單(jindn)聚類法程序 simpleclustering第92頁(yè)/共163頁(yè)第九十三頁(yè)，共163頁(yè)。9424 聚類的算法(sun f)最大最小距離法 第93頁(yè)/共163頁(yè)第九

42、十四頁(yè)，共163頁(yè)。9524 聚類的算法(sun f)-最大最小距離法 算法(sun f)原理步驟11xz 選任一模式特征矢量作為第一個(gè)聚類中心1z例如，。1z作為第二個(gè)聚類中心2z。 從待分類矢量集中選距離最遠(yuǎn)的特征矢量第94頁(yè)/共163頁(yè)第九十五頁(yè)，共163頁(yè)。96 計(jì)算(j sun)未被作為聚類中心的各模式特征矢量 ix與1z、2z之間的距離(jl)，并求出它們之中的最小值，jiijzxd)2 , 1( j 21,miniiiddd ), 2 , 1(Ni為表述簡(jiǎn)潔，雖然某些模式已選做聚類中心，但上面仍將所有模式下角標(biāo)全部列寫出來(ch li)，因這并不影響算法的正確性。即第95頁(yè)/共1

43、63頁(yè)第九十六頁(yè)，共163頁(yè)。972121),min(maxzzdddiiil則相應(yīng)的特征矢量lx作為第三個(gè)聚類中心，lxz3然后轉(zhuǎn)至；否則，轉(zhuǎn)至最后一步。 若 設(shè)存在k個(gè)聚類中心，計(jì)算未被作為聚類中心ijd,并算出ikiiildddd,minmax21如果21zzdl，則lkxz1否則，轉(zhuǎn)至最后一步。的各特征矢量到各聚類中心的距離并轉(zhuǎn)至；第96頁(yè)/共163頁(yè)第九十七頁(yè)，共163頁(yè)。98 當(dāng)判斷出不再有新的聚類中心之后，將模式特Nxxx,21中去，即計(jì)算jiijzxd), 2 , 1;, 2 , 1(Nij當(dāng) ddijjilmin，則判l(wèi)ixw。征矢量按最小距離原則分到各類這種算法的聚類結(jié)果與

44、參數(shù)心的選取有關(guān)。如果沒有先驗(yàn)知識(shí)指導(dǎo)和1z取，可適當(dāng)調(diào)整和1z選取最合理的一種聚類。以及第一個(gè)聚類中的選，比較多次試探分類結(jié)果，第97頁(yè)/共163頁(yè)第九十八頁(yè)，共163頁(yè)。9924 聚類的算法最大最小距離(jl)法程序 maxminclustering第98頁(yè)/共163頁(yè)第九十九頁(yè)，共163頁(yè)。10024 聚類的算法(sun f)層次聚類法 (Hierarchical Clustering Method)(系統(tǒng)(xtng)聚類法、 譜系聚類法）按最小距離(jl)原則不斷進(jìn)行兩類合并 譜系聚類法第99頁(yè)/共163頁(yè)第一百頁(yè)，共163頁(yè)。10124 聚類的算法(sun f)層次聚類法 (Hier

45、archical Clustering Method)(系統(tǒng)(xtng)聚類法、 譜系聚類法）按最小距離(jl)原則不斷進(jìn)行兩類合并 算法思想 首先將 N 個(gè)模式視作各自成為一類，然后計(jì)算類與類之間的距離，選擇距離最小的一對(duì)合并成一個(gè)新類，計(jì)算在新的類別分劃下各類之間的距離，再將距離最近的兩類合并，直至所有模式聚成兩類為止。 譜系聚類法第100頁(yè)/共163頁(yè)第一百零一頁(yè)，共163頁(yè)。10224 聚類的算法(sun f) 譜系(px)聚類法第101頁(yè)/共163頁(yè)第一百零二頁(yè)，共163頁(yè)。10324 聚類的算法(sun f) 譜系(px)聚類法第102頁(yè)/共163頁(yè)第一百零三頁(yè)，共163頁(yè)。104

46、例：如下圖所示 1、設(shè)全部(qunb)樣本分為6類，2、作距離矩陣D(0)3、求最小元素：4、把1,3合并7=(1,3)4,6合并8=(4,6)5、作距離矩陣D(1)3G1G2G5G4G6Gx1234523314474855262685913D(0)第103頁(yè)/共163頁(yè)第一百零四頁(yè)，共163頁(yè)。105例：如下(rxi)圖所示 1、設(shè)全部樣本分為6類，2、作距離矩陣D(0)3、求最小元素：4、把1,3合并7=(1,3)4,6合并8=(4,6)5、作距離矩陣D(1)3G1G2G5G4G6GxD(1)728238745522第104頁(yè)/共163頁(yè)第一百零五頁(yè)，共163頁(yè)。106枝狀圖1w5w2w3

47、w4w6w7w8w9w10w52582dd第105頁(yè)/共163頁(yè)第一百零六頁(yè)，共163頁(yè)。107枝狀圖1w5w2w3w4w6w7w8w9w10w3G1G2G5G4G6Gx第106頁(yè)/共163頁(yè)第一百零七頁(yè)，共163頁(yè)。10824 聚類的算法譜系(px)聚類法程序 Hierarchical clustering第107頁(yè)/共163頁(yè)第一百零八頁(yè)，共163頁(yè)。10924 聚類的算法(sun f)最大距離和層次聚類算法的一個(gè)共同特點(diǎn)是某個(gè)模式一旦劃分到某一類之后，在后繼的算法過程中就不改變了，而簡(jiǎn)單聚類算法中類心一旦選定后在后繼算法過程中也不再改變了。因此，這些方法(fngf)效果一般不會(huì)太理想。

48、第108頁(yè)/共163頁(yè)第一百零九頁(yè)，共163頁(yè)。110)()(12xxd2. 確定評(píng)估(pn )聚類質(zhì)量的準(zhǔn)則函數(shù)。1. 確定模式和聚類的距離測(cè)度。當(dāng)采用歐氏距離時(shí)，是計(jì)算此模式和該類中心的歐氏距離；為能反映出類的模式分布結(jié)構(gòu)，應(yīng)采用馬氏距離，設(shè)該類的均矢為，協(xié)方差陣為，則模式x和該類的x與該類均矢的馬氏距離：距離平方為3. 確定模式(msh)分劃及聚類合并或分裂的規(guī)則。24 聚類的算法(sun f)動(dòng)態(tài)聚類算法(sun f)要點(diǎn)第109頁(yè)/共163頁(yè)第一百一十頁(yè)，共163頁(yè)。11124 聚類的算法動(dòng)態(tài)聚類的基本(jbn)步驟1. 建立初始聚類中心(zhngxn)，進(jìn)行初始聚類；2. 計(jì)算模式

49、和類的距離，調(diào)整模式的類別；3. 計(jì)算各聚類的參數(shù)，刪除、合并或分裂一些聚類；4. 從初始聚類開始，運(yùn)用迭代算法動(dòng)態(tài)地改變模式的類別和聚類的中心(zhngxn)使準(zhǔn)則函數(shù)取得極值或設(shè)定的參數(shù)達(dá)到設(shè)計(jì)要求時(shí)停止。第110頁(yè)/共163頁(yè)第一百一十一頁(yè)，共163頁(yè)。11224 聚類的算法(sun f)動(dòng)態(tài)聚類的框圖產(chǎn)生初始(ch sh)聚類中心聚類檢驗(yàn)(jinyn)聚類合理性待分類模式 分類結(jié)果合理再迭代/修改參數(shù)不合理第111頁(yè)/共163頁(yè)第一百一十二頁(yè)，共163頁(yè)。113 條件及約定 設(shè)待分類的模式特征矢量集為：類的數(shù)目C是事先取定的。Nxxx,2124 聚類的算法(sun f) 動(dòng)態(tài)(dngt

50、i)聚類法C-均值法 算法(sun f)思想 該方法取定 C個(gè)類別和選取 C個(gè)初始聚類中心，按最小距離原則將各模式分配到 C類中的某一類，之后不斷地計(jì)算類心和調(diào)整各模式的類別，最終使各模式到其判屬類別中心的距離平方之和最小。第112頁(yè)/共163頁(yè)第一百一十三頁(yè)，共163頁(yè)。11424 聚類的算法(sun f) 動(dòng)態(tài)(dngti)聚類法C-均值法第113頁(yè)/共163頁(yè)第一百一十四頁(yè)，共163頁(yè)。11524 聚類的算法(sun f) 動(dòng)態(tài)(dngti)聚類法C-均值法第114頁(yè)/共163頁(yè)第一百一十五頁(yè)，共163頁(yè)。116選代表(dibio)點(diǎn)初始分類分類合理否4.動(dòng)態(tài)(dngti)聚類框圖24

51、聚類的算法(sun f) 動(dòng)態(tài)聚類法C-均值法最終分類Y修改分類N第115頁(yè)/共163頁(yè)第一百一十六頁(yè)，共163頁(yè)。117例使用聚類算法實(shí)現(xiàn)圖像(t xin)分割在散射圖上形成了兩個(gè)(lin )聚類，利用模式識(shí)別的方法將其分開，就實(shí)現(xiàn)了圖象的分割。第116頁(yè)/共163頁(yè)第一百一十七頁(yè)，共163頁(yè)。118第一步：令C=2，選初始聚類中心為1122(1)(0, 0 );(1)(1, 0 )TTZxZx樣本序號(hào)樣本序號(hào)x x1 1x x2 2x x3 3x x4 4x x5 5x x6 6x x7 7x x8 8x x9 9x x1010特征特征x x1 10 01 10 01 12 21 12 2

52、3 36 67 7特征特征x x2 20 00 01 11 11 12 22 22 26 66 6x11x12x13x14x15x16x17x18x19x2086789789896777788899第117頁(yè)/共163頁(yè)第一百一十八頁(yè)，共163頁(yè)。1191X5461098765109872X9x10 x11x12x13x14x15x16x17x18x19x20 x311243201x2x3x4x6x7x8x5x第118頁(yè)/共163頁(yè)第一百一十九頁(yè)，共163頁(yè)。12000第二步：000）（1x1(1)Z10100）（1x2(1)Z10001）（2x1(1)Z所以因?yàn)?x1x1(1)Z2(1)Z1

53、(1)Z1x第119頁(yè)/共163頁(yè)第一百二十頁(yè)，共163頁(yè)。1210)01()01(2x2(1)Z,所以因?yàn)?x1(1)Z2x2(1)Z2x2(1)Z同理, 12,213x3x3x4x4x4x1(1)Z1(1)Z1(1)Z2(1)Z2(1)Z2(1)Z.20652065都屬于、離計(jì)算出來，判斷與第二個(gè)聚類中心的距、同樣把所有2(1)Zxxxxxx因此分為兩類：),.,()1(),()1(20542231118,221NNGG二、一、xxxxxx第120頁(yè)/共163頁(yè)第一百二十一頁(yè)，共163頁(yè)。1221X5461098765109872X9x10 x11x12x13x14x15x16x17x18

54、x19x20 x311243201x2x3x4x6x7x8x5x)1(1Z)1(2Z第121頁(yè)/共163頁(yè)第一百二十二頁(yè)，共163頁(yè)。123第122頁(yè)/共163頁(yè)第一百二十三頁(yè)，共163頁(yè)。124111238(2)111(3)(.)8(1.25,1.13)iix GTZxxxxxN2291020(2)211(3)(.)12(7.67,7.33)iix GTZxxxxN11281(2)(,.,),8GxxxN2910202(2)(,.,),12Gx xxN第123頁(yè)/共163頁(yè)第一百二十四頁(yè)，共163頁(yè)。1251X5461098765109872X9x10 x11x12x13x14x15x16x

55、17x18x19x20 x311243201x2x3x4x6x7x8x5x)2(1Z)2(2Z第124頁(yè)/共163頁(yè)第一百二十五頁(yè)，共163頁(yè)。126(3)(2),1,2,jjZZj因轉(zhuǎn)第二步1220121220112829102012,.,(3),(3),.,(4)(,.,)(4)(,.,),8,12x xxZZx xxGx xxGxxxNN重新計(jì)算到的距離，分別把歸于最近的那個(gè)聚類中心，重新分為二類計(jì)算結(jié)束。TTZZZZ)33. 7 ,67. 7() 3() 4()13. 1 ,25. 1 () 3() 4(2211第125頁(yè)/共163頁(yè)第一百二十六頁(yè)，共163頁(yè)。127第126頁(yè)/共16

56、3頁(yè)第一百二十七頁(yè)，共163頁(yè)。128clustering24 聚類的算法(sun f) 動(dòng)態(tài)(dngti)聚類法C-均值法程序第127頁(yè)/共163頁(yè)第一百二十八頁(yè)，共163頁(yè)。129作業(yè)(zuy)P45: 2.7, 2.8第128頁(yè)/共163頁(yè)第一百二十九頁(yè)，共163頁(yè)。13024 聚類的算法(sun f) 動(dòng)態(tài)(dngti)聚類法C-均值法關(guān)于(guny)C-均值法收斂性的分析第129頁(yè)/共163頁(yè)第一百三十頁(yè)，共163頁(yè)。13124 聚類的算法(sun f) 動(dòng)態(tài)(dngti)聚類法C-均值法當(dāng)模式分布呈現(xiàn)類內(nèi)團(tuán)聚狀，C-均值算法是能達(dá)到很好的聚類結(jié)果，故應(yīng)用較多。從算法的迭代過程看，C

57、-均值算法是能使各模式到其所判屬的類別(libi)中心距離(平方)之和為最小的最佳聚類。第130頁(yè)/共163頁(yè)第一百三十一頁(yè)，共163頁(yè)。13224 聚類的算法(sun f) 動(dòng)態(tài)聚類法C-均值(jn zh)法的改進(jìn) 在類別(libi)數(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ù)。 在增加過程中，總會(huì)出現(xiàn)使本來較密集的類再拆開的情況，此時(shí)J雖減小，但減小速度將變緩。如果作一條C一J曲線，其曲率變化的最大點(diǎn)對(duì)應(yīng)的類數(shù)是比較接近最優(yōu)的類數(shù)。然而在許多情

58、況下，曲線并無明顯的這樣的點(diǎn)。第131頁(yè)/共163頁(yè)第一百三十二頁(yè)，共163頁(yè)。13324 聚類的算法(sun f) 動(dòng)態(tài)聚類法C-均值(jn zh)法的改進(jìn) 初始(ch sh)聚類中心的選取 憑經(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è)初始聚類中心。第132頁(yè)/共163頁(yè)第一百三十三頁(yè)，共163頁(yè)。13424

59、 聚類的算法(sun f) 動(dòng)態(tài)聚類法C-均值(jn zh)法的改進(jìn) 初始(ch sh)聚類中心的選取 用相距最遠(yuǎn)的C個(gè)特征點(diǎn)作為初始類心。具體地講，是按前述的最大最小距離算法求取C個(gè)初始聚類中心。 當(dāng)N較大時(shí)，先隨機(jī)地從N個(gè)模式中取出一部分模式用譜系聚類法聚成C類，以每類的重心作為初始類心。 設(shè)已標(biāo)準(zhǔn)化的待分類模式集為 希望將它們分為C類。 Nxxx,21第133頁(yè)/共163頁(yè)第一百三十四頁(yè)，共163頁(yè)。135 設(shè)已標(biāo)準(zhǔn)化的待分類模式集為 希望將它們分為C類。 Nxxx,21),(21niiiixxxx設(shè):nkikxisum1)()(maxisumMAi)(minisumMIi1)() 1(

60、MIMAMIisumci), 2 , 1(Ni計(jì)算(j sun):顯然0aiC，若ai最接近整數(shù)j，則把xi分劃至中wj。對(duì)所有樣本都實(shí)行上述處理，就可實(shí)現(xiàn)初始分類，從而產(chǎn)生(chnshng)初始聚類中心。第134頁(yè)/共163頁(yè)第一百三十五頁(yè)，共163頁(yè)。13624 聚類的算法(sun f) 動(dòng)態(tài)(dngti)聚類法C-均值法的改進(jìn) 用類核代替(dit)類心 前面的算法存在一個(gè)不足，即只用一個(gè)聚類中心點(diǎn)作為一類的代表，但一個(gè)點(diǎn)往往不能充分地反映該類的模式分布結(jié)構(gòu)，從而損失了很多有用的信息。當(dāng)類的分布不是球狀或近似球狀時(shí)，這種算法很難有較好的效果。此時(shí)，可用類核代替類心，類核可以是一個(gè)函數(shù)、一個(gè)