聚类分析.doc

。聚类分析专题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）这里，这种方法称为可变法。四、类平均法类与类之间的平方距离定义为样品对之间平方距离的平均数，即（6.3.7）其中和分别为类和的样品个数，称这种系统聚类法为类平均法。容易得到它的一个递推公式为备注：因为，所以，同理备注完毕。由上所述，有(6.3.8)类平均法较好地利用了所有样品之间的信息，在很多情况下它被认为是一种比较好的系统聚类法。在递推公式（6.3.8）式中，的影响没有被反映出来，为此可将该递推公式进一步推广为(6.3.9)其中，称这种系统聚类法为可变类平均法。对例6.3.1采用类平均法进行聚类。如果我们一开始就将的每个元素都平方，则使用递推公式会方便许多。（1）计算，见表6.9，它是将表6.2的各数平方。表6.9 01025160493640100812590（2）找中的最小元素，它是，将和合并为，计算与（）的距离。这时，由（6.3.8）式计算得同样可算得和，列于表6.10。表6.10 020.5042.54090.52590（3）对重复上述步骤，将和并为，得平方距离矩阵（见表6.11）。表6.11 031.5090.5170将和合并成得（见表6.12），最后将和合并成，聚类过程终止。其聚类图如图6.4所示（此处省略）。表6.12 051.170五、重心法类与类之间的距离定义为它们的重心（均值）之间的欧氏距离。设和的重心分别为和，则和之间的平方距离为（6.3.10）这种系统聚类法称为重心法。重心法在处理异常值方面比其它系统聚类法更稳健，但是在别的方面一般不如类平均法或离差平方和法效果好。六、离差平方和法类、和合并成的新类的（类内）离差平方和分别是它们反映了各自类内样品的分散程度。如果和这两类相距较近，则合并后所增加的离差平方和应较小；否则应较大。于是我们定义和之间的平方距离为（6.3.12）这种系统聚类法称为离差平方和法或Ward法。可以验证，这个距离定义满足通常定义距离所需满足的四个条件。我们现在导出的另一简化表达式。（6.3.13）可见，这个距离与由（6.3.10）式给出的重心法的距离只相差一个常数倍。重心法的类间距离与两类的样品数无关，而离差平方和法的类间距离与两类的样品数有较大关系，两个大的类倾向于有较大的距离，因而不易合并，这往往符合我们对聚类的实际要求。离差平方和法在许多场合下优于重心法，是比较好的一种系统聚类法，但它对异常值很敏感。七、系统聚类法的统一以上我们介绍了常用的八种系统聚类法，所有这些方法的并类原则或过程是完全相同的，不同之处在于类与类之间的距离有不同的定义，因而有不同的距离递推公式。如果能把它们统一成一个公式，则将大大有利于计算机程序的编制。Lance和Williams于1967年将这些递推公式统一了起来，统一的公式为：(6.3.15)其中、和是参数，不同的系统聚类法，它们有不同的取值。对例6.3.1几种方法的聚类结果都相同，但一般而言，不同方法的聚类结果是不完全一样的。各种方法都有其适用的场合，选用哪种方法需视实际情况和对聚类结果的要求而定。为了能取得较好的系统聚类，必须对聚类的一些性质有较清楚的认识。下面我们介绍系统聚类法的两个性质。1单调性令是系统聚类法中第次并类时的距离，如例6.3.1中，用最短距离法时，有且有。如果一种系统聚类法能满足，则称它具有单调性。这种单调性符合系统聚类法的思想，先合并较相似的类，后合并较疏远的类。可以证明，最短距离法、最长距离法、可变法、类平均法、可变类平均法和离差平方和法都具有单调性，但中间距离法和重心法不具有单调性。2空间的浓缩和扩张比较图6.1和图6.2可以看到，对同一问题采用不同的系统聚类法作聚类图时，横坐标的范围可以相差很大，最短距离法的范围，最长距离法的范围。设和是两个元素非负的同阶矩阵，若（对一切），则记作。这个记号仅在本节中使用，请勿与通常涉及非负定矩阵的记号相混淆。设有两种系统聚类法，它们在第步的距离矩阵分别为和，若，则称第一种方法比第二种方法使空间扩张，或第二种方法比第一种方法使空间浓缩。我们以类平均法为基准，其它方法都与它作比较，可以证明有如下一些结论：（1）（短）（平），（重）（平），即最短距离法和重心法比类平均法使空间浓缩。（2）（长）（平），即最长距离法比类平均法使空间扩张。（3）当时，（变平）（平），即这时可变类平均法比类平均法使空间浓缩；当时，（变平）（平），即此时可变类平均法比类平均法使空间扩张；当时，可变类平均法退化为类平均法，即（变平）（平）。以上比较的这些方法中，太浓缩的方法不够灵敏，太扩张的方法灵敏度可能过高而容易失真。类平均法比较适中，它既不太浓缩也不太扩张，因此它被认为是一种比较理想的方法。八、类的个数在聚类过程中类的个数如何来确定才是适宜的呢？这是一个十分困难的问题，人们至今仍未找到令人满意的方法，但这又是一个不可回避的问题。下面我们介绍确定类个数的几种常用方法。1给定一个阈值通过观测聚类图，给出一个你认为合适的阈值，要求类与类之间的距离要大于，有些样品可能会因此而归不了类。这种方法有较强的主观性，这是它的不足之处。如图6.1中，取，即在距离为3.3处切一刀，5个样品分为1，2和6，8，11两个类。2观测样品的散点图如果样品只有两个或三个变量，则可通过观测数据的散点图来确定类的个数。对于三个变量，可使用SAS软件通过旋转三维坐标轴来观测散点图。3统计量设总样品数为，聚类时把所有样品合并成个类，类的样品数和重心分别是和，则，所有样品的总