《第六讲聚类分析》由会员分享,可在线阅读,更多相关《第六讲聚类分析(112页珍藏版)》请在金锄头文库上搜索。
1、n俗话说“物以类聚,人以群分”。就是聚类分析的道理。n市场营销中市场细分和客户细分问题n学校里有些同学经常会在一起,关系密切;有些同学很少往来,关系疏远。第一节第一节 什么是聚类分析什么是聚类分析 例例 对10位应聘者做智能检验。3项指标X,Y和Z分别表示数学推理能力,空间想象能力和语言理解能力。其得分如下,选择合适的统计方法对应聘者进行归类。应聘者12345678910X28181121262016142422Y29232223292322232927Z28181622262222242424例子例子聚类分析数据格式聚类分析数据格式k例题分析n我们直观地来看,这个归类是否合理? 计算4号和6
2、号得分的离差平方和: (21-20)2+(23-23)2+(22-22)2=1 计算1号和2号得分的离差平方和: (28-18)2+(29-23)2+(28-18)2=236n计算1号和3号得分的离差平方和为482,由此可见一般,归类可能是合理的,欧氏距离很大的应聘者没有被聚在一起。n由此,我们的问题是如何来选择样品间相似的测度指标,如何将有相似性的类连接起来?n基本思想基本思想:根据事物本身的特性研究个体分类的方法;即在没有先验知识的情况下进行的。多元统计分析方法就是对样品或指标进行量化分类的问题,它们讨论的对象是大量的样品,要求能合理地按各自的特性来进行合理的分类,没有任何模式可供参考或依
3、循。n聚类原则聚类原则:同一类中的个体有较大的相似性,不同类中的个体差异很大。n常见方法常见方法:Q型聚类法、R型聚类法、灰色聚类法和模糊聚类法等。聚类分析基本思想及原则聚类分析基本思想及原则聚类的程序n基本程序基本程序:根据一批样品的多个观测指标,具体地找出一些能够度量样品或指标之间相似程度的统计量统计量,然后利用统计量将样品或指标进行归类。 如对上市公司的经营业绩进行聚类;又如对企业的经济效益进行评价n由此可知,聚类分析(Cluster Analysis)也是一种分类技术。与多元分析的其他方法相比,该方法较为粗糙,理论上还不完善,但应用方面取得了很大成功。与多元假设检验、回归分析等一起被称
4、为多元分析的三大方法。n聚类分析的步骤:根据已知数据,计算各观察个体或变量之间亲疏关系的统计量。根据某种准则,使同一类内的差别较小,而类与类之间的差别较大,最终将观察个体或变量分为若干类。 思考:样品点间、样品点和小类之间、小思考:样品点间、样品点和小类之间、小类与小类之间按什么刻画亲疏关系类与小类之间按什么刻画亲疏关系第二节第二节 “亲疏程度亲疏程度”度量度量一、变量测量尺度的类型一、变量测量尺度的类型二、亲疏程度的测度二、亲疏程度的测度三、样品与小类、小类与小类三、样品与小类、小类与小类 之间之间“亲疏程度亲疏程度”的度量方法的度量方法四、聚类分析的几点说明四、聚类分析的几点说明n(1)(
5、1)间隔尺度间隔尺度(Scale):用数量来表示,其数值由测量(连续)或计数(离散)、统计得到。n(2)(2)顺序尺度顺序尺度(Ordinal):没有明确的数量表示,只有次序关系,或虽用数量表示,但相邻两数值之间的差距并不相等,它只表示一个有序状态序列。如评价酒的味道,分成好、中、次三等,三等有次序关系,但没有数量表示。n(3)3)名义尺度名义尺度(Nominal):既没有数量表示也没有次序关系,只有一些特性状态。如眼睛的颜色,化学中催化剂的种类等。一、变量测量尺度的类型一、变量测量尺度的类型二、亲疏程度的测度二、亲疏程度的测度n亲疏程度:包含个体间的相似程度和个体间的差异程度n亲疏程度测定方
6、法: 距离:样品间的聚类,Q型聚类分析。 相似系数:变量间的聚类, R型聚类分析。 1 1、定义、定义距离距离的准则的准则 距离满足条件:(一)距离(一)距离2 2、常用距离的算法、常用距离的算法(数值型变量)(数值型变量)设 和是第i和 j 个样品的观测值,则二者之间的距离为:特别:欧氏距离Euclidean distance(1) (1) 闵可夫斯基距离(闵可夫斯基距离(Minkowski) )绝对距离(block)闵可夫斯基距离缺点闵可夫斯基距离缺点与指标量纲有关未考虑总体变异对“距离”远近的影响。(2)马氏距离(广义欧氏距离)n是印度著名统计学家马哈拉诺比斯是印度著名统计学家马哈拉诺比
7、斯(PCMahalanobis)所定义的一种距离。所定义的一种距离。特点:特点:n考虑了观测变量之间的相关性考虑了观测变量之间的相关性。如果各变量间相互独立,即观测变量的协方差矩阵是对角矩阵,则马氏距离就退化为用各个观测指标的标准差的倒数作为权数进行加权的欧氏距离。n考虑到了各个观测指标取值的差异程度考虑到了各个观测指标取值的差异程度,不再受各指标量纲的影响。将原始数据做线性变换后,马氏距离不变。n为了对马氏距离和欧氏距离进行一下比较,以便更清楚地看清二者的区别和联系,现考虑一个例子。例如,假设有一个二维正态总体,它的分布为: 马氏距离的缺点马氏距离的缺点:样品协方差矩阵不变不合理。切比雪夫距
8、离:(Chebychev)兰氏距离:兰氏距离: 适合于一切变量值大于零的情况。该距离与变量单位无关,对大的异常值不敏感,适用于较大变异的数据,但未考虑变量相关性问题。斜交空间距离可考虑变量间相关性问题000 样品点间的距离表样品点间的距离表3 3、距离选择的原则距离选择的原则n一般来说,同一批数据采用不同的距离公式,会得到不同的分类结果。产生不同结果的原因,主要是由于不同的距离公式侧重点和实际意义都不相同。因此我们在聚类分析时,应注意距离公式的选择。在选择距离公式时应注意以下原则:n应考虑变量类型应考虑变量类型(不同类型变量计算距离的方法不同)n所选择的亲疏测度指标在实际应用中应有所选择的亲疏
9、测度指标在实际应用中应有明确的意义明确的意义。(欧几里得距离具有明确的空间距离的概念,马氏距离有消除量纲影响的作用)n要综合考虑对要综合考虑对样本观测数据的预处理和将要采用的聚类样本观测数据的预处理和将要采用的聚类分析方法分析方法。(如在进行聚类分析之前已经对变量作了标准化处理,则通常采用欧几里得距离)n适当地考虑适当地考虑研究对象的特点和计算工作量的大小研究对象的特点和计算工作量的大小。(在实际中,聚类分析前不妨试探性地多选择几个距离公式分别进行聚类,然后对聚类分析的结果进行对比分析,以确定最合适的距离测度方法。)(二)相似系数(二)相似系数n夹角余弦时从向量集合的角度所定义的一种测度变量之
10、间亲疏程度的相似系数。设在n维空间的向量1、夹角余弦、夹角余弦 2 2、相关系数、相关系数有:有:例如夹角余弦夹角余弦相关系数相关系数 三、个体与小类、小类与小类间三、个体与小类、小类与小类间 “亲疏程度亲疏程度”的度量方法的度量方法1 、最短距离(Nearest Neighbor)x21x12x112、最长距离(Furthest Neighbor )x11x213、组间平均连接(Between-group Linkage) 4、组内平均连接法(Within-group Linkage) 每一步均考虑了小类内部相似性的变化 克服了最远、最近距离中距离受极端值影响的特点5、重心距离(Centro
11、id clustering) 该方法充分利用了所涉及的距离信息,同时将小类的样本数也考虑进来了n是Ward提出的。其原则是:聚类过程中使小类内离差平方和增加最小的两小类首先合并为一类。n步骤:首先各个体自成一类,然后逐步凝聚成小类。随着小类的不断凝聚,类内离差平方和必然不断增大。应选择使类内离差平方和增加最小的两类凝聚,直到所有个体合并成一类为止。6、离差平方和法连接(Wards method)例如:例如:例:5商厦个体间欧氏距离CASEEuclidean distanceABCDEABCDE0.0008.06217.80426.90730.4148.0620.00025.45634.6553
12、8.21017.80425.4560.0009.22012.80626.90734.6559.2200.0003.60630.41438.21012.8063.6060.000例题分析nD、E首先聚成一类,A、B、C与该小类n最近邻距离依次为26.907、34.655、9.22n最远距离30.414、38.210、12.806n组间平均连接距离(26.907+30.414)/2、(34.655+38.210)/2、(9.22+12.806)/2n组内平均连接距离(26.907+30.414+3.606)/3、(34.655+38.210+3.606)/3、(9.22+12.806+3.606)
13、/3n重心法: 四、聚类分析的几点说明四、聚类分析的几点说明(1 1)1 1、选择变量、选择变量 (1)根据聚类分析的目的选择聚类变量(聚类是在选变量的基础上对样本数据进行的,分类结果是各变量综合计算的结果) (2)各变量的变量值不应有数量级上的差异(数量级对距离有较大影响,将影响最终聚类结果) (3)变量之间不能高度相关(如变量间有较强的线性相关关系,那么计算距离时同类变量将重复“贡献”,将在距离中有较高的权重,因而使最终的聚类结果偏向该类变量)2 2、计算相似性指标。、计算相似性指标。3 3、聚类、聚类 (1)选择聚类的方法 (2)确定形成的类数 根据分类问题本身的专业知识结合实际需要来选
14、择;用多种分类方法去作,把其中的共性取出来,反映了事物的本质,将有争议的样品暂放在一边;观察样品散点图,从直觉上来判断所采用的聚类方法是否合理。4 4、聚类结果的解释和证实、聚类结果的解释和证实 对聚类结果进行解释是希望对各个类的特征进行准确的描述,给每类起一个合适的名称。这一步可以借助各种描述性统计量进行分析,通常的做法是计算各类在各聚类变量上的均值,对均值进行比较,还可以解释各类别的原因。 四、聚类分析的几点说明四、聚类分析的几点说明(2)第三节第三节 系统聚类法系统聚类法一、含义:一、含义:又叫层次聚类。聚类过程是又叫层次聚类。聚类过程是按一定层次进行的,有按一定层次进行的,有Q Q型聚
15、类和型聚类和R R型型聚类。聚类。二、聚类步骤二、聚类步骤三、常用的聚类方法三、常用的聚类方法四、系统聚类法的性质四、系统聚类法的性质二、步骤:n1、对数据进行变换处理,消除量纲;n2、构造n个类,每个类只包含一个样品;n3、n个样品两两间的距离dij;n4、合并距离最近的两类为一新类;n5、计算新类与当前各类的距离,重复(4)、(5),直到所有的类合并为一类;n6、画聚类图;n7、决定类的个数和类。 1、根据样品的特征,规定样品之间的距离 ,共有 个。将所有距离列表,记为D D(0)表。 2、选择D D(0)表中最小的非零数,不妨假设 ,于是将 和 合并为一类,记为 。3、分别删除D(0)表
16、的第p行和第q列,并新增一行和一列,利用递推公式计算新类与其它类之间的距离。产生D(1)表。4、在D(1)表再选择最小的非零数,其对应的两类又构成新类,分别删除D(1)表的相应的行和列,并新增一行和一列,再利用递推公式计算新类与其它类之间的距离。结果,产生D(2)表。类推直至所有的样本点归为一类为止。例题:下表给出了某地区九个农业区的七项指标表表 某地区九个农业区的七项经济指标数据某地区九个农业区的七项经济指标数据 区代号人均耕地x1(hm2/人)劳均耕地x2(hm2/个)水田比重x3(%)复种指数x4(%)粮食亩产x5(kg/ hm2)人均粮食x6(kg/人)稻谷占粮食比重x7(% )G10
17、.2941.0935.63113.64510.51036.412.2G20.3150.9710.3995.12773.5683.70.85G30.1230.3165.28148.56934.5611.16.49G40.1790.5270.391114458632.60.92G50.0810.21272.04217.812249791.180.38G60.0820.21143.78179.68973636.548.17G70.0750.18165.15194.710689634.380.17G80.2930.6665.3594.93679.5771.77.8G90.1670.4142.994.8
18、4231.5574.61.17 表表 极差标准化处理后的数据极差标准化处理后的数据x1x2x3x4X5X6X7G10.911.000.070.150.181.000.14G21.000.870.000.000.000.240.00G30.200.150.070.440.440.080.07G40.440.380.000.130.180.130.00G50.030.031.001.001.000.451.00G60.030.030.610.690.650.130.59G70.000.000.900.810.840.131.00G80.910.530.070.000.100.430.09G90.3
19、80.260.040.000.150.000.00它们经过极差标准化处理后,如下表所示。 根据上述数据,计算可得九个农业区之间的绝对值距离矩阵如下 在距离矩阵D中,除对角线元素外,d49=d94=0.51为最小者,故将第4区与第9区并为一类,划去第9行和第4列; 在余下的元素中,除对角线元素外,d75= d57=0.83为最小者,故将第5区与第7区并为一类,划掉第7行和第5列; 在第二步之后余下的元素之中,除对角线元素外,d82= d28=0.88为最小者,故将第2区与第8区并为一类,划去对应的行和列; 在第三步之后余下的元素中,除对角线元素外,d43= d34=1.23为最小者,故将第3区与
20、第4区并为一类,划去对应的行和列,此时,第3、4、9区已归并为一类; 用Block距离计算距离,对某地区的九个农业区进行聚类分析,步骤如下: 在第四步之后余下的元素中,除对角线元素外,d21= d12=1.52为最小者,故将第1区与第2区并为一类,划去对应的行和列,此时,第1、2、8区已归并为一类; 在第五步之后余下的元素中,除对角线元素外,d65= d56=1.78为最小者,故将第5区与第6区并为一类,划去对应的行和列,此时,第5、6、7区已归并为一类; 在第六步之后余下的元素中,除对角线元素外,d31= d13=3.10为最小者,故将第1区与第3区并为一类,划去对应行、列,此时,第1、2、
21、3、4、8、9区已归并为一类; 在第七步之后余下的元素中,除去对角线元素外,只有d51= d15=5.86,故将第1区与第5区并为一类,划去对应行、列,此时,第1、2、3、4、5、6、7、8、9、区均归并为一类;G1G2G8G3G4G9G5G7G6根据上述步骤,可以作出聚类过程的谱系图n以当前某个样品与已经形成的小类中的各样品距离中的最小值作为当前样品与该小类之间的距离。 Gr= Gp,Gq, drl=mindpl,dql。n类Gp与Gq之间的距离定义为两类最近样品的距离,即:三、常用的种类三、常用的种类1、最短距离法(、最短距离法(Nearest Neighbor) 假设第p类和第q类合并成
22、第r类,第r类与其它各旧类的距离按最短距离法为:最短距离法的分析步骤n定义样品之间的距离,计算n个样品的距离矩阵D(0),开始每个样品自成一类,显然这时Dijdijn找出D(0)中非对角线最小元素,设为Dpq,将Gp和Gq合并为一个新类,记为Gr,即Gr = Gp,Gq 。n按计算公式计算出新类与其它类的距离。n重复以上步骤,直到所有元素并为一类为止。 如果某一步最小元素不止一个,则对应这些最小元素的类可以同时合并。例:为了研究以下5省区某年城镇居民生活消费的分布规律,根据调查资料做类型划分省份x1x2x3x4x5x6x7x8辽宁浙江河南甘肃青海 7.90 7.68 9.42 9.16 10.
23、0639.7750.3727.9327.9828.64 8.49 11.35 8.20 9.0110.5212.9413.30 8.14 9.3210.0519.2719.2516.1715.9916.1811.0514.59 9.42 9.10 8.392.042.751.551.821.9613.2914.87 9.7611.3510.81d12=(7.9-7.68)2+(39.77-50.37)2+(8.49-11.35)2+(12.94-13.3)2+(19.27-19.25)2+(11.05-14.59)2+(2.04-2.75)2+(13.29-14.87)21/2=11.67 d
24、13=13.80 d14=13.12 d15=12.80 d23=24.63 d24=24.06 d25=23.54 d34=2.2 d35=3.51 d45=2.21 1 2 3 4 5D1= 1 0 2 11.67 0 3 13.80 24.63 0 4 13.12 24.06 2.20 0 5 12.80 23.54 3.51 2.21 0河南与甘肃的距离最近,先将二者(3和4)合为一类G6=G3,G4G1=辽宁,G2=浙江,G3=河南,G4=甘肃,G5=青海d61=d(3,4)1=mind13,d14=13.12 d62=d(3,4)2=mind23,d24=24.06d65=d(3,
25、4)5=mind35,d45=2.21 6 1 2 5 6 0D2= 1 13.12 0 2 24.06 11.67 0 5 2.21 12.80 23.54 0d71=d(3,4,5)1=mind13,d14,d15=12.80d72=d(3,4,5)2=mind23,d24,d25=23.54 7 1 2D3= 7 0 1 12.80 0 2 23.54 11.67 0河南、甘肃与青海并为一新类G7=G6,G5=G3,G4,G6G8=G1,G2d78=mind71,d72=12.80 7 8D4= 7 0 8 12.8 0河南3甘肃4青海5辽宁1浙江2 如果某一步最小非零元素不止一个时,则
26、对应于这些最小元素的类可以同时合并。n以当前某个样品与已经形成的小类中的各样品距离中的最大值作为当前样品与该小类之间的距离。n最长距离法的并类与最短距离法的并类步骤完全一样。也就是先将各个样品自成一类,然后将类间距离最短的两类合并。 2 2、最长距离法、最长距离法( furthest neighbor) 假设第p类和第q类合并成第r类,第r类与其它各旧类的距离按最长距离法为:例:对前例的数据以最长距离法聚类。 1 2 3 4 5 1 0 2 11.67 0 D1= 3 13.80 24.63 0 4 13.12 24.06 2.20 0 5 12.80 23.54 3.51 2.21 0d61
27、=d(3,4)1=maxd13,d14=13.80 d62=d(3,4)2=maxd23,d24=24.63d65=d(3,4)5=maxd35,d45=3.51 6 1 2 5 6 0D2= 1 13.80 0 2 24.63 11.67 0 5 3.51 12.80 23.54 0河南与甘肃的距离最近,先将二者(3和4)合为一类G6=G3,G4河南、甘肃与青海并为一新类G7=G6,G5=G3,G4,G6d71=d(3,4,5)1=maxd13,d14,d15=13.80d72=d(3,4,5)2=maxd23,d24,d25=24.63 7 1 2D3= 7 0 1 13.80 0 2 2
28、4.63 11.67 0d78=maxd71,d72=24.63 7 8D4= 7 0 8 24.63 0G8=G1,G2G8=G1,G2河南1甘肃4G6G7G8G9青海5辽宁1浙江23 3、中间距离法、中间距离法 最长距离夸大了类间距离,最短距离低估了类间距离。介于两者间的距离即为中间距离。 例例:对对5 5个个样样品品(1 1、2 2、3.53.5、7 7、9 9)进进行行分分类类。用用绝绝对对距离计算距离计算距离平方距离平方矩阵:矩阵:(1)将每个样品看作自成一类,因此Dij=dij,得下表。G6G3G4G5G6=X1、X20G3 =X340G4 =X430.2512.250G5 =X5
29、56.2530.2540(2)找出上表中非对角线最小元素是1,则将G1,G2合并为一个新类G6.计算新类与其它类的距离。(3)找出上表中非对角线最小元素是4,则将G3,G6合并为一个新类G7,将G4,G5合并为一个新类G8.最后计算它们的距离。G7G8G7 =X1、X2、 X30G8=X4 、X530.250X1X2 X3X4X5G6G7G8G91444、类平均法:、类平均法:两类间样品距离的平均数。对两类间样品距离的平均数。对应组间平均连接应组间平均连接n用两类样品两两之间的距离的平方和的平均值作为两类间的距离的平方。它利用了所有样品对距离的信息。设聚类到某一步将Gp和Gq合并为Gr,则任一
30、类Gl与Gr的距离为:G1G2G3G4G5G1=X10G2 =X210G3 =X3 6.252.250G4 =X4362512.250G5 =X5644930.2540 找出上表中非对角线最小元素是1,则将G1,G2合并为一个新类G6.按类均法计算新类与其它类的距离。 例例:对对5 5个个样样品品(1 1、2 2、3.53.5、7 7、9 9)进进行行分分类类。用用绝绝对对距离计算距离计算距离平方距离平方矩阵:矩阵:G6G3G4G5G6=X1、X20G3 =X34.250G4 =X430.512.250G5 =X556.530.2540 找出上表中非对角线最小元素是4,则将G4,G5合并为一个
31、新类G7.按类平均法计算新类与其它类的距离。G6G3G7G60G3 4.250G7 43.521.250 找出上表中非对角线最小元素是4.25,则将G3,G6合并为一个新类G8.按类均法计算新类与其它类的距离。G6G7G60G7 36.080X1X2 X3X4X5G6G8G7G914.25436.085 5、中间距离法的变形、中间距离法的变形可变法可变法 如果让中间距离法的递推公式前两项的系数也依赖于,则递推公式为: 6、可变类平均法、可变类平均法n由于类平均法中没有反映Gp和Gq之间的距离Dpq的影响,所以给出可变类平均法。对所有样品对的距离求平均值,包括小类之间的样品对、小类内的样品对。计
32、算公式为: 用此递推公式进行聚类就是可变类平均法。递推公式由: p类和q类与L类的距离的加权平均数 p类和q类的距离两项的加权和构成,的大小根据哪项更重要而定的大小根据哪项更重要而定 可变类平均法与可变法的分类效果与可变类平均法与可变法的分类效果与的选择的选择关系很大,在实际应用中关系很大,在实际应用中常取负值常取负值。G1G2G3G4G5G1=X10G2 =X210G3 =X3 6.252.250G4 =X4362512.250G5 =X5644930.2540 找出上表中非对角线最小元素是1,则将G1,G2合并为一个新类G6.按可变类均法计算新类与其它类的距离。取-1/4。得下表。 例例:
33、对对5 5个个样样品品(1 1、2 2、3.53.5、7 7、9 9)进进行行分分类类。用用绝绝对对距离计算距离计算距离平方距离平方矩阵:矩阵:G6G3G4G5G6=X1、X20G3 =X35.060G4 =X437.8812.250G5 =X570.3830.2540 上表中非对角线最小元素是4,则将G4,G5合并为一个新类G7. 计算新类与其它类的距离。G6G3G7G6=X1、X20G3 =X35.060G7 =X4 、 X566.6625.560 上表中非对角线最小元素是5.06,则将G3,G6合并为一个新类G8. 计算新类与其它类的距离。G6G7G6=X1、X2 、 X30G7 =X4
34、 、 X564.940X1X2 X3X4X5G6G8G7G915.06464.947 7、离差平方和法:、离差平方和法:是Ward提出的,基本思想来自于方差分析的想法,如类分得恰当,同类内的样品之间的离差平方和应较小,而类间的离差平方和应当较大。将k固定时,要选择使S达到极小的分类,一切可能的分法有:nWard 寻找到一个局部最优解的方法。n先将n个样本各成一类,然后每次缩小一类,每缩小一类离差平方和就要增大,选择使离差平方和S增加最小的两类合并,直至所有样本归为一类为止。n如果分类正确,同类样品的离差平方和应该较小,类与类的离差平方和应当较大。因此应使小类内各样本的欧氏欧氏距离距离总平方和增
35、加最小的两小类合并为一类。用Ward法分类。(1)将五个样品各自分成一类,显然这时类内离差平方和S=0。(2)将一切可能的任意两列合并,计算所增加的离差平方和,取其中较小的S所对应的类进行合并,例如将G1=X1 , G2 =X2合并成一类,它的离差平方和S12=(1-1.5)2+(2-1.5)2=0.5,如果将G1=X1 ,G3 =X3合并成一类,它的离差平方和为 S13=(1-2.25)2+(3.5-2.25)2=3.125。将一切可能的两类合并的离差平方和都计算出来,并列表如下: 例:例:对对5 5个样品(个样品(1 1、2 2、3.53.5、7 7、9 9)进行分类)进行分类G1G2G3
36、G4G5G1=X10G2 =X20.50G3 =X33.125 1.1250G4 =X41812.56.1250G5 =X53224.515.12520 上表中非对角线最小元素是0.5,说明将G1,G2合并为一个新类G6增加的S最少. 计算新类G6与其它类的距离,得下表。G6G3G4G5G6=X1、X20G3 =X32.6670G4 =X420.1676.1250G5 =X537.515.12520 上表中非对角线最小元素是2,则将G4,G5合并为一个新类G7. 计算新类G7与其它类的距离。G6G3G7G6=X1、X20G3 =X32.6670G7 =X4 、 X542.2513.50 上表中
37、非对角线最小元素是2.667,则将G3,G6合并为一个新类G8. 计算新类G8与其它类的距离。G6G7G6=X1、X2 、 X30G7 =X4 、 X540.830X1X2 X3X4X5G6G8G7G90.52.667240.83 分别为Gp和Gq的重心,类与类之间的距离定义为两个类重心(类内样品平均值)间的平方距离。8、重心法:也称为样品的均值法。设Gp和Gq 为两个类重心法递推公式重心法递推公式 假设第p类和第q类合并成第r类,第r类与其它各旧类的距离按重心法为: 重心法的归类步骤与以上方法基本相同,所不同的是每合并一次,就要重新计算新类的重心及各类与新类的距离。GrGl例:设5个样品(1
38、,2,3.5,7,9)。重心法的初始距离与中间距离法相同。G1G2G3G4G5G1=X10G2 =X210G3 =X3 6.252.250G4 =X4362512.250G5 =X5644930.2540找出上表中非对角线最小元素是1,则将G1,G2合并为一个新类G6.计算新类的重心,其与其它类的距离。G6G3G4G5G6=X1、X20G3 =X340G4 =X430.2512.250G5 =X556.2530.2540找出上表中非对角线最小元素是4,则将G3,G6合并为一个新类G7,将G4,G5合并为一个新类G8.最后计算它们的距离。G7G8G7 =X1、X2、 X30G8=X4 、X534
39、.030X1X2 X3X4X5G6G7G8G9144几种系统聚类方法的统一 以上聚类方法的计算步骤完全相同,仅类与类之间距离的定义不同。Lance(兰斯)和Williams(威廉姆斯)于1967年将其统一为:几种系统聚类法公式的参数 方法pq最短距离法0-1/2最长距离法0中间距离法-1/40重心法np/nrnq/nr-pq0类平均法np/nrnq/nr00可变类平均法(1-) np/nr(1-) nq/nr10可变法(1-)/2(1-)/210离差平方和法(np+nl)/( nr+ nl)(nq+nl )/( nr+ nl)-nl/( nr+ nl)0 实例分析选取指标 y1人均GDP,它反
40、映了经济社会发展的总体状况和一般水平; y2人均第三产业增加值,它反映了人均服务产品占有量或服务密度; y3第二产业增加值比重,它反映了工业化水平和产业结构现代化程度; y4第三产业增加值比重,它反映了第三产业的发展程度及其对国民经济的贡献; y5第三产业从业人员比重,它反映了第三产业对劳动力的吸纳能力; y6第三产业固定资产投资比重,它反映了第三产业的资金投入程度; y7城市化水平,它反映了农村人口转化为城市人口的程度及对服务的需求量。 例: 对中国大陆31个省级区域第三产业综合发展水平进行类型划分及差异性程度分析- 用标准差标准化方法对7项指标的原始数据进行处理。 采用欧氏距离测度31个省
41、(市、区)之间的样本间距离。 选用组平均法计算类间的距离,并对样本进行归类。具体的数据与计算过程在此略。经过上述聚类计算步骤,得到的聚类结果见下图。 聚类计算聚类计算( (计算过程计算过程 ) ) 样本 Num +-+-+-+-+-+ 安徽 12 河南 16 甘肃 28 四川 23 贵州 24 河北 3 山东 15 山西 4 湖北 17 重庆 22 陕西 27 宁夏 30 江西 14 湖南 18 广西 20 云南 25 江苏 10 浙江 11 广东 19 福建 13 辽宁 6 黑龙江 8 吉林 7 新疆 31 内蒙古 5 青海 29 海南 21 西藏 26 北京 1 上海 9 天津 2 图图
42、中国中国31个省级区域第三产业发展水平组平均聚类谱系图个省级区域第三产业发展水平组平均聚类谱系图 聚类结果分析当类间距离取为4.0和2.5时,全国各省份被合并成以下几类: 上海、北京、天津3直辖市为一类,而上海和北京更接近; 西藏、海南为一特殊类;青海、内蒙古、新疆、吉林为一类,其中内蒙古、新疆、吉林合并为一亚类;江苏、浙江、广东、福建、辽宁、黑龙江为一类,其中江苏、浙江、广东合并为一亚类; 重庆、陕西、宁夏、江西、湖南、广西为一类,其中重庆、陕西、宁夏和江西、湖南、广西各自为一亚类,云南为一孤立点; 河北、山东、山西、湖北为一类; 安徽、河南、甘肃、四川、贵州为一类。例:例:为了更深入地了解
43、我国人口的文化程度状况,现利用1990年全国人口普查数据对全国30个省、市进行聚类分析。分析选用了三个指标(1)大学以上文化程度的人口占全部人口的比例(X1);(2)初中文化程度的人口占全部人口的比例(X2);(3)文盲半文盲的人口占全部人口的比例(X3)。用它们分别来反映较高、中等、较低文化程度人口的状况,原始数据如下:地区序号X1X2X3北京19.3030.558.70天津24.6729.388.92河北30.9624.6915.21山西41.3829.2411.30内蒙51.4825.4715.39辽宁62.6032.328.81吉林72.1526.3110.49黑龙江82.1428.4
44、610.87上海96.5331.5911.04江苏101.4726.4317.23浙江111.1723.7417.461990年全国人口普查文化程度人口比例()地区序号X1X2X3安徽120.8819.9724.43福建131.2316.8715.63江西140.9918.8416.22山东150.9825.1816.87河南160.8526.5516.15湖北171.5723.1615.79湖南181.1422.5712.10广东191.3423.0410.45广西200.7919.1410.61海南211.2422.5313.97四川220.9621.6516.241990年全国人口普查文
45、化程度人口比例()地区序号X1X2X3贵州230.7814.6524.27云南240.8113.8525.44西藏260.573.8544.43陕西261.6724.3617.62甘肃271.1016.8527.93青海281.4917.7627.70宁夏291.6120.2722.06新疆301.8520.6612.751990年全国人口普查文化程度人口比例() 首先计算样品之间的相似系数,使用最长距离法、重心法和Ward法,分别计算,并画出聚类图(从略),聚类结果为:第一类:北京、天津、山西、辽宁、吉林、黑龙江、上海。其中大部分是东部经济、文化较发达的地区。第二类:安徽、宁夏、青海、甘肃、
46、云南、贵州。其中大部分是西部经济、文化发展较慢的地区。第三类:西藏。经济、文化发展落后的地区。第四类:其它省、市。经济、文化发展处于全国中等水平。分析分析 四、系统聚类法的性质 单调性:设Dk是系统聚类法中的第k次并类时的距离,如果D1D2D3,则称并类距离具有单调性。 可以证明最短距离法、最长距离法、类平均法、离差平方和法、可变法和可变类平均法都具有单调性,而中间距离法、重心法不具有单调性。这种单调性符合系统聚类法的思想,先合并较相近的类,然后合并较疏远的类。空间的浓缩与扩张 通过前面的例题可以看出,对于同一问题采用不同聚类法作图 时,横坐标的范围可相差很大。与类平均法相比类平均法相比最短距
47、离法与重心法 比较浓缩;最长距离法、离差平方和法、可变类平均比较扩张;类平类平 均法均法比较适中。 太浓缩的方法不够灵活,太扩张的方法可能因灵敏度过高而容易 失真。类平均法类平均法比较适中。它既不太浓缩,也不太扩张。相对而言它 被认为是一种比较理想的方法。第四节第四节 K K均值聚类均值聚类(快速聚类)(快速聚类)n一、思想一、思想n二、原理二、原理n三、凝聚点的选择三、凝聚点的选择n四、四、R R型聚类型聚类n五、确定类的个数五、确定类的个数n六、各种聚类方法的比较六、各种聚类方法的比较n七、聚类的应用七、聚类的应用n小结小结 一、思想一、思想 当样本点数量十分庞大时,则用系统聚类是一件非常
48、繁重的工作,且聚类的计算速度也比较慢。作出的树状图也十分复杂, 不便于分析。比如在市场抽样调查中,有4万人就其对衣着的偏好作了回答,希望能迅速将他们分为几类。这时,采用系统聚类法就很困难,因此人们提出能否先给出一个初始的分类(初始分类不一定完全合理),然后按照某种原则进行修改,直至分类达到合理为止。 如果选择了N个数值型变量参与聚类分析,最后要求聚类数K,那么可以由系统首先选择K个观测量作为聚类的种子,也称初始类中心、凝聚点初始类中心、凝聚点。二、原理二、原理(1)按照一定的原则,选择k个初始凝聚点(2)根据欧氏距离将每个样品归类。将每个样品归入凝聚点离它最近的那个类。(3)各类的重心代替初始
49、凝聚点(4)重复第(2)、(3)步直至分类达到稳定。即不能再分配为止。三、凝聚点的选择1、经验选择 根据对分类问题的了解,依据经验将分类问题预先确定一个分类数或初始分类,并在每类中选一个有代表性的样品点作为凝聚点。2、运用系统聚类的结果作为参考(以一部分样品为对象进行聚类,结果作为K均值法确定类数的参考与系统聚类比较:都是以距离的远近亲蔬为标准进行聚类的系统聚类对不同的类数产生一系列聚类结果,而快速聚类法只能产生指定类数的聚类结果。具体类数的确定,离不开实践经验的积累。该方法的优点就是计算量小,速度快;缺点是最终结果受初始凝聚点的选择影响。n例:设有5个样品(1,2,6,8,11),试用动态聚
50、类法进行聚类,且指定k2。步骤为:(1)我们随意将这些样品分成以下两类。四、R型聚类法(指标聚类、变量聚类)对变量聚类,是一种降维的方法。用于在变量众多时寻找有代表性的变量,以便当用少量、有代表性的变量代替大变量时损失信息最少。对指标聚类时,常采用相似系数,相似系数大或距离小则表示类间关系密切。利用几种聚类方法获得的结果是相同的,但一般情况下,结果不完全相同。哪一种方法效果好呢?这就需要提出一个标准作为衡量的依据,但至今还没有一个统一的标准。在实际应用中,一般采用以下两种方法:一种是根据分类问题本身的专业知识结合实际需要来选择分类方法,并确定分类个数。另一种是用多种分类方法去作,把结果中的共性
51、取出来,如果几种方法的某些结果都一样,则说明这样的聚类确实反映了事物的本质,而将有争议的样品暂放在一边或用其它方法进行归类。 计算每类中相关指数的平均值,其中较大者就是该类的代表性指标。 计算公式:代表性指标的选择例如:若体重、胸围、大腿围是研究胖瘦一类中的三个指标,其相关系数如下表:体重胸围大腿围体重1胸围0.82231大腿围0.74030.6411计算体重对胸围及大腿围的指标为: (0.8223)2+(0.7403)2/(3-1)=0.6121计算胸围对体重及大腿围的指标为(0.8223)2+(0.6413)2/(3-1)=0.5445计算大腿围对体重及胸围的指标(0.6413)2+(0.
52、7403)2/(3-1)=0.4331 因此用体重作为研究胖瘦这一类代表性指标。它与实际情况是相符的。五、确定类的个数五、确定类的个数 1、给定阈值通过观测聚类图,给出一个合适的阈值t。要求类与类之间的距离不要超过T值。例如我们给定t=0.35,当聚类时,类间的距离已经超过了0.35,则聚类结束。总离差平方和的分解(准备知识)2、统计量可以证明: 总离差平方和组内离差平方和组间离差平方和 比较大,说明分G个类时类内的离差平方和比较小,也就是说分G类是合适的。但是,分类越多,每个类的类内的离差平方和就越小, 也就越大;所以我们只能取合适的G,使得 足够大,而G本身很小,随着G的增加, 的增幅不大
53、。比如,假定分4类时, =0.8;下一次合并分三类时,下降了许多, =0.32,则分4 类是合适的。 (PG为分为G类的组内离差平方和。) 伪F统计量用于评价聚为G类的效果。如果聚类的效果好,类间的离差平方和相对于类内的离差平方和大,所以应该取伪F统计量较大而类数较小的聚类水平。 3、伪F统计量的定义为PseudoFStatistic0102030405060708090100110120NumberofClusters12345678910111213141516171819其中 分别是的类内离差平方和, 是将K和L合并为第M类的离差平方和 为合并导致的类内离差平方和的增量。用它评价合并第K
54、和L类的效果,伪 统计量大说明不应该合并这两类,应该取合并前的水平。4、伪 统计量的定义为聚类方法很多:除介绍的系统聚类法、动态聚类法外,还有有序样品聚类法、模糊聚类法、灰色聚类法等等。为了便于大家使用这些方法,这里简单介绍一下这些方法的所能解决的哪类问题。系统聚类法,被分的样品是相互独立的,分类时彼此是平等的。动态聚类动态聚类它是先粗糙的进行预分类,然后再逐步调整,直到满意为止。六六 各种聚类方法的比较各种聚类方法的比较(1 1)有序样品聚类法有序样品聚类法要求样品按照一定的顺序排列的,分类时是不能打乱次序的,即同一类样品是必须相互邻接的。比如要将建国以来国民收入的情况划分为几个阶段,此阶段
55、的划分必须依年份的顺序为依据;又如研究天气演变的历史时,样品是按从古到今的年代排列的,年代的次序也是不能打乱的,研究这类样品的分类问题就必须用有序样品聚类法。 有序样品的分类有序样品的分类实质上是找一些分点,将有序样品划分为几个阶段,每个阶段看作一个类,所以分类也称为分割。显然分点取在不同的位置就可以得到不同的分割。通常寻找最好分割的一个依据就是使各段内部样品之间的差异最小,而各段样品之间的差异较大。有序样品聚类法就是研究这种最优分割法。六六 各种聚类方法的比较各种聚类方法的比较(2 2)模糊聚类法模糊聚类法是将模糊集的概念用到聚类分析中所产生的一种聚类方法,它是根据研究对象本身的属性而构造一
56、个模糊矩阵,在此基础上根据一定的隶属度来确定其分类关系的。灰色聚类法灰色聚类法是根据灰色关联矩阵或灰色白化权函数将观测指标或观测对象分成若干个类。灰色聚类按聚类对象划分,可分为灰色关联聚类和灰色白化权函数聚类。灰色关联聚类主要用于同类因素的归并,以使复杂系统简化,通过灰色关联聚类,我们可以检查许多因素中是否有若干个因素关系十分密切,使我们既能够用这些因素的综合平均指标或其中的某一个因素来代表这几个因素,使信息不受严重损失。这属于系统变量的删简问题。灰色白化权函数聚类主要用于检查观测对象是否属于事先设定的不同类别。六六 各种聚类方法的比较各种聚类方法的比较(3 3)七、聚类的应用七、聚类的应用
57、n零售业n将经常同时购买的数据项聚类到一起有利于改善商品的布置,提高销售利润。将具有相似的购买模式的顾客聚类到一起,分析每一类顾客的特征,有利于对特定的顾客群进行特定商品的宣传和销售n信息检索n对文档进行分类,改善信息检索的效率,或者发现某一领域文献的组成结构n医疗分析n对一组新型疾病聚类,得到每类疾病的特征描述,对这些疾病进行识别,提高治疗的功效n发现不属于正常类别的特殊病例,识别组织的病变细胞n天文学n利用聚类分析宇宙仿真系统得到的数据,更好地理解黑洞形成和进化的物理过程小结聚类分析是一种探索性技术,对于同一问题,聚类分析是一种探索性技术,对于同一问题,可获得多种结果,解释需要结合专业知识
58、可获得多种结果,解释需要结合专业知识样品量大可采用快速聚类方法样品量大可采用快速聚类方法变量的形式:距离与相似系数变量的形式:距离与相似系数系统聚类常用方法系统聚类常用方法存在的问题分类数的确定分类数的确定 专业知识专业知识聚类方法的选择聚类方法的选择试用多种方法,如系统聚类与快速聚类相结合试用多种方法,如系统聚类与快速聚类相结合思考题n聚类的基本思想及原则分别是什么n距离的类型(欧氏距离与马氏距离的区别、距离选择的原则)n样品与样品、样品与小类间亲疏程度测定方法有哪些?亲疏测度指标有哪些?n聚类分析的步骤n学会利用重心法和离差平方和法进行系统聚类n如何确定类的个数n聚类分析考虑的主要问题有哪些推荐阅读n中国可持续发展问题特征研究暨中等发达国家可持续发展模式的聚类分析 数量经济技术经济研究 2003.7n基于竞争力聚类分析的企业并购决策方法基于竞争力聚类分析的企业并购决策方法 系统工程,系统工程,2005.4我又学会了一种新的统计分析方法