第四章 聚类分析

第四章聚类分析聚类分析(clusteranalysis)是研究分类问题的多元数据分析方法。聚类分析有极其广泛的分类背景。在经济学中，为了了解不同地区城镇居民的收入及消费情况，往往需要划分不同的类型去研究；在产品质量管理中，要根据各产品的某些重要指标而将其分为一等品、二等品等；在生物学中，要根据各生物体的综合特征进行分类；又如在考古学中，要对某些古生物化石进行科学的分类，等等．随着人类社会的发展与科学技术的进步，对分类学的要求也越来越高。只凭经验或专业知识对研究对象进行分类，往往很不够，有时不能进行确切的分类。于是数学被引进分类学中，形成了数值分类学。随着多元数据分析方法研究的深入，在数值分类学中形成了聚类分析这一分支。聚类分析是多元数据分析的重要组成部分。§4.1聚类的目的多元数据形成数据矩阵，见表4.1。共有n个样品，p个指标x1,x2,…xp。聚类分析有2两种类型：对样品聚类或对变量(指标)聚类。表4.1

数据矩阵指标样品

x1

x2…xj

…xp12…i…n

x11

x12…x1j

…x1px21

x22…x1j…x2p……………….

xi1

xi2…xij…xip………………xk1

xk2…xkj…xnp注意：变量(指标)的选取，取决于聚类的目的。数据的类型有间隔尺度、有序尺度和名义尺度，主要讨论间隔尺度。聚类分析的基本思想是在样品之间定义距离，在变量之间定义相似系数,距离或相似系数代表样品或变量之间的相似程度。按相似程度的大小,将样品(或变量)逐一归类，形成一个表示亲疏关系的聚类图，依次按照某些要求对样品(或变量)进行分类。聚类分析的方法很多,如系统聚类法、动态聚类法、分解法、加入法、模糊聚类法、有序样品聚类法等，我们重点介绍系统聚类法和快速(动态)聚类法。作为聚类分析的出发点，先介绍分类统计量—距离与相似系数。每个样品可看成p维空间的一个点，n个样品组成p维空间的n个点。我们自然用各点之间的距离来衡量样品之间的相似程度（或靠近程度）。§4.2距离和相似系数定义4.1

设E是一个点的集合,d.,.是E到[0,∞]的函数,满足：a.dij≥0，i,jE;b.dij=0

,当且仅当i=j;d.dijdik+dkj

，i,j,kE。则称dij为i与j之间的距离。c.dij=dji，i,jE;定义4.1

设E是一个点的集合,d.,.是E到[0,∞]的函数,满足：a.dij≥0，i,jE;b.dij=0

,当且仅当i=j;d.dijdik+dkj

，i,j,kE。则称dij为i与j之间的距离。c.dij=dji，i,jE;当条件加强为d.dijmax{dik,dkj}时，相应的距离称为极端距离。常用的距离是明考斯基(Minkowski)距离当q=1,2,∞时分别得到Chebyshev(切比雪夫)

距离欧氏距离绝对距离以上距离与各变量指标的量纲有关，为消除量纲的影响，有时应先对数据进行标准化，然后用标准化数据计算距离。标准化数据样品之间聚类主要用到以上提到的各种距离。样品聚类通常称为Q型聚类。在SAS系统中，采用欧氏距离聚类或先将数据标准化，再计算欧氏距离进行聚类。

当对p个指标变量进行聚类时，用相似系数来衡量变量之间相似程度(或关联性程度)。相似系数中最常用的是相关系数与夹角余弦。变量xi,xj的夹角余弦为

变量xi,xj的相关系数为

变量聚类通常称为R型聚类。有时变量之间也可以用距离来描述他们的接近程度。实际上距离和相似系数之间可以相互转化。若dij是一个距离，则是相似系数，若dij是相似系数，则可令或这样转换得到的距离不一定符合距离定义，但用它可以实现聚类。§4.3类和类的特征一、类用G表示类。设G中有k个元素，用i,j等简示。定义4.2

T为一给定的阈值，如果对任意的i,jG有

dij≤T，则称G为一个类。定义4.3对阈值T，如果对每个iG有则称G为一个类。定义4.4对阈值T、V,如果则称G为一个类。二、类的特征类G的元素用X1,X2,…,Xm表示,m为G内的样品数(或变量数),可从不同的角度刻画G的特征,常用的特征有(1)均值或称为类G的重心(2)样本散布阵及协方差阵(3)G的直径有多种定义，例如三、类与类之间的距离设两个类Gp,Gq分别含有np和nq个样品，它们之间的距离用D(p,q)表示，下面是一些常用的定义：（1）最短距离法它等于Gp和Gq中最近的两个样品的距离。（1）最短距离法（2）最长距离法它等于Gp和Gq中最近的两个样品的距离。它等于Gp和Gq中最远的两个样品的距离。（3）重心法它等于两重心和之间的距离。（5）最小方差法（离差平方和法）它与重心法只差一个常数倍。离差平方和法是由Ward提出，又称Ward法。（4）类平均距离法它等于Gp和Gq中任两个样品距离的平均。四、类间距离的递推公式设类Gr由类Gp,Gq合并所得，则Gr包含nr=np+nq个样品。我们的问题是：如何由类Gp和Gq计算其他类Gk与Gr之间的距离。即建立类间距离的递推公式。（1）最短距离法（2）最长距离法（3）类平均距离法

（4）重心法（5）离差平方和法当样品间采用欧氏距离时,则上述类间距离的递推公式有如下的统一形式:其参数见下表。这种形式为编程提供了极大方便。

方法pq最短距离法最长距离法类平均法重心法离差平方和法1/21/2np/nrnp/nr(nk+np)/(nk+nr)1/21/2nq/nrnq/nr(nk+nq)/(nk+nr)000pq-nk/(nk+nr)-1/21/2000其参数见下表。这种形式为编程提供了极大方便。§4.4系统聚类法一、系统聚类法的步骤(A)计算n个样品两两间的距离{dij}，记作D=(dij)；(B)构造n个类，每个类只包含一个样品；(C)合并距离最近的两类为一新类；(D)计算新类与当前各类的距离。若类的个数等于1，转到步骤(E)，否则回到步骤(C)；(E)画聚类图；(F)决定类的个数和类。每一种类间距离用到上述系统聚类程序中就得到一种系统聚类法。通过一个例子来说明系统聚类法。

例4.1

为研究辽宁、浙江、河南、甘肃、青海5省份1991年城镇居民生活消费规律，需要利用调查资料对这5个省份分类。指标变量共8个，含义如下:数据如下表。将每个省份的数据看成一个样品，计算样品之间的欧氏距离矩阵。

x1:人均粮食支出，x2:人均副食支出，

x3:人均烟酒茶支出，

x4:人均其他副食支出，

x5:人均衣着商品支出，

x6:人均日用品支出，

x7:人均燃料支出，x8:人均非商品指出。1991年5省城镇居民月均消费(单位：元／人)

指标省份

x1

x2

x3

x4

x5

x6

x7

x8辽宁浙江河南甘肃青海

7.9039.778.4912.9419.2711.052.0413.297.6850.3711.3513.3019.2514.592.7514.879.4227.938.208.1416.179.421.559.769.1627.989.019.3215.999.101.8211.3510.0628.6410.5210.0516.188.391.9610.81解:

以1,2,3,4,5分别表示辽宁、浙江、河南、甘肃、青海5个省(样品),计算每两个样品之间的欧氏距离。如从而得初始距离矩阵如下：将5个省各看成一类，即Gi={i},i=1,2,3,4,5。有Dij=dij从D(0)看出，d43=2.20最小，故将G3,G4合并成一个新类G6={3，4}。计算G6与G1,G2,G5之间的距离得

{1}{2}{3}{4}{5}{1}{2}{3}{4}{5}D61=min{d31,d41}={13.80,13.12}=13.12D62=min{d32,d42}={24.63,24.06}=24.06D65=min{d35,d45}={3.51,2.21}=2.21(为简单记Ds(p,q)为Dpq)从而得D(1)G6={3,4}{1}{2}{5}{3,4}=G6{1}{2}{5}D61=min{d31,d41}={13.80,13.12}=13.12D62=min{d32,d42}={24.63,24.06}=24.06D65=min{d35,d45}={3.51,2.21}=2.21从D(1)看出，G6到G5的距离2.21为最小，故将G6,G5合并成一个新类G7={G6，G5}。计算G7与G1,G2之间的距离得G6={3,4}{1}{2}{5}{3,4}=G6{1}{2}{5}D71=min{d61,d51}={13.12,12.80}=12.80D72=min{d62,d52}={24.06,23.54}=23.54从D(1)看出，G6到G5的距离2.21为最小，故将G6,G5合并成一个新类G7={G6，G5}。计算G7与G1,G2之间的距离得从而得D(2)G7={3,4,5}{1}{2}{3,4,5}=G7{1}{2}D71=min{d61,d51}={13.12,12.80}=12.80D72=min{d62,d52}={24.06,23.54}=23.54从D(2)看出，G1到G2的距离11.67为最小，故将G1,G2合并成一个新类G8={G1，G2}={1,2}。计算G8与G7之间的距离得从而得D(2)D87=min{d17,d27}={12.80,23.54}=12.80G7={3,4,5}{1,2}=G8{3,4,5}=G7{1,2}=G8最后将G7,G8合并成一类G9={G7,G8}={1,2,3,4,5}。按照上述聚类过程，画聚类图。从而得D(3)D87=min{d17,d27}={12.80,23.54}=12.80(1)G6={G3,G4}，距离=2.20；(2)G7={G6,G5}，距离=2.21；(3)G8={G1,G2}，距离=11.67;(4)G9={G7,G8}，距离=12.80。(1)G6={G3,G4}，距离=2.20；(2)G7={G6,G5}，距离=2.21；(3)G8={G1,G2}，距离=11.67;(4)G9={G7,G8}，距离=12.80。1辽宁2浙江3河南4甘肃5青海02468101214距离同理，可用最长距离法进行聚类，可作为练习。系统聚类可用SAS过程cluster来实现。上例的SAS程序如下：dataex4_1;inputprovince$x1-x8;cards;辽宁7.9039.778.4912.9419.2711.052.0413.29浙江7.6850.3711.3513.3019.2514.592.7514.87河南9.4227.938.208.1416.179.421.559.76甘肃9.1627.989.019.3215.999.101.8211.35青海10.0628.6410.5210.0516.188.391.9610.81;procclustermethod=sinnonormouttree=ex4_1t;varx1-x8;idprovince;proctreedata=ex4_1thorizontal;idprovince;run;过程步说明：procclustermethod=sinnonormouttree=ex4_1t;varx1-x8;idprovince;proctreedata=ex4_1thorizontal;idprovince;run;method=聚类方法；ave—

类平均法；cen—

重心法;com—最长距离法;sin—最短距离法;war—

Ward法。nonorm—数据不变换；std—对数据标准化变换。outtree=数据集名，画聚类图时使用。id样品变量名。tree画聚类图过程；horizontal画水平聚类图，缺省为垂直聚类图。输出结果：（1）聚类过程（2）聚类图(sin最短距离法)（2）聚类图(com最长距离法)（2）聚类图(ave类平均法)（2）聚类图(cen重心法)（2）聚类图(ward离差平方和法)聚类方法不同，聚类结果也不尽相同。二、系统聚类法的统计量聚类分析中，分多少类合适，是我们关心的问题。一个较好的聚类应该是类内各样品尽可能相似，类间差异较大。下面介绍几种有助于分类的统计量。Sk越小，说明Gk中各样品越相似。记设在某水平上分为G个类，类Gk中样品的类内离差平方和为1.R2统计量类内离差平方和为1.R2统计量总离差平方和为则R2统计量为R2=1-PG/T显然0R21则R2统计量为R2=1-PG/T显然0R21当n个样品各自为一类时，R2=1；当n个样品合并成一类时，R2=0。

R2的值随分类个数的减少而减小，当R2由平缓减小到“突变”减小时的G，G即为分类个数的参考值。设类Gp，Gq的离差平方和分别为2.半偏相关统计量设类Gp，Gq的离差平方和分别为2.半偏相关统计量将Gp，Gq合并成Gr后的离差平方和为合并后离差平方和的增加量为Wpq=Sr-Sp-Sq由类Gp,Gq合并成Gr时半偏相关统计量SPRSQ为SPRSQ=Wpq/T当SPRSQ值越大时，说明上一次合并效果越好。伪F统计量PSF是3.伪F统计量PSF值越大，表示这些样品可显著地分为G类。伪t2

统计量PST2是PST2值越大，表示上一次聚类效果越好。4.伪t2统计量例4.2

山东省2000年17地市农村居民和城镇居民消费水平如下表，试对17个地市进行分类。表42000年17地市居民消费水平(绝对额，单位：元）资料来源：《山东省统计年鉴》，2001序号地农村居城镇居区民(x1)民(x2)序号地农村居城镇居区民(x1)民(x2)123456789济南市22988182青岛市26417983淄博市25855333枣庄市26085172东营市20858171烟台市32297173潍坊市23256590济宁市19064906泰安市209465641011121314151617威海市29527734日照市21655258莱芜市21125629临沂市16894593德州市11574218聊城市12974371滨州市22685267菏泽市12573310dataex4_2;inputgroup$x1-x2;cards;济南市22988182青岛市26417983…………菏泽市12573310;procclustermethod=avestdrsqpseudoouttree=ex4_2t;varx1-x2;idgroup;run;proctreedata=ex4_2thorizontal;idgroup;run;rsq—R2统计量和半偏相关统计量SPRSQ；pseudo—伪F统计量和伪t2统计量。解SAS程序如下：输出结果：类平均法聚类统计量从R2(RSQ)看，从2类至1类下降最大(0.578~0.000),又G=1时，SPRSQ达最大，说明分2类合适。类平均法聚类图§4.4

快速聚类法系统聚类法的缺点是计算量大。所以产生了快速聚类法，也称动态聚类法。目前在数据挖掘中应用较为广泛。快速聚类法先将样品粗略地分一下类，然后按照某种原则进行调整，直至分类比较合理为止。动态聚类框图如下：选择聚点初始分类分类是否合理最终分类修改分类合理不合理动态聚类法要先给定分类数k，选择k个聚点(种子)，即有代表性的样品。选择聚点(初始聚点)的方法有：

(1)经验选择。(2)将n个样品随机分为k类，每类的重心作为聚点。

(3)最小最大原则。（略）

SAS系统的fastclus过程中，分类数k给定后，种子自动确定。然后按照一定的规则（略）进行聚类。例4.3

从12个不同地区测得了某树种的平均发芽率x1与发芽势x2，数据见下表，距离采用欧氏距离，将12个地区用快速聚类法聚为2类。例4.3

从12个不同地区测得了某树种的平均发芽率x1与发芽势x2，数据见下表，距离采用欧氏距离，将12个地区用快速聚类法聚为2类。地区

x1

x2