第二章距离分类器和聚类分析 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 ；