模式識別聚類續(xù)

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

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

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

例：如下圖所示1、設全部樣本分為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ù)沒有達到要求，轉(zhuǎn)3。否則停止。3、求最小元素：4、ω8,ω5,ω2合并,ω9=（2,5,4,6）第十三頁，共七十七頁，2022年，8月28日分解聚類分解聚類：把全部樣本作為一類，然后根據(jù)相似性、相鄰性分解。目標函數(shù)兩類均值方差

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

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

2、分別計算當劃入時的E值把劃入時有第十九頁，共七十七頁，2022年，8月28日然后再把劃入時對應的E值，找出一個最大的E值。把劃為的E值最大。∴

E(1)=56.6再繼續(xù)進行第二，第三次迭代…計算出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次迭代劃入時，E最大。于是分成以下兩類：∴每次分類后要重新計算的值?？捎靡韵逻f推公式：第二十二頁，共七十七頁，2022年，8月28日動態(tài)聚類——兼顧系統(tǒng)聚類和分解聚類一、動態(tài)聚類的方法概要①先選定某種距離作為樣本間的相似性的度量;②確定評價聚類結(jié)果的準則函數(shù);③給出某種初始分類，用迭代法找出使準則函數(shù)取極值的最好的聚類結(jié)果。第二十三頁，共七十七頁，2022年，8月28日

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

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

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

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

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

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

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

對每個聚合中的每個樣本，計算：

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日Jc與C的關(guān)系曲線上述C－均值算法，其類型數(shù)目假定已知，為c。對于未知時，可以令c逐漸增加。使用C－均值算法，誤差平方和Jc隨c的增加而單調(diào)減少。最初，由于c較小，類型的分裂會使Jc迅速減小，但當c增加到一定數(shù)值時，Jc的減小速度會減慢，直到c=n時，Jc

=0。Jc

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

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

和αimax，αjmax

，只要γij

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