模式识别导论第6章聚类分析

第6章聚类分析6.1聚类分析的根本概念6.2模式相似性测度和聚类准那么6.3基于距离阈值的聚类法6.4层次聚类法6.5动态聚类算法聚类是按照一定的要求和规律对事物进行区分和分类的过程。在这一过程中没有任何关于类别的先验知识，也没有教师的指导，仅靠事物间的相似性作为类属划分的准那么，使其得到的每个类中的模式(样本)是相似的，而不同类之间的模式(样本)差异较大。聚类源于很多领域，包括数学、计算机科学、统计学、生物学和经济学。

本章讨论聚类分析的根本概念、模式相似性测度和聚类准那么，重点介绍基于距离阈值的聚类法、层次聚类法和动态聚类法。6.1聚类分析的根本概念

聚类表达了“人以群分，物以类聚〞的思想，是一种重要的人类行为。早在孩提时代，一个人就能通过不断地改进下意识中的聚类模式来学会如何区分诸如猫和狗，桌子和椅子等对象。聚类也是一个古老的问题，它伴随着人类社会的产生和开展而不断深化，人类要认识世界就必须区别不同的事物并且认识事物间的相似性。下面我们以动物为例进行说明：羊、狗、猫(哺乳动物)、麻雀、海鸥(鸟类)、蛇、蜥蜴(爬虫类)、金鱼、蓝鲨(鱼)、青蛙(两栖)。如果我们按照肺是否存在来对它们进行分类，那么金鱼和蓝鲨是一类，其他的动物为第二类(见图6.1(a))。如果我们以它们生活的环境进行分类，那么羊、狗、猫、麻雀、海鸥、蛇和蜥蜴都是陆生动物，金鱼和蓝鲨是水生动物，青蛙由于是两栖动物将单独成为第三类(见图6.1(b))。当然我们还可以以它们繁衍后代的方式等其他的聚类准那么来对这些动物进行分类，这里就不再一一列举了。图6.1不同聚类准那么下的聚类分析聚类分析是指用数学的方法研究和处理给定对象的分类过程。下面给出聚类分析的数学描述。

设X={x1，x2，…，xn}是待聚类的样本集，聚类分析就是将样本集X聚集成c个子类ω1，ω2，…，ωc，并使得ω1，ω2，…，ωc满足以下条件：

(6-1)

从上述条件可以看出，样本集中的每个样本一定只属于某一类，并且最多只属于这一类。由于在分类中不需要用训练样本进行学习和训练，因此聚类分析属于无监督分类的范畴。需要指出的是，当人为选定某些特征，采用某种模式相似性度量，运用某种聚类算法时，实际上已引入了某些知识和信息，从而隐含地对模式集的分类结构做了大致的估计。使用不同的特征，或采用不同的模式相似性度量，或运用不同的聚类算法等都将产生不同的聚类结果。所以在处理实际问题时，必须要深入了解问题，使选用的特征和相似性度量、运行的聚类算法等能与问题很好的匹配。6.2模式相似性测度和聚类准那么

6.2.1模式相似性测度

模式之间具有一定的相似性，利用相似性度量可以定量地衡量模式间的相似程度，并对相似的模式进行归类。这里我们以量之间的测度为例进行介绍。

1.距离测度

设向量x和y之间的距离记为

ρ(x，y)，ρ(x，y)应满足如下的公理：

(1)ρ(x，y)≥0,当且仅当x=y时等号成立，即

；(2)ρ(x，y)=ρ(y，x)；

(3)ρ(x，y)≤ρ(x，z)+ρ(z，y)。

设x=(x1，x2，…，xd)T，y=(y1，y2，…，yd)T，下面给出几种常用的距离测度。

欧氏(Euclidean)距离：

绝对值距离(市区距离或Manhattan距离)：(6-2)(6-3)切氏(Chebyshev)距离：

明氏(Minkowski)距离：

可以看出，式(6-2)、式(6-3)和式(6-4)实际上分别是式(6-5)在p=2、1和∞时的特殊情况。在实际中应用较多的是欧氏距离，该距离测度具有平移性和旋转不变性。

马氏(Mahalanobis)距离：设向量xi和xj是向量集{x1，x2，…，xn}中的两个向量，它们之间的马氏距离定义为(6-4)(6-5)(6-6)其中(6-7)(6-8)由于V是这个向量集的样本协方差矩阵，因此马氏距离对特征的相关性做了处理。此外，马氏距离对一切非奇异线性变换都是不变的，它还是平移不变的。需要指出，当向量x和y分别是两个数据集中的样本时，设C是它们的互协方差矩阵，那么x和y之间的马氏距离定义为

ρ2(x，y)=(x－y)TC－1(x－y)(6-9)

以上定义的模式相似性度量都是距离测度，两个模式越相似，其测度值越小。

2.相似测度

角度相似系数(夹角余弦)：采用两个向量的夹角余弦来度量它们之间的相似性，定义为

相关系数：数据中心化后的向量夹角余弦，定义为

此处将向量x和y分别看为两个数据集中的样本，和

分别是这两个数据集的平均向量。(6-10)(6-11)指数型相似系数：

式中，σ2i为相应分量的方差，d为向量维数。

以上都是相似测度，最大值为1。两个模式越相似，其测度值越大。(6-12)6.2.2聚类准那么

1.类内距离准那么

类内距离准那么是一种简单且应用广泛的聚类准那么。设待分类的样本集X={x1，x2，…，xn}被划分成c个类ωi(i=1，2，…，c)，其中ωi类的样本数目为ni，。那么，类内距离准那么函数JW定义为

其中，mi表示ωi类的样本均值向量：(6-13)(6-14)类内距离准那么实际上是各样本到其被指派的类的类中心距离平方和，这个准那么也被称为误差平方和准那么。该准那么适用于同类样本密集且各类样本分布区域体积差异不大的情况。当两类样本所占的空间大小明显不同，两类间的距离又缺乏够大时，样本较多的那个类会被分割开，从而产生错误的划分，如图6.2所示。图6.2类内距离准那么产生错误划分的情形2.类间距离准那么

类间距离准那么定义为

式中，mi为ωi类的样本均值向量，m为所有样本的均值向量，其定义如下；

此外，加权的类间距离准那么定义为(6-15)需要指出，类内距离准那么JW是越小越好，而类间距离准那么JB是越大越好。我们希望聚类结果能够同时使得类内距离越小越好、类间距离越大越好。下面介绍能够同时反映类内和类间距离的准那么函数。3.基于类内距离和类间距离的准那么函数

我们在第2章给出了两类情况下的类内和类间离散度矩阵的定义，下面给出多类情况下的类内和类间离散度矩阵的具体定义。

首先定义ωi类的类内离散度矩阵；

总的类内离散度矩阵定义为(6-16)(6-17)类间离散度矩阵定义为

总的离散度矩阵定义为

SW、SB和ST有下面的关系；

ST=SW+SB(6-20)(6-18)(6-19)从上面的定义可知，总的离散度矩阵ST与样本集如何分类无关，只取决于样本如何分布，而类内离散度矩阵SW和类间离散度矩阵SB不仅与样本的分布有关，而且与样

本的划分有关。SW、SB和ST分别从不同的方面反映了样本散布的结构信息，通常采用它们的数值特征，如迹、行列式和特征值等构造聚类准那么函数。

矩阵主对角线上的元素之和称为迹，类内离散度矩阵的迹Tr［SW］定义为(6-21)从上式可知，类内离散度矩阵的迹Tr［SW］表征了各类样本围绕其中心在各个坐标轴方向上散布的方差的加权平均。类间离散度矩阵的迹Tr［SB］定义为

从上式可知，类间离散度矩阵的迹Tr［SB］反映了各类样本中心相对总的样本中心在各个坐标轴方向上的散布距离平

方的加权平均。(6-22)因为Tr［ST］=Tr［SW］+Tr［SB］，当简单地以

作为准那么时，等价于以Tr［SB］=JWBmax作为准那么，即在最小化Tr［SW］的同时，最大化

Tr［SB］。

利用SW、SB和ST可以定义如下的聚类准那么函数；(6-23)(6-24)(6-25)(6-26)

由这些准那么函数的定义可以看出，为得到好的聚类结果，应该使它们尽量的大(小)。在后面介绍特征提取和选择时也经常使用这类准那么函数。(6-27)(6-28)6.3基于距离阈值的聚类法

6.3.1近邻聚类法

设X={x1，x2，…，xn}是待聚类的样本集，ξ表示类内距离阈值。

近邻聚类法的根本思想是计算样本到各聚类中心的距离，并与阈值ξ进行比较，决定该样本属于哪一类或者作为新的一类中心。具体步骤如下：

(1)选取任意一个样本作为第一个聚类中心v1，例如令ω1类的中心v1=x1。(2)计算下一个样本x2到v1的距离ρ21。假设ρ21>ξ，那么建立新的一类ω2，其中心v2=x2；假设ρ21≤ξ，那么认为x2属于ω1类。

(3)假定已有l个聚类中心v1，v2，…，vl，计算尚未确定类别的样本xj到l个聚类中心vi(i=1，2，…，l)的距离ρji。如果ρji均满足ρji>ξ(i=1，2，…，l)，那么将xj作为新的一类ωl+1的中心vl+1，即vl+1=xj；否那么，将xj划分到距离

其最近的聚类中心所代表的类中。(4)检查是否所有的样本已经确定类别，如果都确定完毕,那么算法结束；否那么返回步骤(3)。

近邻聚类法的思想比较简单，其聚类结果与第一个聚类中心的选取、待分类样本的排列次序、阈值ξ的大小以及样本分布的几何特性有关。如果对于聚类结果不满意，可以重新选取第一个聚类中心v1和距离阈值ξ，比较屡次试探分类结果，选取最合理的一个作为最终的聚类结果。6.3.2最大最小距离聚类法

最大最小距离聚类法的根本思想是在样本集中以最大距离原那么选取新的聚类中心，以最小距离原那么进行样本归类。在该算法中，经常使用欧氏距离。

下面介绍最大最小距离聚类法的算法步骤：

(1)选取任意一个样本作为第一个聚类ω1的中心v1。

(2)选取距离v1最远的样本作为第二个聚类ω2的中心v2。

(3)计算所有尚未作为聚类中心的各样本{xj}与v1、v2的距离ρj1和ρj2，并求出它们之中的最小值ρj=min［ρj1，ρj2］。(4)假设存在样本xk得，那么将xk作为第三个聚类ω3的中心v3，然后转步骤(5)；否那么转步骤(6)。

(5)假定已有l个聚类中心，计算尚未作为聚类中心的各样本{xj}到l个聚类中心vi(i=1，2，…，l)的距离，并计算，如果ρk>θ·ρ(v1，v2)，那么将样本xk作为第l+1个聚类中心vl+1，并转步骤(5)；否那么转步骤(6)。(6)将全部样本按最小距离原那么划分到各类中，对于样本{xj}，如果，那么xj∈ωr。

最大最小距离聚类法的性能与参数θ及第一个聚类中心v1的选取有关。如果没有先验知识指导θ和v1的选取，可以适当调整θ和v1，比较屡次试探分类结果，选取最合理的一个聚类结果。6.4层次聚类法

我们前面讨论的聚类算法中，形成的类与类之间是没有任何联系的。在实际中，一个大类中有可能包含很多子类，子类又包含许多更小的子类。层次聚类的方法是对给定的样本集进行层次的分解，直至到达分类要求为止。按照自底向上还是自顶向下进行层次分解，可以将层次聚类法分成凝聚的层次聚类和分裂的层次聚类。凝聚的层次聚类首先将每个样本自成一类，然后按照一定的准那么逐渐合并，减少类别数，直到满足某个终止条件停止合并。分裂的层次聚类与之相反，它首先将所有的样本看成一类，然后逐渐划分为越来越小的类，直到满足某个终止条件。6.4.1类与类之间的距离

在层次聚类法的类合并或分裂过程中，需要考察类间距离准那么。

下面给出一些常用的类间距离定义。

1.最近距离法

聚类ωp和ωq之间的最近距离定义为

其中，ρij表示样本xi∈ωp与样本xj∈ωq之间的距离。如果ωq是由ωs和ωt两类合并而成的，那么有

Dpq=min［Dps，Dpt］(6-30)(6-29)2.最远距离法

聚类ωp和ωq之间的最远距离定义为

(6-31)

如果ωq是由ωs和ωt两类合并而成的，那么有

Dpq=max［Dps，Dpt］(6-32)3.中间距离法

设聚类ωp到ωs和ωt的距离分别为Dps和Dpt，ωs到ωt的距离为Dst,以这3个距离值为边长做三角形△pst，如图6.3所示。在△pst中，边st的中线长的平方等于

，以该中线长作为新类ωq=ωs∪ωt与ωp间的距离，该距离介于最近距离与最远距离之间，称为中间距离，其具体定义为(6-33)图6.3中间距离法示意图4.重心距离法

从物理的观点看，假设要用一个点表示一个类的空间位置，那么类的重心较为合理。因此，类与类之间的距离可以定义为它们重心之间的距离。设类ωs和类ωt分别有ns和nt个样本，其重心分别为xs和xt。如果将类ωs和类ωt合并为ωq，那么ωq有nq=ns+nt个样本，那么类ωq的重心为

设另一类ωp的重心为xp，那么ωp和ωq之间的距离平方为(6-34)(6-35)利用，那么有(6-36)5.平均距离法

聚类ωs和ωt之间的距离平方可以采用两类样本两两之间的平均平方距离来定义，即(6-37)假设将ωs和ωt合并为ωq，那么类ωp和类ωq之间的距离平方为(6-38)由于平均距离法利用了各个类中样本的信息，在层次聚类法中采用该距离度量的效果比较理想。6.可变平均距离法

可变平均距离法是在平均距离法的递推公式(6-38)中参加Dst的影响，递推公式修正为

7.离差平方和法

设聚类ωk的重心是xk，类内离差平方定义为(6-39)(6-40)两个聚类合并后，类内离差平方和要变大，把两类合并后所增加的离差平方和定义为两类之间的平方距离。设类ωs和ωt合并得到类ωq，定义。可以证明，ωs和ωt之间的平方距离为

式中，xs和xt分别表示类ωs和ωt的重心，ns和nt分别表示类ωs和ωt的样本数。那么，类ωp和ωq之间的离差平方和为(6-42)(6-42)其中，np和nq分别表示类ωp和ωq的样本数。在层次聚类法中也经常采用该距离作为类间距离度量。

上述七种类间距离度量的递推公式可以统一成如下的形式；

这里，ωq=ωs∪ωt。上式中系数αs、αt、β、γ取不同值时，可以得到不同的类间距离递推公式。表6.1给出了上述七种类间距离中各个系数的取值。(6-43)表6.1各种类间距离递推公式中的系数

6.4.2层次聚类法

层次聚类法(HierarchicalClusteringMethod)的根本思想是：首先将n个样本各自看成一类，然后计算类与类之间的距离，选择距离最小的两个类合并成一个新类，接着计算在新的类别划分下各类之间的距离，再将距离最近的两类合并，这样每次减少一类，直至所有样本聚成两类为止，或者直到满足分类要求。层次聚类算法的具体步骤如下：

(1)初始分类。令k=0，每个样本自成一类，即，其中，i=1，2，…，n。(2)计算各类之间的距离Dij，由此得到一个类间距离矩阵D(k)=(Dij)c×c，其中c为类别个数(初始时c=n)。

(3)找出前一步求得的距离矩阵D(k)中的最小元素，设它是和间的距离，将和合并为一类，由此得到新的分类，…。令k=k+1，c=c－1，计算新的距离矩阵D(k)。(4)检查类的个数。如果类的个数c等于2或者到达某种分类要求，那么算法停止；否那么，转步骤(3)。

图6.4给出了层次聚类法的示意图；(a)中给出了样本集聚类的过程；(b)中给出了聚类过程的树图；(c)是该过程的Venn图。在层次聚类过程中，类别由多变少，聚类中心不断进行调整。需指出，在层次聚类法中，某个样本一旦划到某个类以后就不会再改变了。图6.4层次聚类示意图例6.1下面给出六个样本构成的数据，分别按最近距离法和平均距离法对该数据进行层次聚类。

x1=(0，3，1，2，0)T,x2=(1，3，0，1，0)T,

x3=(3，4，0，0，1)T，x4=(1，1，0，2，0)T,

x5=(3，3，1，2，1)T,x6=(4，2，1，1，0)T解首先采用最近距离法，步骤如下：

(1)将每个样本自成一类；

按照欧式距离计算距离矩阵D(0)(见表6.2)。表6.2最近距离法对应的D

(2)D(0)中的最小阵元是，它是和之间的距离，因此将它们合并为一类，得到新的分类结果；

计算合并后的距离矩阵D(1)(见表6.3)。在这里使用最近距离法得到；表6.3最近距离法对应的D(1)

(3)D(1)中的最小阵元是2，它是和之间的距离，将它们合并得到新的类；

同样计算D(2)(见表6.4)，进一步聚类得到；

即

计算D(3)(见表6.5)。表6.4最近距离法对应的D(2)

表6.5最近距离法对应的D(3)

(4)由表6.5可知，D(3)中的最小阵元是，它是和

之间的距离，将它们合并得到新的类，即，。

其次采用平均距离法，计算过程如下：

(1)按照欧式距离计算距离矩阵D(0)，见表6.2。

(2)D(0)中的最小阵元是，它是和之间的距离，因此将和合并，得到新的分类结果；采用平均距离法计算合并后的距离矩阵D(1)。这里以为例，利用平均距离法，和之间的距离为

因此，．采用平均距离法计算D(1)(见表6.6)。表6.6平均距离法对应的D(1)

(3)D(1)中的最小阵元是2，它是和之间的距离，将它们合并得到新的类；

同样采用平均距离法计算D(2)(见表6.7)。

进一步聚类得到；

即

计算D(3)(见表6.8)。表6.7平均距离法对应的D(2)

表6.8平均距离法对应的D(3)

进一步聚类得到；

即

注意,本例中两种距离测度下的层次聚类结果是一样的。需指出，在一般情况下，基于不同距离度量的层次聚类结果不一定相同。6.5动态聚类算法

在近邻聚类法和最大最小距离聚类法中，类中心一旦选定后，在后续的聚类过程中就不会改变。虽然层次聚类算法的类中心在后续聚类过程中可以被调整，但是某个样本一旦划到某个类以后，就不会再改变。除了上述的聚类算法，还有一种动态聚类法。动态聚类法的根本思想是首先选择一些初始聚类中心，然后把样本按照某种原那么划分到各类中，获得初始分类的结果，接着采用某种原那么进行修正，直到得到比较合理的分类结果为止。动态聚类法的根本流程框图如图6.5所示。图6.5动态聚类法的流程框图下面介绍两种典型的动态聚类方法；硬c-均值聚类算法(Hardc-meansClusteringAlgorithm，HCM)和迭代自组织数据分析算法(IterativeSelf-OrganizingDataAnalysisTechniques

Algorithm，ISODATA)。

6.5.1HCM算法

对于给定的数据集X={x1，x2，…，xn}，设聚类的数目c是的，HCM算法的根底是误差平方和准那么，采用下式作为目标函数；

其中vi是第i个聚类的聚类中心。(6-44)

HCM算法首先选定c个聚类中心，按最小距离原那么将各样本分配到c个类中的某一类，之后不断计算类中心并调整各样本的类别，最终使得所有样本到其所属聚类的中心的距离平方和到达最小。

HCM算法的流程如下：

(1)任选c个初始聚类中心：，其中，上角标k表示聚类过程中的迭代次数，其初始值为0。

(2)对于某一样本xj，假设满足(6-45)

那么。按照此最小距离原那么将全部样本分配到c个聚类中，就产生了新的聚类，i=1，2，…，c。

(3)计算重新分类后的各聚类中心：

式中，为类中包含的样本数。

(4)假设(i=1，2，…，c)，那么结束；否那么，k=k+1，转到步骤(2)。，i=1，2，…，c(6-46)

HCM算法的性能与聚类中心的数目c和初始聚类中心的选择有关。在实际应用中，需试探不同的c值和选择不同的初始聚类中心。此外，HCM算法的聚类结果还会受到样本的几何性质和读入次序的影响。如果样本分布呈现每类是团状的，那么该算法能得到很好的聚类结果。由于HCM算法实现简单，通常能得到较为令人满意的聚类结果，故应用范围比较广泛。

下面介绍初始聚类中心的一些选取方法：

(1)随机选取样本集的c个样本作为初始聚类中心。

(2)将样本集随机分成c类，计算每类中心，将这些中心作为初始聚类中心。(3)凭经验选择初始聚类中心。根据问题的性质和数据分布，选择从直观上看来较合理的c个初始聚类中心。

(4)按密度大小选择初始聚类中心。求以该中心为球心、以R为半径的球形区域内的样本个数，这个数值称为该点的密度。把所有样本点按照密度大小排序，首先选取密度最大的样本点作为第一个初始聚类中心，然后在与第一个初始聚类中心大于某个距离ξ(ξ为预先设定的一个正数)的那些样本点中选取最大密度的样本点作为第二个初始聚类中心。如此类推，得到c个样本作为初始聚类中心。

(5)将相距最远的c个样本作为初始聚类中心。例6.2试用HCM算法对如图6.6所示的样本集进行聚类，聚类数目c=2。

解在下面的步骤中，括号中的数字表示处理步骤号(与HCM算法的步骤一致)，括号右上角的撇号的数目表示迭代的次数。

(1)随机选取两个样本点作为聚类中心，这里选择，。

(2)按照最小距离原那么，对其他样本进行归类；图6.6样本集以此类推，得到

(3)计算新的聚类中心；(4)因为，故转至(2)。

(2)′由新的聚类中心，得；

因此得到

(3)′计算聚类中心；(4)′因为，2)，故转至(2)。

(2)″求得分类结果与前一次的结果相同，

。

(3)″因此聚类中心也与前一次的结果相同，

。

因为，不再会出现新的类别划分，故分类过程结束。6.5.2ISODATA算法

迭代自组织数据分析算法(ISODATA)是目前应用比较广泛的一种聚类算法。与HCM算法类似，ISODATA算法的聚类中心也是通过样本均值的迭代运算来决定的。该算法的优势在于，在每次迭代过程中，样本重新调整类别之后计算类内及类间的有关参数，并和设定的阈值比较，判断是将两类合并为一类还是将一类分裂为两类，不断的“自组织〞以到达在各参数满足设计要求的条件下，使各样本到其类中心的距离平方和最小。

设样本集为样本集X={x1，x2，…，xn}，ISODATA算法的具体步骤如下：(1)设置算法的初始参数：

c为预期的聚类中心数目；

r为初始聚类中心的数目(不一定等于c)；

θn表示每个聚类中最少的样本数目，假设少于此数就不能作为一个独立的聚类；

θs是一个聚类中样本标准差的最大值，用来控制分裂；

θD是两个聚类中心之间距离的最小值，用于控制合并；

L为每次迭代中允许合并的最多对数；

T为最大的迭代次数。(2)选择初始聚类中心，可从样本集X中选择r个样本作为初始聚类中心vi，i=1，2，…，r。

(3)根据最小距离准那么将样本集X中每一个样本划分到某一聚类中，即如果，j=1，2，…，n，那么xj∈ωl。

(4)依据θn判断聚类是否合并。如果ωi(i=1，2，…，r)中的样本数目ni<θn，那么取消聚类ωi，r=r－1，转入步骤(3)。

(5)将各类的样本均值作为各类的聚类中心：，i=1，2，…，r(6-47)(6)计算各类样本到其聚类中心的平均距离：

(7)计算各个样本到其类内中心的总体平均距离：

(8)根据当前的迭代次数Tp和聚类中心数目r判断停止、分裂或合并：

①如果当前的迭代次数Tp已到达最大迭代次数T，那么置θD=0，转入步骤(12)；否那么转入下一步。，i=1，2，…，r(6-48)(6-49)

②如果，那么转入步骤(9)，将已有

的聚类分裂；否那么转入下一步。

③如果r≥2c，那么不进行分裂处理，转入步骤(12)；否那么转入下一步。

④如果，那么当迭代次数Tp是奇数时,转入步骤(9)进行分裂处理；当迭代次数Tp是偶数时,转入步骤(12)进行合并处理。

(步骤(9)~(11)为分裂处理)(9)计算各个聚类类内样本的标准差σi=(σ1i，

σ2i，…，σdi)T，i=1，2，…，r，其中，σi的第k个分量为

其中，k为分量编号，i为类的编号，d为样本的维数，xkj是样本xj的第k个分量，vki是第i个聚类中心vi的第k个分量。

(10)求出每个聚类的类内样本标准差σi中的最大分量σimax，即，i=1，2，…，r。k=1，2，…，d；i=1，2，…，r(6-50)(11)在{σimax，i=1，2，…，r}中，如果σimax>θs，同时又满足以下两个条件之一：

①和ni>2(θn+1);

②,

那么将聚类ωi分裂为两个聚类，取消原来的聚类中心vi并令r=r+1，新的聚类中心和的计算方法如下：在vi中对应于σimax的分量加上(减去)Kσimax，其他分量不变，其中0<K≤1。分裂后，Tp=Tp+1，转入步骤(3)，否那么转入下一步。(步骤(12)~(14)为合并处理)

(12)计算各个聚类中心之间的距离：Dst=ρ(vs，vt)，s=1，2，…，r－1，t=s+1，…，r。

(13)依据θD判断是否进行合并处理。比较Dst与θD，将小于θD的那些Dst按递增顺序排列，并取前L个，即。

(14)从最小的Dst开始，将相应的两个类合并。如果

原来的两个聚类中心为vs和vt，那么合并后的新聚类中心为

并令r=r－L。(6-51)

(15)如果迭代次数Tp已到达最大的迭代次数T，那么算法结束。否那么，Tp=Tp+1，如果需要改变输入参数，转入步骤(1)；否那么，转入步骤(3)。

需要指出，ISODATA算法是以样本与聚类中心的最小距离作为样本聚类的依据，因此比较适合于各类样本在特征空间中以超球体分布的数据，对于分布形状较复杂的数据那么需要采用别的度量方法。例6.3一个样本集如图6.7所示，试用ISODATA算法对其进行聚类分析。

解从图中展示的样本可知，样本数n=8，预期的聚类数目c=2，执行ISODATA算法：

(1)给定参数(可以通过迭代过程修正这些参数)：r=1，θn=2，θs=1，θD=4，L=1，T=4。

(2)预选x1为聚类中心，即v1=x1=(0，0)T。令迭代次数Tp=1。

(3)因为只有一个聚合中心v1=(0，0)T，故ω1={x1，x2，…，x8}，n1=8。

(4)因为n1>θn，所以不进行合并。图6.7样本集(5)计算新的聚类中心：

(6)计算类内平均距离：

(7)计算全部样本到