第二章距离分类器和聚类分析 21距离分类器 模式的距高度量 通过特征抽取,我们以特征空间中的一个点来表示输入的模式,属于同一个类别的样本 所对应的点在模式空间中聚集在一定的区域,而其它类别的样本点则聚集在其它区域,则就 启发我们利用点与点之间距离远近作为设计分类器的基准。这种思路就是我们这一章所要介 绍的距离分类器的基础。下面先看一个简单的距离分类器的例子 例2.1 作为度量两点之间相似性的距离,欧式距离只是其中的一种,当类别的样本分布情况不 同时,应该采用不同的距离定义来度量。 设XY为空间中的两个点,两点之间的距离d(XY),更一般的称为是范数X-, 个矢量自身的范数N为矢量的长度。 作为距离函数应该满足下述三个条件: a)对称性:d(XY)=d(Y,X) b)非负性:d(XY)20,d(XY)=0当且仅当X=Y c)三角不等式:d(XY)≤d(X,Z)+d(Y,Z 满足上述条件的距离函数很多,下面介绍几种常用的距离定义: 设X=(x1x2…,x),Y=(x,y2,…,y,)为n维空间中的两点 1、欧几里德距离:( Eucidean Distance)
9 第二章 距离分类器和聚类分析 2.1 距离分类器 一、模式的距离度量 通过特征抽取，我们以特征空间中的一个点来表示输入的模式，属于同一个类别的样本 所对应的点在模式空间中聚集在一定的区域，而其它类别的样本点则聚集在其它区域，则就 启发我们利用点与点之间距离远近作为设计分类器的基准。这种思路就是我们这一章所要介 绍的距离分类器的基础。下面先看一个简单的距离分类器的例子。 例 2.1 作为度量两点之间相似性的距离，欧式距离只是其中的一种，当类别的样本分布情况不 同时，应该采用不同的距离定义来度量。 设 X Y, 为空间中的两个点，两点之间的距离 d (X Y, ) ，更一般的称为是范数 X Y− ， 一个矢量自身的范数 X 为矢量的长度。 作为距离函数应该满足下述三个条件： a) 对称性： d d (X Y Y X , , ) = ( ) ； b) 非负性： d (X Y, 0 ) ， d (X Y, 0 ) = 当且仅当 X Y= ； c) 三角不等式： d d d (X Y X Z Y Z , , , ) + ( ) ( ) 。 满足上述条件的距离函数很多，下面介绍几种常用的距离定义： 设 ( 1 2 , , , ) T n X = x x x ， ( 1 2 , , , ) T n Y = y y y 为 n 维空间中的两点 1、 欧几里德距离：(Eucidean Distance)
d(Xy)=|∑(x-y) 2、街市距离:( Manhattan distance d(XY)=∑x-y 3、明氏距离:( Minkowski Distance) d(x,Y)=2)x,-yl 当m=2时为欧氏距离,当m=1时为街市距离。 4、角度相似函数:( Angle distance) d (x,Y) x为矢量X和Y之间的内积,d(X,Y)为矢量X与Y之间夹角的 余弦 距离函数的定义形式还有很多,我们应该根据具体问题来选择一种适合的函数定义,使 其能够真正反映模式之间的相似性。定义了范数的线性空间称为赋范线性空间 二、单个标准样本的距离分类器 设有M个类别,Ω1,92…,Ω,每个类别有一个标准样本T,T2,…,T,现有一待 识样本X,则X应该属于与其距离最小的标准样本代表的那一类,即:如果 = arg mind(X,T),则判别X∈92 类别1距离 类别2距离 待识模式 最小值选择器 识别结果 类别M距离 对于两类问题来说,就相当于用一个垂直平分两个标准样本点的连线的超平面将两类分 开 三、多个标准样本的距高分类器 如果每个类别只有一个训练样本,则只能以这个训练样本作为标准样本来设计距离分类 器。然而一个样本很难反映出类别的总体分布,因此在实际设计中,一般都要尽可能多的搜
10 ( ) ( ) 1 2 2 1 , n i i i d x y = = − X Y 2、 街市距离：(Manhattan Distance) ( ) 1 , n i i i d x y = X Y = − 3、 明氏距离：(Minkowski Distance) ( ) 1 1 , n m m i i i d x y = = − X Y 当 m = 2 时为欧氏距离，当 m =1 时为街市距离。 4、 角度相似函数：(Angle Distance) ( , ) T d = X Y X Y X Y 1 n T i i i x y = X Y = 为矢量 X 和 Y 之间的内积， d (X Y, ) 为矢量 X 与 Y 之间夹角的 余弦。 距离函数的定义形式还有很多，我们应该根据具体问题来选择一种适合的函数定义，使 其能够真正反映模式之间的相似性。定义了范数的线性空间称为赋范线性空间。 二、单个标准样本的距离分类器 设有 M 个类别， 1 2 , , , M ，每个类别有一个标准样本 T ,T , ,T 1 2 M ，现有一待 识样本 X ， 则 X 应 该 属 于 与其 距 离最 小 的标 准 样本 代 表的 那 一类 ， 即： 如 果 0 arg min , ( i) i i d = X T ，则判别 0 Xi 。 类别1距离 类别2距离 类别M距离 ... 最 小 值 选 择 器 待识模式 识别结果 对于两类问题来说，就相当于用一个垂直平分两个标准样本点的连线的超平面将两类分 开。 三、多个标准样本的距离分类器 如果每个类别只有一个训练样本，则只能以这个训练样本作为标准样本来设计距离分类 器。然而一个样本很难反映出类别的总体分布，因此在实际设计中，一般都要尽可能多的搜
集各个类别的样本,样本量的增加能够跟好的反映出类别的中体分布情况,这样带来的问题 就是如何利用多个样本来设计距离分类器?下面介绍几种常用的方法 1.平均样本法 此方法中,我们还希望以一个标准样本来代表每个类别,这样就可以采用单个标准样本 距离分类器的准则来进行分类。下面的问题就是如何来确定这个标准样本,这实际上就是如 何利用训练样本集来进行学习的问题 在模式识别方法中,我们将经常遇到最优化问题,下面我们就以这个简单问题来介绍一 下最优化方法的一些概念 设有M个类别,92.2…,第m类有训练样本集{X,x回,…x吧},我们 希望求得一个标准样本T叫,训练样本X=(x,x…,x)我们要寻找的标准样本 T实际上应该是一个距离训练样本集中所有样本的平均距离最小的一点,则一点最能够 代表这个训练样本集。例如,如果类别样本的分布为一个球形的话,这一点应该是球的中心。 这一条件可以用下面的函数表示:()=∑4(x-T),此函数称为目标 函数。我们的目标就是要寻找到一个T叫,使得(T)最小 以欧氏距离为例,f(T)1 ∑(S("-),下面r的各推元素取偏 导数 afIT at 2K 11-x+)-0 则:(1"=1∑x2,以矢量形式表示:T叫=1∑x 平均样本法的特点是:1、算法简单;2、每个类别只需存储一个平均样本,存储量小 3、识别时只需计算M次距离函数,计算量小:4、对类别样本的分布描述能力不强,效果 不一定很好。 在单个样本的距离分类器中,实际上我们是定义了一个未知类别模式到某一类别的距 离,这个距离就是待识模式与类别标准样本之间的距离:d(Xg)=d(X,T),然后以模 式与类别的距离作为分类的判据。实际上在多个标准样本的问题中,我们还可以定义其它形 式的模式与类别的距离 2.平均距离法 己知类别92的训练样本集为:Tγ,T20…,I},定义待识模式X与类别的距离: d(x Q2 11
11 集各个类别的样本，样本量的增加能够跟好的反映出类别的中体分布情况，这样带来的问题 就是如何利用多个样本来设计距离分类器？下面介绍几种常用的方法。 1. 平均样本法 此方法中，我们还希望以一个标准样本来代表每个类别，这样就可以采用单个标准样本 距离分类器的准则来进行分类。下面的问题就是如何来确定这个标准样本，这实际上就是如 何利用训练样本集来进行学习的问题。 在模式识别方法中，我们将经常遇到最优化问题，下面我们就以这个简单问题来介绍一 下最优化方法的一些概念。 设有 M 个类别， 1 2 , , , M ，第 m 类有训练样本集 ( ) ( ) ( ) 1 2 , , , m m m m X X XK ，我们 希望求得一个标准样本 (m) T ，训练样本 ( ) ( ) ( ) ( ) ( 1 2 , , , ) m m m m i i i iN X = x x x 。我们要寻找的标准样本 (m) T 实际上应该是一个距离训练样本集中所有样本的平均距离最小的一点，则一点最能够 代表这个训练样本集。例如，如果类别样本的分布为一个球形的话，这一点应该是球的中心。 这一条件可以用下面的函数表示： ( ) ( ) ( ) ( ) ( ) 1 1 Km m m m i m i f d K = T X T = − ，此函数称为目标 函数。我们的目标就是要寻找到一个 (m) T ，使得 ( ) ( ) m f T 最小。 以欧氏距离为例， ( ) ( ) ( ) ( ) ( ) 1 2 2 1 1 1 Km N m m m ij j m i j f x t K = = = − T ，下面对 (m) T 的各维元素取偏 导数： ( ) ( ) ( ) ( ) ( ) ( ( ) ( )) ( ) ( ) 1 1 1 1 1 2 1 0 2 m m m m K K K m m m m m ij j j ij m m i i i k f x t t x t K K = = = = − − = − = T 则： ( ) ( ) 1 1 Km m m j ij m i t x K = = 。以矢量形式表示： ( ) ( ) 1 1 Km m m i K m i= T X = 。 平均样本法的特点是：1、算法简单；2、每个类别只需存储一个平均样本，存储量小； 3、识别时只需计算 M 次距离函数，计算量小；4、对类别样本的分布描述能力不强，效果 不一定很好。 在单个样本的距离分类器中，实际上我们是定义了一个未知类别模式到某一类别的距 离，这个距离就是待识模式与类别标准样本之间的距离： d d (X X T , , = i i ) ( ) ，然后以模 式与类别的距离作为分类的判据。实际上在多个标准样本的问题中，我们还可以定义其它形 式的模式与类别的距离。 2. 平均距离法 已知类别 i 的训练样本集为： ( ) ( ) ( ) 1 2 , , , i i i i T T TK ，定义待识模式 X 与类别 i 的距离： ( ) ( ) ( ) 1 1 , , Ki i i j j i d d K = X X T =
然后还是以与待识模式最近的类别作为识别结果。在平均距离法中,需要存储所有的训 练样本,而且在识别时还要计算待识模式与每个训练样本的距离,所以计算量比较大 3.最近邻法 最近邻法以与待识样本距离最近的标准样本点的类别作为分类类别。实际上相当于定义 待识模式与类别g的距离 d(x, Q2, )=min d(x,T') 最近邻法也要存储和计算所有的训练样本,同时与平均距离法相比容易受到噪声的干 扰,当与X最近点为噪声时,就会导致误识。 最近邻法的改进 平均样本法用一点代表一个类别,过分集中;最近邻法以类内的每一点代表类别,过于 分散,在通常情况下可以采用折衷的办法,首先将每个类别的训练样本划分为几个子集,在 各个子集中计算平均样本,每一个类别以几个子集的平均样本代表,采用最近邻法分类。(举 例红莩果,绿莩),这样做的好处是,一方面可以减少存储量和计算量,同时还可以减 小噪声的干扰,这是在实际系统使用比较多的方法 4.K近邻法 K-近邻法是另外一种减小噪声干扰的改进方法,它不是根据与未知样本X最近的一个 样本的类别来分类,而是根据X最近邻的K各样本点中多数点的类别来分类。方法如下: a)计算X与所有训练样本的距离 b)对所有的d(xT)从小到大排序 e)统计前K个中各类训练样本的个数N,i=1.2,…,M,必有∑N=K d)取= arg max M作为X的类别 K-近邻法中,K值得选择非常重要,太大则就会变成那一类的训练样本说多就分类到 哪一类,太少则容易受到噪声的影响,当K=1时,就变为了最近邻法 22聚类分析 在某些问题中,我们已知的只是一个训练样本集,而不知道样本集中每个样本的类别标 号,这就需要我们首先将这些样本分成若干类,然后再用分好类的样本训练出相应的分类器 将未知类别的一组样本分成若干类的过程称为是聚类分析,也称为是无监督学习或无教师学 聚类分析的思路非常直观,也是根据各个带分类模式特征的相似程度来进行分类,将在 特征空间中聚集在一起的样本点划分为一类。 聚类分析的方法可以分为三类:简单聚类法、系统聚类法和动态聚类法。 简单聚类法(试探法) 1、最近邻规则的简单试探法 设N个待分类的模式{X1,X2…X},已知一个阈值7(每个样本到其聚类中心的
12 然后还是以与待识模式最近的类别作为识别结果。在平均距离法中，需要存储所有的训 练样本，而且在识别时还要计算待识模式与每个训练样本的距离，所以计算量比较大。 3. 最近邻法 最近邻法以与待识样本距离最近的标准样本点的类别作为分类类别。实际上相当于定义 待识模式与类别 i 的距离： ( ) ( ) ( ) 1 , min , i i i j j K d d X X T = 最近邻法也要存储和计算所有的训练样本，同时与平均距离法相比容易受到噪声的干 扰，当与 X 最近点为噪声时，就会导致误识。 最近邻法的改进： 平均样本法用一点代表一个类别，过分集中；最近邻法以类内的每一点代表类别，过于 分散，在通常情况下可以采用折衷的办法，首先将每个类别的训练样本划分为几个子集，在 各个子集中计算平均样本，每一个类别以几个子集的平均样本代表，采用最近邻法分类。（举 例：红苹果，绿苹果），这样做的好处是，一方面可以减少存储量和计算量，同时还可以减 小噪声的干扰，这是在实际系统使用比较多的方法。 4. K -近邻法 K -近邻法是另外一种减小噪声干扰的改进方法，它不是根据与未知样本 X 最近的一个 样本的类别来分类，而是根据 X 最近邻的 K 各样本点中多数点的类别来分类。方法如下： a) 计算 X 与所有训练样本的距离； b) 对所有的 ( ) ( , ) i j d X T 从小到大排序； c) 统计前 K 个中各类训练样本的个数 Ni ，i M =1, 2, , ，必有 1 M i i N K = = ； d) 取 0 1 arg max i i M i N = 作为 X 的类别。 K -近邻法中， K 值得选择非常重要，太大则就会变成那一类的训练样本说多就分类到 哪一类，太少则容易受到噪声的影响，当 K = 1 时，就变为了最近邻法。 2.2 聚类分析 在某些问题中，我们已知的只是一个训练样本集，而不知道样本集中每个样本的类别标 号，这就需要我们首先将这些样本分成若干类，然后再用分好类的样本训练出相应的分类器。 将未知类别的一组样本分成若干类的过程称为是聚类分析，也称为是无监督学习或无教师学 习。 聚类分析的思路非常直观，也是根据各个带分类模式特征的相似程度来进行分类，将在 特征空间中聚集在一起的样本点划分为一类。 聚类分析的方法可以分为三类：简单聚类法、系统聚类法和动态聚类法。 一、简单聚类法（试探法） 1、 最近邻规则的简单试探法 设 N 个待分类的模式 X X X 1 2 , , , N ，已知一个阈值 T （每个样本到其聚类中心的
最大距离),分类到21,92…,类别中心分别为Z1Z2 第一步:取任意的样本X作为第一个聚类中心的初始值,例如:Z1=X1∈g1 计算:D21=X2-Z1 若,D21>T,则增加一个新类别g22,取其中心为Z2=X2 否则,将X2归入以Z为中心的921类,重新计算Z1 X+X 第二步:设已有类别g21,_2,其中心为Z1,Z2 计算:D31=|X3-Z,D2=|X3-Z2 若,D1>T且D32>T,则增加新类别923,令Z3=X3 否则,X3属于Z1,Z2最近的类别,即X3∈4,6= arg min D31,并重新计算 类的中心。 第k步:设已有M个类别21,92…,息M,其中心为Z1,Z2…ZM, 计算:D31=X-Z1|,…,Dax=1x4-Z‖ 若,D>T,则增加新类别Ω2M+,其中心ZM+1=Xk 否则,X属于Z1,Z2,…ZM最近的一类,Xk∈g4,io= arg min Du: 重新计算第类的聚类中心Z。。 例2.2-1 这种方法的好处是计算比较简单,缺点是对初始的第一个聚类中心的选择依赖性比较 强,同时聚类效果还要受到阈值T的影响。(图33-2,pp64)一般在实际问题中需要对不同 的初始聚类中心和不同的阈值进行试探,直到得到一个满意的聚类结果为止。 2、最大最小距离算法 最大最小距离法的思路是:在样本集中以最大距离原则选取新的聚类中心,以最小距离 原则进行模式归类。 已知N个待分类的模式{XX2…X},阈值比例系数θ, 1)任选样本作为第一个聚类中心Z1 2)从样本集中选择距离Z1最远的样本X作为第二个聚类中心,Z2=X,设定距离 阅值:T=0|Z1-Z2l:
13 最大距离），分类到 1 2 , , ，类别中心分别为 1 2 Z Z, , 。 第一步：取任意的样本 Xi 作为第一个聚类中心的初始值，例如： Z X 1 1 1 = ； 计算： D21 2 1 = − X Z ， 若， D T 21 ，则增加一个新类别 2 ，取其中心为 Z X 2 2 = ； 否则，将 X2 归入以 Z1 为中心的 1 类，重新计算 1 2 1 2 + = X X Z 。 第二步：设已有类别 1 2 , ，其中心为 1 2 Z Z, ， 计算： D31 3 1 = − X Z ， D32 3 2 = − X Z ； 若， D T 31 且 D T 32 ，则增加新类别 3 ，令 Z X 3 3 = ； 否则， X3 属于 1 2 Z Z, 最近的类别，即 0 X3 i ， 0 3 1 2 arg min i i i D = ，并重新计算 0 i 类的中心。 第 k 步：设已有 M 个类别 1 2 , , , M ，其中心为 1 2 , , Z Z ZM ， 计算： Dk k 1 1 = − X Z ，…， DkM k M = − X Z ； 若， D T ki ，则增加新类别 M +1 ，其中心 Z X M k +1 = ； 否则， Xk 属于 1 2 , , Z Z ZM 最近的一类， 0 Xk i ， 0 1 arg min ki i M i D = ； 重新计算第 0 i 类的聚类中心 0 Zi 。 例 2.2-1 这种方法的好处是计算比较简单，缺点是对初始的第一个聚类中心的选择依赖性比较 强，同时聚类效果还要受到阈值 T 的影响。（图 3.3-2，pp64）一般在实际问题中需要对不同 的初始聚类中心和不同的阈值进行试探，直到得到一个满意的聚类结果为止。 2、 最大最小距离算法 最大最小距离法的思路是：在样本集中以最大距离原则选取新的聚类中心，以最小距离 原则进行模式归类。 已知 N 个待分类的模式 X X X 1 2 , , , N ，阈值比例系数 ， 1) 任选样本作为第一个聚类中心 Z1 ； 2) 从样本集中选择距离 Z1 最远的样本 Xi 作为第二个聚类中心， Z X 2 = i ，设定距离 阈值： T = − Z Z 1 2 ；
3)计算未被作为聚类中心的各样本与Z1,Z2之间的距离,以其中的最小值作为该样本 的距离: d=|X-Z,j=12,取d=min[41d2]=1…N 4)若:d=maxd>T,则相应的样本X作为第三个聚类中心,Z3=X,然后转 5);否则,转6) 5)设存在k个聚类中心,计算未被作为聚类中心的各样本到各聚类中心的最小距离: d=min[d1…dk],然后寻找其中的最大值:d=maxd,如果d>T,则 Z1=X,转5);否则,转6); 6)按照最小距离原则,将所有样本分到个类别中。 例2.2-2 二、合并法(系统聚类法, Hierarchical Clustering Method) 系统聚类法的思路是首先以每一个样本自成一类,然后按照距离准则逐步合并,类别数由 多到少,直到达到合适的类别数为止。 这里,我们在合并两个类别时,需要依据类与类之间的距离度量,首先我们来定义类与 类之间的相似性度量。 1.最短距离法: 设只和9,是两个聚类,两类之间的距离定义为:D=mm((xyx)x为 类的第l个样本,X(为9,类的第k个样本。D为第9类中所有样本与第Ω2,类中所有样 本之间的最小值 2.最长距离法 与最短距离法相似,两类之间的距离定义:D=m((xx2),x为2类 的第l个样本,X为92,类的第k个样本。D为第9类中所有样本与第,类中所有样本 之间的最小值。 3.类平均距离法 两类之间的距离定义为:Dn=NN ∑d(x9,x),n和几分别为92、9,聚 类中的样本数。 系统聚类算法:设有X1X2,…XNN个样本待分类 第一步:建立N个初始类别,g20,g29)…Ω29,其中ΩP={X}。计算距离矩阵 D=(D),其中D,为g与99之间的距离:
14 3) 计算未被作为聚类中心的各样本与 1 2 Z Z, 之间的距离，以其中的最小值作为该样本 的距离： , 1,2 ij i j d j = − = X Z ，取 d d d i N i i i = = min , , 1, , 1 2 ； 4) 若： 1 max l i i N d d T = ，则相应的样本 Xl 作为第三个聚类中心， Z X 3 = l ，然后转 5）；否则，转 6）； 5) 设存在 k 个聚类中心，计算未被作为聚类中心的各样本到各聚类中心的最小距离： d d d i i ik = min , , 1 ，然后寻找其中的最大值： 1 max l i i N d d = ，如果 l d T ，则 Z X k l +1 = ，转 5）；否则，转 6）； 6) 按照最小距离原则，将所有样本分到个类别中。 例 2.2-2 二、合并法（系统聚类法，Hierarchical Clustering Method） 系统聚类法的思路是首先以每一个样本自成一类,然后按照距离准则逐步合并,类别数由 多到少，直到达到合适的类别数为止。 这里，我们在合并两个类别时，需要依据类与类之间的距离度量，首先我们来定义类与 类之间的相似性度量。 1. 最短距离法： 设 i 和 j 是两个聚类，两类之间的距离定义为： ( ) ( ) min , ( ( )) i j D d ij l k = X X ， (i) Xl 为 i 类的第 l 个样本， ( j) Xk 为 j 类的第 k 个样本。 Dij 为第 i 类中所有样本与第 j 类中所有样 本之间的最小值。 2. 最长距离法： 与最短距离法相似，两类之间的距离定义为： ( ) ( ) max , ( ( )) i j D d ij l k = X X ， (i) Xl 为 i 类 的第 l 个样本， ( j) Xk 为 j 类的第 k 个样本。 Dij 为第 i 类中所有样本与第 j 类中所有样本 之间的最小值。 3. 类平均距离法： 两类之间的距离定义为： ( ) ( ) ( ) 1 2 , i j ij l k i j D d N N = X X ， i n 和 j n 分别为 i 、 j 聚 类中的样本数。 系统聚类算法：设有 1 2 , , , X X XN N 个样本待分类， 第一步：建立 N 个初始类别， (0 0 0 ) ( ) ( ) 1 2 , , , N ，其中 ( ) 0 = i i X 。计算距离矩阵： ( ) ( ) 0 D = Dij ，其中 Dij 为 (0) i 与 (0) j 之间的距离；
第二步:寻找D“中的最小元素,合并相应的两个类别,建立新的分类:Q2,92,…,9), 重新计算距离矩阵D) 第三步:重复第二步,直到满足类别数要求,或者D的最小元素大于给定的阈值。 例 合并法避免了聚类结果受初始聚类中心的影响,但是需要预先知道聚类的类别数,或者 需要设定一个类间最小距离阈值。同时当样本数比较多时,计算量比较大 三、动态聚类法(修改法) 动态聚类的思想是首先选择若干个样本点作为聚类中心,然后按照某种聚类准则使各样 本点向各个中心聚集,从而得到初始分类:然后判断初始分类是否合理,如果不合理,则修 改聚类中心,反复进行修改,直到分类合理为止。 动态聚类有多种算法,其中比较著名的是K-均值算法和 ISODATA算法。下面介绍其 中的K-均值算法(或称为C-均值算法)。 设有N个待分类样本X1,X2…X,聚类为K类,N≥K 第一步:任选K个初始聚类中心Z1,Z2…Zx,例如选前K个样本(称为旧聚类中心); 第二步:将每一个待分类样本按照最近邻准则分类,分别以旧聚点为标准样本的各类中去。 第三步:计算分类后各类的重心,称为新聚类中心:Y= X,i=1,2…,K,其中 N为92,类中的样本数 第四步:检验Z1,Z2…Zκ是否分别等于Y1,Y2…Yk’如果相等,则算法收敛,结束; 否则用Y代替Z,返回第二步 例24 K-均值算法的结果也要受到所选的聚类中心的数目、初始聚类位置以及样本的几何性 质的影响 23聚类结果评价 前面我们所介绍的几种聚类方法都存在着一定的缺陷,一般都要受到各种初始状态和各 种预设的阈值影响,需要我们进行多次尝试之后才能得到满意的结果。这就需要有一个对聚 类结果评价的方法,来帮助我们在多次尝试的结果种选择出一个满意的结果。同时如果这个 评价准则建立好之后,也可以由程序来完成这个选择的任务。 常用的评价准则有: 1.类内距离方差:J=∑∑-Z,,可以用来衡量各个类别中的样本的平均离散
15 第二步：寻找 (k−1) D 中的最小元素，合并相应的两个类别，建立新的分类： ( ) ( ) ( ) 1 2 , , , k k k M ， 重新计算距离矩阵 (k ) D 。 第三步：重复第二步，直到满足类别数要求，或者 (k ) D 的最小元素大于给定的阈值。 例 2.3 合并法避免了聚类结果受初始聚类中心的影响，但是需要预先知道聚类的类别数，或者 需要设定一个类间最小距离阈值。同时当样本数比较多时，计算量比较大。 三、动态聚类法（修改法） 动态聚类的思想是首先选择若干个样本点作为聚类中心，然后按照某种聚类准则使各样 本点向各个中心聚集，从而得到初始分类；然后判断初始分类是否合理，如果不合理，则修 改聚类中心，反复进行修改，直到分类合理为止。 动态聚类有多种算法，其中比较著名的是 K -均值算法和 ISODATA 算法。下面介绍其 中的 K -均值算法（或称为 C -均值算法）。 设有 N 个待分类样本 1 2 , , , X X XN ，聚类为 K 类， N K 。 第一步：任选 K 个初始聚类中心 1 2 , , , Z Z ZK ，例如选前 K 个样本（称为旧聚类中心）； 第二步：将每一个待分类样本按照最近邻准则分类，分别以旧聚点为标准样本的各类中去。 第三步：计算分类后各类的重心，称为新聚类中心： 1 i i Ni = X Y X ，i K =1,2, , ，其中 Ni 为 i 类中的样本数； 第四步：检验 1 2 , , , Z Z ZK 是否分别等于 1 2 , , , Y Y YK ，如果相等，则算法收敛，结束； 否则用 Yi 代替 Zi ，返回第二步。 例 2.4 K -均值算法的结果也要受到所选的聚类中心的数目、初始聚类位置以及样本的几何性 质的影响。 2.3 聚类结果评价 前面我们所介绍的几种聚类方法都存在着一定的缺陷，一般都要受到各种初始状态和各 种预设的阈值影响，需要我们进行多次尝试之后才能得到满意的结果。这就需要有一个对聚 类结果评价的方法，来帮助我们在多次尝试的结果种选择出一个满意的结果。同时如果这个 评价准则建立好之后，也可以由程序来完成这个选择的任务。 常用的评价准则有： 1. 类内距离方差： 2 1 i M W i i J = = − X X Z ，可以用来衡量各个类别中的样本的平均离散
程度,类内距离方差越小越好。 2.类间距离方差:J=∑-Z‖,其中Z Z.,为各个聚类中的平均矢量。 类间距离方差可以用来衡量各个类别之间的离散程度,越大越好 3.各类的样本数:一般情况要求各个类别中的样本数应该比较平均,避免出现某一类中样 本数过多,或某一类中样本数过少的情况 一般情况下,需要综合考虑几种评价准则,而不能只考虑其中的一项,同时还要有其它 的条件限制,比如给定的聚类类别数等。例如,只考虑类内距离准则,则当每一个样本单独 为一类时,准则最优:只考虑类间距离准则时,则所有样本聚为一类时,淮则最优 从聚类准则的角度来看,前集中聚类算法都是在某些条件限制下,对某个准则进行寻优 例如动态聚类法是在限定类别数的条件下,寻找到一个对样本集的划分方式,使得类内距离 方差最小。但是各种聚类方法都是一种次优的搜索方法,不能保证最后的结果是一个最优解 如果要求最优解只能对所有的可能情况进行计算。但是当样本数比较多时,组合数很大,不 可能对所有的组合进行遍历,比如在例24中,组合数为:C20+C20+…+C20,其中 C0=670442572800 近些年发展的一种求解上述类似寻优问题的算法是遗传算法,可以在一定程度上解决这 类问题
16 程度，类内距离方差越小越好。 2. 类间距离方差： 2 1 M B i i J = = − Z Z ，其中 1 1 M i M i= Z Z = ，为各个聚类中的平均矢量。 类间距离方差可以用来衡量各个类别之间的离散程度，越大越好。 3. 各类的样本数：一般情况要求各个类别中的样本数应该比较平均，避免出现某一类中样 本数过多，或某一类中样本数过少的情况。 一般情况下，需要综合考虑几种评价准则，而不能只考虑其中的一项，同时还要有其它 的条件限制，比如给定的聚类类别数等。例如，只考虑类内距离准则，则当每一个样本单独 为一类时，准则最优；只考虑类间距离准则时，则所有样本聚为一类时，准则最优。 从聚类准则的角度来看，前集中聚类算法都是在某些条件限制下，对某个准则进行寻优。 例如动态聚类法是在限定类别数的条件下，寻找到一个对样本集的划分方式，使得类内距离 方差最小。但是各种聚类方法都是一种次优的搜索方法，不能保证最后的结果是一个最优解。 如果要求最优解只能对所有的可能情况进行计算。但是当样本数比较多时，组合数很大，不 可能对所有的组合进行遍历，比如在例 2.4 中，组合数为： 1 2 10 C C C 20 20 20 + + + ，其中： 10 C20 =670442572800。 近些年发展的一种求解上述类似寻优问题的算法是遗传算法，可以在一定程度上解决这 类问题