模式识别第二章线性分类器

1、第二章 线性分类器一、 判别函数1、 决策论方法在模式识别中，如果根据模式特息，按照决策论的思路，以一定的数量规则来采取不同的分类决策， 将待识别的模式划分到不同的类别中去，就称为模式识别的决策论方法。在决策论方法中，特征空间被划分成不同的区域，每个区域对应一个模式类，称为决策区域（DeciRegion）。当判定待识别的模式位于某个决策区域时，就它可以划归到对应的类别中。图 1 决策区域需要注意的是：决策区域包含模式类中样本的分布区域，但不等于模式类的真实分布范围。2、 判别函数如果特征空间中的决策区域边界（DeciGi ( x) 0Boundary）可以用一组方程来表示，则将一个模式对应的特

2、征向量 x 代入边界方程中的 Gi ( x) ，确定其正负符号，就可以确定该模式位于决策区域边界的哪一边，从而可以判别其应当属于的类别， Gi ( x) 称为判别函数（Discriminant Function）。判别函数的形式可以是线性的（ Linear）或非线性（第 1 页-linear） 的。例如图 2 就显示了一个非线性判别函数，当 G(x)0 时，可判别模式 x1；当 G(x)0 且 G13(x)0 时，x2；当 G13(x)0 且 G21(x)0 时，x3；当 G21(x)0 时，x1；当 G21(x)0 且 G13(x)0 时，可判别模式 x1；当 G(x)0，可判别 x1；若

3、G(x)0TFFTTFFG2(x)0FTFTFTFG3(x)0FFTFTTF分类决策x 1x 2x 3IR1IR2IR3IR4此时分类决策规则可以用判定表表示为：两两可分的分类不确定区域减少，但至少需要进行 2 次判别才能确定模式的类别划分。（3） 最大值可分如果每个模式类都对应有一个判别函数，一个模式被划归到判别函数值最大的那个模式类中，就称为最大值可分。此时若有 m 个模式类，就有m 个判别函数。图 11 多类问题最大值可分显然，最大值可分是两两可分的特殊情况。此时的分类决策规则为：x k ,当Gk x maxGi (x)1im3、 线性判别函数的几何意义当一个模式位于线性决策边界上时，该

4、模式与决策边界的距离为 0，对应的判别函数值也为 0。直观地可以发现，当一个模式距离决策边界越远时，判别函数的绝对值也应当越大，也就是说判别函数是模式到决策超平面距离远近的一种度量。那么判别函数的几何意义究竟如何呢？下面以二类问题为例来进行分析。如果判别函数 G x 可以将两类分开，则决策边界方程为： G x w x w 0T0设模式 x 距离决策边界的距离为r ，则向量 x 可以表示为其在决策边界上的w投影点所代表的向量 x 和向量r的和，即p第 7 页wG12(x)0TF*FG23(x)0*TFFG31(x)0F*TF分类决策x 1x 2x 3IRwx x rp图 12 线性判别函数的几何

5、意义代入判别函数中，得wT wwG x wx w0 w ( xp r) w0 w xp w0 r rTTTw所以r G x w由此可见，模式 x 到决策边界的距离正比于判别函数值，判别函数的符号代表了距离r 的符号，表示该模式位于决策边界的正侧还是负侧。更一般的情况，权向量w 仅代表决策超平面的法线方向，其长度不会影响决 1，此时的判别函数值就是模式到策边界在特征空间中的位置，完全可以取w决策边界的距离。思考：此时的判别函数与原判别函数相比区别吗？三、 线性分类器设计（DLC， Design of Linear Classifier）1、 线性分类器设计思路（1） 设计目标对于任意两个类之间，

6、都可以使用一个线性判别函数来进行区分， 决第 8 页www策边界方程为： x wT x w 0Gij0其中x n ，即模式对应的特征向量Tw= w , w , w T ，称为权向量12n将其写成n+1 维增广（Augmented）形式，即 x wT xGijx n ,1 ，即n+1 维增广特征向量Tw= w , w , w , w T ，即n+1 维增广权向量12n0此时分类决策规则为：若Gij j ;如果给定一个分好类的样本集，则其中每个样本对应的增广特征向量都是已知的，此时要设计一个线性分类器可以实现两个类的分类决策，就是要求解出一个能使得样本集内所有样本都能划分到正确的类别中的增广权向量

7、w ，这就是线性分类器的设计目标。（2） 求解条件假设用于学习的样本集中有 l 个样本，其中有 li 个属于i 类，对应的特征向量分别为(li ) ；有 l 个属于 类，对应的特征向量分别为jjy(1) , y(2) , y(lj ) 。则增广权向量 w 应当满足G( x(1) ) wT x(1)0ijG( x(2) ) wT x(2) 0ijG ( x) w x 0(l )T (l ) iiijG( y(1) ) wT y(1) 0ij) w y 0Gij ( y(2)T(2)G( y(lj ) ) wT y(lj ) 0ij当样本数 l n 时，该不等式方程组为不定的，没有有意义的解；当样

8、本 l n 时，该不等式方程组为适定或超定的，有无穷多个解，但是这些解有一定的分布区域，称为解区域。第 9 页图 13 线性分类器设计的解区域如果i 和j 两类线性不可分，则解区域不存在。思考：增广权向量有几个未知数？至少需要几个样本才能求解？（3） 设计思路如果用于学习的训练样本集是线性可分的，则一定有无穷多个解向量 w满足判别函数不等式方程组，设计出的线性分类器也有无穷多个，因此，求取线性分类器的设计结果一定是一个寻找最优解的过程。一般设计思路是：a、 设定一个标量函数 J (w) 为准则函数（Criterion Function）；b、 使准则函数 J (w) 取得极小值的增广权向量w

9、，就是最优解；由于准则函数 J (w) 求极值一般无法直接依据J (w) 0 获得解，只能设w计一个逐步 近的算法来根据训练集求取最优增广权向量w 。（4） 梯度法梯度法（Gradient Method）是传统的求极小值算法之一，它是从一个初始的权向量 w(0) 出发，在每一递推中沿当前准则函数 J (w) 的负梯度方向前进一步，对权向量进行修正（Amend），逐步减小准则函数的值，直至其取得最小值，或近似取得最小值为止，即在第k 1 步递推中w(k 1) w(k ) (k 1)J (w(k)第 10 页其中J (w(k) 是准则函数 J (w) 在w(k) 处的梯度值。因为解空间中每一点的负

10、梯度方向就是准则函数值减少最快的方向，因此梯度法又称为“最速下降法”。梯度法中 (k 1) 0 是第k 1 步递推时对权向量的修正步长（Step-length）。(k 1) 取值越大，求解的速度越快，但求解精度越差，容易过冲甚至振荡；(k 1) 取值越小，求解的速度越慢，但求解精度越高。2、 感知器法（1） 感知器模型感知器（Perceptron）是计算机科学家（F. Rosenblatt）状态，是对多个输入量加在 1957 年神经元模型，它没有反馈和权求和后决定输出的值。图 14 感知器模型感知器输出是一个阶跃函数，其输入输出关系为：n( wi xi ) 1,y i1n( wi xi ) 0

11、,i1其中 为输出阈值。显然，感知器可以作为两类的线性分类器。如果已有线性可分的训练样本集，证明，通过分类错误信息调整权值的算法，总可以使权向量收敛到分类错误为 0 的最优解。（2） 样本特征向量的规范化为求解权向量 w ，需要求解不等式方程组第 11 页G( x(1) ) wT x(1)0ijG( x(2) ) wT x(2) 0( x(li ) ) wT x(li ) ( y(1) ) wT y(1) 0ij0GijGij(2) w y 0T (2)Gij ( yG( y(lj ) ) wT y(lj ) 0ij该方程组的不等式有两种形式，不便于处理，因此把属于j 类的样本的增广特征向量取

12、负号，即得到G ( x(1) ) wT x(1) 0ijG( x(2) ) wT x(2) 0ijG ( x) w x 0(l ) T(l ) iiijG ( y(1) ) wT y(1)0ij) w y 0(2)T (2)Gij ( yG( y(lj ) ) wT y(lj ) 0ij此时可用的形式G ( x) wT x 0ij来表示判别函数对所有训练样本集中的样本的取值条件，只是其中属于j类的样本对应的增广特征向量每一分量都为原始值的负值。这一过程称为样本特征向量的“规范化（Normalization）”。（3） 感知器算法感知器算法（PA, Perceptron Algorithm）采用

13、梯度法来求取权向量的最优值。其准则函数定义为：-wT x J (w) xX0其中 X 0 是规范化后的样本集中分类错误的子集。当存在错分样本时，J (w) 0 ；当不存在错分样本时， J (w) 0 ，取得极小值，此时的权向量 w 就是最优解。根据梯度法，每一步递推时的权向量都由前一步的权向量向当前准则函数J (w) 的负梯度方向修正得到，即w(k 1) w(k ) (k 1)J (w(k)而第 12 页J (w(k) ( J (w(k) , J (w(k ) , J (w(k ) , J (w(k ) ) -x w1w1wnw0 xX0即等于规范化后的错分样本特征向量取负号后之和，则w(k

14、1) w(k) (k 1)xxX0这就是感知器算法的递推公式。感知器算法的具体步骤为：设定初始权向量 w(0) ， k 0 ；对训练样本集的所有规范化增广特征向量进行分类，将分类错误a、b、的样本（即不满足 G ( x) wT x 0 的样本）放入集合 X 中；ij0修正权向量： w(k 1) w(k) (k 1)c、xxX0k k 1，返回步骤b，直至所有样本都能被正确分类为止。d、也可采取单样本修正的算法，步骤为：设定初始权向量 w(0) ， k 0 ；从训练样本集中顺序抽取一个样本，将其规范化增广特征向量 x代入到判别函数中计算；a、b、若分类正确（即 G ( x) wT x 0 ）返回

15、到步骤b，抽取下一个样本；c、ij若分类错误（即不满足 G ( x) wT x 0 ），修正权向量：d、ijw(k 1) w(k) (k 1) x返回到步骤b，抽取下一个样本；直至训练样本集中所有样本均被正确分类。e、（4） (k 1) 的选择感知器算法中递推步长 (k 1) 决定了每次对权向量修正的幅度，它的大小会影响权向量求解的速度和精度。一般 (k 1) 的选择有以下一些方式：固定值即 (k 1) 选择固定的非负数；绝对修正在单样本修正算法中，为保证分类错误的样本在对权向量进行一次第 13 页修正后能正确分类，需要满足wT (k 1) x 0w(k 1) w(k) (k 1) x ，得代

16、入递推修正公式wT (k 1) x wT (k)0即(k 1) xT x满足该条件的 (k 1) 称为绝对修正因子。部分修正若取(k 1) ,0 2xT x则称为部分修正。变步长法可以取按照某种规律逐步减少的 (k 1) ，使得算法开始时收敛较快，接近最优解时收敛速度变慢，以提高求解的精度。比较常用的变步长法是取(k 1) 1 , 0k最优步长法在每一步时，通过求准则函数 J (w(k 1) 对于不同的 (k 1) 可以取得的最小值，来确定最优的 (k 1) 。该方法在于：相比采用小步长带来的递推次数增加，每步求最优步长会带来更大的计算量。感知器法例题一：有 4 个训练样本如下：1 类: (0

17、,0)T，(0,1)T2 类: (1,0)T，(1,1)T用感知器算法求其判别函数。解：样本的规范化增广特征向量为X(1)=(0,0,1)T，X(2)=(0,1,1)T，X(3)=(-1,0,-1)T，X(4)=(-1,-1,-1)T， W(0)=(1,1,1)，取 1第 14 页wT (k ) xwT (k) x 01 1) 0 1X (1W T (0)(1) 1 0 1 1) 1 2 0WT (1X (0)(2) 1 11 1) 0 2 0WT (1X(0)(3) 1W(1)=W(0)+X(3)=(0,1,0)T 1 (010) 1 1 0WT X(1)(4) 1W(2)=W(1)+X(4

18、)=(-1,0,-1)T 0 (101) 0 1 0WTX (2)(1) 1 W(3)=W(2)+X(1)=(-1,0,0)T 0 (100) 1 0WTX (3) (2) 1 W(4)=W(3)+X(2)=(-1,1,1)T 1 (1 1 1) 0 0WTX(4)(3) 1W(5)=W(4)+X(3)=(-2,1,0)T 1 (2 10) 1 1 0WTX(5)(4) 1 0 (2 10) 0 0WTX (5)(1) 1 W(6)=W(5)+X(1)=(-2,1,1)T第 15 页 0 1 1) 1 2 0X (2WT (6)(2) 1 11 1) 0 1 0WT (2X(6)(3) 1 1

19、1 1) 1 0WT (2X(6)(4) 1W(7)=W(6)+X(4)=(-3,0,0)T 0 (300) 0 0WTX (7)(1) 1 W(8)=W(7)+X(1)=(-3,0,1)T 0 0 1) 1 1 0WT (3X (8) (2) 1 10 1) 0 2 0WT (3X(8) (3) 1101) 1 2 0WT (3X(8) (4)1 0 01) 0 1 0X (3WT (8) (1) 1 解得权向量为（-3,0,1），决策边界方程为3x1 1 0第 16 页图 15 感知器法例题一感知器法例题二：有 4 个训练样本如下：1 类: (1,0,1)T，(0,1,1)T2 类: (1

20、,1,0)T，(0,1,0)T用感知器算法求其判别函数。解：样本的规范化增广特征向量为X(1)=(1,0,1,1)T，X(2)=(0,1,1,1)T，X(3)=(-1,-1,0,-1)T，X(4)=(0,-1,0,-1)T， W(0)=(0,0,0,0)，取 1 1 0 00 0WTX00 1 1 (0)(1) W(1)=W(0)+X(1)=(1,0,1,1)T 0 1 1 2 0 1WT X01 1 1 (1)(2) 1 11 2 0 1WT X0 1 0 (1)(3) 1W(2)=W(1)+X(3)=(0,-1,1,0)T第 17 页 0 1 00 1 01WTX1 0 (2)(4) 1

21、1 0 00 1 01WTX1 1 1 (2)(1) 0 1 00 01WTX1 1 1 (2)(2) W(3)=W(2)+X(2)=(0,0,2,1)T 1 11 1 0 0WTX020 (3)(3) 1W(4)=W(3)+X(3)=(-1,-1,2,0)T 0 1 10 1 01WTX2 0 (4)(4) 1 1 0 10 1 01WTX2 1 1 (4) (1) 0 1 10 1 01WTX2 1 1 (4)(2) 1 1 10 2 01WTX2 0 (4)(3) 1第 18 页解得权向量为（-1,-1,2,0），决策边界方程为3 0图 16 感知器法例题二（5） 感知器算法分析感知器算

22、法简单明了，对线性可分问题收敛性有理论保证，但它以减少错分样本为求解目标，其最优解为无错分样本的权向量，因此该算法存在以下问题：求解结果落入解区域中则算法停止，不能在解区域的所有解中求得最优解；求解结果与初始权向量、样本处理顺序、递推步长都有关系，即求解结果不确定；对于线性不可分问题无法在允许错分的情况下求得次优解。算法3、（1）线性分类器的松弛求解（Relaxation Solution）对于两类问题，设样本集有 l 个样本，在对所有样本的增广特征向量规范化后，线性分类器的求解即求满足线性不等式方程组G ( x(1) ) wT x(1) 0ijG( x(2) ) wT x(2)0ijGij

23、( x) w x 0(l )T (l )的权向量w ，如该不等式方程组有解，其解为一个区域，包含无穷多个解。对该不等式方程组松弛化， 任意给定一个裕量向量（ Margin Vector ）b (b , b , b ) ，令T1 2l第 19 页G ( x(1) ) wT x(1) b 0ij1G ( x(2) ) wT x(2) b 0ij2Gij ( x) w x bl 0(l )T(l ) 则求解线性不等式方程组再令矩阵转化为求解线性方程组。 x(1)T x(2)T X (l )T x上述线性方程组可写为Xw b当训练样本数l 小于样本特征维数n 时，权向量 w 有无穷多个解，不存在有意义

24、的类别分界线。当l 等于n 时，权向量 w 也有无穷多个解，但这些解是线性相关的，其所决定的分类决策边界均满足：G (x) wT x 0ij所以，分类决策边界有精确解（Exact Solution）。当训练样本数l 大于样本特征维数 n 时，且方程组中的各方程不是线性相关的话，则线性方程组是超定的（Over-determined），权向量 w确解。但是对于此类问题，可采用最小二乘法的方法，求得一个尽可能满足方程的近似解。（2）最小均方误差算法设定误差向量为： e Xw b2 Xw b 2均方误差准则函数为： J (w) e则当均方误差 J (w) 取得最小值时，所求得的权向量w 是最优的。仍然

25、采用梯度法，权向量的递推公式为w(k 1) w(k ) (k 1)J (w(k)因为ll ( xw(k) b ) (w (k ) x bi )2J (w(k ) Xw(k ) b(i )T 2T(i)2ii 1i1所以均方误差准则函数 J (w) 在w(k) 处的梯度为lliJ (w(k) (w (k ) x b ) 2(w (k ) x b ) x 2XT (Xw(k) b)T(i) 2T(i) (i )ii1i 1所以第 20 页w(k 1) w(k) (k 1) 2XT (Xw(k ) b) w(k) (k 1)XT (Xw(k) b)即对任意给定的裕量向量 b ，可根据以上递推公式逐步

26、求解最优的权向量w ，(k 1) 0 是递推修正的步长。该算法称为最小均方误差算Mean Square Error）。值得注意的是，如果任意给定b ，最小均方误差算法得到的最优权向量可能MSE（Least把一个原本线性可分变成一个线性不可分。也就是说，均方误差准则函数取得最小值和线性分类器的不等式方程组成立这两个条件可能无法同时满足。（3）最优的裕量向量 b前述最小均方误差算法中裕量向量 b 是任意给定的，其值将影响最终分类器设计结果。对于一般的线性分类器设计， 希望在求解权向量w 的过程中b也能取得最优值。设求解过程中权向量 w 和裕量向量 b 都可变，若两类线性可分，则最小均方误差准则函数

27、可取得最小值 0，此时决策边界与所有以各样本为中心，以最优裕量向量 b 的各分量为半径指标的圆相切。求取最优裕量向量 b 的过程同样可采用梯度法，在第 k 1 步递推中，有b(k 1) b(k ) (k 1) J (w(k )b(k 1) 0 是递推修正的步长。因为2 J (w(k) 2(Xw(k ) b)bb所以b(k 1) b(k) (k 1) 2(Xw(k ) b(k) b(k) 2(k 1)(Xw(k ) b(k) b(k) 2(k 1)e(k )第 21 页Xw(k) b图 17 最优裕量向量 b由于误差向量e(k ) 有可能大于 0 也可能小于 0，而递推过程必须始终保证b(k 1

28、) 0 ，一种做法是只在e(k ) 0 时进行修正，即取b(k 1) b(k ) (k 1)(e(k )+ e(k ) )若在已知每一步的 b(k ) 后利用J (w(k) 2XT (Xw(k) b) 0w (k )来求取最优的w(k) ，则w(k ) (T b(k)因此有w(k +1) ( ( (T b(k +1)T b(k) (k 1)(e(k)+ e(k) )T b(k) (k 1)(T (e(k)+ e(k) )(k) ) w(k) (k 1)( w(k) (k 1)(XT X)1 w(k)+(k 1)(Te(k )Te(k )Te(k )此时得到一种可同时求取最优权向量w 和最优裕量

29、向量 b 的递推算法，步骤为：a、 设定初始裕量向量b(0) 0 ，初始权向量w(0) (T b(0) ，k=0；第 22 页b、 计算误差向量： e(k ) Xw(k) b(k ) ；c、 对权向量进行递推修正： w(k +1) w(k )+(k 1)(Te(k ) ；d、 对裕量向量进行递推修正： b(k 1) b(k ) (k 1)(e(k )+ e(k ) ) ；e、 k=k+1，返回步骤 b，直至e(k ) 0 ，求得最优解；或者e(k ) 0 ，证明训练样本集线性不可分。T 称为X 的伪逆，可以记为 X# 。该算法称为 Ho-Kashyap 算其中，(法，其收敛性性可分和1 (k

30、1) 0 的条件下已得到证明。思考：为什么可以通过只在e(k ) 0 时修正b(k ) 来保证b(k 1) 0 ？ b(k ) 的绝对值只增不减对最后的最优权向量有影响吗？H-K 算法例题：有 4 个训练样本如下：1 类: (0,0)T，(0,1)T2 类: (1,0)T，(1,1)T用 H-K 算法求其判别函数。解：样化增广特征向量的特征矩阵为0010 1101X 1 1 1 1伪逆为1001010111 0111 01100011011101 001) 1 XT1111 11 11121 01 011 0.50 1 0 121220111011 12 01 0 0.50 12 4 1 0.

31、50.50.251 0.5 0.50.75 1 1 0.5 0.5 0.50.5 0.25 0.5 0.5 0.750.25 第 23 页取b(0) 1,1,1,1T ，则0.5 10.50.5 10.50.5 2, 0,1Tw(0) X#b(0) 5 10.75 11 211100001011 1110e(0) Xw(0) b(0) 0 11 1 1110 11 0111 所以， w(0) 2, 0,1T 就是所求的最优权向量。图 18 H-K 算法例题4、支持向量机（SVM）（1）分类间隔和支持向量对于线性可分的两类问题，其分类决策边界为一 n 维

32、特征空间中的超平面 H，其解有无穷多个。可以在一定的范围内平移超平面 H，只要不达到或者越过两类中距离 H 最近的样本，分类决策边界都可以正确地实现线性分类，中间的裕量为 d，称为分类间隔（Margin of Classification）。在所有线性分类器的解中，虽然都能实现线性分类，但随着权向量的方向不同，分类间隔也会随之变化。显然，具有最大分类间隔的权向量 w优于其他的权向量，因为如果取决策边界到两类最近的样本的距离相等（也就是“居中”划分），此时分类错误的可能性是最小的。第 24 页图 19 分类间隔和支持向量当找到分类间隔最大的最优权向量 w 后，可以发现它是由距离决策边界最近的样本

33、所决定的，这些样本与整个训练集相比数量并不多， 并且除它们以外，其他的样本都不会影响到最优权向量的确定。这些训练集中的少量样本就称为“支持向量（Support Vector）”。（2）支持向量机分类间隔可以由支持向量到分类决策边界的距离来决定，即d 2设 Gij ( xs ) =1，则此时最大的分类间隔，等效长度最小的权向量，即max d max minw如何求取到具有最大分类间隔的最优线性分类器，转化为如何求取到长度最小的权向量。支持向量机 SVM（Support Vector Machine）是 Vapnik 和 Cortes 于 1995年首次基于统计学习理论的模式识别方法，由于它在解决

34、有限数量样本、非线性及度模式识别问题上所具有的优秀性能，以及很强的泛化能力，得到了研究者普遍的重视和广泛的应用。支持向量机的主要特点有：所需样本少真正决定具有最大分类间隔的最优线性分类器的是少量的“支持向量”，因此即时用于训练的样本个数少，只要能包含合理的支持向量，就能得到一个最优的训练结果。泛化能力强分类器设计过程是使用训练样本集来实现的， 所得到的分类器一第 25 页2Gij ( x)wGij ( xs )w般都能对训练集实现良好的分类，但是否能对未知的其它样本也取得好的分类结果，就体现了分类器设计算法的泛化能力（ Generalization Ability）。分类器的泛化能力一般用泛化

35、误差界来表示，公式为R(w) Remp (w) (n / h)其中 R(w) 代表设计出的分类器分类错误的总的风险，称为结构风险。它的上界由两部分：一部分是分类器对训练集中的样本分类的误差，称为经验风险 Remp (w) ，另一部分是设计出的分类器对训练集以外的其它样本分类的误差，称为置信风险(n / h) ，它由训练集中的样本数多少和分类决策面方程的非线性程度决定。支持向量机不仅能针对训练集找到最优的分类决策边界， 而且具有最简单的线性形式， 因此其设计出的分类器结构风险小，泛化能力强。能处理非线性分类问题事实上，任意能用非线性方程表达的决策边界，都可以通过向高维度特征空间机来解决。来转化为线性