六章聚类分析课件.ppt

1、六章聚类分析6.1 引言v聚类分析：将分类对象分成若干类，相似的归为同一类，不相似的归为不同的类。v聚类分析和判别归类有着不同的分类目的，彼此之间既有区别又有联系。v聚类分析分为Q型（分类对象为样品）和R型（分类对象为变量）两种。2v对于间隔变量，距离常用来度量样品之间的相似性，相似系数常用来度量变量之间的相似性。v本章主要讨论具有间隔尺度变量的样品聚类分析方法。v一、距离v二、相似系数5一、距离v设x=(x1,x2,xp)和y=(y1,y2,yp)为两个样品，则所定义的距离一般应满足如下三个条件：(i)非负性：d(x,y)0，d(x,y)=0当且仅当x=y；(ii)对称性：d(x,y)=d(

2、y,x)；(iii)三角不等式：d(x,y)d(x,z)+d(z,y)。6常用的距离v1.明考夫斯基（Minkowski）距离v2.兰氏（Lance和Williams）距离v3.马氏距离v4.斜交空间距离71.明考夫斯基距离v明考夫斯基距离（简称明氏距离）：这里q0。v明氏距离的三种特殊形式：v(i)当q=1时，称为绝对值距离，常被形象地称作“城市街区”距离；v(ii)当q=2时，这是欧氏距离，它是聚类分析中最常用的一个距离；v(iii)当q=时，称为切比雪夫距离。11,qpqiiidxyx y1,piiidxyx y 1 221,piiidxyx yxyxy1,maxiii pdxy x y

3、8绝对值距离图示9对各变量的数据作标准化处理v当各变量的单位不同或测量值范围相差很大时，应先对各变量的数据作标准化处理。最常用的标准化处理是，令 其中 和sii分别为xi的样本均值和样本方差。*,1,2,iiiiixxxipsix102.兰氏距离v当所有的数据皆为正时，可以定义x与y之间的兰氏距离为v该距离与各变量的单位无关，且适用于高度偏斜或含异常值的数据。1,piiiiixydxyx y113.马氏距离vx和y之间的马氏距离为其中S为样本协差阵。1,dx yxySxy124.斜交空间距离vx和y之间的斜交空间距离定义为 其中rij是第i个变量与第j个变量间的相关系数。v当p个变量互不相关时

4、，该距离即为欧氏距离的1/p倍。1 22111,ppiijjijijdxyxyrpx y13名义尺度变量的一种距离定义v例6.2.1 某高校举办一个培训班，从学员的资料中得到这样六个变量：性别(x1)，取值为男和女；外语语种(x2)，取值为英、日和俄；专业(x3)，取值为统计、会计和金融；职业(x4)，取值为教师和非教师；居住处(x5)，取值为校内和校外；学历(x6)，取值为本科和本科以下。现有两名学员：x=(男，英，统计，非教师，校外，本科)y=(女，英，金融，教师，校外，本科以下)一般地，若记配合的变量数为m1，不配合的变量数为m2，则它们之间的距离可定义为故按此定义，本例中x 与y 之间

5、的距离为2/3。21212mdmm14二、相似系数v变量之间的相似性度量，在一些应用中要看相似系数的大小，而在另一些应用中要看相似系数绝对值的大小。v相似系数（或其绝对值）越大，认为变量之间的相似性程度就越高；反之，则越低。v聚类时，比较相似的变量倾向于归为一类，不太相似的变量归属不同的类。15相似系数一般需满足的条件v(1)cij=1，当且仅当xi=axj+b，a(0)和b是常数；(2)|cij|1，对一切i,j；(3)cij=cji，对一切i,j。16两个向量的夹角余弦 cosx yxy171.夹角余弦v变量xi与xj的夹角余弦定义为它是Rn中变量xi的观测向量(x1i,x2i,xni)与

6、变量xj的观测向量(x1j,x2j,xnj)之间夹角ij的余弦函数，即cij(1)=cosij。11 222111nkikjkijnnkikjkkx xcxx182.相关系数v变量xi与xj的相关系数为v如果变量xi与xj是已标准化了的，则它们间的夹角余弦就是相关系数。11 222112nkiikjjkijnnkiikjjkkxxxxcxxxx19v相似系数除常用来度量变量之间的相似性外有时也用来度量样品之间的相似性，同样，距离有时也用来度量变量之间的相似性。v由距离来构造相似系数总是可能的，如令 这里dij为第i个样品与第j个样品的距离，显然cij满足定义相似系数的三个条件，故可作为相似系数

7、。v距离必须满足定义距离的三个条件，所以不是总能由相似系数构造。高尔（Gower）证明，当相似系数矩阵(cij)为非负定时，如令 则dij满足距离定义的三个条件。11ijijcd2 1ijijdc206.3 系统聚类法v系统聚类法（或层次聚类法，hierarchical clustering method）是通过一系列相继的合并或相继的分割来进行的，分为聚集的（agglomerative）和分割的（divisive）两种，适用于样品数目n不是很大的情形。v聚集系统法的基本思想是：开始时将n个样品各自作为一类，并规定样品之间的距离和类与类之间的距离，然后将距离最近的两类合并成一个新类，计算新类与

8、其他类的距离；重复进行两个最近类的合并，每次减少一类，直至所有的样品合并为一类。21一开始每个样品各自作为一类22v分割系统法的聚类步骤与聚集系统法正相反。由n个样品组成一类开始，按某种最优准则将它分割成两个尽可能远离的子类，再用同样准则将每一子类进一步地分割成两类，从中选一个分割最优的子类，这样类数将由两类增加到三类。如此下去，直至所有n个样品各自为一类或采用某种停止规则。v聚集系统法最为常用，本节集中介绍其中常用的八种方法，所有这些聚类方法的区别在于类与类之间距离的定义不同。236.3 系统聚类法v一、最短距离法 v二、最长距离法v三、类平均法v四、重心法v*五、中间距离法v六、离差平方和

9、法（Ward方法）v七、系统聚类法的统一v八、类的个数24一、最短距离法v定义类与类之间的距离为两类最近样品间的距离，即,minKLKLiji Gj GDd图6.3.1 最短距离法：DKL=d2325最短距离法的聚类步骤v(1)规定样品之间的距离，计算n个样品的距离矩阵D(0)，它是一个对称矩阵。v(2)选择D(0)中的最小元素，设为DKL，则将GK和GL合并成一个新类，记为GM，即GM=GKGL。v(3)计算新类GM与任一类GJ之间距离的递推公式为,minminmin,minmin,MJKJLJMJijijiji Gj Gi Gj Gi Gj GKJLJDdddDD26递推公式的图示理解27

10、最短距离法的聚类步骤 在D(0)中，GK和GL所在的行和列合并成一个新行新列，对应GM，该行列上的新距离值由上述递推公式求得，其余行列上的距离值不变，这样就得到新的距离矩阵，记作D(1)。v(4)对D(1)重复上述对D(0)的两步得D(2)，如此下去直至所有元素合并成一类为止。28v如果某一步D(m)中最小的元素不止一个，则称此现象为结（tie），对应这些最小元素的类可以任选一对合并或同时合并。最短距离法最容易产生结，且有一种挑选长链状聚类的倾向，称为链接（chaining）倾向。v由于最短距离法是用两类之间最近样本点的距离来聚的，因此该方法不适合对分离得很差的群体进行聚类。29v例6.3.1

11、 设有五个样品，每个只测量了一个指标，分别是1，2，6，8，11，试用最短距离法将它们分类。记G1=1，G2=2，G3=6，G4=8，G5=11，样品间采用绝对值距离。G1G2G3G4G5G10G210G3540G47620G5109530表6.3.1 D(0)30其中G6=G1G2其中G7=G3G4G6G3G4G5G60G340G4620G59530表6.3.2 D(1)表6.3.3 D(2)G6G7G5G60G740G593031其中G6=G1G2表6.3.4 D(3)G6G8G60G840图6.3.2 最短距离法树形图32二、最长距离法v类与类之间的距离定义为两类最远样品间的距离，即,m

12、axKLKLiji Gj GDd图6.3.3 最长距离法：DKL=d1533v最长距离法与最短距离法的并类步骤完全相同，只是类间距离的递推公式有所不同。v递推公式：max,MJKJLJDDD34v对例6.3.1采用最长距离法，其树形图如图6.3.4所示，它与图6.3.2有相似的形状，但并类的距离要比图6.3.2大一些，仍分成两类为宜。图6.3.4 最长距离法树形图35异常值的影响v最长距离法容易被异常值严重地扭曲。36v例6.3.2 对305名女中学生测量八个体型指标：x1：身高x5：体重x2：手臂长x6：颈围x3：上肢长x7：胸围x4：下肢长x8：胸宽表6.3.5各对变量之间的相关系数 x1

13、x2x3x4x5x6x7x8x11.000 x20.8461.000 x30.8050.8811.000 x40.8590.8260.8011.000 x50.4730.3760.3800.4361.000 x60.3980.3260.3190.3290.7621.000 x70.3010.2770.2370.3270.7300.5831.000 x80.3820.4150.3450.3650.6290.5770.5391.00037图6.3.5 八个体型变量的最长距离法树形图38三、类平均法v有两种定义。一种定义方法是把类与类之间的距离定义为所有样品对之间的平均距离，即定义GK和GL之间的距

14、离为,1KLKLiji Gj GKLDdn n图6.3.6 类平均法39v递推公式：,11MJKJLJMJijijiji Gj Gi Gj Gi Gj GMJMJKLKJLJMMDdddn nn nnnDDnn40v另一种定义方法是定义类与类之间的平方距离为样品对之间平方距离的平均值，即v它的递推公式为v类平均法较好地利用了所有样品之间的信息，在很多情况下它被认为是一种比较好的系统聚类法。22,1KLKLiji Gj GKLDdn n222KLMJKJLJMMnnDDDnn41v对例6.3.1采用（使用平方距离的）类平均法进行聚类。一开始将D(0)的每个元素都平方，并记作 。2(0)DG1G2

15、G3G4G5G10G210G325160G4493640G51008125902(0)D表6.3.642G6G3G4G5G60G320.50G442.540G590.52590表6.3.72(1)DG6G7G5G60G731.50G590.5170表6.3.82(2)D43G6G8G60G851.170G6G8G60G851.170表6.3.92(3)D图6.3.7 类平均法树形图44四、重心法v类与类之间的距离定义为它们的重心(均值)之间的欧氏距离。设GK和GL的重心分别为 ，则GK与GL之间的平方距离为KLxx和 22KLKLKLKLDdx xxxxx图6.3.8 重心法45v合并GK和G

16、L之后的新类GM的重心是 其中nM=nK+nL为GM的样品个数。v重心法的递推公式为v与其他系统聚类法相比，重心法在处理异常值方面更稳健，但是在别的方面一般不如类平均法或离差平方和法的效果好。22222KLKLMJKJLJKLMMMnnn nDDDDnnnKKLLMMnnnxxx46*五、中间距离法v设某一步将GK和GL合并为GM，对于任一类GJ，考虑由DKJ，DLJ和DKL为边长组成的三角形，取DKL边的中线作为DMJ。DMJ的计算公式为2222111222MJKJLJKLDDDD图6.3.9 中间距离法的几何表示47六、离差平方和法(Ward方法)v（类内）离差平方和：类中各样品到类重心（

17、均值）的平方欧氏距离之和。v设类GK和GL合并成新类GM，则GK,GL和GM的离差平方和分别是对固定的类内样品数，它们反映了各自类内样品的分散程度。KLMKiKiKi GLiLiLi GMiMiMi GWWWxxxxxxxxxxxx48类内离差平方和的几何解释v类内离差平方和WK是类GK内各点到类重心点 的直线距离之平方和。kx49v定义GK和GL之间的平方距离为v 也可表达为 v离差平方和法使得两个大的类倾向于有较大的距离，因而不易合并；相反，两个小的类却因倾向于有较小的距离而易于合并。这往往符合我们对聚类的实际要求。2KLMKLDWWW2KLD 2KLKLKLKLMn nDnxxxx1=1

18、12KLKLKLKKLMKLLKMn nn nn nnnnnnnnnn，当时，50图6.3.10 离差平方和法与重心法的聚类比较51v离差平方和法的平方距离递推公式为v对例6.3.1采用离差平方和法进行聚类。2222JKJLJMJKJLJKLJMJMJMnnnnnDDDDnnnnnn图6.3.11 离差平方和法树形图52v最短距离法、最长距离法和类平均法都属于连接方法，它们既可以用于样品的聚类，也能够用于变量的聚类。本章介绍的其他聚类方法都将只能用于样品的聚类。v例6.3.3 表6.3.10列出了1999年全国31个省、直辖市和自治区的城镇居民家庭平均每人全年消费性支出的八个主要变量数据。这八

19、个变量是 x1：食品x5：交通和通讯 x2：衣着x6：娱乐教育文化服务 x3：家庭设备用品及服务x7：居住x4：医疗保健x8：杂项商品和服务分别用最短距离法、重心法和Ward方法对各地区作聚类分析。为同等地对待每一变量，在作聚类前，先对各变量作标准化变换。53表6.3.10 消费性支出数据 单位：元地区x1x2x3x4x5x6x7x8北京2959.19730.79749.41513.34467.871141.82478.42457.64天津2459.77495.47697.33302.87284.19735.97570.84305.08河北1495.63515.9362.37285.32272

20、.95540.58364.91188.63山西1406.33477.77290.15208.57201.5414.72281.84212.1内蒙古1303.97524.29254.83192.17249.81463.09287.87192.96辽宁1730.84553.9246.91279.81239.18445.2330.24163.86吉林1561.86492.42200.49218.36220.69459.62360.48147.76黑龙江1410.11510.71211.88277.11224.65376.82317.61152.85上海3712.31550.74893.37346.9

21、35271034.98720.33462.03江苏2207.58449.37572.4211.92302.09585.23429.77252.54浙江2629.16557.32689.73435.69514.66795.87575.76323.36安徽1844.78430.29271.28126.33250.56513.18314151.39福建2709.46428.11334.12160.77405.14461.67535.13232.29江西1563.78303.65233.81107.9209.7393.99509.39160.12山东1675.75613.32550.71219.792

22、72.59599.43371.62211.8454河南1427.65431.79288.55208.14217337.76421.31165.32湖北1783.43511.88282.84201.01237.6617.74523.52182.52湖南1942.23512.27401.39206.06321.29697.22492.6226.45广东3055.17353.23564.56356.27811.88873.061082.82420.81广西2033.87300.82338.65157.78329.06621.74587.02218.27海南2057.86186.44202.72171

23、.79329.65477.17312.93279.19重庆2303.29589.99516.21236.55403.92730.05438.41225.8四川1974.28507.76344.79203.21240.24575.1430.36223.46贵州1673.82437.75461.61153.32254.66445.59346.11191.48云南2194.25537.01369.07249.54290.84561.91407.7330.95西藏2646.61839.7204.44209.11379.3371.04269.59389.33陕西1472.95390.89447.9525

24、9.51230.61490.9469.1191.34甘肃1525.57472.98328.9219.86206.65449.69249.66228.19青海1654.69437.77258.78303244.93479.53288.56236.51宁夏1375.46480.89273.84317.32251.08424.75228.73195.93新疆1608.82536.05432.46235.82250.28541.3344.85214.455图6.3.12 最短距离法56图6.3.13 重心法57图6.3.14 离差平方和法58从这三个树形图来看，只有Ward方法较好地符合了我们的实际聚

25、类要求，它将31个地区分为以下三类：第类：北京、浙江、上海和广东。这些都是我国经济最发达、城镇居民消费水平最高的沿海地区。第类：天津、江苏、云南、重庆、河北、新疆、山东、湖北、四川、湖南、福建、广西、海南和西藏。这些地区在我国基本上属于经济发展水平和城镇居民消费水平中等的地区。第类：山西、甘肃、内蒙古、辽宁、黑龙江、吉林、青海、宁夏、安徽、贵州、河南、陕西和江西。这些地区在我国基本上属于经济较落后地区，城镇居民的消费水平也是较低的。v如果分为五类，则广东和西藏将各自为一类。59图6.3.15 离差平方和法所分三类的平行图60七、系统聚类法的统一vLance和Williams于1967年将（书中

26、介绍的）八种系统聚类法的递推公式统一为：其中K,L,是参数，不同的系统聚类法，它们有不同的取值。表6.3.11列出了上述八种方法四个参数的取值。v1.单调性v2.空间的浓缩与扩张 222222MJKKJLLJKLKJLJDDDDDD61表6.3.11 系统聚类法参数表621.单调性v令Di是系统聚类法中第i次并类时的距离，如果一种系统聚类法能满足D1D2D3 ，则称它具有单调性。这种单调性符合系统聚类法的思想，先合并较相似的类，后合并较疏远的类。v最短距离法、最长距离法、可变法、类平均法、可变类平均法和离差平方和法都具有单调性，但中间距离法和重心法不具有单调性。632.空间的浓缩与扩张v设A=

27、(aij)和B=(bij)是两个元素非负的同阶矩阵，若aijbij(对一切i,j)，则记作AB。该记号仅在本节中使用。v设有两种系统聚类法，它们在第i步的距离矩阵分别为Ai和Bi，i=0,1,n1，若AiBi，i=1,n1，则称第一种方法比第二种方法使空间扩张，或第二种方法比第一种方法使空间浓缩。v以类平均法为基准，有如下一些结论：(1)D(短)D(平)，D(重)D(平)。(2)D(长)D(平)。(3)当01时,D(变平)D(平)；当0时,D(变平)D(平)。64例6.3.4（最短距离法的链接倾向）65v(1)采用最短距离法。可以算得，当聚成两类时，C1和C11组成一类，其余所有的点组成另一类

28、，这里出现了链接现象；当聚成三类时，C1和C11组成第类，其余的C点组成第类，所有的A点和B点组成第类。v(2)采用类平均法。经算得，当聚成两类时，一类由所有C点构成，另一类由所有A点和所有B点构成；当聚成三类时，A点群、B点群和C点群各自作为一类。66从直观的图形中进行主观聚类v当p=2时，可通过目测散点图从直觉上来判断所采用的正规聚类方法是否合理。我们甚至可以直接在散点图上进行主观的聚类，其效果未必逊于正规的聚类方法，特别是在寻找“自然的”类和符合我们实际需要的类方面。v当p=3时，我们可使用SAS软件的交互式数据分析菜单系统产生三维旋转图，通过旋转三维坐标轴从各个角度来观测散点图，以直观

29、评估所作聚类的效果如何，不过观测效果一般明显不如平面散点图清楚。v当p3时，有时我们可采用主成分分析（见第七章）或因子分析（见第八章）的技术将维数降至2或3维，然后再生成散点图或旋转图，从直觉上进行主观的聚类。67寻找“自然的”类68八、类的个数v如果能够分成若干个很分开的类，则类的个数就比较容易确定；反之，如果无论怎样分都很难分成明显分开的若干类，则类个数的确定就比较困难了。v确定类个数的常用方法有：1.给定一个阈值T。2.观测样品的散点图。3.使用统计量。691.给定一个阈值Tv通过观测树形图，给出一个你认为合适的阈值T，要求类与类之间的距离要大于T，有些样品可能会因此而归不了类或只能自成

30、一类。这种方法有较强的主观性，这是它的不足之处。702.观测样品的散点图v如果样品只有两个（或三个）变量，则可通过观测数据的散点图（或旋转图）来主观确定类的个数。v如果变量个数超过三个，则可对每一可能考虑的聚类结果，将所有样品的前两个（或三个）费希尔判别函数得分制作成散点图（或旋转图），目测类之间是否分离得较好。该图既能帮助我们评估聚类效果的好坏，也能帮助我们判断所定的类数目是否恰当。71图6.3.17 按图6.3.14分三类的两个判别函数得分的散点图72图6.3.18 按图6.3.14分五类的两个判别函数得分的散点图733.使用统计量v（1）R2统计量。v（2）半偏R2统计量。v（3）伪F统

31、计量。v（4）伪t统计量。746.4 动态聚类法v在系统聚类法中，对于那些先前已被“错误”分类的样品不再提供重新分类的机会，而动态聚类法（或称逐步聚类法）却允许样品从一个类移动到另一个类中。v动态聚类法的计算量要比建立在距离矩阵基础上的系统聚类法小得多。因此，使用动态聚类法计算机所能承受的样品数目n要远远超过使用系统聚类法所能承受的n。75v动态聚类法的基本思想是，选择一批凝聚点或给出一个初始的分类，让样品按某种原则向凝聚点凝聚，对凝聚点进行不断的修改或迭代，直至分类比较合理或迭代稳定为止。类的个数k需先指定一个。v选择初始凝聚点（或给出初始分类）的一种简单方法是采用随机抽选（或随机分割）样品

32、的方法，可以要求凝聚点之间至少应间隔某个距离值。v动态聚类法只能用于对样品的聚类，而不能用于对变量的聚类。v动态聚类法有许多种方法，在这一节中，我们将讨论一种比较流行的动态聚类法k均值法。它是由麦奎因（MacQueen，1967）提出并命名的一种算法。76k均值法的基本步骤v(1)选择k个样品作为初始凝聚点，或者将所有样品分成k个初始类，然后将这k个类的重心（均值）作为初始凝聚点。v(2)对除凝聚点之外的所有样品逐个归类，将每个样品归入凝聚点离它最近的那个类（通常采用欧氏距离），该类的凝聚点更新为这一类目前的均值，直至所有样品都归了类。v(3)重复步骤(2)，直至所有的样品都不能再分配为止。7

33、7v最终的聚类结果在一定程度上依赖于初始凝聚点或初始分类的选择。经验表明，聚类过程中的绝大多数重要变化均发生在第一次再分配中。v例6.4.1 对例6.3.1采用k均值法聚类，指定k=2，具体步骤如下：(1)随意将这些样品分成两类，则这两个初始类的均值分别是5和 。(2)计算1到两个类(均值)的欧氏距离(0)(0)121,6,82,11GG和162(0)1(0)21,154111,16522dGdG781不用重新分配，计算6到两个类的距离故6应重新分配到 中，修正后的两个类为 ，新的类均值分别为 。计算(0)1(0)26,651116,6622dGdG(0)2G(1)22,6,11G和11462

34、3和(1)11,8G(1)1(1)2118,84322128,86133dGdG79结果8重新分配到 中，两个新类为 ，其类均值分别为1和 。再计算重新分配2到 中，两个新类为 ，其类均值分别为 。(3)再次计算每个样品到类均值的距离，结果列于表6.4.1。最终得到的两个类为1,2和6,8,11。(1)2G(2)11G364(2)1(2)22,211332,26444dGdG(2)1G(2)22,6,8,11G(3)11,2G,(3)26,8,11G111823和80表6.4.1 各样品到类均值的距离81v例6.4.2 对例6.3.3使用k均值法进行聚类，聚类前对各变量作标准化变换，聚类结果如

35、下：第类：北京、上海和浙江。第类：广东。第类：天津、江苏、福建、山东、湖南、广西、重庆、四川和云南。第类：河北、山西、内蒙古、辽宁、吉林、黑龙 江、安徽、江西、河南、湖北、海南、贵 州、陕西、甘肃、青海、宁夏和新疆。第类：西藏。82v由于k均值法对凝聚点的初始选择有一定敏感性，故再试一下其他初始的凝聚点也许是个不错的想法。如果不同初始凝聚点的选择产生明显不同的最终聚类结果，或者迭代的收敛是极缓慢的，那么可能表明没有自然的类可以形成。vk均值法有时也可用来改进系统聚类的结果，例如，先用类平均法聚类，然后将其各类的重心作为k均值法的初始凝聚点重新聚类，这可使得系统聚类时错分的样品能有机会获得重新的分类。不过，k均值法能否有效地改善系统聚类，我们不能一概而论，还应视聚类的最终结果而定。83