04聚类分析.docx

聚类分析专题§ 6.1 言俗话说，“物以类聚，人以群分“，在自然科学和社会科学等各领域中，存在着大量的分类问题。分类学是人类相识世界的基础科学，在古老的分类学中，人们主要靠阅历和专业学问进行定性的分类，很少利用数学工具进行定量的分类。随着人类科学技术的发展，对分类的要求越来越高，以致有时仅凭阅历和专业学问难以准确地进行分类，于是人们渐渐地把数学工具引用到了分类学中，这便形成了数值分类学这一学科，之后又将多元分析的技术引入到数值分类学，便又从数值分类学中分别出一个重要分支一聚类分析。与多元分析的其它分析方法相比，聚类分析方法较为粗糙，理论上还不够完善，正处于发展阶段。但是，由于该方法应用便利，分类效果较好，因此越来越为人们所重视。这些年来聚类分析的方法发展较快，内容越来越丰富。判别分析与聚类分析都是探讨事物分类的基本方法，它们有着不同的分类目的，彼此之间既有区分又有联系。各种判别分析方法都要求对类有事先的了解，通常是每一类都有一个样本，据此得出判别函数和规则，进而可对其它新的样品属于哪一类作出推断。对类的事先了解和确定经常可以通过聚类分析得到。聚类分析的目的是把分类对象按肯定规则分成若干类，这些类不是事先给定的，而是依据数据的特征确定的。在同一类里的这些对象在某种意义上倾向于彼此相像，而在不同类里的对象倾向于不相像。聚类分析能够用来概括数据而不只是为了找寻“自然的”或“实在的”分类。例如，在选拔少年运动员时，对少年的身体形态、身体素养、生理功能的各种指标进行测试，据此对少年进行分类，分在同一类里的少年这些指标较为相近。类确定好之后，可以依据各类的样本数据得出选材的判别规则，作为选材的依据。又如，依据啤酒中含有的酒精成分、纳成分、所含的热量“卡路里”数值，可以对啤酒进行分类。聚类分析依据分类对象不同分为Q型聚类分析和R型聚类分析。Q型聚类分析是指对样品进行聚类，R型聚类分析是指对变量进行聚类。本章我们主要探讨。型聚类。§ 6.2 离和相像系数在对样品(或变量)进行分类时，样品(或变量)之间的相像性是如何度量的呢？这一节中，我们介绍两个相像性度量一距离和相像系数,前者常用来度量样品之间的相像性。后者常用来度量变量之间的相像性。样品之间的距离和相像系数有着各种不同的定义，而这些定义与变量的类型有着特别亲密的关系。通常变量按测量尺度的不同可以分为以下三类:(1)间隔尺度变量：变量用连续的量来表示，如长度、重量、速度、温度等。(2)有序尺度变量：变量度量时不用明确的数量表示，而是用等级来表示，如某产品分为一等品、二等品、三等品等有次序关系。(3)名义尺度变量：变量用一些类表示，这些类之间既无等级关系也多数量关系，如性别、职业、产品的型号等。我们这里主要探讨具有间隔尺度变量的样品聚类分析方法。一、距离设为为第i个样品的第j个指标，数据矩阵列于表6.1。每个样品有P个变量，故每个样品都可以看成是RP中的一个点，个样品就是R'中的个点。在瞪中需定义某种距离,第i个样品与第/个样品之间的距离记为d"在聚类过程中，距离较近的点倾向于归为一类,距离较远的点应归属不同的类。所定义的距离d厂般应满足如下四个条件：(I)四0,对一切(IDdij=0,当且仅当第i个样品与第/个样品的各变量值相同；(III) dij=dji,对一切仃；(IV) dijdik+dkjf对一切i,/,女。表6.1数据矩阵7量样限X2XP1孙22%2X2lX22n1乙2XnP常用的距离有如下几种：1 .明考夫斯基(MinkOWSki)距离第j个样品与第/个样品间的明考夫斯基距离定义为q°1.hI.这里g为某一自然数，这是一个最常用最直观的距离。当g=l时，4,(l)=fk法一,，称为肯定值距离；A=IZ(Xa-xjk),称为欧氏距离;=l当4=2时，6/.(2)=WJ_*=1当4=00时，dij()=rr11xxrt-xjk|,称为切比雪夫距离。当各变量的单位不同或虽单位相同但各变量的测量值相差很大时，不应干脆采纳明考夫斯基距离，而应先对各变量的数据作标准化处理，然后用标准化后的数据计算距离。最常用的标准化处理是，令,Xji-XjXij=1.，i=1,2,",=l,2,p其中，焉汽局为第j个变量的样本均值，S=1.之(X-焉产为第/个变量的I-1片样本方差。2 .马氏(MahaIanObiS)距离第，个样品与第/个样品间的马氏距离为dj(M)=(xi-xj)fS'Qi-Xj)其中Xj=(X“,项2,，x,p)'，S为样本协方差矩阵。运用马氏距离的好处是考虑到了各变量之间的相关性，并且与各变量的单位无关。不足之处是对马氏距离公式中的S,若始终不变，则往往显得不妥；若要随聚类过程而不断改变，则会有很多不便。3 .兰氏(1.anCe和WilIiamS)距离当%>0,»=1,2,，J=I,2,时，则可以定义第i个样品与第/个样品间的兰氏距离为%(1.)=£这个距离与各变量单位无关，但没有考虑变量间的相关性。由于它对大的异样值不敏感，故适用于高度偏斜的数据。4 .斜交空间距离由于样品的各个变量之间往往存在不同程度的相关关系，因此有时采纳欧氏距离显得不够志向，有人建议采纳斜交空间距离。第i个样品与第J个样品间的斜交空间距离定义为11 PP2Pk=Z=I4=r-)(-X/其中力是变量S与变量/间的相关系数。当P个变量互不相关时，dj=1.*Q),即斜交空间距离退化为欧氏距离(除相差一个常数倍外)。以上几种距离的定义均要求变量是间隔尺度的，假如运用的变量是有序尺度或名义尺度的，则有相应的一些定义距离的方法。下例是对名义尺度变量的一种距离定义。例设有五个变量均为名义尺度变量，再取值V和1,七取值M和Q,与取值S和A,5取值3、T和尸，Z取值。和K。现有两个样品王二(KQS,y,x2=(y,M,s,F,y这两个样品的第一个变量都取值V,称为协作的，其次个变量一个取Q,一个取称为不协作的。记协作的变量数为mI，不协作的变量数为加2,定义它们之间的距离为wl+tn12因此M与£之间的距离为二、相像系数聚类分析方法不仅用来对样品进行分类，而且可以用来对变量进行分类，在对变量进行分类时，经常采纳相像系数来度量变量之间的相像性。变量之间的关系越是亲密，其相像系数越接近于1(或-1)；反之，它们的关系越是疏远，其相像系数越是接近于0。聚类时,比较相像的变量倾向于归为一类，不怎么相像的变量归属不同的类。变量七与与的相像系数用】来表示，它一般应满足以下三个条件：(I)Cij=±1,当且仅当芍=QXj+6,(0)和人为常数;(IDCj1.对一切i,j；(HI)Cij=Cjif对一切最常用的相像系数有如下两种：1 .夹角余弦变量Xi与Xj的夹角余弦定义为它是R"中变量Xi的观测向量xi=(xh-,x2,xw),与变量Xj的观测向量Xj=(Xlj,冗2/，4)'之间夹角氏的余弦函数，即g=CoS%。2 .相关系数变量巧与巧的相关系数定义为相关系数我们曾用为来表示，这里表示为G(2)是为了与其它相像系数的符号一样。假如变量Xj与巧是已标准化了的，则它们间的夹角余弦就是原变量的相关系数。变量之间常借助于相像系数来定义距离，如令或=Y()样品之间有时也用相像系数来度量样品间的相像性程度。一般来说，同一批数据采纳不同的相像性度量，会得到不同的分类结果。在进行聚类分析的过程中，应依据实际状况选取好合适的相像性度量。如在经济变量分析中，常采纳相关系数来描述变量间的相像性程度。一般状况下，相关系数比其它的相像系数有更强的可变性，但辨别力要弱一些。§6.3系统聚类法系统聚类法是聚类分析诸方法中用得最多的一种，其基本思想是：起先将个样品各自作为一类，并规定样品之间的距离和类与类之间的距离，然后将距离最近的两类合并成一个新类，计算断卷与其它类的距离(注：未合并的类之间的距离不用重新计算)；重复进行两个最近类的合并，每次削减一类，直至全部的样品合并为一类。本节介绍常用的八种系统聚类方法，全部这些聚类方法的区分在于类与类之间距离的计算方法不同。以下我们用B.表示第i个样品与第j个样品的距离，G，G?,表示类，DK1.表示GK与G1.的距离。本节介绍的系统聚类法中，除离差平方和法之外，其余全部的方法因一起先每个样品自成一类，类与类之间的距高与样品之间的距离相同，即。也=4"，所以起初的距离矩阵全部相同，记为O(O)=(%)。一、最短距离法定义类与类之间的距离为两类最近的样品间的距离，即DKl=min(dii)()称这种系统聚类法为最短距离法。用最短距离法的聚类步骤如下：(1)规定样品之间的距离，计算个样品的距离矩阵。，它是一个对称矩阵。(2)选择中的最小元素，设为。代，则将GK与G1.合并成一个新类，记为G廿，即GM=G,Gjo(3)计算新类与任一类GJ之间的距离为DMJ=益盘GW)一mh/K)总%卜min%,为O将O(O)中的PM行，p,q列用O式并成一个新行新列，新行新列对应GM,所得矩阵记为。（4）对。重复上述对。（°）的两步得。，如此下去直至全部元素合并成一类为止。假如某一步O（M中最小的元素不止一个，则对应这些最小元素的类可以同时合并。例设有五个样品，每个只测量了一个指标，分别为1,2,6,8,H,试用最短距离法将它们分类。（1）样品间采纳肯定值距离（这时它与其它的明考夫斯基距离完全相同），计算样品间的距离矩阵列于表6.2。表6.3。G,G3G4GGfi040Gq620q9530（3）。中最小的元素是。弘=2,于是将G3和G4合并成G,，并利用（）式计算G7与其它类的距离，列于表6.4。与其它类的距离，列于表6.5。表6.5。n1.J(5)最终将Ge和Gg合并为Gg,这时全部五个样品聚为一类，过程终止。上述聚类过程可以画成一张图，如图6.1所示。横坐标的刻度是并类的距离，从图上看，分两类较为合适。这只是从直观上确定了类的个数为2,关于确定类的个数问题我们将在稍后进行探讨。图6.1二、最长距离法类与类之间的距离定义为两类最远样品间的距离，即DK1.maxdii)iwG,jeG-"称这种系统聚类法为最长距离法。最长距离法与最短距离法的并类步骤完全相同，只是类间距离的递推公式有所不同。设某步将类GK与G7,合并成一个新类GM,则GM与任一类GJ的距离为Dmj=.max)=maxmaxUJmax=max%,DuOigGm,jeGjIYGKjeGJIWG1.,jwGjJ对例采纳最长距离法，。与前面相同，将G和G2合并成G6,计算Z>6J(J=3,4,5)的公式为D6j=maxDuyD2j,J=3,4,5。的计算结果列于表6.6。表6.6。G,GAQGsO5O72OGIO53O。中的最小元素是。34=2,合并G3和G4成G,计算（/=5,6）的公式为Dij=maxD3j,D47,J=5,6。的计算结果列于表6.7。表6.7D(2)G6GSG6OG770G,105O。中的最小元素为。57=5,将G5和G,合并成Gg,见表6.8。计算。86的公式为D86=maxD56,D76=10最终将Ge和Gg并为G9。其聚类图如图6.2所示，它与图6.1有相像的形态，但并类的距离要比图6.1大一些，仍分为两类为宜。图6.2最长距离法可能被异样值严峻地扭曲，这是值得我们在应用中留意的问题。一个有效的方法是删去这些异样值之后再进行聚类。三、中间距离法类与类之间的距离既不取两类最近样品间的距离，也不取两类最远样品间的距离，而是取介于两者中间的距离，称之为中间距离法。设某一步将GK和G1.合并为Gg,对于任一类Gj,考虑由。山、OU和为边组成的三角形（如图6.3所示），取QKA边的中线作为OM由初等平面几何可知，OMJ的计算公式为%=；1+翱_淮（）这就是中间距离法的递推公式。中间距离法可推广为更一般的情形，将O式三项的系数依靠于某个参数£,即DiJ=Y（D%+讣0席（）GK图6.3这里vl,这种方法称为可变法。四、类平均法类与类之间的平方距离定义为样品对之间平方距离的平均数，即2K1.其中K和勺分别为类GK和G1.的样品个数，称这种系统聚类法为类平均法。简单得到它的一个递推公式为%=-1.-4ftMftJ注GMJWGJ=fq+gnMnJUeGKJeGj汨GSjWGJ）备注：因为。乙=一EG，所以Z力=心%。2，同理4=n1.njDhnKnJMKJwGJNGkJgGj备注完毕。由上所述，有GnMnJGmJeGt-l-g+g'(6.3.8)nMnJieGJeGjiwGt,jwGj)-(nnjDij+nlnjDjj)nMnJ,2U类平均法较好地利用了全部样品之间的信息,在很多状况下它被认为是一种比较好的系统聚类法。在递推公式（）式中，。机的影响没有被反映出来，为此可将该递推公式进一步推广(6.3.9)其中尸1,称这种系统聚类法为可变类平均法。对例采纳类平均法进行聚类。假如我们起先就将。的每个元素都平方，则运用递推公式会便利很多°（1）计算，），见表6.9,它是将表6.2的各数平方。表6.9%GlG?G,GGl0G?1025160Ga493640G5100812590找Zn中的最小元素，它是Z=l,将Gl和G2合并为G6,计算G6与GJ（J=3,4,5）的距离。这时珥=2=1，%=2，由O式计算得%=押+/z=205同样可算得。；和。;6,列于表6.10。表6.10DXGsG3G4Gg0G,20.5042.540Gs90.52590（3）对。;）重复上述步骤，将G3和Git并为G7,得平方距离矩阵Z（见表6.11）。表6.11%Gs3GsGs0G,31.50Gs90.5170将G5和G?合并成Gg得Z（见表6.12）,最终将Gg和G6合并成聚类过程终止。其聚类图如图6.4所示（此处省略）。表6.12%GsQGg051.170五、重心法类与类之间的距离定义为它们的重心（均值）之间的欧氏距离。设GK和G1.的重心分别为IK和则GK和GA之间的平方距离为Dj1.l=（XK-Xl）,（XK-Xl.）（）这种系统聚类法称为重心法。重心法在处理异样值方面比其它系统聚类法更稳健，但是在别的方面一般不如类平均法或离差平方和法效果好。六、离差平方和法类GqG1.和合并成的新类GM的（类内）离差平方和分别是WK=Z（七-XK）'（巧-XK）MGk%=U,-X1.）xi-X1.）WM=Z（X-XM）'（七-XM）-Gm它们反映了各自类内样品的分散程度。假如GK和G1.这两类相距较近，则合并后所增加的离差平方和叱w-唯一应较小；否则应较大。于是我们定义GK和G1.之间的平方距离为DIl=Wxl-W-WbO这种系统聚类法称为离差平方和法或Ward法。可以验证，这个距离定义满足通常定义距离所需满足的四个条件。我们现在导出D2kl的另一简化表达式。YlYlD1kl=1.K（XK-X1.y（XK-Xl）（）nM可见，这个距离与由O式给出的重心法的距离只相差一个常数倍。重心法的类间距离与两类的样品数无关，而离差平方和法的类间距离与两类的样品数有较大关系，两个大的类倾向于有较大的距离，因而不易合并，这往往符合我们对聚类的实际要求。离差平方和法在很多场合下优于重心法，是比较好的一种系统聚类法，但它对异样值很敏感。七、系统聚类法的统一以上我们介绍了常用的八种系统聚类法，全部这些方法的并类原则或过程是完全相同的，不同之处在于类与类之间的距离有不同的定义，因而有不同的距离递推公式.假如能把它们统一成一个公式，则将大大有利于计算机程序的编制。1.anCe和WiIIiamS于1967年将这些递推公式统一了起来，统一的公式为：dIjkdIj+4。：+。席+其此一困（6315）其中。长、入、4和y是参数，不同的系统聚类法，它们有不同的取值。对例几种方法的聚类结果都相同，但一般而言，不同方法的聚类结果是不完全一样的。各种方法都有其适用的场合，选用哪种方法需视实际状况和对聚类结果的要求而定。为了能取得较好的系统聚类，必需对聚类的一些性质有较清晰的相识。下面我们介绍系统聚类法的两特性质。1 .单调性令B是系统聚类法中第i次并类时的距离，如例中，用最短距离法时，有D=1,D2=2,D3=3,D4=4,且有D<D2<D3<D4,假如一种系统聚类法能满足D1D2D3D4,则称它具有单调性。这种单调性符合系统聚类法的思想，先合并较相像的类，后合并较疏远的类。可以证明，最短距离法、最长距离法、可变法、类平均法、可变类平均法和离差平方和法都具有单调性，但中间距离法和重心法不具有单调性。2 .空间的浓缩和扩张比较图6.1和图6.2可以看到，对同一问题采纳不同的系统聚类法作聚类图时，横坐标的范围可以相差很大，最短距离法的范围4,最长距离法的范围100设4=（%）和8=（%）是两个元素非负的同阶矩阵，若为%（对一切i,j）,则记作A30这个记号仅在本节中运用，请勿与通常涉及非负定矩阵的记号A8相混淆。设有两种系统聚类法，它们在第i步的距离矩阵分别为A和i=（）,l,2,-1,若48,=1,2.,11-1,则称第一种方法比其次种方法使空间扩张，或其次种方法比第一种方法使空间浓缩。我们以类平均法为基准，其它方法都与它作比较，可以证明有如下一些结论：（1） D（短）WO（平），。（重）WQ（平），即最短距离法和重心法比类平均法使空间浓缩。（2）。（长）2。（平），即最长距离法比类平均法使空间扩张。（3）当Ov/Vl时，D（变平）WD（平），即这时可变类平均法比类平均法使空间浓缩；当尸<0时，D（变平）2。（平），即此时可变类平均法比类平均法使空间扩张;当£=0时，可变类平均法退化为类平均法，即。（变平）=D（平）。以上比较的这些方法中，太浓缩的方法不够灵敏，太扩张的方法灵敏度可能过高而简单失真。类平均法比较适中，它既不太浓缩也不太扩张，因此它被认为是一种比较志向的方法。八、类的个数在聚类过程中类的个数如何来确定才是相宜的呢？这是一个特别困难的问题，人们至今仍未找到令人满足的方法，但这又是一个不行回避的问题。下面我们介绍确定类个数的几种常用方法。1 .给定一个阈值T通过观测聚类图，给出一个你认为合适的阈值T,要求类与类之间的距离要大于T,有些样品可能会因此而归不了类。这种方法有较强的主观性，这是它的不足之处。如图6.1中，取T=3.3,即在距离为3.3处切一刀，5个样品分为1,2和6,8,11两个类。2 .观测样品的散点图假如样品只有两个或三个变量，则可通过观测数据的散点图来确定类的个数。对于三个变量，可运用SAS软件通过旋转三维坐标轴来观测散点图。3 .K?统计量设总样品数为，聚类时把全部样品合并成加个类G,G2,G,”，类Gj的样品数和_m_1叫_重心分别是q和Xi,i=l,2,m，则X%=，全部样品的总重心x=。令国/=1W=SQj；)化；)()y=为全部样品的总离差平方和，叱="J1.")°为类Gj中样品的类内离差平方和，e,=叱()=l为m个类的类内离差平方和之和。W可作如下分解W=SkjT(XjT7=1=(xj-)(xJ=lJeGf=EZ(XM+即-X)区-工+为-/)f=lJeGi'm_,_,=Z(S3)H3)+"H-X)Wr)+2Zkj-即)I=I|_G,jeGi易知，交叉项同-可GT=IN4,j仅TG1.jWGJ=o.p-x)=0所以W=E(xj-Xi)(xy-Xi)+ni(x-x)(xf-x)=lIJea_=1.-X)(y-<)÷11,(-HG1.)ijwGjZ=Il因为WW所以PM'TST1一一叱二旦WW再令R2越大，（即C1.值越小），表明类内离差平方和之和在总离差平方和中所占的比例小，也W就说明加个类分得越开。因此，R2统计量可用于评价合并成次个类时的聚类效果，R2值越大，聚类效果越好。内的取值范围在O与1之间，聚类刚起先时，个样品各自为一类，这时R2=1;当个样品最终合并成一类时R2=0。由于R2的值总是随着分类个数的削减而变小，因此只是孤立地看每次并类后的心值是无多大意义的。假如我们希望通过分析R2值来确定个样品应分为几类最合适，应当看K?值如何随类的个数用削减而改变。比如，假定分为4类之前的并类过程中R2的削减是缓慢的、改变不大的；分为4类时，R2=0.80;而下一次合并后分为3类时R2下降很多，=0.32O这时我们可以认为分为4类是最合适的。4 .伪产统计量伪F=mlOn-m该统计量用于评价分为用个类的聚类效果。伪F值越大，表明个样品越可显著地分为加个类。伪F统计量可以作为确定类个数的有用指标，但不具有像随机变量产那样的分布。5 .伪统计量伪2=½O唯十%n+nb-2其中。力=Ww-Wk-Wl,表示合并类GK和G1.为新类GM后类内离差平方和的增量。伪t2统计量用于评价合并类GK和G/.的效果。伪t2值较大表示Gk和G1.合并成GM后，类内离差平方和的增量D%相对于原GK和G1.两类的类内离差平方和的和较大。这说明被合并的两个类GK和G1,是很分开的，也即上一次聚类的效果是好的。伪产统计量是确定类个数的有用指标，但不具有像随机变量那样的分布。6 .半偏心统计量n2半偏r2=4l（）W该统计量用于评价合并类GK和GA的效果。半偏R2值是上一步R2值与该步R2值之差，因此半偏内值越大，则上一次聚类的效果就越好。