兩種簡單的聚類算法

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

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

3、量：設(shè)樣本已分成ωp,ωq兩類，若把ωp,ωq合為ωr類，則定義離差平方：,（2）系統(tǒng)聚類的算法 首先將m個樣品自成一類，然后每次將具有最小距離的兩類合并，合并后重新計算類與類之間的距離，這個過程一直繼續(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ù)沒有達到要求，轉(zhuǎn)3。否則停止。3、求最小元素： 4、ω8,ω5,ω2合并, ω9=（2,5,4,6）,分解聚類,分解聚類：把全部樣本作為一類，然后根據(jù)相似性、相鄰性分解。目標函數(shù) 兩類均值方差,N：總樣本數(shù)， ：ω1類樣本數(shù) ：ω2類樣本數(shù)，,分解聚類框圖：,對分算法：略 例：已知21個樣本，每個樣本取二個特征，原始資料矩陣如下表：,解：第一次分類時計算所有樣本，分別劃到,時的E值，找出

5、最大的。1、開始時，,2、分別計算當 劃入,時的E值,把 劃入,時有,然后再把 劃入 時對應(yīng)的E值，找出一個最大的E值。 把 劃為 的E值最大?！?E(1)=56.6,再繼續(xù)進行第二，第三次迭代…計算出 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次迭代 劃入 時，E最大。于是分成以下兩類：∴,每次分類后要重新計算 的值?？捎靡韵逻f推公式：,,,,動態(tài)聚類——兼顧系統(tǒng)聚類和分解聚類,一、動態(tài)聚類的方法概要 ① 先選定某種距離作為樣本間的相似性的度量; ② 確定評價聚類結(jié)果的準

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

11、先選密度最大的作為第一個代表點，即第一個聚類中心。再考慮第二大密度點，若第二大密度點距第一代表點的距離大于d1（人為規(guī)定的正數(shù)）則把第二大密度點作為第二代表點，，否則不能作為代表點，這樣按密度大小考察下去，所選代表點間的距離都大于d1。d1太小，代表點太多，d1太大，代表點太小，一般選d1＝2d。對代表點內(nèi)的密度一般要求大于T。T>0為規(guī)定的一個正數(shù)。④ 用前k個樣本點作為代表點。,三、初始分類和調(diào)整 ① 選一批

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

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

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

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

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

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

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

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

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

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

22、近鄰函數(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ā)生為止,例：如圖所示樣本，使

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

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

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