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

第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  各特征值非负时，还可定义下列相似系数

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

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