第5章 聚类分析幻灯片

第五章聚类分析第四节

K均值聚类分析

第五节有序样品的聚类分析法

第六节实例分析与计算机实现第5章聚类分析(2)第四节K均值聚类分析系统聚类法需要计算出不同样品或变量的距离，还要在聚类的每一步都要计算“类间距离”，相应的计算量自然比较大；特别是当样本的容量很大时，需要占据非常大的计算机内存空间，这给应用带来一定的困难。而K—均值法是一种快速聚类法，采用该方法得到的结果比较简单易懂，对计算机的性能要求不高，因此应用也比较广泛。K均值法是麦奎因（MacQueen，1967）提出的，这种算法的基本思想是将每一个样品分配给最近中心（均值）的类中，具体的算法至少包括以下三个步骤：

1．将所有的样品分成K个初始类；

2．通过欧氏距离将某个样品划入离中心最近的类中，并对获得样品与失去样品的类，重新计算中心坐标；

3．重复步骤2，直到所有的样品都不能再分配时为止。第5章聚类分析(2)K均值法和系统聚类法一样，都是以距离的远近亲疏为标准进行聚类的，但是两者的不同之处也是明显的：系统聚类对不同的类数产生一系列的聚类结果，而K—均值法只能产生指定类数的聚类结果。具体类数的确定，离不开实践经验的积累；有时也可以借助系统聚类法以一部分样品为对象进行聚类，其结果作为K—均值法确定类数的参考。下面通过一个具体问题说明K均值法的计算过程。第5章聚类分析(2)【例5.3】假定我们对A、B、C、D四个样品分别测量两个变量和得到结果见表5.9。 试将以上的样品聚成两类。表5.9样品测量结果第5章聚类分析(2)

第一步：按要求取K=2，为了实施均值法聚类，我们将这些样品随意分成两类，比如（A、B）和（C、D），然后计算这两个聚类的中心坐标，见表5.10所示。 表5.10中的中心坐标是通过原始数据计算得来的，比如（A、

B）类的，等等。表5.10中心坐标第5章聚类分析(2)

第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品分配给最近的一类。对于样品有变动的类，重新计算它们的中心坐标，为下一步聚类做准备。先计算A到两个类的平方距离： 由于A到（A、B）的距离小于到（C、D）的距离，因此A不用重新分配。计算B到两类的平方距离：第5章聚类分析(2)由于B到（A、B）的距离大于到（C、D）的距离，因此B要分配给（C、D）类，得到新的聚类是（A）和（B、C、D）。更新中心坐标如表5.11所示。表5.11更新后的中心坐标第5章聚类分析(2)

第三步：再次检查每个样品，以决定是否需要重新分类。计算各样品到各中心的距离平方，得结果见表5.12。到现在为止，每个样品都已经分配给距离中心最近的类，因此聚类过程到此结束。最终得到K=2的聚类结果是A独自成一类，B、C、D聚成一类。表5.12样品聚类结果第5章聚类分析(2)9

K-均值聚类法的步骤选择聚点的方法：(1)经验选择：如果对研究对象比较了解，根据以往的经验确定k个样品作为聚点；(2)将n个样品人为地或随机地分为k类，以每类地均值(称为重心)作为聚点。1选择聚点：是一批有代表性的样品，它的选择决定了初始分类，对最终分类有较大的影响；先定下分类的数目k，在每一类中选择一个有代表性的样品作为聚点(初始聚点)第5章聚类分析(2)10(3)最大最小原则：将n个样品分为k类，选择相距最远的两个样品xi1,xi2为初始的两个聚点。即

再选择第3个聚点xi3,使其与前两个聚点的距离最小者等于所有其余的与前两者的距离较小中的最大者，即

按同一原则选取第4个，依此下去，直至选出k个聚点xi1,xi2,…,xik.第5章聚类分析(2)11

最大最小原则的一般过程可以用递推公式表达。若已选了l个聚点(l<k),则第l+1个聚点xl+1为

SAS系统procfastclus过程中，分类数k是事先给定的，在给定k以后，可按上述方法(1)或(3)选出初始聚点。第5章聚类分析(2)12(1)设k个初始聚点集为假设采用欧氏距离用下列原则，i=1,…,k

将样品分成不相交的初始k类，此原则是每个样品以最靠近的初始聚点归类，初始分类为

K-均值聚类法的步骤第5章聚类分析(2)13(2)从G(0)出发,求新的聚点集L(1).以G(0)的重心为新的聚点：新的聚点集为

从L(1)出发,

根据靠近聚点原则将样品作新的分类,

i=1,…,k得到新的分类集依次计算下去第5章聚类分析(2)14(3)设在第m步得到分类为注意：是类的重心不一定是样品，一般不是的重心.当m逐渐增大时，分类趋于稳定，从而就会近似为的重心因而有算法结束。实际计算时，若从第m步开始,分类与完全相同时，计算结束第5章聚类分析(2)15

SAS系统procfastclus过程中，设置的收敛准则为当聚点改变的最大距离小于或等于初始聚点之间的最小距离乘以给定的某个数值ε时，计算过程结束，即若令给定ε>0,

若则递推计算过程结束.procfastclus过程中ε默认0.02第5章聚类分析(2)16procfastclus过程:procfastclusmaxclusters=n|radius=t

<options>;Varvariables;Idvariable;Run;procfastclus

语句必须说明maxclusters=或radius=中的一个。MAXCLUSTERS=n|MAXC=n：指定所允许的最大分类个数。如果缺省，其值假定100。RADIUS=t：为选择新的“聚点”指定的最小距离准则。当观测点与已有的“聚点”的最小距离均大于由该选项规定的值t时，该观测可考虑用来作为新的“聚点”。的缺省值为0。如果使用选项replace＝random，则RADIUS＝不起作用。第5章聚类分析(2)17procfastclusmaxclusters=n|radius=t

<options>;1、规定数据集及细节的选项①DATA＝(SAS数据集)—进行聚类的观测的数据集名字。数据必须是坐标数据，不能是距离、相似或相关值。②MEAN=(SAS数据集)—生成一个输出数据集，其中包含每个类的均值和一些统计量。③OUT＝(SAS数据集)—生成一个输出数据集，其中包含原始数据和新变量CLUSTER和DISTANCE。④CLUSTER=NAME—规定在MEAN＝和OUT＝的数据集中用以指示观测属于哪一类的变量名字。缺省时这个指示变量的名字为CLUSTER。第5章聚类分析(2)182、选择初始“聚点”的选项：①RANDOM＝n—规定一个正整数n，用在REPLACE＝RANDOM中作为伪随机数发生的种子(初值)；如果缺省则使用当天的时间来初始化随机数发生器。Least=m:表示用Lm距离进行聚类;3、控制打印输出选项①

DISTANCE—要求打印类均值之间的距离②

LIST—要求列出所有观测的ID变量值（如果有），观测所归入类的类好及观测与最终“聚点”之间的距离procfastclusmaxclusters=n|radius=t

<options>;第5章聚类分析(2)194、计算最终类“聚点”的选项：①DRIFT—执行聚类的逐个修改法。在初始“聚点”选好后，每当一个观测靠近的“聚点”所在的类后，此类的“聚点”都要被该类中现有观测的均值所代替。

MAXITER＝n—指定重新计算类的“聚点”的最大迭代次数。当n＞0时，

FASTCLUS执行聚类步骤的步骤3。在每次循环中，所有观测均归入最近“聚点”的类后，此类的“聚点”用该类的均值替代。n的缺省值为l。procfastclusmaxclusters=n|radius=t

<options>;第5章聚类分析(2)20procfastclus过程:procfastclusmaxclusters=n|radius=t

<options>;Varvariables;Idvariable;Run;Varvariables;

列出参与聚类分析的指标变量名称若省略，则未列在其它语句(如其后的ID语句)中的数值变量均参与分析。Idvariable;用以表征各样品的名称，它可以是定性变量也可以是定量变量。第5章聚类分析(2)21procfastclus过程的缺点：没有将原始数据标准货摊功能；不能自动确定类别数；需要确定初始聚点；不能输出树状图的聚类信息；因此，在使用此过程前，可以用standard过程步将原始数据标准化，即将数据化为均值为0、标准差为1的数据；要根据经验确定类别数；要根据经验选取聚点，或者在确定类别数的基础上指令系统自动选取初始聚点；procfastclus过程的优点：能快速对大样本进行聚类分析且聚类后输出类内指标的均值；第5章聚类分析(2)22procstandard过程:procstandarddata=out=mean=0std=1;Varvariables;Run;out=

给出含有化数据的新数据集名。mean=0给出标准化数据的均值，一般取0;std=1给出标准化数据的标准差，一般取1;Varvariables给出要标准化的变量;

第5章聚类分析(2)*23例6.1对13个国家1990年，1995年与2000年的可持续发展综合国力做评估，其得分值如表6.1,试用快速聚类法将上述13个国家分为4类dataexamp6_1;inputcountry$x1x2x3@@;cards;澳大利亚1249.391273.611282.68

巴西821.60859.85919.73

加拿大1641.011591.541608.32

中国1330.451382.681462.08

法国1546.551501.771525.95

德国1656.521630.521570.69

印度861.30862.51945.11意大利1321.771232.301243.51

日本1873.681949.891851.20

俄罗斯1475.161315.871297.00

南非794.25787.48782.38

英国1486.751441.711465.12

美国2824.292659.642740.12;

run;第5章聚类分析(2)*24procfastclusdata=examp6_1out=aamean=bbmaxc=4cluster=clistdistance;varx1x2x3;idcountry;run;procgplotdata=aa;/*做聚类结果的散点图*/plotx2*x1=c;symbol1v='1';symbol2v='2';symbol3v='3';symbol4v='4';run;第5章聚类分析(2)*25procfastclusdata=examp6_1out=aa

mean=bb

maxc=4cluster=clistdistance;varx1x2x3;idcountry;run;data=examp6_1/*指明以分析的数据集，数据是原始观测数据，不能是距离或相似矩阵*/

out=aa

/*生成一个输出数据集，包括原始数据及两个新变量：指示样品属于哪个类的变量cluster和各样品到所属类的中心的距离distance*/maxc=4

/*指出所允许的分类数，若省略则默认为n=100.必须指定才能快速聚类*/第5章聚类分析(2)*26procfastclusdata=examp6_1out=aa

mean=bbmaxc=4cluster=clistdistance;varx1x2x3;idcountry;run;mean=bb/*生成一个输出数据集，包括各个类的均值和其他统计量*/cluster=c/*规定在上面的两个输出数据集中用以指示样品属于哪一个类的变量名称，缺省时系统自动命名为cluster*/

List

/*列出所有样品的ID变量值(如果有)，样品所归入类的类号及观测与最终“聚点”之间的距离*/第5章聚类分析(2)*27procfastclusdata=examp6_1out=aa

mean=bbmaxc=4cluster=clistdistance;varx1x2x3;idcountry;run;distance/*要求打印类均值之间的距离*/varx1x2x3;

/*列出参与聚类分析的指标变量名称若省略，则未列在其它语句(如其后的ID语句)中的数值变量均参与分析。*/

idcountry;/*用以表征各样品的名称，它可以是定性变量也可以是定量变量*/。第5章聚类分析(2)*28

InitialSeeds/*初始聚点*/Clusterx1x2x311321.771232.31243.512794.25787.48782.3832824.292659.642740.1241873.681949.891851.2

InitialMeans/*各个类中每个指标观察值的均值*/Clusterx1x2x311401.6783331357.9900001379.3900002825.716667836.613333882.40666732824.2900002659.6400002740.12000041723.7366671723.9833331676.736667第5章聚类分析(2)*29

ClusterListing/*快速聚类结果*/ObscountryClusterDistancefromSeed1澳大利亚1199.22巴西244.1579

加拿大4170.54中国1111.95法国1251.36德国4156.57印度276.60638意大利1201.69日本4322.410俄罗斯1118.211南非2115.8

英国1147.013美国30第5章聚类分析(2)*30ClusterStandardDeviations/*每个类中各个指标观察值的标准差*/Clusterx1x2x31116.8546938102.9401552118.5507598233.714030242.571495587.55019493...4130.0860962196.6093249152.2566755第5章聚类分析(2)*31

DistanceBetweenClusterCentroids/*各重心之间的距离*/NearestClu12341.922.2572360.0218571.04092922.2567.3281.58811491.58432360.02183281.5881.1793.7264571.04091491.58491793.7266.第5章聚类分析(2)*32第5章聚类分析(2)第五节有序样品的聚类分析法

一有序样品可能的分类数目

二费希尔最优求解法三一个典型例子第5章聚类分析(2)以上的系统聚类和K—均值聚类中，样品的地位是彼此独立的，没有考虑样品的次序。但在实际应用中，有时样品的次序是不能变动的，这就产生了有序样品的聚类分析问题。例如对动植物按生长的年龄段进行分类，年龄的顺序是不能改变的，否则就没有实际意义了；又例如在地质勘探中，需要通过岩心了解地层结构，此时按深度顺序取样，样品的次序也不能打乱。如果用X（1），

X（2），

…，X（n）表示n个有序的样品，则每一类必须是这样的形式，即X（i），X（i+1)，…，X（j），其中1

r

n，且j

n，简记为Gi

=

｛i，i+1，…，j｝。在同一类中的样品是次序相邻的。这类问题称为有序样品的聚类分析。第5章聚类分析(2)一、有序样品可能的分类数目n个有序样品分成k类，则一切可能的分法有种。实际上，n个有序样品共有（n

1）个间隔，分成k类相当于在这（n

1）个间隔中插入k

1根“棍子”。由于不考虑棍子的插入顺序，是一个组合问题，共有种插法。 图5.4有序样品的分类法这就是n个有序样品分成k类的一切可能分法。因此，对于有限的n和k，有序样品的所有可能分类结果是有限的，可以在某种损失函数意义下，求得最优解。所以有序样品聚类分析又称为最优分割，该算法是费希尔（Fisher）最先提出来的，故也称之为费希尔最优求解法。第5章聚类分析(2)二、费希尔最优求解法

第5章聚类分析(2)第5章聚类分析(2)这里需要注意，若要寻找将n个样品分为k类的最优分割，则对于任意的j（k

j

n）,先将前面j

1个样品最优分割为k1类，得到p（j1，k1），否则从j到n这最后一类就不可能构成k类的最优分割，参见图5.6。再考虑使L[b（n，k）]最小的j＊，得到p（n，k）。因此我们得到费希尔最优求解法的递推公式为（5.23）图5.6最优分割第5章聚类分析(2)第5章聚类分析(2)

第5章聚类分析(2)三、一个典型例子【例5.4】为了了解儿童的生长发育规律，今随机抽样统计了男孩从出生到11岁每年平均增长的重量数据表5.13，试问男孩发育可分为几个阶段？在分析这是一个有序样品的聚类问题时，我们通过图形可以看到男孩增重随年龄顺序变化的规律，从图5.6中发现男孩发育确实可以分为几个阶段。表5.131－11岁儿童每年平均增长的重量第5章聚类分析(2)图5.7儿童成长阶段分析第5章聚类分析(2)下面通过有序样品的聚类分析确定男孩发育分成几个阶段较合适。步骤如下：第5章聚类分析(2)表5.14直径D（i，j）

第5章聚类分析(2)第5章聚类分析(2)

第5章聚类分析(2)

（3）分类个数的确定。如果能从生理角度事先确定k当然最好；有时不能事先确定k时，可以从L[p（l，k）]随k的变化趋势图中找到拐点处，作为确定k的根据。当曲线拐点很平缓时，可选择的k很多，这时需要用其它的办法来确定，比如均方比和特征根法，限于篇幅此略，有兴趣的读者可以查看其它资料。本例从表5.15中的最后一行可以看出k

=3，4处有拐点，即分成3类或4类都是较合适的，从图5.8中可以更明显看出这一点。第5章聚类分析(2)第5章聚类分析(2)第5章聚类分析(2)第六节实例分析与计算机实现一在SPSS中利用系统聚类法进行聚类分析

二在SPSS中利用K均值法进行聚类分析

第5章聚类分析(2)一、在SPSS中利用系统聚类法进行

聚类分析设有20个土壤样品分别对5个变量的观测数据如表5.16所示，试利用系统聚类法对其进行样品聚类分析。表5.16土壤样本的观测数据第5章聚类分析(2)第5章聚类分析(2)

（一）操作步骤

1.在SPSS窗口中选择Analyze→Classify→HierachicalCluster，调出系统聚类分析主界面，并将变量X1～X5移入Variables框中。在Cluster栏中选择Cases单选按钮，即对样品进行聚类（若选择Variables，则对变量进行聚类）。在Display栏中选择Statistics和Plots复选框，这样在结果输出窗口中可以同时得到聚类结果统计量和统计图。第5章聚类分析(2)图5.15K均值聚类分析主界面第5章聚类分析(2) 2.点击Iterate按钮，对迭代参数进行设置。MaximumIterations参数框用于设定K-means算法迭代的最大次数，ConvergenceCriterion参数框用于设定算法的收敛判据，其值应该介于0和1之间。例如判据设置为0.02，则当一次完整的迭代不能使任何一个类中心距离的变动与原始类中心距离的比小于2时，迭代停止。设置完这两个参数之后，只要在迭代的过程中先满足了其中的参数，则迭代过程就停止。这里我们选择系统默认的标准。单击Continue，返回主界面。图5.16Iterate子对话框第5章聚类分析(2) 3.点击Save按钮，设置保存在数据文件中的表明聚类结果的新变量。其中Clustermembership选项用于建立一个代表聚类结果的变量，默认变量名为qcl_1；Distancefromclustercenter选项建立一个新变量，代表各观测量与其所属类中心的欧氏距离。我们将两个复选框都选中，单击Continue按钮