模式識(shí)別聚類(lèi)精品課件

1、模式識(shí)別聚類(lèi)第1頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四什么是聚類(lèi)聚類(lèi)是一種無(wú)監(jiān)督分類(lèi)法: 沒(méi)有預(yù)先指定的類(lèi)別分類(lèi)：用已知類(lèi)別的樣本訓(xùn)練集來(lái)設(shè)計(jì)分類(lèi)器（監(jiān)督學(xué)習(xí)）聚類(lèi)：用事先不知類(lèi)別的樣本，利用樣本的先驗(yàn)知識(shí)來(lái)構(gòu)造分類(lèi)器（無(wú)監(jiān)督學(xué)習(xí)）聚類(lèi)分析無(wú)訓(xùn)練過(guò)程，訓(xùn)練與識(shí)別混合在一起。 第2頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四相似性度量設(shè)有樣本集 ，要求按某種相似性把分類(lèi)，怎樣實(shí)現(xiàn)？聚類(lèi)分析符合“物以類(lèi)聚，人以群分“的原則，它把相似性大的樣本聚集為一個(gè)類(lèi)型，在特征空間里占據(jù)著一個(gè)局部區(qū)域。每個(gè)局部區(qū)域都形成一個(gè)聚合中心，聚合中心代表相應(yīng)類(lèi)型。第3頁(yè)，共48頁(yè)，2022

2、年，5月20日，6點(diǎn)30分，星期四如下圖中，(a)有一個(gè)聚合中心，(b)、(c)有兩個(gè)。第4頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四聚類(lèi)分析避免了估計(jì)類(lèi)概率密度的困難，對(duì)每個(gè)聚合中心來(lái)說(shuō)都是局部密度極大值位置，其附近密度高，距離越遠(yuǎn)密度越小。 聚類(lèi)分析的關(guān)鍵問(wèn)題：如何在聚類(lèi)過(guò)程中自動(dòng)地確定類(lèi)型數(shù)目c。實(shí)際工作中，也可以給定值作為算法終止的條件。第5頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四聚類(lèi)分析的結(jié)果與特征的選取有很大的關(guān)系。不同的特征，分類(lèi)的結(jié)果不同。第6頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四1.距離相似性度量一個(gè)模式樣本，對(duì)應(yīng)特征空間里的一

3、個(gè)點(diǎn)。如果模式的特征是適當(dāng)選擇的，也就是各維特征對(duì)于分類(lèi)來(lái)說(shuō)都是有效的，那么同類(lèi)樣本就會(huì)密集地分布在一個(gè)區(qū)域里，不同類(lèi)的模式樣本就會(huì)遠(yuǎn)離。因此，點(diǎn)間距離遠(yuǎn)近反映了相應(yīng)模式樣本所屬類(lèi)型有無(wú)差異，可以作為樣本相似性度量。距離越近，相似性越大，屬于一個(gè)類(lèi)型。聚類(lèi)分析中，最常用的就是距離相似性。第7頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四（1）歐氏距離歐氏距離簡(jiǎn)稱(chēng)距離，模式樣本向量 x與y之間的歐氏距離定義為： d為特征空間的維數(shù)。 當(dāng) 較小時(shí)，表示x與y在一個(gè)類(lèi)型區(qū)域，反之，則不在一個(gè)類(lèi)型區(qū)域。這里有一個(gè)門(mén)限的選擇問(wèn)題。若選擇過(guò)大，則全部樣本被視作一個(gè)唯一類(lèi)型；若選取過(guò)小，則可能造成

4、每個(gè)樣本都單獨(dú)構(gòu)成一個(gè)類(lèi)型。必須正確選擇門(mén)限值以保證正確分類(lèi)。 第8頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四（1）歐氏距離（續(xù)）另外，模式特征坐標(biāo)單位的選取也會(huì)強(qiáng)烈地影響聚類(lèi)結(jié)果。例如：一個(gè)二維模式，一個(gè)特征是長(zhǎng)度，另一個(gè)特征是壓力。當(dāng)長(zhǎng)度由厘米變?yōu)槊?，?中長(zhǎng)度特征的比重會(huì)下降，同樣，若把比重單位由毫米汞柱高度變成厘米汞柱高度， 中壓力特征的影響也會(huì)下降。第9頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四（1）歐氏距離（續(xù)）可以用圖表示上述情況：從上圖看出，(b)、(c)特征空間劃分是不同的。(b)中 為一類(lèi)， 為另一類(lèi)，(c) 中 為一類(lèi)， 為另一類(lèi)。 第10頁(yè)，

5、共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四（1）歐氏距離（續(xù)）另外，使用歐氏距離度量時(shí)，還要注意模式樣本測(cè)量值的選取，應(yīng)該是有效反映類(lèi)別屬性特征（各類(lèi)屬性的代表應(yīng)均衡）。但馬氏距離可解決不均衡（一個(gè)多，一個(gè)少）的問(wèn)題。例如，取5個(gè)樣本，其中有4個(gè)反映對(duì)分類(lèi)有意義的特征A，只有1個(gè)對(duì)分類(lèi)有意義的特征B，歐氏距離的計(jì)算結(jié)果，則主要體現(xiàn)特征A。第11頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四（2）馬氏（Mahalanobis）距離定義：馬氏距離的平方其中，為均值向量，為協(xié)方差矩陣。馬氏距離排除了不同特征之間相關(guān)性的影響，其關(guān)鍵在于協(xié)方差矩陣的計(jì)算。當(dāng)為對(duì)角陣時(shí)，各特征之間才完

6、全獨(dú)立；當(dāng)為單位矩陣時(shí)，馬氏距離等于歐氏距離。馬氏距離比較適用于對(duì)樣本已有初步分類(lèi)的情況，做進(jìn)一步考核、修正。第12頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四（3）明氏（Minkowsky）距離定義：明氏距離:它是若干距離函數(shù)的通式： 時(shí)，等于歐氏距離； 時(shí)，稱(chēng)為“街坊”（city block）距離。第13頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四2. 角度相似性度量樣本x與y之間的角度相似性度量定義為它們之間夾角的余弦，即 也是單位向量之間的點(diǎn)積（內(nèi)積）。 越大， x與y越相似。常用于情報(bào)檢索、植物分類(lèi)、疾病分類(lèi)。第14頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)3

7、0分，星期四2. 角度相似性度量 滿足： 當(dāng) 時(shí)， 達(dá)到最大。對(duì)于坐標(biāo)系的旋轉(zhuǎn)及放大、縮小 是不變的量，但對(duì)位移和一般性的線性變換不是不變的。樣本與核的相似性度量近鄰函數(shù)值相等第15頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四樣本相似性度量是聚類(lèi)分析的基礎(chǔ)，針對(duì)具體問(wèn)題，選擇適當(dāng)?shù)南嗨菩远攘渴潜ＷC聚類(lèi)質(zhì)量的重要問(wèn)題。但有了相似性度量還不夠，還必須有適當(dāng)?shù)木垲?lèi)準(zhǔn)則函數(shù)。聚類(lèi)準(zhǔn)則函數(shù)對(duì)聚類(lèi)質(zhì)量也有重大影響。相似性度量 集合與集合的相似性。相似性準(zhǔn)則 分類(lèi)效果好壞的評(píng)價(jià)準(zhǔn)則 第16頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四聚類(lèi)準(zhǔn)則函數(shù)在樣本相似性度量的基礎(chǔ)上，聚類(lèi)分析還需要

8、一定的準(zhǔn)則函數(shù)，才能把真正屬于同一類(lèi)的樣本聚合成一個(gè)類(lèi)型的子集，而把不同類(lèi)的樣本分離開(kāi)來(lái)。如果聚類(lèi)準(zhǔn)則函數(shù)選得好，聚類(lèi)質(zhì)量就會(huì)高。第17頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四聚類(lèi)準(zhǔn)則函數(shù)同時(shí)，聚類(lèi)準(zhǔn)則函數(shù)還可以用來(lái)評(píng)價(jià)一種聚類(lèi)結(jié)果的質(zhì)量，如果聚類(lèi)質(zhì)量不滿足要求，就要重復(fù)執(zhí)行聚類(lèi)過(guò)程，以優(yōu)化結(jié)果。在重復(fù)優(yōu)化中，可以改變相似性度量，也可以選用新的聚類(lèi)準(zhǔn)則。第18頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四1誤差平方和準(zhǔn)則（最常用的）假定有混合樣本 ，采用某種相似性度量， 被聚合成 c個(gè)分離開(kāi)的子集，每個(gè)子集是一個(gè)類(lèi)型，它們分別包含 個(gè)樣本。為了衡量聚類(lèi)的質(zhì)量，采用誤差

9、平方和 聚類(lèi)準(zhǔn)則函數(shù)，定義為：mj是個(gè)集合的中心，可以用來(lái)代表c個(gè)類(lèi)型。第19頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四誤差平方和準(zhǔn)則（續(xù)） 是樣本和集合中心的函數(shù)。在樣本集X給定的情況下， 的取值取決于c個(gè)集合中心。 描述個(gè)n試驗(yàn)樣本聚合成c個(gè)類(lèi)型時(shí)，所產(chǎn)生的總誤差平方和。 越小越好。 第20頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四誤差平方和準(zhǔn)則（續(xù)）誤差平方和準(zhǔn)則適用于各類(lèi)樣本比較密集且樣本數(shù)目懸殊不大的樣本分布。例如：上圖的樣本分布，共有3個(gè)類(lèi)型，各個(gè)類(lèi)型的樣本數(shù)目相差不多（10個(gè)左右）。類(lèi)內(nèi)較密集，誤差平方和很小，類(lèi)別之間距離遠(yuǎn)。第21頁(yè)，共48頁(yè)，202

10、2年，5月20日，6點(diǎn)30分，星期四誤差平方和準(zhǔn)則（續(xù)）注意：如果不同類(lèi)型的樣本數(shù)目相差很大，采用誤差平方和準(zhǔn)則，有可能把樣本數(shù)目多的類(lèi)型分開(kāi)，以便達(dá)到總的 最小。如下圖所示：第22頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四誤差平方和準(zhǔn)則（續(xù)）下面進(jìn)一步說(shuō)明上述問(wèn)題：例如：有5個(gè)樣本，如下圖所示 第23頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四誤差平方和準(zhǔn)則（續(xù)）虛線為正確類(lèi)型區(qū)分域，實(shí)線為采用誤差平方和最小準(zhǔn)則時(shí)的類(lèi)別區(qū)分。虛線劃分時(shí)： 第24頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四誤差平方和準(zhǔn)則（續(xù)）實(shí)線劃分時(shí)： 所以 ，如果按誤差平方和準(zhǔn)則聚類(lèi)

11、將得到錯(cuò)誤結(jié)果。第25頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四2加權(quán)平均平方距離和準(zhǔn)則定義：加權(quán)平均平方距離和準(zhǔn)則 式中： 是類(lèi)內(nèi)樣本間平均平方距離，即所有的樣本之間距離的平均值 。第26頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四加權(quán)平均平方距離和準(zhǔn)則（續(xù)） 為 類(lèi)的先驗(yàn)概率，可以用樣本數(shù)目 和樣本總數(shù)目 來(lái)估計(jì) 因此： 第27頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四加權(quán)平均平方距離和準(zhǔn)則（續(xù)）用 重新討論誤差平方和準(zhǔn)則中所舉例子。5個(gè)樣本，如圖所示。第28頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四第29頁(yè)，共48頁(yè)，2022年，5月

12、20日，6點(diǎn)30分，星期四加權(quán)平均平方距離和準(zhǔn)則（續(xù)）雖然 ，但已較接近。所以，當(dāng)各類(lèi)樣本數(shù)目相差懸殊時(shí)，使用加權(quán)平均平方距離和準(zhǔn)則，要比使用誤差平方和準(zhǔn)則容易得到正確聚類(lèi)結(jié)果。同 一樣， 越小，樣本類(lèi)內(nèi)越密集。以聚合中心為極大值的局部區(qū)域密度越高，聚類(lèi)結(jié)果越好。第30頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四3類(lèi)間距離和準(zhǔn)則類(lèi)間距離和可用于描述聚類(lèi)結(jié)果的類(lèi)間距離分布狀態(tài)。它定義為：加權(quán)類(lèi)間距離和： 式中，第31頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四類(lèi)間距離和準(zhǔn)則（續(xù)）對(duì)于兩類(lèi)問(wèn)題，類(lèi)間距離常用下式計(jì)算類(lèi)間距離和準(zhǔn)則描述不同類(lèi)型之間的分離程度，所以值越大，表示各

13、類(lèi)之間分離性好，聚類(lèi)質(zhì)量高。 第32頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四4散射矩陣為了對(duì)聚類(lèi)質(zhì)量有一個(gè)全面的描述和考核標(biāo)準(zhǔn)，可以通過(guò)散射矩陣引導(dǎo)出一些準(zhǔn)則函數(shù)，它們不但反映同類(lèi)樣本的聚集程度，而且也反映不同類(lèi)之間的分離程度。 第33頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四散射矩陣（續(xù)）假定混合樣本集X的n個(gè)樣本被聚集成c個(gè)類(lèi)型的子集Xj，每個(gè)子集有nj個(gè)樣本，則類(lèi)內(nèi)散射矩陣 定義為：其中 為某一個(gè)類(lèi)型的類(lèi)內(nèi)散射矩陣：第34頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四散射矩陣（續(xù)）類(lèi)間散射矩陣 定義為： 式中， 為各類(lèi)型的均值向量， 為全部樣本的均

14、值向量， ( )為各類(lèi)型先驗(yàn)概率。 第35頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四定義全部樣本的總散射矩陣 為：上述3個(gè)散射矩陣有如下關(guān)系：這一結(jié)果表明，對(duì)于給定的混合樣本集，類(lèi)內(nèi)散射的減少，將導(dǎo)致類(lèi)間散射的增加。對(duì)某一聚類(lèi)結(jié)果，類(lèi)內(nèi)散射越小越好，類(lèi)間散射越大越好。 第36頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四利用 、 、 可以定義如下的4個(gè)聚類(lèi)準(zhǔn)則： 表示矩陣的跡，也就是對(duì)角線元素之和，| |為行列式。J1J4同時(shí)考慮了類(lèi)內(nèi)的散射和類(lèi)間散射，為了得到好的聚類(lèi)結(jié)果，它們的值越大越好。第37頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四兩種簡(jiǎn)單的聚類(lèi)算

15、法 介紹兩種簡(jiǎn)單的聚類(lèi)分析方法，它是對(duì)某些關(guān)鍵性的元素進(jìn)行試探性的選取，使某種聚類(lèi)準(zhǔn)則達(dá)到最優(yōu)，又稱(chēng)為基于試探的聚類(lèi)算法。采用最近鄰規(guī)則的聚類(lèi)算法 最大最小距離聚類(lèi)算法第38頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四1采用最近鄰規(guī)則的聚類(lèi)算法假設(shè)已有混合樣本集 ，按照最近鄰原則進(jìn)行聚類(lèi)，算法如下： 選取距離閾值T，并且任取一個(gè)樣本作為第一個(gè)聚類(lèi)中心Z1，如： 。 計(jì)算樣本 到Z1的距離D21： 若 ，則 ，否則令 為第二個(gè)聚合中心， 。第39頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四采用最近鄰規(guī)則的聚類(lèi)算法（續(xù)）設(shè) ，計(jì)算 到 Z1和Z2的距離D31和D32，若 D

16、31 T和D32 T ，則建立第三個(gè)聚合中心。否則把 歸于最近鄰的聚合中心。依此類(lèi)推，直到把所有樣本都進(jìn)行分類(lèi)。 按照某種聚類(lèi)準(zhǔn)則考察聚類(lèi)結(jié)果，若不滿意，則重新選取距離閾值T、第一個(gè)聚合中心Z1 ，返回，直到滿意，算法結(jié)束。第40頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四在樣本分布一定時(shí)，該算法的結(jié)果在很大程度上取決于第一個(gè)聚合中心的選取和距離閾值的大小。該算法的優(yōu)點(diǎn)是簡(jiǎn)單，如果有樣本分布的先驗(yàn)知識(shí)用于指導(dǎo)閾值和起始點(diǎn)的選取，則可較快得到合理結(jié)果。對(duì)于高維的樣本集來(lái)說(shuō)，則只有經(jīng)過(guò)多次試探，并對(duì)聚類(lèi)結(jié)果進(jìn)行驗(yàn)算，從而選擇最優(yōu)的聚類(lèi)結(jié)果。采用最近鄰規(guī)則的聚類(lèi)算法（續(xù)）第41頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四2最大最小距離聚類(lèi)算法該算法以歐氏距離為基礎(chǔ)，除首先辨識(shí)最遠(yuǎn)的聚類(lèi)中心外，與上述算法相似。用一個(gè)例子說(shuō)明該算法。第42頁(yè)，共48頁(yè)，2022年，5月20日，6點(diǎn)30分，星期四例：樣本分布如圖所示。第43頁(yè)，共4