下面通过一个具体问题说明K均值法的计算过程。
【例】假定我们对A、B、C、D四个样品分别测量两个变量和得到结果见表5.9。 样品 变量 X1 X2 A 5 3 B -1 1 C 1 -2 D -3 -2 试将以上的样品聚成两类。
第一步：按要求取K=2，为了实施均值法聚类，我们将这些样品随意分成两类，比如（A、B）和（C、D），然后计算这两个聚类的中心坐标，见表5.10所示。
聚类 （A、B） （C、D） 中心坐标 X1 2 -1 X2 2 -2 表5.10中的中心坐标是通过原始数据计算得来的，比如（A、B）类的,X1?5?(?1)?2等等。 2第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品分配给最近的一类。对于样品有变动的类，重新计算它们的中心坐标，为下一步聚类做准备。先计算A到两个类的平方距离：
d2(A,(AB))?(5?2)2?(3?2)2?10， d2(A,(CD))?(5?1)2?(3?2)2?61
由于A到（A、B）的距离小于到（C、D）的距离，因此A不用重新分配。计算B到两类的平方距离：
d2(B,(AB))?(?1?2)2?(1?2)2?10，d2(B,(CD))?(?1?1)2?(1?2)2?9
由于B到（A、B）的距离大于到（C、D）的距离，因此B要分配给（C、D）类，得到新的聚类是（A）和（B、C、D）。更新中心坐标如表5.11所示。
聚类 （A） （B、C、D） 中心坐标 X1 5 -1 样品到中心的距离平方 B C 40 41 4 5 X2 3 -1 第三步：再次检查每个样品，以决定是否需要重新分类。计算各样品到各中心的距离平方，得结果见表5.12。
聚类 （A） （B、C、D） A 0 52 D 89 5 到现在为止，每个样品都已经分配给距离中心最近的类，因此聚类过程到此结束。最终得到K=2的聚类结果是A独自成一类，B、C、D聚成一类。
第五节 有序样品的聚类分析法
以上的系统聚类和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｝样品是次序相邻的。这类问题称为有序样品的聚类分析。
一、有序样品可能的分类数目
k?1n个有序样品分成k类，则一切可能的分法有Cn?1种。实际上，n个有序样品共有（n ?1）个间隔，分
成k类相当于在这（n ?1）个间隔中插入k ?1根“棍子”。由于不考虑棍子的插入顺序，是一个组合问
k?1题，共有Cn?1种插法。
这就是n个有序样品分成k类的一切可能分法。因此，对于有限的n和k，有序样品的所有可能分类结果是有限的，可以在某种损失函数意义下，求得最优解。所以有序样品聚类分析又称为最优分割，该算法是费希尔（Fisher）最先提出来的，故也称之为费希尔最优求解法。
二、费希尔最优求解法 2．定义分类的损失函数。费希尔最优求解法定义的分类损失函数的思想类似于系统聚类分析中的Ward法，即要求分类后产生的离差平方和的增量最小。用b(n,k)表示将n个有序样品分为k类的某一种分法：
G1?{i1,i1?1,?,i2?1}，G2?{i2,i2?1,?,i3?1}，?，Gk?{ik,ik?1,?,n}
其中i1?1?i1???ik?n。定义上述分类法的损失函数为
L[b(n,k)]??D(it,it?1?1) (5.31)
t?1k上式中的ik?1?n?1。
对于固定的n和k，L[(b(n,k)]越小，表示各类的离差平方和越小，分类就是越有效的。因此，要求寻找一种分法b(n,k)，使分类的损失函数L[(b(n,k)]最小，这种最优分类法记为p(n,k)。
3．求最优分类法的递推公式。具体计算最优分类的过程是通过递推公式获得的。先考虑k?2的情形对所
*有的j考虑使得,L[(b(n,2)]?D(1,j)?D(j,n)最小的j。得到最优分类p(n,2)：G1?{1,2,?,j*?1}，G2?{j*,?,n}。
图5.5 k?2时的情形
进一步考虑对于k，求p(n,k)。
这里需要注意，若要寻找将n个样品分为k类的最优分割，则对于任意的j（k ? j ? n）,先将前面j ?1个样品最优分割为k ?1类，得到p（j ? 1，k ? 1），否则从j到n这最后一类就不可能构成k类的最优分割，参见图5.6。再考虑使L[b（n，k）]最小的j＊，得到p（n，k）。
因此我们得到费希尔最优求解法的递推公式为
min{D(1,j?1)?D(j,n)}?L[p(n,2)]?2?j?n? ?L[p(n,k)]?min{L[p(j?1,k?1)]?D(j,n)}?k?j?n?4．费希尔最优求解法的实际计算。从递推公式(5.32)可知，要得到分点jk，使得
L[(p(n,k)]?L[p(jk?1,k?1)]?D(jk,n)
从而获得第k类：Gk?{jk,?,n}，必须先计算jk?1使得
L[(p(jk?1,k?1)]?L[p(jk?1?1,k?2)]?D(jk?1,jk?1)
从而获得第k?1类：Gk?1?{jk?1,?,jk?1}。
依此类推，?，要得到分点j3，使得L[(p(j4?1,3]?L[p(j3?1,2)]?D(j3,j4?1)
从而获得第3类：G3?{j3,?,j4?1}，必须先计算j2L[(p(j3?1,2)]?min{D(1,j?1)?D(j,j3?1)}
2?j?j3?1从而获得第2类：这时自然获得G1?{1,?,j2?1}。最后获得最优分割： G1,G2,?,Gk。G2?{j2,?,j3?1}。因此，实际计算过程中是从计算j2开始的，一直到最后计算出jk为止。
总之，为了求最优解，主要是计算{D(i,j),1?i?j?n}和{L[p(l,k)]，3?l?n,2?k?l,k?n?1}。
三、一个典型例子
【例5.4】为了了解儿童的生长发育规律，今随机抽样统计了男孩从出生到11岁每年平均增长的重量数据表5.13，试问男孩发育可分为几个阶段？ 年龄（岁） 1 2 3 增重（公斤） 9.3 1.8 1.9 在分析这是一个有序样品的聚类问题时，我们通过图形可以看到男孩增重随年龄顺序变化的规律，从图5.6中发现男孩发育确实可以分为几个阶段。
下面通过有序样品的聚类分析确定男孩发育分成几个阶段较合适。步骤如下：
（1）计算直径{D(i,j)}，结果如表5.14。例如计算D(1,2)，此类包含两个样品{9.3，1.8}，故有：
122XG?(9.3?1.8)=5.55， D(1,2)?(9.3?5.55)?(1.8?5.55)=28.125
2其它依此计算，其结果见表5.14。 i j 2 3 4 5 6 7 8 9 10 11 1 28.125 37.007 42.208 45.992 49.128 51.100 51.529 51.980 52.029 52.182 2 0.005 0.020 0.088 0.232 0.280 0.417 0.467 0.802 0.909 3 0.020 0.080 0.200 0.232 0.393 0.454 0.800 0.909 4 0.020 0.080 0.088 0.308 0.393 0.774 0.895 5 0.020 0.020 0.290 0.388 0.773 0.889 6 0.005 0.287 0.370 0.708 0.793 7 0.180 0.207 0.420 0.452 8 0.005 0.087 0.088 9 0.080 0.080 10 0.020 （2）计算最小分类损失函数{L[p(l,k)]}，结果如表5.15。 k l 2 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 11 0.005(2) 0.020(2) 0.088(2) 0.232(2) 0.280(2) 0.417(2) 0.469(2) 0.802(2) 0.909(2) 0.005(4) 0.020(5) 0.040(5) 0.040(5) 0.280(8) 0.285(8) 0.367(8) 0.368(8) 0.005(5) 0.020(6) 0.025(6) 0.040(8) 0.045(8) 0.127(8) 0.128(8) 0.005(6) 0.010(6) 0.025(8) 0.030(8) 0.045(10) 0.065(10) 0.005(6) 0.010(8) 0.015(8) 0.030(10) 0.045(11) 0.005(8) 0.010(3) 0.015(10) 0.030(11) 0.005(8) 0.010(10) 0.015(11) 0.005(8) 0.010(11) 0.005(11) 首先计算{L[p(l,2)],3?l?11}（即表中的k?2列），例如计算： L[p(3,2)]?min{D(1,j?1)?D(j,3)}?min{D(1,1)?D(1,3), D(1,2)?D(3,3)}
2?j?3?min{0?0.005, 28.125?0}?0.005
极小值是在j?2处达到，故记L[p(3,2)]?0.005(2)，其它类似计算。 再计算{L[p(l,3)],4?l?11}（即表中的k?3列），例如计算：
L[p(4,3)]?min{L[p(2,2)]?D(3,4),L[p(3,2)]?D(4,4)} ?min{0?0.02, 0.005?0}?0.005(4) 表5.15中其它数值同样计算，括弧内的数字表示最优分割处的序号。
（3）分类个数的确定。如果能从生理角度事先确定k当然最好；有时不能事先确定k时，可以从L[p（l，k）]随k的变化趋势图中找到拐点处，作为确定k的根据。当曲线拐点很平缓时，可选择的k很多，这时需要用其它的办法来确定，比如均方比和特征根法，限于篇幅此略，有兴趣的读者可以查看其它资料。
本例从表5.15中的最后一行可以看出k =3，4处有拐点，即分成3类或4类都是较合适的，从图5.8中可以更明显看出这一点。
（4）求最优分类。例如我们把儿童生长分成4个阶段，即可查表5.15中k?4例的最后一行（即l?11行）得L[p(11,4)]?0.128(8)，说明最优损失函数值为0.128，最后的最优分割在第8个元素处，因此G4?{8~11}或G4?{2.0,1.9,2.3,2.1}。进一步从表中查L[p(7,3)]?0.040(5)，因此G3?{5~7}或G3?{1.5,1.3,1.4}，再从表中查得L[p(4,2)]?0.020(2)最后G2?{2~4}或G2?{1.8,1.9,1.7}，剩下的G1?{9.3}。
