数学地质系列------4聚类分析课件

地质与环境学院地质与环境学院College of Geology&Environment 俗话说：俗话说：“物以类聚，人以群分物以类聚，人以群分”，在社会、经济、管理、气象、地质、人口、在社会、经济、管理、气象、地质、人口、考古等众多领域，都存在着大量的考古等众多领域，都存在着大量的分类研究问题分类研究问题。分类是自然科学重要研究内容之一第五章 聚类分析第一节第一节 概概 述述第二节第二节 数据的规格化处理数据的规格化处理第三节第三节 相似性度量相似性度量第四节第四节 系统聚类法系统聚类法第五节第五节 应用实例应用实例地质与环境学院地质与环境学院College of Geology&Environment 合理的科学的分类，能够反映某类事物的合理的科学的分类，能够反映某类事物的最基本的特征最基本的特征以及以及同别类事物的区别同别类事物的区别，推动学科的发展和科学研究。，推动学科的发展和科学研究。第一节 概 述在地学领域：岩石、矿物、构造、地层、古生物等在地学领域：岩石、矿物、构造、地层、古生物等在环境领域：环境质量在环境领域：环境质量在经济领域：股市在经济领域：股市 聚类分析：聚类分析：是一种分类技术，是一种分类技术，它是它是根据根据“物以类聚物以类聚”的道理，的道理，对对事物事物(样品或指标样品或指标)进进行分类的一种行分类的一种多元统计方法多元统计方法，又称又称“群分析、点群分析、簇群分析群分析、点群分析、簇群分析”。一、聚类分析的含义根据根据事物本身的特征事物本身的特征分类，分类，即，即，将事物将事物性质相近性质相近的归为一类，的归为一类，将事物将事物性质的差异较大性质的差异较大的归在不同的类。的归在不同的类。所谓所谓“类类”，通俗地说就是，通俗地说就是相似元素的集合相似元素的集合。分类，是将一个观测对象指定到某一类（组）。分类，是将一个观测对象指定到某一类（组）。聚类分析特点：将事物将事物性质相近性质相近的归为一类，的归为一类，将事物将事物性质的差异较大性质的差异较大的归在不同的类。的归在不同的类。当有当有一个分类指标一个分类指标时，分类时，分类比较容易比较容易。当当有有多个多个分类分类指标指标时时，要进行分类就，要进行分类就不是很容易了不是很容易了。由于不同的指标项由于不同的指标项对对重要程度重要程度或或依赖关系依赖关系是相互不同的，是相互不同的，所以也不能用所以也不能用平均的方法平均的方法，这样会忽视相对，这样会忽视相对重要程度重要程度的问题。的问题。传统的分类方法起源很早，在古老的分类学中，人们主要传统的分类方法起源很早，在古老的分类学中，人们主要靠靠经验经验和和专业知识专业知识进行定性的分析，进行定性的分析，许多分类往往带有许多分类往往带有主观主观性和任意性性和任意性，不能揭示客观事物的内在本质差别和联系不能揭示客观事物的内在本质差别和联系。随着人类科学技术的发展，对分类的要求越来越高，仅随着人类科学技术的发展，对分类的要求越来越高，仅凭经验和专业知识难以确切的进行分类，特别是对于凭经验和专业知识难以确切的进行分类，特别是对于多因素、多因素、多指标多指标的分类问题。的分类问题。数学工具数学工具引用到分类学中，形成引用到分类学中，形成数值分类学数值分类学,后来又将后来又将多元分析多元分析的技术引入到数值分类学，逐步形成的技术引入到数值分类学，逐步形成聚类分析聚类分析这一这一数值分类方法。数值分类方法。根据分类对象根据分类对象Q Q型：型：研究研究样品之间样品之间的关系，把不同的物体归类分群的关系，把不同的物体归类分群R R型：型：研究同一物种不同研究同一物种不同变量之间变量之间的关系的关系 根据维数：根据维数：1 1、2 2、多、多 根据聚类的方法：根据聚类的方法：系统聚类、分解法系统聚类、分解法 系统聚类法：系统聚类法：最短距离法（近邻连接法）、最长距离法（远邻连接法）最短距离法（近邻连接法）、最长距离法（远邻连接法）类平均法、重心法、离差平方和增量法类平均法、重心法、离差平方和增量法二、聚类分析的对象类型 以分类对象为标准，可以将变量（指标）分类R型聚类分析。如城镇居民消费水平通常用八项指标来描述，八项指标间存在一定的线性相关。为研究城镇居民的消费结构，需将相关性强的指标归并到一起，这实际上就是对指标聚类等。在生产活动中不乏有变量聚类的实例，如：衣服型号就是根据人体各部分尺寸数据找出最有代表性的指标如身长、胸围和裤长、腰围作为上衣和裤子的代表性指标。变量聚类使批量生产成为可能。R R 型聚类是对型聚类是对变量进行分类处理变量进行分类处理。一般来说，可以反映研究对象特点的一般来说，可以反映研究对象特点的变量有许多变量有许多，由于对，由于对客观事物的认识有限，往往难以找出彼此独立且有客观事物的认识有限，往往难以找出彼此独立且有代表性的变代表性的变量量，影响对问题进一步的认识和研究。，影响对问题进一步的认识和研究。因此需要先进行因此需要先进行变量聚类变量聚类，找出，找出相互独立又有代表性的变相互独立又有代表性的变量量，而又不丢失大部分信息。，而又不丢失大部分信息。Q Q 型聚类是对型聚类是对样品进行分类样品进行分类，即，即对观测进行分类对观测进行分类。根据观测有关变量的特征，将根据观测有关变量的特征，将特征相似的样品特征相似的样品归为一类。归为一类。它是聚类分析中用的最多的一种。它是聚类分析中用的最多的一种。Q 型、型、R型这两种聚类在数学上是对称的，没有什么不同。型这两种聚类在数学上是对称的，没有什么不同。主要讨论主要讨论Q型聚类分析问题。型聚类分析问题。三、聚类分析的基本思想 我们所研究的样品或指标（变量）之间存在着程度不同我们所研究的样品或指标（变量）之间存在着程度不同的的相似性相似性（亲疏关系），于是：（亲疏关系），于是：（1 1）根据一批样品的多个观测指标，具体找出一些能够度）根据一批样品的多个观测指标，具体找出一些能够度量量样品或变量（指标）之间相似程度的统计量样品或变量（指标）之间相似程度的统计量；与多元分析的其它方法比，聚类分析方法较为粗糙，理与多元分析的其它方法比，聚类分析方法较为粗糙，理论上还不够完善，但应用方便、广泛，论上还不够完善，但应用方便、广泛，与回归分析、判别分与回归分析、判别分析一起被称为多元分析的三大方法析一起被称为多元分析的三大方法。（2 2）以这些统计量为）以这些统计量为分类的依据分类的依据，建立一种，建立一种分类方法分类方法，将一，将一批样品或变量（指标），按照它们在性质上的批样品或变量（指标），按照它们在性质上的亲疏、相似程亲疏、相似程度进行分类度进行分类。第二节 数据的规格化处理一、聚类分析的数据格式一、聚类分析的数据格式 设有设有n n个样品个样品单位，每个样品测得单位，每个样品测得 m m 项变量（指标），项变量（指标），原始资料阵为：原始资料阵为：nmnnmmijxxxxxxxxxxX212222111211)(第第i i个样品个样品X Xi i为矩阵为矩阵X X的第的第i i行所描述，行所描述，任何两个样品任何两个样品X Xk k与与X XL L之间的之间的相似性相似性，可以通过矩阵，可以通过矩阵X X中中的第的第K K行与第行与第 L L 行的相似程度来刻划；行的相似程度来刻划；nmnnmmijxxxxxxxxxxX212222111211)(x xijij（i=1,n;j=1,mi=1,n;j=1,m）为第）为第i i个样品的第个样品的第j j个指标的个指标的观测数据观测数据。任何两个变量任何两个变量x xk k与与x xL L之间的相似性，之间的相似性，可以通过第可以通过第K K列与列与第第L L列的列的相似程度相似程度来刻划。来刻划。nmnnmmijxxxxxxxxxxX212222111211)(x xijij（i=1,n;j=1,mi=1,n;j=1,m）为第）为第i i个样品的第个样品的第j j个指标的个指标的观测数据观测数据。为了将为了将样本进行分类样本进行分类，就需要研究，就需要研究样品之间样品之间的关系；的关系；为了将为了将变量进行分类变量进行分类，就需要研究，就需要研究变量之间变量之间的关系。的关系。无论是样品之间的关系，还是变量之间的关系，都是无论是样品之间的关系，还是变量之间的关系，都是用用变量来描述变量来描述的，的，变量的类型不同，描述方法也就不同变量的类型不同，描述方法也就不同。二、变量测量尺度的类型二、变量测量尺度的类型通常，变量按照通常，变量按照测量的尺度测量的尺度不同，可以分为三类：不同，可以分为三类：二、变量测量尺度的类型二、变量测量尺度的类型 间隔尺度间隔尺度（定距尺度、定量变量）：（定距尺度、定量变量）：变量用变量用连续的量连续的量表示，由表示，由测量、计数测量、计数或或统计统计所得到的量。所得到的量。如，长度、重量、经济统计数字、抽样调查数据等；如，长度、重量、经济统计数字、抽样调查数据等；间隔尺度、有序尺度、间隔尺度、有序尺度、名义尺度名义尺度有序尺度有序尺度（定序变量、定性变量）：（定序变量、定性变量）：用该变量度量时用该变量度量时没有明确的数量表示没有明确的数量表示，只有次序只有次序（等级）（等级）关系。如，产品质量，分为一等品、二等品等。关系。如，产品质量，分为一等品、二等品等。名义尺度名义尺度（定类变量、定性变量）：（定类变量、定性变量）：具有该种特性的变量在度量时既没有数量表示，也没有具有该种特性的变量在度量时既没有数量表示，也没有次序关系，而次序关系，而只有性质上的差异只有性质上的差异（用一些类表示）。（用一些类表示）。如，性别、职业等。如，性别、职业等。不同类型的变量，在定义距离和相似系数时，其方法不同类型的变量，在定义距离和相似系数时，其方法有很大差异。有很大差异。在实际应用中，研究比较多的是在实际应用中，研究比较多的是间隔尺度间隔尺度，本章主要讨，本章主要讨论具有间隔尺度变量的样品聚类分析方法。论具有间隔尺度变量的样品聚类分析方法。为了使为了使不同量纲不同量纲、不同取值范围不同取值范围的数据能放在一起进行比的数据能放在一起进行比较，通常需要对数据进行规格化处理，较，通常需要对数据进行规格化处理，即将原始数据矩阵中的每个元素，按照某种即将原始数据矩阵中的每个元素，按照某种特定的运算，特定的运算，把它变为把它变为一个新值，一个新值，而且数值的变化不依赖于原始数据集合中而且数值的变化不依赖于原始数据集合中其它数据的新值。其它数据的新值。第二节 数据的规格化处理nmnnmmijxxxxxxxxxxX212222111211)(nijijniijijjjijijxxnxnxsxxz121)(1111 1、数据标准化、数据标准化nmnnmmijzzzzzzzzzzZ212222111211)(第二节 数据的规格化处理nijijjxxnS12)(11nmnnmmijxxxxxxxxxxX212222111211)(jjjijijxxxxzminmaxmin2 2、数据正规化、数据正规化nmnnmmijzzzzzzzzzzZ212222111211)(nmnnmmijxxxxxxxxxxX212222111211)(niijijjijijxnxxxz113 3、中心化、中心化nmnnmmijzzzzzzzzzzZ212222111211)(nmnnmmijxxxxxxxxxxX212222111211)()log(ijijxz 4 4、对数化、对数化nmnnmmijzzzzzzzzzzZ212222111211)(nmnnmmijxxxxxxxxxxX212222111211)(jxzxniijijmax15 5、极大值规格化、极大值规格化nmnnmmijzzzzzzzzzzZ212222111211)(nmnnmmijxxxxxxxxxxX212222111211)(jijijxxz6 6、均值规格化、均值规格化nmnnmmijzzzzzzzzzzZ212222111211)(nmnnmmijxxxxxxxxxxX212222111211)(nijijijjijijxxnxSxz12)(117 7、标准差规格化、标准差规格化nmnnmmijzzzzzzzzzzZ212222111211)(第三节 相似性度量聚类分析用于系统类群聚类分析用于系统类群相似性相似性的研究的实质，的研究的实质，寻找寻找一种能客观反映事物（样品或变量）之间一种能客观反映事物（样品或变量）之间亲疏亲疏(相近或相近或相似）相似）关系的统计量关系的统计量，根据这种根据这种统计量统计量把事物（样品或变量）把事物（样品或变量）分成若干类分成若干类。相似性度量：相似性度量：能够能够度量度量变量（或样品）之间变量（或样品）之间相似相似性程度性程度的数量指标。的数量指标。常用的有常用的有相似系数相似系数、相关系数相关系数、欧氏距离欧氏距离、斜交距离斜交距离、离差（误差）平方和增量离差（误差）平方和增量等。等。描述样品（或变量）间相近（亲疏）、相似程度描述样品（或变量）间相近（亲疏）、相似程度的统计量很多，目前用得最多的聚类统计量是的统计量很多，目前用得最多的聚类统计量是距离距离和和相似系数相似系数，距离系数距离系数一般用于对一般用于对样品分类样品分类，相似系数相似系数一般用于对一般用于对变量聚类变量聚类。假使每个样品有假使每个样品有p p个变量个变量，则每个样品都可以看成，则每个样品都可以看成p p维空间维空间中的一个点，中的一个点，n n个样品个样品就是就是p p维空间中的维空间中的n n个点，个点，用距离来度量样品之间接近的程度用距离来度量样品之间接近的程度,即即两个样品间接近程度用两个样品间接近程度用p p维空间中两点的距离来度量维空间中两点的距离来度量。在聚类过程中，在聚类过程中，距离较近的点倾向于归为一距离较近的点倾向于归为一类类，距离较远的点应归属不同的类。，距离较远的点应归属不同的类。样品间相近性（亲疏程度）的测度样品间相近性（亲疏程度）的测度 首先我们看样本数据：首先我们看样本数据：个样品之间的距离个样品与第表示第设：jijidnmnnmmijxxxxxxxxxxX212222111211)(1 1、定义距离的准则、定义距离的准则 定义距离要求满足第i个和第j个样品之间的距离如下四个条件（距离可以自己定义，只要满足距离的条件）;0成立和对一切的jidij;0成立当且仅当jidij;成立和对一切的jiddjiij.成立和对于一切的jidddkjikij（样品（样品 i 和样品和样品 j 的各指标相同的各指标相同)(对称性）对称性）(三角不等式）三角不等式）2、常用距离的算法、常用距离的算法 通常我们定义的距离一般是指通常我们定义的距离一般是指欧氏距离欧氏距离（直线距离），（直线距离），几何平面上的点几何平面上的点P P（x x1 1,x,x2 2)到原点到原点o o（0 0，0 0）的欧氏距离，依的欧氏距离，依勾股定理勾股定理xxpod2221),(R Rp p 中两点中两点 X X（x x1 1,x,x2 2,x xp p)和和 Y(yY(y1 1,y,y2 2,y yp p)之间的之间的欧欧氏距离氏距离为：为：)()()()(,(2112)yxyxyxyxDpp2、常用距离的算法、常用距离的算法 常用距离常用距离明氏距离明氏距离MinkowskiMinkowski距离）：距离）：11()qpqijikjkkdqxx （通用的距离测度公式）（通用的距离测度公式）2、常用距离的算法、常用距离的算法2、常用距离的算法、常用距离的算法1(1)pijikjkkdxx 1 221(2)pijikjkkdxx （最直观的距离）（最直观的距离）当当q=2q=2时：时：欧氏距离欧氏距离(Euclidean)(Euclidean)当当q=1q=1时：时：绝对值距离绝对值距离1()max ijikjkkpdxx 当当q=q=时时：切比雪夫距离切比雪夫距离(ChebychevChebychev)当当量纲不一致时量纲不一致时，往往突出，往往突出数量级高的变量数量级高的变量的作用，的作用，压低数量级低的变量作用压低数量级低的变量作用结果与实际有较大偏差结果与实际有较大偏差维数维数m m增加使增加使D Dikik变大，其变化无规律可循变大，其变化无规律可循解决解决:原始数据预处理原始数据预处理修正公式修正公式 欧氏距离系数欧氏距离系数D Dikik大小受变量观测值大小受变量观测值量纲量纲影响和影响和变量个数变量个数（维数）的影响。（维数）的影响。量纲量纲原始数据预处理原始数据预处理 统一量纲变换：统一量纲变换：成为成为无量纲的无量纲的、具有统一尺度具有统一尺度的数据，的数据，使每个变量在使每个变量在同一水平上同一水平上显示显示各自的作用各自的作用。维数维数修正公式修正公式 消除维数影响，并将欧氏距离系数的消除维数影响，并将欧氏距离系数的变化范围变化范围限制在限制在（0 0，1 1）之间。之间。当两点距离越小当两点距离越小，d dikik越大越大，两样品相似性愈大，两样品相似性愈大；反之，距离反之，距离，d dikik，相似性，相似性变量样品，mjnkixxmdmjkjijik,2,1,2,1,1112例如：对体重和身高进行测量，采用不同单位，其距离测量例如：对体重和身高进行测量，采用不同单位，其距离测量的结果不同。的结果不同。当长度为当长度为cmcm时：时：CDAB22CD22ABdd1250)(105)(0d1010)(110)(0d当长度为当长度为mmmm时：时：CDAB22CD22ABdd26000)(1050)(0d100010)(1100)(0d通常改进办法有两个：通常改进办法有两个：（1 1）当各指标的）当各指标的测量值相差悬殊时测量值相差悬殊时，先对数据，先对数据标准化标准化，用，用标准化后的数据计算距离。标准化后的数据计算距离。标准化后的数据，每个变量的样本均值为标准化后的数据，每个变量的样本均值为0 0，标准差为，标准差为1 1，与变量的量纲无关；与变量的量纲无关；常用的聚类分析软件中都有这项功能，可以自动完成。常用的聚类分析软件中都有这项功能，可以自动完成。（2 2）为）为克服变量之间的相关性影响克服变量之间的相关性影响，可以采用，可以采用马氏距离马氏距离。下面用一个一维的例子说明欧氏距离与马氏距离在概率上下面用一个一维的例子说明欧氏距离与马氏距离在概率上的差异。的差异。设有两个正态总体，设有两个正态总体，给定一个样品位于给定一个样品位于A A处，试问处，试问A A处的样品离哪一个总体较近。处的样品离哪一个总体较近。按按欧氏距离欧氏距离来度量，来度量，A A点离点离 的中心的中心 ，要比离要比离 的中心的中心 “近一些近一些”，从概率论的角度来看，从概率论的角度来看，A A点位于点位于 右侧约右侧约 处，处，而位于而位于 左侧约左侧约 处，处，用标准差来度量，那么用标准差来度量，那么A A点离点离 要比离要比离 “近一些近一些”。25.2 从图上看，从图上看，显然，显然，概率论的角度概率论的角度的度量更为合理。的度量更为合理。它是用它是用坐标差平方除以方差坐标差平方除以方差（或乘以方差的倒数），从而（或乘以方差的倒数），从而化为化为无量纲数无量纲数，推广到多维就要乘以协方差阵推广到多维就要乘以协方差阵 的逆矩阵的逆矩阵 ，这就是这就是是是马氏距离马氏距离的概念。的概念。1 马氏距离是由印度统计学家马氏距离是由印度统计学家马哈拉诺比斯马哈拉诺比斯于于19361936年引入的，年引入的，故称为故称为马氏距离马氏距离。这一距离在多元统计分析中起着十分重要的。这一距离在多元统计分析中起着十分重要的作用。作用。2、常用距离的算法、常用距离的算法，考虑点考虑点 X X 到到），（），（22222111NNGGG G1 1、G G2 2的相对距离：的相对距离：222222121221),(xGdxGdxx），（设设2222221)()(),(1)(1)(),(21GPGGpijGddmmP时，当的马氏距离定义为：与总体则样品，协差阵为），（为的均值向量总体，najajiaiijxxxxn1p,1,ji,)(11naajjnaaiixnxnx111x 11)()()(12jijiijXXXXMd其中其中如果如果存在，则两个样品之间的存在，则两个样品之间的马氏距离马氏距离为为:马氏距离虽然考虑了观测变量之间的马氏距离虽然考虑了观测变量之间的相关性相关性，并且也，并且也不受不受观测变量量纲观测变量量纲不同的影响，不同的影响，在聚类分析之前，如果用全部数据计算的在聚类分析之前，如果用全部数据计算的均值向量均值向量和和协方协方差矩阵差矩阵来计算马氏距离，效果并不是很好。来计算马氏距离，效果并不是很好。马氏距离马氏距离2、常用距离的算法、常用距离的算法 比较合理的办法是用比较合理的办法是用各个类的样本各个类的样本来计算来计算各自的协方差矩阵各自的协方差矩阵，同一类样本同一类样本的马氏距离应当用这一类的协方差矩阵来计算。的马氏距离应当用这一类的协方差矩阵来计算。然而，然而，类的形成要依赖于样品之间的距离类的形成要依赖于样品之间的距离，反过来样品间合理的，反过来样品间合理的马氏距离又依赖于类，这就形成了一个恶性循环。马氏距离又依赖于类，这就形成了一个恶性循环。马氏距离马氏距离2、常用距离的算法、常用距离的算法因此，在实际聚类分析处理中，马氏距离也不是理想的距离。因此，在实际聚类分析处理中，马氏距离也不是理想的距离。兰氏距离兰氏距离（CanberraCanberra）pajaiajaiaijxxxxpLd1n,1,ji,1)(仅适用于一切仅适用于一切0ijx的情况，的情况，这个距离有助于这个距离有助于克服各指标之间量纲的影响克服各指标之间量纲的影响，没有考虑指标之间的相关性。没有考虑指标之间的相关性。2、常用距离的算法、常用距离的算法3、欧氏距离系数、欧氏距离系数 一维：一维：DAB=|xAxB|二维：勾股定理二维：勾股定理 M维（欧氏距离系数）：维（欧氏距离系数）：21j2BA2BA2BA2x2xAB)x(x)x(x)x(xDDDjj221121m1j2kjijik)x(xD4 4、斜交距离、斜交距离变量样品，mjnkimxxxxPmjmljlklilkjijDIK,2,1,2,1,211离差平方和增量离差平方和增量21)(jqmjjpqpqppqxxnnnnE)(qptpqEEEE组内离差平方和：组内离差平方和：先计算组内每个变量的平均值，先计算组内每个变量的平均值，再用每个变量与该平均值相减再用每个变量与该平均值相减后的平方和相加得此值。后的平方和相加得此值。“按列计算按列计算”组内平均值计算：组内平均值计算：组内每个样品的某个变量（列）求和再除组内每个样品的某个变量（列）求和再除以样品数以样品数pqrqrrqprrprttrEnEnnEnnnnE12、常用距离的算法、常用距离的算法 以上几种距离的定义均要求变量是间隔尺度的，以上几种距离的定义均要求变量是间隔尺度的，如果使用的变量是如果使用的变量是有序尺度有序尺度或名义尺度的，则或名义尺度的，则有相应的有相应的一些定义距离的方法。一些定义距离的方法。欧氏距离是聚类分析中用得最广泛的距离。欧氏距离是聚类分析中用得最广泛的距离。2、常用距离的算法、常用距离的算法 两两样品的距离都算出来后，形成距离阵两两样品的距离都算出来后，形成距离阵D D，其中：，其中：，D D是一个实对称阵是一个实对称阵，只须计算上（或下）三角形部分，根据只须计算上（或下）三角形部分，根据 D D可对可对 n n 个点进个点进行分类，行分类，距离近的点归为一类，距离远的点归为不同的类距离近的点归为一类，距离远的点归为不同的类。02211nndddnpn2n12p22211p1211ddddddddd)(Dijd距离矩阵：距离矩阵：有些事物的相似，并非要求数值上的一致或相近，有些事物的相似，并非要求数值上的一致或相近，例如：例如：三角形的相似、尽管尺寸、大小相差悬殊，却非常相似，三角形的相似、尽管尺寸、大小相差悬殊，却非常相似，又如：又如：两形象平行，也可为非常相似，两形象平行，也可为非常相似，为此，必须引入另外一个聚类分析的统计量为此，必须引入另外一个聚类分析的统计量相似系数相似系数。在对变量在对变量进行分类时进行分类时，常常采用，常常采用相似系数相似系数来度量变量之间来度量变量之间的相似性，的相似性，变量之间的关系越是变量之间的关系越是密切密切，其相似系数越，其相似系数越接近于接近于1 1（或（或-1-1）；）；变量之间的关系越是变量之间的关系越是疏远疏远，其相似系数越，其相似系数越接近于接近于0 0。在聚类过程中，在聚类过程中，变量间相似性的测度变量间相似性的测度 比较相似的变量比较相似的变量倾向于归为一类，倾向于归为一类，不怎么相似的变量不怎么相似的变量归属不同的类。归属不同的类。变量变量X Xi i 与与 X Xj j的的相似系数相似系数用用C Cijij来表示。来表示。对于间隔尺度，对于间隔尺度，最常用的相似系数最常用的相似系数有两种：有两种：夹角余弦夹角余弦和和相关系数相关系数。1.1.夹角余弦夹角余弦cosinecosine 尽管图中尽管图中ABAB和和CDCD长度不一样，长度不一样，但但形状相似形状相似。当长度不是主要矛盾时，就可当长度不是主要矛盾时，就可利用利用夹角余弦夹角余弦这样的相似系数。这样的相似系数。变量变量X Xi i的的n n次观测值（次观测值（X X1i1i,X,X2i2i,X Xnini)看成看成n n维空间的向量，维空间的向量，则则X Xi i和和X Xj j夹角夹角a aijij的余弦的余弦称为称为两向量的相似系数。两向量的相似系数。（它是它是P P维空间中维空间中变量变量X Xi i的观测向量的观测向量与与变量变量X Xj j的观测向量的观测向量之间夹角的余弦函数）。之间夹角的余弦函数）。1.1.夹角余弦夹角余弦 ：将任何两个样品将任何两个样品 与与 看成看成 p 维空间的两个向量，这两个维空间的两个向量，这两个iXjXijcos向量的向量的夹角余弦夹角余弦 用表示。则：用表示。则：kkkjkkikkkjkikijxxxx12121cos1.1.夹角余弦夹角余弦 ：由于由于-1 -1 coscos ijij 1 1，其值越接近于，其值越接近于 1 1，说明二样品的相似程度越高。说明二样品的相似程度越高。求出两两样品的相似系数，得到求出两两样品的相似系数，得到相似系数矩阵相似系数矩阵：它是一个它是一个 n n 阶实对称矩阵，其主对角元素为阶实对称矩阵，其主对角元素为 1 1。nnnnnnHcos,cos,coscos,cos,coscos,cos,cos2122221112111.1.夹角余弦夹角余弦 ：mkjSSxxxxxxxxxxxxrkkjjnikikjijninikikjijnikikjijjk,2,1,111221愈大表示关系愈密切，rr12.2.相关系数：相关系数：相关系数常用相关系数常用r rijij表示，表示，把两两样品的相关系数都计算出来，可形成样品把两两样品的相关系数都计算出来，可形成样品相关系数矩阵相关系数矩阵。其中其中 ，可根据，可根据R R可对可对n n个样品进行分类。个样品进行分类。12211nnrrr2.2.相关系数：相关系数：第四节 系统聚类法 系统聚类法系统聚类法（分层聚类）（分层聚类）:是诸聚类分析方法中是诸聚类分析方法中使用最多使用最多的一种，的一种，它是将类它是将类由多变到少由多变到少的一种方法。的一种方法。系统聚类分析的基本思想：系统聚类分析的基本思想：首先将所研究的首先将所研究的每个样品各自看成一类每个样品各自看成一类，然后然后根据样品间的相似程度根据样品间的相似程度，每次将最相似的两类合并每次将最相似的两类合并。计算新类与其他类之间的相似程度，计算新类与其他类之间的相似程度，再选择最相似者加以合并，这样每合并一次，就减少一类，再选择最相似者加以合并，这样每合并一次，就减少一类，继续这一过程，继续这一过程，直到将所有样品合并成一类直到将所有样品合并成一类为止。为止。计算计算新类与其他类之间的新类与其他类之间的相似程度相似程度，再选择再选择最相似类合并最相似类合并，这样每合并一次，就减少一类，这样每合并一次，就减少一类，(一一)类间距离类间距离 根据问题和数据的实际情况，根据问题和数据的实际情况，样品之间的距离：样品之间的距离：可从介绍过的几种可从介绍过的几种聚类统计量聚类统计量中选取最中选取最合适的一种。合适的一种。类与类之间的距离：类与类之间的距离：主要解决以谁来代表全类主要解决以谁来代表全类，由此产生不同的由此产生不同的类间距离类间距离和不同的和不同的系统聚类过程系统聚类过程。以下用以下用 表示表示样品样品 与与 之间距离，之间距离，用用 表示表示类类 与与ijdiXjXijDiGjG之间的距离。之间的距离。(一一)类间距离类间距离1.1.最短距离法最短距离法(single linkage，nearest neighbor)样品间：样品间：欧氏距离欧氏距离类类间：类类间：两类间两两样品距离最短。两类间两两样品距离最短。即，下图中样品即，下图中样品A A1 1和和B B2 2之间的距离之间的距离.类间距离类间距离B1B3B2A1A2最短距离最短距离(single linkage)(single linkage)聚类算法：聚类算法：把把两个类之间的距离两个类之间的距离定义为一个类的所有样品与另定义为一个类的所有样品与另一个类的一个类的所有样品之间距离所有样品之间距离的的最小者最小者。定义类定义类G Gi i与与G Gj j之间的距离为之间的距离为两类最近样品的距离两类最近样品的距离，即，即dDijijGxGxjjii,min 将将G GK K和和G GL L合并成一个合并成一个新类新类，记为，记为G GM M，则任一类则任一类G GJ J 与与G GM M的距离：的距离：),min()(JLJkkLJJMDDDD （1）规定样品之间的距离，计算）规定样品之间的距离，计算n个样品的个样品的距离矩阵距离矩阵D(0)，它是一个对称矩阵，它是一个对称矩阵，开始每个样品自成一类开始每个样品自成一类，。ijijdD（2）选择）选择D(0)中非对角线的最小元素中非对角线的最小元素，设为，设为DKL，将将GK和和GL合并成一个合并成一个新类新类，记为，记为GM，即即GM=GK,GL。1.1.最短距离法最短距离法聚类步骤：聚类步骤：（3）计算新类与任一类之间的距离计算新类与任一类之间的距离为为 DJM=minDJK,DJL 将将D(0)中中K、L行，行，K、L列用上式列用上式并成一个新行新列并成一个新行新列，新行新列新行新列对应对应GM，所得矩阵记作，所得矩阵记作D(1)。(4)(4)对对D D（1 1）重复上述重复上述对对D D（0 0）的两步得的两步得D D（2 2），直至，直至如果某一步如果某一步D(m)D(m)中中最小的元素不止一个最小的元素不止一个，则对应这些最小元素的类可以则对应这些最小元素的类可以同时合并同时合并。所有元素合并成一类为止。所有元素合并成一类为止。例：例：5个样品，每个样品只有一个指标，分别为：个样品，每个样品只有一个指标，分别为：1.0，2.0，3.5，7.0，9.0，试用最短距离进行聚类分析。，试用最短距离进行聚类分析。),min()(JLJkkLJJMDDDDG1 G2 G3 G4 G5G1G2G3G4G50 1 02.5 1.5 06 5 3.5 0 8 7 5.5 2 0解解：（1）样品间的距离采用绝对距离，计算样品两两距离，样品间的距离采用绝对距离，计算样品两两距离，得得距离矩阵距离矩阵D（0）：G6 G3 G4 G5G6G3G4G50 1.5 05 3.5 07 5.5 2.0 0 G1 G2 G3 G4 G5G1G2G3G4G50 1 02.5 1.5 06 5 3.5 0 8 7 5.5 2 0（2 2）D D（0 0）样中非对角线最小元素为样中非对角线最小元素为1 1，即，即D D1212=1=1，根据最短距，根据最短距离准则将离准则将G1G1、G2G2合并为一新类合并为一新类，记为，记为G6=G1,G2G6=G1,G2；（3 3）计算）计算G6G6与剩余其他类的距离，按照公式：与剩余其他类的距离，按照公式：D=min D=min（D Di1i1，D Di2i2），），即即D D（0 0）的前两列中取较小者，得的前两列中取较小者，得距离矩阵距离矩阵D D（1 1）：G6 G3 G4 G5G6G3G4G50 1.5 05 3.5 07 5.5 2.0 0 G1 G2 G3 G4 G5G1G2G3G4G50 1 02.5 1.5 06 5 3.5 0 8 7 5.5 2 0（2 2）D D（0 0）样中非对角线最小元素为样中非对角线最小元素为1 1，即，即D D1212=1=1，根据最短距，根据最短距离准则将离准则将G1G1、G2G2合并为一新类合并为一新类，记为，记为G6=G1,G2G6=G1,G2；（3 3）计算）计算G6G6与剩余其他类的距离，按照公式：与剩余其他类的距离，按照公式：D=min D=min（D Di1i1，D Di2i2），），即即D D（0 0）的前两列中取较小者，得的前两列中取较小者，得距离矩阵距离矩阵D D（1 1）：G6 G3 G4 G5G6G3G4G50 1.5 05 3.5 07 5.5 2.0 0 （4 4）D D（1 1）样中非对角线最小元素为样中非对角线最小元素为1.51.5，即，即D D3636=1.5=1.5，根据最，根据最短距离准则将短距离准则将G3G3、G6G6合并为一新类合并为一新类，记为，记为G7=G1,G2,G3G7=G1,G2,G3；即即,D,D（1 1）的前两列中取较小者，得的前两列中取较小者，得距离矩阵距离矩阵D D（2 2）：G3 G4 G5G3G4G503.5 05.5 2.0 0 G6 G3 G4 G5G6G3G4G50 1.5 05 3.5 07 5.5 2.0 0 （4 4）D D（1 1）样中非对角线最小元素为样中非对角线最小元素为1.51.5，即，即D D3636=1.5=1.5，根据最，根据最短距离准则将短距离准则将G3G3、G6G6合并为一新类合并为一新类，记为，记为G7=G1,G2,G3G7=G1,G2,G3；即即,D,D（1 1）的前两列中取较小者，得的前两列中取较小者，得距离矩阵距离矩阵D D（2 2）：G3 G4 G5G3G4G503.5 05.5 2.0 0 （5 5）D D（2 2）样中非对角线最小元素为样中非对角线最小元素为2.02.0，即，即D D4545=2.0=2.0，根据最，根据最短距离准则将短距离准则将G4G4、G5G5合并为一新类合并为一新类，记为，记为G8=G4,G5G8=G4,G5；即即,D,D（2 2）的前两列中取较小者，得的前两列中取较小者，得距离矩阵距离矩阵D D（3 3）：G7 G4 G5G7G4G503.5 05.5 2.0 0 G7 G8 G7G803.5 0（5 5）D D（2 2）样中非对角线最小元素为样中非对角线最小元素为2.02.0，即，即D D4545=2.0=2.0，根据最，根据最短距离准则将短距离准则将G4G4、G5G5合并为一新类合并为一新类，记为，记为G8=G4,G5G8=G4,G5；即即,D,D（2 2）的前两列中取较小者，得的前两列中取较小者，得距离矩阵距离矩阵D D（3 3）：G7 G4 G5G7G4G503.5 05.5 2.0 0 G7 G8 G7G803.5 0X X1 1X X5 5X X4 4X X3 3X X2 2G G6 6G G7 7G G8 8G G9 9系统聚类谱系图系统聚类谱系图2.2.最最长长距离法距离法(complete linkage，furthest neighbor)样品间：样品间：欧氏距离欧氏距离类类间：类类间：两类间样品两两距离最长。两类间样品两两距离最长。即下图中样品即下图中样品A A2 2和和B B3 3之间的距离之间的距离 ),max(JLJKJMDDD最长距离最长距离(complete linkage)(complete linkage)类间距离类间距离B1B3A1A2B2聚类算法：聚类算法：(1)(1)把把两个类之间的距离两个类之间的距离定义为一个类的所有样品与另一个类定义为一个类的所有样品与另一个类 的的所有样品之间的所有样品之间的距离最大者距离最大者，(2)(2)并类的标准并类的标准仍采用它与仍采用它与其它类的最小距离其它类的最小距离。例：例：5个样品，每个样品只有一个指标，分别为：个样品，每个样品只有一个指标，分别为：1.0，2.0，3.5，7.0，9.0，试用最，试用最长长距离进行聚类分析。距离进行聚类分析。解解：（1）样品间的距离采用绝对距离，计算样品两两距离，样品间的距离采用绝对距离，计算样品两两距离，得得距离矩阵距离矩阵D（0）：),max(JLJKJMDDDG1 G2 G3 G4 G5G1G2G3G4G50 1 02.5 1.5 06 5 3.5 0 8 7 5.5 2.0 0G1 G2 G3 G4 G5G1G2G3G4G50 1 02.5 1.5 06 5 3.5 0 8 7 5.5 2.0 0（2 2）D D（0 0）样中非对角线最小元素为样中非对角线最小元素为1 1，即，即D D1212=1=1，根据最短距，根据最短距离准则将离准则将G1G1、G2G2合并为一新类合并为一新类，记为，记为G6=G1,G2G6=G1,G2；（3 3）计算）计算G6G6与剩余其他类的距离，按照公式：与剩余其他类的距离，按照公式：D=max D=max（D Di1i1，D Di2i2），），即即D D（0 0）的前两列中取较小者，得的前两列中取较小者，得距离矩阵距离矩阵D D（1 1）：（2 2）D D（0 0）样中非对角线最小元素为样中非对角线最小元素为1 1，即，即D D1212=1=1，根据最短距，根据最短距离准则将离准则将G1G1、G2G2合并为一新类合并为一新类，记为，记为G6=G1,G2G6=G1,G2；（3 3）计算）计算G6G6与剩余其他类的距离，按照公式：与剩余其他类的距离，按照公式：D=max D=max（D Di1i1，D Di2i2），），即即D D（0 0）的前两列中取较小者，得的前两列中取较小者，得距离矩阵距离矩阵D D（1 1）：G6 G3 G4 G5G6G3G4G50 2.5 06 3.5 08 5.5 2.0 0 G1 G2 G3 G4 G5G1G2G3G4G50 1 02.5 1.5 06 5 3.5 0 8 7 5.5 2 0（4 4）D D（1 1）样中非对角线最小元素为样中非对角线最小元素为2.02.0，即，即D D4545=2.0=2.0，根据最，根据最短距离准则将短距离准则将G4G4、G5G5合并为一新类合并为一新类，记为，记为G7=G4,G5G7=G4,G5；即即,D,D（1 1）的前两列中取较小者，得的前两列中取较小者，得距离矩阵距离矩阵D D（2 2）：G6 G3 G4 G5G6G3G4G50 2.5 06 3.5 08 5.5 2.0 0 G6 G3 G4 G5G6G3G4G50 2.5 06 3.5 08 5.5 2.0 0 G6 G3 G7 G6G3G70 2.5 08 5.5 0 （4 4）D D（1 1）样中非对角线最小元素为样中非对角线最小元素为2.02.0，即，即D D4545=2.0=2.0，根据最，根据最短距离准则将短距离准则将G4G4、G5G5合并为一新类合并为一新类，记为，记为G7=G4,G5G7=G4,G5；即即,D,D（1 1）的前两列中取较小者，得的前两列中取较小者，得距离矩阵距离矩阵D D（2 2）：（5 5）D D（2 2）样中非对角线最小元素为样中非对角线最小元素为2.52.5，即，即D D3636=2.5=2.5，根据最，根据最短距离准则将短距离准则将G3G3、G6G6合并为一新类合并为一新类，记为，记为G8=G3,G6G8=G3,G6；即即,D,D（2 2）的前两列中取较小者，得的前两列中取较小者，得距离矩阵距离矩阵D D（3 3）：G8 G7 G8G708 0G6 G3 G7 G6G3G70 2.5 08 5.5 0 X X1 1X X5 5X X4 4X X3 3X X2 2G G6 6G G8 8G G7 7G G9 9系统聚类谱系图系统聚类谱系图有两种形式：有两种形式：一种是一种是组间联结法组间联结法，组间联结法在计算距离时，只考虑两类，组间联结法在计算距离时，只考虑两类之间样品之间的之间样品之间的距离的平均距离的平均，另一种是另一种是组内联结法组内联结法，组内联结法在计算距离时把两组所有，组内联结法在计算距离时把两组所有样品之间的距离都考虑在内样品之间的距离都考虑在内。3.3.类平均法类平均法(average linkage between group)类间距离类间距离B1B3B2A1A2平均距离平均距离(average)(average)(61235234225224215214212ddddddD 4.4.重心法重心法(centroid method)样品间：样品间：欧氏距离欧氏距离 类类间：类类间：两类重心（即该类样品的均值）之间的距离两类重心（即该类样品的均值）之间的距离 重心重心法法类的重心之间的距离类的重心之间的距离 从物理观点来看，一类即一组质点，用它的重心从物理观点来看，一类即一组质点，用它的重心（质量的中心质量的中心）做为代表比较合理，由此产生重心法。）做为代表比较合理，由此产生重心法。类与类之间的距离：类与类之间的距离：定义为它们的重心（均值）之间的定义为它们的重心（均值）之间的(平方）欧氏距离。平方）欧氏距离。设设G GK K和和G GL L的重心分别为的重心分别为x xk k和和x xL L，则则G GK K与与G GL L之间的平方距离之间的平方距离为：为：LkDKL22(centroid method)4.4.重心法重心法)(222222KLMLKKLMLKJLMLJKMKJMDnnnDnnnDnnDnnD比中间距离多设某一步将设某一步将G GK K和和G GL L合并的合并的新类新类为为G GM M，它们的它们的重心重心分别是分别是X Xk k、X XL L、X Xm m，它们各有它们各有n nk k、n nL L、n nm m(n(nm m=n nk k+n+nL L)个个样品样品，显然，显然，新类新类G GM M与任一类与任一类G GJ J(重心为重心为x xJ J）的）的平方距离平方距离是是这就是这就是重心法的距离递推公式重心法的距离递推公式。4.4.重心法重心法 重心法的归类步骤与以上三种方法基本上一样，所不重心法的归类步骤与以上三种方法基本上一样，所不同的是同的是 每合并一次类，就要每合并一次类，就要重新计算新类的重心重新计算新类的重心及及各类与各类与新类的距离新类的距离。重心法在重心法在处理异常值处理异常值方面比其它系统聚类法更稳健，方面比其它系统聚类法更稳健，有很好的代表性。有很好的代表性。4.4.重心法重心法(centroid method)5.5.WardWard最小方差法最小方差法(Ward minimum variance method)样品间：样品间：欧氏距离欧氏距离类类间：类类间：离差平方和增量法离差平方和增量法WardWard最小方差法最小方差法 由沃德提出，其思想来源于由沃德提出，其思想来源于方差分析方差分析。如果分类正确，如果分类正确，Cluster KCluster KCluster LCluster LCluster MCluster M 同类样品的离差平方和同类样品的离差平方和 应当较小，应当较小，类与类之间的离差平方和类与类之间的离差平方和应当较大。应当较大。设将设将n n个样品个样品分成分成k k类类：G1,G2,G1,G2,GkGk,用用 表示表示 中的第中的第i i个样品（注意个样品（注意 是是p p维向量），维向量），n nt t 表示表示G Gt t中的中的样品个数样品个数，是是G Gt t的重心，则的重心，则G Gt t中样品的离差平方和中样品的离差平方和为：为：)(tiXtG)(tiX)(tXWardWard最小方差法最小方差法tnittittitXXXXS1)()()()()()(k个类的类内离差平方和个类的类内离差平方和:ktnittittiktttXXXXSS11)()()()(1)()(先将先将n n个样品各自成一类个样品各自成一类，此时总离差平方和，此时总离差平方和W=0,W=0,然后每次将其中然后每次将其中某两类合并为一类某两类合并为一类 （因每缩小一类（因每缩小一类离差平方和就要增大）离差平方和就要增大），每次选择使每次选择使总离差平方和总离差平方和w w增加最小增加最小的两类的两类进行合并进行合并 直到所有的样品归为一类为止。直到所有的样品归为一类为止。5.Ward5.Ward最小方差法最小方差法基本思想：基本思想：系统聚类小结系统聚类小结 几种系统聚类法，几种系统聚类法，并类的原则并类的原则和和步骤基本一致步骤基本一致，所不同的是所不同的是类与类之间的距离类与类之间的距离有不同的定义，依此所给出有不同的定义，依此所给出的新类与任一类的的新类与任一类的距离公式不同距离公式不同。可以把这可以把这几种方法统一几种方法统一起来，有利于在计算机上灵活地选起来，有利于在计算机上灵活地选择更有意义的谱系图（有利于计算机程序的编制）。择更有意义的谱系图（有利于计算机程序的编制）。LanceLance和和WilliamsWilliams于于19671967年将其统一为：年将其统一为：222222LJKJKLLJLKJKMJDDDDDD各种系统聚类法公式的参数各种系统聚类法公式的参数在实际应用中，一般采用以下在实际应用中，一般采用以下两种处理方法两种处理方法：根据分类问题本身的根据分类问题本身的专业知识，结合实际需要，专业知识，结合实际需要，选择分类选择分类方法，并确定分类个数。方法，并确定分类个数。用多种分类方法用多种分类方法去作，去作，取出结果中的共性取出结果中的共性来，如果用几种来，如果用几种方法的某些方法的某些结果都一样结果都一样，则说明这样的聚类确实，则说明这样的聚类确实反映了事反映了事物的本质物的本质，而将有争议的样品暂放一边或用其它办法（如，而将有争议的样品暂放一边或用其它办法（如判别分析）去归类。判别分析）去归类。1.1.数据变换数据变换为了便于为了便于比较、计算上的方便比较、计算上的方便或或改变数据的结构改变数据的结构；选择选择 度量样品间距离的定义度量样品间距离的定义（如欧氏距离）及（如欧氏距离）及 度量类间距离的定义度量类间距离的定义（如最短距离法）。（如最短距离法）。2.计算计算n个样品两两间的距离个样品两两间的距离dij，得得样品间的距离矩阵样品间的距离矩阵D(0)；3.一开始（第一步：一开始（第一步：i=1)n个样品各自构成一类，个样品各自构成一类，类的个数类的个数k=n个类个类,Gi=X(i)(i=1,.n)，此时此时类间的距离类间的距离就是就是样品间的距离样品间的距离（即（即D(1)=D(0)；4.4.合并距离最近的两类为一新类；合并距离最近的两类为一新类；5.5.计算新类与当前其它各类的距离，得计算新类与当前其它各类的距离，得新的距离矩阵新的距离矩阵D(i)D(i)，若合并后类的若合并后类的总个数总个数k k大于大于1 1，重复（，重复（3 3）和（）和（4 4）步，）步，直到类的个数为直到类的个数为1 1时止；时止；6.6.画谱系聚类图；画谱系聚类图；7.7.决定类的个数及各类的成员。决定类的个数及各类的成员。系统聚类法的步骤系统聚类法的步骤可选择