《数据挖掘原理与应用 第2版 》课件 7.4聚类分析-层次聚类

第7章聚类分析层次聚类层次聚类层次聚类(HierarchicalClustering)，即按照一定的规则，对给定的数据集进行分层次的聚集或分解，直到满足某种事先设定的条件。按聚类的次序：凝聚的层次聚类分裂的层次聚类凝聚的层次聚类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）分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。13254600.050.10.150.2基本凝聚层次聚类方法凝聚层次聚类算法计算邻近度矩阵让每个点作为一个ClusterRepeat

合并最近的两个类

更新邻近度矩阵，以反映新的簇与原来的簇之间的邻近性Until仅剩下一个簇

传统的算法利用相似性或相异性的邻近度矩阵进行凝聚的或分裂的层次聚类关键的操作是2个簇的邻近度计算不同的邻近度的定义区分了各种不同的凝聚层次技术[例1]1.将每单个数据聚为一个簇；p7p12p3p9p5p1p8p10p11p2p6p4p7p12p3p9p5p1p8p10p11p2p6p4

xyp11310p21411p3165p41822p51817p6194p72122p8307p9314p103420p113515p123622[例]2.将最邻近的两个簇聚为一个簇；1.将每单个数据聚为一个簇；

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.将每单个数据聚为一个簇；ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p12314改进的算法充分利用邻近度矩阵进行聚类？示例2.将最邻近的两个簇聚为一个簇；1.将每单个数据聚为一个簇；ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p123143.迭代进行，直至聚类为一个簇。示例ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p12314示例ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p12314示例ptxyp11822p22122p31817p43622p53420p63515p71411p81310p9165p10194p11307p12314Cluster间的相似性相似性？p3p6p4p1p2p5MIN（单链）MAX（全链）GroupAverage组平均DistanceBetweenCentroids质心距ObjectiveFunction目标函数类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目标函数类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目标函数类Ward算法两个簇的邻近度定义为两个簇合并时导致的平方误差增量当邻近度取它们之间的平方时，ward与组平均类似噪音和极端值影响小偏好球型簇Cluster间的相似性MIN单链MAX全链组平均W