聚类分析专题
聚类分析专题§6.1 引言俗话说，“物以类聚，人以群分”，在自然科学和社会科学等各领域中，存在着大量的分类问题。分类学是人类认识世界的基础科学，在古老的分类学中，人们主要靠经验和专业知识进行定性的分类，很少利用数学工具进行定量的分类。随着人类科学技术的发展，对分类的要求越来越高，以致有时仅凭经验和专业知识难以确切地进行分类，于是人们逐渐地把数学工具引用到了分类学中，这便形成了数值分类学这一学科，之后又将多元分析的技术引入到数值分类学，便又从数值分类学中分离出一个重要分支聚类分析。与多元分析的其它分析方法相比，聚类分析方法较为粗糙，理论上还不够完善，正处于发展阶段。但是，由于该方法应用方便，分类效果较好，因此越来越为人们所重视。这些年来聚类分析的方法发展较快，内容越来越丰富。判别分析与聚类分析都是研究事物分类的基本方法，它们有着不同的分类目的，彼此之间既有区别又有联系。各种判别分析方法都要求对类有事先的了解，通常是每一类都有一个样本，据此得出判别函数和规则，进而可对其它新的样品属于哪一类作出判断。对类的事先了解和确定常常可以通过聚类分析得到。聚类分析的目的是把分类对象按一定规则分成若干类，这些类不是事先给定的，而是根据数据的特征确定的。在同一类里的这些对象在某种意义上倾向于彼此相似，而在不同类里的对象倾向于不相似。聚类分析能够用来概括数据而不只是为了寻找“自然的”或“实在的”分类。例如，在选拔少年运动员时，对少年的身体形态、身体素质、生理功能的各种指标进行测试，据此对少年进行分类，分在同一类里的少年这些指标较为相近。类确定好之后，可以根据各类的样本数据得出选材的判别规则，作为选材的依据。又如，根据啤酒中含有的酒精成分、纳成分、所含的热量“卡路里”数值，可以对啤酒进行分类。聚类分析根据分类对象不同分为型聚类分析和型聚类分析。型聚类分析是指对样品进行聚类，型聚类分析是指对变量进行聚类。本章我们主要讨论型聚类。§6.2 距离和相似系数在对样品（或变量）进行分类时，样品（或变量）之间的相似性是如何度量的呢？这一节中，我们介绍两个相似性度量距离和相似系数，前者常用来度量样品之间的相似性。后者常用来度量变量之间的相似性。样品之间的距离和相似系数有着各种不同的定义，而这些定义与变量的类型有着非常密切的关系。通常变量按测量尺度的不同可以分为以下三类：（1） 间隔尺度变量：变量用连续的量来表示，如长度、重量、速度、温度等。（2） 有序尺度变量：变量度量时不用明确的数量表示，而是用等级来表示，如某产品分为一等品、二等品、三等品等有次序关系。（3） 名义尺度变量：变量用一些类表示，这些类之间既无等级关系也无数量关系，如性别、职业、产品的型号等。我们这里主要讨论具有间隔尺度变量的样品聚类分析方法。一、距离设为第个样品的第个指标，数据矩阵列于表6.1。每个样品有个变量，故每个样品都可以看成是中的一个点，个样品就是中的个点。在中需定义某种距离，第个样品与第个样品之间的距离记为，在聚类过程中，距离较近的点倾向于归为一类，距离较远的点应归属不同的类。所定义的距离一般应满足如下四个条件：（） ，对一切；（） ，当且仅当第个样品与第个样品的各变量值相同；（） ，对一切；（） ，对一切。表6.1 数据矩阵变量样品12常用的距离有如下几种：1明考夫斯基(Minkowski)距离第个样品与第个样品间的明考夫斯基距离定义为（6.2.1）这里为某一自然数，这是一个最常用最直观的距离。当时，称为绝对值距离；当时，称为欧氏距离；当时，称为切比雪夫距离。当各变量的单位不同或虽单位相同但各变量的测量值相差很大时，不应直接采用明考夫斯基距离，而应先对各变量的数据作标准化处理，然后用标准化后的数据计算距离。最常用的标准化处理是，令，其中，为第个变量的样本均值，为第个变量的样本方差。2马氏(Mahalanobis)距离第个样品与第个样品间的马氏距离为（6.2.2）其中，为样本协方差矩阵。使用马氏距离的好处是考虑到了各变量之间的相关性，并且与各变量的单位无关。不足之处是对马氏距离公式中的，若始终不变，则往往显得不妥；若要随聚类过程而不断变化，则会有许多不便。3兰氏(Lance和Williams)距离当，时，则可以定义第个样品与第个样品间的兰氏距离为（6.2.3）这个距离与各变量单位无关，但没有考虑变量间的相关性。由于它对大的异常值不敏感，故适用于高度偏斜的数据。4斜交空间距离由于样品的各个变量之间往往存在不同程度的相关关系，因此有时采用欧氏距离显得不够理想，有人建议采用斜交空间距离。第个样品与第个样品间的斜交空间距离定义为其中是变量与变量间的相关系数。当个变量互不相关时，即斜交空间距离退化为欧氏距离（除相差一个常数倍外）。以上几种距离的定义均要求变量是间隔尺度的，如果使用的变量是有序尺度或名义尺度的，则有相应的一些定义距离的方法。下例是对名义尺度变量的一种距离定义。例6.2.1 设有五个变量均为名义尺度变量，取值和，取值和，取值和，取值、和，取值和。现有两个样品，这两个样品的第一个变量都取值，称为配合的，第二个变量一个取，一个取，称为不配合的。记配合的变量数为，不配合的变量数为，定义它们之间的距离为（6.2.5）因此与之间的距离为。二、相似系数聚类分析方法不仅用来对样品进行分类，而且可以用来对变量进行分类，在对变量进行分类时，常常采用相似系数来度量变量之间的相似性。变量之间的关系越是密切，其相似系数越接近于1（或-1）；反之，它们的关系越是疏远，其相似系数越是接近于0。聚类时，比较相似的变量倾向于归为一类，不怎么相似的变量归属不同的类。变量与的相似系数用来表示，它一般应满足以下三个条件：（），当且仅当，和为常数；（），对一切；（），对一切。最常用的相似系数有如下两种：1夹角余弦变量与的夹角余弦定义为（6.2.6）它是中变量的观测向量与变量的观测向量之间夹角的余弦函数，即。2相关系数变量与的相关系数定义为（6.2.7）相关系数我们曾用来表示，这里表示为是为了与其它相似系数的符号一致。如果变量与是已标准化了的，则它们间的夹角余弦就是原变量的相关系数。变量之间常借助于相似系数来定义距离，如令（6.2.8）样品之间有时也用相似系数来度量样品间的相似性程度。一般来说，同一批数据采用不同的相似性度量，会得到不同的分类结果。在进行聚类分析的过程中，应根据实际情况选取好合适的相似性度量。如在经济变量分析中，常采用相关系数来描述变量间的相似性程度。一般情况下，相关系数比其它的相似系数有更强的可变性，但分辨力要弱一些。§6.3 系统聚类法系统聚类法是聚类分析诸方法中用得最多的一种，其基本思想是：开始将个样品各自作为一类，并规定样品之间的距离和类与类之间的距离，然后将距离最近的两类合并成一个新类，计算新类与其它类的距离（注：未合并的类之间的距离不用重新计算）；重复进行两个最近类的合并，每次减少一类，直至所有的样品合并为一类。本节介绍常用的八种系统聚类方法，所有这些聚类方法的区别在于类与类之间距离的计算方法不同。以下我们用表示第个样品与第个样品的距离，表示类，表示与的距离。本节介绍的系统聚类法中，除离差平方和法之外，其余所有的方法因一开始每个样品自成一类，类与类之间的距离与样品之间的距离相同，即，所以起初的距离矩阵全部相同，记为。一、最短距离法定义类与类之间的距离为两类最近的样品间的距离，即（6.3.1）称这种系统聚类法为最短距离法。用最短距离法的聚类步骤如下：（1）规定样品之间的距离，计算个样品的距离矩阵，它是一个对称矩阵。（2）选择中的最小元素，设为，则将与合并成一个新类，记为，即。（3）计算新类与任一类之间的距离为（6.3.2）将中的行，列用（6.3.2）式并成一个新行新列，新行新列对应，所得矩阵记为。（4）对重复上述对的两步得，如此下去直至所有元素合并成一类为止。如果某一步中最小的元素不止一个，则对应这些最小元素的类可以同时合并。例6.3.1 设有五个样品，每个只测量了一个指标，分别为1,2,6,8,11，试用最短距离法将它们分类。（1）样品间采用绝对值距离（这时它与其它的明考夫斯基距离完全相同），计算样品间的距离矩阵，列于表6.2。表6.2 0105407620109530（2）中最小的元素是，于是将和合并成，并利用（6.3.2）式计算与其它类的距离，列于表6.3。表6.3 0406209530（3）中最小的元素是，于是将和合并成，并利用（6.3.2）式计算与其它类的距离，列于表6.4。表6.4 040930（4）中最小的元素是，于是将和合并成，并利用（6.3.2）式计算与其它类的距离，列于表6.5。表6.5 040（5）最后将和合并为，这时所有五个样品聚为一类，过程终止。上述聚类过程可以画成一张图，如图6.1所示。横坐标的刻度是并类的距离，从图上看，分两类较为合适。这只是从直观上确定了类的个数为2，关于确定类的个数问题我们将在稍后进行讨论。二、最长距离法类与类之间的距离定义为两类最远样品间的距离，即（6.3.3）称这种系统聚类法为最长距离法。最长距离法与最短距离法的并类步骤完全相同，只是类间距离的递推公式有所不同。设某步将类与合并成一个新类，则与任一类的距离为（6.3.4）对例6.3.1采用最长距离法，与前面相同，将和合并成，计算（）的公式为，的计算结果列于表6.6。表6.6 05072010530中的最小元素是，合并和成，计算（）的公式为，的计算结果列于表6.7。表6.7 0701050中的最小元素为，将和合并成，见表6.8。计算的公式为最后将和并为。其聚类图如图6.2所示，它与图6.1有相似的形状，但并类的距离要比图6.1大一些，仍分为两类为宜。表6.8 0100最长距离法可能被异常值严重地扭曲，这是值得我们在应用中注意的问题。一个有效的方法是删去这些异常值之后再进行聚类。三、中间距离法类与类之间的距离既不取两类最近样品间的距离，也不取两类最远样品间的距离，而是取介于两者中间的距离，称之为中间距离法。设某一步将和合并为，对于任一类，考虑由、和为边组成的三角形（如图6.3所示），取边的中线作为。由初等平面几何可知，的计算公式为（6.3.5）这就是中间距离法的递推公式。中间距离法可推广为更一般的情形，将（6.3.5）式三项的系数依赖于某个参数，即（6.3.6）这里，这种方
