模式識(shí)別(chapter3)

1、1第第3 3章章 聚類分析聚類分析 (Clustering Analysis) 3.1 3.1 聚類分析的概念聚類分析的概念3.2 3.2 模式相似性測(cè)度模式相似性測(cè)度3.3 3.3 類的定義與類間距離類的定義與類間距離3.4 3.4 聚類的算法聚類的算法23.1 3.1 聚類分析的概念聚類分析的概念一、聚類分析的基本思想一、聚類分析的基本思想 相似的歸為一類。相似的歸為一類。 模式相似性的度量和聚類算法。模式相似性的度量和聚類算法。 無(wú)監(jiān)督分類無(wú)監(jiān)督分類（Unsupervised） 。二、特征量的類型二、特征量的類型 物理量物理量-(-(重量、長(zhǎng)度、速度重量、長(zhǎng)度、速度) ) 次序量次序量-

2、(-(等級(jí)、技能、學(xué)識(shí)等級(jí)、技能、學(xué)識(shí)) ) 名義量名義量-(-(性別、狀態(tài)、種類性別、狀態(tài)、種類) )3三、方法的有效性三、方法的有效性 取決于分類算法和特征點(diǎn)取決于分類算法和特征點(diǎn)分布情況的匹配。分布情況的匹配。3.1 聚類分析的概念2w2W1w1W2x1xb分類無(wú)效時(shí)的情況分類無(wú)效時(shí)的情況1.1.特征選取特征選取不當(dāng)不當(dāng)使分類無(wú)效。使分類無(wú)效。42 2. .特征選取特征選取不足不足可能使不同可能使不同類別的模式判為一類。類別的模式判為一類。2w2W1w1W2x1x3w3W3 3. .特征選取特征選取過(guò)多過(guò)多可能無(wú)益反可能無(wú)益反而有害而有害, ,增加分析負(fù)擔(dān)并使增加分析負(fù)擔(dān)并使分析效果變差

3、。分析效果變差。2w2W1w1W2x1xb54 4. .量綱選取不當(dāng)。量綱選取不當(dāng)。6下列是一些動(dòng)物的名稱：下列是一些動(dòng)物的名稱：羊羊 （sheepsheep）狗狗 （dogdog）藍(lán)鯊（藍(lán)鯊（blue sharkblue shark） 蜥蜴蜥蜴 （lizardlizard）毒蛇（毒蛇（viperviper）貓貓 （catcat）麻雀（麻雀（sparrowsparrow）海鷗海鷗 （seagullseagull）金魚(yú)（金魚(yú)（gold fishgold fish）緋鯢鰹（緋鯢鰹（red-mulletred-mullet）蛙蛙 （frogfrog）要對(duì)這些動(dòng)物進(jìn)行分類，則不同的特征有不同的分法：要

4、對(duì)這些動(dòng)物進(jìn)行分類，則不同的特征有不同的分法：特征選取不同對(duì)聚類結(jié)果的影響特征選取不同對(duì)聚類結(jié)果的影響7羊羊, , 狗狗, , 貓貓藍(lán)鯊藍(lán)鯊蜥蜴蜥蜴, ,毒蛇毒蛇, ,麻雀麻雀, ,海鷗海鷗, ,金魚(yú)金魚(yú), ,緋鯢鰹緋鯢鰹, , 青蛙青蛙(a) 按繁衍后代的方式分按繁衍后代的方式分哺乳動(dòng)物哺乳動(dòng)物非哺乳動(dòng)物非哺乳動(dòng)物(b) 按肺是否存在分按肺是否存在分金魚(yú)金魚(yú)緋鯢鰹緋鯢鰹藍(lán)鯊藍(lán)鯊羊羊, ,狗狗, ,貓貓蜥蜴蜥蜴, ,毒蛇毒蛇麻雀麻雀, ,海鷗海鷗 青蛙青蛙無(wú)肺無(wú)肺有肺有肺8藍(lán)鯊藍(lán)鯊金魚(yú)金魚(yú)緋鯢鰹緋鯢鰹蜥蜴蜥蜴, ,毒蛇毒蛇麻雀麻雀, ,海鷗海鷗 青蛙青蛙羊羊, ,狗狗, ,貓貓(d) 按繁衍后

5、代方式和肺是否存在分按繁衍后代方式和肺是否存在分非哺乳且有肺非哺乳且有肺哺乳且無(wú)肺哺乳且無(wú)肺哺乳且有肺哺乳且有肺非哺乳且無(wú)肺非哺乳且無(wú)肺(c) 按生活環(huán)境分按生活環(huán)境分青蛙青蛙羊羊, ,狗狗, ,貓貓 蜥蜥蜴蜴, ,毒蛇毒蛇麻雀麻雀, ,海鷗海鷗 金魚(yú)金魚(yú)緋鯢鰹緋鯢鰹 藍(lán)鯊藍(lán)鯊陸地陸地水里水里兩棲兩棲9距離測(cè)度不同距離測(cè)度不同,聚類結(jié)果也不同聚類結(jié)果也不同數(shù)據(jù)的粗聚類是兩類數(shù)據(jù)的粗聚類是兩類,細(xì)聚類為細(xì)聚類為4類類10綜上可見(jiàn)綜上可見(jiàn):選擇什么特征？選擇什么特征？選擇多少個(gè)特征？選擇多少個(gè)特征？選擇什么樣的量綱？選擇什么樣的量綱？選擇什么樣的距離測(cè)度？選擇什么樣的距離測(cè)度？ 這些對(duì)分類結(jié)果都會(huì)

6、產(chǎn)生極大影響。這些對(duì)分類結(jié)果都會(huì)產(chǎn)生極大影響。11聚類過(guò)程遵循的基本步驟 一、特征選擇(feature selection) 盡可能多地包含任務(wù)關(guān)心的信息二、近鄰測(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 result

7、s） 由專家用其他方法判定結(jié)果的正確性12聚類應(yīng)用的四個(gè)基本方向一、減少數(shù)據(jù) 許多時(shí)候，當(dāng)數(shù)據(jù)量N很大時(shí)，會(huì)使數(shù)據(jù)處理變得很費(fèi)力。因此可使用聚類分析的方法將數(shù)據(jù)分成幾組可判斷的聚類m（mN）來(lái)處理，每一個(gè)類可當(dāng)作獨(dú)立實(shí)體來(lái)對(duì)待。從這個(gè)角度看，數(shù)據(jù)被壓縮了。13二、假說(shuō)生成 在這種情況下，為了推導(dǎo)出數(shù)據(jù)性質(zhì)的一些假說(shuō)，對(duì)數(shù)據(jù)集進(jìn)行聚類分析。因此，這里使用聚類作為建立假說(shuō)的方法，然后用其他數(shù)據(jù)集驗(yàn)證這些假說(shuō)。14三、假說(shuō)檢驗(yàn) 用聚類分析來(lái)驗(yàn)證指定假說(shuō)的有效性。例如：考慮這樣的假說(shuō)例如：考慮這樣的假說(shuō)“大公司在海外投資大公司在海外投資”。要驗(yàn)證這個(gè)假說(shuō)是否正確，就要對(duì)大公司和有要驗(yàn)證這個(gè)假說(shuō)是否正確

8、，就要對(duì)大公司和有代表性的公司按規(guī)模、海外活躍度、成功完成代表性的公司按規(guī)模、海外活躍度、成功完成項(xiàng)目的能力等進(jìn)行聚類分析。從而來(lái)支持這個(gè)項(xiàng)目的能力等進(jìn)行聚類分析。從而來(lái)支持這個(gè)假說(shuō)。假說(shuō)。15四、基于分組的預(yù)測(cè) 對(duì)現(xiàn)有數(shù)據(jù)進(jìn)行聚類分析，形成模式的特征，并用特征表示聚類，接下來(lái)，對(duì)于一個(gè)未知模式，就可以用前面的聚類來(lái)確定是哪一類？例如：考慮被同種疾病感染的病人數(shù)據(jù)集。例如：考慮被同種疾病感染的病人數(shù)據(jù)集。先按聚類分析進(jìn)行分類，然后對(duì)新的病人確定他先按聚類分析進(jìn)行分類，然后對(duì)新的病人確定他適合的聚類，從而判斷他病情。適合的聚類，從而判斷他病情。163.2 3.2 模式相似性測(cè)度模式相似性測(cè)度 用

9、于描述各模式之間特征的相似程度用于描述各模式之間特征的相似程度 距距 離離 測(cè)測(cè) 度度 相相 似似 測(cè)測(cè) 度度 匹匹 配配 測(cè)測(cè) 度度17一、距離測(cè)度一、距離測(cè)度( (差值測(cè)度差值測(cè)度) )測(cè)度基礎(chǔ)：測(cè)度基礎(chǔ)：兩個(gè)矢量矢端的距離兩個(gè)矢量矢端的距離測(cè)度數(shù)值：測(cè)度數(shù)值：兩矢量各相應(yīng)分量之差的函數(shù)兩矢量各相應(yīng)分量之差的函數(shù)。時(shí)，等號(hào)成立；時(shí)，等號(hào)成立；0),(yxd，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)xy),(),(xydyxd),(),(),(yzdzxdyxd18常用的距離測(cè)度有：常用的距離測(cè)度有：1.1.歐氏歐氏(Euclidean)(Euclidean)距離距離 194.明氏(Minkowski)距離 2.

10、絕對(duì)值距離(街坊距離或Manhattan距離) 3.切氏(Chebyshev)距離 2021注意！馬氏距離對(duì)一切非奇異線性變換都是不變的，這說(shuō)明它不受特征量綱選擇的影響，并且是平移不變的。上面的V V的含義是這個(gè)矢量集的協(xié)方差陣的統(tǒng)計(jì)量，故馬氏距離加入了對(duì)特征的相關(guān)性的考慮。22現(xiàn)金識(shí)別例子現(xiàn)金識(shí)別例子( (歐氏平均距離歐氏平均距離) )數(shù)據(jù)樣本介紹：數(shù)據(jù)樣本介紹：10個(gè)文本文件個(gè)文本文件文件名：文件名：rmb00.txt rmb09.txt每個(gè)文件有每個(gè)文件有4個(gè)幣種的數(shù)據(jù)，分別是：個(gè)幣種的數(shù)據(jù)，分別是： 100圓、圓、50圓、圓、20圓、圓、10圓圓每個(gè)幣種有新舊兩種版本，每個(gè)幣種有新舊兩

11、種版本，4個(gè)方向，故有個(gè)方向，故有8個(gè)數(shù)據(jù)塊：個(gè)數(shù)據(jù)塊：如如100圓的圓的8個(gè)數(shù)據(jù)塊：個(gè)數(shù)據(jù)塊： data100a,data100b,data100c,data100ddata100a,data100b,data100c,data100d老版老版 data100e,data100f,data100g,data100hdata100e,data100f,data100g,data100h新版新版每個(gè)數(shù)據(jù)塊有每個(gè)數(shù)據(jù)塊有8個(gè)傳感器數(shù)據(jù)：個(gè)傳感器數(shù)據(jù)： 傳感器傳感器1，傳感器，傳感器2，傳感器，傳感器8每個(gè)傳感器有每個(gè)傳感器有60個(gè)采樣數(shù)據(jù)：個(gè)采樣數(shù)據(jù)： 數(shù)據(jù)數(shù)據(jù)1，數(shù)據(jù)，數(shù)據(jù)2，數(shù)據(jù)，數(shù)據(jù)6023

12、現(xiàn)金識(shí)別例子現(xiàn)金識(shí)別例子EuclidenEucliden=15.000000=15.000000Manhattan=33.000000Manhattan=33.000000ChebyshevChebyshev=11.000000=11.000000MinkowskiMinkowski=11.039449m=8=11.039449m=8100100元元A A面第面第1 1個(gè)樣本第個(gè)樣本第1010點(diǎn)和點(diǎn)和2020點(diǎn)的距離點(diǎn)的距離X:X: (75, 76,101, 83,102, 96, 91, 82) (75, 76,101, 83,102, 96, 91, 82)Y:Y: (70, 74, 90

13、, 76, 99, 96, 90, 86) (70, 74, 90, 76, 99, 96, 90, 86)X-Y: X-Y: 5, 2, 11, 7, 3, 0, 1, -45, 2, 11, 7, 3, 0, 1, -4距離測(cè)度距離測(cè)度rmbdis24二、相似測(cè)度測(cè)度基礎(chǔ)：以兩矢量的方向是否相近作為考慮的基礎(chǔ),矢量長(zhǎng)度并不重要。設(shè)1.角度相似系數(shù)(夾角余弦)注意：坐標(biāo)系的旋轉(zhuǎn)和尺度的縮放是不變的,但對(duì)一般的線形變換和坐標(biāo)系的平移不具有不變性。 252.相關(guān)系數(shù)它實(shí)際上是數(shù)據(jù)中心化后的矢量夾角余弦。 21)( )( )()( )(),(yyyyxxxxyyxxyxr3.指數(shù)相似系數(shù)niiii

14、yxnyxe122)(43exp1),(式中式中 為相應(yīng)分量的協(xié)方差，為相應(yīng)分量的協(xié)方差， 為矢量維數(shù)。為矢量維數(shù)。它不受量綱變化的影響。它不受量綱變化的影響。 2in26當(dāng)特征只有兩個(gè)狀態(tài)（當(dāng)特征只有兩個(gè)狀態(tài)（0 0，1 1）時(shí)，常用匹配測(cè)度。）時(shí)，常用匹配測(cè)度。0 0表示無(wú)此特征表示無(wú)此特征 ，1 1表示有此特征。故稱之為表示有此特征。故稱之為二值特征二值特征。 對(duì)于給定的對(duì)于給定的x x和和y y中的某兩個(gè)相應(yīng)分量中的某兩個(gè)相應(yīng)分量x xi i與與y yj j若若x xi i=1,y=1,yj j=1 =1 ，則稱，則稱 x xi i與與y yj j是是 (1-1)(1-1)匹配匹配；若

15、若x xi i=1,y=1,yj j=0 =0 ，則稱，則稱 x xi i與與y yj j是是 (1-0)(1-0)匹配；匹配；若若x xi i=0,y=0,yj j=1 =1 ，則稱，則稱 x xi i與與y yj j是是 (0-1)(0-1)匹配；匹配；若若x xi i=0,y=0,yj j=0 =0 ，則稱，則稱 x xi i與與y yj j是是 (0-0)(0-0)匹配。匹配。三、三、匹配測(cè)度匹配測(cè)度2728(1)Tanimoto測(cè)度測(cè)度yxyyxxyxcbaayxs),(2) RaoRao測(cè)度測(cè)度注：注：(1-1)匹配特征數(shù)目和所選用的特征數(shù)目之比。匹配特征數(shù)目和所選用的特征數(shù)目之比

16、。nyxecbaayxs),(3)(3)簡(jiǎn)單簡(jiǎn)單匹配系數(shù)匹配系數(shù)注：上式分子為注：上式分子為(1-1)匹配特征數(shù)目與匹配特征數(shù)目與(0-0)匹配特征數(shù)目之和，分母為匹配特征數(shù)目之和，分母為所考慮的特征數(shù)目。所考慮的特征數(shù)目。neayxm),(29例例 可以看出，它等于可以看出，它等于共同具有的特征數(shù)目共同具有的特征數(shù)目與分別與分別具有的特征種類總數(shù)之比。這里只考慮具有的特征種類總數(shù)之比。這里只考慮(1-1)(1-1)匹配而匹配而不考慮不考慮(0-0)(0-0)匹配。匹配。)0, 1, 1, 0, 1, 0(x) 1, 0, 1, 1, 0, 0(y 1 , 3 , 3yxyyxx511331)

17、,(yxs設(shè)設(shè)則則30(4) Dice系數(shù)系數(shù)(5) Kulzinsky系數(shù)系數(shù)的總數(shù)倆矢量中匹配個(gè)數(shù)11)-(12),(yyxxyxcbaayxm匹配個(gè)數(shù)匹配個(gè)數(shù)0)-(11)-(01)-(12),(yxyyxxyxcbayxm3133 類的定義與類間距離3.3.1 3.3.1 類的定義類的定義定義之定義之1 1 設(shè)集合設(shè)集合S S中任意元素中任意元素x xi i與與y yj j間的距離間的距離d dijij有有 d dijij h h其中其中h h為給定的閥值，稱為給定的閥值，稱S S對(duì)于閥值對(duì)于閥值h h組成一類。組成一類。 類的定義有很多種，類的劃分具有人為規(guī)定性，這類的定義有很多種，

18、類的劃分具有人為規(guī)定性，這反映反映在定義在定義的選取及參數(shù)的選擇上。一個(gè)分類結(jié)果的優(yōu)劣最后只能根據(jù)實(shí)際來(lái)評(píng)的選取及參數(shù)的選擇上。一個(gè)分類結(jié)果的優(yōu)劣最后只能根據(jù)實(shí)際來(lái)評(píng)價(jià)。價(jià)。323.3.2 3.3.2 類間距離測(cè)度方法類間距離測(cè)度方法 最近距離法最近距離法 最遠(yuǎn)距離法最遠(yuǎn)距離法 中間距離法中間距離法 重心距離法重心距離法 平均距離法平均距離法 離差平方和法離差平方和法33 最近距離法最近距離法 ijjikldD,minijdkixwljxw式中式中 表示表示 和和 之間的距離。之間的距離。 最遠(yuǎn)最遠(yuǎn)距離法距離法式中式中 表示表示 和和 之間的距離。之間的距離。 ijjikldD,maxijdk

19、ixwljxw34 中間中間距離法距離法pw wqw wkw wpqkpqDkqDklDkpDlw wpqkqkpklDDDD2222412121qplwww 重心距離法重心距離法22222)(pqqpqpkqqpqkpqppklDnnnnDnnnDnnnD35 平均平均距離法距離法wwqjpixxijqppqdnnD221 離差平方和法離差平方和法wtixtititxxxxs)()(qplwwwqplpqsssD2)()(2qpqpqpqppqxxxxnnnnDtxpxqx分別為對(duì)應(yīng)類的重心分別為對(duì)應(yīng)類的重心類內(nèi)離差平方和類內(nèi)離差平方和 2222pqlkkkqlkqkkplkpkklDnnn

20、DnnnnDnnnnD遞推公式為遞推公式為:36222222kqkppqkqqkppklDDDDDD 最近距離法最近距離法 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 (112121lkpknnnnlkqknnnnlkknnn373.3.3 3.3.3 聚類的準(zhǔn)則函數(shù)聚類的準(zhǔn)則函數(shù)判別

21、分類結(jié)果好壞的一般標(biāo)準(zhǔn)：判別分類結(jié)果好壞的一般標(biāo)準(zhǔn)：類內(nèi)距離小，類間距離大。類內(nèi)距離小，類間距離大。 某些算法需要一個(gè)能對(duì)分類過(guò)程或分類結(jié)果某些算法需要一個(gè)能對(duì)分類過(guò)程或分類結(jié)果的優(yōu)劣進(jìn)行評(píng)估的準(zhǔn)則函數(shù)。如果聚類準(zhǔn)則函數(shù)的優(yōu)劣進(jìn)行評(píng)估的準(zhǔn)則函數(shù)。如果聚類準(zhǔn)則函數(shù)選擇得好，聚類質(zhì)量就會(huì)高。聚類準(zhǔn)則往往是和選擇得好，聚類質(zhì)量就會(huì)高。聚類準(zhǔn)則往往是和類的定義有關(guān)的，是類的定義的某種體現(xiàn)。類的定義有關(guān)的，是類的定義的某種體現(xiàn)。38一、類內(nèi)距離準(zhǔn)則一、類內(nèi)距離準(zhǔn)則 設(shè)有待分類的模式集設(shè)有待分類的模式集 在某種相似性測(cè)在某種相似性測(cè)度基礎(chǔ)上被劃分為度基礎(chǔ)上被劃分為 類，類，類內(nèi)距離準(zhǔn)則函數(shù)類內(nèi)距離準(zhǔn)則函數(shù)

22、 定義為定義為:( 表示表示 類的模式均值矢量。類的模式均值矢量。)Nxxx,21cjjinicjx, 2 , 1;, 2 , 1)(；WJcjnijjiWjmxJ112)(jmjw39加權(quán)類內(nèi)距離準(zhǔn)則加權(quán)類內(nèi)距離準(zhǔn)則 : :WWJ21jcjjWWdNnJ2)()(2)()() 1(2jjijjkxxjkjijjjxxnndww式中，2)()(jkjixx表示jw類內(nèi)任兩個(gè)模式距離2) 1(jjnn 個(gè)組合數(shù)，所以2jd表示類內(nèi)Nnj表示jw類先驗(yàn)概率的估計(jì)頻率。平方和，共有兩模式間的均方距離。N為待分類模式總數(shù)，4041加權(quán)類間距離準(zhǔn)則加權(quán)類間距離準(zhǔn)則: :對(duì)于兩類問(wèn)題，類間距離有時(shí)取)()

23、(21212mmmmJB2BJ和WBJ的關(guān)系是221BWBJNnNnJmax)()(1cjjjjWBmmmmNnJ4243 的類內(nèi)離差陣定義為的類內(nèi)離差陣定義為 jw), 2 , 1()(1)(1)()(cjmxmxnSjjijnijijjWjmjjwjnijijjxnm1)(1), 2 , 1(cj式中式中 為類為類 的模式均值矢量的模式均值矢量 4445證明證明：jnijijicjjjTmxmxnNnS1)()(1)(1jnijjjjijjijcjjmmmmmxmxnNn1)()(1)()(1BWSSBWTSSSNiiiTmxmxNS1)(1jnijijicjmxmxN1)()(1)(1聚

24、類的基本目的是使聚類的基本目的是使 或或 。TrmaxBSTrminWS46 利用利用線形代數(shù)有關(guān)矩陣的跡和行列式的性質(zhì)線形代數(shù)有關(guān)矩陣的跡和行列式的性質(zhì), ,可可以定義如下以定義如下4 4個(gè)聚類的準(zhǔn)則函數(shù)個(gè)聚類的準(zhǔn)則函數(shù): : 11TrWBJS SBWSSJ1213TrWTJS STWSSJ14 由它們的構(gòu)造可以看出，為得到好的聚類由它們的構(gòu)造可以看出，為得到好的聚類結(jié)果，應(yīng)該使它們盡量的大。這類準(zhǔn)則也大量結(jié)果，應(yīng)該使它們盡量的大。這類準(zhǔn)則也大量用在特征提取和選擇中。用在特征提取和選擇中。 4734 聚類的算法 3.4.1 聚類的技術(shù)方案聚類的技術(shù)方案聚類分析有很多具體的算法聚類分析有很多具

25、體的算法,有的比較簡(jiǎn)單有的比較簡(jiǎn)單,有的相對(duì)復(fù)雜和完善有的相對(duì)復(fù)雜和完善,但歸納起來(lái)就是三大類但歸納起來(lái)就是三大類:1、按最小距離原則簡(jiǎn)單聚類方法、按最小距離原則簡(jiǎn)單聚類方法2、按最小距離原則進(jìn)行兩類合并的方法、按最小距離原則進(jìn)行兩類合并的方法3、依據(jù)準(zhǔn)則函數(shù)動(dòng)態(tài)聚類方法、依據(jù)準(zhǔn)則函數(shù)動(dòng)態(tài)聚類方法48(1) (1) 簡(jiǎn)單聚類方法簡(jiǎn)單聚類方法 針對(duì)具體問(wèn)題確定相似性閾值，將模式到各聚針對(duì)具體問(wèn)題確定相似性閾值，將模式到各聚類中心間的距離與閾值比較，當(dāng)大于閾值時(shí)該模類中心間的距離與閾值比較，當(dāng)大于閾值時(shí)該模式就作為另一類的類心，小于閾值時(shí)按最小距離式就作為另一類的類心，小于閾值時(shí)按最小距離原則將其

26、分劃到某一類中。原則將其分劃到某一類中。這類算法運(yùn)行中模式的類別及類的中心一旦確這類算法運(yùn)行中模式的類別及類的中心一旦確定將不會(huì)改變。定將不會(huì)改變。49首先視各模式自成一類首先視各模式自成一類, ,然后將距離最小的兩然后將距離最小的兩類合并成一類類合并成一類, ,不斷地重復(fù)這個(gè)過(guò)程，直到成為不斷地重復(fù)這個(gè)過(guò)程，直到成為兩類為止。兩類為止。(2) 按最小距離原則進(jìn)行兩類合并的方法按最小距離原則進(jìn)行兩類合并的方法這類算法運(yùn)行中，類心不斷地修正，但模式這類算法運(yùn)行中，類心不斷地修正，但模式類別一旦指定后就不再改變，就是模式一旦劃為類別一旦指定后就不再改變，就是模式一旦劃為一類后就不再被分劃開(kāi)，這類算

27、法也稱為譜系聚一類后就不再被分劃開(kāi)，這類算法也稱為譜系聚類法。類法。50(3) 依據(jù)準(zhǔn)則函數(shù)動(dòng)態(tài)聚類法依據(jù)準(zhǔn)則函數(shù)動(dòng)態(tài)聚類法設(shè)定一些分類的控制參數(shù)，定義一個(gè)能表征聚設(shè)定一些分類的控制參數(shù)，定義一個(gè)能表征聚類結(jié)果優(yōu)劣的準(zhǔn)則函數(shù)，聚類過(guò)程就是使準(zhǔn)則函類結(jié)果優(yōu)劣的準(zhǔn)則函數(shù)，聚類過(guò)程就是使準(zhǔn)則函數(shù)取極值的優(yōu)化過(guò)程。數(shù)取極值的優(yōu)化過(guò)程。算法運(yùn)行中，類心不斷地修正，各模式的類別算法運(yùn)行中，類心不斷地修正，各模式的類別的指定也不斷地更改。這類方法有的指定也不斷地更改。這類方法有C C均值法、均值法、ISODATAISODATA法等。法等。5134 聚類的算法-簡(jiǎn)單聚類方法簡(jiǎn)單聚類方法 Simple-clus

28、teringSimple-clustering5234 聚類的算法-簡(jiǎn)單聚類方法簡(jiǎn)單聚類方法 5334 聚類的算法-簡(jiǎn)單聚類方法簡(jiǎn)單聚類方法 5434 聚類的算法-簡(jiǎn)單聚類方法簡(jiǎn)單聚類方法 這類算法的突出優(yōu)點(diǎn)是算法簡(jiǎn)單。但聚類過(guò)程這類算法的突出優(yōu)點(diǎn)是算法簡(jiǎn)單。但聚類過(guò)程中，類的中心一旦確定將不會(huì)改變，模式一旦指定中，類的中心一旦確定將不會(huì)改變，模式一旦指定類后也不再改變。類后也不再改變。算法特點(diǎn)算法特點(diǎn):從算法的過(guò)程可以看出，該算法結(jié)果很大程度從算法的過(guò)程可以看出，該算法結(jié)果很大程度上依賴于距離門限上依賴于距離門限T的選取及模式參與分類的次序。的選取及模式參與分類的次序。如果能有先驗(yàn)知識(shí)指導(dǎo)門

29、限如果能有先驗(yàn)知識(shí)指導(dǎo)門限T的選取，通常可獲得的選取，通常可獲得較合理的效果。也可考慮設(shè)置不同的較合理的效果。也可考慮設(shè)置不同的T和選擇不同和選擇不同的次序，最后選擇較好的結(jié)果進(jìn)行比較。的次序，最后選擇較好的結(jié)果進(jìn)行比較。5534 聚類的算法-簡(jiǎn)單聚類方法簡(jiǎn)單聚類方法 簡(jiǎn)單聚類圖簡(jiǎn)單聚類圖例例56例例.1：初始條件不同的簡(jiǎn)單聚類結(jié)果：初始條件不同的簡(jiǎn)單聚類結(jié)果初始中心不同門限不同樣本順序不同 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 1

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

31、602121),min(maxzzdddiiil則相應(yīng)的特征矢量lx作為第三個(gè)聚類中心，lxz3然后轉(zhuǎn)至；否則，轉(zhuǎn)至最后一步。 若 設(shè)存在k個(gè)聚類中心，計(jì)算未被作為聚類中心ijd,并算出ikiiildddd,minmax21如果21zzdl，則lkxz1否則，轉(zhuǎn)至最后一步。的各特征矢量到各聚類中心的距離并轉(zhuǎn)至；61 當(dāng)判斷出不再有新的聚類中心之后，將模式特Nxxx,21中去，即計(jì)算jiijzxd), 2 , 1;, 2 , 1(Nij當(dāng) ddijjilmin，則判l(wèi)ixw。征矢量按最小距離原則分到各類這種算法的聚類結(jié)果與參數(shù)心的選取有關(guān)。如果沒(méi)有先驗(yàn)知識(shí)指導(dǎo)和1z取，可適當(dāng)調(diào)整和1z選取最合理

32、的一種聚類。以及第一個(gè)聚類中的選，比較多次試探分類結(jié)果，623.4.3 3.4.3 層次層次聚類法聚類法 (Hierarchical Clustering Method) (系統(tǒng)聚類法、系統(tǒng)聚類法、 譜系聚類法）譜系聚類法） 算法思想算法思想 首先將首先將 N N 個(gè)模式視作各自成為一類，然后計(jì)算個(gè)模式視作各自成為一類，然后計(jì)算類與類之間的距離，選擇距離最小的一對(duì)合并成一類與類之間的距離，選擇距離最小的一對(duì)合并成一個(gè)新類，計(jì)算在新的類別分劃下各類之間的距離，個(gè)新類，計(jì)算在新的類別分劃下各類之間的距離，再將距離最近的兩類合并，直至所有模式聚成兩類再將距離最近的兩類合并，直至所有模式聚成兩類為止。

33、為止。636465例3.4.3：如下圖所示 1、設(shè)全部樣本分為6類， 2、作距離矩陣D(0) 3、求最小元素： 4、把1,3合并7=(1,3) 4,6合并8=(4,6) 5、作距離矩陣D(1)3G1G2G5G4G6Gx1234523314474855262685913D(0)66例3.4.3：如下圖所示 1、設(shè)全部樣本分為6類， 2、作距離矩陣D(0) 3、求最小元素： 4、把1,3合并7=(1,3) 4,6合并8=(4,6) 5、作距離矩陣D(1)3G1G2G5G4G6GxD(1)72823874552267 6 6、若合并的類數(shù)沒(méi)有達(dá)到要求，轉(zhuǎn)、若合并的類數(shù)沒(méi)有達(dá)到要求，轉(zhuǎn)3 3。否則停止

34、。否則停止。 3 3、求最小元素：、求最小元素： 4 4、8,5,28,5,2合并合并, 9=, 9=（2,5,4,62,5,4,6）枝狀圖1w5w2w3w4w6w7w8w9w10w52582dd68枝狀圖1w5w2w3w4w6w7w8w9w10w3G1G2G5G4G6Gx6934 聚類的算法最大距離和層次聚類算法的一個(gè)共同特點(diǎn)是某最大距離和層次聚類算法的一個(gè)共同特點(diǎn)是某個(gè)模式一旦劃分到某一類之后，在后繼的算法過(guò)程個(gè)模式一旦劃分到某一類之后，在后繼的算法過(guò)程中就不改變了，而簡(jiǎn)單聚類算法中類心一旦選定后中就不改變了，而簡(jiǎn)單聚類算法中類心一旦選定后在后繼算法過(guò)程中也不再改變了。因此，這些方法在后繼

35、算法過(guò)程中也不再改變了。因此，這些方法效果一般不會(huì)太理想。效果一般不會(huì)太理想。 70)()(12xxd2. 確定評(píng)估聚類質(zhì)量的準(zhǔn)則函數(shù)。1. 確定模式和聚類的距離測(cè)度。當(dāng)采用歐氏距離時(shí)，是計(jì)算此模式和該類中心的歐氏距離；為能反映出類的模式分布結(jié)構(gòu)，應(yīng)采用馬氏距離，設(shè)該類的均矢為，協(xié)方差陣為，則模式x和該類的x與該類均矢的馬氏距離：距離平方為3. 確定模式分劃及聚類合并或分裂的規(guī)則。34 聚類的算法動(dòng)態(tài)聚類算法要點(diǎn)動(dòng)態(tài)聚類算法要點(diǎn)7134 聚類的算法動(dòng)態(tài)聚類的基本步驟動(dòng)態(tài)聚類的基本步驟1. 建立初始聚類中心，進(jìn)行初始聚類；2. 計(jì)算模式和類的距離，調(diào)整模式的類別；3. 計(jì)算各聚類的參數(shù)，刪除、合

36、并或分裂一些聚類；4. 從初始聚類開(kāi)始，運(yùn)用迭代算法動(dòng)態(tài)地改變模式的類別和聚類的中心使準(zhǔn)則函數(shù)取得極值或設(shè)定的參數(shù)達(dá)到設(shè)計(jì)要求時(shí)停止。7234 聚類的算法動(dòng)態(tài)聚類的框圖動(dòng)態(tài)聚類的框圖產(chǎn)生初始產(chǎn)生初始聚類中心聚類中心聚類聚類檢驗(yàn)聚類檢驗(yàn)聚類合理性合理性待分類模式待分類模式 分類結(jié)分類結(jié)果果合理合理再迭代再迭代/修改參數(shù)修改參數(shù)不合理不合理73 條件及約定條件及約定 設(shè)待分類的模式特征矢量集為：設(shè)待分類的模式特征矢量集為：類的數(shù)目類的數(shù)目C C是事先取定的。是事先取定的。Nxxx,2134 聚類的算法 3.4.3 動(dòng)態(tài)聚類法動(dòng)態(tài)聚類法C-均值法均值法 算法思想算法思想 該方法該方法取定取定 C C

37、個(gè)類別個(gè)類別和選取和選取 C C個(gè)初始聚類中個(gè)初始聚類中心心，按最小距離原則將各模式分配到按最小距離原則將各模式分配到 C C類中的某類中的某一類，之后不斷地一類，之后不斷地計(jì)算類心和調(diào)整各模式計(jì)算類心和調(diào)整各模式的類別，的類別，最終使各模式到其判屬類別中心的距離平方之和最終使各模式到其判屬類別中心的距離平方之和最小。最小。7434 聚類的算法 3.4.3 動(dòng)態(tài)聚類法動(dòng)態(tài)聚類法C-均值法均值法75選代表點(diǎn)選代表點(diǎn)初始分類初始分類分類合理否分類合理否4.4.動(dòng)態(tài)聚類框圖動(dòng)態(tài)聚類框圖34 聚類的算法 3.4.3 動(dòng)態(tài)聚類法動(dòng)態(tài)聚類法C-均值法均值法最終分類最終分類Y修改分類修改分類N76例例3.4

38、.2 3.4.2 使用聚類算法實(shí)現(xiàn)圖像分割使用聚類算法實(shí)現(xiàn)圖像分割在散射圖上形成了兩個(gè)聚類，利用模式識(shí)別的在散射圖上形成了兩個(gè)聚類，利用模式識(shí)別的方法將其分開(kāi)，就實(shí)現(xiàn)了圖象的分割。方法將其分開(kāi)，就實(shí)現(xiàn)了圖象的分割。77 例例.3：已知有已知有2020個(gè)樣本，每個(gè)樣本有個(gè)樣本，每個(gè)樣本有2 2個(gè)特征，數(shù)據(jù)個(gè)特征，數(shù)據(jù)分布分布如下圖如下圖, ,使用使用C C均值法實(shí)現(xiàn)樣本分類（均值法實(shí)現(xiàn)樣本分類（C=2C=2）。）。第一步第一步：令：令C=2C=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 23 36 67 7特征特征