实用统计方法—— 聚类分析.pptx

实用统计方法实用统计方法 聚类分析聚类分析引言引言引言引言距离的度量距离的度量距离的度量距离的度量k-k-均值聚类及均值聚类及均值聚类及均值聚类及SPSSSPSS实现实现实现实现分层聚类及分层聚类及分层聚类及分层聚类及SPSSSPSS实现实现实现实现附录（聚类的相关附录（聚类的相关附录（聚类的相关附录（聚类的相关MatlabMatlab命令）命令）命令）命令）第1页/共50页引言引言物以类聚、人以群分；物以类聚、人以群分；物以类聚、人以群分；物以类聚、人以群分；但根据什么分类呢？但根据什么分类呢？但根据什么分类呢？但根据什么分类呢？如要想把中国的县分类，就有多种方法如要想把中国的县分类，就有多种方法如要想把中国的县分类，就有多种方法如要想把中国的县分类，就有多种方法可以按照自然条件来分，比如考虑降水、可以按照自然条件来分，比如考虑降水、可以按照自然条件来分，比如考虑降水、可以按照自然条件来分，比如考虑降水、土地、日照、湿度等，土地、日照、湿度等，土地、日照、湿度等，土地、日照、湿度等，也可考虑收入、教育水准、医疗条件、基也可考虑收入、教育水准、医疗条件、基也可考虑收入、教育水准、医疗条件、基也可考虑收入、教育水准、医疗条件、基础设施等指标；础设施等指标；础设施等指标；础设施等指标；既可以用某一项来分类，也可以同时考虑既可以用某一项来分类，也可以同时考虑既可以用某一项来分类，也可以同时考虑既可以用某一项来分类，也可以同时考虑多项指标来分类。多项指标来分类。多项指标来分类。多项指标来分类。第2页/共50页聚类分析聚类分析对对一一个个数数据据，既既可可以以对对变变量量(指指标标)进进行行分分类类(相相当当于于对对数数据据中中的的列列分分类类)，也也可可以以对对观观测测值值(事事件件，样样品品)来来分分类类(相当于对数据中的行分类相当于对数据中的行分类)。当当然然，不不一一定定事事先先假假定定有有多多少少类类，完完全可以按照数据本身的规律来分类。全可以按照数据本身的规律来分类。本本讲讲要要介介绍绍的的分分类类的的方方法法称称为为聚聚类类分分析析（cluster analysis）。对对变变量量的的聚聚类类称称为为R型型聚聚类类，而而对对观观测测值值聚聚类类称称为为Q型型聚聚类类。它它们们在在数数学学上上是是无无区区别别的。的。第3页/共50页饮料数据（饮料数据（drink.txt）1616种饮料的热量、咖啡因、钠及价格四种变量种饮料的热量、咖啡因、钠及价格四种变量种饮料的热量、咖啡因、钠及价格四种变量种饮料的热量、咖啡因、钠及价格四种变量 第4页/共50页如何度量距离远近如何度量距离远近？如如果果想想要要对对100个个学学生生进进行行分分类类，而而仅仅知知道道他他们们的的数数学学成成绩绩，则则只只好好按按照照数数学学成成绩绩分分类类；这这些些成成绩绩在在直直线线上上形形成成100个个点点。这这样样就就可可以以把把接近的点放到一类。接近的点放到一类。如如果果还还知知道道他他们们的的物物理理成成绩绩，这这样样数数学学和和物物理理成成绩绩就就形形成成二二维维平平面面上上的的100个个点点，也也可可以以按按照照距距离离远远近近来分类。来分类。第5页/共50页如何度量距离远近如何度量距离远近？三三维维或或者者更更高高维维的的情情况况也也是是类类似似；只只不不过过三三维维以以上上的的图图形形无无法法直直观观地地画出来而已。画出来而已。在在饮饮料料数数据据中中，每每种种饮饮料料都都有有四四个个变变量量值值。这这就就是是四四维维空空间间点点的的问问题题了。了。第6页/共50页两个距离概念两个距离概念按按照照远远近近程程度度来来聚聚类类需需要要明明确确两两个个概概念念：一一个个是是点点和和点点之之间间的的距距离，一个是离，一个是类和类之间类和类之间的距离。的距离。点点间间距距离离有有很很多多定定义义方方式式。最最简简单的是欧氏距离。单的是欧氏距离。当当然然还还有有一一些些和和距距离离相相反反但但起起同同样样作作用用的的概概念念，比比如如相相似似性性等等，两两点点相相似似度度越越大大，就就相相当当于于距距离离越短。越短。第7页/共50页两个距离概念两个距离概念由由一一个个点点组组成成的的类类是是最最基基本本的的类类；如如果果每每一一类类都都由由一一个个点点组组成成，那那么么点点间间的的距距离离就就是是类类间间距距离离。但但是是如如果果某某一一类类包包含含不不止止一一个个点点，那那么么就就要要确确定定类类间距离，间距离，类类间间距距离离是是基基于于点点间间距距离离定定义义的的：比比如如两两类类之之间间最最近近点点之之间间的的距距离离可可以以作作为为这这两两类类之之间间的的距距离离，也也可可以以用用两两类类中中最最远远点点之之间间的的距距离离或或各各类类的的中中心心之之间的距离来作为类间距离。间的距离来作为类间距离。第8页/共50页两个距离概念两个距离概念在在计计算算时时，各各种种点点间间距距离离和和类类间间距距离离的的选选择择是是通通过过统统计计软软件件的的选选项项实实现现的的。不不同同的的选选择择它它的的结结果果会会不不同同，但但一一般不会差太多。般不会差太多。第9页/共50页向量向量向量向量x=(xx=(x1 1,x,xp p)与与与与y=(yy=(y1 1,y,yp p)之间的距离或相似系数之间的距离或相似系数之间的距离或相似系数之间的距离或相似系数:欧氏距离欧氏距离:Euclidean平方欧氏距离平方欧氏距离:Squared Euclidean夹角余弦夹角余弦(相似系数相似系数1):cosinePearson correlation(相似系数相似系数2):Chebychev:Maxi|xi-yi|Block(绝对距离绝对距离):S Si|xi-yi|Minkowski:Lance距距离离第10页/共50页类类类类GGp p与类与类与类与类GGq q之间的距离之间的距离之间的距离之间的距离D Dpqpq(d(xd(xi i,x,xj j)表示点表示点表示点表示点x xi i G Gp p和和和和x xj j G Gq q之间的距离之间的距离之间的距离之间的距离)最短距离法最短距离法:最长距离最长距离法法:重心法重心法:离差平方和离差平方和:(Wald)类平均法类平均法:在用欧氏距离时在用欧氏距离时,有统一的递推公式有统一的递推公式第11页/共50页最短距离（Nearest Neighbor)x21x12x22x11第12页/共50页最长距离（Furthest Neighbor）x11x21第13页/共50页组间平均连接（Between-group Linkage)第14页/共50页 组内平均连接法（Within-group Linkage)x21x12x22x11第15页/共50页重心法（Centroid clustering):均值点的距离第16页/共50页离差平方和法连接2，41，56，5第17页/共50页红绿（2，4，6，5）8.75 离差平方和增加8.752.56.25 黄绿（6，5，1，5）14.75离差平方和增加14.758.56.25黄红（2，4，1，5）10100故按该方法的连接和黄红首先连接。第18页/共50页有了上面的点间距离和类有了上面的点间距离和类间距离的概念，就可以介间距离的概念，就可以介绍聚类的方法了。绍聚类的方法了。第19页/共50页事先不用确定分多少类：分层聚类事先不用确定分多少类：分层聚类 分分层层聚聚类类或或系系统统聚聚类类（hierarchical cluster）。开开始始时时，有有多多少少点点就就是是多多少类。少类。它它第第一一步步先先把把最最近近的的两两类类（点点）合合并并成成一一类类，然然后后再再把把剩剩下下的的最最近近的的两两类类合并成一类；合并成一类；这这样样下下去去，每每次次都都少少一一类类，直直到到最最后后只只有有一一大大类类为为止止。越越是是后后来来合合并并的的类类，距离就越远。距离就越远。第20页/共50页例例例例:为研究辽宁、浙江、河南、甘肃、青海为研究辽宁、浙江、河南、甘肃、青海为研究辽宁、浙江、河南、甘肃、青海为研究辽宁、浙江、河南、甘肃、青海5 5省份省份省份省份19911991年城年城年城年城镇居民生活消费的分布规律，需要利用调查资料对这镇居民生活消费的分布规律，需要利用调查资料对这镇居民生活消费的分布规律，需要利用调查资料对这镇居民生活消费的分布规律，需要利用调查资料对这5 5个省个省个省个省分类。变量名称及原始数据如下表：分类。变量名称及原始数据如下表：分类。变量名称及原始数据如下表：分类。变量名称及原始数据如下表：变量变量省份省份X1X2X3X4X5X6X7X8辽宁辽宁7.9039.778.4912.9419.2711.052.0413.29浙江浙江7.6850.3711.3513.3019.2514.592.7514.87河南河南9.4227.938.208.2416.179.421.559.76甘肃甘肃9.1627.989.019.3215.999.101.8211.35青海青海10.0628.6410.5210.0516.188.391.9610.81其中，其中，X1：人均粮食支出，人均粮食支出，X2：人均副食支出，人均副食支出，X3：人均烟酒茶支出，等。人均烟酒茶支出，等。第21页/共50页计算两组间的欧式距离，如：计算两组间的欧式距离，如：计算两组间的欧式距离，如：计算两组间的欧式距离，如：D D1212=D=D2121=(7.90-7.68)=(7.90-7.68)2 2+(39.77-+(39.77-50.37)50.37)2 2+(13.29-14.87)+(13.29-14.87)2 2 第22页/共50页Lance和和Williams给出给出(对欧氏距离对欧氏距离)统一统一递推递推公式公式:D2(k,r)=a apD2(k,p)+a aqD2(k,q)+b bD2(p,q)+g g|D2(k,p)-D2(k,q)|前面方法的递推公式可选择参数而得前面方法的递推公式可选择参数而得:方法方法a ai(i=p,q)b b g g最短距离最短距离 0-1/2最长距离最长距离 01/2重心重心 ni/nr -a apa aq 0类平均类平均 ni/nr 0 0 离差平方和离差平方和(ni+nk)/(nr+nk)-nk/(nr+nk)0 中间距离中间距离 1/2 -1/4 0 可变法可变法 (1-b b)/2 b b(1)0 可变平均可变平均 (1-b b)ni/nr b b(1)0 返回第23页/共50页事先要确定分多少类：事先要确定分多少类：k-均值聚类均值聚类 系统聚类法需要计算出不同样品或变量的距离，还要在聚系统聚类法需要计算出不同样品或变量的距离，还要在聚类的每一步都要计算类的每一步都要计算“类间距离类间距离”，相应的计算量自然比，相应的计算量自然比较大；特别是当样本的容量很大时，需要占据非常大的计较大；特别是当样本的容量很大时，需要占据非常大的计算机内存空间，这给应用带来一定的困难。而算机内存空间，这给应用带来一定的困难。而KK均值法是均值法是一种快速聚类法，采用该方法得到的结果比较简单易懂，一种快速聚类法，采用该方法得到的结果比较简单易懂，对计算机的性能要求不高，因此应用也比较广泛。对计算机的性能要求不高，因此应用也比较广泛。K K均值法是麦奎因（均值法是麦奎因（MacQueenMacQueen，19671967）提出的，这种算）提出的，这种算法的基本思想是将每一个样品分配给最近中心（均值）的法的基本思想是将每一个样品分配给最近中心（均值）的类中，具体的算法至少包括以下三个步骤：类中，具体的算法至少包括以下三个步骤：1 1将所有的样品分成将所有的样品分成K K个初始类；个初始类；2 2通过欧氏距离将某个样品划入离中心最近的类中，通过欧氏距离将某个样品划入离中心最近的类中，并对获得样品与失去样品的类，重新计算中心坐标；并对获得样品与失去样品的类，重新计算中心坐标；3 3重复步骤重复步骤2 2，直到所有的样品都不能再分配时为止。，直到所有的样品都不能再分配时为止。第24页/共50页K均值法和系统聚类法一样，都是以距离的远近亲疏为标准进行聚类的，但是两者的不同之处也是明显的：系统聚类对不同的类数产生一系列的聚类结果，而K均值法只能产生指定类数的聚类结果。具体类数的确定，离不开实践经验的积累；有时也可以借助系统聚类法以一部分样品为对象进行聚类，其结果作为K均值法确定类数的参考。下面通过一个具体问题说明K均值法的计算过程。第25页/共50页【例】假定我们对A、B、C、D四个样品分别测量两个变量和得到结果见表5.9。试将以上的样品聚成两类。表表5.9 样品测量结果样品测量结果第26页/共50页第一步：按要求取K=2，为了实施均值法聚类，我们将这些样品随意分成两类，比如（A、B）和（C、D），然后计算这两个聚类的中心坐标，见表5.10所示。表5.10中的中心坐标是通过原始数据计算得来的，比如（A、B）类的，等等。表表5.10 中心坐标中心坐标第27页/共50页第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品分配给最近的一类。对于样品有变动的类，重新计算它们的中心坐标，为下一步聚类做准备。先计算A到两个类的平方距离：由于A到（A、B）的距离小于到（C、D）的距离，因此A不用重新分配。计算B到两类的平方距离：第28页/共50页由于B到（A、B）的距离大于到（C、D）的距离，因此B要分配给（C、D）类，得到新的聚类是（A）和（B、C、D）。更新中心坐标如表5.11所示。表表5.11 更新后的中心坐标更新后的中心坐标第29页/共50页 第三步：再次检查每个样品，以决定是否需要重新分类。计算各样品到各中心的距离平方，得结果见表5.12。到现在为止，每个样品都已经分配给距离到现在为止，每个样品都已经分配给距离中心最近的类，因此聚类过程到此结束。中心最近的类，因此聚类过程到此结束。最终得到最终得到K=2K=2的聚类结果是的聚类结果是A A独自成一类，独自成一类，B B、C C、D D聚成一类。聚成一类。表表5.12 样品聚类结果样品聚类结果第30页/共50页有序样品的聚类分析法有序样品的聚类分析法 一一 有序样品可能的分类数目有序样品可能的分类数目 二二 费希尔最优求解法费希尔最优求解法三三 一个典型例子一个典型例子第31页/共50页以上的系统聚类和以上的系统聚类和KK均值聚类中，样品的地位是均值聚类中，样品的地位是彼此独立的，没有考虑样品的次序。但在实际应用彼此独立的，没有考虑样品的次序。但在实际应用中，有时样品的次序是不能变动的，这就产生了有中，有时样品的次序是不能变动的，这就产生了有序样品的聚类分析问题。例如对动植物按生长的年序样品的聚类分析问题。例如对动植物按生长的年龄段进行分类，年龄的顺序是不能改变的，否则就龄段进行分类，年龄的顺序是不能改变的，否则就没有实际意义了；又例如在地质勘探中，需要通过没有实际意义了；又例如在地质勘探中，需要通过岩心了解地层结构，此时按深度顺序取样，样品的岩心了解地层结构，此时按深度顺序取样，样品的次序也不能打乱。次序也不能打乱。如果用如果用X X（1 1），X X（2 2），X X（n n）表示表示n n个有序的样个有序的样品，则每一类必须是这样的形式，即品，则每一类必须是这样的形式，即X X（i i），X X（i i+1)+1)，X X（j j），其中，其中1 1 i i n n，且，且j j n n，简记为，简记为GGi i =i i，i i+1+1，j j。在同一类中的样品是次序相邻。在同一类中的样品是次序相邻的。这类问题称为有序样品的聚类分析。的。这类问题称为有序样品的聚类分析。第32页/共50页一、有序样品可能的分类数目 n个有序样品共有（n 1）个间隔，分成k类相当于在这（n 1）个间隔中插入k 1根“棍子”。由于不考虑棍子的插入顺序，是一个组合问题，共有 种插法。图5.4 有序样品的分类法第33页/共50页v这就是n个有序样品分成k类的一切可能分法。因此，对于有限的n和k，有序样品的所有可能分类结果是有限的，可以在某种损失函数意义下，求得最优解。所以有序样品聚类分析又称为最优分割，该算法是费希尔（Fisher）最先提出来的，故也称之为费希尔最优求解法。第34页/共50页二、费希尔最优求解法 第35页/共50页第36页/共50页这里需要注意，若要寻找将n个样品分为k类的最优分割，则对于任意的j（k j n）,先将前面j 1个样品最优分割为k 1类，得到p（j 1，k 1），否则从j到n这最后一类就不可能构成k类的最优分割，参见图5.6。再考虑使Lb（n，k）最小的j，得到p（n，k）。因此我们得到费希尔最优求解法的递推公式为 图图5.6 最优分割最优分割第37页/共50页第38页/共50页 第39页/共50页三、一个典型例子【例例5.45.4】为了了解儿童的生长发育规律，今随机为了了解儿童的生长发育规律，今随机抽样统计了男孩从出生到抽样统计了男孩从出生到1111岁每年平均增长的重量岁每年平均增长的重量数据表数据表5.135.13，试问男孩发育可分为几个阶段？，试问男孩发育可分为几个阶段？在分析这是一个有序样品的聚类问题时，我们通过在分析这是一个有序样品的聚类问题时，我们通过图形可以看到男孩增重随年龄顺序变化的规律，从图形可以看到男孩增重随年龄顺序变化的规律，从图图5.65.6中发现男孩发育确实可以分为几个阶段。中发现男孩发育确实可以分为几个阶段。表表5.13 111岁儿童每年平均增长的重量岁儿童每年平均增长的重量第40页/共50页图图5.7 儿童成长阶段分析儿童成长阶段分析 第41页/共50页下面通过有序样品的聚类分析确定男孩发育分成几个阶段较合适。步骤如下：第42页/共50页表表5.14 直径直径 D（i，j）第43页/共50页第44页/共50页 第45页/共50页（3）分类个数的确定。如果能从生理角度事先确定k当然最好；有时不能事先确定k时，可以从Lp（l，k）随k的变化趋势图中找到拐点处，作为确定k的根据。当曲线拐点很平缓时，可选择的k很多，这时需要用其它的办法来确定，比如均方比和特征根法，限于篇幅此略，有兴趣的读者可以查看其它资料。本例从表5.15中的最后一行可以看出k=3，4处有拐点，即分成3类或4类都是较合适的，从图5.8中可以更明显看出这一点。第46页/共50页第47页/共50页第48页/共50页第49页/共50页