聚类分析部分课件.ppt

1、 多元统计课程设计 之 聚类分析长春工业大学聚类分析概述 聚类分析又称群分析，它是研究（样品或指标）分类问题的一种多元统计方法。所谓类，通俗的说，就是指相似元素的集合。在社会经济领域中存在着大量 分类问题。比如，在经济学中，根据人均国民收入、人均工农业产值和人均消费水平等多项指标对世界上所有国家的经济发展状况进行分类。世界上，按经济发展水平可以将各个国家和地区划分为发达国家、发展中国家和贫困落后国家等。聚类分析的目的是把分类对象按一定规则分成若干类，这些类不是事先给定的，而是根据数据的特征确定的，对类的数目和类的结构不必作任何假定。聚类分析也能用来概括数据而不只是为了寻找“自然的”或“实在的”

2、分类。判别分析与聚类分析的关系 判别分析是在已知研究对象分成若干类型（或组别）并已取得各种类型的一批已知样品的观测数据，在此基础上根据某些准则建立判别式，然后对未知类型的样品进行判别分类。对于聚类分析来说，一批给定样品要划分的类型事先并不知道，正需要通过聚类分析来给以确定类型。正因为如此，判别分析和聚类分析往往联合起来使用，例如判别分析是要求先知道各类总体情况才能判断新样品的归类，当总体分类不清楚时，可先用聚类分析对原来的一批样品进行分类，然后再用判别分析建立判别式以对新样品进行判别。聚类分析与判别分析、主成分 分析、回归分析等方法联合起来使用，往往效果更好。聚类分析根据分类对象不同分 为Q型

3、聚类分析型聚类分析和R型聚类分析型聚类分析。Q型聚类型聚类是指对样品样品进行聚类，R型聚类型聚类是指对变量变量进行聚类。教材中主要介绍Q型聚类。聚类分析内容非常丰富，有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。我们主要介绍系统聚类法。在对样品（或变量）进行分类时，很直观地，我们认为在同一类里的的这些对象在某种意义上倾向于彼此相似，而在不同类里的对象倾向于不相似。多元统计分析中，样品（或变量）之间的这种相似性用距离和相似系数来度量。距离和相似系数距离常用来度量样品之间的相似性相似系数常用来度量变量之间的相似性 样品之间的距离和相似系数有着各种不同的定义，而这些

4、定义与变量的类型有着非常密切的关系。变量的类型 通常变量按测量尺度的不同可以分为以下三类：（1）间隔尺度变量间隔尺度变量：变量用连续的量来表示，如长度、重量、速度、温度等；（2）有序尺度变量有序尺度变量：变量度量时不用明确的数量表示，而是用等级来表示，如某产品分为一等品、二等品、三等品等有次序的关系。（3）名义尺度变量名义尺度变量：变量用一些类表示，这些类之间既无等级关系，也无数量关系，如性别职业、产品的型号等。距离 设 为第i个样品的第j个指标，数据矩阵表如下：ijx 在上表中，每个样品有p个变量，故每个样品都可以看成是 中的一个点，n个样品就是 中的n个点。在 中需定义某种距离，将第i个样

5、品与第j个样品之间的距离记为 ,在聚类过程冲，相距较近的点倾向于归为一类，相距较远的点应归属不同的类。pRijdpRpR距离的性质 距离 一般应满足如下四个条件：（1），对一切i，j；（2），当且仅当第i个样品与第j个样品的 各变量值都相同；（3），对一切i，j；（4），对一切i，j，k。ijd0ijd 0ijd ijjiddijikkjddd常用距离定义vMinkowski（明考夫斯基）距离（明氏距离）第i个样品与第j个样品间的明氏距离明氏距离定义为：明氏距离有以下三种特殊形式：（1）当q=1时，成为绝对值距离绝对值距离,也常被称为“城市街区”距离；（2）当q=2时，称为欧氏距欧氏距 离离，

6、这是聚类分析中最常用的一个距离；（3）当q=时，称为契比雪契比雪夫距离。夫距离。11()qpqijikjkkdqxx1(1)pijikjkkdxx1 221(2)pijikjkkdxx1()maxijikjkkpdxx 当各变量的单位不同或测量值范围相差很大时，不应直接采用明氏距离，而应先对各变量的数据作标准化处理，然后用标准化后的数据计算距离。最常用的标准化处理是其中 为第j个变量的样板均值，为第j个变量的样本方差。*ijjijjjxxxsjxjjs 明氏距离特别是其中的欧氏距离是人们比较熟悉的也是使用最多的距离。但明氏距离存在不足之处，主要表现在两个方面：第一,它与各指标的量纲有关；第二，

7、它没有考虑指标之间的相关性。除此以外，从统计的角度上看，使用欧氏距离要求一个向量的n个分量是不相关的且具有相同的方差，或者说各坐标对欧氏距离的贡献是同等的且变差大小也是相同的，这时使用欧氏距离才合适，效果也较好，否则就有可能不能如实反映情况，甚至导致错误的结论。故一个合理的做法，就是对坐标加权，这就产生了“统计距离”。比如设 ，且Q的坐标是固定的，点P的坐标相互独立地变化。用 表示p个变量 的n次观测的样本方差，则可定义P到Q的统计距离为：所加的权是 ，即用样本方差除相应坐标。当取 时，就是点P到原点O的距离。若 时，为欧氏距离。12,pPx xx12,pQy yy1122,ppsss12,p

8、x xx22211221122(,)ppppxyxyxyd P Qsss121122111,pppkkksss120pyyy1122ppsssv兰氏（Lance和Williams）距离当 时，可以定义第i个样品与第j个样品间的兰氏距离兰氏距离为这个距离与各变量的单位无关。由于它对大的异常值不敏感，故适用于高度偏斜的数据。兰氏距离有助于克服各指标之间量纲的影响，但与明氏距离一样，也没有考虑指标建的相关性。0,1,2,;1,2,ijxin jp11()pikjkijkikjkxxdLpxxv马氏（Mahalanobis）距离 第i个样品与第j个样品间的马氏距离为 ，S为样本协方差矩阵。马氏距离的优

9、点是考虑到了变量间的相关性，且与各变量的单位无关。除此之外，他还有一些优点，如可以证明，将原数据作线性变换，马氏距离仍不变等。但马氏距离有一个很大的缺陷，就是马氏距离公式中的S难以确定。因此，在实际聚类分析中，马氏距离不理想。1()ijijijdMxxSxx12,iiiipxxxx12,jjjjpxxxxv斜交空间距离 第i个样品与第j个样品间的斜交空间距离斜交空间距离定义为其中 是变量 与 间的相关系数。当p个变量互不相关时，即斜交空间距离退化为欧氏距离（除相差一个常数倍）。1 2*2111ppijikjkiljlklkldxxxxrpklrkxlx*(2)ijijddp 以上几种距离的定义

10、均要求变量是间隔尺度的，如果使用的变量是有序尺度或名义尺度的，则又吸纳供应的一些定义距离的方法。某培训学院资料如下（名义尺度变量）：这两名学员的第二个变量都取值“英”，称为配合的配合的，第一个变量取值不同，称为不配合的不配合的。一般地，记配合的变量数为 ，不配合的变量数为 ，则它们之间的距离可定义为故上述两个样本之间的距离为2/3。1x 男，英，统计，非教师，校外，本科2x 女，英，金融，教师，校外，本科以下1m2m21212mdmm相似系数 聚类分析方法不仅用来对样品进行分类，而且可用来对变量进行分类，在对变量进行分类时，常常采用相似系数来度量变量之间的相似性。变量之间的这种相似性度量，在一

11、些应用中要看相似系数的大小，而在另一些应用中要看相似系数绝对值的大小。相似系数（或其绝对值）越大，认为变量之间的相似性程度就越高；反之，则越低。聚类时，比较相似的变量倾向于归为一类，不太相似的变量归属不同的类。相似系数性质 变量 与 的相似系数用 来表示，它一般应满足如下三个条件：（1），当且仅当 和b为常数；（2），对一切i，j；（3），对一切i，j。ixjxijc1ijc ,(0)ijxaxb a1ijcijjicc最常用的相似系数有两种：1.夹角余弦夹角余弦 变量 与 的夹角余弦夹角余弦定义为它是 中变量 的观测向量 与变量 的观测向量 之间的夹角 的余弦函数，即 。ixjx11 222

12、11(1)nkikjkijnnkikjkkx xcxxnRix12,iinixxxjx12,jjnjxxxij(1)cosijijc2.相关系数相关系数 变量 与 的相关系数相关系数定义为样本相关系数我们曾用 来表示，这里表示为 是为了与其他相似系数符号一致。若变量与变量 是已标准化了的，则它们间的夹角 余弦就是相关系数。ixjx11 22211(2)nkiikjjkijnnkiikjjkkxxxxcxxxxixjxijr(2)ijc 变量之间常借助于相似系数来定义距离，如令 ，同样，样品之间的相似系数也由类似的定义。距离度量的是样品（或变量）间的差异程度，相似系数度量的是样品（或变量）间的相

13、似程度。221ijijdc 一般来说，同一批数据采用不同的相似性度量，会得到不同的分类结果。在进行聚类分析的过程中，应根据实际情况选取合适的相似性度量。如在经济变量分析中，常用相关系数来描述变量间的相似性程度。一般情况下，相关系数比其他的相似系数有更强的可变性，但分辨力要弱一点。系统聚类法 系统聚类法是聚类分析诸方法中用得最多的一种，其基本思想是：开始将n个样品各自作为一类，并规定样品之间的距离和类与类之间的距离，然后将距离最近的两类合并成一个新类，计算新类于其他类的距离；重复进行两个最近类的合并，每次减少一类，直至所有的样品和为一类。常用的系统聚类法有八种，这些聚类方法的区别在于类与类之间距

14、离的计算方法不同。这里我们用 表示第i个样品与第j个样品的距离，表示类 表示 与 的距离。所有的系统聚类法一开始每个样品自成一类，类与类之间的距离与样品之间的距离相同（除离差平方和法之外），即 ，所以起初的距离矩阵全部相同，记为 。ijd12,G G KLDKGLGKLKLDd(0)ijDdv最短距离法 定义类与类之间的距离为两类最近样品间的距离，即称这种系统聚类法为最短距离法（最短距离法（single linkage method）,minKLKLiji Gj GDd最短距离法聚类步骤：（1）规定样品之间的距离，计算n个样品的距 离矩阵 ，它是一个对称矩阵；（2）选择 中的最小元素，设为 ，

15、则将 和 合并成一个新类 ，即 0D 0DKLDKGLGMG,MKLGGG（3）计算新类 与任一类 之间的距离的递推公 式为在 中，和 所在的行和列合并成一个新行新列,对应 ，该行列上的新距离值由上式计算，其余行列上的距离值不变，即得新的距离矩阵，记作 。（4）对 重复上述步骤得 ，如此下去直至所有元 素合并成一类为止。MGJG,minminmin,min min,MJkJLJMJijijiji Gj Gi Gj Gi Gj GKJLJDdddDD 0DKGLGMG 1D 1D 2D 如果某一步的距离矩阵中最小的元素不止一个，则称此现象为结结，对应这些最小元素的类可以任选一堆合并或同时合并。最

16、短距离法最容易产生结。v最长距离法 类与类之间的距离定义为两类最远样品间的距离,即称这种系统聚类法为最长距离法最长距离法（complete linkage method）。最长距离法与最短距离法的并类步骤完全相同，只是类间距离的递推公式有所不同。设某步将类 和 合并成新类 ，则 与任一类 的距离为,maxKLKLiji Gj GDdKGLGMGMGJGmax,MJKJLJDDD 最长距离法容易被异常值严重地扭曲，这是值得我们在应用中注意的问题。一个有效的方法是删去这些异常值后再进行聚类。v中间距离法 类与类之间的距离既不取两类最近样品间的距离，也不取两类最远样品间的距离，而是取介于两者中间的距

17、离，称为中中间距离法（间距离法（median method）。）。设某一步将 与 合并为 ，对于任一类 ，考虑由 、和 为边长组成的三角形，取 边的中线作为 ，则 的计算公式为这就是中间距离法的递推公式。中间距离法可推广为更一般的情形，将上式三项的系数依赖于某个参数 ，即这里 ，这种方法称为可变法可变法。KG2222111224MJKJLJKLDDDDLGMGJGKJDLJDKLDKLDMJDMJD222212MJKJLJKLDDDD1v类平均法 类平均法类平均法（average linkage method）有两种定义，一种定义方法是把类与类之间按的距离定义为所有样品对之间的平均距离，即定义

18、 和 之间的距离为其中 和 分别为类 和 的样品个数，为中的样品i与 中的样品j之间的距离。其递推公式：KGLG,1KLKLiji Gj GKLDdn nKnLnKGLGijdKGLGKLMJKJLJMMnnDDDnn 另一种定义方法是定义类与类之间的平方距离为样品对之间的平方距离的平均值，即它的递推公式类似于前面的递推式，即类平均法较好地利用了所有样品之间的信息，在很多情况下它被认为是一种比较好的系统聚类法。22,1KLKLiji Gj GKLDdn n222KLMJKJLJMMnnDDDnn 在上面的递推式中，的影响没有被反映出来，为此可将递推公式进一步推广为其中 ，称这种系统聚类法为可变

19、类平均法可变类平均法。若采用第二种距离定义的类平均法进行聚类，我们可以一开始就将 的每个元素都平方,则使用递推公式会比较方便。KLD22221KLMJKJLJKLMMnnDDDDnn1 0Dv重心法 类与类之间的距离定义为它们的重心（均值）之间的欧氏距离。设 和 的重心分别为 和 ，则 和 之间的平方距离为这种系统聚类法称为重心法重心法（centroid hierarchical method）。它的递推公式为KGLGKxLxKGLG 22KLKLx xKLKLDdxxxx22222KLKLMJKJLJKLMMMnnn nDDDDnnn 重心法在处理异常值方面比其他系统聚类法更稳健，但在别的方

20、面一般不如类平均法和离差平方和法的效果好。v离差平方和法（ward方法）类中各样品到类重心（均值）的平方欧氏距离之和称为（类内）离差平方和离差平方和。设类 和 合并成新类 ，则 、和 的离差平方和分别是KGLGMGKGLGMG KKiKiKi GWxxxx LLiLiLi GWxxxx MMiMiMi GWxxxx 它们反映了各自类内样品的分散程度。如果 和 这两类相距较近，则合并后所增加的离差平方和 应较小；否则，应较大。于是我们定义 和 之间的平方距离为这种系统聚类法称为离差平方和法离差平方和法或ward方方法法（wards minimum variance method）。KGLGMKL

21、WWWKGLG2KLMKLDWWW 也可表达为可见这个距离与重心法的距离只相差一个常数倍。重心法的类间距离与两类的样品数无关，而离差平方和法的类间距离与两类的样品数有较大的关系，两个大的类倾向于有较大的距离，因而不易合并，这往往符合我们对聚类的实际要求。2KLD 2LKKLKLKLMn nDxxxxn 离差平方和法在许多场合下优于重心法，是比较好的一种系统聚类法，但它对异常值很敏感。离差平方和法的平均距离递推公式为2222JKJLJMJKJLJKLJMJMJMnnnnnDDDDnnnnnn 一般来说，只要聚类的样品数目不是太少，各种聚类方法所产生的聚类结果一般是不同的，甚至会有大的差异。各种系

22、统聚类法都有其适用的场合，选用哪种方法需视实际情况和对聚类结果的要求而定。系统聚类法性质1.单调性 令 是系统聚类法中第i次并类时的距离。若一种统聚类法能满足 ，则称它具有单单调性调性。这种单调性符合系统聚类法的思想，先合并较相似的类，后合并较疏远的类。可以证明，最短距离法、最长距离法、可变法、类平均法、可变类平均法和离差平方和法都具有单调性，但中间距离法和重心法不具有单调性。123DDDiD2.空间的浓缩与扩张 设有两种系统聚类法，它们在第i步的距离矩阵分别为 和 ，若 ，则称第一种方法比第二种方法更使空间扩张使空间扩张，或第二种方法比第一种方法更使空间浓使空间浓缩缩。我们以类平均法为基准，

23、其他方法都与它作比较，有：（1）最短距离法和重心法比类平均法更使空间浓缩；（2）最长距离法比类平均法更使空间扩张；（3）当 ，可变类平均法比类平均法更使空间浓缩；当 ，可变类平均法比类平均法更使空间扩张。iA,0,1,2,1iB in,iiAB1,2,1in010 比较以上这些方法可见，太浓缩的方法不够灵敏，太扩张的方法可能因灵敏度过高而容易失真。类平均法比较适中，它既不太浓缩也不太扩张，因此它被认为是一种比较理想的方法。类的个数确定类个数的几种常用的方法：v给定一个阙值T 通过观测树形图，给出一个你认为合适的阙值T，要求类与类之间的距离要大于T，有些样品可能会因此而归不了类或只能自成一类。这

24、种方法有较强的主观性，这是它的不足之处。v观测样品的散点图 如果样品只有两个或三个变量，则可通过观测数据的散点图来确定类的个数。对于三个变量，可使用SAS软件通过旋转三位坐标轴从各个角度来观测散点图。若变量超过三个，则可将原始变量综合成两个或三个综合变量，然后再观测这些综合变量的散点图。观测散点图还有一个重要的用途，即从直觉上来判断所采用的聚类方法是否合理，甚至有时直接从散点图中进行主观的分类，效果也许会好于正规的聚类方法。v使用统计量（1）统计量 越大，表明k个类分得越开。因此，统计量可用于评价合并成k个类时的聚类效果，值越大，聚类效果越好。的取值范围在0与1之间，它总是随着分类个数的减少而

25、变小。聚类刚开始时，n个样品各自为一类，这时 ；当n个样品最后合并成一类时一般来说，我们希望类的个数尽可能地少，同时 又保持较大。因此，类个数的进一步减少一般不应以的大为减少作为代价。2R2R2R2R2R21R 20R 2R2R（2）半偏 统计量 半偏 值是上一步 值与该步 值之差，因此半偏 值越大，说明上一次聚类的效果越好。2R2R2R2R2R（3）伪F统计量 伪F值越大，表明此时的分类效果越好。（4）伪 统计量 伪 值达，表明上一次的聚类的效果是好的。2t2t动态聚类法 Q型系统聚类法一般是在样品间距离矩阵的基础上进行的，故当样品的个数n很大（如n100)时，系统聚类法的计算量是非常大的，

26、将占据大量的计算机内存空间和较多的计算时间，甚至会因计算机内存或计算时间的限制而无法进行。因此，当n很大时，我们需要一种相比系统聚类法而言计算量少得多，以致计算机运行时只需占用较少内存空间和较短计算时间的聚类方法。动态聚类法动态聚类法（或称逐步聚类法逐步聚类法）正是基于这种考虑而产生的一种方法。由于该方法不必确定距离矩阵，在计算机运行中也不必存储基本数据，因此同系统聚类法相比，这种方法更适用于大的数据集，而且n越大，它的优越性就越突出。动态聚类法的基本思想是，选择一批凝聚点或给出一个初始的分类，让样品按某种原则、向凝聚点凝聚，对凝聚点进行不断的修改或迭代，直至分类比较合理或迭代稳定为止。类的个

27、数k可以事先指定，也可以在聚类过程中确定。选择初始凝聚点（或给出初始分类）的一种简单方法是采用随机抽选（或随机分割）样品的方法。动态聚类法有许多种方法，主要介绍k均值法。k均值法基本步骤为：（1）选择k个样品作为初始凝聚点，或者将所有样品分成k个初始类，然后将这k个类的重心（均值）作为初始凝聚点；（2）对除凝聚点之外的所有样品逐个归类，将每个样品归入凝聚点离它最近的那个类（通常采用欧氏距离），该类的凝聚点更新为这一类目前的均值，直至所有样品都归了类。（3）重复步骤（2），直至所有样品都不能再分配。最终的聚类结果在一定程度上依赖于初始凝聚点或初始分类的选择。经验表明，聚类过程中的绝大多数重要变化

28、均发生在第一次再分配中。有序样品分类法 有序样品的分类实质上是找一些分点，将有序样品划分为几个分段，每个分段看作一个类，所以分类也称为分割。显然分点取在不同的位置就可以得到不同的分割。通常寻找最好分割的一个依据就是使各段内部样品之间的差异最小，而各段样品之间的差异较大。有序样品聚类法就是研究这种最优分割法。系统聚类法，被分类的样品是相互独立的，分类时彼此是平等的。而有序样品分类法要求样品按一定的顺序排列，分类时不能打乱次序。模糊聚类法 模糊聚类法是将模糊集的概念用到聚类分析中所产生的一种聚类方法，它是根据研究对象本身的属性而构造一个模糊矩阵，在此基础上根据一定的隶属度来确定其分类关系。SAS实

29、现proc cluster data=method=name;var variables;copy varibles;rmsstd variable;id variable;by variables;freq variable;run;除第一语句为必需语句外，其余均为可选择语句。Rmsstd语句出现时，freq语句必需出现，其余情况下可选。不能省略的说明项：1.method=name或M=name=用来确定聚类方法name：（1）average/ave=类平均法；（2）centroid/cen=重心法；（3）complete/com=最长距离法；（4）density/den=密度估计法；（5）

30、eml=最大似然谱系聚类；（6）flexible/fle=可变类平均法；（7）mcquitty/mcq=mcquitty相似分析方法;（8）median/med=中间距离法；（9）single/sin=最短距离法；（10）two stage/two=两阶段密度估计法；（11）ward/war=离差平方和法2.Cluster过程选项：（1）指定输入与输出数据集（）data=；命名包含进行聚类的观测的输入SAS数据集，若数据集类型为type=distance，则数据被认为是距离矩阵，若数据不是type=distance，数据被认为是坐标数据,并计算欧氏距离；（）outtree=；生成记录并类过程的

31、输出SAS数据集，画树状图的tree过程使用该数据集作为输入数据集。若缺省，数据集采用data n规则命名，且该数据集为临时数据集。若不想生成此输出数据集，使用outtree=_null_;（2）指定聚类方法细节beta=n=对method=flexible等规定beta，n应小于1，通常介于0与-1之间，缺省值为 -0.25，Milligan建议对有较多异常值的数据集采用更小的beta值，如beta=-0.5；（3）控制聚类之前的数据处理（）nonorm=防止将距离规范化为单位均值或单位均方，若与m=ward一起使用，阻止过程用总平方和去除类间平方和来得到平方半偏相关；（）nosquare=

32、阻止过程在m=ave，cen，med或war方法中输入的距离被平方；（4）控制聚类历史过程的输出（）noid=在聚类历史过程中每次产生的合并时不输出id值；（）print=n/p=n=指定输出的聚类历史过程的层数。p=n表只输出最后n层，p=的值须为非负整数。缺省时，输出全部聚类过程；p=0不输出聚类历史过程；（）pseudo=输出伪F和伪t方统计量，此时数据为坐标数据，或m=ave，cen，war时才有效；（）rmsstd=输出每一类均方根标准差，此时数据为坐标数据，或m=ave，cen，war时有效；（）rsquare/rsq=输出R方和半偏R方，此时数据为坐标数据，或m=ave，cen时有效，m=war时，R方和半偏R方总会输出；copy语句=将其列出的变量（一般是var等语句没有列出的）从输入数据集复制到outtree=数据集中，以备后用。