04聚类分析

1聚类分析专题§6.1引言俗话说，“物以类聚，人以群分”，在自然科学和社会科学等各领域中，存在着大量的分类问题。分类学是人类认识世界的基础科学，在古老的分类学中，人们主要靠经验和专业知识进行定性的分类，很少利用数学工具进行定量的分类。随着人类科学技术的发展，对分类的要求越来越高，以致有时仅凭经验和专业知识难以确切地进行分类，于是人们逐渐地把数学工具引用到了分类学中，这便形成了数值分类学这一学科，之后又将多元分析的技术引入到数值分类学，便又从数值分类学中分离出一个重要分支──聚类分析。与多元分析的其它分析方法相比，聚类分析方法较为粗糙，理论上还不够完善，正处于发展阶段。但是，由于该方法应用方便，分类效果较好，因此越来越为人们所重视。这些年来聚类分析的方法发展较快，内容越来越丰富。判别分析与聚类分析都是研究事物分类的基本方法，它们有着不同的分类目的，彼此之间既有区别又有联系。各种判别分析方法都要求对类有事先的了解，通常是每一类都有一个样本，据此得出判别函数和规则，进而可对其它新的样品属于哪一类作出判断。对类的事先了解和确定常常可以通过聚类分析得到。聚类分析的目的是把分类对象按一定规则分成若干类，这些类不是事先给定的，而是根据数据的特征确定的。在同一类里的这些对象在某种意义上倾向于彼此相似，而在不同类里的对象倾向于不相似。聚类分析能够用来概括数据而不只是为了寻找“自然的”或“实在的”分类。例如，在选拔少年运动员时，对少年的身体形态、身体素质、生理功能的各种指标进行测试，据此对少年进行分类，分在同一类里的少年这些指标较为相近。类确定好之后，可以根据各类的样本数据得出选材的判别规则，作为选材的依据。又如，根据啤酒中含有的酒精成分、纳成分、所含的热量“卡路里”数值，可以对啤酒进行分类。聚类分析根据分类对象不同分为Q型聚类分析和R型聚类分析。Q型聚类分析是指对样品进行聚类，R型聚类分析是指对变量进行聚类。本章我们主要讨论Q型聚类。§6.2距离和相似系数在对样品（或变量）进行分类时，样品（或变量）之间的相似性是如何度量的呢？这一节中，我们介绍两个相似性度量──距离和相似系数，前者常用来度量样品之间的相似性。后者常用来度量变量之间的相似性。样品之间的距离和相似系数有着各种不同的定义，而这些定义与变量的类型有着非常密切的关系。通常变量按测量尺度的不同可以分为以下三类：（1）间隔尺度变量：变量用连续的量来表示，如长度、重量、速度、温度等。（2）有序尺度变量：变量度量时不用明确的数量表示，而是用等级来表示，如某产品分为一等品、二等品、三等品等有次序关系。（3）名义尺度变量：变量用一些类表示，这些类之间既无等级关系也无数量关系，如性别、职业、产品的型号等。我们这里主要讨论具有间隔尺度变量的样品聚类分析方法。2一、距离设ijx为第i个样品的第j个指标，数据矩阵列于表6.1。每个样品有p个变量，故每个样品都可以看成是pR中的一个点，n个样品就是pR中的n个点。在pR中需定义某种距离，第i个样品与第j个样品之间的距离记为ijd，在聚类过程中，距离较近的点倾向于归为一类，距离较远的点应归属不同的类。所定义的距离ijd一般应满足如下四个条件：（Ⅰ）0ijd，对一切ji,；（Ⅱ）0ijd，当且仅当第i个样品与第j个样品的各变量值相同；（Ⅲ）jiijdd，对一切ji,；（Ⅳ）kjikijddd，对一切kji,,。表6.1数据矩阵变量样品1x2x…px111x12x…px1221x22x…px2n1nx2nx…npx常用的距离有如下几种：1．明考夫斯基(Minkowski)距离第i个样品与第j个样品间的明考夫斯基距离定义为qpkqjkikijxxqd11)(（6.2.1）这里q为某一自然数，这是一个最常用最直观的距离。当1q时，pkjkikijxxd1)1(，称为绝对值距离；当2q时，pkjkikpkjkikijxxxxd122112)2(，称为欧氏距离；当q时，jkikpkijxxd1max)(，称为切比雪夫距离。当各变量的单位不同或虽单位相同但各变量的测量值相差很大时，不应直接采用明考夫斯基距离，而应先对各变量的数据作标准化处理，然后用标准化后的数据计算距离。最常用的标准化处理是，令3jjjijijsxxx*，ni,,2,1，pj,,2,1其中，niijjxnx11为第j个变量的样本均值，nijijjjxxns12)(11为第j个变量的样本方差。2．马氏(Mahalanobis)距离第i个样品与第j个样品间的马氏距离为)()()(12jijiijxxSxxMd（6.2.2）其中),,,(21ipiiixxxx，S为样本协方差矩阵。使用马氏距离的好处是考虑到了各变量之间的相关性，并且与各变量的单位无关。不足之处是对马氏距离公式中的S，若始终不变，则往往显得不妥；若要随聚类过程而不断变化，则会有许多不便。3．兰氏(Lance和Williams)距离当0ijx，ni,,2,1，pj,,2,1时，则可以定义第i个样品与第j个样品间的兰氏距离为pkjkikjkikijxxxxLd1)(（6.2.3）这个距离与各变量单位无关，但没有考虑变量间的相关性。由于它对大的异常值不敏感，故适用于高度偏斜的数据。4．斜交空间距离由于样品的各个变量之间往往存在不同程度的相关关系，因此有时采用欧氏距离显得不够理想，有人建议采用斜交空间距离。第i个样品与第j个样品间的斜交空间距离定义为21112*))((1pkplkljliljkikijrxxxxpd其中klr是变量kx与变量lx间的相关系数。当p个变量互不相关时，)2(1*ijijdpd，即斜交空间距离退化为欧氏距离（除相差一个常数倍外）。以上几种距离的定义均要求变量是间隔尺度的，如果使用的变量是有序尺度或名义尺度的，则有相应的一些定义距离的方法。下例是对名义尺度变量的一种距离定义。例6.2.1设有五个变量均为名义尺度变量，1x取值V和I，2x取值M和Q，3x取值S和A，4x取值B、T和F，5x取值D和K。现有两个样品),,,,(1KTSQVx，),,,,(2KFSMVx这两个样品的第一个变量都取值V，称为配合的，第二个变量一个取Q，一个取M，称为4不配合的。记配合的变量数为1m，不配合的变量数为2m，定义它们之间的距离为21212mmmd（6.2.5）因此1x与2x之间的距离为52。二、相似系数聚类分析方法不仅用来对样品进行分类，而且可以用来对变量进行分类，在对变量进行分类时，常常采用相似系数来度量变量之间的相似性。变量之间的关系越是密切，其相似系数越接近于1（或-1）；反之，它们的关系越是疏远，其相似系数越是接近于0。聚类时，比较相似的变量倾向于归为一类，不怎么相似的变量归属不同的类。变量ix与jx的相似系数用ijC来表示，它一般应满足以下三个条件：（Ⅰ）1ijC，当且仅当baxxji，a)0(a和b为常数；（Ⅱ）1ijC，对一切ji,；（Ⅲ）jiijCC，对一切ji,。最常用的相似系数有如下两种：1．夹角余弦变量ix与jx的夹角余弦定义为2112121)1(nkkjnkkinkkjkiijxxxxC（6.2.6）它是nR中变量ix的观测向量),,,(21niiiixxxx与变量jx的观测向量),,,(21njjjjxxxx之间夹角ij的余弦函数，即ijijCcos)1(。2．相关系数变量ix与jx的相关系数定义为2112121)2(nkjkjnkikinkjkiikiijxxxxxxxxC（6.2.7）相关系数我们曾用ijr来表示，这里表示为)2(ijC是为了与其它相似系数的符号一致。如果5变量ix与jx是已标准化了的，则它们间的夹角余弦就是原变量的相关系数。变量之间常借助于相似系数来定义距离，如令221ijijCd（6.2.8）样品之间有时也用相似系数来度量样品间的相似性程度。一般来说，同一批数据采用不同的相似性度量，会得到不同的分类结果。在进行聚类分析的过程中，应根据实际情况选取好合适的相似性度量。如在经济变量分析中，常采用相关系数来描述变量间的相似性程度。一般情况下，相关系数比其它的相似系数有更强的可变性，但分辨力要弱一些。§6.3系统聚类法系统聚类法是聚类分析诸方法中用得最多的一种，其基本思想是：开始将n个样品各自作为一类，并规定样品之间的距离和类与类之间的距离，然后将距离最近的两类合并成一个新类，计算新类．．与其它类的距离（注：未合并的类之间的距离不用重新计算）；重复进行两个最近类的合并，每次减少一类，直至所有的样品合并为一类。本节介绍常用的八种系统聚类方法，所有这些聚类方法的区别在于类与类之间距离的计算方法不同。以下我们用ijd表示第i个样品与第j个样品的距离，1G，2G，…表示类，KLD表示KG与LG的距离。本节介绍的系统聚类法中，除离差平方和法之外，其余所有的方法因一开始每个样品自成一类，类与类之间的距离与样品之间的距离相同，即KLKLdD，所以起初的距离矩阵全部相同，记为)()0(ijdD。一、最短距离法定义类与类之间的距离为两类最近的样品间的距离，即ijGjGiKLdDLK,min（6.3.1）称这种系统聚类法为最短距离法。用最短距离法的聚类步骤如下：（1）规定样品之间的距离，计算n个样品的距离矩阵)0(D，它是一个对称矩阵。（2）选择)0(D中的最小元素，设为KLD，则将KG与LG合并成一个新类，记为MG，即LKMGGG,。（3）计算新类与任一类JG之间的距离为LJKJijGjGiijGjGiijGjGiMJDDdddDJLJKJM,minmin,minminmin,,,（6.3.2）将)0(D中的qp,行，qp,列用（6.3.2）式并成一个新行新列，新行新列对应MG，所得矩6阵记为)1(D。（4）对)1(D重复上述对)0(D的两步得)2(D，如此下去直至所有元素合并成一类为止。如果某一步)(mD中最小的元素不止一个，则对应这些最小元素的类可以同时合并。例6.3.1设有五个样品，每个只测量了一个指标，分别为1,2,6,8,11，试用最短距离法将它们分类。（1）样品间采用绝对值距离（这时它与其它的明考夫斯基距离完全相同），计算样品间的距离矩阵)0(D，列于表6.2。表6.2)0(D1G2G3G4G5G1G02G103G5404G76205G109530（2）)0(D中最小的元素是112D，于是将1G和2G合并成6G，并利用（6.3.2）式计算6G与其它类的距离，列于表6.3。表6.3)1(D6G3G4G5G6G03G404G6205G9530（3）)1(D中最小的元素是234D，于是将3G和4G合并成7G，并利用（6.3.2）式计算7G与其它类的距离，列于表6.4。表6.4)2(D6G7G5G6G07G405G930（4）)2(D中最小的元素是357D，于是将5G和7G合并成8G，并利用（6.3.2）式计7算7G与其它类的距离，列于表6.5。表6.5)3(D6G8G6G08G40（5）最后将6G和8G合并为9G，这时所有五个样品聚为一类，过程终止。上述聚类过程可以画成一张图，如图6.1所示。横坐标的刻度是并类的距离，从图上看，分两类较为合适。这只是从直观上确定了类的个数为2，关于确定类的个数问题我们将在稍后进行讨论。6.1图二、最长距离法类与类之间的距离定义为两类最远样品间的距离，即ijGjGiKLdDLK,max（6.3.3）称这种系统聚类法为最长距离法。最长距离法与最短距离法的并类步骤完全相同，只是类间距离的递推公式有所不同。设某步将类KG与LG合并成一个新类MG，则MG与任一类JG的