模式識(shí)別聚類續(xù)

模式識(shí)別聚類續(xù)第一頁，共七十七頁，2022年，8月28日兩種簡單的聚類算法第二頁，共七十七頁，2022年，8月28日兩種簡單的聚類算法（續(xù)）2．最大最小距離聚類算法例：樣本分布如圖所示。第三頁，共七十七頁，2022年，8月28日第四頁，共七十七頁，2022年，8月28日第五頁，共七十七頁，2022年，8月28日系統(tǒng)聚類系統(tǒng)聚類：先把每個(gè)樣本作為一類，然后根據(jù)它們間的相似性和相鄰性聚合。相似性、相鄰性一般用距離表示（1）兩類間的距離1、最短距離：兩類中相距最近的兩樣本間的距離。第六頁，共七十七頁，2022年，8月28日2、最長距離：兩類中相距最遠(yuǎn)的兩個(gè)樣本間的距離。3、中間距離：最短距離和最長距離都有片面性，因此有時(shí)用中間距離。設(shè)ω1類和ω23類間的最短距離為d12，最長距離為d13，ω

23類的長度為d23，則中間距離為d0

：第七頁，共七十七頁，2022年，8月28日4、重心距離：均值間的距離5、類平均距離：兩類中各個(gè)元素兩兩之間的距離平方相加后取平均值第八頁，共七十七頁，2022年，8月28日6、離差平方和：設(shè)N個(gè)樣品原分q類，則定義第i類的離差平方和為：離差平方和增量：設(shè)樣本已分成ωp,ωq兩類，若把ωp,ωq合為ωr類，則定義離差平方：第九頁，共七十七頁，2022年，8月28日（2）系統(tǒng)聚類的算法首先將m個(gè)樣品自成一類，然后每次將具有最小距離的兩類合并，合并后重新計(jì)算類與類之間的距離，這個(gè)過程一直繼續(xù)到所有樣品歸為一類為止。

例：如下圖所示1、設(shè)全部樣本分為6類，第十頁，共七十七頁，2022年，8月28日ω1ω2ω3ω4ω5ω29ω3116ω4491664ω5254364ω6642581192、作距離矩陣D(0)第十一頁，共七十七頁，2022年，8月28日3、求最小元素：4、把ω1,ω3合并ω7=(1,3)ω4,ω6合并ω8=(4,6)5、作距離矩陣D(1)ω7ω2ω8ω29ω84916ω52544第十二頁，共七十七頁，2022年，8月28日6、若合并的類數(shù)沒有達(dá)到要求，轉(zhuǎn)3。否則停止。3、求最小元素：4、ω8,ω5,ω2合并,ω9=（2,5,4,6）第十三頁，共七十七頁，2022年，8月28日分解聚類分解聚類：把全部樣本作為一類，然后根據(jù)相似性、相鄰性分解。目標(biāo)函數(shù)兩類均值方差

N：總樣本數(shù)，：ω1類樣本數(shù)：ω2類樣本數(shù)，第十四頁，共七十七頁，2022年，8月28日分解聚類框圖：初始分類調(diào)整分類方案最終結(jié)果目標(biāo)函數(shù)達(dá)到最優(yōu)？第十五頁，共七十七頁，2022年，8月28日對分算法：略例：已知21個(gè)樣本，每個(gè)樣本取二個(gè)特征，原始資料矩陣如下表：

樣本號(hào)12345678910x10022445667x265534312101112131415161718192021-4-2-3-3-5100-1-1-3322021-1-2-1-3-5第十六頁，共七十七頁，2022年，8月28日第十七頁，共七十七頁，2022年，8月28日∴目標(biāo)函數(shù)∴解：第一次分類時(shí)計(jì)算所有樣本，分別劃到時(shí)的E值，找出最大的。1、開始時(shí)，第十八頁，共七十七頁，2022年，8月28日

2、分別計(jì)算當(dāng)劃入時(shí)的E值把劃入時(shí)有第十九頁，共七十七頁，2022年，8月28日然后再把劃入時(shí)對應(yīng)的E值，找出一個(gè)最大的E值。把劃為的E值最大。∴

E(1)=56.6再繼續(xù)進(jìn)行第二，第三次迭代…計(jì)算出E(2),E(3),…第二十頁，共七十七頁，2022年，8月28日次數(shù)E值

156.6279.16390.904102.615120.116137.157154.108176.159195.2610213.0711212.01第二十一頁，共七十七頁，2022年，8月28日第10次迭代劃入時(shí)，E最大。于是分成以下兩類：∴每次分類后要重新計(jì)算的值。可用以下遞推公式：第二十二頁，共七十七頁，2022年，8月28日動(dòng)態(tài)聚類——兼顧系統(tǒng)聚類和分解聚類一、動(dòng)態(tài)聚類的方法概要①先選定某種距離作為樣本間的相似性的度量;②確定評價(jià)聚類結(jié)果的準(zhǔn)則函數(shù);③給出某種初始分類，用迭代法找出使準(zhǔn)則函數(shù)取極值的最好的聚類結(jié)果。第二十三頁，共七十七頁，2022年，8月28日

二、代表點(diǎn)的選取方法：代表點(diǎn)就是初始分類的聚類中心數(shù)k

①憑經(jīng)驗(yàn)選代表點(diǎn)，根據(jù)問題的性質(zhì)、數(shù)據(jù)分布，從直觀上看來較合理的代表點(diǎn)k;②將全部樣本隨機(jī)分成k類，計(jì)算每類重心，把這些重心作為每類的代表點(diǎn);

第二十四頁，共七十七頁，2022年，8月28日③按密度大小選代表點(diǎn)：

以每個(gè)樣本作為球心，以d為半徑做球形;落在球內(nèi)的樣本數(shù)稱為該點(diǎn)的密度，并按密度大小排序。首先選密度最大的作為第一個(gè)代表點(diǎn)，即第一個(gè)聚類中心。再考慮第二大密度點(diǎn)，若第二大密度點(diǎn)距第一代表點(diǎn)的距離大于d1（人為規(guī)定的正數(shù)）則把第二大密度點(diǎn)作為第二代表點(diǎn)，，否則不能作為代表點(diǎn)，這樣按密度大小考察下去，所選代表點(diǎn)間的距離都大于d1。d1太小，代表點(diǎn)太多，d1太大，代表點(diǎn)太小，一般選d1＝2d。對代表點(diǎn)內(nèi)的密度一般要求大于T。T>0為規(guī)定的一個(gè)正數(shù)。④用前k個(gè)樣本點(diǎn)作為代表點(diǎn)。第二十五頁，共七十七頁，2022年，8月28日三、初始分類和調(diào)整

①選一批代表點(diǎn)后，代表點(diǎn)就是聚類中心，計(jì)算其它樣本到聚類中心的距離，把所有樣本歸于最近的聚類中心點(diǎn)，形成初始分類，再重新計(jì)算各聚類中心，稱為成批處理法。②選一批代表點(diǎn)后,依次計(jì)算其它樣本的歸類，當(dāng)計(jì)算完第一個(gè)樣本時(shí)，把它歸于最近的一類，形成新的分類。再計(jì)算新的聚類中心，再計(jì)算第二個(gè)樣本到新的聚類中心的距離，對第二個(gè)樣本歸類。即每個(gè)樣本的歸類都改變一次聚類中心。此法稱為逐個(gè)處理法。③直接用樣本進(jìn)行初始分類，先規(guī)定距離d,把第一個(gè)樣本作為第一類的聚類中心，考察第二個(gè)樣本，若第二個(gè)樣本距第一個(gè)聚類中心距離小于d，就把第二個(gè)樣本歸于第一類，否則第二個(gè)樣本就成為第二類的聚類中心，再考慮其它樣本，根據(jù)樣本到聚類中心距離大于還是小于d，決定分裂還是合并。

第二十六頁，共七十七頁，2022年，8月28日最佳初始分類。如圖所示，隨著初始分類k的增大，準(zhǔn)則函數(shù)下降很快，經(jīng)過拐點(diǎn)A后，下降速度減慢。拐點(diǎn)A就是最佳初始分類。第二十七頁，共七十七頁，2022年，8月28日1．C－均值聚類算法聚類準(zhǔn)則函數(shù)是誤差平方和準(zhǔn)則：

四、c－均值與ISODATA聚類算法第二十八頁，共七十七頁，2022年，8月28日算法特點(diǎn)：①每次迭代中都要考查每個(gè)樣本的分類是否正確，若不正確，就要調(diào)整，在全部樣本調(diào)整完之后，再修改聚合中心，進(jìn)入下一次迭代。如果在某一個(gè)迭代運(yùn)算中，所有的樣本都被正確分類，則樣本不會(huì)調(diào)整，聚合中心也不會(huì)有變化，也就是收斂了。②c個(gè)初始聚合中心的選擇對聚類結(jié)果有較大影響。第二十九頁，共七十七頁，2022年，8月28日第三十頁，共七十七頁，2022年，8月28日第三十一頁，共七十七頁，2022年，8月28日第三十二頁，共七十七頁，2022年，8月28日④

對每個(gè)聚合中的每個(gè)樣本，計(jì)算：

2)(||)(||1IZxnniikiiii--=r，ci,...2,1=

iir表示cJ減少的部分。

2)(||)(||1IZxnnjikjjij-+=r，cj,...2,1=，ij1

ijr表示cJ增加的部分。

令：}{minijijilrr1=，若iiilrr<，則把樣本)(ikx移到聚合中心lw中，并修改聚合中心和cJ值。

])([11)()1()(ikiiiixIZnIZIZ--+=+

])([11)()1()(iklljlxIZnIZIZ-+-=+

)()()1(iliiccIJIJrr--=+

⑤

判斷：若)()1(IJIJcc<+，則1+=II，返回④。否則，算法結(jié)束。

第三十三頁，共七十七頁，2022年，8月28日第三十四頁，共七十七頁，2022年，8月28日第三十五頁，共七十七頁，2022年，8月28日第三十六頁，共七十七頁，2022年，8月28日J(rèn)c與C的關(guān)系曲線上述C－均值算法，其類型數(shù)目假定已知，為c。對于未知時(shí)，可以令c逐漸增加。使用C－均值算法，誤差平方和Jc隨c的增加而單調(diào)減少。最初，由于c較小，類型的分裂會(huì)使Jc迅速減小，但當(dāng)c增加到一定數(shù)值時(shí)，Jc的減小速度會(huì)減慢，直到c=n時(shí)，Jc

=0。Jc

-C關(guān)系曲線如下圖。第三十七頁，共七十七頁，2022年，8月28日圖中，曲線的拐點(diǎn)A對應(yīng)著接近最優(yōu)的c值。并非所有的情況都容易找到Jc－C關(guān)系曲線的拐點(diǎn)，此時(shí)c值將無法確定。下面介紹一種確定類型數(shù)目c的方法。第三十八頁，共七十七頁，2022年，8月28日2．ISODATA聚類算法ISODATA算法：IterativeSelf-OrganizingDataAnalysisTechniguesAlgorithm，迭代自組織的數(shù)據(jù)分析算法。ISODATA算法特點(diǎn)：可以通過類的自動(dòng)合并（兩類合一）與分裂（一類分為二），得到較合理的類型數(shù)目c。具體算法步驟： ⑴給定控制參數(shù)

k：預(yù)期的聚類中心數(shù)目。四、c－均值與ISODATA聚類算法（續(xù)）第三十九頁，共七十七頁，2022年，8月28日第四十頁，共七十七頁，2022年，8月28日第四十一頁，共七十七頁，2022年，8月28日第四十二頁，共七十七頁，2022年，8月28日第四十三頁，共七十七頁，2022年，8月28日第四十四頁，共七十七頁，2022年，8月28日第四十五頁，共七十七頁，2022年，8月28日第四十六頁，共七十七頁，2022年，8月28日第四十七頁，共七十七頁，2022年，8月28日第四十八頁，共七十七頁，2022年，8月28日第四十九頁，共七十七頁，2022年，8月28日第五十頁，共七十七頁，2022年，8月28日第五十一頁，共七十七頁，2022年，8月28日ISODATA算法中，起始聚合中心的選取對聚類過程和結(jié)果都有較大影響，如果選擇的好，則算法收斂快，聚類質(zhì)量高。注意：ISODATA與C－均值算法的異同點(diǎn)： ①都是動(dòng)態(tài)聚類算法。 ②C－均值簡單，ISODATA復(fù)雜。 ③C－均值中，類型數(shù)目固定，ISODATA中，類型數(shù)目可變。第五十二頁，共七十七頁，2022年，8月28日各類呈橢圓狀分布時(shí)C-均值算法效果不好第五十三頁，共七十七頁，2022年，8月28日五、基于樣本和核相似性度量基于樣本和核相似性度量的聚類算法采用一個(gè)“核”來代表一個(gè)類核Kj可以是一個(gè)函數(shù)，一個(gè)點(diǎn)集，等等樣本和核之間相似性的度量準(zhǔn)則函數(shù)，最小化的目標(biāo)第五十四頁，共七十七頁，2022年，8月28日樣本和核相似性度量的聚類算法（續(xù)）算法步驟類似于C-均值1.選擇初始劃分并計(jì)算初始核2.重新分配各個(gè)樣本3.修正核，并重復(fù)2-3直至收斂C-均值算法=以類均值為核，歐氏距離作為樣本和核之間的相似性度量第五十五頁，共七十七頁，2022年，8月28日樣本和核相似性度量的聚類算法（續(xù)）算法收斂的充分條件：準(zhǔn)則函數(shù)J滿足Γ，K修正之前的分類和對應(yīng)的核，修正之后的分類和對應(yīng)的第五十六頁，共七十七頁，2022年，8月28日樣本和核相似性度量的聚類算法（續(xù)）正態(tài)核函數(shù)，適用于各類為正態(tài)分布參數(shù)集從各類樣本中估計(jì)相似性度量第五十七頁，共七十七頁，2022年，8月28日樣本和核相似性度量的聚類算法（續(xù)）主軸核函數(shù)，適用于各類樣本集中在各自的主軸方向上的子空間里的情況是第j類樣本協(xié)方差陣的前個(gè)最大特征值對應(yīng)的特征向量系統(tǒng)是樣本到主軸子空間的距離第五十八頁，共七十七頁，2022年，8月28日樣本和核相似性度量的聚類算法（續(xù)）可以擬合各種形狀的分布需要預(yù)先知道數(shù)據(jù)的分布形狀第五十九頁，共七十七頁，2022年，8月28日第六十頁，共七十七頁，2022年，8月28日六、近鄰函數(shù)準(zhǔn)則近鄰函數(shù)準(zhǔn)則算法近鄰函數(shù)：樣本間相似性的度量 如果yi是yj的第I個(gè)近鄰，yj是yi的第K個(gè)近鄰近鄰函數(shù)使得密度相近的點(diǎn)容易聚成一類第六十一頁，共七十七頁，2022年，8月28日近鄰函數(shù)準(zhǔn)則算法（續(xù)）純粹按照歐氏距離，則黃色點(diǎn)歸為第一類按照近鄰函數(shù)值，黃色點(diǎn)歸為第二類。這是比較合理的第六十二頁，共七十七頁，2022年，8月28日近鄰函數(shù)準(zhǔn)則算法（續(xù)）同一類中的點(diǎn)之間存在“連接”。連接損失就定義為兩點(diǎn)之間的近鄰函數(shù)αij。一個(gè)點(diǎn)和其自身的連接損失定義為αii=2N，以懲罰只有一個(gè)點(diǎn)的聚類不同類的點(diǎn)不存在連接，連接損失為αij=0總類內(nèi)損失第六十三頁，共七十七頁，2022年，8月28日近鄰函數(shù)準(zhǔn)則算法（續(xù)）第i類和第j類之間的最小近鄰函數(shù)值定義為第i類內(nèi)最大連接損失記為αimax第i類與第j類之間的連接損失定義為βij,第六十四頁，共七十七頁，2022年，8月28日近鄰函數(shù)準(zhǔn)則算法（續(xù)）βij的設(shè)計(jì)目標(biāo)是：如果兩類間的最小近鄰值大于任何一方的類內(nèi)的最大連接損失時(shí)，損失代價(jià)就是正的，從而應(yīng)該考慮把這兩類合并第六十五頁，共七十七頁，2022年，8月28日近鄰函數(shù)準(zhǔn)則算法（續(xù)）總類間損失準(zhǔn)則函數(shù)第六十六頁，共七十七頁，2022年，8月28日近鄰函數(shù)準(zhǔn)則算法（續(xù)）算法步驟1.計(jì)算距離矩陣2.用距離矩陣計(jì)算近鄰矩陣Mij，Mij表示yj是yi的第幾個(gè)近鄰3.計(jì)算近鄰函數(shù)矩陣Lij=Mij+Mji-2I,Lii=2N4.在L中，每個(gè)點(diǎn)與其最近鄰連接，形成初始的劃分5.對每兩個(gè)類計(jì)算γij

和αimax，αjmax

，只要γij

小于αimax、αjmax中的任何一個(gè)，就合并兩類（建立連接）。重復(fù)至沒有新的連接發(fā)生為止第六十七頁，共七十七頁，2022年，8月28日例：如圖所示樣本，使用近鄰函數(shù)準(zhǔn)則聚類。解：①計(jì)算D矩陣，結(jié)果從簡；②計(jì)算M矩氏，結(jié)果從簡；③計(jì)算L矩陣，結(jié)果見表第六十八頁，共七十七頁，2022年，8月28日L123456789101112124138486916171719212403811111417171818330241101391215161817483124710610141615115481072400413141617681113100244081814167611960424061213158914121040024481214916171514138642413610171716161418128124031117181815161413123024112191817111716151563124第六十九頁，共七十七頁，2022年，8月28日第七十頁，共七十七頁，2022年，8月28日最小張樹聚類術(shù)語：①線段：兩個(gè)模式樣本點(diǎn)的連線②路徑：連接兩點(diǎn)的線段序列③回路：閉合路徑④連通圖形：任兩點(diǎn)之間有一條或一條以上的路徑者。（即各點(diǎn)之間是