第五章特征选择与特征提取 51问题的提出 前面主要介绍的是各种分类器的设计方法,实际上我们已经完全可以解决模式识别的问 题了。然而在实际应用中,在分类器设计之前,往往需要对抽取出的特征进行一下处理,争 取尽量减小特征的维数。在实践中我们发现,特征的维数越大,分类器设计的难度也越大 维特征的识别问题最容易解决,我们只要找到一个阈值1,大于t的为一类,小于t的为 类。同时特征维数越大,要求的训练样本数量越多,例如在一维的情况下,10个训练样本 就可以比较好的代表一个类别了,而在10维空间中,10个训练样本则是远远不够的。这 章中我们就来介绍一下减小特征维数的方法。 般来说模式识别系统的输入是传感器对实物或过程进行测量所得到的一些数据,其中 有一些数据直接可以作为特征,有一些数据经过处理之后可以作为特征,这样的一组特征一 般称为原始特征。在原始特征中并不一定每个特征都是有用的,比如在识别苹果和橙子的系 统中,我们可以抽取出的特征很多,(体积,重量,颜色,高度,宽度,最宽处高度),同样 还有可能抽取出其它更多的特征。在这些特征中对分类有用的是(颜色,高度,最宽处高度) 其它特征对识别意义不大,应该去除掉。这样的过程称为是特征选择,也可以称为是特征压 缩 特征选择可以描述成这样一个过程,原始特征为N维特征X=(x,x2…,x),从中 选择出M个特征构成新的特征矢量Y=(x,x1…x),M<N 同时,特征矢量的每一个分量并不一定是独立的,它们之间可能具有一定的相关性,比 如说高度和最宽处的高度,高度值越大,最宽处的高度值也越大,它们之间具有相关性,我 们可以通过一定的变换消除掉这种相关性,比如取一个比值:最宽处的高度/高度。这样的 过程称为特征提取。 特征提取可以描述为这样一个过程,对特征矢量X=(x1,x2,…,x)施行变换 y=h(X),1=12…,M,M<N,产生出降维的特征矢量Y=(y,y2,…,yn)。 在一个实际系统的设计过程中,特征的选择和提取过程一般都需要进行,首先进行特征 选择,去除掉无关特征,这些特征实践上根本就不需要抽取出来,这部分传感器根本不需要 安装,这样也可以减小系统的的成本。然后进行特征提取,降低特征的维数。然后利用降维 之后的样本特征来设计分类器。 52模式类别的可分性判据 在讨论特征选择和特征压缩之前,我们先要确定一个选择和提取的原则。对一个原始特
43 第五章 特征选择与特征提取 5.1 问题的提出 前面主要介绍的是各种分类器的设计方法，实际上我们已经完全可以解决模式识别的问 题了。然而在实际应用中，在分类器设计之前，往往需要对抽取出的特征进行一下处理，争 取尽量减小特征的维数。在实践中我们发现，特征的维数越大，分类器设计的难度也越大， 一维特征的识别问题最容易解决，我们只要找到一个阈值 t ，大于 t 的为一类，小于 t 的为一 类。同时特征维数越大，要求的训练样本数量越多，例如在一维的情况下，10 个训练样本 就可以比较好的代表一个类别了，而在 10 维空间中，10 个训练样本则是远远不够的。这一 章中我们就来介绍一下减小特征维数的方法。 一般来说模式识别系统的输入是传感器对实物或过程进行测量所得到的一些数据，其中 有一些数据直接可以作为特征，有一些数据经过处理之后可以作为特征，这样的一组特征一 般称为原始特征。在原始特征中并不一定每个特征都是有用的，比如在识别苹果和橙子的系 统中，我们可以抽取出的特征很多，（体积，重量，颜色，高度，宽度，最宽处高度），同样 还有可能抽取出其它更多的特征。在这些特征中对分类有用的是（颜色，高度，最宽处高度）， 其它特征对识别意义不大，应该去除掉。这样的过程称为是特征选择，也可以称为是特征压 缩。 特征选择可以描述成这样一个过程，原始特征为 N 维特征 ( 1 2 , , , ) T N X = x x x ，从中 选择出 M 个特征构成新的特征矢量 ( ) 1 1 , , , M T Y x x x = i i i ， M N 。 同时，特征矢量的每一个分量并不一定是独立的，它们之间可能具有一定的相关性，比 如说高度和最宽处的高度，高度值越大，最宽处的高度值也越大，它们之间具有相关性，我 们可以通过一定的变换消除掉这种相关性，比如取一个比值：最宽处的高度/高度。这样的 过程称为特征提取。 特征提取可以描述为这样一个过程，对特征矢量 ( 1 2 , , , ) T N X = x x x 施行变换： y h i i = (X) ，i M =1, 2, , ， M N ，产生出降维的特征矢量 ( 1 2 , , , ) T Y y y y = M 。 在一个实际系统的设计过程中，特征的选择和提取过程一般都需要进行，首先进行特征 选择，去除掉无关特征，这些特征实践上根本就不需要抽取出来，这部分传感器根本不需要 安装，这样也可以减小系统的的成本。然后进行特征提取，降低特征的维数。然后利用降维 之后的样本特征来设计分类器。 5.2 模式类别的可分性判据 在讨论特征选择和特征压缩之前，我们先要确定一个选择和提取的原则。对一个原始特
征来说,特征选择的方案很多,从N维特征种选择出M个特征共有CM= N! M! (N-M) 选法,其中哪一种方案最佳,则需要有一个原则来进行指导。同样,特征的压缩实际上是要 找到M个N元函数,N元函数的数量是不可数的,这也要有一个原则来指导找出M个最 佳的N元函数。 我们进行特征选择和特征提取的最终目的还是要进行识别,因此应该是以对识别最有利 原则,这样的原则我们称为是类别的可分性判据。用这样的可分性判据可以度量当前特征维 数下类别样本的可分性。可分性越大,对识别越有利,可分性越小,对识别越不利 人们对的特征的可分性判据研究很多,然而到目前为止还没有取得一个完全满意的结 果,没有哪一个判据能够完全度量出类别的可分性。下面介绍几种常用的判据,我们需要根 据实际问题,从中选择出一种。 一般来说,我们希望可分性判据满足以下几个条件: 1.与识别的错误率由直接的联系,当判据取最大值时,识别的错误率最小 2.当特征独立时有可加性,即 J是第i类和第j类的可分性判据,J越大,两类的可分程度越大 (x1,x2…,x)为N维特征: 3.应具有某种距离的特点 J>0,当i≠j时 J=0,当i=j时 4.单调性,加入新的特征后,判据不减小: J(x,x2…,x)≤J(x,x,…,x,x) 但是遗憾的是现在所经常使用的各种判据很难满足上述全部条件,只能满足一个或几个 条件。 基于几何距离的可分性判据 在介绍这一类判据之前,先来看一下各种几何距离的定义 1.点与点的距离 这是我们前面已经介绍过的一种距离,可以有多种形式,如欧氏距离、街市距离、 马氏距离等,特征矢量X和Y之间的距离可以表示为 d(XY)=(X-Y)(X-Y)(欧氏距离) 2.点与类别之间的距离 这也是我们前面定义过的一种距离度量,常用的有:平均样本法、平均距离法、最
44 征来说，特征选择的方案很多，从 N 维特征种选择出 M 个特征共有 ( ) ! ! ! M N N C M N M = − 中 选法，其中哪一种方案最佳，则需要有一个原则来进行指导。同样，特征的压缩实际上是要 找到 M 个 N 元函数， N 元函数的数量是不可数的，这也要有一个原则来指导找出 M 个最 佳的 N 元函数。 我们进行特征选择和特征提取的最终目的还是要进行识别，因此应该是以对识别最有利 原则，这样的原则我们称为是类别的可分性判据。用这样的可分性判据可以度量当前特征维 数下类别样本的可分性。可分性越大，对识别越有利，可分性越小，对识别越不利。 人们对的特征的可分性判据研究很多，然而到目前为止还没有取得一个完全满意的结 果，没有哪一个判据能够完全度量出类别的可分性。下面介绍几种常用的判据，我们需要根 据实际问题，从中选择出一种。 一般来说，我们希望可分性判据满足以下几个条件： 1. 与识别的错误率由直接的联系，当判据取最大值时，识别的错误率最小； 2. 当特征独立时有可加性，即： ( 1 2 ) ( ) 1 , , , N ij N ij k k J x x x J x = = ij J 是第 i 类和第 j 类的 可分 性判 据， ij J 越大， 两类 的可 分程 度越 大， ( x x x 1 2 , , , N ) 为 N 维特征； 3. 应具有某种距离的特点： 0 ij J ，当 i j 时； 0 ij J = ，当 i j = 时； ij ji J J = ； 4. 单调性，加入新的特征后，判据不减小： J x x x J x x x x ij N ij N N ( 1 2 1 2 1 , , , , , , , ) ( + ) 。 但是遗憾的是现在所经常使用的各种判据很难满足上述全部条件，只能满足一个或几个 条件。 一、基于几何距离的可分性判据 在介绍这一类判据之前，先来看一下各种几何距离的定义。 1. 点与点的距离 这是我们前面已经介绍过的一种距离，可以有多种形式，如欧氏距离、街市距离、 马氏距离等，特征矢量 X 和 Y 之间的距离可以表示为： ( , ) ( ) ( ) T d X Y X Y X Y = − − （欧氏距离） 2. 点与类别之间的距离 这也是我们前面定义过的一种距离度量，常用的有：平均样本法、平均距离法、最
近距离法,K-近邻法等。特征矢量X与2类别之间距离的平方可以表示为: d(x9)=∑4(xx)(平均距离法) k=1 其中x,x2,…XQ为9类中的样本,N为g类别中的样本数。 3.类内距离 设旦了由样本集{x,xy…x,样本的均值矢量为m,则由样本集定义 的类内均方距离为 dX NN 当取欧氏距离时有: ()m() 4.类别之间的距离 在第二章中对类别之间的距离也做过定义,包括最短距离法,最长距离法,类平均 距离法等。9类与92,类之间的距离可以表示为 (v() 均距离法) NN 当取欧氏距离时,可定义两类之间的均方距离: d2(9.g 有了距离度量之后,我们就可以在此基础上定义可分性测度了。一般来讲,当各个类别 的类内距离越小时可分性越强,而类间距离越大时,可分性越强。因此可以有以各类样本 间的平均距离作为判据 J(x)=∑P(9P(2)4(929) J(X)所反映的主要还是类别之间的分离程度,对类内的聚集程度反映不够。通常我 们采用跟一般的矩阵形式来构造可分性判据 类内散度矩阵 设有M个类别,92…9,9类样本集(x,xy…X},类的散度矩 阵定义为:
45 近距离法， K -近邻法等。特征矢量 X 与 i 类别之间距离的平方可以表示为： ( ) ( ) ( ) 2 2 1 1 , , Ni i i k i k d d N = X X X = （平均距离法） 其中 ( ) ( ) ( ) 1 2 , , , i i i i X X XN 为 i 类中的样本， Ni 为 i 类别中的样本数。 3. 类内距离 设 i 了由样本集 ( ) ( ) ( ) 1 2 , , , i i i i X X XN ，样本的均值矢量为 (i) m ，则由样本集定义 的类内均方距离为： ( ) ( ) ( ) ( ) 2 2 1 1 1 , N N i i i i i k l k l i i d d N N = = = X X 当取欧氏距离时有： ( ) ( ) ( ) ( ) ( ) ( ) ( ) 2 1 1 Ni T i i i i i k k i k d N = = − − X m X m 4. 类别之间的距离 在第二章中对类别之间的距离也做过定义，包括最短距离法，最长距离法，类平均 距离法等。 i 类与 j 类之间的距离可以表示为： ( ) ( ) ( ) ( ) 1 1 1 , , j i N N i j i j k l k l i j d d N N = = = X X （平均距离法） 当取欧氏距离时，可定义两类之间的均方距离： ( ) ( ) ( ) ( ) ( ) ( ) ( ) 2 1 1 1 , j i N N T i j i j i j k l k l k l i j d N N = = = − − X X X X 有了距离度量之后，我们就可以在此基础上定义可分性测度了。一般来讲，当各个类别 的类内距离越小时可分性越强，而类间距离越大时，可分性越强。因此可以有以各类样本之 间的平均距离作为判据： ( ) ( ) ( ) ( ) 1 1 1 , 2 M M d i j i j i j J P P d = = X = Jd (X) 所反映的主要还是类别之间的分离程度，对类内的聚集程度反映不够。通常我 们采用跟一般的矩阵形式来构造可分性判据。 1. 类内散度矩阵 设有 M 个类别， 1 , , M ， i 类样本集 ( ) ( ) ( ) 1 2 , , , i i i i X X XN ，i 类的散度矩 阵定义为： ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 Ni T i i i i i w k k i k S N = = − − X m X m
总的类内散度矩阵为 S=∑P(2) ∑(x-m9)(x-my) 类间散度矩阵 第i个类别和第j个类别之间的散度矩阵定义为: 总的类间散度矩阵可以定义为 P( P(9)2P(9)m0-m)m9-m) 令:m为总体均值,m=∑P(92,)m0,则有 P(2)(m9-m)( 3.总体散度矩阵 总体散度矩阵可以定义为: S=∑(x-m)X-m) 其中N为总的样本数,N=∑N。可以证明:S=S+SB 可以看出三个散度矩阵均为实对称矩阵 上面我们所定义的判据:(X)=(X)=t(S)=t(S+SB)。m表示取一个矩 阵的迹,也就是主对角线元素之和,N维方阵A的迹为:t(A)=∑an 同样我们可以利用三个散度矩阵定义出一系列的可分性判据 J,=tr(SwB tr (SB)
46 总的类内散度矩阵为： ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 M M Ni T i i i i i w i w i k k i i k i S P S P = = = N = = − − X m X m 2. 类间散度矩阵 第 i 个类别和第 j 个类别之间的散度矩阵定义为： ( ) ( ) ( ) ( ) ( ) ( ) ( ) T ij i j i j B S = − − m m m m 总的类间散度矩阵可以定义为： ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 1 2 2 M M M M ij i j i j B i j B i i i j i j S P P S P P = = = = = = − − m m m m 令： m 为总体均值， ( ) ( ) 1 M i i i P = m m = ，则有： ( ) ( ) ( ) ( ) ( ) 1 M T i i B i i S P = = − − m m m m 3. 总体散度矩阵 总体散度矩阵可以定义为： ( )( ) 1 1 N T T l l l S N = = − − X m X m 其中 N 为总的样本数， 1 M i i N N = = 。可以证明： T W B S S S = + 。 可以看出三个散度矩阵均为实对称矩阵。 上面我们所定义的判据： Jd (X) = J S S S d T W B (X) = = + tr tr ( ) ( ) 。 tr 表示取一个矩 阵的迹，也就是主对角线元素之和， N 维方阵 的迹为： ( ) 1 tr N ii i a = = 同样我们可以利用三个散度矩阵定义出一系列的可分性判据： ( ) 1 1 tr W B J S S − = 2 B W S J S = ( ) ( ) 3 tr tr B W S J S = 4 T W S J S =
其中A表示方阵A的行列式的值,比较常用的判据是J 基于几何距离的可分性判据计算起来比较简单,只要我们已知各个类别的训练样本集, 就可以计算出三个散度矩阵,同时也就可以计算出各种可分性判据。 基于概率分布的可分性判据 基于几何距离的可分性判据计算起来比较简单,然而它没有考虑各类别的概率分布,因 此与识别错误率之间的联系却不是很紧密。下面介绍一种直接基于概率分布的可分性判据 先以最简单的一维特征、两类问题为例,下图表示了两种极端情况: P(X Q)=p(x Q2,) 第一种情况是两类完全可分:对所有p(X92)≠0的点,有p(X2)=0 第二种情况是两类完全不可分:对所有的X有p(X92)=p(X2) 下面我们可以定义两个类条件概率密度函数之间的距离Jp作为交叠程度的度量,Jp应 该满足如下条件 1.非负性,J2≥0; 2.当两类完全重叠时J取最大值,即若对所有X有p(Xg2)≠0时, P(X92)=0,则Jp=max 3.当两类密度函数完全相同时,J应为零,即若P(X92)=P(Xg21),则J=0 按照这样的要求,可以定义出多种可分性判据,这里我们只介绍其中一种一散度 现在考虑9,和92,两类之间的可分性,取其对数似然比: l(X)=In P(X/2 则Ω1类对Ω,类的平均可分性信息可以定义为:
47 其中 Α 表示方阵 Α 的行列式的值，比较常用的判据是 1 J 。 基于几何距离的可分性判据计算起来比较简单，只要我们已知各个类别的训练样本集， 就可以计算出三个散度矩阵，同时也就可以计算出各种可分性判据。 二、基于概率分布的可分性判据 基于几何距离的可分性判据计算起来比较简单，然而它没有考虑各类别的概率分布，因 此与识别错误率之间的联系却不是很紧密。下面介绍一种直接基于概率分布的可分性判据。 先以最简单的一维特征、两类问题为例，下图表示了两种极端情况： 第一种情况是两类完全可分：对所有 p (X 1 ) 0 的点，有 p(X = 2 ) 0 ； 第二种情况是两类完全不可分：对所有的 X 有 p p (X X = 1 2 ) ( ) 。 下面我们可以定义两个类条件概率密度函数之间的距离 P J 作为交叠程度的度量， P J 应 该满足如下条件： 1. 非负性， 0 P J ； 2. 当 两 类 完 全 重 叠 时 P J 取 最 大 值 ， 即 若 对 所 有 X 有 p(X 2 ) 0 时 ， p (X = 1 ) 0 ，则 max P J = ； 3. 当两类密度函数完全相同时， P J 应为零，即若 p p (X X = 2 1 ) ( ) ，则 0 P J = 。 按照这样的要求，可以定义出多种可分性判据，这里我们只介绍其中一种—散度。 现在考虑 i 和 j 两类之间的可分性，取其对数似然比： ( ) ( ) ( ) ln i ij j p l p = X X X 则 i 类对 j 类的平均可分性信息可以定义为：