= d:(X)-d,(X)可知d2(X)是ds(X)和dz(X)的线性组合，换句话说，ds(X)和dz(X）是独立的，而d23（X）是不独立的，且在二维空间理，三个判决函数必须相交于一点，如图4-5。d(X)-d(x)=0X24d(X)-d(X)=0d,>dd>dsd.sdd>dAd>dd>dd(X)-d(X)=0图4-5多类情况三从图4-5可以看出，三个类别的分布情况来看，它们满足第二种情况的判决规则，且无不确定区。也就是该类方法的判决函数，对于c个类别来说，独立方程式为c-1个，而非の,/の两分法的c(c-1)/2个。尽管有此差别，该类方法的判别式d,(X)>d,(X)与の,/の,两分法的判别式d,(X)>0相同。因此，该方法此时也被转变成の,/の,二分法问题。4.1.3广义线性判别函数线性判别函数是形式最为简单的判别函数，但在实际应用中有较大的局限性，对稍复杂一些的情况，线性判别函数就有可能失效。例如，在一维空间中的两类模式，其分布如图4-6所示，两类模式的类域分布为Q：(-00,α)和(b,o)，Q2,:(a,b)。若要将两类模式正确分类，则需设计一个一维样本的分类器，满足如下性能(X<b或X>a,Xe0)如果、(4-15)b≤X<a, Xeo,g(x) 4bC0W,W2W图4-6二次判别函数举例
13 12 d X d X ( ) ( ) 可知 23 d X( ) 是 13 d X( ) 和 12 d X( ) 的线性组合，换句话说， 13 d X( ) 和 12 d X( ) 是独立的， 而 23 d X( ) 是不独立的，且在二维空间理，三个判决函数必须相交于一点，如图4-5。 图4-5 多类情况三 从图4-5可以看出，三个类别的分布情况来看，它们满足第二种情况的判决规则，且无 不确定区。也就是该类方法的判决函数，对于c个类别来说，独立方程式为c-1个，而非 / i j 两分法的c(c-1)/2个。尽管有此差别，该类方法的判别式 ( ) ( ) i j d X d X 与 / i j 两分法的 判别式 ( ) 0 ij d X 相同。因此，该方法此时也被转变成 / i j 二分法问题。 4.1.3广义线性判别函数 线性判别函数是形式最为简单的判别函数，但在实际应用中有较大的局限性，对稍复 杂一些的情况，线性判别函数就有可能失效。例如，在一维空间中的两类模式，其分布如图 4-6 所示，两类模式的类域分布为 1 ：( , ) ( , ) a b 和 ， 2 ：( , ) a b 。若要将两类模式正确分 类，则需设计一个一维样本的分类器，满足如下性能 1 2 , , X b X a X b X a X 或 如果 (4-15) o a x g x( ) bw1 w2 w3 图 4-6 二次判别函数举例
显然，这两类模式不是线性可分的，式（4-13）的分类器无法采用线性判别函数实现针对这种情况，如果设计二次判别函数(4-16)d(X)=(X-a)(X-b)=X-(a+b)X+ab及其相应的决策规则[d(X)>0,X 0(4-17)[d(X)≤0, X 0,如图4-6所示，此时dX）是X的非线性函数。由此可见，样本原来在一维空间线性不可分，但当转换到二维空间时，样本就变成线性可分了。由于线性判别函数形式简单、计算方便，因此人们希望能找到一种能将非线性可分问题转化为线性可分问题的方法。其思路是选择一种映射X→Y，即将原样本特征向量X映射成另一向量Y，从而可以采用线性判别函数的方法。例如对于图4-6的二次函数情况，其一般式可表示成d(X)=C +cx+c2x?(4-18)如果采用映射X一Y，使y)1Y=Vy3则判别函数d(X）又可表示成3d(X)=d-Za,y:(4-19)1=1aC其中，a=。此时d(X）被称为广义线性判别函数，a称为广义权向量。因此a(a)(C2一个原属二次函数的分类问题就转化为一个线性判别函数问题。事实上，可以将这类方法一般化，任何形式的高次判别函数都可转化成线性判别函数来处理。设样本集模式X是在原始的n维特征空间是非线性可分的，对各模式X,进行非线性变换T：X"→Y"，m>n，使得样本模式在特征空间Y"中是线性可分的，也即分类界面是线性的。需要指出的是由于m>n，将非线性函数用映射的方法变成线性函数的形式，但同时也产生维数增加的问题。非线性判别函数的典型形式是非线性多项式函数。设一训练用n维样本模式集(X在模式空间X中线性不可分，非线性判别函数形式如下d(X)=wf.(X)+w2J2(x)+...+ w.J.(X) +Wn+1(4-20)式中f.(X)，i=l,2,,n是模式X的单值实函数，且fd+(X)=1，由于变换函数f.(X)形式是多种多样的，所以式(4-18)可以有多个具体的变形，,(X)取什么形式及d（X）取多少项数，取决于模式类之间非线性分界面的复杂程度
显然，这两类模式不是线性可分的，式（4-13）的分类器无法采用线性判别函数实现， 针对这种情况，如果设计二次判别函数 2 d X X a X b X a b X ab ( ) ( )( ) ( ) (4-16) 及其相应的决策规则 1 2 ( ) 0, ( ) 0, d X X d X X (4-17) 如图 4-6 所示，此时 d X( ) 是 X 的非线性函数。由此可见，样本原来在一维空间线性不可分， 但当转换到二维空间时，样本就变成线性可分了。由于线性判别函数形式简单、计算方便， 因此人们希望能找到一种能将非线性可分问题转化为线性可分问题的方法。其思路是选择一 种映射 X→Y，即将原样本特征向量 X 映射成另一向量 Y，从而可以采用线性判别函数的方 法。例如对于图 4-6 的二次函数情况，其一般式可表示成 2 0 1 2 d X c c x c x ( ) (4-18) 如果采用映射 X→Y，使 1 2 2 3 y 1 Y y x y x 则判别函数 d X( ) 又可表示成 3 1 ( ) T i i i d X a Y a y (4-19) 其中， 1 0 2 1 3 2 a c a a c a c 。此时 d X( ) 被称为广义线性判别函数， a 称为广义权向量。因此 一个原属二次函数的分类问题就转化为一个线性判别函数问题。事实上，可以将这类方法一 般化，任何形式的高次判别函数都可转化成线性判别函数来处理。设样本集模式 Xi 是在 原始的 n 维特征空间是非线性可分的，对各模式 Xi 进行非线性变换 : n m T X Y ，m n ， 使得样本模式在特征空间 m Y 中是线性可分的，也即分类界面是线性的。需要指出的是由于 m n ，将非线性函数用映射的方法变成线性函数的形式，但同时也产生维数增加的问题。 非线性判别函数的典型形式是非线性多项式函数。设一训练用 n 维样本模式集{X}在模 式空间 X 中线性不可分，非线性判别函数形式如下 d w f w f w f w X X X X 1 1 2 2 1 n n n (4-20) 式中 f X i n i , 1,2, , 是模式 X 的单值实函数，且 1 1 d f X ，由于变换函数 f X i 形式是多种多样的，所以式(4-18)可以有多个具体的变形， f X i 取什么形式及 d X 取多少项数，取决于模式类之间非线性分界面的复杂程度
定义广义形式的模式向量为Y =[y,y2, ",ym, } =[f(x),J(x), m(x),1]这里Y空间的维数m高于X空间的维数n，（4-18)式可写为d(X)=w'Y=d()(4-21)式中，W=[wi,w2,",we,W]”是增广向量，Y是增广模式向量，其所在的空间是一个m维的空间，称为Y空间。至此，非线性函数d(X)已经变成线性函数d(Y）。也就是说，完成了从非线性判别函数到线性判别函数的转化，这里d(Y）也称为广义线性判别函数。当非线性判别函数d(X）为二次多项式时，d(X）的一般形式为d(X)-*++*+wm(4-22)1=1i=l此时，选取f.(X)为二次函数和一次函数，即可把d(X)转化为线性函数d()。下面讨论变换前面特征向量维数的变化，式（4-20）的左边前两项是X各分量的二次项求和式，第一个求和式有n项，第二个求和项有n(n-1)/2；第三项有n项，是X各分量的一次项求和式。所以，d(X)的总项数为n+n(n-1)/2+n+1=(n+1)(n+2)/2，变换后的特征空间的维数(n+1)(n+2)/2-1=n(n+3)/2。用广义线性判别函数虽然可以将非线性问题转化为简单的线性问题来处理，但是实现这种转化的非线性变换的形式可能非常复杂。另外，在原空间X中模式样本X是n维向量，在新空间Y中，Y是m维向量，通常m比n大许多，经过上述变换，维数大大增加了。例如，当非线性判别函数d(X）为二次多项式时，n维特征向量需要映射为n(n+3)/2特征向量。事实上，当d(X)为r次多项式时，变换后的特征向量的维数为(n+r)!n!r!。样本模式特征维数的增加会导致计算量的迅速增加，以致计算机难以处理，这就是所谓的“维数灾难”。4.1.4线性分类器的主要特性及设计步骤1.线性分类器的主要特性1）模式空间与超平面设有n维模式向量X，则以X的n个分量为坐标变量的欧式空间称为模式空间。在模式空间里，模式向量可以表示成一个点，也可以表示成从原点出发到这个点的一个有向线段。当模式类别线性可分时，判别函数的形式是线性的，剩下的问题就是确定一组系数，从而确定一个符合条件的超平面。对于两类问题，利用线性判别函数d(X）进行分类，就是用超平面d(X）=0把模式空间分成两个决策区域。设判别函数为(4-23)d(X)=WxX+W,x,+..+w,x,+WnI=WX+WnI式中，W。=w,w2w，X=x,x2,,x,，则由d(X)确定的超平面为d(X)=WX+Wai=0(4-24)
定义广义形式的模式向量为 [ , , , ,1] , , , ,1 1 2 1 2 T T Y y y y f X f X f X m m 这里 Y 空间的维数 m 高于 X 空间的维数 n ，(4-18)式可写为 T d X W Y d Y （4-21） 1 2 1 , , , , T 式中，W w w w w k k 是增广向量， Y 是增广模式向量，其所在的空间是一个 m 维的空间，称为 Y 空间。至此，非线性函数 d X( ) 已经变成线性函数 d Y( ) 。也就是说， 完成了从非线性判别函数到线性判别函数的转化，这里 d Y( ) 也称为广义线性判别函数。 当非线性判别函数 d X 为二次多项式时， d X 的一般形式为 1 2 1 1 1 1 1 n n n n ii i ij i j i i n i i j i i d X w x w x x w x w （4-22） 此时，选取 f X i 为二次函数和一次函数，即可把 d X 转化为线性函数 d Y 。下面讨论 变换前面特征向量维数的变化，式（4-20）的左边前两项是 X 各分量的二次项求和式，第 一个求和式有 n 项，第二个求和项有 n n( 1) / 2 ；第三项有 n 项，是 X 各分量的一次项求 和式。所以， d X 的总项数为 n n n n n n ( 1) / 2 1 1 2 / 2 ，变换后的特征 空间的维数 n n n n 1 2 / 2 1 ( 3) / 2 。 用广义线性判别函数虽然可以将非线性问题转化为简单的线性问题来处理，但是实现 这种转化的非线性变换的形式可能非常复杂。另外，在原空间 X 中模式样本 X 是 n 维向量， 在新空间 Y 中， Y 是 m 维向量，通常 m 比 n 大许多，经过上述变换，维数大大增加了。例 如，当非线性判别函数 d X 为二次多项式时， n 维特征向量需要映射为 n n( 3) / 2 特征 向量。事实上，当 d X 为 r 次多项式时，变换后的特征向量的维数为 ( )! ! ! n r n r 。样本 模式特征维数的增加会导致计算量的迅速增加，以致计算机难以处理，这就是所谓的“维数 灾难”。 4.1.4 线性分类器的主要特性及设计步骤 1．线性分类器的主要特性 1）模式空间与超平面 设有 n 维模式向量 X ，则以 X 的 n 个分量为坐标变量的欧式空间称为模式空间。在模 式空间里，模式向量可以表示成一个点，也可以表示成从原点出发到这个点的一个有向线段。 当模式类别线性可分时，判别函数的形式是线性的，剩下的问题就是确定一组系数，从而确 定一个符合条件的超平面。对于两类问题，利用线性判别函数 d X( ) 进行分类，就是用超平 面 d X( ) 0 把模式空间分成两个决策区域。 设判别函数为 1 1 2 2 1 0 1 ( ) T n n n n d X w x w x w x w W X w （4-23） 式中， 0 1 2 , , T W w w w n ， 1 2 , , , T X x x x n ，则由 d X( ) 确定的超平面为 0 1 ( ) 0 T d d X W X w （4-24）
为了说明线性判别函数中向量W。的意义，假设在该决策平面上有两个特征向量X，与X，，如图（4-7）（a）所示，将X与X,代入式（4-22），则有WTX,+Wn+ =W"X,+wn(4-25)也即w"(X,-X,)=0(4-26)其中，（X，一X，）也是一个向量，（4-24)式的几何意见是向量W。与该平面上任两点组成的向量(X,-X,)正交。也就是说，Wo就是d(X)=0所确定超平面的法线向量，方向由超平面的负侧指向正侧。设超平面的单位法线向量为U，则有W.U=(4-27)I w.l式中的W。可理解为向量W。的模值，由下式计算得到wl=w+w+..+w(4-28)设X为不在超平面上的模式点，将X向超平面投影得向量X，，并构造向量R，如图（4-7）（b）所示，由式（4-25）有W.R=r.U=rI w.ll式中，r为X到超平面的垂直距离。这样，X就可以表示成W.X=X,+R=X,+r(4-29)Iw.ll将（4-26）代入式（4-23）得到Wo. (w .) (4-30)d(X)=w(X, +rw.llw.因X，位于超平面上，故式（4-27）中第一项为零，应用WTW。=W。IP，得d()= W)(4-31)因此，X到超平面的距离为d(X)r(4-32)IIw,II图（4-7）（b）中X位于超平面的正侧，因而d（X）>O：若X位于超平面的负侧，则d（X）<0。当d（X）确定后，ⅡW。Ⅱ为常数，式（4-29）表明点X到超平面的代数距离（带正负号）正比于d（X）函数值。也可以看出，对于两类问题，可按两类样本到决策面距
为了说明线性判别函数中向量 W0 的意义，假设在该决策平面上有两个特征向量 X1 与 X2 ，如图（4-7）（a）所示，将 X1 与 X2 代入式（4-22），则有 0 1 1 0 2 1 T T W X w W X w n n （4-25） 也即 0 1 2 ( ) 0 T W X X (4-26) 其中， 1 2 ( ) X X 也是一个向量，(4-24)式的几何意见是向量 W0 与该平面上任两点组成的 向量 1 2 ( ) X X 正交。也就是说，W0就是 d X( ) 0 所确定超平面的法线向量，方向由超平 面的负侧指向正侧。设超平面的单位法线向量为 U，则有 0 0 W U W (4-27) 式中的 W0 可理解为向量 W0 的模值，由下式计算得到 2 2 2 W w w w 0 1 2 n （4-28） 设 X 为不在超平面上的模式点，将 X 向超平面投影得向量 X p ，并构造向量 R ，如图 （4-7）（b）所示，由式（4-25）有 0 0 W R r r W U 式中，r 为 X 到超平面的垂直距离。这样， X 就可以表示成 0 0 p p W X X R X r W （4-29） 将（4-26）代入式（4-23）得到 0 0 1 0 ( ) ( ) T p n W d X W X r w W 0 0 1 0 0 ( ) T T p n W W X w W r W （4-30） 因 X p 位于超平面上，故式（4-27）中第一项为零，应用 2 0 0 0 || || T W W W ，得 0 d X r W || || （4-31） 因此， X 到超平面的距离为 0 ( ) || || d X r W （4-32） 图（4-7）（b）中 X 位于超平面的正侧，因而 d X 0 ；若 X 位于超平面的负侧， 则 d X 0 。当 d X 确定后， 0 || || W 为常数，式（4-29）表明点 X 到超平面的代数距离 （带正负号）正比于 d X 函数值。也可以看出，对于两类问题，可按两类样本到决策面距