第五章特征选择与特征提取 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 类的平均可分性信息可以定义为：
1(X)=E[4(x)]=p(x9)n XΩ P(x2) 同样Ω,类对2类的平均可分性信息 (x)-5(xp)n2)q X 1(X)=E[ 散度J定义为区分92类和,类的总平均信息: X J=1+1=J[p(x9)-p(x9)jm P(XQ 从小的定义可以看出,当两类分不完全性同p(X9)=p(XO)时,J=0:当两 类完全可分时,Jp=+0 基于概率的可分性判据优点是直接与识别的错误率相联系,缺点是需要已知各个类别类 概率密度函数,只有当我们预先已知各类别的概率分布时,才可以利用训练样本集合估计出 概率密度函数,但是对很多实际问题来说各类别的概率分布情况我们是无法预先知道的 53特征选择 所谓特征选择,就是从一组数量为N的特征中选择出一组数量为M的最优特征, N>M)这里有两个问题要解决,1、选择一种可分性判据作为最优特征选择的标准;2、 找到一个好的算法,来选择出这组最优特征。下面我们就来介绍几种特征选择的算法。 个最简单的思路是:我们假设N个特征之间相互独立,并且使用的可分性判据满足 可加性:J(X)=∑J(x),这时候我们只要把N个特征每个单独使用时的可分性判据 J(x)计算出来,然后从大到小排序:J(x)>J(x)>…>J/(x),选择出前M个特征 就是一组最优的特征。然而问题往往没有这么简单,这种特征独立性假设多数情况下并不成 立,并且可分性判据也不一定满足可加性。 另外一个简单的思路是(穷举法):对从N中选择出M个特征的所有组合情况都计算其 可分性判据,然后选择出其中的最大者作为解决方案。当N的数值比较小时,这种方法一 定是可行的,然而当N比较大时,这个组合数会非常大,比如N=100,M=10时,组合 数的数量级是103,当N=20,M=10时,组合数为184756。将所有的组合都计算一遍 显然是不现实的。因此我们需要有一个搜索算法来进行特征选择 最优搜索算法一分支定界算法 到目前为止唯一能够找到最优解的算法是“分支定界”算法。它所利用的是可分性判据
48 ( ) ( ) ( ) ( ) ( ) ln i ij ij i j p I E l p d p = = X X X X X X X 同样 j 类对 i 类的平均可分性信息： ( ) ( ) ( ) ( ) ( ) ln j ji ji j i p I E l p d p = = X X X X X X X 散度 P J 定义为区分 i 类和 j 类的总平均信息： ( ) ( ) ( ) ( ) ln i P ij ji i j j p J I I p p d p = + = − X X X X X X 从 P J 的定义可以看出，当两类分不完全性同 p p (X X = i j ) ( ) 时， 0 P J = ；当两 类完全可分时， P J = + 。 基于概率的可分性判据优点是直接与识别的错误率相联系，缺点是需要已知各个类别类 概率密度函数，只有当我们预先已知各类别的概率分布时，才可以利用训练样本集合估计出 概率密度函数，但是对很多实际问题来说各类别的概率分布情况我们是无法预先知道的。 5.3 特征选择 所谓特征选择，就是从一组数量为 N 的特征中选择出一组数量为 M 的最优特征， （ N M ）这里有两个问题要解决，1、选择一种可分性判据作为最优特征选择的标准；2、 找到一个好的算法，来选择出这组最优特征。下面我们就来介绍几种特征选择的算法。 一个最简单的思路是：我们假设 N 个特征之间相互独立，并且使用的可分性判据满足 可加性： ( ) ( ) 1 N i i J J x = X = ，这时候我们只要把 N 个特征每个单独使用时的可分性判据 J x( i) 计算出来，然后从大到小排序： J x J x J x ( 1 2 ) ( ) ( N ) ，选择出前 M 个特征 就是一组最优的特征。然而问题往往没有这么简单，这种特征独立性假设多数情况下并不成 立，并且可分性判据也不一定满足可加性。 另外一个简单的思路是(穷举法)：对从 N 中选择出 M 个特征的所有组合情况都计算其 可分性判据，然后选择出其中的最大者作为解决方案。当 N 的数值比较小时，这种方法一 定是可行的，然而当 N 比较大时，这个组合数会非常大，比如 N =100，M =10 时，组合 数的数量级是 3 10 ，当 N = 20， M =10 时，组合数为 184756。将所有的组合都计算一遍 显然是不现实的。因此我们需要有一个搜索算法来进行特征选择。 一、最优搜索算法—分支定界算法 到目前为止唯一能够找到最优解的算法是“分支定界”算法。它所利用的是可分性判据
中的单调性质:Jn(x,x2…,x)≤J(x1,x,…x,x+),我们前面定义的各种判据都满 足这个性质 1.分支定界的思想 分支定界算法实际上是对一个特征选择的搜索树进行搜索,下面先以N=6,M=2的 情况来说明一下搜索树 3 4o5o5 456566566656666 在搜索树中根节点x0代表全部特征的集合{x,x2,…,x},每向下一级节点代表从集 合中删除一个特征,节点边上的数字表示在这一级中删除的特征,比如A节点表示删除x,特 征,代表{x,x…,x},因为最后要保留2个特征,因此树的级数为N-M=4。每一个 叶节点代表一种组合,比如C节点代表{x1,x}。 由于可分性判据具有单调性,因此在搜索树中的节点具有这样的性质:每个节点代表的 特征集合的可分性判据要大于其后继节点代表的特征集合的可分性判据,比如 J(4)≥J(B)≥J(C) 根据这样的性质,我们就可以有如下的搜索算法 2.分支定界算法(不严格) 1)搜索从右向左进行,首先设置一个界值B,初始化为B=0: 2)如果当前节点没有分支,则向下搜索,直到叶节点为止,计算叶节点代表的特征集合的 可分性判据,如果大于界值B,则将B替换为这个判据值,并记录这个特征集合,作 为当前的最优选择;向上回溯,直到有节点有未搜索过的分支为止,按照从右向左的顺 序搜索其子节点; 3)如果当前节点有分支,则计算当前节点代表的特征集合的可分性判据,如果小于界值 B,则中止该节点向下的搜索,因为其子节点的可分性判据已经不可能大于B了。否 则按照从右向左的顺序搜索其子节点。 分支定界算法的计算时间是不确定的,同最优解分支所在位置有关,如果最优解分支在 最右端,并且去掉x1或x2的可分性判据均小于最优解,则搜索时间最短,只需计算3组可
49 中的单调性质： J x x x J x x x x ij N ij N N ( 1 2 1 2 1 , , , , , , , ) ( + ) ，我们前面定义的各种判据都满 足这个性质。 1. 分支定界的思想 分支定界算法实际上是对一个特征选择的搜索树进行搜索，下面先以 N = 6，M = 2 的 情况来说明一下搜索树。 4 5 6 5 6 6 5 6 6 6 5 6 6 6 6 3 4 5 4 5 5 4 5 5 5 2 2 3 3 3 4 4 4 A B C X0 1 在搜索树中根节点 X0 代表全部特征的集合 x x x 1 2 6 , , , ，每向下一级节点代表从集 合中删除一个特征，节点边上的数字表示在这一级中删除的特征，比如 A 节点表示删除 2 x 特 征，代表 x x x 1 3 6 , , , ，因为最后要保留 2 个特征，因此树的级数为 N M− = 4 。每一个 叶节点代表一种组合，比如 C 节点代表 x x 1 4 , 。 由于可分性判据具有单调性，因此在搜索树中的节点具有这样的性质：每个节点代表的 特征集合的可分性判据要大于其后继节点代表的特征集合的可分性判据，比如： J A J B J C ( ) ( ) ( ) 根据这样的性质，我们就可以有如下的搜索算法。 2. 分支定界算法（不严格） 1) 搜索从右向左进行，首先设置一个界值 B ，初始化为 B = 0 ； 2) 如果当前节点没有分支，则向下搜索，直到叶节点为止，计算叶节点代表的特征集合的 可分性判据，如果大于界值 B ，则将 B 替换为这个判据值，并记录这个特征集合，作 为当前的最优选择；向上回溯，直到有节点有未搜索过的分支为止，按照从右向左的顺 序搜索其子节点； 3) 如果当前节点有分支，则计算当前节点代表的特征集合的可分性判据，如果小于界值 B ，则中止该节点向下的搜索，因为其子节点的可分性判据已经不可能大于 B 了。否 则按照从右向左的顺序搜索其子节点。 分支定界算法的计算时间是不确定的，同最优解分支所在位置有关，如果最优解分支在 最右端，并且去掉 1 x 或 2 x 的可分性判据均小于最优解，则搜索时间最短，只需计算 3 组可
分性判据;如果每个分支的可分性判据都大于其左端分支的可分性判据,则搜索时间最长, 需计算可分性判据的次数可能>15次。 次优搜索算法 1.顺序前进法( Sequential Forward Selection.,SFS) 每次从未入选的特征中选择一个特征,使得它与已入选的特征组合到一起所得到的可分 性判据最大,直到特征数增加到M为止。用x表示在第k步时的特征集合,搜索算法如 1)开始时,X6=⑦,从N个特征中选择一个J(x)最大的特征,加入已选特征集, X1={x} 2)在第k步,Xk中包含已经选择的k个特征,对未入选的N-k个特征计算, J(xU(x),其中j=12…,N-k,并且按照由大到小排序,将可分性判据 最大的特征x加入Xk,Xn=XU{x} 3)直到所选的特征数等于M为止 2.顺序后退法( Sequential Backward Selection,SBS) 同顺序前进法的过程刚好相反,最开始时取X0={x1…,x},每次从中剔除一个特征, 使得剩余的特征可分性判据最大 3.增1减r法(l-r法) 前两种方法可以进一步改进,比如每次不是加入1个特征,而是加入l个特征;或者每 次不是剔除一个特征,而是剔除r个特征。这样的效果要比每次加1或减1的效果好,但是 计算量要增大。 另外一种改进方法是将SFS和SBS结合,先使用SFS算法逐个选入l个最佳特征,然 后使用SBS算法逐个剔除r个最差特征,l>r,再使用SFS算法增加l个特征,再使用SBS 剔除r个特征, 直到选出M个特征为止。 54特征提取 特征抽取的方法很多,下面我们以其中的一种一基于离散KL变换DKLT的特征抽取, 其它方法与此类似 设原始特征为N为矢量X=(x,x…,x),均值矢量m=EX],相关矩阵 R、=E[x]·协方差矩阵Cx=E(X-m)(X-m) 我们可以对X作如下的标准正交变换,将其变为矢量Y=(y,y2,…,y)
50 分性判据；如果每个分支的可分性判据都大于其左端分支的可分性判据，则搜索时间最长， 需计算可分性判据的次数可能 15 次。 二、次优搜索算法 1. 顺序前进法（Sequential Forward Selection, SFS） 每次从未入选的特征中选择一个特征，使得它与已入选的特征组合到一起所得到的可分 性判据最大，直到特征数增加到 M 为止。用 Xk 表示在第 k 步时的特征集合，搜索算法如 下： 1) 开始时， X0 = ，从 N 个特征中选择一个 J x( i) 最大的特征，加入已选特征集， X x 1 = i ； 2) 在第 k 步， Xk 中包含已经选择的 k 个特征，对未入选的 N k − 个特征计算， J X x ( k j ) ，其中 j N k = − 1, 2, , ，并且按照由大到小排序，将可分性判据 最大的特征 l x 加入 Xk ， X X x k k l +1 = ； 3) 直到所选的特征数等于 M 为止。 2. 顺序后退法 (Sequential Backward Selection, SBS) 同顺序前进法的过程刚好相反，最开始时取 X x x 0 1 = , , N ，每次从中剔除一个特征， 使得剩余的特征可分性判据最大。 3. 增 l 减 r 法（ l r − 法） 前两种方法可以进一步改进，比如每次不是加入 1 个特征，而是加入 l 个特征；或者每 次不是剔除一个特征，而是剔除 r 个特征。这样的效果要比每次加 1 或减 1 的效果好，但是 计算量要增大。 另外一种改进方法是将 SFS 和 SBS 结合，先使用 SFS 算法逐个选入 l 个最佳特征，然 后使用 SBS 算法逐个剔除 r 个最差特征， l r ，再使用 SFS 算法增加 l 个特征，再使用 SBS 剔除 r 个特征，…，直到选出 M 个特征为止。 5.4 特征提取 特征抽取的方法很多，下面我们以其中的一种—基于离散 K-L 变换(DKLT)的特征抽取， 其它方法与此类似。 设原始特征为 N 为矢量 ( 1 2 , , , ) T N X = x x x ，均值矢量 m X = E ，相关矩阵 T = E X R XX ，协方差矩阵 ( )( ) T = − − E C X m X m X 。 我们可以对 X 作如下的标准正交变换，将其变为矢量 ( 1 2 , , , ) T N Y = y y y :
Y=TX Y的每个分量:y2=TX,其中T为一个N×N的标准正交矩阵,T为其第个列矢 量,TT= 也就是说Y的每个分量是X每一个分量的线性组合。 0,i≠j 同样X可以表示为: x=(r)y=TY=(x…x)=∑ 我们要进行特征提取,也就是要用Y的M项来代替X,这种代替必然带来误差,下面 我们来对这个误差进行估计: 令:x=yT,1≤M<N,引入的均方误差为 x-x)(x-8)=-E[ ∑TE[X]T=∑TRT 这又变成一个优化问题,我们希望寻找到一个标准正交矩阵T,使得(M)最小,因 此可以去这样的准则函数: J=∑TR、I-∑4(TT-) 第一项保证均方误差最小,第二项保证T为标准正交矩阵,λ为一待定常数 T (Rx-D)T=0,i=M+1 即:RxT=AT,很明显λ为相关矩阵Rx的特征值,T为对应于的特征矢量,由 于R是一个实对称矩阵,所以TT2,…T相互正交,T为一个正交矩阵。均方无差 e2(M)=∑TRxT=∑TT=∑ i=M+ i=M+I i=M+1
51 1 2 T T T N = T T T Y = T X X T Y 的每个分量： T i i y = T X ，其中 T 为一个 N N 的标准正交矩阵， Ti 为其第 i 个列矢 量， 1, 0, T i j i j i j = = T T 。也就是说 Y 的每个分量是 X 每一个分量的线性组合。 同样 X 可以表示为： ( ) ( ) 1 1 2 1 2 1 N T N i i i N y y y y − = = = = = X T Y TY T T T T 我们要进行特征提取，也就是要用 Y 的 M 项来代替 X ，这种代替必然带来误差，下面 我们来对这个误差进行估计： 令： 1 ˆ M i i i y = X T = ，1 M N ，引入的均方误差为： ( ) ( ) ( ) 2 2 1 1 N N T T i i i i M i M e M E E y E y y = + = + = − − = = X X X X 1 1 N N T T T i i i i i M i M E = + = + = = T XX T T R T X 这又变成一个优化问题，我们希望寻找到一个标准正交矩阵 T ，使得 ( ) 2 e M 最小，因 此可以去这样的准则函数： ( ) 1 1 1 N N T T i i i i i i M i M J = + = + = − − T R T T T X 第一项保证均方误差最小，第二项保证 T 为标准正交矩阵， i 为一待定常数。 ( i i ) i J = − = R I T 0 X T ，i M N = +1, , 即： R T T X i i i = ，很明显 i 为相关矩阵 RX 的特征值， Ti 为对应于 i 的特征矢量，由 于 RX 是一个实对称矩阵，所以 1 2 , , . T T TN 相互正交， T 为一个正交矩阵。均方无差： ( ) 2 1 1 1 N N N T T i i i i i i i M i M i M e M = + = + = + = = = T R T T T X
根据矩阵论,有这样的结论:一个N×N的正定实对称矩阵有N个特征值和特征矢量 这些特征矢量之间是正交的。相关矩阵Rx就是一个实对称矩阵,当训练样本足够多时,也 可以满足正定性,根据上式我们知道,当要从N维特征中提取出M维特征时,我们只需要 统计出特征相关矩阵Rx,然后计算其特征值和特征矢量,选择对应特征值最大的前M个 特征矢量作成一个N×M特征变换矩阵T,就可以完成特征提取。步骤如下: 利用训练样本集合估计出相关矩阵Rx=E|XX: 2、计算Rx的特征值,并由大到小排序:A≥2…≥A,以及相应的特征矢量: T,T2…T 3、选择前M个特征矢量作成一个变换矩阵T=[TT2…T] 4、在训练和识别时,每一个输入的N维特征矢量X可以转换为M维的新特征矢量: Y=TX 这种方法是利用相关矩阵Rx进行变换,同样也可以利用协方差矩阵Cx进行变换,还 可以利用样本的散度矩阵S,Sg,S或者SnS进行变换。过程都是一样的,需要计算 特征值和特征向量,选择最大的M个特征值对应的特征矢量作出变换矩阵 例5
52 根据矩阵论，有这样的结论：一个 N N 的正定实对称矩阵有 N 个特征值和特征矢量， 这些特征矢量之间是正交的。相关矩阵 RX 就是一个实对称矩阵，当训练样本足够多时，也 可以满足正定性，根据上式我们知道，当要从 N 维特征中提取出 M 维特征时，我们只需要 统计出特征相关矩阵 RX ，然后计算其特征值和特征矢量，选择对应特征值最大的前 M 个 特征矢量作成一个 N M 特征变换矩阵 T ，就可以完成特征提取。步骤如下： 1、 利用训练样本集合估计出相关矩阵 T = E X R XX ； 2、 计算 RX 的特征值，并由大到小排序： 1 2 N ，以及相应的特征矢量： 1 2 , , , T T TN ； 3、 选择前 M 个特征矢量作成一个变换矩阵 T T T T = 1 2 M ； 4、 在训练和识别时，每一个输入的 N 维特征矢量 X 可以转换为 M 维的新特征矢量： T Y = T X。 这种方法是利用相关矩阵 RX 进行变换，同样也可以利用协方差矩阵 CX 进行变换，还 可以利用样本的散度矩阵 SW ，SB ，ST 或者 1 W B − S S 进行变换。过程都是一样的，需要计算 特征值和特征向量，选择最大的 M 个特征值对应的特征矢量作出变换矩阵。 例 5.1