第二十讲 聚类分析物以类聚，人以群分
第二十讲 聚类分析 物以类聚，人以群分
聚类分析ClusterAnalysis在事先不知道类别信息的情况下（无监督学习）★★*★聚类分析将相似度高的或者距离小的个体聚集成一类(cluster)，不相似的个体分属不同的类++指标集={,2.n的子集C...C称为的一个K划分划分Partition(partition),如果它们两两不交，且UC,=1.17n=100,K=2,J)K-in个研究对象的K-划分个数：=O(K")2100=30位个穷尽所有划分几乎是不可能的，几乎所有的聚类算法基本都是贪心算法。下面主要介绍几个经典的算法：层次聚类、K-medoid聚类、K-均值聚类（混合高斯分布模型）、谱聚类
2 在事先不知道类别信息的情况下(无监督学习)， 聚类分析将相似度高的或者距离小的个体聚集 成一类(cluster)，不相似的个体分属不同的类。 ( 1) ( ) ! 1 - 0 n n K j K j j O K j K K n K 个研究对象的 划分个数： 聚类分析 Cluster Analysis 穷尽所有划分几乎是不可能的，几乎所有的聚类算法基本都是贪 心算法。下面主要介绍几个经典的算法： 层次聚类、𝐾-medoid 聚类、𝐾 -均值聚类（混合高斯分布模型） 、谱聚类。 𝑛 = 100,𝐾 = 2, 2 100 = 30位 划分 Partition (partition), . {1,2,., } ,., - 1 1 C I I n C C I K K i i K 如果它们两两不交，且 指标集 的子集 称为 的一个 划分
层次聚类HierarchicalClustering层次聚类将研究对象逐步合并（或分拆），也称作系统聚类，主要包括聚合层次聚类法和分割层次聚类法。其中的关键是定义类与类之间的距离。foalhorseoxcalfcowgoatkidlambsheephenroosterduckgooseturkeychickducklingdogcatrabbit
3 层次聚类Hierarchical Clustering 层次聚类将研究对象逐步合并（或分拆），也称作系统聚 类，主要包括聚合层次聚类法和分割层次聚类法。其中的 关键是定义类与类之间的距离
层次聚类中需要考虑子集（类）的合并或分拆，因此需要定义类之Linkage:间的距离，我们将距离小的集合进行合并，称为连结（linkage：类之间themannerbeingunited)。的距离假设个体a,b之间的距离为d(ab），则集合之间的距离/连结：单连结(single-linkage):dmin(A,B)= min_d(a,b)aEA.bER完全连结(complete-linkage): dmax(A,B) = max,d(a,b)aEA,bEB 平均连结(mean-linkage): dmean(A, B) = ZaEA,beB d(a, b) /IAIBI其它连结：median，centroid，WardSingle linkageCompletelinkageCentroid linkageMean/medianlinkage
4 层次聚类中需要考虑子集( 类)的合并或分拆，因此需要定义类之 间的距离, 我们将距离小的集合进行合并，称为连结（linkage: the manner being united）。 Linkage: 类之间 的距离 Mean/median linkage Centroid linkage 假设个体𝑎, 𝑏之间的距离为𝑑(𝑎, 𝑏), 则集合之间的距离/连结： 单连结(single-linkage): 𝑑min 𝐴, 𝐵 = min 𝑎∈𝐴,𝑏∈𝐵 𝑑(𝑎, 𝑏) 完全连结(complete-linkage): 𝑑max 𝐴, 𝐵 = max 𝑎∈𝐴,𝑏∈𝐵 𝑑(𝑎, 𝑏) 平均连结(mean-linkage): 𝑑mean 𝐴, 𝐵 = σ𝑎∈𝐴,𝑏∈𝐵 𝑑 𝑎, 𝑏 /|𝐴||𝐵| 其它连结：median，centroid，Ward
ClusterdistanceSingle：只要两个集合存在一对点距离较小，就认为d24这两个集合是同一类。(a)Complete：只有当两个集合031的所有点都距离较小时才认4dis为两个集合属于同一类(b)Averge：当所有点对之间di3+ di4 + dis + d23 + d24 +d25距离的平均/中位数较小时：46认为两个集合属于同一类。5median/centroid与此类似。(c)5
5 Single: 只要两个集合存在 一对点距离较小，就认为 这两个集合是同一类。 Complete：只有当两个集合 的所有点都距离较小时才认 为两个集合属于同一类 Averge ：当所有点对之间 距离的平均 /中位数较小时， 认为两个集合属于同一类 。 median/centroid与此类似
聚合（agglomeration）层次聚类法首先把每个研究对象聚合层次(object，item,unit)看作一类，然后逐步合并相异度（距离）最小聚类算法的或相似度最大的类，相继地逐步聚集1.初始假定每一个研究对象是一个类(cluster)，计算各个类之间的距离；2．距离最小的两个cluster合并成一个更大的cluster；3.重新计算各个类(cluster)之间的距离；重复2，3直到达到某个预定标准或者所有对象合并成一类。R：hclust(d）#d：距离矩阵分割层次聚类法分割层次与聚合聚类相反，首先将所有个体当作一类，逐步分割成距离聚类算法最大或相似度最小的两类.效果与聚合方法类似，不常用。6
6 聚合（agglomeration）层次聚类法首先把每个研究对象 (object，item,unit)看作一类，然后逐步合并相异度(距离)最小 的或相似度最大的类，相继地逐步聚集 1. 初始假定每一个研究对象是一个类(cluster)，计算各个 类之间的距离； 2. 距离最小的两个cluster合并成一个更大的cluster； 3. 重新计算各个类(cluster)之间的距离； 重复2，3直到达到某个预定标准或者所有对象合并成一类。 聚合层次 聚类算法 分割层次聚类法 与聚合聚类相反，首先将所有个体当作一类，逐步分割成距离 最大或相似度最小的两类 . 效果与聚合方法类似，不常用。 R: hclust(d) # d: 距离矩阵 分割层次 聚类算法
树图树状图（Dendrogram）表示层次聚类关系，在根部所有物体为一类朝枝叶方向依次细分（左图）树旁的刻度尺表示聚集或分拆时的距离。更紧凑的树图如右图（不再是树状！）myhc=hclust(d,method=）#层次聚类library(ape)plot(myhc)#画树图plot(as.phylo(myhc),type="fan")
7 树图 树状图(Dendrogram) 表示层次聚类关系，在根部所有物体为一类， 朝枝叶方向依次细分（左图）树旁的刻度尺表示聚集或分拆时的 距离。更紧凑的树图如右图（不再是树状！） myhc= hclust(d,method=) #层次聚类 plot(myhc) #画树图 library(ape) plot(as.phylo(myhc), type = "fan")
例1.平面上的点a-f.单连结聚合层次聚类abcdeb9c91D=d734e8431f75522abcdef步骤细节：7-b,c之间、d,e之间的距离都是1，最bcdef小，首先将它们合并集为(bc)，（de)两3-个类。至此有4个类：def2 -(bc), (de), a,f计算这它们的两两距离，f与（de）距离1-bcde2最小，合并为（def），至此有3个类(bc), (def), (a)03类间(bc),(def)距离3最小，合并(bcdef), (a)交汇/合并处的数字(Height)表示聚合时的距离，比如f与（d.e）聚合时的距离为2。8
8 a b c d e f a b c d e f bc de def bcdef abcdef 例1. 平面上的点a-f, 单连结聚合层次聚类 a b c d e b 9 c 9 1 d 7 3 4 e 8 4 3 1 f 7 5 5 2 2 D= 3 2 1 0 步骤细节： b,c之间、d,e 之间的距离都是1，最 小，首先将它们合并集为(bc), (de)两 个类。至此有4个类： (bc), (de), a,f 计算这它们的两两距离，f与(de)距离 2最小，合并为(def), 至此有3个类 (bc), (def), (a) 3类间(bc), (def)距离3最小，合并 (bcdef), (a) 交汇/合并处的数字(Height)表示聚合时 的距离，比如f与(d,e) 聚合时的距离为2。 1 1 2 2 3 3 7
01例2（课本例12.3)，5个物体的距离矩阵如右，290D=(dik考虑Single-linkage聚集层次聚类分析。346511.把每个对象当作一个类，ds=②=min(d,)将3,5合并为一类(35)，得到4个类：(35),1,2,4计算4个类：(35),1,2，4的两两距离：d(35)1 = min(d31,ds1)= min(3,11)= 3,d(35)2 = min(d32,ds2) = 7,d(35)4 = min(d34,d54)= 81,2,4之间的距离9,6,5(35)21最小距离③=d(35)0(35)③01合并(35),(1)2970486T0
9 例2 (课本例12.3)，5个物体的距离矩阵如右， 考虑Single-linkage 聚集层次聚类分析。 最小距离3 d(35)1 1 2 4 9 6 5 min( , ) 8 min( , ) 7, min( , ) min(3,11) 3 4 (35),1 2 4 (35)4 34 54 (35)2 32 52 (35)1 31 51 ，之间的距离 ， ， 计算 个类： ，的两两距离： d d d d d d d d d 3 5 (35), 4 (35),1 2 4 1. 2 min( ), 35 将 ，合并为一类 得到 个类： ， 把每个对象当作一个类，d dij 合并(35), (1)
2.合并(35)和1之后，计算(351)2.4三个类的两两距离d(351)2 = min(d(35)2,dj2) = min(7,9) = 7d(351)4 = min(d(35)4,dj4)= min(8,6)= 6d24 = 5(135)42最小距离(5)0(135)270合并(2), (4)?46Objects3.合并2,4为之后，共有两个类(135),(24)，读树图：其距离=6，合并，完成。a:3，5首先合并，距离=2，b：（35）与1合并，距离=3c：2,4合并，距离=5.10
10 5 min( , ) min(8,6) 6 min( , ) min(7,9 7 2. (35) 1 (351),2,4 : 24 (351)4 (35)4 14 (351)2 (35)2 12 d d d d d d d ） 合并 和 之后，计算 三个类的两两距离 读树图： a:3，5首先合并,距离=2, b:(35)与1合并,距离=3, c: 2,4合并,距离=5. 其距离 ，合并，完成。 合并 ，为之后，共有两个类 ， 6 3. 2 4 (135),(24) 最小距离5 d24 合并(2), (4) a b c