兩種簡(jiǎn)單的聚類算法

1、兩種簡(jiǎn)單的聚類算法,介紹兩種簡(jiǎn)單的聚類分析方法，它是對(duì)某些關(guān)鍵性的元素進(jìn)行試探性的選取，使某種聚類準(zhǔn)則達(dá)到最優(yōu)，又稱為基于試探的聚類算法。采用最近鄰規(guī)則的聚類算法 最大最小距離聚類算法,兩種簡(jiǎn)單的聚類算法,兩種簡(jiǎn)單的聚類算法（續(xù)）,2．最大最小距離聚類算法例：樣本分布如圖所示。,,系統(tǒng)聚類,系統(tǒng)聚類：先把每個(gè)樣本作為一類，然后根據(jù)它們間的相似性和相鄰性聚合。相似性、相鄰性一般用距離表示（1）兩類間的距離1、最短距離：兩類中相

2、距最近的兩樣本間的距離。,2、最長(zhǎng)距離 ：兩類中相距最遠(yuǎn)的兩個(gè)樣本間的距離。 3、中間距離：最短距離和最長(zhǎng)距離都有片面性，因此有時(shí)用中間距離。設(shè)ω1類和ω23類間的最短距離為d12，最長(zhǎng)距離為d13，ω 23類的長(zhǎng)度為d23，則中間距離為d0 ：,4、重心距離：均值間的距離5、類平均距離：兩類中各個(gè)元素兩兩之間的距離平方相加后取平均值,6、 離差平方和：設(shè)N個(gè)樣品原分q類，則定義第i類的離差平方和為：離差平方和增

3、量：設(shè)樣本已分成ωp,ωq兩類，若把ωp,ωq合為ωr類，則定義離差平方：,（2）系統(tǒng)聚類的算法 首先將m個(gè)樣品自成一類，然后每次將具有最小距離的兩類合并，合并后重新計(jì)算類與類之間的距離，這個(gè)過(guò)程一直繼續(xù)到所有樣品歸為一類為止。 例：如下圖所示 1、設(shè)全部樣本分為6類，,2、作距離矩陣D(0),3、求最小元素：4、把ω1,ω3合并ω7=(1,3)ω4,ω6合并ω8=(4,6)5、作距離矩陣D(1),6、若合并的類

4、數(shù)沒(méi)有達(dá)到要求，轉(zhuǎn)3。否則停止。3、求最小元素： 4、ω8,ω5,ω2合并, ω9=（2,5,4,6）,分解聚類,分解聚類：把全部樣本作為一類，然后根據(jù)相似性、相鄰性分解。目標(biāo)函數(shù) 兩類均值方差,N：總樣本數(shù)， ：ω1類樣本數(shù) ：ω2類樣本數(shù)，,分解聚類框圖：,對(duì)分算法：略 例：已知21個(gè)樣本，每個(gè)樣本取二個(gè)特征，原始資料矩陣如下表：,解：第一次分類時(shí)計(jì)算所有樣本，分別劃到,時(shí)的E值，找出

5、最大的。1、開(kāi)始時(shí)，,2、分別計(jì)算當(dāng) 劃入,時(shí)的E值,把 劃入,時(shí)有,然后再把 劃入 時(shí)對(duì)應(yīng)的E值，找出一個(gè)最大的E值。 把 劃為 的E值最大?！?E(1)=56.6,再繼續(xù)進(jìn)行第二，第三次迭代…計(jì)算出 E(2) , E(3) , …,次數(shù)

6、 E值 1 56.6 2 79.16 3 90.90

7、 4 102.61 5 120.11 6 137.15 7

8、 154.10 8 176.15 9 195.26 10 213

9、.07 11 212.01,,,第10次迭代 劃入 時(shí)，E最大。于是分成以下兩類：∴,每次分類后要重新計(jì)算 的值?？捎靡韵逻f推公式：,,,,動(dòng)態(tài)聚類——兼顧系統(tǒng)聚類和分解聚類,一、動(dòng)態(tài)聚類的方法概要 ① 先選定某種距離作為樣本間的相似性的度量; ② 確定評(píng)價(jià)聚類結(jié)果的準(zhǔn)

10、則函數(shù); ③ 給出某種初始分類，用迭代法找出使準(zhǔn)則函數(shù)取極值的最好的聚類結(jié)果。,二、代表點(diǎn)的選取方法：代表點(diǎn)就是初始分類的聚類中心數(shù)k ① 憑經(jīng)驗(yàn)選代表點(diǎn)，根據(jù)問(wèn)題的性質(zhì)、數(shù)據(jù)分布，從直觀上看來(lái)較合理的代表點(diǎn)k; ②將全部樣本隨機(jī)分成k類，計(jì)算每類重心，把這些重心作為每類的代表點(diǎn);,③ 按密度大小選代表點(diǎn)： 以每個(gè)樣本作為球心，以d為半徑做球形;落在球內(nèi)的樣本數(shù)稱為該點(diǎn)的密度，并按密度大小排序。首

11、先選密度最大的作為第一個(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。對(duì)代表點(diǎn)內(nèi)的密度一般要求大于T。T>0為規(guī)定的一個(gè)正數(shù)。④ 用前k個(gè)樣本點(diǎn)作為代表點(diǎn)。,三、初始分類和調(diào)整 ① 選一批

12、代表點(diǎn)后，代表點(diǎn)就是聚類中心，計(jì)算其它樣本到聚類中心的距離，把所有樣本歸于最近的聚類中心點(diǎn)，形成初始分類，再重新計(jì)算各聚類中心，稱為成批處理法。 ② 選一批代表點(diǎn)后,依次計(jì)算其它樣本的歸類，當(dāng)計(jì)算完第一個(gè)樣本時(shí)，把它歸于最近的一類，形成新的分類。再計(jì)算新的聚類中心，再計(jì)算第二個(gè)樣本到新的聚類中心的距離，對(duì)第二個(gè)樣本歸類。即每個(gè)樣本的歸類都改變一次聚類中心。此法稱為逐個(gè)處理法。 ③ 直接用樣本進(jìn)行初始分類，

13、先規(guī)定距離d, 把第一個(gè)樣本作為第一類的聚類中心，考察第二個(gè)樣本，若第二個(gè)樣本距第一個(gè)聚類中心距離小于d，就把第二個(gè)樣本歸于第一類，否則第二個(gè)樣本就成為第二類的聚類中心，再考慮其它樣本，根據(jù)樣本到聚類中心距離大于還是小于d，決定分裂還是合并。,最佳初始分類。 如圖所示，隨著初始分類k的增大，準(zhǔn)則函數(shù)下降很快，經(jīng)過(guò)拐點(diǎn)A后，下降速度減慢。拐點(diǎn)A就是最佳初始分類。,1．C－均值聚類算法聚類準(zhǔn)則函數(shù)是誤差平方和準(zhǔn)則：,四、c

14、－均值與ISODATA聚類算法,,算法特點(diǎn)：① 每次迭代中都要考查每個(gè)樣本的分類是否正確，若不正確，就要調(diào)整，在全部樣本調(diào)整完之后，再修改聚合中心，進(jìn)入下一次迭代。如果在某一個(gè)迭代運(yùn)算中，所有的樣本都被正確分類，則樣本不會(huì)調(diào)整，聚合中心也不會(huì)有變化，也就是收斂了。② c個(gè)初始聚合中心的選擇對(duì)聚類結(jié)果有較大影響。,,,Jc與C的關(guān)系曲線,上述C－均值算法，其類型數(shù)目假定已知，為c。對(duì)于未知時(shí)，可以令c逐漸增加。使用C－均值算法，誤差

15、平方和Jc隨c的增加而單調(diào)減少。最初，由于c較小，類型的分裂會(huì)使 Jc迅速減小，但當(dāng)c增加到一定數(shù)值時(shí)， Jc的減小速度會(huì)減慢，直到c=n時(shí)， Jc =0。 Jc -C關(guān)系曲線如下圖。,圖中，曲線的拐點(diǎn)A對(duì)應(yīng)著接近最優(yōu)的c值。并非所有的情況都容易找到Jc－C關(guān)系曲線的拐點(diǎn)，此時(shí)c值將無(wú)法確定。下面介紹一種確定類型數(shù)目c的方法。,,2．ISODATA聚類算法ISODATA算法：Iterative Self-Organizing Dat

16、a Analysis Technigues Algorithm，迭代自組織的數(shù)據(jù)分析算法。ISODATA算法特點(diǎn)：可以通過(guò)類的自動(dòng)合并（兩類合一）與分裂（一類分為二），得到較合理的類型數(shù)目c。具體算法步驟：⑴ 給定控制參數(shù)k：預(yù)期的聚類中心數(shù)目。,四、c－均值與ISODATA聚類算法（續(xù)）,,,,ISODATA算法中，起始聚合中心的選取對(duì)聚類過(guò)程和結(jié)果都有較大影響，如果選擇的好，則算法收斂快，聚類質(zhì)量高。注意：ISODAT

17、A與C－均值算法的異同點(diǎn)：① 都是動(dòng)態(tài)聚類算法。② C－均值簡(jiǎn)單，ISODATA復(fù)雜。③ C－均值中，類型數(shù)目固定，ISODATA中，類型數(shù)目可變。,各類呈橢圓狀分布時(shí)C-均值算法效果不好,五、基于樣本和核相似性度量,基于樣本和核相似性度量的聚類算法采用一個(gè)“核”來(lái)代表一個(gè)類核Kj可以是一個(gè)函數(shù)，一個(gè)點(diǎn)集，等等樣本和核之間相似性的度量準(zhǔn)則函數(shù)，最小化的目標(biāo),樣本和核相似性度量的聚類算法（續(xù)）算法步驟類似于C-均值

18、1.選擇初始劃分并計(jì)算初始核2.重新分配各個(gè)樣本3.修正核，并重復(fù)2-3直至收斂C-均值算法=以類均值為核，歐氏距離作為樣本和核之間的相似性度量,樣本和核相似性度量的聚類算法（續(xù)）算法收斂的充分條件：準(zhǔn)則函數(shù)J滿足Γ，K修正之前的分類和對(duì)應(yīng)的核 ， 修正之后的分類和對(duì)應(yīng)的,樣本和核相似性度量的聚類算法（續(xù)）􀂄正態(tài)核函數(shù)，適用于各類為正態(tài)分布參數(shù)集

19、 從各類樣本中估計(jì)相似性度量,樣本和核相似性度量的聚類算法（續(xù)）主軸核函數(shù)，適用于各類樣本集中在各自的主軸方向上的子空間里的情況 是第j類樣本協(xié)方差陣的前 個(gè)最大特征值對(duì)應(yīng)的特征向量系統(tǒng) 是樣本到主軸子空間的距離,樣本和核相似性度量的聚類算法（續(xù)）可以擬合各種形狀的分布需要

20、預(yù)先知道數(shù)據(jù)的分布形狀,六、近鄰函數(shù)準(zhǔn)則,近鄰函數(shù)準(zhǔn)則算法近鄰函數(shù)：樣本間相似性的度量如果yi是yj的第I個(gè)近鄰，yj是yi的第K個(gè)近鄰近鄰函數(shù)使得密度相近的點(diǎn)容易聚成一類,近鄰函數(shù)準(zhǔn)則算法（續(xù)）純粹按照歐氏距離，則黃色點(diǎn)歸為第一類按照近鄰函數(shù)值，黃色點(diǎn)歸為第二類。這是比較合理的,近鄰函數(shù)準(zhǔn)則算法（續(xù)）同一類中的點(diǎn)之間存在“連接”。連接損失就定義為兩點(diǎn)之間的近鄰函數(shù)αij。一個(gè)點(diǎn)和其自身的連接損失定義為αii=2N，

21、以懲罰只有一個(gè)點(diǎn)的聚類不同類的點(diǎn)不存在連接，連接損失為αij=0總類內(nèi)損失,近鄰函數(shù)準(zhǔn)則算法（續(xù)）第i類和第j類之間的最小近鄰函數(shù)值定義為第i類內(nèi)最大連接損失記為αimax第i類與第j類之間的連接損失定義為βij,,近鄰函數(shù)準(zhǔn)則算法（續(xù)）βij的設(shè)計(jì)目標(biāo)是：如果兩類間的最小近鄰值大于任何一方的類內(nèi)的最大連接損失時(shí)，損失代價(jià)就是正的，從而應(yīng)該考慮把這兩類合并,近鄰函數(shù)準(zhǔn)則算法（續(xù)）總類間損失準(zhǔn)則函數(shù),,,

22、近鄰函數(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.對(duì)每?jī)蓚€(gè)類計(jì)算γij 和αimax，αjmax ，只要γij 小于αimax、αjmax中的任何一個(gè)，就合并兩類（建立連接）。重復(fù)至沒(méi)有新的連接發(fā)生為止,例：如圖所示樣本，使

23、用近鄰函數(shù)準(zhǔn)則聚類。解：①計(jì)算D矩陣，結(jié)果從簡(jiǎn)；②計(jì)算M矩氏，結(jié)果從簡(jiǎn)；③計(jì)算L矩陣，結(jié)果見(jiàn)表,最小張樹(shù)聚類,術(shù)語(yǔ)：①線段：兩個(gè)模式樣本點(diǎn)的連線②路徑：連接兩點(diǎn)的線段序列③回路：閉合路徑④連通圖形：任兩點(diǎn)之間有一條或一條以上的路徑者。（即各點(diǎn)之間是連結(jié)起來(lái)的，但不一定直接相連。⑤樹(shù)圖：沒(méi)有回路的連通圖形（單線順序相連，不閉合，不返回）,⑥張樹(shù)圖：包含模式樣本集合中每一點(diǎn)的樹(shù)圖（即連結(jié)每一個(gè)模式樣本點(diǎn)且沒(méi)有重復(fù)的連

24、通圖）⑦線段權(quán)重（線的重要性），（可取點(diǎn)間距離）整個(gè)樹(shù)圖的權(quán)重為樹(shù)圖中各線段權(quán)重之和。 ⑧最小張樹(shù)圖：權(quán)重最小的張樹(shù)圖（若以距離作權(quán)重，則各模式樣本點(diǎn)以最小距離連結(jié)每一樣本點(diǎn)，且無(wú)重復(fù)），沿著該路線，連結(jié)相鄰每點(diǎn)間的距離總和min一條路，經(jīng)過(guò)最多點(diǎn)，代價(jià)最小。⑨主直徑：在最小張樹(shù)圖中走過(guò)最多模式樣本點(diǎn)的那條路徑,最小張樹(shù)圖構(gòu)成方法：①計(jì)算距離表②所有距離按從小到大順序排列③按距離從小到大順序連結(jié)點(diǎn)對(duì)。規(guī)則：最小生成

25、樹(shù)算法，找到圖的最小生成樹(shù)，然后把樹(shù)上最長(zhǎng)的邊去掉形成兩個(gè)類。在兩個(gè)子圖中再去掉最長(zhǎng)邊，…，依次進(jìn)行下去,例：遞增排序：BC、DF、DE、EF、AB、AC、CD、AD、 CF連接順序：BC AB CD DF DE,缺點(diǎn)：對(duì)密集點(diǎn)集之間干擾敏感改進(jìn)：引入樹(shù)的直徑和點(diǎn)深度點(diǎn)的深度：與該點(diǎn)連接的最長(zhǎng)分支的長(zhǎng)度算法步驟如下：①給定混合樣本集，生成最小張樹(shù)(可按距離給權(quán)值)；②確定最小張樹(shù)上的直徑和計(jì)算直徑上各點(diǎn)深度；②繪制直