第3章-聚类分析m课件.ppt

1、1第三章聚类分析 Cluster Analysis把对象分类本章内容本章内容 第一节第一节 聚类分析的基本思想聚类分析的基本思想 第二节第二节 距离和相似系数距离和相似系数 （难点）（难点） 第三节第三节 系统聚类法（系统聚类法（ 重点、难点）重点、难点） 第四节第四节 K-均值聚类均值聚类 第五节第五节 有序样品的聚类有序样品的聚类 第六节第六节 计算步骤及在经济管理中的应用计算步骤及在经济管理中的应用3 第一节第一节 聚类分析的基本思想聚类分析的基本思想一、什么是聚类分析一、什么是聚类分析 二、聚类分析的目的二、聚类分析的目的三、聚类的种类三、聚类的种类四、聚类分析的主要步骤四、聚类分析的

2、主要步骤 俗话说：“物以类聚，人以群分”，在社会、经济、管理、气象、地质、人口、考古等众多领域，都存在着大量的分类研究问题。 不同地区城镇居民收入和消费状况的分类研究； 区域经济及社会发展水平的分析及全国区域经济综 对某城市按大气污染的轻重分成几类区域； 对某年级学生按学习成绩的好差分成几等；合评价；在儿童生长发育研究中，把以形态学为主的指标归于一类，以机能为主的指标归于另一类5 u当有一个分类指标时，分类比较容易。u但是当有多个指标，要进行分类就不是很容易了。u比如，要想把中国的县分成若干类，可以按照自然条件来分：考虑降水、土地、日照、湿度等各方面；u也可以考虑收入、教育水准、医疗条件、基础

3、设施等指标；u由于不同的指标项对重要程度或依赖关系是相互不同的，所以也不能用平均的方法，因为这样会忽视相对重要程度的问题。 在古老的分类学中，人们主要靠经验和专业知识进行定性的分析，很少利用数学工具进行定量的分类。许多分类往往带有主观性和任意性，不能揭示客观事物的内在本质差别和联系。 7 随着人类科学技术的发展，对分类的要求越来越高，仅凭经验和专业知识难以确切的进行分类，数学工具引用到分类学中 数值分类学, 又将多元分析的技术引入到数值分类学聚类分析.聚类分析就是研究聚类分析就是研究“物以类聚物以类聚”的一种多元统计方法。的一种多元统计方法。最早的聚类分析是由考古学家在对考古分类研究中发展起来

4、的，同时又应用于昆虫的分类中，此后又广泛地应用在天气、生物等方面。8一、什么是聚类分析？一、什么是聚类分析？ 聚类分析是一种分类技术，又称群分析、点群分析、簇群分析，它是研究如何对事物进行分类的一种多元统计方法。这种方法的特点是只根据事物本身的特征分类，即将事物性质相近的归为一类，性质的差异较大的归在不同的类。所谓“类”，通俗地说就是相似元素的集合。分类，是将一个观测对象指定到某一类（组）。9 以分类对象为标准，可以将变量（指标）分类R型型聚类分析聚类分析（如在儿童的生长发育研究中，把以形态学为主的指标归于一类，以机能为主的指标归于另一类等） ，但更多的应用是将样品（个体）分类Q型聚类分析型聚

5、类分析（如对我国人口的文化程度状况进行分析） 。 这两种聚类在数学上是对称的，没有什么不同。这两种聚类在数学上是对称的，没有什么不同。本章主要讨论章主要讨论Q型聚类分析问题。型聚类分析问题。10 认为：我们所研究的样品或指标（变量）之间存在着程度不同的相似性（亲疏关系），于是：（1）根据一批样品的多个观测指标，具体找出一些能够度量样品或变量（指标）之间相似程度的统计量；（2）以这些统计量为划分类型的依据，建立一种分类方法，将一批样品或变量（指标），按照它们在性质上的亲疏、相似程度进行分类。分类11聚类分析的基本思想聚类分析的基本思想相近的聚为一类相近的聚为一类( (以距离表示，样品聚类以距离表

6、示，样品聚类) )相似的聚为一类相似的聚为一类( (以相似系数表示，变量聚类以相似系数表示，变量聚类) ) 聚类分析适用于对事物类别的面貌尚不清楚，甚至在事前连总共有几类都不能确定的情况下进行分类的场合。 与多元分析的其它方法比，聚类分析方法较为粗糙，理论上还不够完善，但应用方便、因此被广泛使用.13把相似的研究对象归成类把相似的研究对象归成类 二、聚类分析的目的二、聚类分析的目的 在一些社会、经济问题中，我们面临的往往是比较复杂的研究对象，如果能把相似的样品（或变量）归成类，处理起来就大为方便。说得简单一点，聚类就是把事物按其相似程度进行分类，并寻找不同类别事物特征的分析工具。 三、聚类的种

7、类三、聚类的种类根据分类的原理根据分类的原理系统聚类系统聚类快速聚类快速聚类根据分类的对象根据分类的对象变量聚类变量聚类clustering for variablesclustering for variables 样品聚类样品聚类clustering for individualsclustering for individuals15四、聚类分析的主要步骤 一般来说，聚类分析至少都应该包括以下四个步骤： 1、选择变量：因为聚类分析是根据所选定的变量对研究对象进行分类，聚类的结果仅仅反映了所选定变量所定义的数据结构。聚类中选择变量的要求：u和聚类分析的目标密切相关u反映了要分类对象的特征u

8、变量之间不应该高度相关162、计算相似性：选定了聚类变量，下一步就是计算研究对象之间的相似性，相似性是聚类分析中的一个基本概念，它反映了研究对象之间的亲疏程度，聚类分析就是根据研究对象之间的相似性来进行分类的。3、聚类：选定聚类方法；确定形成的类数。4、聚类结果的解释和证实。一、数据的变换一、数据的变换二、距离二、距离样品间相似性的测度样品间相似性的测度三、相似系数三、相似系数变量之间相似性的测度变量之间相似性的测度四、距离和相似系数选择的原则四、距离和相似系数选择的原则17第二节第二节 相似性测度相似性测度距离和相似系数 聚类分析实质上是寻找一种能客观反映元素之间亲疏关系的统计量，然后根据这

9、种统计量把元素分成若干类。描述样品（或变量）间亲疏、相似程度的统计量很多，目前用得最多的聚类统计量是距离和相似系数，距离系数一般用于对样品分类，而相似系数一般用于对变量聚类。 19在聚类分析中，一般的规则是将“距离”较小的点或“相似系数”较大的点归为同一类，将“距离”较大的点或“相似系数”较小的点归为不同的类。20 在进行聚类分析时，样品间的距离和相似系数有各种不同的定义，而这些定义与变量的类型密切相关，根据变量取值的不同，变量特性的测量尺度有以下三种类型（定量、定性）：211、间隔尺度、间隔尺度（定量变量）-指标度量时用数量来表示。其数值由测量、计数或统计所得到，如长度、重量、经济统计数字、

10、抽样调查数据等；2、顺序尺度、顺序尺度（定序变量、定性变量） 指标度量时没有明确的数量表示，只有次序（等级）关系，如产品质量，分为一等品、二等品、三等品等 ；3、名义尺度、名义尺度（定类变量、定性变量）-具有该种特性的变量在度量时既没有数量表示，也没有次序关系，而只有性质上的差异（用一些类表示），如性别、职业等。22 不同类型的变量，在定义距离和相似系数时，其方法有很大差异。 在实际应用中，研究比较多的是间隔尺度，本章主要讨论具有间隔尺度变量的样品聚类分析方法。目前已设计了大量的相似系数和距离（40种）；但在数值分类中较常用的是少数。23一、数据的变换 由于样本数据矩阵往往由多个指标（即变量）

11、构成，不同指标一般都有不同的量纲，并且有不同的数量级单位，为了使不同量纲、不同数量级的数据能放在一起进行比较，通常需要对数据进行变换处理。24常用的变换方法1.中心化变换 一种标准化处理方法，先求出每个变量的样本平均值，再从原始数据中减去该变量的均值，变换后数据的均值为0，而协差阵不变。25常用的变换方法为变量个数。为样品个数，其中：设原始观测数据阵为：pnxxxxxxxxxXnpnnpp21222211121126常用的变换方法pjxnxpjnixxxxniijjjijijij, 2 , 1121211其中：，；，则有：设变换后的数据为27常用的变换方法2.标准化变换 主要是对变量的属性进行

12、变换处理。首主要是对变量的属性进行变换处理。首先对变量进行中心化变换，然后用该变量的先对变量进行中心化变换，然后用该变量的标准差进行标准化。标准差进行标准化。 变换后每个变量的样本均值为变换后每个变量的样本均值为0 0，标准，标准差为差为1 1，且变换后的数据与变量的量纲无关。，且变换后的数据与变量的量纲无关。在抽样样本改变时，它仍保持相对稳定性。在抽样样本改变时，它仍保持相对稳定性。28常用的变换方法即：pjxxnspjxnxpjnisxxxnijijjniijjjjijij，其中：，；，211121121212112129常用的变换方法3.规格化变换 规格化变换是从数据矩阵的每一个变量中找

13、出其最大值和最小值，这两者之间的差值称为极差，然后从每个变量的每个原始数据中减去该变量中的最小值，再除以极差，就得到规格化数据。30常用的变换方法即有： pjnixxxxxijniijniijniijij，；，2121minmaxmin11131常用的变换方法注：经过规格化变换以后，数据矩阵中每列即每个变量的最大数值为1，最小数值为0，其余数据取值均在01之间。并且变换后的数据都不再具有量纲，便于不同变量之间的比较。32常用的变换方法4.对数变换对数变换是将各个原始数据取对数，将原始数据的对数值作为变换后的新值。即：对数变换可将具有指数特征的数据结构化为线性数据结构。 0,logijijijx

14、xx二、距离样品间相似性的测度 对于样品之间的聚类即Q型聚类分析，常用距离来测度样品之间的相似程度。341.定义距离的准则定义距离的方法很多，但是不论用什么方法来定义距离，都必须遵循一定的规则。个样品之间的距离个样品和第示第表并且用个指标个样品的第表示第用jidlixijil,35一般来说，距离dij要求满足如下四个条件。都成立（三角不等式），对一切）（都成立（对称性）；，对一切）（；的各指标值都相同，即与样品，样品）（都成立；，对一切）（kjidddjiddjijidjidkjikijjiijijij43020136注：如果所定义的距离不满足第四个条件，则称该距离为广义距离；距离。均成立时，

15、则称为极端，式对一切，该不等，当第四个条件加强为kjidddkjikijmaxu首先我们看样本数据： 个样品之间的距离个样品与第表示第jiij设：dx，即XxxxxxxxxxXpnijnpn2n12p22211p12112.常用的距离38当q=1时：绝对距离绝对距离当q=2时：欧氏欧氏(Euclidean)距离距离1(1)pijikjkkdxx 1 221(2)pijikjkkdxx Minkowski距离）距离）：（最直观的距离）11( ) qpqijikjkkdqxx （通用的距离测度公式）1( )max ijikjkkpdxx 当q=时：切比雪夫切比雪夫(Chebychev)距离距离 明

16、氏距离特别是其中的欧氏距离是聚类分析中用得最广泛的距离，但是有一些缺点：一方面距离与各变量的量纲有关，而各指标计量单位的选择有一定的人为性和随意性。另一方面，没有考虑指标之间的相关性。例如：对长度和重量进行测量，采用不同单位，其距离测量的结果不同。 22221112)()(2)dyxyx41当长度当长度=cm时：时：CDAB22CD22ABdd1250)(105)(0d1010)(110)(0d42当长度当长度=mm时：时：CDAB22CD22ABdd26000)(1050)(0d100010)(1100)(0d43通常改进办法有两个： 当各指标的测量值相差悬殊时，先对数据标准化，用标准化后的

17、数据计算距离。 标准化后的数据，每个变量的样本均值为0，标准差为1，与变量的量纲无关；常用的聚类分析软件中都有这项功能，可以自动完成常用的聚类分析软件中都有这项功能，可以自动完成。4445对指标的相关性作了考虑且不受测量单位影响的距离是马氏距离（Mahalanobis)。 下面用一个一维的例子说明欧氏距离与马氏距离在概率上的差异。 设有两个正态总体， 现给定一个样品位于A处，试问A处的样品离哪一个总体较近。从图上看出，若按欧氏距离来度量，A点离 的中心 要比离 的中心 “近一些”，但是从概率论的角度来看，A点位于 右侧约 处，而位于 左侧约 处，那么应该认为A点离 要比离 “近一些”。显然，后

18、一种度量更为合理.它是用坐标差平方除以方差（或乘以方差的倒数），从而化为无量纲数，推广到多维就要乘以协方差阵25 . 2念。，这就是马氏距离的概的逆矩阵148设，考虑点X到22222111，NGNGG1、G2的相对距离：222222121221),(xGdxGdxx），（492222122121)()(),(1)()(),(XXXGXpXXGXGXXXXppGddpnnijp时，则有当的马氏距离定义为：与总体，则样品，协差阵为），（个指标），均值向量为维总体（考察为设总体50 其中，Xi、Xj 分别为第i个样品 和第j个样品的p个指标观测值所组成的向量， 为观测变量之间的协方差阵的逆矩阵。定义

19、Xi，Xj两点之间的马氏距离为：1jijiijXXXXMd1251注：1.马氏距离又称为广义欧氏距离（generalized Euclidean distance）。2.马氏距离考虑了观测变量之间的相关性。如果假定各变量之间相互独立，即观测变量的协方差矩阵是对角矩阵，则马氏距离就退化为欧氏距离。52为了对马氏距离和欧氏距离进行一下比较，以便更清楚地看到二者之间的区别和联系，现在考虑一个例子。例如：假设有一个二维正态总体，它的分布为：19 . 09 . 01,002N 的距离。，总体均值点各自到和计算这两点用马氏距离和欧氏距离，现分别和并且还已知有两点001, 11 , 1BABA53计算总体协

20、差阵的逆矩阵19 . 09 . 0119. 01154分别计算出点A和点B各自到总体均值点的马氏距离的平方分别为：05. 119. 02 . 0111 . 01 . 019. 011119 . 09 . 011119. 01111112MdA 2019. 08 . 3119 . 19 . 119. 011119 . 09 . 011119. 01111112MdB55点A和点B分别到总体均值点的欧氏距离的平方为： 201012201012222222BAdd56可见，按欧氏距离计算，点A和点B各自到总体均值点的距离相等；而按马氏距离计算，两者相差很多。在本例中总体变量的分布密度是：而点A和点B

21、两点的密度分别是：说明前者应当离均值点近，后者离均值点远，马氏距离正确地反映了这一情况。222121218 . 138. 01exp19. 021,xxxxxxf 00001658. 01, 1,2157. 01 , 1ff 马氏距离的不足之处是公式中的（样品协方差矩阵），若始终不变，则往往显得不妥；若要随聚类过程而不断变化，则有许多不便。因此在实际聚类分析中，马氏距离也不是理想的距离。 58兰氏距离仅适用于一切xij0的情况。兰氏距离克服了明氏距离与各指标的量纲有关的缺点，且对大的奇异值不敏感，适合高度偏倚的数据，但也没考虑变量间的相关性。 兰氏兰氏(Lance&Williams )(Lan

22、ce&Williams )距离距离11()pikjkijkikjkxxdLpxx 以上几种距离的定义均要求变量是间隔尺度的，如果使用的变量是有序尺度或名义尺度的，则有相应的一些定义距离的方法。 通常人们还是喜欢应用欧氏距离聚类。60三、相似系数事物之间相似性的测度事物之间相似性的测度 聚类分析方法不仅用来对样品进行分类，对样品进行分类，而且可用来对对变量（指标）进行分类变量（指标）进行分类，在对变量进行分类时，常常采采用相似系数来度量变量之间的相似性。用相似系数来度量变量之间的相似性。相似系数相似系数是衡量变量之间相似程度的一个量，变量之间的关系越是密切，其相似系数越接近于1（或-1）；反之，

23、它们的关系越是疏远，其相似系数越接近于0聚类时，比较相似的变量倾向于归为一类，不怎么相似的变量归属不同的类。611.1.相似系数相似系数c cijij应满足的条件应满足的条件10101) 1 (ijijjijiijcacaaxxxxc时，；而时，则且，成比例，即若与，若变量都成立，对一切jicij1)2(都成立，对一切jiccjiij)3( 2.2.常用的相似系数常用的相似系数相似系数的定义和计算方法视观测变量的性质的不同而不同，名义尺度变量和顺序尺度变量的取值与间隔尺度变量的取值方法不同，因而计算相似系数的方法也不同。对于间隔尺度，最常用的相似系数有两种：夹角余弦和相关系数来表示。的相似系数

24、用与变量ijjiCXX63（1）夹角余弦）夹角余弦夹角余弦是从向量几何的角度所定义的一种夹角余弦是从向量几何的角度所定义的一种测度变量间亲疏程度的相似系数。测度变量间亲疏程度的相似系数。 1ijC64余弦函数）。的观测向量之间夹角的的观测向量与变量维空间中变量数（它是似系的余弦称为两向量的相夹角和量，则维空间的向看成次观测值的和变量次观测值的变量jiijjinjjjjniiiixxnxxnxxxnxxxxnx,2121夹角余弦夹角余弦cosine 尽管图中AB和CD 长度不一样，但形 状相似。当长度不 是主要矛盾时，就 可利用夹角余弦这 样的相似系数。66 nkkjnkkinkkjkijjii

25、jiijijxxxxxxxxxxC12121cos11cos1ij在上式中，显然有67把所有两两变量的相似系数都计算出来，可排成相似系数矩阵：1coscoscoscoscoscoscoscoscoscoscoscos2211212222111211pppppppp其中68该矩阵是一个实对称阵，所以只需计算上三角形部分或下三角形部分。根据该矩阵可以对p个变量分类，把比较相似的变量归为一类，把不怎么相似的变量归为不同的类。（2）相关系数这是前面已经有过的大家最熟悉的统计量，它是将样本观测数据中心化或标准化后的夹角余弦。相关系数常用rij表示，为了和其它相似系数记号统一，记为Cij（2）6970 2

26、1121212nkjkjnkikinkjkjikiijijxxxxxxxxrC其中：nkkjjnkkiixnxxnx1111，71把两两变量的相关系数都计算出来，可形成变量相关系数矩阵。1rrrrrrrrrrrr)(Rpp2211ppp2p12p22211p1211其中ijr72若需要用距离来测度变量间的亲疏程度，则变量之间常借助于相似系数来定义距离。例如可定义变量xi与变量xj之间的距离为：221ijijcd73四、距离和相似系数选择的原则四、距离和相似系数选择的原则1.所选择的亲疏测度指标在实际应用中应有明确的意义。如在经济变量分析中，常用相关系数表示经济变量之间的亲疏程度。2.亲疏测度指

27、标的选择要综合考虑已对样本观测数据实施了的变换方法和将要采用的聚类分析方法。例如：在标准化变换之下，夹角余弦实际上就是相关系数。3.适当地考虑计算工作量的大小。74第三节 系统聚类法本节内容本节内容系统聚类法的基本思想系统聚类法的基本步骤系统聚类分析的方法系统聚类法的性质 系统聚类法是诸聚类分析方法中使用最多的一种，它是将类由多变到少的一种方法。本节的重点和难点是各种聚类分析方法的介绍注意各种聚类分析方法的异同点异同点不同点不同点距离定义的区别；相同点相同点归类步骤基本一致。系统聚类法的基本思想 考虑n个样品的聚类问题，系统聚类方法的基本思想是： 开始将n个样品各自作为一类，并规定样品之间的距

28、离和类与类之间的距离（这时类间的距离与样品间的距离是相同的），然后将距离最近的两类合并成一个新类，并计算新类与其它类的类间距离；再将距离最近的两类合并，这样每次减少一类，直到所有的样品合并成一类为止。 本节介绍常用的几种系统聚类方法，所有这些聚类方法的区别在于类与类之间距离的计算方法不同。77系统聚类法的基本步骤 （0）数据变换-为了便于比较、计算上的方便或改变数据的结构；选择度量样品间距离的定义（如欧氏距离）及度量类间距离的定义（如最短距离法）； （1）计算n个样品两两间的距离 ，得样品间的距离矩阵D(0)；ijd78系统聚类法的基本步骤 （2）一开始（第一步)，n个样品各自构成一类，这时类

29、的个数k=n个类，即每一类 ; 此时，类间的距离就是样品间的距离（即D(1) =D(0)； （3）合并距离最近的两类为一新类； niXGii, 2 , 1系统聚类法的基本步骤（4）计算新类与当前其它各类的距离，得到新的距离矩阵D(i)，若合并后类的总个数k大于1，重复（3）和（4）步，直到类的个数为1时止；（5）画谱系聚类图； 谱系聚类图是一种类似于树状结构的图形，由谱系聚类图可清楚地看出全部样品的聚集情况。（6）决定类的个数及各类的成员。80系统聚类法的步骤系统聚类法的步骤可选择适当的距离，计算距离可选择适当的距离，计算距离把每个样品看成一类，构造把每个样品看成一类，构造n个类个类合并最近的

30、两类为一新类合并最近的两类为一新类计算新类与当前各类的距离计算新类与当前各类的距离判断判断画聚类图画聚类图根据实际情况，确定类和类的个数根据实际情况，确定类和类的个数仅有一个类仅有一个类不是仅有一个类不是仅有一个类采用系统聚类法采用系统聚类法1.最短距离法(single linkage) 2.最长距离法(complete linkage) 3.中间距离法(median method)4.类平均法(average linkage)5.可变类平均法(flexible-beta method)6.重心法(centroid method)7.可变法8.Ward离差平方和法(Wards minimum-

31、variance method)9.Mcquitty的相似分析法(Mcquittys similarity analysis)10.最大似然估计法(EML)11.密度估计(density linkage)12.两阶段密度估计法(two-stage density linkage) B2A2 * B1 A1 * * B3 *样品间样品间：欧氏距离类类间类类间：两类间两两样品距离最短。即图中样品A2和B1之间的距离. 它的聚类算法是把两个类之间的距离定义为一个类的所有个体与另一个类的所有个体之间距离的最小者。 84类间距离类间距离B1B3B2A1A2最短距离(single linkage)85定义

32、类Gi与Gj之间的距离为两类最近样品的距离，即dDijijGxGxjjii,min 将Gp和Gq合并成一个新类，记为Gr，则任一类Gk与Gr的距离是：),min(min,minminmin,kqkpijGxGxijGxGxijGxGxkrDDdddDqjkipjkijjii86使用最短距离法的聚类步骤如下： 。一类，这时显然开始每个样品都自成，它是一个对称矩阵。个样品的距离矩阵，计算）规定样品之间的距离（pqpqdDDn01 qprrqppqGGGGGGDD,20，即合并为一个新类，记为和，则将中的最小元素，设为）选择（87 。，所得矩阵记为列，新行新列对应着列合并成一个新行新列与行和行与中的

33、将，间的距离为）计算新类与任一类之（10,min3DGqpqpDDDDrkqkpkr 一类为止。直至所有的元素合并成，如此下去的步骤得重复施行对于）对（2014DDD 以同时合并。应这些最小元素的类可，则对中最小的元素不止一个如果某一步mD88最短距离法Nearest Neighbor例1：设抽取五个样品，每个样品只测一个指标，它们是1，2，3.5，7，9，试用最短距离法对五个样品分类。kqkpkrDDD,min89G1 G2 G3 G4 G5G1G2G3G4G50 1 02.5 1.5 06 5 3.5 0 8 7 5.5 2 0G6 G3 G4 G5G6G3G4G50 1.5 05 3.5

34、 07 5.5 2 0 G7 G4 G5G7G4G5 0 3.5 0 5.5 2 0 G7 G8G7G8 0 3.5 090例例2: 6个不同民族的标化死亡率与出生时的期望寿命 民族原始数据标准化数据标化死亡率()出生时期望寿命(岁)标化死亡率()出生时期望寿命(岁)满族 5.8070.59-1.59 1.44朝鲜族 7.4467.14-0.62 0.73蒙古族 8.1165.48-0.22 0.38维吾尔族10.2158.88 1.03-0.99藏族 9.5159.24 0.61-0.91哈萨克族 9.81 60.47 0.79-0.66均数8.480063.6333 0.00 0.00标准

35、差1.68664.8167 1.00 1.0091各民族之间的欧氏距离各民族之间的欧氏距离( (标准化资料标准化资料) )D D0 0 满族朝鲜族蒙古族维吾尔族藏族哈萨克族G1=S1G2=S2G3=S3G4=S4G5=S5G6=S6满族G1=S10朝鲜族G2=S21.2080蒙古族G3=S31.7320.5260维吾尔族G4=S43.5702.3741.8510藏族G5=S53.2242.0481.5390.4220哈萨克族G6=S63.1731.9731.4480.4060.311092D1 G1=S1G2=S2G3=S3G4=S4 G7=S5,S6G1=S10G2=S21.2080G3=S

36、31.7320.5260G4=S43.5702.3741.8510G7=S5,S63.1731.9731.4480.406093D2G1=S1G2=S2G3=S3G8=S4,S5,S6G1=S10G2=S21.2080G3=S31.7320.5260G8=S4,S5,S63.1731.9731.448094D3G1=S1G9=S2,S3G8=S4,S5,S6G1=S10G9=S2,S31.2080G8=S4,S5,S63.1731.448095D4G10=S1,S2,S3G8= S4,S5,S6G10=S1,S2,S3 0G8= S4,S5,S61.448096例例2资料的谱系聚类图资料的谱系

37、聚类图(最短距离法最短距离法) Dendrograms (cluster trees) 0.3110.4060.5261.2081.448藏族哈萨克族 维吾尔族 朝鲜族 蒙古族 满族 B2A2 * B1 A1 * * B3 *样品间样品间：欧氏距离类类间类类间：两类间样品两两距离最长。即图中样品A2和B3之间的距离 最长距离法的聚类算法是把两个类之间的距离定义为一个类的所有个体与另一个类的所有个体之间的距离最大者，但并类的标准仍采用它与其它类的最小距离。 100最长距离(complete linkage)类间距离类间距离B1B3A1A2B2101最长距离法Furthest Neighbor最长

38、距离法与最短距离法的并类步骤完全一样，也是将各样品先自成一类，然后将非对角线上最小元素对应的两类合并。ijGxGxpqjidDGGqjpi,max的距离，即样品之间的距离为两类最远与类定义类102kqkpijGxGxijGxGxijGxGxkrrkrqpDDdddDGGGGGqjkipjkirjki,maxmax,maxmaxmax,表示为的距离用最长距离公式与，则任一类合并为与设某一步将类103注：最长距离法与最短距离法只有两点不同：（1）类与类之间的距离定义不同；（2）计算新类与其他类的距离所用的公式不同例1：设抽取五个样品，每个样品只测一个指标，它们是1，2，3.5，7，9，试用最长距离

39、法对五个样品分类。104G1 G2 G3 G4 G5G1G2G3G4G50 1 02.5 1.5 06 5 3.5 0 8 7 5.5 2 0G6 G3 G4 G5G6G3G4G50 2.5 06 3.5 08 5.5 2 0 G7 G6 G3G7G6G3 0 8 0 5.5 2.5 0 G7 G8G7G8 0 8 0105例例2:2:6个不同民族的标化死亡率与出生时的期望寿命民族原始数据标准化数据标化死亡率()出生时期望寿命(岁)标化死亡率()出生时期望寿命(岁)满族 5.8070.59-1.59 1.44朝鲜族 7.4467.14-0.62 0.73蒙古族 8.1165.48-0.22 0

40、.38维吾尔族10.2158.88 1.03-0.99藏族 9.5159.24 0.61-0.91哈萨克族 9.81 60.47 0.79-0.66均数8.480063.6333 0.00 0.00标准差1.68664.8167 1.00 1.00106各民族之间的欧氏距离各民族之间的欧氏距离(标准化资料标准化资料)D0 满族朝鲜族蒙古族维吾尔族藏族哈萨克族G1=S1G2=S2G3=S3G4=S4G5=S5G6=S6满族G1=S10朝鲜族G2=S21.2080蒙古族G3=S31.7320.5260维吾尔族G4=S43.5702.3741.8510藏族G5=S53.2242.0481.5390.

41、4220哈萨克族G6=S63.1731.9731.4480.4060.3110107D1 G1=S1G2=S2G3=S3G4=S4 G7=S5,S6G1=S10G2=S21.2080G3=S31.7320.5260G4=S43.5702.3741.8510G7=S5,S63.2242.0481.5390.4220108D2G1=S1G2=S2G3=S3G8=S4,S5,S6G1=S10G2=S21.2080G3=S31.7320.5260G8=S4,S5,S63.5702.3741.8510109D3G1=S1G9=S2,S3G8=S4,S5,S6G1=S10G9=S2,S31.7320G8=

42、S4,S5,S63.5702.3740110D4G10=S1,S2,S3G8= S4,S5,S6G10=S1,S2,S3 0G8= S4,S5,S63.5700111例例2资料的谱系聚类图资料的谱系聚类图(最长距离法最长距离法) Dendrograms (cluster trees) 0.3110.4220.5261.7323.570 藏族哈萨克族 维吾尔族 朝鲜族 蒙古族 满族 最长距离夸大了类间距离，最短距离低估了类间距离。类与类之间的距离既不取两类最近样品间的距离，也不取两类最远样品间的距离，而是取介于两者中间的距离，称之为中间距离法。PQKR113G Gk kG Gp pG Gq qD

43、 DkpkpD DpqpqD Dkqkq 这就是中间距离法的递推公式。2222412121pqkqkpkrDDDDDkr的计算公式为：由初等平面几何可知，边的中线作为为边组成的三角形，取和、，考虑由，对于任一类合并为和设某一步将krkrpqpqkqkpkrqpDDDDDDGGGG114注：由于距离公式中的量都是距离的平方，为了计算上的方便，可将表D(0)、D(1)、D(2)、中的元素，都用相应元素的平方代替，而得表。、2)2(2)1(2)0(DDD B2A2 * B1 A1 * * B3 * 类类间的距离用各自重心间的距离表示 这种系统聚类法称为重心法。116类与类之间的距离定义为它们的重心（

44、均值）之间的(平方）欧氏距离。qpDpq22之间的平方距离为：和，则和的重心分别为和设qpqpqpGGXXGG117公式。时，即为中间距离法的显然，当qppqrqrpkqrqkprpkrnnDnnnnDnnDnnD2222这就是重心法的距离递推公式。距离为的平方与任一类个样品，显然，新类、，它们各有、，它们的重心分别为合并为和将设某一步krqprrqpqqpprrrqprqpGGnnnnnnXnXnnXXXXGGG1,118重心法在处理异常值方面比其它系统聚类法更稳健，但是在别的方面一般不如类平均法或离差平方和法的效果好。重心法的谱系树状图可能重叠凌乱，而且它的递推公式中各距离的系数改变频繁，

45、计算比较麻烦。SPSS作为默认方法，称为 between-groups linkage。 PQKR重心法虽然有较好的代表性，但并未充分利用各样品的信息，因此苏克和米切尔提出了类平均法，又称为平均联结法。120 类与类之间的平方距离定义为这两类元素两两之间距离平方的平均，即 piqjGxGxijqppqdDnn221称这种系统聚类法为类平均法。的样品个数和分别为类和其中：qpqpGGnn121类间距离类间距离B1B3B2A1A2平均距离(average)(61235234225224215214212ddddddD 122的距离为与，则任一类，且有，即合并为类和设某一步将类rkqprqprrqp

46、GGnnnGGGGGG222kqrqkprpkrDnnDnnD类平均法较好地利用了所有样品之间的信息，在很多情况下它被认为是一种比较好的系统聚类法。123类平均法。充分。为此，给出可变的距离，信息利用的不之间与括之间的距离，而没有包与和与式中，只有类平均法的距离递推公qpqkpkGGGGGG124可变类平均法的距离递推公式为：1112222是可变的，且，其中：qprqprpqkqrqkprpkrnnnGGGDDnnDnnD41取都取负值。一般地，选通常（七）可变法 可变法是兰思和威廉姆斯在研究统一的组合模型时，从代数角度给出的一种系统聚类方法。在可变类平均法中，若不考虑Gp和Gq两类中各自样品

47、的个数，而是将两类同等看待，则就得到了可变法。126可变法的距离递推公式为：222221pqkqkpkrDDDD为上式。，即中取显然，在可变类平均法。常取。实际应用中，经是可变的，且其中21411rqrpnnnn（八）Ward离差平方和法(Ward minimum variance method) 离差平方和法是由沃德（Ward，1936）提出，其思想来源于方差分析。如果类分得合理，同类样品之间的离差平方和应当较小，类与类之间的离差平方和应当较大。128 ktnittittikttnittittitttttttittikttXXXXSSkXXXXSGGXGnpXiGXGGGGkn1111321

48、:为个类的类内离差平方和中样品的离差平方和为则的重心，是中的样品个数，表示量），维向是个样品（注意中的第表示用，类：个样品分成设将129 Ward法的基本思想是，先将n个样品各自成一类，此时总离差平方和S=0,然后每次将其中某两类合并为一类，因为每缩小一类离差平方和就要增大，每次选择使S增加最小的两类进行合并(因为如果分类正确，同类样品的离差平方和应当较小）直到所有的样品归为一类为止。130较大。应当较小，否则，应当和并后所增加的离差平方这两类相距较近，则合与样品的分散程度。若，它们反映了各自类内、和分别为，它们的类内离差平方，合并为新类与，某一步将类和设有类qprqprqpqprqpqpSS

49、SGGSSSGGGGGGG法。差平方和法或这种系统聚类法称为离之间的平方距离为：和的平方距离，即令的离差平方和看成类间法把这两类合并后增加WardSSSDGGWardqprpqqp21312222pqkrkkqkrqkkpkrpkkrDnnnDnnnnDnnnnD 可以推得离差平方和法的平方距离递推公式： 注：离差平方和法样品间的距离必须采用欧氏距离。 上面介绍的几种系统聚类法，并类的原则和步骤基本一致，所不同的是类与类之间的距离有不同的定义，依此所给出的新类与任一类的距离公式不同。其实可以把这几种方法统一起来，有利于在计算机上灵活地选择更有意义的谱系图（有利于计算机程序的编制）。133 兰思

50、（Lance）和威廉姆斯（Williams）在1967年发现它们的距离递推公式可以统一起来，并提出了统一公式。222222kqkppqkqqkppkrDDDDDD形式是：的距离递推公式的统一与其他任意一类，则，即合并为和设将类krqprrqpGGGGGGGG134系统聚类法的性质系统聚类法的性质 单调性单调性 令Dr是系统聚类法中第r次并类时的距离，如例1中，用最短距离法时，有D1=1，D2=1.5，D3=2，D4=3.5，且有D1D2D3D4。 如果一种系统聚类法能满足D1D2D3Bi（aijbij,对一切i,j)，则称第一种方法比第二种方法使空间扩张，或第二种方法比第一种方法使空间浓缩。