武汉理工大学：《模式识别》课程授课教案（讲义）第5章 聚类分析

第5章聚类分析俗话说“物以类聚，人以群分”，这句话实际上就反映了聚类分析的基本思想。一般来说，数据集根据其客观属性可分为若干个自然类，每个自然类中的数据的一些属性都具有较强的相似性。聚类分析是基于这种思想而建立的一种数据描述方法。在第2草里为了获取判别模型的参数，需要由带有类别标签的数据组成训练样本集，但在实际应用中，常常会遇到因条件限制无法得到训练样本集，只是要求对已获取的大量未知类别数据，根据这些数据中的特性进行分类。在模式识别系统中，我们称这种算法为聚类算法。聚类算法把特征彼此相似的归入同一类，而把特性不相似的数据分到不同的类中，而且在分类中不需要用训练样本进行学习，所以也称为无监督分类。5.1模式相似性测度在贝叶斯判决中，为了求得后验概率，需要已知先验概率和类条件概率。由于条件概率通常也未知，就需要用训练样本去对概率密度进行估计。在实际应用中，这一过程往往非常困难。聚类分析避免了估计类概率密度的困难，每个聚类中心都是局部密度极大值位置，越靠近聚合中心，密度越高，越远离聚合中心，密度越小。聚类算法把特征相似性的样本聚集为一个类别，在特征空间里占据着一个局部区域。每个局部区域都形成一个聚类中心，聚类中心代表相应类别。图5-1中是具有相同的平均值和协方差矩阵的数据集，无论采用参数估计，还是非参数估计，都无法取得合理的结果，而采用聚类分析，从图中可以直观看出（a）具有一个类别，（b）、（c）各有两个类别：:.(b)(c)(a)图5-1有相同的平均值和协方差矩阵的数据集特征选择是聚类分析的关键因素，选取不同的特征，聚类的结果可能不同。图5-2中，（a）为样本集，根据样本的面积大小可分成三类，如图（b）：根据外形特征也分成三类，如图（c）：根据线型则分成二类如图（d）。可以想象，属于不同类别的样本，他们之间必然会有某些特征显著不同。如果在聚类分析中，没能把不同类的样本区分开来，可能是因为特征选择的不当，没有选取标志类别显著差别的特征，这时应当重新选择特征。特征选择不当不仅可能会使聚类性能下降，甚至会使聚类完全无效。特征较少可能会使特征向量包含的分类信息太少，特征太多又会使特征之间产生信息穴余，都会直接影响到聚类的结果。因此特征选择也成了聚类分析中最困难的环节之一。关于特征选择的方法，我们将在第8章进行详细介绍。1

1 第 5 章 聚类分析 俗话说“ 物以类聚，人以群分”，这句话实际上就反映了聚类分析的基本思想。一般来说，数据集根 据其客观属性可分为若干个自然类，每个自然类中的数据的一些属性都具有较强的相似性。聚类分析是基 于这种思想而建立的一种数据描述方法。在第2章里为了获取判别模型的参数，需要由带有类别标签的数据 组成训练样本集，但在实际应用中，常常会遇到因条件限制无法得到训练样本集，只是要求对已获取的大 量未知类别数据，根据这些数据中的特性进行分类。在模式识别系统中，我们称这种算法为聚类算法。聚 类算法把特征彼此相似的归入同一类，而把特性不相似的数据分到不同的类中，而且在分类中不需要用训 练样本进行学习，所以也称为无监督分类。 5.1 模式相似性测度 在贝叶斯判决中，为了求得后验概率，需要已知先验概率和类条件概率。由于条件概率通常也未知， 就需要用训练样本去对概率密度进行估计。在实际应用中，这一过程往往非常困难。聚类分析避免了估计 类概率密度的困难，每个聚类中心都是局部密度极大值位置，越靠近聚合中心，密度越高，越远离聚合中 心，密度越小。聚类算法把特征相似性的样本聚集为一个类别，在特征空间里占据着一个局部区域。每个 局部区域都形成一个聚类中心，聚类中心代表相应类别。图5-1中是具有相同的平均值和协方差矩阵的数据 集，无论采用参数估计，还是非参数估计，都无法取得合理的结果，而采用聚类分析，从图中可以直观看 出 (a)具有一个类别，(b)、(c)各有两个类别。 （a） (b) (c) 图5-1 有相同的平均值和协方差矩阵的数据集 特征选择是聚类分析的关键因素，选取不同的特征，聚类的结果可能不同。图5-2中，（a）为样本集， 根据样本的面积大小可分成三类，如图（b）；根据外形特征也分成三类，如图（c）;根据线型则分成二类， 如图(d)。可以想象，属于不同类别的样本，他们之间必然会有某些特征显著不同。如果在聚类分析中，没 能把不同类的样本区分开来，可能是因为特征选择的不当，没有选取标志类别显著差别的特征，这时应当 重新选择特征。特征选择不当不仅可能会使聚类性能下降，甚至会使聚类完全无效。特征较少可能会使特 征向量包含的分类信息太少，特征太多又会使特征之间产生信息冗余，都会直接影响到聚类的结果。因此， 特征选择也成了聚类分析中最困难的环节之一。关于特征选择的方法，我们将在第8章进行详细介绍

ODOAAOADOAO△?OADAAoA0A0OADOA（a）混合训练样本集（b）根据面积分成三类（c）根据外形分成三类（d）根据线型分成两类图5-2聚类分析的结果与特征的选取有很大的关系实际应用中，对已知样本集X=X,X.…,X}，是按某种相似性把X分类，衡量样本相似性的方法对聚类结果同样也有很大的影响。为了能区分样本的类别，首先需要定义模式相似性的测度。5.1.1.距离测度一个样本模式被表示成特征向量，则对应于特征空间的一个点。当样本特征选择恰当，也即同类样本特征相似，不同类样本的特征显著不同时，同类样本就会聚集在一个区域，不同类样本相对远离。显然，样本点在特征空间距离的距离远近直接反映了相应样本所属类别，可以作为样本相似性度量。距离越近，相似性越大，属于同一类的可能性就越大：距离越远，相似性越小，属于同一类的可能性就越小。聚类分析中，最常用的就是距离相似性测度。实际应用中，有各种各样距离的定义，下面我们给出距离定义应满足的条件。设已知3个样本，他们分别为：X,=（xa,2xm）、X=(x*2xm）和X，=（xk2,Xm）。其中，n为特征空间的维数，矢量X,和X,的距离以及X,和X，的距离分别记为d(X,,X)和d(X,,X），对任意两失量的距离定义应满足下面的公理：1）d(XX)≥0，当且仅当X=X,时，等号成立；2) d(X,X,)=d(X,,X);3) d(X,X,)≤d(X,,X)+d(X,X)。需要指出，模式识别中定义的某些距离测度不满足第3个条件，只是在广义意义上称之为距离。下面给出距离测度的几种具体算式。（1）欧氏距离(5-1)d,(X,X)=IX -X, I=1Zxik-xi1Nk=l根据d(X,X，)的定义，通过选择合适的门限d，，可以判决X,和X，是否为同一类别。当d.(X,X)小于门限d时，表示X，和X，属于同一类别，反之，则属于不同类别。这里门限d，的选取非常关键，若d，选择过大，则全部样本被归为同一类别；若d，选取过小，则可能造成每个样本都单独构成一个类别。必须正确选择门限值以保证正确分类。实际应用中还需注意以下两点：2

2 （a） 混合训练样本集 （b）根据面积分成三类 （c）根据外形分成三类 （d）根据线型分成两类 图5-2 聚类分析的结果与特征的选取有很大的关系 实际应用中，对已知样本集 1 2 { , ,., } X X X X  n ，是按某种相似性把 X 分类，衡量样本相似性的方 法对聚类结果同样也有很大的影响。为了能区分样本的类别，首先需要定义模式相似性的测度。 5.1.1.距离测度 一个样本模式被表示成特征向量，则对应于特征空间的一个点。当样本特征选择恰当，也即同类样本特 征相似，不同类样本的特征显著不同时，同类样本就会聚集在一个区域，不同类样本相对远离。显然，样 本点在特征空间距离的距离远近直接反映了相应样本所属类别，可以作为样本相似性度量。距离越近，相 似性越大，属于同一类的可能性就越大；距离越远，相似性越小，属于同一类的可能性就越小。聚类分析 中，最常用的就是距离相似性测度。实际应用中，有各种各样距离的定义，下面我们给出距离定义应满足 的条件。 设已知3个样本，他们分别为： 1, 2 ( , , )T X x x x i i i in  、 1, 2 ( , , )T X x x x j j j jn  和 1, 2 ( , , )T X x x x k k k kn  。其中， n为特征空间的维数，矢量 Xi 和 X j 的距离以及 Xi 和 Xk 的距离分别记为 ( , ) i j d X X 和 ( , ) i k d X X ，对任意两矢量的距离定义应满足下面的公理： 1) ( , ) 0 i j d X X  ，当且仅当 X X i j  时，等号成立； 2) ( , ) ( , ) i j j i d X X d X X  ； 3) ( , ) ( , ) ( , ) i j j k i k d X X d X X d X X   。 需要指出，模式识别中定义的某些距离测度不满足第3个条件，只是在广义意义上称之为距离。下面 给出距离测度的几种具体算式。 （1）欧氏距离 2 1 ( , ) || || | | n e i j i j ik jk k d X X X X x x       （5-1） 根据 1 2 ( , ) e d X X 的定义，通过选择合适的门限 s d ，可以判决 X1 和 X2 是否为同一类别。当 1 2 ( , ) e d X X 小于门限 s d 时，表示 X1 和 X2 属于同一类别，反之，则属于不同类别。这里门限 s d 的选取非常关键，若 s d 选择过大，则全部样本被归为同一类别；若 s d 选取过小，则可能造成每个样本都单独构成一个类别。 必须正确选择门限值以保证正确分类。实际应用中还需注意以下两点：

1）模式特征向量的构成。一种物理量对应一种量纲，而一种量纲一般有不同的单位制式，每种单位制式下又有不同的单位，简单地说就是一种物理量对应着一个具体的单位。对于各特征向量，对应的维度上应当是相同的物理量，并且要注意物理量的单位。通常特征向量中的每一维所表示的物理意义不尽相同，如x表示周长，x，表示面积等。如果某些维度上的物理量采用的单位发生变化，就可能会导致相同样本集出现不同的聚类结果。例如图5-3中，4个二维向量a、b、c和d，向量的两个分量x，x,均表示长度，当x,，x,的单位发生不同的变化时，会出现不同的聚类结果。图5-3(b)中a,b为一类，c.d为另一类，图5-3(c)中a,c为一类，b,d为另一类。由此可见，坐标轴的简单缩放就能引起样本点的重新聚类。2）实际应用中，可以采用特征数据标准化方法，对原始特征进行预处理，使其与变量的单位无关。此时所描述的点是一种相对的位置关系，只要样本点间的相对位置关系不变，就不会影响聚类结果。例如，对图5-3（b）和（c）中的数据标准化后，四个点的相对位置关系总是和图5-3（a）相同。同样地，如果对原始特征不满意，感觉所有维度上的特征上都太大或太小，也可以采用类似的处理方法。需要指出的是，并不是所有的标准化都是合理的。如果数据散布恰恰是由于类别差异引起的，标准化反而会引起错误的聚类结果。因此，在聚类之前是否应进行标准化处理，建立在对数据各维度物理量充分研判的基础上。, (mm), (mm)I-dro.3.d(4,5) (cm)c(1,4)c(0.1,4)ALa(0,1)(1,0.4)0(4,0.5)b(530)a(0,1)b(5,0)1bxp.s,0),+x (mm)23x(cm)1-3235x, (mm)a(0,0.1)(a)(b)(c)图5-3特征量纲对聚类结果的影响(2）绝对值距离（街坊距离或Manhattan距离）7d(X,X)=(5-2)k=12,....nXik-Xik=l(3）切氏(Chebyshev)距离d(X,X,)=max|xi -xxlk=1,2...n(5-3)(4）明氏(Minkowski)距离，元>0(5-4)d,(X.,X)=k=l2,.,nXa>x.tk=l它是若干距离函数的通式：入=2时，等于欧氏距离；元=1时，称为“街坊”（cityblock）距离。(5）马氏(Mahalanobis)距离设n维矢量X和X，是矢量集X，X，，，X中的两个量，它们的马氏距离定义为d(X,X)=(X, -X)Z-(X, -X)(5-5)2-1E1、式中：=Z(X,-μ)(X,-μ), μ=-FN-1E3

3 1）模式特征向量的构成。一种物理量对应一种量纲，而一种量纲一般有不同的单位制式，每种单位制 式下又有不同的单位，简单地说就是一种物理量对应着一个具体的单位。对于各特征向量，对应的维度上 应当是相同的物理量，并且要注意物理量的单位。 通常特征向量中的每一维所表示的物理意义不尽相同，如 1 x 表示周长， 2 x 表示面积等。如果某些维度 上的物理量采用的单位发生变化，就可能会导致相同样本集出现不同的聚类结果。例如图5-3中，4个二维向 量a、b、c 和 d，向量的两个分量 1 x ， 2 x 均表示长度，当 1 x ， 2 x 的单位发生不同的变化时，会出现不同的 聚类结果。图5-3(b)中 ab, 为一类， cd, 为另一类，图5-3(c) 中 ac, 为一类， bd, 为另一类。由此可见，坐 标轴的简单缩放就能引起样本点的重新聚类。 2）实际应用中，可以采用特征数据标准化方法，对原始特征进行预处理，使其与变量的单位无关。此 时所描述的点是一种相对的位置关系，只要样本点间的相对位置关系不变，就不会影响聚类结果。例如， 对图5-3（b）和(c)中的数据标准化后，四个点的相对位置关系总是和图5-3(a)相同。同样地，如果对原始 特征不满意，感觉所有维度上的特征上都太大或太小，也可以采用类似的处理方法。 需要指出的是，并不 是所有的标准化都是合理的。如果数据散布恰恰是由于类别差异引起的，标准化反而会引起错误的聚类结 果。因此，在聚类之前是否应进行标准化处理，建立在对数据各维度物理量充分研判的基础上。 b(5,0) d(4,5) c(1,4) 1 a(0,1) 2 3 4 5 0 1 2 3 4 5 (a) (mm) 1 x (mm) 2 x d(0.4,5) c(0.1,4) a(0,1) 1 2 3 4 5 0 1 2 3 b(0.5,0) (b) (mm) 2 x (cm) 1x b(5,0) c(1,0.4) d(4,0.5) a(0,0.1) 1 2 3 0 1 2 3 4 5 (cm) 2 x (mm) 1 x (c) 图5-3 特征量纲对聚类结果的影响 ⑵ 绝对值距离(街坊距离或Manhattan距离) 1 ( , ) 1,2,., n i j ik jk k d X X x x k n      (5-2） ⑶ 切氏(Chebyshev)距离 ( , ) max 1,2,., i j ik jk k d X X x x   k  n (5-3） ⑷ 明氏(Minkowski)距离 1 1 ( , ) | | n i j ik jk k d X X x x              ，  0 k n 1, 2,., (5-4） 它是若干距离函数的通式：   2 时，等于欧氏距离；  1 时，称为“街坊”（city block）距离。 ⑸ 马氏(Mahalanobis)距离 设n维矢量 Xi 和 X j 是矢量集 X X X 1 2 , , , N  中的两个矢量，它们的马氏距离定义为 1 2 ( , ) ( ) ( ) T i j i j i j d X X X X X X      （5-5） 式中: 1 1 ( )( ) 1 N T i i i X X N          ， 1 1 N i i X N    

容易证明，马氏距离对一切非奇异线性变换都是不变的。即具有坐标系比例、旋转、平移不变性，并且从统计意义上尽量去掉了分量间的相关性。这说明它不受特征量纲选择的影响，另外，由手之的含义是这个量集的协方差阵的统计量，所以马氏距离对特征的相关性也作了考虑。当为单位矩阵时，马氏距离和欧氏距离是等价的。(6）Camberra距离（Lance距离、Willims距离）d(X,X,)=之α-xxl(XX≥0,Xk+X0)(5-6)k=x+x该距离能克服量纲引起的问题，但不能克服分量间的相关性。5.1.2相似测度与距离测度不同，相似测度考虑两矢量的方向是否相近，矢量长度并不重要。如果两样本点在特征空间的方向越接近，则两样点划归为同一类别的可能性越大。下面给出相似测度的几种定义。(1）角度相似系数（夹角余弦）样本X，与X，之间的角度相似性度量定义为它们之间夹角的余弦，也是单位向量之间的点积（内积）即：X,x,S(X,X,)=cos =(5-7)IIx, II-II , IIIS(,X，S(X,,X)越大，X,与X,越相似，当X,=X,时，S(X,X)达到最大值。因矢量长度已规格化，S(X，X）对于坐标系的旋转及放大、缩小是不变的，但对位移和一般性的线性变换不具有不变性。当X与X，的各特征为（O,1)二元取值时，SX，X）的意义如下：①若模式样本的第i维特征取值为1，则该样本占有第i维特征。②若模式样本的第i维特征取值为0，则该样本无此维特征。此时，X，X表示X，与X，两个样本中共有的特征数目。SX,X）反映X，与X，共有的特征数目的相似性度量。S(X.,X）越大，共有特征数目越多，相似性越高。对S(X,X）稍加变化，可得到Tanimoto度量。(2）相关系数它实际上是数据中心化后的失量夹角余弦。(X -μx)(Y-μy)r(X,Y)=(5-8)[(X -μx)"(X - μx)(Y -μ)"(Y -μ)"2其中，X=（x,xz，",x），Y=(y,y2",y）分别为两个数据集的样本，x和u分别是这两个数据集的平均矢量。相关系数对于坐标系的平移、旋转和尺度缩放具有不变性。（3）指数相似系数已知样本X,=(XaX2,Xm）、X,=(xnj2,Xm），其指数相似系数定义为3(x-x)!Zexpl-e(X,,X )= -(5-9)40kn式中为相应分量的协方差，n为矢量维数。(4)其它相似测度当样本X,=(xz2,",xm）、X,=(xj2,"x）各特征值非负时，还可定义下列相似系数4

4 容易证明，马氏距离对一切非奇异线性变换都是不变的。即具有坐标系比例、旋转、平移不变性，并 且从统计意义上尽量去掉了分量间的相关性。这说明它不受特征量纲选择的影响，另外，由于  的含义是 这个矢量集的协方差阵的统计量，所以马氏距离对特征的相关性也作了考虑。 当  为单位矩阵时，马氏 距离和欧氏距离是等价的。 ⑹ Camberra距离(Lance距离、Willims距离) 1 ( , ) , ( , 0, 0) | | n ik jk i j ik jk ik jk k ik jk x x d X X x x x x  x x        (5-6) 该距离能克服量纲引起的问题，但不能克服分量间的相关性。 5.1.2 相似测度 与距离测度不同，相似测度考虑两矢量的方向是否相近，矢量长度并不重要。如果两样本点在特征空 间的方向越接近，则两样点划归为同一类别的可能性越大。下面给出相似测度的几种定义。 (1) 角度相似系数(夹角余弦） 样本 Xi 与 X j 之间的角度相似性度量定义为它们之间夹角的余弦，也是单位向量之间的点积（内积） 即： ( , ) cos || || || || T i j i j i j X X S X X X X     (5-7) | ( , ) | 1 i j S X X  ， ( , ) i j S X X 越大， Xi 与 X j 越相似，当 X X i j  时， ( , ) i j S X X 达到最大值。因矢量 长度已规格化， ( , ) i j S X X 对于坐标系的旋转及放大、缩小是不变的，但对位移和一般性的线性变换不具有 不变性。当 Xi 与 X j 的各特征为(0,1)二元取值时， ( , ) i j S X X 的意义如下：① 若模式样本的第 i 维特征取 值为 1，则该样本占有第 i 维特征。② 若模式样本的第 i 维特征取值为 0，则该样本无此维特征。此时， T X Xi j 表示 Xi 与 X j 两个样本中共有的特征数目。 ( , ) i j S X X 反映 Xi 与 X j 共有的特征数目的相似性度量。 ( , ) i j S X X 越大，共有特征数目越多，相似性越高。对 ( , ) i j S X X 稍加变化，可得到 Tanimoto 度量。 (2) 相关系数 它实际上是数据中心化后的矢量夹角余弦。 1/2 ( ) ( ) ( , ) [( ) ( )( ) ( )] T X Y T T X X Y Y X Y r X Y X X Y Y              (5-8) 其中， 1 2 ( , , , ) X x x x  n ， 1 2 ( , , , ) Y y y y  n 分别为两个数据集的样本，  X 和 Y 分别是这两个数 据集的平均矢量。相关系数对于坐标系的平移、旋转和尺度缩放具有不变性。 (3) 指数相似系数 已知样本 1, 2 ( , , ) X x x x i i i in  、 1, 2 ( , , ) X x x x j j j jn  ，其指数相似系数定义为 2 1 1 3( ) ( , ) exp[ ] 4 n ik jk i j k k x x e X X n       (5-9) 式中 2  k 为相应分量的协方差, n 为矢量维数。 (4) 其它相似测度 当样本 1, 2 ( , , ) X x x x i i i in  、 1, 2 ( , , ) X x x x j j j jn  各特征值非负时，还可定义下列相似系数

min(xi,xk)S(X,,X,)=(5-10)Emax(xi,Xk)kEmin(xuxx)S(X,X ):(5-11)22(+)Zmin(xik,Xk)S(X,X )=(5-12)ZJ**k4上述相似性系数，均可做为样本相似测度，当两个样本X,与X,越相似，S(X,X）的值越大，当X与X,相等时，其值为1.5.1.3匹配测度当X与X，的各特征为(0,1)二元取值时，我们称之为二值特征。对于给定的二值特征矢量X,=(X1，Xi2，,Xm）和X,=(X,X2,,Xm），根据它们两个相应分量x与X的取值，可定义如下四种匹配关系：若x=1和x=1，则称x与x是(1-1)匹配；若Xik=1和x=0，则称与X是(1-0)匹配；若送=0和X=1，则称x与X是(0-1)匹配：若x=0和X=0，则称x与Xx是(0-0)匹配。令a=Exy,b=Ey(I-x, c=Ex(1-y) e=E(1-x,)(1-y)则αa、b、C、e分别表示X,与X,的(1-1)、(0-1)、(1-0)和(0-0)的匹配特征数目。对于二值n维特征矢量可定义如下相似性测度：(1)Tanimoto测度xIx,a(5-13)S(X,X, +a+b+cxx,+X'x,-xix可以看出，S(X,Y)等于X和Y共同具有的特征数目与X和Y分别具有的特征种类总数之比。这里只考虑（1-1）匹配而不考虑（0-0)匹配。(2)Rao测度X,x,a(5-14)S,(X Y +a+b+c+en上式等于（1-1)匹配特征数目和所选用的特征数目之比。(3)简单匹配系数a+e(5-15)m(X,X, +n这时匹配系数分子为(1-1)匹配特征数目与(0-0)匹配特征数目之和，分母为所考虑的特征数目。5

5 min( , ) ( , ) max( , ) ik jk k i j ik jk k x x S X X x x    (5-10) min( , ) ( , ) 1 ( ) 2 ik jk k i j ik jk k x x S X X x x     (5-11) min( , ) ( , ) ik jk k i j ik jk k x x S X X x x    (5-12) 上述相似性系数，均可做为样本相似测度，当两个样本 Xi 与 X j 越相似， ( , ) i j S X X 的值越大，当 Xi 与 X j 相等时，其值为 1. 5.1.3 匹配测度 当 Xi 与 X j 的各特征为(0,1)二元取值时，我们称之为二值特征。对于给定的二值特征矢量 1 2 ( , , , ) X x x x i i i in  和 1 2 ( , , , ) X X X X j j j jn  ，根据它们两个相应分量 ik x 与 jk x 的取值， 可定义如下四 种匹配关系：若 1 ik x  和 1 jk x  ，则称 ik x 与 jk x 是(1-1)匹配；若 1 ik x  和 0 jk x  ，则称 ik x 与 jk x 是(1-0) 匹配；若 0 ik x  和 1 jk x  ，则称 ik x 与 jk x 是(0-1)匹配；若 0 ik x  和 0 jk x  ，则称 ik x 与 jk x 是(0-0)匹配。 令 i i i a x y   (1 ) i i i b y x    (1 ) i i i c x y    (1 )(1 ) i i i e x y     则 a 、b 、c 、 e 分别表示 Xi 与 X j 的(1-1)、(0-1)、(1-0)和(0-0)的匹配特征数目。对于二值 n 维特征矢量 可定义如下相似性测度： （1） Tanimoto 测度 ( , ) T i j t i j T T T i i j j i j a X X S X X a b c X X X X X X       （5-13） 可以看出， ( , ) t S X Y 等于 X 和 Y 共同具有的特征数目与 X 和 Y 分别具有的特征种类总数之比。 这里只考虑(1-1)匹配而不考虑(0-0)匹配。 （2） Rao 测度 ( , ) T i j r a X X S X Y a b c e n      （5-14） 上式等于(1-1)匹配特征数目和所选用的特征数目之比。 （3） 简单匹配系数 ( , ) i j a e m X X n   （5-15） 这时匹配系数分子为(1-1)匹配特征数目与(0-0)匹配特征数目之和，分母为所考虑的特征数目

(4)Dice系数X,IX,a(5-16)m(X,X,)=2a+b+cx,x,+X,x(5)Kulzinsky系数xIx,a(5-17)m(X,X):b+cXx,+X/x,-2x,x上式分子为(1-1)匹配特征数目，分母为(1-0)和(0-1)匹配特征数目之和，也即不匹配特征数目之和。上面从不同角度给出了许多样本相似性测度的定义，各种相似性测度有其特点和适用的条件，在实际使用时应根据具体问题进行选择。建立了模式相似性测度之后，两个样本的相似程度就可量化了，据此便可以进行聚类分析。5.2类间距离测度方法在有些聚类算法中要用到类间距离，下面给出一些类间距离定义方式。5.2.1最近距离法如H、K是两个聚类，则两类间的最短距离定义为DHk =min|D(XH,X))XHEH,XkEK式中，D（X，X）表示H类中的某个样本X.和K类中的某个样本X之间的欧氏距离：Dk表示H类中所有样本与K类中所有样本之间的最小距离。如图5-5（a）所示。DHKHHDH(a)(b)图5-5最短距离法图示如果K类由I和J两类合并而成，如图5-5（b）所示，则得到递推公式(5-18)DHk =min(DH,Du)5.2.2最长距离法与最短距离法类似，两个聚类H和K之间的最长距离定义为DHk=max(D(XH,X)) XeH,XxeK(5-19)若K类由I和J两类合并而成，则得到递推公式DHx =max(Dm,Du)(5-20)6

6 （4） Dice 系数 ( , ) 2 T i j i j T T i i j j a X X m X X a b c X X X X      （5-16） （5） Kulzinsky 系数 ( , ) 2 T i j i j T T T i i j j i j a X X m X X b c X X X X X X      （5-17） 上式分子为(1-1)匹配特征数目，分母为(1-0)和(0-1)匹配特征数目之和，也即不匹配特征数目之和。 上面从不同角度给出了许多样本相似性测度的定义，各种相似性测度有其特点和适用的条件，在实际 使用时应根据具体问题进行选择。建立了模式相似性测度之后，两个样本的相似程度就可量化了，据此便 可以进行聚类分析。 5.2 类间距离测度方法 在有些聚类算法中要用到类间距离，下面给出一些类间距离定义方式。 5.2.1 最近距离法 如 H 、 K 是两个聚类，则两类间的最短距离定义为 D D H K HK H K H K    min , ,   X X X X  式中，D X X H K ,  表示 H 类中的某个样本 X H 和 K 类中的某个样本 XK 之间的欧氏距离； DHK 表示 H 类 中所有样本与 K 类中所有样本之间的最小距离。如图5-5(a)所示。 H K I J DHI DHJ (a) (b) 图 5-5 最短距离法图示 如果 K 类由 I 和 J 两类合并而成，如图 5-5（b）所示，则得到递推公式 D D D HK HI HJ  min ,   （5-18） 5.2.2 最长距离法 与最短距离法类似，两个聚类 H 和 K 之间的最长距离定义为 D D H K HK H K H K    max , ,   X X X X  （5-19） 若 K 类由 I 和 J 两类合并而成，则得到递推公式 D D D HK HI HJ  max ,   （5-20） H K

5.2.3中间距离法中间距离法介于最长与最短的距离之间。若K类由I和J两类合并而成，则H和K类之间的距离为Di+Di-iDHK=,(5-21)V25.2.4重心距离法以上定义的类间距离中并未考虑每一类所包含的样本数目，重心法在这一方面有所改进。从物理的观点看，一个类的空间位置若要用一个点表示，那么用它的重心代表较合理。将每类中包含的样本数考虑进去。若I类中有n个样本，J类中有n，个样本，则类与类之间的距离递推式为ni-Dai+nnnDi.Dis-m(5-22)DHK=(n,+n,)2n,+n,n,+nj5.2.5平均距离法（类平均距离法）设H、K是两个聚类，则H类和K类间的距离定义为Dux=Zd,(5-23)ngnkiek式中，d是H类任一样本X和K类任一样本X之间的欧氏距离平方；nk和n分别表示H和K类中的样本数目。如果K类由I类和J类合并产生，则可以得到H和K类之间距离的递推式为"D+_"Da(5-24)DHk=Vn,+n,n,+n,定义类间距离的方法不同，会使分类结果不太一致。实际问题中常用几种不同的方法，比较其分类结果，从而选择一个比较切合实际的分类。5.3聚类准则函数样本相似性度量是聚类分析的基础，针对具体问题，选择适当的相似性度量是保证聚类效果的基础。但有了相似性度量还不够，还必须有适当的聚类准则函数，才能把真正把属手同一类的样本聚合成一个类别的子集，而把不同类的样本分离开来。因此，聚类准则函数对聚类质量也有重要影响。相似性度量是解决集合与集合的相似性问题：相似性准则是用来评价分类效果的好坏。如果聚类准则函数选得好，聚类质量就会高。同时，聚类准则函数还可以用来评价一种聚类结果的质量，如果聚类质量不满足要求，就要重复执行聚类过程，以优化结果。在重复优化中，可以改变相似性度量，也可以选用新的聚类准则。5.3.1误差平方和准则7

7 5.2.3 中间距离法 中间距离法介于最长与最短的距离之间。若 K 类由 I 和 J 两类合并而成，则 H 和 K 类之间的距离为 1 1 1 2 2 2 2 2 4 D D D D H K H I H J I J    （5-21） 5.2.4 重心距离法 以上定义的类间距离中并未考虑每一类所包含的样本数目，重心法在这一方面有所改进。从物理的观 点看，一个类的空间位置若要用一个点表示，那么用它的重心代表较合理。将每类中包含的样本数考虑进 去。若 I 类中有 I n 个样本， J 类中有 J n 个样本，则类与类之间的距离递推式为 2 2 2 2 ( ) I J I J H K H I H J I J I J I J I J n n n n D D D D n n n n n n       （5-22） 5.2.5 平均距离法(类平均距离法) 设 H 、 K 是两个聚类，则 H 类和 K 类间的距离定义为 1 2 H K i j H K i H j K D d n n     （5-23） 式中， 2 ij d 是 H 类任一样本 X H 和 K 类任一样本 XK 之间的欧氏距离平方； K n 和 H n 分别表示 H 和 K 类 中的样本数目。如果 K 类由 I 类和 J 类合并产生，则可以得到 H 和 K 类之间距离的递推式为 I 2 2 J H K H I H J I J I J n n D D D n n n n     （5-24） 定义类间距离的方法不同，会使分类结果不太一致。实际问题中常用几种不同的方法，比较其分类结 果，从而选择一个比较切合实际的分类。 5.3 聚类准则函数 样本相似性度量是聚类分析的基础，针对具体问题，选择适当的相似性度量是保证聚类效果的基础。 但有了相似性度量还不够，还必须有适当的聚类准则函数，才能把真正把属于同一类的样本聚合成一个类 别的子集，而把不同类的样本分离开来。因此，聚类准则函数对聚类质量也有重要影响。相似性度量是解 决集合与集合的相似性问题；相似性准则是用来评价分类效果的好坏。如果聚类准则函数选得好，聚类质 量就会高。同时，聚类准则函数还可以用来评价一种聚类结果的质量，如果聚类质量不满足要求，就要重 复执行聚类过程，以优化结果。在重复优化中，可以改变相似性度量，也可以选用新的聚类准则。 5.3.1 误差平方和准则

给定样本集（X,X,X%)依据某种相似性测度划分为c类の.2…)，定义误差平方和准则函数为J-2ZIX,-M,IPi=l X,EeZx,为属于o，集的样本的均值向量，n,为Q，中样本数目。式中：M=n, X,e0,J代表了分属于c个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。在此准则函数下，聚类的目标转化为使J取最小值，即聚类的结果应使全部样本与其相应模式均值之间的误差平方和最小。该准则适用于各类样本密集且数目相差不多，而不同类间的样本又明显分开的情况；当类别样本数相差较大，且类间距离又不足够大时，并不适宜采用该准则函数。因为可能会造成样本数较多类中的边缘处样本距离另一类的类心更近，从而产生错误的划分。X(b)(a)图5-7样本分布例如在图5-7所示，（a）图中类内误差平方和很小，类间距离很远。可得到最好的结果。（b）图中类长轴两端距离中心很远，J值较大，结果不易令人满意。在该准则下，有时可能把样本数目多的一类分拆为二，造成错误聚类。如图5-8所示の，中的某些样本被错分到の，中，因为这样分开，J值会更小。X2x00M0202M2M?xCx,(b)(a)图5-8正确分类与错误分类5.3.2加权平均平方距离和准则误差平方和准则只是考虑了各样本到判定类心的距离，并没有考虑样本周围空间其它样本对聚类的影响，当综合考虑这些因素，误差平方和准则可改进为加权平均平方距离和准则。加权平均平方距离和准则函数定义为8

8 给定样本集 X X X 1 2 , ,., N  依据某种相似性测度划分为 c 类    1 2 , ,., c ，定义误差平方和准则 函数为 2 1 i i c i i i X J       X M 式中： 1 i i i i ni X  M X   为属于 i 集的样本的均值向量， i n 为 i 中样本数目。 J 代表了分属于 c 个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。 在此准则函 数下，聚类的目标转化为使 J 取最小值，即聚类的结果应使全部样本与其相应模式均值之间的误差平方和 最小。该准则适用于各类样本密集且数目相差不多，而不同类间的样本又明显分开的情况；当类别样本数 相差较大，且类间距离又不足够大时，并不适宜采用该准则函数。因为可能会造成样本数较多类中的边缘 处样本距离另一类的类心更近，从而产生错误的划分。 （a） 2 x 1 x M1 1 M2 2 M3 3 O 1 x （b） 2 x 2 M2 M1 1 O 图 5-7 样本分布 例如在图 5-7 所示，（a）图中类内误差平方和很小，类间距离很远。可得到最好的结果。（b）图中 类长轴两端距离中心很远，J 值较大，结果不易令人满意。在该准则下，有时可能把样本数目多的一类分拆 为二，造成错误聚类。如图 5-8 所示 1 中的某些样本被错分到 2 中，因为这样分开，J 值会更小。 2 x （a） 2 M2 M1 1 1 O x 2 x （b） 2 M2 M1 1 1 O x 图 5-8 正确分类与错误分类 5.3.2 加权平均平方距离和准则 误差平方和准则只是考虑了各样本到判定类心的距离，并没有考虑样本周围空间其它样本对聚类的影 响，当综合考虑这些因素，误差平方和准则可改进为加权平均平方距离和准则。加权平均平方距离和准则 函数定义为

(5-25)其中2d?=7xik(5-26)n(n-1)rT.EXyEe,Zxi表示の类中任意两个不同样本距离平方和，由于の中包含样本的个数为n，因此共有eeXyeo“("-}）个组合，由此可见，7的含义是类内任意两样本的平均平方距离。n为样本总数，"n为の类的2n先验概率，因此J称为加权平均平方距离和准则。5.3.3类间距离和准则给定待分样本X,X,，X，将它们分成c类，定义の,类的样本均值向量M和总体样本均值向量M为M,=IZ x,(5-27)n, X,ee,14M =Zx(5-28)n=l则类间距离和准则定义为J=Z(M,-M)(M,-M)(5-29)-1聚类的目标是最大化式（5-29），J越大表示各类之间的可分离性越好，聚类效果越好。对于二分类问题，类间距离常用式（5-30）表示类间距离。J=(M,-M,)(M,-M,)(5-30)5.3.4散射矩阵给定待分样本{X,X2,…,X），将它们分成2)c类。定义类的散布矩阵为S, = Z(X,-M)(X,-M)(5-31)X,e0,定义总的类内散布矩阵为Sw=s(5-32)i=l定义类间散布矩阵为S =Zn(M,-M)(M,-M)(5-33)i=l定义总体散布矩阵为S, =Z(X,-M)(X -M)(5-34)i=l可以证明S,=Sw+Ss，聚类的目标是极大化S.和极小化Sw，即使不同类的样本尽可能分开，而同一类的样本尽可能聚集，由此可定义如下基于散射矩阵的4个聚类准则。J, =T,[Sw'S](5-35)J,=Sw'SB(5-36)9

9 2 1 c i i i n J d  n  （5-25） 其中   2 2 2 1 ik i ij i i ik ij x i i x d x x n n         （5-26） 2 ik i ij i ik ij x x x x       表示 i 类中任意两个不同样本距离平方和，由于 i 中包含样本的个数为 i n ，因此共有  1 2 i i n n  个组合，由此可见， 2 i d 的含义是类内任意两样本的平均平方距离。 n 为样本总数， i n n 为 i 类的 先验概率，因此 J 称为加权平均平方距离和准则。 5.3.3 类间距离和准则 给定待分样本 X X X 1 2 , , , N  ，将它们分成 c 类，定义 i 类的样本均值向量 Mi 和总体样本均值向量 M 为 1 i i i i i X M X n    (5-27) 1 1 N i i M X n    (5-28) 则类间距离和准则定义为     1 c T i i i J M M M M      (5-29) 聚类的目标是最大化式（5-29）， J 越大表示各类之间的可分离性越好，聚类效果越好。 对于二分类问题，类间距离常用式（5-30）表示类间距离。  1 2 1 2    T J M M M M    （5-30） 5.3.4 散射矩阵 给定待分样本 X X X 1 2 , , , N  ，将它们分成    1 2 , ,., c c 类。定义 i 类的散布矩阵为    i i T i i i i i X S X M X M      （5-31） 定义总的类内散布矩阵为 1 c W i i S S   (5-32) 定义类间散布矩阵为    1 c T B i i i i S n M M M M      (5-33) 定义总体散布矩阵为    1 N T T i i i S X M X M      (5-34) 可以证明 T W B S S S   ，聚类的目标是极大化 B S 和极小化 W S ，即使不同类的样本尽可能分开，而同一 类的样本尽可能聚集，由此可定义如下基于散射矩阵的 4 个聚类准则。 1 1 Tr W B J S S       (5-35) 1 2 W B J S S   (5-36)

J, =T,[Sw's.](5-37)J,=Sw'ST(5-38)聚类的目标是极大化J，（i=1,2,3,4），J,越大表示各类之间的可分离性越好，聚类质量越好。若待分样本特征向量的维数为d时，SS.则为d×d的对称矩阵，其对应的特征值为^（i=l,2,,d），易知J=24(5-39)1J,=a(5-40)i=lJ, =Z(1+)(5-41)1=J,=(1+2)(5-42)i=l因此，在实际运算中，只要求出SwS，的特征值，即可求得J，（i=1,2,3,4）。5.4基于距离值的聚类算法当确定了相似性测度和准则函数后，聚类的过程是依靠聚类算法来实现的。因此，聚类算法是一个试图识别数据集合聚类的特殊性质的学习过程。本节介绍两种简单的聚类分析方法，它是对某些关键性的元素进行试探性的选取，使某种聚类准则达到最优，又称为基于试探的聚类算法。5.4.1最近邻规则的聚类算法最近邻规则聚类分析问题描述为：假设已有混合样本集X(N)=X,X,，",X,，给定类内距离门限值T，将XN=X,X，"",X划分为の，の"，の个类别。最近邻规则聚类算法的基本思想是：计算样本的特征向量到聚类中心的距离，将该距离与门限阈值T比较，决定该样本属于哪一类别或作为新一类别的中心。按照最近邻原则进行聚类，算法步聚如下：①选取距离阈值T，并且任取一个样本作为第一个聚合中心Z，如：Z,=X,。②计算样本X，到Z,的距离D21：若D2I≤T，则X,EZ,，否则令X,为第二个聚合中心，即Z,=X,。设Z=X，计算X,到Z,和Z,的距离D3和D32，若D>T和D2>T，则建立第三个聚合中心Z。否则把X，归于最近邻的聚合中心。依此类推，直到把所有的n个样本都进行分类。③按照某种聚类准则考察聚类结果，若不满意，则重新选取距离阅值T和第一个聚合中心Z，，返回②，直到满意，算法结束。该算法的优点是简单，如果有样本分布的先验知识用于指导值和起始点的选取，则可较快得到合理结果。其缺点是聚类过程中类别的中心一经选定，在聚类过程将不再改变。同样，样本一经判定类别归属后也不再改变。因此，在样本分布一定时，该算法的结果在很大程度上取决于第一个聚合中心的选取和距离阅值的大小。对于高维的样本集来说，只有经过多次试探，并对聚类结果进行检验，才能选择最优的聚类结果。10

10 1 3 Tr W T J S S       (5-37) 1 4 W T J S S   (5-38) 聚类的目标是极大化 i J （ i 1,2,3,4 ）， i J 越大表示各类之间的可分离性越好，聚类质量越好。若 待分样本特征向量的维数为 d 时， 1 W B S S  则为 d d  的对称矩阵，其对应的特征值为 i （ i d 1,2, , ）， 易知 1 1 d i i J     (5-39) 2 1 d i i J    (5-40) 3 1 (1 ) d i i J      (5-41) 4 1 (1 ) d i i J      (5-42) 因此，在实际运算中，只要求出 1 W B S S  的特征值，即可求得 i J （ i 1,2,3,4 ）。 5.4 基于距离阈值的聚类算法 当确定了相似性测度和准则函数后，聚类的过程是依靠聚类算法来实现的。因此，聚类算法是一个试 图识别数据集合聚类的特殊性质的学习过程。本节介绍两种简单的聚类分析方法，它是对某些关键性的元 素进行试探性的选取，使某种聚类准则达到最优，又称为基于试探的聚类算法。 5.4.1 最近邻规则的聚类算法 最近邻规则聚类分析问题描述为：假设已有混合样本集   (N) 1 2 , , , X X X X  n ，给定类内距离门限阈 值 T ，将   (N) 1 2 , , , X X X X  n 划分为    1 2 ， ， ， c 个类别。 最近邻规则聚类算法的基本思想是：计算样本的特征向量到聚类中心的距离，将该距离与门限阈值 T 比 较，决定该样本属于哪一类别或作为新一类别的中心。 按照最近邻原则进行聚类，算法步聚如下： ① 选取距离阈值 T ，并且任取一个样本作为第一个聚合中心 Z1 ，如： Z X 1 1  。 ② 计算样本 X2 到 Z1 的距离 D21： 若 D21  T ，则 X Z 2 1  ，否则令 X2 为第二个聚合中心，即 Z X 2 2  。 设 Z X 2 2  ，计算 X3 到 Z1 和 Z2 的距离 D31 和 D32 ，若 D31  T 和 D32  T ，则建立第三个聚合中心 Z3 。 否则把 X3 归于最近邻的聚合中心。依此类推，直到把所有的 n 个样本都进行分类。 ③ 按照某种聚类准则考察聚类结果，若不满意，则重新选取距离阈值 T 和第一个聚合中心 Z1 ，返回②， 直到满意，算法结束。 该算法的优点是简单，如果有样本分布的先验知识用于指导阈值和起始点的选取，则可较快得到合理 结果。其缺点是聚类过程中类别的中心一经选定，在聚类过程将不再改变。同样，样本一经判定类别归属 后也不再改变。因此，在样本分布一定时，该算法的结果在很大程度上取决于第一个聚合中心的选取和距 离阈值的大小。对于高维的样本集来说，只有经过多次试探，并对聚类结果进行检验，才能选择最优的聚 类结果