第二章 聚 类 分 析 2·4 聚类的算法
2.4.1 聚类的技术方案
⑴ 简单聚类
根据相似性阈值和最小距离原则聚类 xi∈={ x1,x2,„,xn} = 12„c；
if D(xi,mj)≤T, mj=(1/nj)xi(j)，xi(j) ∈j，nj是j中的样本个数，T是给定的阀值。
Then xi∈i
类心一旦确定将不会改变。
⑵ 谱系或层次聚类
按最小距离原则不断进行两类合并
类心不断地修正，但模式类别一旦指定后就不再改变。
⑶ 依据准则函数动态聚类
影响聚类结果的主要因数：类心、类别个数、模式输入顺序。 所谓动态聚类，是指上述因数在聚类过程中是可变的。
规定一些分类的目标参数，定义一个能刻划聚类过程或结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。这类方法有—均值法、ISODATA法、近邻函数法以及运用图论理论的最小张树法。 2.4.2 简单聚类方法
㈠ 根据相似性阈值和最小距离原则的简单聚类方法 ⒈ 条件及约定 设待分类的模式为⒉ 算法思想
计算模式特征矢量到聚类中心的距离并和门限比较而决定归属该类或作
，选定类内距离门限。
为新的一类中心。通常选择欧氏距离。
⒊ 算法原理步骤
⑴
取任意的一个模式特征矢量作为第一个聚类中心。例如，令第一类中心
。
到
的距离。
，计算尚未确定类别的模式特征矢量，
如果
，则
到各
。若
，
则建立新的一类
的
⑵ 计算下一个模式特征矢量，其中心
；若
，则
⑶ 假设已有聚类中心聚类中心类
的中心，
的距离
作为新的一
；否则，如果
( 2-4-1)
则指判返到⑶。
⒋ 性能
。检查是否所有的模式都分划完类别，如都分划完了则结束；否则
计算简单。
聚类结果很大程度上依赖于距离
门限的选取、待分类特征矢量参与分
类的次序和聚类中心的选取。
当有特征矢量分布的先验知识来指导门限及初始中心得较合理结果。
⒌ 改进
通常采用试探法，选用不同的门限及模式输入次序来试分类，并对聚类结果进行检验,即用聚类准则函数J1。例如，计算每一聚类中心与该类中最远样本点的距离，或计算类内及类间方差，用这些结果指导及案的划分结果进行比较，选取最好的一种聚类结果。
的重选。最后对各种方
的选取时，可以获
图 (2-4-1) 距离阈值及初始类心对聚类的影响
㈡ 最大最小距离算法 ⒈ 条件及约定
设待分类的模式特征矢量集为⒉ 基本思想
在模式特征矢量集中以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。这种方法通常也使用欧氏距离。
⒊ 算法原理步骤
⑴ 选任一模式特征矢量作为第一个聚类中心⑵ 从待分类矢量集中选距离如图( 2-4-2)中
最大，取
。例如，
。
。例
，选定比例系数。
最远的特征矢量作为第二个聚类中心
。
与
、
⑶
计算未被作为聚类中心的各模式特征矢量出它们之中的最小值，即
之间的距离并求
( 2-4-2)
为表述简洁，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全部列写出来，因这并不影响算法的正确性。
⑷ 若
( 2-4-3)
则相应的特征矢量作为第三个聚类中心，。此例中。然后转至⑸；
否则，转至最后一步⑹。
⑸
设存在个聚类中心，计算未被作为聚类中心的各特征矢量到各聚类中心的距离
,并算出
如果
，则
( 2-4-4)
并转至⑸；否则，转至最后一步⑹。
按最
⑹
当判断出不再有新的聚类中心之后，将模式特征矢量小距离原则分到各类中去，即计算
当
；
，则判
。在此例中，，
。
，
( 2-4-5) ；
，
这种算法的聚类结果与参数以及第一个聚类中心的选取有关。如果没有先
的选取，可适当调整和
，比较多次试探分类结果，选取最
验知识指导和
合理的一种聚类。
图 (2-4-2) 最大最小距离算法举例
2.4.3 谱系聚类法(Hierarchical Clustering Method)(系统聚类法、层次聚类法）
效果较好、是常用方法之一。
⒈ 条件及约定
设待分类的模式特征矢量为
⒉ 基本思想
首先将
个模式视作各自成为一类，然后计算类与类之间的距离，选择距
，
表示第k次合并时的第类。
离最小的一对合并成一个新类，计算在新产生的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。
⒊ 算法步骤
⑴ 初始分类。令⑵ 计算各类间的距离
，每个模式自成一类，即，生成一个对称的距离矩阵
。 ，为类
的个数。
⑶ 找出前一步求得的矩阵将
和
中的最小元素，设它是
和，令
间的距离，
。
两类合并成一类，于是产生新的聚类
大于2，令
⑷ 检查类的个数。如果类数，转至⑵；否则，停止。
如果某一循环中具有最小类间距离不止一个类对，则对应这些最小距离的类可以同时合并。上述算法步骤给出了从
停止条件
以类间距离
门限
作为停止条件，即取距离门限
，当
大于时，聚类过程停止；
以预定的类别数目作为停止条件，当类别合并过程中，类数等于预定值
时，聚类过程停止。 类间距离的定义与递推
在该算法中可以采用上节已详细介绍过的不同的类间距离定义方式，并使用类间距离递推公式。所采用的类间距离定义不同，聚类过程及结果是不一样的。
类至类的完整聚类过程，
中最小阵元
上述算法在归并的每次迭代过程中，距离矩阵的最小元素值不断地改变，如果有单调不减关系则称类间距离对并类具有单调性。最近距离法、最远距离法、平均法及离差平方和法等定义的类间距离都具有这个性质，而重心法没有这个性质。
算法特点
聚类过程中类心不断地调整，但某一模式一旦分划到某一类中就不再改变。 从粗到细的层次聚类
这类技术的另一个算法和上述算法过程相反，依据类的离差平方和递推公式按类至
类进行谱系分解，这里不作介绍了。聚类过程可以表示成一个树图。
例：给出个样本特征矢量如下，按最小距离原则进行聚类。
解：
⑴ 将每一样本看成自成一类
计算距离矩阵
⑵
(表 2-4-1)。
它是
与
之间的距离，将它们合并为一类，
中最小阵元为
得一新的分类为
计算合并后的距离矩阵
与
⑶
分类
中距离最小者为
(表 2-4-2)。在这里使用了距离递推公式，如
与
距离
它是
与
间的距离，合并
和
，得新的
距离，
同样计算
(表 2-4-3)，进一步聚类得
即 计算
(表 2-4-4)。
、
和 可以一起合并成一类。
表(2-4-2)
⑷ 由表可知， 表(2-4-1) 表(2-4-3) 表(2-4-4)
2.4.4 动态聚类法(Dynamic clustering algorithm)
最大距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之后，在后继的算法过程中就不改变了，而简单聚类算法中类心一旦选定后在后继算法过程中也不再改变了，这类方法效果一般不会太理想。和上述各算法相对应有一种动态聚类法。其要点为：
⑴ 确定模式和聚类的距离测度。当采用欧氏距离时，是计算此模式和该类中
心的欧氏距离；为能反映出类的模式分布结构，应采用马氏距离，设该类的均矢为，协方差阵为，则模式和该类的距离平方为与该类均矢的马氏距离
⑵ 确定评估聚类质量的准则函数。 ⑶ 确定模式分划及聚类合并或分裂的规则。
动态聚类算法的基本步骤：
⑴ 建立初始聚类中心，进行初始聚类； ⑵ 计算模式和类的距离，调整模式的类别；
⑶ 计算各聚类的参数，删除、合并或分裂一些聚类；
⑷ 从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心使准
则函数取得极值或设定的参数达到设计要求时停止。 动态聚类原理框图如下：
图 (2-4-3)
㈠ —均值法(—means) ⒈ 条件及约定
设待分类的模式特征矢量集为
⒉ 基本思想
，类的数目是取定的。
取定c个类别和选取个初始聚类中心，按最小距离原则将各模式分配到类中的某一类，不断地计算类心和调整各模式的类别使每个模式特征矢量到其所属类别的距离平方之和最小
⒊ 算法步骤
⑴ 任选个模式特征矢量作为初始聚类中心：⑵
将待分类的模式特征矢量集类中的某一类，即
如果
( 2-4-6) 则判
式中
聚类
表示
和
。
的中心。
的距离，上角标表示迭代次数。于是产生新的
。
中的模式逐个按最小距离原则分划给
⑶ 计算重新分类后的各类心
( 2-4-7) 式中
为
类中所含模式的个数。
因为这一步采取平均的方法计算调整后类的中心，且定为类，故称一均值法。 ⑷ 如果⒋ 分析
我们以欧氏距离为例，简单地分析该算法的可收敛性。在上述算法中，虽然没有直接运用准则函数
(
)，则转至⑵；如果
，则结束。
进行分类，但在⑵中根据式(2-4-6)进行模式分划可使从聚类
。设为
、
移至聚类和、
中，
移出
后的集合记为和
，聚类
，
、
( 2-4-8)
趋于变小。设某样本移入
、
和
后的集合记为的均矢分别
所含样本数分别为和
，显然有
( 2-4-9)
而这两个新的聚类的类内欧氏距离(平方)距离(平方)
和
的关系是
和
( 2-4-10)
与原来的两个聚类的类内欧氏
( 2-4-11)
当距
比距
更近时，使得
( 2-4-12)
由式(2-4-11)、(2-4-12)及(2-4-13)
可知，将
分划给
( 2-4-13)
类可使变小。这说
明在分类问题中不断地计算新分划的各类的类心，并按最小距离原则归类可使值减至极小值。在上述算法中，也可以利用式(2-4-13)进行模式类别的重新分划。
⒌ 性能
算法简单，收敛（已于1974年和1967年分别给出了严格证明）。
如模式分布呈现类内团聚状，该算法是能达到很好聚类结果的，故应用较多。
能使各模式到其所判属类别中心距离(平方)之和为最小的最佳聚类。
以确定的类数、模式输入次序及选定的初始聚类中心为前提，受此限制结果只是局部最优。
⒍ 改进 ⑴ 的调整
作一条一曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。 在类别数未知的情况下，可使类数由较小值逐步增加，对于每个选定的分
别使用该算法。显然准则函数是随的增加而单调减少。在增加过程中，总会出现使本来较密集的类再拆开的情况，此时J虽减小，但减小速度将变缓。如果作一条一曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。然而在许多情况下，曲线并无明显的这样的点。另一种方法是利用问题的先验知识分析选取合理的聚类数。 ⑵ 初始聚类中心选取
初始聚类中心可按以下几种方法之一选取：
① 凭经验选择初始类心。
② 将模式随机地分成类，计算每类中心，以其作为初始类心。
为半径的球形域
③ （最大密度），求以每个特征点为球心、某一正数
中特征点个数，这个数称为该点的密度。选取密度最大的特征点作为第一个初始类心
，然后在与
大于某个距离的那些特征点中选取具有“最大”
，如此进行，选取个初始聚类中心。
密度的特征点作为第二个初始类心
④ 用相距最远的个特征点作为初始类心。具体地讲，是按前述的最大
最小距离算法求取个初始聚类中心。
⑤
当
较大时，先随机地从个模式中取出一部分模式用谱系聚类法
聚成类，以每类的重心作为初始类心。
⑥
设已标准化的待分类模式集为令模式
，定义
，希望将它们分为类。
且令
计算
( 2-4-14)
( 2-4-15) ( 2-4-16)
显然
，若
最接近整数
，则把
分划至
( 2-4-17)
中。对所有样本都实
行上述处理，就可实现初始分类，从而产生初始聚类中心。
⑶ 用类核代替类心
前面的算法存在一个不足，即是只用一个聚类中心点作为一类的代表，但是一个点往往不能充分地反映该类的模式分布结构，从而损失很多有用的信息。当类的分布是球状或近似球状时，算法尚能有较好的效果，但对于如图(2-4-4)所示的那种各分量方差不等的正态分布而两类的主轴和类心又是那样的情况，分类
效果就不好了，则被指判到
点应属于
类，但由于它距
类的均矢更近，按前述的算法
类。如果已知各类模式分布的某些知识，则可以利用它们指导聚
表示类
的模式分布情况，其
可以是一个函数、
类。为此，我们定义一个类核函数
中
关于类
的一个参数集，是维空间中的特征矢量，
一个点集或其他适当的模型。为了刻划待识模式
和一个模式特征矢量到核离的一种简化。
类的接近程度还应规定
的距离。实际上，马氏距离就是核函数距
当已知某类的分布近似为正态分布时，可以用以这类样本统计估计值为参数的正态分布函数作为核函数，即
( 2-4-18)
其中
式中
， ，
为进行参数估计的该类样本数。则模式与该类的距离为
( 2-4-19)
这实际上是第四章将要讨论的最小误判概率准则下先验概率相同时的判决函数。
当已知各类样本分别在相应的主轴附近分布时，可以定义主轴核函数：
( 2-4-20) 式中，
是由和
类的统计协方差阵
的
个最大特
给出的部分
征值所对应的已规格化的特征矢量作成的矩阵，即
主轴系统，映出来)。为
是协方差阵
给出了样本分布的主轴方向(散布的情况由特征值反
轴上的单位矢量。设
是
类样本的均值矢量，求一点和一类间的距离平方可以用和该类的主
个轴的距离可见图( 2-4-5)。模式和轴间的欧氏距离平方来度量。
( 2-4-21)
(a) 各分量方差不等的正态分布
图 (2-4-4) 类的模式分布情况的示例
(b) 沿主轴分布
图 (2-4-5) 求和主轴距离示意图
例：模式分布如图(2-4-6)所示，试用一均值法进行聚类，取=2。
⑴ 选
⑵ 因
„„
，
；
，
，故
，故
，故
得
⑶ 计算新的聚类中心
，故转至⑵。
⑷ 因
⑵' 由新的聚类中心，得
故得
，
⑶' 计算聚类中心
，
⑷'
因
，故转至⑵。
因
⑵
求得的分类结果与前一次的结果相同，⑶
各聚类中心必然也与前一次的相同，
。 。
，不再出现新的类别划分，故分类过程结束。
㈡ 改进的—均值法
文献【10】基于核函数的概念提出了一种改进的—均值法，其分类性能要好于通常计算模式到类的距离时采用这个模式到类心的欧氏距离或马氏距离的—均值法。
由于—均值法我们已作详细介绍，这种改进的—均值法只简单表述如下：
⑴ 对给定的待分类模式集⑵ 计算各聚类⑶ 将各模式
进行初始分划产生类；
、均值矢量
和协方差阵
；
所含模式数
按最小距离原则分划到某一聚类中。这里采用最小误判概
的距离
率准则下正态分布情况的判决规则，计算模式到
如果
则判
( 2-4-22)
⑷ 如果没有模式改变其类别，则停止算法；否则转至⑵。
（三） ISODATA(迭代自组织数据分析)算法
(Iterative Self-Organizing Data Analysis Techniques Algorithm) 特点：具有启发性推理、分析监督、控制聚类结构及人机交互。
⒈ 条件及约定
设待分类的模式特征矢量为⒉ 算法思想
在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地“自组织”，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。
⒊ 算法原理步骤
，算法运行前需设定7个初始参数。
⑴ 预置
① 设定聚类分析控制参数：
=预期的类数，
=初始聚类中心个数(可以不等于)，
=每一类中允许的最少模式数目(若少于此数就不能单独成为一类)，
=类内各分量分布的距离标准差上界(大于此数就分裂)，
=两类中心间的最小距离下界(若小于此数，这两类应合并)，
=在每次迭代中可以合并的类的最多对数，
=允许的最多迭代次数。 ② 将待分类的模式特征矢量
读入。
中任选
个
③ 选定初始聚类中心，可从待分类的模式特征矢量集
模式特征矢量作为初始聚类中心
⑵ 按最小距离原则将模式集
如果
则判
式中
表示
和类
的中心
之间的距离。
中样本数
。
中每个模式分到某一类中，即
( 2-4-23)
⑶
依据
判断合并。如果类
，转至⑵(
或计算
，则取消该类的中心
，将
，
并入距
离最近的那一类中；这时，转至⑵。
⑷ 计算分类后的参数:各类中心、类内平均距离及总体平均距离。
① 计算各类的中心
( 2-4-24)
② 计算各类中模式到类心的平均距离
( 2-4-25)
③ 计算各个模式到其类内中心的总体平均距离
⑸ 依据
、
判断停止、分裂或合并。
已达，则置
( 2-4-26)
① 若迭代次数转到⑼；否则转下。
② 若③ 若
则转到⑹(将一些类分裂)；否则转下。 ,(则跳过分裂处理)转至⑼,否则转下。
④ 若
数
，当迭代次数是奇数时转至⑹(分裂处理)；迭代次
是偶数时转至⑼(合并处理)。
⑹ 计算各类类内距离的标准差矢量
其各分量
( 2-4-27)
( 2-4-28)
式中，为分量编号，为类的编号，为矢量维数，是
的第个分量。
⑺ 对每一聚类，求出类内距离标准差矢量
⑻
在
中，对任一
，若有
中的最大分量
是
的第个分量，
( 2-4-29)
，同时又满足下面两个条件
之一：
①
②
和
则将该类
样构成的：
分裂为两个聚类，且令和
只是在
中相应于，
的选取应使
和
距离较远，而原
。这两个新类的中心的分量分别加上和减去和
仍在
和是这，而其
它分量不变，其中
类
裂后，
的模式到
的类域空间中且其它
类中的模式和它们距离较小。分
，转至⑵；否则，转下。
⑼ 计算各对聚类中心间的距离
⑽
依据
判断合并。将
与
比较，并将小于
。从最小的
和
的那些
( 2-4-30) 按递增次序
排列，取前
个，
合并。若原来的两个类心为
开始，将相应的两类
，则合并后的聚类中心为
( 2-4-31)
（已并掉的类数）。在一次迭代中，某一类最多只能被合并一次。 ⑾ 如果迭代次数
已达次或过程收敛，则结束。否则，
，若需
要调整参数，则转至⑴；若不改变参数，则转至⑵。
我们将该算法的合并和分裂的条件归纳如下： 合并的条件： (类内样本数分裂的条件：
)(类的数目
)(两类间中心距离
)。
(类的数目)(类的某分量标准差)
。
这里，
表示“或”的关系；
表示“与”的关系。如果类的数目
有
，当是奇数时分裂，当是偶数时合并。
由上述合并与分裂的判断条件可以看出算法初设的7个参数存在一定的相互制约。
例 ：用ISODATA方法聚类图(2-4-7)中的数据 解：在本例中
，
。
⑴ 设定参数和初始值
在无先验知识的情况下，可任意选取这些参数和初始值，然后在逐次迭代中加以调整。
⑵ 因只有一个聚类中心，故
，
⑶ 因
，无合并。
⑷ 计算聚类中心、类内平均距离和总的平均距离。 ① 计算聚类中心
② 计算类内平均距离
③ 计算总的平均距离
⑸ 因不是最后一步迭代，且⑹ 求
的标准差矢量
，转至⑹
⑺ 算得
⑻
因
则
且
将
分裂成两类，取，
，转至⑵
⑵' 按最小距离原则，新划分的类是
⑶' 因
，无合并。
⑷' 计算类的中心、类内平均距离和总的平均距离
① ② ③
⑸' 因这是偶次迭代，满足算法原理步骤⑸中④的条件，故转⑼
⑼' 计算类间距离
由
，类不能合并。 ⑾' 因不是最后一次迭代
(
，题设
)
，
，判断是否修
改参数。由上面结果可知，已获得所要求类别数目，类间距离大于类内距离，每类样本数都有样本总数的足够大的百分比，因此不改变参数。 ⑵
和
的标准差矢量
⑺
⑻
，
，分裂条件不满足，转至⑼。
⑼
与前一次迭代结果相同， ⑽
，无新的变化，
，转至⑵。
⑵
⑽
，同前。 ，无合并发生。
，转至⑼。
⑾
实际上，根据第三次迭代发现计算结果不变时，就可以结束算法。
图 (2-4-7) ISODATA算法例题中的模式集
第二章 聚 类 分 析 2·4 聚类的算法
2.4.1 聚类的技术方案
⑴ 简单聚类
根据相似性阈值和最小距离原则聚类 xi∈={ x1,x2,„,xn} = 12„c；
if D(xi,mj)≤T, mj=(1/nj)xi(j)，xi(j) ∈j，nj是j中的样本个数，T是给定的阀值。
Then xi∈i
类心一旦确定将不会改变。
⑵ 谱系或层次聚类
按最小距离原则不断进行两类合并
类心不断地修正，但模式类别一旦指定后就不再改变。
⑶ 依据准则函数动态聚类
影响聚类结果的主要因数：类心、类别个数、模式输入顺序。 所谓动态聚类，是指上述因数在聚类过程中是可变的。
规定一些分类的目标参数，定义一个能刻划聚类过程或结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。这类方法有—均值法、ISODATA法、近邻函数法以及运用图论理论的最小张树法。 2.4.2 简单聚类方法
㈠ 根据相似性阈值和最小距离原则的简单聚类方法 ⒈ 条件及约定 设待分类的模式为⒉ 算法思想
计算模式特征矢量到聚类中心的距离并和门限比较而决定归属该类或作
，选定类内距离门限。
为新的一类中心。通常选择欧氏距离。
⒊ 算法原理步骤
⑴
取任意的一个模式特征矢量作为第一个聚类中心。例如，令第一类中心
。
到
的距离。
，计算尚未确定类别的模式特征矢量，
如果
，则
到各
。若
，
则建立新的一类
的
⑵ 计算下一个模式特征矢量，其中心
；若
，则
⑶ 假设已有聚类中心聚类中心类
的中心，
的距离
作为新的一
；否则，如果
( 2-4-1)
则指判返到⑶。
⒋ 性能
。检查是否所有的模式都分划完类别，如都分划完了则结束；否则
计算简单。
聚类结果很大程度上依赖于距离
门限的选取、待分类特征矢量参与分
类的次序和聚类中心的选取。
当有特征矢量分布的先验知识来指导门限及初始中心得较合理结果。
⒌ 改进
通常采用试探法，选用不同的门限及模式输入次序来试分类，并对聚类结果进行检验,即用聚类准则函数J1。例如，计算每一聚类中心与该类中最远样本点的距离，或计算类内及类间方差，用这些结果指导及案的划分结果进行比较，选取最好的一种聚类结果。
的重选。最后对各种方
的选取时，可以获
图 (2-4-1) 距离阈值及初始类心对聚类的影响
㈡ 最大最小距离算法 ⒈ 条件及约定
设待分类的模式特征矢量集为⒉ 基本思想
在模式特征矢量集中以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。这种方法通常也使用欧氏距离。
⒊ 算法原理步骤
⑴ 选任一模式特征矢量作为第一个聚类中心⑵ 从待分类矢量集中选距离如图( 2-4-2)中
最大，取
。例如，
。
。例
，选定比例系数。
最远的特征矢量作为第二个聚类中心
。
与
、
⑶
计算未被作为聚类中心的各模式特征矢量出它们之中的最小值，即
之间的距离并求
( 2-4-2)
为表述简洁，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全部列写出来，因这并不影响算法的正确性。
⑷ 若
( 2-4-3)
则相应的特征矢量作为第三个聚类中心，。此例中。然后转至⑸；
否则，转至最后一步⑹。
⑸
设存在个聚类中心，计算未被作为聚类中心的各特征矢量到各聚类中心的距离
,并算出
如果
，则
( 2-4-4)
并转至⑸；否则，转至最后一步⑹。
按最
⑹
当判断出不再有新的聚类中心之后，将模式特征矢量小距离原则分到各类中去，即计算
当
；
，则判
。在此例中，，
。
，
( 2-4-5) ；
，
这种算法的聚类结果与参数以及第一个聚类中心的选取有关。如果没有先
的选取，可适当调整和
，比较多次试探分类结果，选取最
验知识指导和
合理的一种聚类。
图 (2-4-2) 最大最小距离算法举例
2.4.3 谱系聚类法(Hierarchical Clustering Method)(系统聚类法、层次聚类法）
效果较好、是常用方法之一。
⒈ 条件及约定
设待分类的模式特征矢量为
⒉ 基本思想
首先将
个模式视作各自成为一类，然后计算类与类之间的距离，选择距
，
表示第k次合并时的第类。
离最小的一对合并成一个新类，计算在新产生的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。
⒊ 算法步骤
⑴ 初始分类。令⑵ 计算各类间的距离
，每个模式自成一类，即，生成一个对称的距离矩阵
。 ，为类
的个数。
⑶ 找出前一步求得的矩阵将
和
中的最小元素，设它是
和，令
间的距离，
。
两类合并成一类，于是产生新的聚类
大于2，令
⑷ 检查类的个数。如果类数，转至⑵；否则，停止。
如果某一循环中具有最小类间距离不止一个类对，则对应这些最小距离的类可以同时合并。上述算法步骤给出了从
停止条件
以类间距离
门限
作为停止条件，即取距离门限
，当
大于时，聚类过程停止；
以预定的类别数目作为停止条件，当类别合并过程中，类数等于预定值
时，聚类过程停止。 类间距离的定义与递推
在该算法中可以采用上节已详细介绍过的不同的类间距离定义方式，并使用类间距离递推公式。所采用的类间距离定义不同，聚类过程及结果是不一样的。
类至类的完整聚类过程，
中最小阵元
上述算法在归并的每次迭代过程中，距离矩阵的最小元素值不断地改变，如果有单调不减关系则称类间距离对并类具有单调性。最近距离法、最远距离法、平均法及离差平方和法等定义的类间距离都具有这个性质，而重心法没有这个性质。
算法特点
聚类过程中类心不断地调整，但某一模式一旦分划到某一类中就不再改变。 从粗到细的层次聚类
这类技术的另一个算法和上述算法过程相反，依据类的离差平方和递推公式按类至
类进行谱系分解，这里不作介绍了。聚类过程可以表示成一个树图。
例：给出个样本特征矢量如下，按最小距离原则进行聚类。
解：
⑴ 将每一样本看成自成一类
计算距离矩阵
⑵
(表 2-4-1)。
它是
与
之间的距离，将它们合并为一类，
中最小阵元为
得一新的分类为
计算合并后的距离矩阵
与
⑶
分类
中距离最小者为
(表 2-4-2)。在这里使用了距离递推公式，如
与
距离
它是
与
间的距离，合并
和
，得新的
距离，
同样计算
(表 2-4-3)，进一步聚类得
即 计算
(表 2-4-4)。
、
和 可以一起合并成一类。
表(2-4-2)
⑷ 由表可知， 表(2-4-1) 表(2-4-3) 表(2-4-4)
2.4.4 动态聚类法(Dynamic clustering algorithm)
最大距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之后，在后继的算法过程中就不改变了，而简单聚类算法中类心一旦选定后在后继算法过程中也不再改变了，这类方法效果一般不会太理想。和上述各算法相对应有一种动态聚类法。其要点为：
⑴ 确定模式和聚类的距离测度。当采用欧氏距离时，是计算此模式和该类中
心的欧氏距离；为能反映出类的模式分布结构，应采用马氏距离，设该类的均矢为，协方差阵为，则模式和该类的距离平方为与该类均矢的马氏距离
⑵ 确定评估聚类质量的准则函数。 ⑶ 确定模式分划及聚类合并或分裂的规则。
动态聚类算法的基本步骤：
⑴ 建立初始聚类中心，进行初始聚类； ⑵ 计算模式和类的距离，调整模式的类别；
⑶ 计算各聚类的参数，删除、合并或分裂一些聚类；
⑷ 从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心使准
则函数取得极值或设定的参数达到设计要求时停止。 动态聚类原理框图如下：
图 (2-4-3)
㈠ —均值法(—means) ⒈ 条件及约定
设待分类的模式特征矢量集为
⒉ 基本思想
，类的数目是取定的。
取定c个类别和选取个初始聚类中心，按最小距离原则将各模式分配到类中的某一类，不断地计算类心和调整各模式的类别使每个模式特征矢量到其所属类别的距离平方之和最小
⒊ 算法步骤
⑴ 任选个模式特征矢量作为初始聚类中心：⑵
将待分类的模式特征矢量集类中的某一类，即
如果
( 2-4-6) 则判
式中
聚类
表示
和
。
的中心。
的距离，上角标表示迭代次数。于是产生新的
。
中的模式逐个按最小距离原则分划给
⑶ 计算重新分类后的各类心
( 2-4-7) 式中
为
类中所含模式的个数。
因为这一步采取平均的方法计算调整后类的中心，且定为类，故称一均值法。 ⑷ 如果⒋ 分析
我们以欧氏距离为例，简单地分析该算法的可收敛性。在上述算法中，虽然没有直接运用准则函数
(
)，则转至⑵；如果
，则结束。
进行分类，但在⑵中根据式(2-4-6)进行模式分划可使从聚类
。设为
、
移至聚类和、
中，
移出
后的集合记为和
，聚类
，
、
( 2-4-8)
趋于变小。设某样本移入
、
和
后的集合记为的均矢分别
所含样本数分别为和
，显然有
( 2-4-9)
而这两个新的聚类的类内欧氏距离(平方)距离(平方)
和
的关系是
和
( 2-4-10)
与原来的两个聚类的类内欧氏
( 2-4-11)
当距
比距
更近时，使得
( 2-4-12)
由式(2-4-11)、(2-4-12)及(2-4-13)
可知，将
分划给
( 2-4-13)
类可使变小。这说
明在分类问题中不断地计算新分划的各类的类心，并按最小距离原则归类可使值减至极小值。在上述算法中，也可以利用式(2-4-13)进行模式类别的重新分划。
⒌ 性能
算法简单，收敛（已于1974年和1967年分别给出了严格证明）。
如模式分布呈现类内团聚状，该算法是能达到很好聚类结果的，故应用较多。
能使各模式到其所判属类别中心距离(平方)之和为最小的最佳聚类。
以确定的类数、模式输入次序及选定的初始聚类中心为前提，受此限制结果只是局部最优。
⒍ 改进 ⑴ 的调整
作一条一曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。 在类别数未知的情况下，可使类数由较小值逐步增加，对于每个选定的分
别使用该算法。显然准则函数是随的增加而单调减少。在增加过程中，总会出现使本来较密集的类再拆开的情况，此时J虽减小，但减小速度将变缓。如果作一条一曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。然而在许多情况下，曲线并无明显的这样的点。另一种方法是利用问题的先验知识分析选取合理的聚类数。 ⑵ 初始聚类中心选取
初始聚类中心可按以下几种方法之一选取：
① 凭经验选择初始类心。
② 将模式随机地分成类，计算每类中心，以其作为初始类心。
为半径的球形域
③ （最大密度），求以每个特征点为球心、某一正数
中特征点个数，这个数称为该点的密度。选取密度最大的特征点作为第一个初始类心
，然后在与
大于某个距离的那些特征点中选取具有“最大”
，如此进行，选取个初始聚类中心。
密度的特征点作为第二个初始类心
④ 用相距最远的个特征点作为初始类心。具体地讲，是按前述的最大
最小距离算法求取个初始聚类中心。
⑤
当
较大时，先随机地从个模式中取出一部分模式用谱系聚类法
聚成类，以每类的重心作为初始类心。
⑥
设已标准化的待分类模式集为令模式
，定义
，希望将它们分为类。
且令
计算
( 2-4-14)
( 2-4-15) ( 2-4-16)
显然
，若
最接近整数
，则把
分划至
( 2-4-17)
中。对所有样本都实
行上述处理，就可实现初始分类，从而产生初始聚类中心。
⑶ 用类核代替类心
前面的算法存在一个不足，即是只用一个聚类中心点作为一类的代表，但是一个点往往不能充分地反映该类的模式分布结构，从而损失很多有用的信息。当类的分布是球状或近似球状时，算法尚能有较好的效果，但对于如图(2-4-4)所示的那种各分量方差不等的正态分布而两类的主轴和类心又是那样的情况，分类
效果就不好了，则被指判到
点应属于
类，但由于它距
类的均矢更近，按前述的算法
类。如果已知各类模式分布的某些知识，则可以利用它们指导聚
表示类
的模式分布情况，其
可以是一个函数、
类。为此，我们定义一个类核函数
中
关于类
的一个参数集，是维空间中的特征矢量，
一个点集或其他适当的模型。为了刻划待识模式
和一个模式特征矢量到核离的一种简化。
类的接近程度还应规定
的距离。实际上，马氏距离就是核函数距
当已知某类的分布近似为正态分布时，可以用以这类样本统计估计值为参数的正态分布函数作为核函数，即
( 2-4-18)
其中
式中
， ，
为进行参数估计的该类样本数。则模式与该类的距离为
( 2-4-19)
这实际上是第四章将要讨论的最小误判概率准则下先验概率相同时的判决函数。
当已知各类样本分别在相应的主轴附近分布时，可以定义主轴核函数：
( 2-4-20) 式中，
是由和
类的统计协方差阵
的
个最大特
给出的部分
征值所对应的已规格化的特征矢量作成的矩阵，即
主轴系统，映出来)。为
是协方差阵
给出了样本分布的主轴方向(散布的情况由特征值反
轴上的单位矢量。设
是
类样本的均值矢量，求一点和一类间的距离平方可以用和该类的主
个轴的距离可见图( 2-4-5)。模式和轴间的欧氏距离平方来度量。
( 2-4-21)
(a) 各分量方差不等的正态分布
图 (2-4-4) 类的模式分布情况的示例
(b) 沿主轴分布
图 (2-4-5) 求和主轴距离示意图
例：模式分布如图(2-4-6)所示，试用一均值法进行聚类，取=2。
⑴ 选
⑵ 因
„„
，
；
，
，故
，故
，故
得
⑶ 计算新的聚类中心
，故转至⑵。
⑷ 因
⑵' 由新的聚类中心，得
故得
，
⑶' 计算聚类中心
，
⑷'
因
，故转至⑵。
因
⑵
求得的分类结果与前一次的结果相同，⑶
各聚类中心必然也与前一次的相同，
。 。
，不再出现新的类别划分，故分类过程结束。
㈡ 改进的—均值法
文献【10】基于核函数的概念提出了一种改进的—均值法，其分类性能要好于通常计算模式到类的距离时采用这个模式到类心的欧氏距离或马氏距离的—均值法。
由于—均值法我们已作详细介绍，这种改进的—均值法只简单表述如下：
⑴ 对给定的待分类模式集⑵ 计算各聚类⑶ 将各模式
进行初始分划产生类；
、均值矢量
和协方差阵
；
所含模式数
按最小距离原则分划到某一聚类中。这里采用最小误判概
的距离
率准则下正态分布情况的判决规则，计算模式到
如果
则判
( 2-4-22)
⑷ 如果没有模式改变其类别，则停止算法；否则转至⑵。
（三） ISODATA(迭代自组织数据分析)算法
(Iterative Self-Organizing Data Analysis Techniques Algorithm) 特点：具有启发性推理、分析监督、控制聚类结构及人机交互。
⒈ 条件及约定
设待分类的模式特征矢量为⒉ 算法思想
在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地“自组织”，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。
⒊ 算法原理步骤
，算法运行前需设定7个初始参数。
⑴ 预置
① 设定聚类分析控制参数：
=预期的类数，
=初始聚类中心个数(可以不等于)，
=每一类中允许的最少模式数目(若少于此数就不能单独成为一类)，
=类内各分量分布的距离标准差上界(大于此数就分裂)，
=两类中心间的最小距离下界(若小于此数，这两类应合并)，
=在每次迭代中可以合并的类的最多对数，
=允许的最多迭代次数。 ② 将待分类的模式特征矢量
读入。
中任选
个
③ 选定初始聚类中心，可从待分类的模式特征矢量集
模式特征矢量作为初始聚类中心
⑵ 按最小距离原则将模式集
如果
则判
式中
表示
和类
的中心
之间的距离。
中样本数
。
中每个模式分到某一类中，即
( 2-4-23)
⑶
依据
判断合并。如果类
，转至⑵(
或计算
，则取消该类的中心
，将
，
并入距
离最近的那一类中；这时，转至⑵。
⑷ 计算分类后的参数:各类中心、类内平均距离及总体平均距离。
① 计算各类的中心
( 2-4-24)
② 计算各类中模式到类心的平均距离
( 2-4-25)
③ 计算各个模式到其类内中心的总体平均距离
⑸ 依据
、
判断停止、分裂或合并。
已达，则置
( 2-4-26)
① 若迭代次数转到⑼；否则转下。
② 若③ 若
则转到⑹(将一些类分裂)；否则转下。 ,(则跳过分裂处理)转至⑼,否则转下。
④ 若
数
，当迭代次数是奇数时转至⑹(分裂处理)；迭代次
是偶数时转至⑼(合并处理)。
⑹ 计算各类类内距离的标准差矢量
其各分量
( 2-4-27)
( 2-4-28)
式中，为分量编号，为类的编号，为矢量维数，是
的第个分量。
⑺ 对每一聚类，求出类内距离标准差矢量
⑻
在
中，对任一
，若有
中的最大分量
是
的第个分量，
( 2-4-29)
，同时又满足下面两个条件
之一：
①
②
和
则将该类
样构成的：
分裂为两个聚类，且令和
只是在
中相应于，
的选取应使
和
距离较远，而原
。这两个新类的中心的分量分别加上和减去和
仍在
和是这，而其
它分量不变，其中
类
裂后，
的模式到
的类域空间中且其它
类中的模式和它们距离较小。分
，转至⑵；否则，转下。
⑼ 计算各对聚类中心间的距离
⑽
依据
判断合并。将
与
比较，并将小于
。从最小的
和
的那些
( 2-4-30) 按递增次序
排列，取前
个，
合并。若原来的两个类心为
开始，将相应的两类
，则合并后的聚类中心为
( 2-4-31)
（已并掉的类数）。在一次迭代中，某一类最多只能被合并一次。 ⑾ 如果迭代次数
已达次或过程收敛，则结束。否则，
，若需
要调整参数，则转至⑴；若不改变参数，则转至⑵。
我们将该算法的合并和分裂的条件归纳如下： 合并的条件： (类内样本数分裂的条件：
)(类的数目
)(两类间中心距离
)。
(类的数目)(类的某分量标准差)
。
这里，
表示“或”的关系；
表示“与”的关系。如果类的数目
有
，当是奇数时分裂，当是偶数时合并。
由上述合并与分裂的判断条件可以看出算法初设的7个参数存在一定的相互制约。
例 ：用ISODATA方法聚类图(2-4-7)中的数据 解：在本例中
，
。
⑴ 设定参数和初始值
在无先验知识的情况下，可任意选取这些参数和初始值，然后在逐次迭代中加以调整。
⑵ 因只有一个聚类中心，故
，
⑶ 因
，无合并。
⑷ 计算聚类中心、类内平均距离和总的平均距离。 ① 计算聚类中心
② 计算类内平均距离
③ 计算总的平均距离
⑸ 因不是最后一步迭代，且⑹ 求
的标准差矢量
，转至⑹
⑺ 算得
⑻
因
则
且
将
分裂成两类，取，
，转至⑵
⑵' 按最小距离原则，新划分的类是
⑶' 因
，无合并。
⑷' 计算类的中心、类内平均距离和总的平均距离
① ② ③
⑸' 因这是偶次迭代，满足算法原理步骤⑸中④的条件，故转⑼
⑼' 计算类间距离
由
，类不能合并。 ⑾' 因不是最后一次迭代
(
，题设
)
，
，判断是否修
改参数。由上面结果可知，已获得所要求类别数目，类间距离大于类内距离，每类样本数都有样本总数的足够大的百分比，因此不改变参数。 ⑵
和
的标准差矢量
⑺
⑻
，
，分裂条件不满足，转至⑼。
⑼
与前一次迭代结果相同， ⑽
，无新的变化，
，转至⑵。
⑵
⑽
，同前。 ，无合并发生。
，转至⑼。
⑾
实际上，根据第三次迭代发现计算结果不变时，就可以结束算法。
图 (2-4-7) ISODATA算法例题中的模式集