聚类分析.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,聚类分析,主讲人：尹婷婷,1,目录,聚类分析背景和定义,聚类的依据,常见的聚类方法,2,1.1,聚类产生的背景,聚类分析起源于分类学，在考古的分类学中人们主要依靠经验和专业知识来实现分类。,随着生产技术和科学的发展，人类的认识不断加深，分类越来越细，要求也越来越高，有时光凭经验和专业知识是不能进行确切分类的，往往需要定性和定量分析结合起来去分类，于是数学工具逐渐被引进分类学中，形成了数值分类学。,后来随着多元分析的引进，聚类分析又逐渐从数值分类学中分离出来而形成一个相对独立的分支。,3,在社会经济领域中存在着大量分类问题。比如：,对我国,30,个省市自治区独立核算工业企业经济效益进行分析，一般不是逐个省市自治区去分析，而较好的做法是选取能反映企业经济效益的代表性指标，如百元固定资产实现利税、资金利税率、产值利税率、百元销售收入实现利润、全员劳动生产率等等，根据这些指标对,30,个省市自治区进行分类，然后根据分类结果对企业经济效益进行综合评价，就易于得出科学的分析。,4,又比如若对某些大城市的物价指数进行考察，而物价指数很多，有农用生产物价指数、服务项目物价指数、食品消费物价指数、建材零售价指数等等。由于要考察的物价指数很多，通常先对这些物价指数进行分类。,总之，需要分类的问题很多，因此聚类分析这个数学工具越来越受到人们的重视，它在数学的领域中都得到了广泛的应用。,5,1.2 聚类分析的定义,聚类分析又称为,群分析,或,分类分析,等分析，是一种重要的分类方法。它是根据事物自身的特征，通过已建立的统计模型对事物进行多元分析方法的一种统计分析，其,目的,在于将,相似,的事物进行归类。这些类不是事先给定的，而是需要通过聚类分析来给以确定类型。,分类一般是对样品分类或者对变量分类，对样品进行分类称为,Q,型聚类分析,，对变量进行分类称为,R,型聚类分析,。,6,2、聚类的依据,为了将样品（或变量）进行分类，就需要研究样品之间关系。目前用的最多的方法有两个：一种方法是用相似系数，性质越接近的样品，它们的相似系数的绝对值越接近于,1,；而彼此无关的样品，它们的相似系数的绝对值越接近于,0.,比较相似的样品归为一类，不怎么相似的样品归为不同的类。另一种方法是将一个样品看做,P,维空间的一个点，并在空间定义距离，距离越近的点归为一类，距离较远的点归为不同的类。,对样品进行聚类分析，通常采用,距离,测量样品之间的相似程度。目前最常用的距离是,明氏距离。,对变量进行进行聚类分析，一般采用,夹角余弦,或,相关系数,。,7,样品相似性的度量,设有,n,个样品 、，每个样品有个指标的测试数据，用矩阵表示为：,称为样品观测值矩阵。用 表示 与 之间的距离，,p,表示,p,维空间，,n,表示样品个数。则有：,8,明氏距离（,闵可夫斯基距离）：,明氏距离的表现公式为：,这里的,p,表示,p,维空间，,q,表示自然数，根据,q,的取值不同又可以分为：,（,1,）绝对值距离（,q=1,）：,9,（,2,）欧氏距离（,q=2,）,欧氏距离是聚类分析中,最常用的距离,。,（,3,）切比雪夫距离（,q=,）,10,变量相似性的度量,多元数据中的变量表现为向量形式，在几何上可用有向线段表示。在对多元数据进行分析时，相对于数据的大小，我们更多的对变量的变化趋势或方向感兴趣。因此变量之间的相似性可以从它们的方向趋同性或相关性进行考察，从而得到,夹角余弦法,和,相关系数,两种度量方法。,11,（,1,）夹角余弦,：,与 看做,p,维空间中的两个向量，这两个向量间的夹角余弦可用下式进行计算,例如在二维空间中，,对 、这两个变量有：,12,（,2,）相关系数：,相关系数经常用来度量变量之间的相似性,，,变量 、,的相关系数定义为：,13,无论是夹角余弦还是相关系数，他们的绝对值都小于等于,1,，作为变量近似值得工具，我们把它们统计为,当,=1,时，说明两个变量完全相似；,当 近似于,1,时，说明两变量非常密切；,当,=0,时，说明两变量完全不一样；,当 近似于,0,时，说明两变量差别很大。,这样，我们把比较相似的变量聚为一类，把不太相似的变量归到不同的类中。,14,3、聚类分析的方法,常见的聚类方法有：,有序样品聚类法、系统聚类法、,K,均值法、模糊聚类法和动态聚类法,等等。,不同的聚类方法可以将样品或变量分成不同的类别，根据分类要求的不同，选择不同的分类方法。,15,（1）有序样品聚类法,许多实际问题中有序事物按一定次序排列的，这样的事物称为有序事物。,如儿童的增重数按年龄排序；历史的研究按时间的先后排序；地质勘探取样资料按地层的深浅排序等。对有序事物分类时不能打乱原先事物的次序。,16,例如：为了了解儿童的生长发育规律，今随机抽样统计了男孩从出生到,11,岁平均增长的重量数据表如下，试问：男孩发育可分为几个阶段？,记与年龄对应的儿童增重数的,11,个数据，表示儿童的增重数，例如 表示,8,岁儿童的平均年增重为,2,(,千克,),。,如果要把增重数 分成保持次序的,3,个组这时可以有 种选择。例如 ，就是一种可选择的分类方法。,17,一个好的分类方法就是应该使处于同一类事物之间的差别尽可能地小，而使类与类之间的差别尽可能地大。为了表示类内部事物与事物的差别，我们借用统计中全距（直径）的计算方法，以 、这个分类为例来说明计算类内差别的方法：,其中第一类 对应的数据为,9.3,、,1.8,、,1.9,，最大值为,9.3,，最小值为,1.8,，这一类的差异我们用全距,9.3-1.8=7.5,第二类 中最大值为,2.0,，最小值为,1.3,，则,2.0-1.3=0.7,第三类 中的最大值为,2.3,，最小值为,1.9,，则,2.3-1.9=0.4,为衡量上述分类方法的优劣，我们计算此种分类方法中的三个类内的平均差异，即规定该分类方法的优劣指标,K,为,18,对于另一种分类方法,1.,、,2,、,3,、,4,、,5,、,6,、,7,、,8,、,9,、,10,、,11,其第一类的类内差异为,7.6,，第二类的类内差异为,0.2,第三类的类内差异为,0.9,。该分类方法的优劣指标,K,为,2.9,。相比之下，此分类方法不如前一种分类方法好。,试问：分三类最好的分类方法应怎么分？,把,11,个有序数据分成,3,类共有,45,种方法，计算每类分法的优劣指标并加以比较，可以得到最好的,(,分三类,),方法为,1,、,2,3,4,5,6,7,、,8,、,9,、,10,、,11,此分类方法的优劣指标,K,是,0.3,19,以同样的方法分析，可知把这,11,个数据分成两类的最好分类方法是,这时的优劣指标,K,为,0.5,20,那么这,11,个数据分成几类为宜呢,?,为此我们分别找到把,11,个数据分成,1,类、,2,类、,、,11,类的最好的分类法，计算出各最好分类方法的优劣指标，列表如下,：,由表可看到，如果把,1,至,11,岁的数据只分成一类时，,K,8,，优劣指标值太大；而对,n,大于,4,时的,K,值相差不多；而当,n,3,或,n,4,时，,K,值已降为,0.30,和,0.20.,而,n=5,及其以上时，,K,相差太小，而类分得太多无意义，因此分成,3,类或,4,类为宜。,21,我们也许可以对分成三类的情况予以如下实际解释；,儿童从,1,岁到,11,岁可分为三个阶段；,1,岁的儿童睡得多吃得多，处于体重增加最快的阶段；,2,岁至,7,岁的儿童处于入学前或刚入学的阶段，体重增加有所减缓，,8,岁至,11,岁后生活规律化，开始进入发育期体重稳定增加。,22,（2）系统聚类法,3.1,系统聚类的基本思想,系统聚类的,基本思想,是：距离相近的样品（或变量）先聚成类，距离相远的后聚成类，过程一直进行下去，每个样品（或变量）总能聚到合适的类中。,系统聚类,过程,是：,假设总共 有,n,个样品（或变量），,第一步：将每个样品（或变量）独自聚成一类，共有,n,类；,第二步：根 据所确定的样品（或变量）“距离”公式，把距离较近的两个样品（或变量）聚合成一类，其 他的样品（或变量）仍各自聚为一类，共聚成,n-1,类；,23,第三步：将“距离”最近的两个类进一步 聚成一类，共聚成,n-2,类；,以上步骤一直进行下去，最后将所有的样品（或变量）聚成 一类。,为了直观地反映以上的系统聚类过程，可以把整 个分类系统地画成一张谱系图。所以 有时系统聚类也称为谱系分析。,24,在进行系统聚类之前，我们首先要定义类与类之间的距离，由类间距离定义的不同产生了不同的系统聚类法，系统聚类法中常用的距离有,最短距离法、最长距离法、中间距离法、重心法,等等。每种距离法的归类步骤是一致的，主要差异是类间距离的计算方法不同。我们以最短距离为例进行说明。,用 表示第,i,个事物与第,j,个事物之间的距离，,设 表示类，用 表示类 与类,之间的距离,25,最短距离法：,定义：即 中任一事物与 任一事物距离的最小值。,最短距离法进行聚类分析的步骤如下：,（,1,）定义样品之间的距离，计算样品的两两距离，得一距离阵，开始时每个样品自成一类。,（,2,）找出距离最小元素，设为 ，则将 与 合并成一个新类，记为,=,，,（,3,）将 与其他类再进行求出最短距离，再进行合并。,（,4,）重复上述步骤，直到所有元素并成一类为止。,26,例,1,，设有,6,个样品，每个只测量一个指标，分别为,1,2,5,7,9,10,，试用最短距离法将他们分类。,（,1,）样品采用绝对值距离，计算样品间的距离阵，如下表,G1,G2,G3,G4,G5,G6,G1,0,G2,1,0,G3,4,3,0,G4,6,5,2,0,G5,8,7,4,2,0,G6,9,8,5,3,1,0,(2),上述矩阵中最小的元素是,D12,，,D56,，于是将,G1,，,G2,合并成,G7,，将,G5,，,G6,合并成,G8,，可知,G7=1,，,2,，,G8=9,，,10,，于是得到新的距离阵：,27,G3,G4,G7,G8,G3,0,G4,2,0,G7,3,5,0,G8,4,2,7,0,在上述距离阵中最小值是,D34=D48=2,，于是,G3,与,G4,合并，再与,G8,合并，成一个新类,G9=5,，,7,，,9,，,10,，将其再与其他类进行计算，得新的距离阵：,G7,G9,G7,0,G9,3,0,(4),最后将,G7,G9,合并成,G10,，这时所有的六种样品聚为一类，过程终止。,28,例,2,对某地,21,个古墓挖掘后，记录每个古墓陪葬的瓷器用具数和陶桶数，分别记为 和 要求按这两个指标对古墓进行分类。数据列表如下：,29,此处 和 均可以看作平面直角坐标系中点的两个坐标，每个古墓可以用该坐标平面上的一个点来表示，得图,2.6.1,。我们采用通常平面上点的距离作为对应的古墓与古墓间的差别。,30,第一，从图和表都可看出两个古墓的最小距离是,1,其中下面几组古墓之间的距离都是,1,；,1,号与,2,号，,5,号与,6,号，,11,号与,5,号，,8,号与,9,号，,12,号与,13,号，,17,号与,18,号，,17,号与,19,号。,把距离为,1,的点合成一类，就得到新的类，把这些新类用实线圈圈起来，分别记为,G1,，,G2,，,G3,，,G4,，,G5,；,31,第二，以两个类元素中的最短距离作为两个类的类间的距离。可计算得目前两个类问的最短距离为 。此处,4,号墓与,G2,中的,11,号墓距离为 。同样，,10,号墓与,G3,的距离为 ，,20,号墓与,G5,的距离都是 。把距离不大于收的类归为一类，则得到新类，如图,2.6.3,中,实线,所圈的集合,。,32,第三，仍以两个类中的最短距离作为两类之间的距离，则现在两个类间的最小距离为,2,，将类的距离小于,2,的类合并成新类。在图,2.6.3,中新的类用,虚线,围成。现在，除去,16,、,21,这两点外，所有的点全在这,4,个类中。,第四，再重复上述的过程，我们最终可以把这,21,个样本归为一类，但是在进行分类的过程中，如果是要求对样本进行分类，在第三步时就可以终止了，这样将,16,号和,21,号单独归为一类，就可以分为,6,类。,33,（,3,）,K,均值法,系统聚类需要计算出不同样品之间的距离，当样本容量较大时，计算量也比较，需要占据非常大的计算机内存空间，这给应用带来一定的困难。,K,均值法是一种快速的分类法，采用该方法得到的结果比较简单。,基本思想,是：将每一个样品分配给最近中心（均值）的类中，具体的算法包括以下步骤：,（,1,）将所有样品分成,K,个初始类；计算每一个类的中心坐标,（,2,）通过欧几里得距离将某个样品划入离中心最近的类中，并对获得样品与失去样品的类，重新计算中心坐标。,（,3,）重复步骤（,2,），直到所有的样品都不能再分配时为止,34,例,3,：假定我们对,A,、,B,、,C,、,D,四个样品分别测量两个变量 和 ，得到结果如下，试将以下样品聚成两类。,样品,变量,A,5,3,B,-1,1,C,1,-2,D,-3,-2,35,第一步,：,我们将这些项目先随意分成两个聚类，比如说（,AB,）和（,CD,），然后计算这两个聚类的中心（均值）的坐标,第二步,：计算某个样品到各类中心的欧几里得距离，然后将该样品分配到最近的一类，先计算,A,到两个类的平方距离：,d,2,(A,，（,AB,）,)=(5-2),2,+(3-2),2,=10,d,2,(A,，（,CD,）,)=(5+1),2,+(3+2),2,=61,由于,A,到（,A,B,）的距离小于到（,C,D,），因此不用重新分配,聚类,中心坐标,（）,2,2,（）,-1,-2,36,再计算,B,到两个类的平方距离：,d,2,(B,，（,AB,）,)=(-1-2),2,+(1-2),2,=10,d,2,(B,，（,CD,）,)=(-1+1),2,+(1+2),2,=9,由于,B,到（,A,B,）的距离大于到（,C,D,），因此,B,要分配给,CD,。于是得到一个新的聚类（,A,）和（,BCD,）,再重新计算中心坐标，如图所示：,聚类,中心坐标,（）,5,3,（,B,）,-1,-1,37,第三步,：再次检查每个样品，以决定是否需要重新分类。计算各样品到各中心的距离平方，得结果如下：,到现在为止，每个样品都已经分配给距离中心最近的类，因此聚类过程到此结束。最终得到,K=2,的聚类结果是,A,独自成一类，,B,、,C,、,D,聚成一类。,聚类,到组中心的距离平方,项目,（）,0,40,41,89,（）,52,4,5,5,38,参考文献：,1,应用多元统计分析,（第二版）,.,朱建平,.,科学出版社,2spss,数据统计与分析,.,夏丽华，谢金玲,.,清华大学出版社,3,基于主元的多元时间序列聚类分析方法研究,.,郭小芳，叶华,.,江苏科技大学,.,4,成分数据的协方差结构分析,.,郑媛媛,.,山西大学,.,39,谢谢观看！,40,