模式識別聚類

模式識別聚類第1頁，共48頁，2023年，2月20日，星期五什么是聚類聚類是一種無監(jiān)督分類法:沒有預(yù)先指定的類別分類：用已知類別的樣本訓(xùn)練集來設(shè)計分類器（監(jiān)督學(xué)習(xí)）聚類：用事先不知類別的樣本，利用樣本的先驗知識來構(gòu)造分類器（無監(jiān)督學(xué)習(xí)）聚類分析無訓(xùn)練過程，訓(xùn)練與識別混合在一起。

第2頁，共48頁，2023年，2月20日，星期五相似性度量設(shè)有樣本集，要求按某種相似性把分類，怎樣實現(xiàn)？聚類分析符合“物以類聚，人以群分“的原則，它把相似性大的樣本聚集為一個類型，在特征空間里占據(jù)著一個局部區(qū)域。每個局部區(qū)域都形成一個聚合中心，聚合中心代表相應(yīng)類型。第3頁，共48頁，2023年，2月20日，星期五如下圖中，(a)有一個聚合中心，(b)、(c)有兩個。第4頁，共48頁，2023年，2月20日，星期五聚類分析避免了估計類概率密度的困難，對每個聚合中心來說都是局部密度極大值位置，其附近密度高，距離越遠(yuǎn)密度越小。聚類分析的關(guān)鍵問題：如何在聚類過程中自動地確定類型數(shù)目c。實際工作中，也可以給定值作為算法終止的條件。第5頁，共48頁，2023年，2月20日，星期五聚類分析的結(jié)果與特征的選取有很大的關(guān)系。不同的特征，分類的結(jié)果不同。第6頁，共48頁，2023年，2月20日，星期五1.距離相似性度量一個模式樣本，對應(yīng)特征空間里的一個點。如果模式的特征是適當(dāng)選擇的，也就是各維特征對于分類來說都是有效的，那么同類樣本就會密集地分布在一個區(qū)域里，不同類的模式樣本就會遠(yuǎn)離。因此，點間距離遠(yuǎn)近反映了相應(yīng)模式樣本所屬類型有無差異，可以作為樣本相似性度量。距離越近，相似性越大，屬于一個類型。聚類分析中，最常用的就是距離相似性。第7頁，共48頁，2023年，2月20日，星期五（1）歐氏距離歐氏距離簡稱距離，模式樣本向量x與y之間的歐氏距離定義為：

d為特征空間的維數(shù)。

當(dāng)較小時，表示x與y在一個類型區(qū)域，反之，則不在一個類型區(qū)域。這里有一個門限的選擇問題。若選擇過大，則全部樣本被視作一個唯一類型；若選取過小，則可能造成每個樣本都單獨構(gòu)成一個類型。必須正確選擇門限值以保證正確分類。

第8頁，共48頁，2023年，2月20日，星期五（1）歐氏距離（續(xù)）另外，模式特征坐標(biāo)單位的選取也會強(qiáng)烈地影響聚類結(jié)果。例如：一個二維模式，一個特征是長度，另一個特征是壓力。當(dāng)長度由厘米變?yōu)槊?，在中長度特征的比重會下降，同樣，若把比重單位由毫米汞柱高度變成厘米汞柱高度，中壓力特征的影響也會下降。第9頁，共48頁，2023年，2月20日，星期五（1）歐氏距離（續(xù)）可以用圖表示上述情況：從上圖看出，(b)、(c)特征空間劃分是不同的。(b)中為一類，為另一類，(c)中為一類，為另一類。第10頁，共48頁，2023年，2月20日，星期五（1）歐氏距離（續(xù)）另外，使用歐氏距離度量時，還要注意模式樣本測量值的選取，應(yīng)該是有效反映類別屬性特征（各類屬性的代表應(yīng)均衡）。但馬氏距離可解決不均衡（一個多，一個少）的問題。例如，取5個樣本，其中有4個反映對分類有意義的特征A，只有1個對分類有意義的特征B，歐氏距離的計算結(jié)果，則主要體現(xiàn)特征A。第11頁，共48頁，2023年，2月20日，星期五（2）馬氏（Mahalanobis）距離定義：馬氏距離的平方其中，為均值向量，為協(xié)方差矩陣。馬氏距離排除了不同特征之間相關(guān)性的影響，其關(guān)鍵在于協(xié)方差矩陣的計算。當(dāng)為對角陣時，各特征之間才完全獨立；當(dāng)為單位矩陣時，馬氏距離等于歐氏距離。馬氏距離比較適用于對樣本已有初步分類的情況，做進(jìn)一步考核、修正。第12頁，共48頁，2023年，2月20日，星期五（3）明氏（Minkowsky）距離定義：明氏距離:它是若干距離函數(shù)的通式：時，等于歐氏距離；時，稱為“街坊”（cityblock）距離。第13頁，共48頁，2023年，2月20日，星期五2.角度相似性度量樣本x與y之間的角度相似性度量定義為它們之間夾角的余弦，即

也是單位向量之間的點積（內(nèi)積）。

越大，x與y越相似。常用于情報檢索、植物分類、疾病分類。第14頁，共48頁，2023年，2月20日，星期五2.角度相似性度量滿足：①②當(dāng)時，達(dá)到最大。對于坐標(biāo)系的旋轉(zhuǎn)及放大、縮小是不變的量，但對位移和一般性的線性變換不是不變的。樣本與核的相似性度量近鄰函數(shù)值相等第15頁，共48頁，2023年，2月20日，星期五樣本相似性度量是聚類分析的基礎(chǔ)，針對具體問題，選擇適當(dāng)?shù)南嗨菩远攘渴潜ＷC聚類質(zhì)量的重要問題。但有了相似性度量還不夠，還必須有適當(dāng)?shù)木垲悳?zhǔn)則函數(shù)。聚類準(zhǔn)則函數(shù)對聚類質(zhì)量也有重大影響。相似性度量→集合與集合的相似性。相似性準(zhǔn)則→分類效果好壞的評價準(zhǔn)則

第16頁，共48頁，2023年，2月20日，星期五聚類準(zhǔn)則函數(shù)在樣本相似性度量的基礎(chǔ)上，聚類分析還需要一定的準(zhǔn)則函數(shù)，才能把真正屬于同一類的樣本聚合成一個類型的子集，而把不同類的樣本分離開來。如果聚類準(zhǔn)則函數(shù)選得好，聚類質(zhì)量就會高。第17頁，共48頁，2023年，2月20日，星期五聚類準(zhǔn)則函數(shù)同時，聚類準(zhǔn)則函數(shù)還可以用來評價一種聚類結(jié)果的質(zhì)量，如果聚類質(zhì)量不滿足要求，就要重復(fù)執(zhí)行聚類過程，以優(yōu)化結(jié)果。在重復(fù)優(yōu)化中，可以改變相似性度量，也可以選用新的聚類準(zhǔn)則。第18頁，共48頁，2023年，2月20日，星期五1．誤差平方和準(zhǔn)則（最常用的）假定有混合樣本，采用某種相似性度量，被聚合成c個分離開的子集，每個子集是一個類型，它們分別包含個樣本。為了衡量聚類的質(zhì)量，采用誤差平方和聚類準(zhǔn)則函數(shù)，定義為：mj是個集合的中心，可以用來代表c個類型。第19頁，共48頁，2023年，2月20日，星期五誤差平方和準(zhǔn)則（續(xù)）是樣本和集合中心的函數(shù)。在樣本集X給定的情況下，的取值取決于c個集合中心。描述個n試驗樣本聚合成c個類型時，所產(chǎn)生的總誤差平方和。越小越好。

第20頁，共48頁，2023年，2月20日，星期五誤差平方和準(zhǔn)則（續(xù)）誤差平方和準(zhǔn)則適用于各類樣本比較密集且樣本數(shù)目懸殊不大的樣本分布。例如：上圖的樣本分布，共有3個類型，各個類型的樣本數(shù)目相差不多（10個左右）。類內(nèi)較密集，誤差平方和很小，類別之間距離遠(yuǎn)。第21頁，共48頁，2023年，2月20日，星期五誤差平方和準(zhǔn)則（續(xù)）注意：如果不同類型的樣本數(shù)目相差很大，采用誤差平方和準(zhǔn)則，有可能把樣本數(shù)目多的類型分開，以便達(dá)到總的最小。如下圖所示：第22頁，共48頁，2023年，2月20日，星期五誤差平方和準(zhǔn)則（續(xù)）下面進(jìn)一步說明上述問題：例如：有5個樣本，如下圖所示～第23頁，共48頁，2023年，2月20日，星期五誤差平方和準(zhǔn)則（續(xù)）虛線為正確類型區(qū)分域，實線為采用誤差平方和最小準(zhǔn)則時的類別區(qū)分。虛線劃分時：第24頁，共48頁，2023年，2月20日，星期五誤差平方和準(zhǔn)則（續(xù)）實線劃分時：所以，如果按誤差平方和準(zhǔn)則聚類將得到錯誤結(jié)果。第25頁，共48頁，2023年，2月20日，星期五2．加權(quán)平均平方距離和準(zhǔn)則定義：加權(quán)平均平方距離和準(zhǔn)則式中：是類內(nèi)樣本間平均平方距離，即所有的樣本之間距離的平均值

。第26頁，共48頁，2023年，2月20日，星期五加權(quán)平均平方距離和準(zhǔn)則（續(xù)）為類的先驗概率，可以用樣本數(shù)目和樣本總數(shù)目來估計因此：

第27頁，共48頁，2023年，2月20日，星期五加權(quán)平均平方距離和準(zhǔn)則（續(xù)）用重新討論誤差平方和準(zhǔn)則中所舉例子。5個樣本，如圖所示。第28頁，共48頁，2023年，2月20日，星期五第29頁，共48頁，2023年，2月20日，星期五加權(quán)平均平方距離和準(zhǔn)則（續(xù)）雖然，但已較接近。所以，當(dāng)各類樣本數(shù)目相差懸殊時，使用加權(quán)平均平方距離和準(zhǔn)則，要比使用誤差平方和準(zhǔn)則容易得到正確聚類結(jié)果。同一樣，越小，樣本類內(nèi)越密集。以聚合中心為極大值的局部區(qū)域密度越高，聚類結(jié)果越好。第30頁，共48頁，2023年，2月20日，星期五3．類間距離和準(zhǔn)則類間距離和可用于描述聚類結(jié)果的類間距離分布狀態(tài)。它定義為：加權(quán)類間距離和：

式中，第31頁，共48頁，2023年，2月20日，星期五類間距離和準(zhǔn)則（續(xù)）對于兩類問題，類間距離常用下式計算類間距離和準(zhǔn)則描述不同類型之間的分離程度，所以值越大，表示各類之間分離性好，聚類質(zhì)量高。

第32頁，共48頁，2023年，2月20日，星期五4．散射矩陣為了對聚類質(zhì)量有一個全面的描述和考核標(biāo)準(zhǔn)，可以通過散射矩陣引導(dǎo)出一些準(zhǔn)則函數(shù)，它們不但反映同類樣本的聚集程度，而且也反映不同類之間的分離程度。

第33頁，共48頁，2023年，2月20日，星期五散射矩陣（續(xù)）假定混合樣本集X的n個樣本被聚集成c個類型的子集Xj，每個子集有nj個樣本，則類內(nèi)散射矩陣定義為：其中為某一個類型的類內(nèi)散射矩陣：第34頁，共48頁，2023年，2月20日，星期五散射矩陣（續(xù)）類間散射矩陣定義為：

式中，為各類型的均值向量，為全部樣本的均值向量，()為各類型先驗概率。

第35頁，共48頁，2023年，2月20日，星期五定義全部樣本的總散射矩陣為：上述3個散射矩陣有如下關(guān)系：這一結(jié)果表明，對于給定的混合樣本集，類內(nèi)散射的減少，將導(dǎo)致類間散射的增加。對某一聚類結(jié)果，類內(nèi)散射越小越好，類間散射越大越好。

第36頁，共48頁，2023年，2月20日，星期五利用、、可以定義如下的4個聚類準(zhǔn)則：表示矩陣的跡，也就是對角線元素之和，||為行列式。J1～J4同時考慮了類內(nèi)的散射和類間散射，為了得到好的聚類結(jié)果，它們的值越大越好。第37頁，共48頁，2023年，2月20日，星期五兩種簡單的聚類算法

介紹兩種簡單的聚類分析方法，它是對某些關(guān)鍵性的元素進(jìn)行試探性的選取，使某種聚類準(zhǔn)則達(dá)到最優(yōu)，又稱為基于試探的聚類算法。采用最近鄰規(guī)則的聚類算法

最大最小距離聚類算法第38頁，共48頁，2023年，2月20日，星期五1．采用最近鄰規(guī)則的聚類算法假設(shè)已有混合樣本集，按照最近鄰原則進(jìn)行聚類，算法如下：①選取距離閾值T，并且任取一個樣本作為第一個聚類中心Z1，如：。②計算樣本到Z1的距離D21：若，則，否則令為第二個聚合中心，。第39頁，共48頁，2023年，2月20日，星期五采用最近鄰規(guī)則的聚類算法（續(xù)）設(shè)，計算到Z1和Z2的距離D31和D32，若D31>T和D32>T

，則建立第三個聚合中心。否則把歸于最近鄰的聚合中心。依此類推，直到把所有樣本都進(jìn)行分類。③按照某種聚類準(zhǔn)則考察聚類結(jié)果，若不滿意，則重新選取距離閾值T、第一個聚合中心Z1

，返回②，直到滿意，算法結(jié)束。第40頁，共48頁，2023年，2月20日，星期五在樣本分布一定時，該算法的結(jié)果在很大程度上取決于第一個聚合中心的選取和距離閾值的大小。該算法的優(yōu)點是簡單，如果有樣本分布的先驗知識用于指導(dǎo)閾值和起始點的選取，則可較快得到合理結(jié)果。對于高維的樣本集來說，則只有經(jīng)過多次試探，并對聚類結(jié)果進(jìn)行驗算，從而選擇最優(yōu)的聚類結(jié)果。采用最近鄰規(guī)則的聚類算法（續(xù)）第41頁，共48頁，2023年，2月20日，星期五2．最大最小距離聚類算法該算法以歐氏距離為基礎(chǔ)，除首先辨識最遠(yuǎn)的聚類中心外，與上述算法相似。用一個例子說明該算法。第42