第7章聚類分析層次聚類層次聚類層次聚類(HierarchicalClustering)，即按照一定的規(guī)則，對給定的數(shù)據集進行分層次的聚集或分解，直到滿足某種事先設定的條件。按聚類的次序：凝聚的層次聚類分裂的層次聚類凝聚的層次聚類a,b,c,d,ec,d,ed,ea,bedcba第4步第3步第2步第1步第0步凝聚的（AGENS）凝聚的層次聚類采用自底向上的策略，開始時把每個對象作為一個單獨的簇，然后逐次對各個簇進行適當合并，直到滿足某個終止條件。分裂的層次聚類a,b,c,d,ec,d,ed,ea,bedcba第0步第1步第2步第3步第4步分裂的（DIANA）分裂的層次聚類采用自頂向下的策略，與凝聚的層次聚類相反，開始時將所有對象置于同一個簇中，然后逐次將簇分裂為更小的簇，直到滿足某個終止條件。層次聚類按數(shù)據分層建立簇，形成一棵以簇為節(jié)點的樹，稱為聚類圖。13254600.050.10.150.2基本凝聚層次聚類方法凝聚層次聚類算法計算鄰近度矩陣讓每個點作為一個ClusterRepeat

合并最近的兩個類

更新鄰近度矩陣，以反映新的簇與原來的簇之間的鄰近性Until僅剩下一個簇

傳統(tǒng)的算法利用相似性或相異性的鄰近度矩陣進行凝聚的或分裂的層次聚類關鍵的操作是2個簇的鄰近度計算不同的鄰近度的定義區(qū)分了各種不同的凝聚層次技術[例1]1.將每單個數(shù)據聚為一個簇；p7p12p3p9p5p1p8p10p11p2p6p4p7p12p3p9p5p1p8p10p11p2p6p4

xyp11310p21411p3165p41822p51817p6194p72122p8307p9314p103420p113515p123622[例]2.將最鄰近的兩個簇聚為一個簇；1.將每單個數(shù)據聚為一個簇；

xyp11310p21411p3165p41822p51817p6194p72122p8307p9314p103420p113515p123622p1p2p3p6p4p7p5p8p9p10p12p11C1,2C3,6C4,7C8,9C10,12p10p3p7p5p4p9p8p6p11p12p1p2p1p2p3p6p4p7p5p8p9p10p12p11C1,2C3,6C4,7C8,9C10,12C1,2,3,6C4,7,5C10,12,11p10p3p7p5p4p9p8p6p11p12p1p2p1p2p3p6p4p7p5p8p9p10p12p11C1,2C3,6C4,7C8,9C10,12C1,2,3,6C4,7,5C10,12,11C1,2,3,6,4,7,5C8,9,10,12,11C1,2,3,6,4,7,5,8,9,10,12,11p10p3p7p5p4p9p8p6p11p12p1p2[例2]2.將最鄰近的兩個簇聚為一個簇；1.將每單個數(shù)據聚為一個簇；ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p12314改進的算法充分利用鄰近度矩陣進行聚類？示例2.將最鄰近的兩個簇聚為一個簇；1.將每單個數(shù)據聚為一個簇；ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p123143.迭代進行，直至聚類為一個簇。示例ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p12314示例ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p12314示例ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p12314Cluster間的相似性相似性？p3p6p4p1p2p5MIN（單鏈）MAX（全鏈）GroupAverage組平均DistanceBetweenCentroids質心距ObjectiveFunction目標函數(shù)類Cluster間的相似性MINp3p6p4p1p2p5MIN（單鏈）兩個Cluster的相似性定義為基于

這兩個Cluster中最大相似度（最近距離）由一對最近鄰點決定p1p2p5p4p3p6p1

p215.6

p518.4

p42613.320.6

p3169.818.410.8

p620.61725.613

p2p5p3p6p4p1dist({3,6},{2,5})=min(dist(3,2),dist(3,5),dist(6,2),dist(6,5))

=min(9.8,18.4,17,25.6)

=9.8Cluster間的相似性MIN（單鏈）p2p5p3p6p4p1p1p2p3p5p6p4p1p4p2p5p3p6p1

p426

p215.613.3

p518.420.6

p31610.8

p620.613

p1p4p2p5p3p6p1

p426

p215.6

p518.4

p316

p620.6

Cluster間的相似性MIN（單鏈）單鏈技術可以處理非橢圓形狀的簇Cluster間的相似性MIN（單鏈）單鏈技術可以處理非橢圓形狀的簇但對噪音和離群點很敏感Cluster間的相似性MAXp3p6p4p1p2p5MAX（全鏈）兩個Cluster的相似性定義為基于

這兩個Cluster中最小相似度（最遠距離）由一對最遠離點決定p1p2p5p4p3p6p1

p215.6

p518.4

p42613.320.6

p3169.818.410.8

p620.61725.613

p2p5p3p6p4p1dist({3,6},{2,5})=max(dist(3,2),dist(3,5),dist(6,2),dist(6,5))

=min(9.8,18.4,17,25.6)=25.6Cluster間的相似性MAX（全鏈）p2p5p3p6p4p1p1p2p3p5p6p4p1p2p5p4p3p6p1

p215.6

p518.4

p42613.320.6

p3169.818.4

p620.61725.6

p1p2p5p4p3p6p1

p2

p5

p42613.320.6

p3169.818.4

p620.61725.6

Cluster間的相似性MAX（全鏈）對噪音和離群不敏感Cluster間的相似性MAX（全鏈）對噪音和離群不敏感可能使大的簇破裂，偏好球型簇Cluster間的相似性GroupAverage組平均兩個簇的鄰近度定義為不同的所有點

對的平均逐對鄰近度是一種單鏈與全鏈的折中算法p2p5p3p6p4p1p1p2p3p5p6p4組平均Cluster間的相似性GroupAverage組平均兩個簇的鄰近度定義為不同簇的所有點

對的平均逐對鄰近度是一種單鏈與全鏈的折中算法p2p5p3p6p4p1p1p2p3p5p6p4p1p2p5p4p3p6p1

p217

p5

p42616.9

p318.317.711.9

p6

組平均Cluster間的相似性GroupAverage組平均p2p5p3p6p4p1p1p2p5p4p3p6p1

p217

p5

p420.917.5

p3

p6

p1p2p5p4p3p6p1

p2

p5

p418.6

p3

p6

p1p2p3p5p6p4Cluster間的相似性GroupAverage組平均對噪音和極端值影響小偏好球型簇Cluster間的相似性DistanceBetweenCentroids質心距兩個簇的鄰近度定義為不同簇的質心

的鄰近度p2p5p3p6p4p1p1p2p3p5p6p4質心距p1p2,5p4p3,6p1

p2,516.5

p42616.8

p3,618.117.711.4

Cluster間的相似性DistanceBetweenCentroids質心距兩個簇的鄰近度定義為不同簇的質心

的鄰近度p2p5p3p6p4p1p1p2,5p4,3,6p1

p2,516.51

p4,3,620.3616.54

p1p2p3p5p6p4p1,2,5p4,3,6p1,2,5

p4,3,616.12Cluster間的相似性ObjectiveFunction目標函數(shù)類Ward算法兩個簇的鄰近度定義為兩個簇合并時導致的平方誤差的增量p2p5p3p6p4p1p1p2p3p5p6p4C1C2SSEp1p27.8p1p38.0p1p413.0p1p59.2p1p610.3p2p34.9p2p46.7p2p54.3p2p68.5p3p45.4p3p59.2p3p63.6p4p66.5p4p510.3p5p612.8C1C2SSEp1p27.8p1p3,69.1p1p413.0p1p59.2p2p3,66.7p2p46.7p2P54.3p4p3,65.7p4p510.3p5p3,611.0C1C2SSEp1p2,58.3p1p3,69.1p1p413.0p2,5p3,68.8p3,6p2,58.8p4p3,65.7p4p2,58.4C1C2SSEp1p2,58.3p1p4,3,610.2p2,5p4,3,68.3C1C2SSEp1,2,5p4,3,68.1Cluster間的相似性ObjectiveFunction目標函數(shù)類Ward算法兩個簇的鄰近度定義為兩個簇合并時導致的平方誤差增量當鄰近度取它們之間的平方時，ward與組平均類似噪音和極端值影響小偏好球型簇Cluster間的相似性MIN單鏈MAX全鏈組平均W