聚类分析及MATLAB实现

1、4.1 样品（变量）相近性度量样品（变量）相近性度量 4.2 谱系聚类法及谱系聚类法及MATLAB实现实现 4.3 快速聚类法快速聚类法 统计方法（聚类分析）: 聚类分析所研究的样本或者变量之间存 在程度不同的相似性，要求设法找出一些 能够度量它们之间相似程度的统计量作为 分类的依据，再利用这些量将样本或者变 量进行分类 系统聚类分析将n个样本或者n个指标看 成n类，一类包括一个样本或者指标，然 后将性质最接近的两类合并成为一个新类， 依此类推。最终可以按照需要来决定分多 少类，每类有多少样本（指标） 统计方法（系统聚类分析步骤）: 系统聚类方法步骤： 计算n个样本两两之间的距离 构成n个类，

2、每类只包含一个样品 合并距离最近的两类为一个新类 计算新类与当前各类的距离（新类与当 前类的距离等于当前类与组合类中包含 的类的距离最小值），若类的个数等于 1，转5，否则转3 画聚类图 1. 决定类的个数和类。 系统聚类分析: 主要介绍系统聚类分析方法。系统聚类法 是聚类分析中应用最为广泛的一种方法， 它的基本原理是：首先将一定数量的样 品或指标各自看成一类，然后根据样品 （或指标）的亲疏程度，将亲疏程度最 高的两类进行合并。然后考虑合并后的 类与其他类之间的亲疏程度，再进行合 并。重复这一过程，直至将所有的样品 （或指标）合并为一类。 系统聚类分析用到的函数: 函 数功 能 pdist计算

3、观测量两两之间的距离 squareform 将距离矩阵从上三角形式转换为方形 形式，或从方形形式转换为上三角形 式 linkage 创建系统聚类树 dendrogram 输出冰柱图 cophenet 计算Cophenetic相关系数 cluster 根据linkage函数的输出创建分类 clusterdata 根据数据创建分类 inconsistent 计算聚类树的不连续系数 聚类分析 研究对研究对样品或指标样品或指标进行分类的一种多元统计方法进行分类的一种多元统计方法, 是依据研究对象的个体的特征进行分类的方法。是依据研究对象的个体的特征进行分类的方法。 聚类分析把分类对象按一定规则分成若干

4、类，这聚类分析把分类对象按一定规则分成若干类，这 些类些类非事先给定非事先给定的，而是根据数据特征确定的。的，而是根据数据特征确定的。 在同一类中这些对象在某种意义上趋向于彼此相在同一类中这些对象在某种意义上趋向于彼此相 似，而在不同类中趋向于不相似。似，而在不同类中趋向于不相似。 职能是建立一种能按照样品或变量的相似程度进职能是建立一种能按照样品或变量的相似程度进 行分类的方法。行分类的方法。 聚类分析有两种聚类分析有两种：一种是对样品的分类，称为：一种是对样品的分类，称为Q 型，另一种是对变量（指标）的分类，称为型，另一种是对变量（指标）的分类，称为R型。型。 R型聚类分析的主要作用：型聚

5、类分析的主要作用： 不但可以了解个别变量之间的亲疏程度，而且可以了解不但可以了解个别变量之间的亲疏程度，而且可以了解 各个变量组合之间的亲疏程度。各个变量组合之间的亲疏程度。 根据变量的分类结果以及它们之间的关系，可以选择主根据变量的分类结果以及它们之间的关系，可以选择主 要变量进行要变量进行Q型聚类分析或回归分析。（型聚类分析或回归分析。（R2为选择标准）为选择标准） Q型聚类分析的主要作用：型聚类分析的主要作用： 可以综合利用多个变量的信息对样本进行分析。可以综合利用多个变量的信息对样本进行分析。 分类结果直观，聚类谱系图清楚地表现数值分类结果。分类结果直观，聚类谱系图清楚地表现数值分类结

6、果。 聚类分析所得到的结果比传统分类方法更细致、全面、聚类分析所得到的结果比传统分类方法更细致、全面、 合理。合理。 在课堂上主要讨论在课堂上主要讨论Q型聚类分析型聚类分析, Q型聚类常用的统计量是距型聚类常用的统计量是距 离离. 4.1 样品（变量）间相近性度量样品（变量）间相近性度量 4.1.1 聚类分析的基本思想聚类分析的基本思想 在生产实际中经常遇到给产品等级进行分类的问题，在生产实际中经常遇到给产品等级进行分类的问题， 如一等品、二等品等，在生物学中，要根据生物的如一等品、二等品等，在生物学中，要根据生物的 特征进行分类；在考古时要对古生物化石进行科学特征进行分类；在考古时要对古生物

7、化石进行科学 分类；在球类比赛中经常要对各球队进行分组如何分类；在球类比赛中经常要对各球队进行分组如何 确定种子队，这些问题就是聚类分析问题。随着科确定种子队，这些问题就是聚类分析问题。随着科 学技术的发展，我们利用已知数据首先提取数据特学技术的发展，我们利用已知数据首先提取数据特 征，然后借助计算机依据这些特征进行分类，聚类征，然后借助计算机依据这些特征进行分类，聚类 的依据在于各类别之间的接近程度如何计量，通常的依据在于各类别之间的接近程度如何计量，通常 采取距离与相似系数进行衡量。采取距离与相似系数进行衡量。 设有设有n个样品的个样品的p元观测数据组成一个数据矩阵元观测数据组成一个数据矩

8、阵 npn2n1 2p2221 1p1211 xxx xxx xxx X 其中每一行表示一个样品，每一列表示一个指标，其中每一行表示一个样品，每一列表示一个指标，xij 表示第表示第i个样品关于第个样品关于第j项指标的观测值，聚类分析的项指标的观测值，聚类分析的 基本思想就是在样品之间定义距离，在指标之间定义基本思想就是在样品之间定义距离，在指标之间定义 相似系数，样品之间距离表明样品之间的相似度，指相似系数，样品之间距离表明样品之间的相似度，指 标之间的相似系数刻画指标之间的相似度。将样品标之间的相似系数刻画指标之间的相似度。将样品 （或变量）按相似度的大小逐一归类，关系密切的聚（或变量）按

9、相似度的大小逐一归类，关系密切的聚 集到较小的一类，关系疏远的聚集到较大的一类，聚集到较小的一类，关系疏远的聚集到较大的一类，聚 类分析通常有：类分析通常有：谱系聚类、快速聚类，我们主要介绍谱系聚类、快速聚类，我们主要介绍 谱系聚类的方法与谱系聚类的方法与MATLAB实现实现 4.1.2 样品间的相似度量样品间的相似度量距离距离 一一.常用距离的定义常用距离的定义 设有设有n个样品的个样品的p元观测数据：元观测数据： n21ixxxx T ipi2i1i ,),( 这时，每个样品可看成这时，每个样品可看成p p元空间的一个点，每两个点之元空间的一个点，每两个点之 间的距离记为间的距离记为 满足

10、条件：满足条件： ),( ji xxd jijiji xx0 xxd0 xxd当且仅当且),(,),( ),(),( ijji xxdxxd ),(),(),( jkkiji xxdxxdxxd 1.欧氏距离欧氏距离 21 p 1k 2 jkikji xxxxd / )(),( pdist(x) 2.绝对距离绝对距离 p 1k jkikji xxxxd|),(pdist(x,cityblock) 3.明氏距离明氏距离 m1 p 1k m jkikji xxxxd / |),( pdist(x,minkowski,r) 4.切氏距离切氏距离 |),( jkik pk1 ji xxmaxxxd m

11、ax(abs(xi-xj) 5.方差加权距离方差加权距离 21 p 1k 2 k 2 jkikji sxxxxd / /)(),( 将原数据标准化以后的欧氏距离将原数据标准化以后的欧氏距离 6.马氏距离马氏距离 T1 ijijij d(x ,x )(xx )(xx ) pdist(x,mahal) 7.兰氏距离兰氏距离 p 1k jkik jkik ji xx xx p 1 xxd | ),( 8.杰氏距离（杰氏距离（Jffreys x3:人均烟酒茶支出，人均烟酒茶支出， x4:人均其他副食支出人均其他副食支出,x5:人均衣着商品支出人均衣着商品支出,x6:人均人均 日用品支出，日用品支出，x

12、7:人均燃料支出，人均燃料支出，x8人均非商品支出人均非商品支出 X X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 7X X8 8 辽宁辽宁7.97.939.7739.778.498.4912.9412.9419.2719.2711.0511.052.042.0413.2913.29 浙江浙江7.687.6850.3750.3711.3511.3513.313.319.2519.2514.5914.592.752.7514.8714.87 河南河南9.429.4227.9327.938.28.28.148.1416.1716.179.429.421.551.55

13、9.769.76 甘肃甘肃9.169.1627.9827.989.019.019.329.3215.9915.999.19.11.821.8211.3511.35 青海青海10.0610.0628.6428.6410.5210.5210.0510.0516.1816.188.398.391.961.9610.8110.81 表表1 1991年五省城镇居民生活月均消费（元年五省城镇居民生活月均消费（元/人）人） 计算各省之间的欧氏、绝对、明氏距离计算各省之间的欧氏、绝对、明氏距离 解：解：a=7.939.778.4912.9419.2711.052.0413.29 7.6850.3711.351

14、3.319.2514.592.7514.87 9.4227.938.28.1416.179.421.559.76 9.1627.989.019.3215.999.11.8211.35 10.0628.6410.5210.0516.188.391.9610.81; d1=pdist(a);% 此时计算出各行之间的欧氏距离，此时计算出各行之间的欧氏距离， 为了得到书中的距离矩阵，我们键入命令：为了得到书中的距离矩阵，我们键入命令： D= squareform(d1), % 注意此时注意此时d1必须是一个行向量，必须是一个行向量， 结果是实对称矩阵结果是实对称矩阵 若想得到书中的三角阵，则有命令：若

15、想得到书中的三角阵，则有命令： S = tril(squareform(d1) S = 0 0 0 0 0 11.6726 0 0 0 0 13.8054 24.6353 0 0 0 13.1278 24.0591 2.2033 0 0 12.7983 23.5389 3.5037 2.2159 0 d2=pdist(a,cityblock); S2 = tril(squareform(d2) S2 = 0 0 0 0 0 19.89 0 0 0 0 27.2 47.05 0 0 0 24.58 43.39 4.66 0 0 26.52 42.31 8.08 5.38 0 d3=pdist(a

16、,minkowski,3); S3 = tril(squareform(d3) 序号序号国家国家199019952000 1澳大利亚澳大利亚1249.391273.611282.68 2巴西巴西821.6859.85919.73 3加拿大加拿大1641.011591.541608.32 4中国中国1330.451382.681462.08 5法国法国1546.551501.771525.95 6德国德国1656.521630.521570.69 7印度印度861.30862.51945.11 8意大利意大利1321.771232.31243.51 9日本日本1873.681949.891851

17、.20 10俄罗斯俄罗斯1475.161315.871297 11南非南非794.25787.48782.38 12英国英国1486.751441.711465.12 13美国美国2824.292659.642740.12 例例2. 13个国家个国家1990，1995，2000可持续发展可持续发展 能力如下：分成能力如下：分成4类类 采用不同的距离，得到结果如下采用不同的距离，得到结果如下 类别类别欧氏距离（最短距离）欧氏距离（最短距离） 1日本日本 2澳大利亚、加拿大、英、德、意、中、俄、法澳大利亚、加拿大、英、德、意、中、俄、法 3巴西、印度、南非巴西、印度、南非 4美国美国 类别类别欧氏

18、距离（欧氏距离（ward距离）距离） 1澳大利亚、中、意、俄澳大利亚、中、意、俄 2加拿大、英、德、法、日本加拿大、英、德、法、日本 3巴西、印度、南非巴西、印度、南非 4美国美国 类别类别马氏距离（马氏距离（ward距离）距离） 1日本日本 2澳大利亚、加拿大、英、德、意、南非、俄、法澳大利亚、加拿大、英、德、意、南非、俄、法 3巴西、印度、中巴西、印度、中 4美国美国 4.1.3 变量间的相似度量变量间的相似度量相似系数相似系数 当对当对p个指标变量进行聚类时，用相似系数来个指标变量进行聚类时，用相似系数来 衡量变量之间的相似程度（关联度），若用衡量变量之间的相似程度（关联度），若用 表表

19、 示变量之间的相似系数，则应满足：示变量之间的相似系数，则应满足： , C 1C1C 且,| 0kk1C, 当且仅当 CC 相似系数中最常用的是相似系数中最常用的是相关系数与夹角余弦相关系数与夹角余弦。 夹角余弦夹角余弦 两变量的夹角余弦定义为：两变量的夹角余弦定义为： 相关系数相关系数 两变量的相关系数定义为：两变量的相关系数定义为： 例例3.计算例计算例1中各指标之间的相关系数与夹角余弦中各指标之间的相关系数与夹角余弦 解：解：a=7.939.77 8.4912.94 19.27 11.052.04 13.29 7.6850.37 11.3513.319.25 14.59 2.75 14.

20、87 9.4227.93 8.28.1416.17 9.421.55 9.76 9.1627.98 9.019.3215.99 9.11.82 11.35 10.06 28.64 10.52 10.05 16.18 8.391.96 10.81; R=corrcoef(a);% 指标之间的相关系数指标之间的相关系数 a1=normc(a); % 将将a的各列化为单位向量的各列化为单位向量 J=a1*a1 % 计算计算a中各列之间的夹角余弦中各列之间的夹角余弦 J = 1.0000 0.9410 0.9847 0.9613 0.9824 0.9546 0.9620 0.9695 0.9410 1

21、.0000 0.9782 0.9939 0.9853 0.9977 0.9947 0.9935 0.9847 0.9782 1.0000 0.9859 0.9911 0.9840 0.9931 0.9909 0.9613 0.9939 0.9859 1.0000 0.9944 0.9919 0.9947 0.9981 0.9824 0.9853 0.9911 0.9944 1.0000 0.9901 0.9901 0.9968 0.9546 0.9977 0.9840 0.9919 0.9901 1.0000 0.9952 0.9953 0.9620 0.9947 0.9931 0.9947

22、0.9901 0.9952 1.0000 0.9968 0.9695 0.9935 0.9909 0.9981 0.9968 0.9953 0.9968 1.0000 4.2 谱系聚类法谱系聚类法 谱系聚类法是目前应用较为广泛的一种聚类法。谱谱系聚类法是目前应用较为广泛的一种聚类法。谱 系聚类是根据生物分类学的思想对研究对象进行分类的系聚类是根据生物分类学的思想对研究对象进行分类的 方法。在生物分类学中，分类的单位是：门、纲、目、方法。在生物分类学中，分类的单位是：门、纲、目、 科、属、种。其中种是分类的基本单位，分类单位越小，科、属、种。其中种是分类的基本单位，分类单位越小， 它所包含的生物

23、就越少，生物之间的共同特征就越多。它所包含的生物就越少，生物之间的共同特征就越多。 利用这种思想，谱系聚类首先将各样品自成一类，然后利用这种思想，谱系聚类首先将各样品自成一类，然后 把最相似（距离最近或相似系数最大）的样品聚为小类，把最相似（距离最近或相似系数最大）的样品聚为小类， 再将已聚合的小类按各类之间的相似性（用类间距离度再将已聚合的小类按各类之间的相似性（用类间距离度 量）进行再聚合，随着相似性的减弱，最后将一切子类量）进行再聚合，随着相似性的减弱，最后将一切子类 都聚为一大类，从而得到一个按相似性大小聚结起来的都聚为一大类，从而得到一个按相似性大小聚结起来的 一个谱系图。一个谱系图

24、。 聚类分析的聚类分析的基本思想基本思想是认为我们所研究的样是认为我们所研究的样 本或指标（变量）之间存在着程度不同的相似性本或指标（变量）之间存在着程度不同的相似性 （亲疏关系）。于是根据一批样本的多个观测指标，（亲疏关系）。于是根据一批样本的多个观测指标， 具体找出一些彼此之间相似程度较大的样本（或指具体找出一些彼此之间相似程度较大的样本（或指 标）聚合为一类，把另外一些彼此之间相似程度较标）聚合为一类，把另外一些彼此之间相似程度较 大的样本（或指标）又聚合为另一类，关系密切的大的样本（或指标）又聚合为另一类，关系密切的 聚合到一个小的分类单位，关系疏远的聚合到一个聚合到一个小的分类单位，

25、关系疏远的聚合到一个 大的分类单位，直到把所有样本（或指标）都聚合大的分类单位，直到把所有样本（或指标）都聚合 完毕，把不同的类型一一划分出来，形成一个由小完毕，把不同的类型一一划分出来，形成一个由小 到大的分类系统。最后把整个分类系统画成一张谱到大的分类系统。最后把整个分类系统画成一张谱 系图，用它把所有样本（或指标）间的亲疏关系表系图，用它把所有样本（或指标）间的亲疏关系表 示出来。这种方法是最常用的、最基本的一种，称示出来。这种方法是最常用的、最基本的一种，称 为为系统聚类分析系统聚类分析。 4.2.1 类间距离类间距离 前面，我们介绍了两个向量之间的距离，下面我们前面，我们介绍了两个向

26、量之间的距离，下面我们 介绍两个类别之间的距离：介绍两个类别之间的距离： 设设dij表示两个样品表示两个样品xi,xj之间的距离，之间的距离，Gp,Gq分别表示两分别表示两 个类别，各自含有个类别，各自含有np,nq个样品个样品. （1）最短距离）最短距离 ij GjGi pq dminD qp , 即用两类中样品之间的距离最短者作为两类间距离即用两类中样品之间的距离最短者作为两类间距离 （2）最长距离）最长距离 , pq pqij i Gj G Dmax d 即用两类中样品之间的距离最长者作为两类间距离即用两类中样品之间的距离最长者作为两类间距离 最短距离（Nearest Neighbor)

27、 x21 x12 x22 x11 13 d 最长距离（Furthest Neighbor ） x11 x21 12 d 重心距离重心距离 11 ,x y 22 ,xy / 9 i i=1 d9 最长距离最长距离 最短距离最短距离 A B C D E F 中间距离中间距离 （3）类平均距离）类平均距离 pq GiGj ij qp pq d nn 1 D 即用两类中所有两两样品之间距离的平均作为两类间即用两类中所有两两样品之间距离的平均作为两类间 距离距离 （4）重心距离）重心距离 )()(),( qp T qpqppq xxxxxxdD 其中其中 分别是分别是Gp,Gq的重心，这是用两类的重心的

28、重心，这是用两类的重心 之间的欧氏距离作为两类间的距离。之间的欧氏距离作为两类间的距离。 qp xx , （5）离差平方和距离（）离差平方和距离（ward）)()( qp T qp qp qp 2 pq xxxx nn nn D 显然，离差平方和距离与重心距离的平方成正比。显然，离差平方和距离与重心距离的平方成正比。 4.2.2 类间距离的递推公式类间距离的递推公式 设有两类设有两类Gp,Gq合并成新的一类合并成新的一类Gr，包含了，包含了 nr=np+nq个样品，如何计算个样品，如何计算Gr与其他类别与其他类别Gk之间的之间的 距离，这就需要建立类间距离的递推公式。距离，这就需要建立类间距离

29、的递推公式。 （1）最短距离）最短距离),( qkpkrk DDminD （2）最长距离）最长距离 ),( qkpkrk DDmaxD （3）类平均距离）类平均距离 qk r q pk r p rk D n n D n n D （4）重心距离）重心距离2 pq r q r p 2 qk r q 2 pk r p 2 rk D n n n n D n n D n n D 证明：证明： r T rk T rk T krk T rk 2 rk xxxx2xxxxxxD)()( k T k r q k T k r p k T k xx n n xx n n xx () rppqq r 1 ,xn xn

30、 x n 将将 代入（代入（1） (1) _._. pqpq 2TTTT2TT2T rkkkkkkpkqppppqpqqqq 2 rrrrr nnnn 1 Dx xx x2x x2x xn x x2n n x xn x x nnnnn . . 将上式中加上再减去将上式中加上再减去 与与 ，合并同类项，合并同类项 得得 _ p T p r p xx n n q T q r q xx n n q T q r q p T p r p q T q 2 qq T pqpp T p 2 p 2 r q T qq T kk T k r q p T pp T kk T k r p 2 rk xx n n xx

31、 n n xxnxxn2nxxn n 1 xxxx2xx ( n n xxxx2xx ( n n D ) 上式第二行合并同类项，得上式第二行合并同类项，得 2 pq r q r p 2 qk r q 2 pk r p 2 rk D n n n n D n n D n n D （5）离差平方和距离）离差平方和距离 2 pq kr k2 qk kr kq 2 pk kr kp 2 rk D nn n D nn nn D nn nn D 1. 选择样本间距离的定义及类间距离的定义；选择样本间距离的定义及类间距离的定义； 2. 计算计算n n个个样本样本两两之间的距离，得到距离矩阵两两之间的距离，得到

32、距离矩阵 3. 构造个类，每类只含有一个构造个类，每类只含有一个样本样本； 4. 合并符合类间距离定义要求的两类为一个新类；合并符合类间距离定义要求的两类为一个新类； 5. 计算新类与当前各类的距离。若类的个数为计算新类与当前各类的距离。若类的个数为1 1，则转，则转 到步骤到步骤6 6，否则回到步骤，否则回到步骤4;4; 6.6.画出聚类图；画出聚类图； 7.7.决定类的个数和类。决定类的个数和类。 ij dD 4.2.3 4.2.3 谱系聚类法的步骤谱系聚类法的步骤 谱系聚类的步骤如下：谱系聚类的步骤如下： 系统聚类分析的方法系统聚类分析的方法 系统聚类法的聚类原则决定于样品间的距离以系统

33、聚类法的聚类原则决定于样品间的距离以 及类间距离的定义，及类间距离的定义，类间距离类间距离的不同定义就产的不同定义就产 生了不同的系统聚类分析方法。生了不同的系统聚类分析方法。 以下用以下用dij表示样品表示样品X(i)和和X(j)之间的距离，当样品之间的距离，当样品 间的亲疏关系采用相似系数间的亲疏关系采用相似系数Cij时，时， 令令 ； 以下用以下用D(p,q)表示类表示类Gp和和Gq之间的距离。之间的距离。 22 1 ijij Cd （1）n个样品开始作为个样品开始作为n个类，计算两两之间的个类，计算两两之间的 距离或相似系数，得到实对称矩阵距离或相似系数，得到实对称矩阵 nnn2n1

34、2n2221 1n1211 0 ddd ddd ddd D （2）从）从D0的非主对角线上找最小（距离）或最大的非主对角线上找最小（距离）或最大 元素（相似系数），设该元素是元素（相似系数），设该元素是Dpq，则将，则将Gp,Gq合合 并成一个新类并成一个新类Gr=（Gp,Gq），在），在D0中去掉中去掉Gp,Gq 所在的两行、两列，并加上新类与其余各类之间的所在的两行、两列，并加上新类与其余各类之间的 距离距离(或相似系数或相似系数)，得到，得到n-1阶矩阵阶矩阵D1。 （3）从）从D1出发重复步骤（出发重复步骤（2）的做法得到）的做法得到D2，再，再 由由D2出发重复上述步骤，直到所有样品

35、聚为一个出发重复上述步骤，直到所有样品聚为一个 大类为止。大类为止。 （4）在合并过程中要记下合并样品的编号及两类合）在合并过程中要记下合并样品的编号及两类合 并时的水平，并绘制聚类谱系图。并时的水平，并绘制聚类谱系图。 例例4. 从例从例1算得的样品间的欧氏距离矩阵出发，用算得的样品间的欧氏距离矩阵出发，用 下列方法进行谱系聚类。下列方法进行谱系聚类。 （1）最短距离，（）最短距离，（2）最长距离）最长距离 解：我们用解：我们用1，2，3，4，5分别表示辽宁、浙江、河分别表示辽宁、浙江、河 南、甘肃和青海，将距离矩阵记为南、甘肃和青海，将距离矩阵记为D0 5 4 3 2 1 D0 02125

36、1354238012 020206241213 063248013 06711 0 54321 . . . . （1）最短距离法：将各省看成一类，即）最短距离法：将各省看成一类，即Gi=i i=1,5, 从从D0可以看出各类中距离最短的是可以看出各类中距离最短的是d43=2.20,因此将因此将 G3,G4在在2.20水平上合成一个新类水平上合成一个新类G6=3,4,计算计算G6和和 G1,G2,G5之间的最短距离之间的最短距离 ，得，得 212ddminD 0624ddminD 1213ddminD 453565 423262 413161 ., ,., ,., 将计算结果作为第一列，从将计算

37、结果作为第一列，从D0中去掉第中去掉第3、4行与行与3、 4列，剩余元素作为其余各列得到列，剩余元素作为其余各列得到D1 1 D , 5 2 1 43 023.5412.802.21 011.6724.06 013.12 0 52143, 从从D1可以看出可以看出G6与与G5的距离最小，因此在的距离最小，因此在2.21的水的水 平上将平上将G6与与G5合成一类合成一类G7，即，即G7=3，4，5计算计算 G7与与G1，G2之间的最短距离，得之间的最短距离，得 542354230624minDDminD 801280121213minDDminD 526262 516171 .,., .,.,

38、将计算结果作为第一列，从将计算结果作为第一列，从D1中划掉中划掉3，4与与5 所在的行与列，剩余元素作为其他列得所在的行与列，剩余元素作为其他列得 2 1 3,4,5 D2 067115423 0812 0 21543 . . , 从从D2可以看出可以看出G1,G2最接近，在最接近，在11.67的水平上合并的水平上合并 成一类成一类G8，至此只剩下，至此只剩下G7,G8两类，他们之间的距两类，他们之间的距 离为：离为：12.8，故在此水平上将合成一类，包含了全，故在此水平上将合成一类，包含了全 部的五个省份。部的五个省份。 最后，我们作出谱系聚类图：最后，我们作出谱系聚类图： 图1 最短距离聚

39、类图 最长距离聚类方法，同学练习最长距离聚类方法，同学练习 例 为了研究辽宁等为了研究辽宁等5省省1991年城镇居民生活消费年城镇居民生活消费 情况的分布规律，根据调查资料做类型分类，情况的分布规律，根据调查资料做类型分类， 用最短距离做类间分类。数据如下：用最短距离做类间分类。数据如下： x1x2x3x4x5x6x7x8 辽宁17.9039.778.4912.9419.2711.052.0413.29 浙江27.6850.3711.3513.3019.2514.592.7514.87 河南39.4227.938.208.1416.179.421.559.76 甘肃49.1627.989.01

40、9.3215.999.101.8211.35 青海510.0628.6410.5210.0516.188.391.9610.81 将每一个省区视为一个样品，先计算将每一个省区视为一个样品，先计算5个省区之间的欧个省区之间的欧 式距离，用式距离，用D0表示距离矩阵（对称阵，故给出下三角表示距离矩阵（对称阵，故给出下三角 阵）阵） 因此将因此将3.4合并为一类，为类合并为一类，为类6，替代了，替代了3、4两类两类 类类6与剩余的与剩余的1、2、5之间的距离分别为：之间的距离分别为： d(3,4)1=min(d31,d41)=min(13.80,13.12)=13.12 d(3,4)2=min(d3

41、2,d42)=min(24.63,24.06)=24.06 d(3,4)5=min(d35,d45)=min(3.51,2.21)=2.21 021.251.354.2380.12 020.206.2412.13 063.2480.13 067.11 0 54321 5 4 3 2 1 0 青海 甘肃 河南 浙江 辽宁 D 得到新矩阵得到新矩阵 合并类合并类6和类和类5，得到新类，得到新类7 类类7与剩余的与剩余的1、2之间的距离分别为：之间的距离分别为： d(5,6)1=min(d51,d61)=min(12.80,13.12)=12.80 d(5,6)2=min(d52,d62)=min(

42、23.54,24.06)=23.54 054.2380.1221. 25 067.1106.242 012.131 06 5216 1 G G G G GGGG D 得到新矩阵得到新矩阵 合并类合并类1和类和类2，得到新类，得到新类8 此时，我们有两个不同的类：类此时，我们有两个不同的类：类7和类和类8。 它们的最近距离它们的最近距离 d(7,8) =min(d71,d72)=min(12.80,23.54)=12.80 067.1154.232 080.121 07 217 2 G G G GGG D 得到矩阵得到矩阵 最后合并为一个大类。这就是按最短距离定义类间距最后合并为一个大类。这就是

43、按最短距离定义类间距 离的系统聚类方法。最长距离法类似！离的系统聚类方法。最长距离法类似！ 080.128 07 87 3 G G GG D 4.2.4 谱系聚类的谱系聚类的MATLAB实现：实现： （1）输入数据矩阵，注意行与列的实际意义；输入数据矩阵，注意行与列的实际意义； （2）计算各样品之间的距离（行？列？）计算各样品之间的距离（行？列？） 欧氏距离：欧氏距离：d=pdist(A) % 注意计算注意计算A中各行之中各行之 间的距离；间的距离； 绝对距离：绝对距离：d= pdist(A,cityblock); 明氏距离：明氏距离：d=pdist(A,minkowski,r); % r要填

44、要填 上具体的实数；上具体的实数； 方差加权距离：方差加权距离：d= pdist(A,seuclid); 马氏距离：马氏距离：d= pdist(A,mahal); 注意：以上命令输出的结果是一个注意：以上命令输出的结果是一个行向量行向量， 如果要得到距离矩阵，可以用命令：如果要得到距离矩阵，可以用命令： D= squareform(d), 若得到三角阵，可以用命令：若得到三角阵，可以用命令： D= tril(squareform(d1) (3) 选择不同的类间距离进行聚类选择不同的类间距离进行聚类 最短距离最短距离：z1= linkage(d) % 此处及以下的此处及以下的d 都是（都是（2）

45、中算出的距离行向量）中算出的距离行向量 最长距离：最长距离：z2= linkage(d,complete) 中间距离：中间距离：z3= linkage(d,centroid) 重心距离：重心距离：z4= linkage(d,average) 离差平方和：离差平方和：z5= linkage(d,ward) 注意：此时输出的结果是一个注意：此时输出的结果是一个n-1行行3列的矩阵，列的矩阵， 每一行表示在某水平上合并为一类的序号；每一行表示在某水平上合并为一类的序号； （4）作出谱系聚类图作出谱系聚类图 H=dendrogram(z,d) % 注意若样本少于注意若样本少于 30，可以省去，可以省去

46、d,否则必须填写否则必须填写. （5）根据分类数目，输出聚类结果根据分类数目，输出聚类结果 T=cluster(z,k) % 注意注意k是分类数目，是分类数目，z是（是（3） 中的结果中的结果 Find(T=k0) % 找出属于第找出属于第k0类的样品编号类的样品编号 例例5. 将例将例1 利用利用MATLAB软件进行聚类软件进行聚类 解：解：b=7.939.77 8.4912.94 19.27 11.052.0413.29 7.6850.37 11.3513.319.25 14.59 2.7514.87 9.4227.93 8.28.1416.17 9.421.559.76 9.1627.9

47、8 9.019.3215.99 9.11.8211.35 10.06 28.64 10.52 10.05 16.18 8.391.9610.81; 欧氏距离：欧氏距离：d1=pdist(b); %b中每行之间距离中每行之间距离 % 五种类间距离聚类五种类间距离聚类 z1=linkage(d1); z2=linkage(d1,complete); z3=linkage(d1,average); z4=linkage(d1,centroid); z5=linkage(d1,ward); 其中其中z1输出结果为：输出结果为： z1 = 3.0000 4.0000 2.2033 6.0000 5.00

48、00 2.2159 1.0000 2.0000 11.6726 8.0000 7.0000 12.7983 % 在在2.2033的水平，的水平，G3,G4合成一类为合成一类为G6 % 在在2.2159的水平，的水平，G6,G5合成一类为合成一类为G7 % 在在11.6726的水平，的水平，G1,G2合成一类为合成一类为G8 % 在在12.7983的水平，的水平，G7,G8合成一类合成一类 作谱系聚类图：作谱系聚类图：H= dendrogram(z1) % 输出分类结果输出分类结果 T=cluster(z1,3) T 1 2 3 3 3 图图2.最短距离聚类图最短距离聚类图 结果表明：若分为结果

49、表明：若分为 三类，则辽宁是一三类，则辽宁是一 类，浙江是一类，类，浙江是一类， 河南、青海和甘肃河南、青海和甘肃 是另一类。是另一类。 以上是样品之间是欧氏距离，类间距离以上是样品之间是欧氏距离，类间距离 是最短距离聚类的结果，实际上，对样品之是最短距离聚类的结果，实际上，对样品之 间的每一种距离，可以由五种不同的类间距间的每一种距离，可以由五种不同的类间距 离进行聚类。那么哪一种最好呢？离进行聚类。那么哪一种最好呢？为此我们为此我们 可以计算复合相关系数，若该系数越接近于可以计算复合相关系数，若该系数越接近于1 则该聚类越理想。在则该聚类越理想。在MATLAB中计算复合相中计算复合相 关系

50、数的命令如下：关系数的命令如下： R=cophenet(z,d) 其中其中，z 是用某种类间距离是用某种类间距离linkage后的结果，后的结果， d是样品之间的某种距离，是样品之间的某种距离， 想了解利用欧氏距离聚类，那种类间距离最想了解利用欧氏距离聚类，那种类间距离最 好，可以计算五个复合相关系数：好，可以计算五个复合相关系数： R=cophenet(z1,d1),cophenet(z2,d1), cophenet(z3,d1),cophenet(z4,d1), cophenet(z5,d1) 结果为：结果为：0.8413 0.8571 0.8623 0.8622 0.8532 由于由于0

51、.8623 最大，故认为若样品之间采用欧最大，故认为若样品之间采用欧 氏距离，则类间距离以中间距离最好，如果我氏距离，则类间距离以中间距离最好，如果我 们要找到最理想的分类方法，可以对每一种样们要找到最理想的分类方法，可以对每一种样 品之间的距离，都计算上述的复合相关系数，品之间的距离，都计算上述的复合相关系数， 这样就可以找到最理想的样品距离与对应的类这样就可以找到最理想的样品距离与对应的类 间距离。间距离。 a=28 ,18,11 , 21 ,26, 20 ,16, 14, 24 ,22 29, 23, 22, 23, 29, 23, 22, 23, 29, 27 28 ,18, 16,

52、22, 26 ,22,22 ,24, 24,24; 对对a的各列进行聚类，如何计算复合相关系的各列进行聚类，如何计算复合相关系 数数 d=pdist(a);pdist(a,mahal);pdist(a,cityblock); pdist(a,seuclid);pdist(a,minkowski,0.4); for i=1:5 d1=linkage(d(i,:); r1(i)=cophenet(d1,d(i,:); end for i=1:5 d2=linkage(d(i,:),complete);r2(i)=cophenet(d2,d(i,:); end for i=1:5 d3=linkag

53、e(d(i,:),average) ;r3(i)=cophenet(d3,d(i,:); end for i=1:5 d4=linkage(d(i,:),centroid);r4(i)=cophenet(d4,d(i,:); end for i=1:5 d5=linkage(d(i,:),ward);r5(i)=cophenet(d5,d(i,:); end r=r1;r2;r3;r4;r5; 4.3 快速聚类法快速聚类法 快速聚类法又称为快速聚类法又称为动态聚类法动态聚类法，该方法首先将样，该方法首先将样 品进行粗糙分类，然后依据样品间的距离按一定规品进行粗糙分类，然后依据样品间的距离按一定

54、规 则进行调整，直至不能调整为止则进行调整，直至不能调整为止.该方法适用于样品该方法适用于样品 数量较大的数据集的聚类分析，但是需要事先给定数量较大的数据集的聚类分析，但是需要事先给定 聚类数目，此数目对最终聚类结果有很大影响，实聚类数目，此数目对最终聚类结果有很大影响，实 际应用时要选择多个数目进行分类，然后找出合理际应用时要选择多个数目进行分类，然后找出合理 的分类结果的分类结果. 4.3.1 快速聚类的步骤快速聚类的步骤 1. 选择聚点选择聚点 聚点是一批有代表性的样品，他的选择决定了聚点是一批有代表性的样品，他的选择决定了 初始分类，并对最终分类有很大影响，选择聚点初始分类，并对最终分

55、类有很大影响，选择聚点 之前要先确定聚类数之前要先确定聚类数k. 通常，有以下确定聚点的方法：通常，有以下确定聚点的方法： 经验确定：对样品非常熟悉，根据经验确定经验确定：对样品非常熟悉，根据经验确定k 个样品作为聚点个样品作为聚点. (比如确定种子队比如确定种子队) 将将n个样品随机地分为个样品随机地分为k类，然后以每一类的均类，然后以每一类的均 值向量作为聚点值向量作为聚点. 最小最大原则：若最小最大原则：若n个样品分为个样品分为k类，先选择所类，先选择所 有样品中距离最大的两个样品有样品中距离最大的两个样品xi1, xi2为两个初始聚为两个初始聚 点，即点，即d(xi1,xi2)=max

56、(dij),然后选择第然后选择第3个聚点个聚点xi3， 使得该点到上述两点距离最小是所有其它点到上述使得该点到上述两点距离最小是所有其它点到上述 两点距离最小中最大者，即两点距离最小中最大者，即 mind(xi3,xir),r=1,2=maxmind(xj,xr),r=1,2 按照同样的原则选取按照同样的原则选取xi4，依次下去，直至选出，依次下去，直至选出k 个聚点个聚点xi1,xi2,xik 序号序号国家国家199019952000 1澳大利亚澳大利亚1249.391273.611282.68 2巴西巴西821.6859.85919.73 3加拿大加拿大1641.011591.541608

57、.32 4中国中国1330.451382.681462.08 5法国法国1546.551501.771525.95 6德国德国1656.521630.521570.69 7印度印度861.30862.51945.11 8意大利意大利1321.771232.31243.51 9日本日本1873.681949.891851.20 10俄罗斯俄罗斯1475.161315.871297 11南非南非794.25787.48782.38 12英国英国1486.751441.711465.12 13美国美国2824.292659.642740.12 前前 例例2中，分成中，分成4类用不同方法确定聚点类用不同方法确定聚点 人为确定：澳大利亚、中国、英国、美国人为确定：澳大利亚、中国、英国、美国 首先按照亚非洲、美洲、欧洲、大洋洲分首先按照亚非洲、美洲、欧洲、大洋洲分 为四类，以每一类的均值向量作为聚点为四类，以每一类的均值向量作为聚点. 最小最大准则最小最大准则(a为原始数据矩阵）为原始数据矩阵） m,n=size(a); for i=