武汉理工大学：《模式识别》课程授课教案（讲义）第4章 非参数判别分类方法

第4章非参数判别分类方法第2章讨论了贝叶斯决策理论和统计判别方法。贝叶斯分类器采用错误率最小或风险最小作为指标，构造判别函数和决策面，这给出了一般情况“最优”分类器的设计方法，对各种不同的分类器设计技术在理论上都有指导意义。直接使用贝叶斯决策理论需要已知有关样本总体分布的知识，如各类先验概率、类条件概率密度函数，然后计算出样本的后验概率，并以此设计出相应的判别函数与决策面。然而，实际问题中并不一定具备获取准确统计分布的条件，当样本分布未知时，需要借助第3章的理论，进行更困难的参数估计。为此，本章将讨论跳过了统计分布的参数估计，依据不同的准则函数，由样本直接设计出满足准则要求的分类器。这一类分类器设计技术统称为非参数方法的分类器设计技术，在非参数判别方法的设计中，使用什么样的分类决策方法是需要预先由设计者确定，然后利用训练样本集提供的信息确定这些函数中的参数。这是参数与非参数判别方法的一个重要不同点。非参数判别分类方法选择函数类型与确定参数是两个过程，下面就从简单的线性分类器进行讨论学习。4.1线性分类器在本节中，假设所有类别的模式向量都可以用线性分类器正确分类，我们将讨论线性判别函数的定义和计算方法，以及线性分类器的设计方法。4.1.1线性判别函数的基本概念首先考虑两类问题的线性判别函数，设模式向量X是d维的，则两类别问题中线性判别函数的一般形式可表示成d(X)=Wxi+WaX +...+WaXa+Wa+I=WX+Wa+I(4-1)式中，W。=[w,w2,wa，称为权向量或参数向量；X=x,2,xa是d维特征向量，又称模式向量或样本向量；Wa+是常数，称为阅值权。为了简洁起见，式（4-1）也可写成d(X)=wX +w2x +.+waxa+Wa+-1

第 4 章 非参数判别分类方法 第 2 章讨论了贝叶斯决策理论和统计判别方法。贝叶斯分类器采用错误率最小或风险 最小作为指标，构造判别函数和决策面，这给出了一般情况“最优”分类器的设计方法，对各 种不同的分类器设计技术在理论上都有指导意义。直接使用贝叶斯决策理论需要已知有关样 本总体分布的知识，如各类先验概率、类条件概率密度函数，然后计算出样本的后验概率， 并以此设计出相应的判别函数与决策面。然而，实际问题中并不一定具备获取准确统计分布 的条件，当样本分布未知时，需要借助第 3 章的理论，进行更困难的参数估计。为此，本章 将讨论跳过了统计分布的参数估计，依据不同的准则函数，由样本直接设计出满足准则要求 的分类器。这一类分类器设计技术统称为非参数方法的分类器设计技术。 在非参数判别方法的设计中，使用什么样的分类决策方法是需要预先由设计者确定，然 后利用训练样本集提供的信息确定这些函数中的参数。这是参数与非参数判别方法的一个重 要不同点。非参数判别分类方法选择函数类型与确定参数是两个过程，下面就从简单的线性 分类器进行讨论学习。 4.1 线性分类器 在本节中，假设所有类别的模式向量都可以用线性分类器正确分类，我们将讨论线性判 别函数的定义和计算方法，以及线性分类器的设计方法。 4.1.1 线性判别函数的基本概念 首先考虑两类问题的线性判别函数，设模式向量 X 是 d 维的，则两类别问题中线性判 别函数的一般形式可表示成 1 1 2 2 1 0 1 ( )          T d d d d d X w x w x w x w W X w （4-1） 式中， 0 1 2   , ,  T W w w wd ，称为权向量或参数向量；   1 2 , , ,  T X x x xd 是 d 维特征向 量，又称模式向量或样本向量； wd 1 是常数，称为阈值权。为了简洁起见，式（4-1）也可 写成 1 1 2 2 1 ( ) 1 d d d d X w x w x w x w       

XX2=WIX=[w w.. wa(4-2)Wa+I]Xd1式(4-2)中，W=[w,w2"wawa+为增广权向量；X=[x，x2，，xa，1]}为增广特征向量，增广特征向量的全体称为增广特征空间。在给出线性判别函数后，如果满足[d(X)>0, Xe0d(X)<0, Xe02(4-3)d(X)=0,不确定d(X)=O就是相应的决策面方程，在线性判别函数条件下，它对应d维空间的一个超平面。对于两分类问题，如果样本模式为二维特征向量，则所有分布在二维平面的模式样本可以用一条直线划分开来，这条直线就可以作为一个识别分类的依据，其判别函数可以表示为(4-4)d(X)=W +W2x +W=0式中，x，x为坐标变量；Wi，W2，w,为方程参数，决策规则依然为式（4-3），两类二维模式分布的示意图见4-1。Xd(X)=00图4-1两类二维模式的分布注意，判别界面的正负侧，是在训练判别函数的权值时确定的。对于一个两类问题，训练判别函数的方法一般是输入已知类别的训练样本X，当样本属于第一类时，定义d(X)大于零，当样本属于第二类时，定义d(X）小于零，这样做的结果就在几何判别边界划分为“+”侧和“_”侧

  1 2 1 2 1 1 T d d d x x w w w w W X x                    （4-2） 式 (4-2) 中 ，  1 2 1 , , , , T W w w w w  d d  为 增 广 权 向 量 ；  1 2 , , , , 1 T X x x x  d 为增广特征向量，增广特征向量的全体称为增广特征空间。 在给出线性判别函数后，如果满足 1 2 ( ) 0 ( ) 0, ( ) 0, d X X d X X d X             , 不确定 （4-3） d X( ) 0  就是相应的决策面方程，在线性判别函数条件下，它对应 d 维空间的一个超 平面。对于两分类问题，如果样本模式为二维特征向量，则所有分布在二维平面的模式样本 可以用一条直线划分开来，这条直线就可以作为一个识别分类的依据，其判别函数可以表示 为 1 1 2 2 3 d X w x w x w ( ) 0     (4-4) 式中， 1 x , 2 x 为坐标变量； w1 , w2 , w3 为方程参数，决策规则依然为式（4-3），两类二 维模式分布的示意图见 4-1。 d(X)  0 2 x 1 x O 1 2 ＋ － 图 4-1 两类二维模式的分布 注意，判别界面的正负侧，是在训练判别函数的权值时确定的。对于一个两类问题，训 练判别函数的方法一般是输入已知类别的训练样本 X ，当样本属于第一类时，定义 d X( ) 大 于零，当样本属于第二类时，定义 d X( ) 小于零，这样做的结果就在几何判别边界划分为“+” 侧和“-” 侧

样本模式的特征维数不同，决策面方程d(X）的几何形式也不同。在一维空间里，决策面方程d(X）为分界点：在二维空间里，d(X）是一条分界线：在三维空间里，d(X）)是分界面：当维数空间大于3，决策面方程d(X）为超平面。根据判决函数d(X）的数学表达式，有线性的判决函数，也有非线性的判决函数。但是，非线性判决函数一般都可以转变成线性判决函数（又称为广义线性判决函数）。4.1.2多类问题中的线性判别函数下面将讨论多类问题的解决方案，将两类问题进行推广可将应用扩展到多类情况。假设样本整体有の，2,の。共c个模式类，且c≥3。为了把所有的类型分开，存在三种不同的技术途径。一、の,/の,两分法の,/の,两分法的基本思想是通过唯一一个线性判别函数，将属于の,类的模式与其余不属于の,类的模式分开。对于c类问题，如果样本模式是完全线性可分的，则需要c-1个独立的判别函数。为了方便，可建立c个判别函数，形如d,(X)=W)X, i=1,2,", c(4-5)其中，每一个判别函数具有以下功能[d(X)>0 Xe0,i=1,2,..., c(4-6)d(X)<0XE0,通过这类判别函数，把c类问题转为c个属于の和不属于の的问题。若把不属于の记为の，上述问题就成了c个の和の的两类问题，因此称为の/二分法。由上述分析知道，决策面d(X)=WTX=0，把空间划分成两个区域，一个属于の,，另一个属于の,。再考察另一个决策的判别函数d,(X)=W,X（j+i)，其决策面W,X=0同样把特征空间划分成两个区域，一个属于の，，另一个属于の，。这两个决策面分别确定的の和の，类型区域可能会有重叠，这个重叠区域不能由这两个判别函数确定类别。同样，の和の，也可能出现重叠，如果由c个决策面确定的c个属于の，（i=1,2,.，℃）的区域有一个共同的重叠区域时，当样本落入该区域时，这类判别函数不能对它所属的类别做出判决。因此，在使用这类判别函数时，可能会出现两个或两个以上的判别式都大于零，或所有的判别式都小于零的情况。也即特征空间会出现同属于两个类型以上的区域和不属于任何类型的区域，样本落入这些区域时，就无法作出最后判断，这样的区域就是不确定区，用IR标记。样本的类别越多，不确定区IR就越多

样本模式的特征维数不同，决策面方程 d X( ) 的几何形式也不同。在一维空间里，决策 面方程 d X( ) 为分界点；在二维空间里， d X( ) 是一条分界线；在三维空间里， d X( ) 是分 界面；当维数空间大于3，决策面方程 d X( ) 为超平面。根据判决函数 d X( ) 的数学表达式， 有线性的判决函数，也有非线性的判决函数。但是，非线性判决函数一般都可以转变成线性 判决函数（又称为广义线性判决函数）。 4.1.2 多类问题中的线性判别函数 下面将讨论多类问题的解决方案，将两类问题进行推广可将应用扩展到多类情况。假设 样本整体有 1 2 , ,.,   c 共 c 个模式类，且 c  3 。为了把所有的类型分开，存在三种不同 的技术途径。 一、 /  i i 两分法 /  i i 两分法的基本思想是通过唯一一个线性判别函数，将属于 i 类的模式与其余不 属于 i 类的模式分开。对于 c 类问题，如果样本模式是完全线性可分的，则需要 c 1 个独 立的判别函数。为了方便，可建立 c 个判别函数，形如 ( ) T i i d X W X  ，i c 1,2, ， （4-5） 其中，每一个判别函数具有以下功能 ( ) 0 1,2, ( ) 0 i i i i d X X i c d X X           ， （4-6） 通过这类判别函数，把 c 类问题转为 c 个属于 i 和不属于 i 的问题。若把不属于 i 记为 i ， 上述问题就成了 c 个 i 和 i 的两类问题，因此称为 /  i i 二分法。 由上述分析知道，决策面 ( ) 0 T i i d X W X   ，把空间划分成两个区域，一个属于 i ， 另一个属于 i 。再考察另一个决策的判别函数 ( ) T j j d X W X  ( j i  )，其决策面 0 T W Xj  同样把特征空间划分成两个区域，一个属于 j ，另一个属于  j 。这两个决策面分别确定的 i 和 j 类型区域可能会有重叠，这个重叠区域不能由这两个判别函数确定类别。同样，i 和  j 也可能出现重叠，如果由 c 个决策面确定的 c 个属于 i （ i c 1,2, ， ）的区域有一 个共同的重叠区域时，当样本落入该区域时，这类判别函数不能对它所属的类别做出判决。 因此，在使用这类判别函数时，可能会出现两个或两个以上的判别式都大于零，或所有 的判别式都小于零的情况。也即特征空间会出现同属于两个类型以上的区域和不属于任何类 型的区域，样本落入这些区域时，就无法作出最后判断，这样的区域就是不确定区，用IR 标记。样本的类别越多，不确定区IR就越多

d,(M)=0R，可能属于或di.da>odso,d>o.d.dg0,d.dz0不能做出最终判决XEの，还必须检查另外的判决函数d,(X)的值。若d,(X)≤0，j+i才能确定xEの,。所以此时判决规则为[d,(X)>0如果则XEO,。(4-7)d,(X)≤0j+i二、の,/0,两分法の,/の,两分法的基本思想是对c个类别中的任意两个类别の,和の,建立一个判别函数d,(X)，决策面方程d(X)=0，能把の,和の,两个类别区分开，但对其他类别的分类则不提供任何信息。因为c个类别中，任取两个类别的组合数为c(c-1)/2（d,(X)=-d,(X)；即d,(X)=WIX, i,j=1,2,..c(4-8)此时，判别函数具有性质d,(X)=-d,(X)(4-9)每个判别函数具有以下功能>0 XE0,d,(x)(4-10)<0 XE0,从（4-8）式可知，这类判别函数也是把c类问题转变为两类问题，与の,/の,两分法不同的是，两类问题的数目不是c个，而是c(c一1)/2个，并且每个两类问题不是の/の，而是の,/の,。也就是，此时转变成了c(c-1)/2个の,/の,二分法问题。只有一个决策面d(X)=0是不能最后做出X是属于の,还是の，因为d(X)只涉及の,和の，的关系，只能判定样本模式X是位于含有の,类的空间，还是位于の,类的空间，而对它们和别的类型の,（k=1,2.....c,k≠i,k≠j）之间的关系不提供任何信息。要得到X的

图4-2 /  i i 两分法 在二维空间里，图4-2给出了3个类型的决策面 ( ) 0 i d X  （ i 1,2 3， ），图中出现了4 个不确定区。由于不确定区的存在，仅有 ( ) 0 i d X  不能做出最终判决 X i ，还必须检 查另外的判决函数 ( ) j d X 的值。若 ( ) 0 j d X  ， j i  才能确定 i x 。所以此时判决规则 为 如果 ( ) 0 ( ) 0 i j d X d X j i       则 X i 。 （4-7） 二、 /  i j 两分法 /  i j 两分法的基本思想是对 c 个类别中的任意两个类别 i 和 j 建立一个判别函数 ( ) ij d X ，决策面方程 ( ) 0 ij d X  ，能把 i 和 j 两个类别区分开，但对其他类别的分类则不 提供任何信息。因为 c 个类别中，任取两个类别的组合数为 c c( 1) / 2  （ ( ) ( ) ij ji d X d X   ， 即 ( ) T ij ij d X W X  ，i, j 1,2,.c （4-8） 此时，判别函数具有性质 ( ) ( ) ij ji d X d X   （4-9） 每个判别函数具有以下功能 0 ( ) 0 i ij j X d X X         （4-10） 从（4-8）式可知，这类判别函数也是把 c 类问题转变为两类问题，与 /  i i 两分法不 同的是，两类问题的数目不是 c 个，而是 c(c 1)/ 2 个，并且每个两类问题不是 /  i i ，而 是 /  i j 。也就是，此时转变成了 c(c 1)/ 2 个 /  i j 二分法问题。 只有一个决策面 ( ) 0 ij d X  是不能最后做出 X 是属于 i 还是 j ，因为 ( ) ij d X 只涉及 i 和 j 的关系，只能判定样本模式 X 是位于含有 i 类的空间，还是位于 j 类的空间，而 对它们和别的类型 k ( k 1,2,.,c,k  i,k  j )之间的关系不提供任何信息。要得到 X 的

判别结论，必须考察c-1个判决函数。即有判决规则：(4-11)如果d(X)>0，j+i，则Xeの,。三、没有不确定区域的の,/の,两分法这类方法的思想是对c种类型中的每一种类别，均建立一个判决函数，即d,(X)=wx, i=1,2....。(4-12)为了区分出其中的某一个类别の，则需要k个判决函数(k≤c），判别规则为(4-13)如果d(X)>d,(X),ji,则Xeの,。上述判决规则也可以有另一种表示形式为(4-14)如果d,(X)= max (d,(X)),则X e0i=1.2.....显然，对不同的の，k的取值不尽相同，k值的选择与类别之间的相邻关系密切相关。下面举例说明，如图4-4所示，特征空间里有一个五类问题，五个不同的类别可用分段线性函数分开。从图中可以看出，类别の,与其余4个类别均相邻，の,分别与の,和の,相邻，の,分别与の，、の和の相邻。k的选取取决于所考察的类型与其相邻类别的个数，如：の，k=4；0，k=2；对0，k=3。02O00图4-4五类问题下面进一步讨论，该类方法与の,/,两分法的区别，假定c=3，且已建立3个判决函数满足最大值判决规则。d,(X)=WIxd,(X)=w,x(d,(X)=Wx三个类型区域均相邻，有d,(X)=d(X)-d,(X)=(wT-w))X =wx同理ds(X)=W,X, d(X)=W2X 又由dz(X)=d,(X)-d,(X)+d,(X)-d,(X)=[d(X)-d,(X)]-[d,(X)-d,(X))

判别结论，必须考察 c 1 个判决函数。即有判决规则： 如果 ( ) 0 ij d X  ， j i  ，则 X i 。 （4-11） 三、没有不确定区域的 /  i j 两分法 这类方法的思想是对c种类型中的每一种类别，均建立一个判决函数，即 ( ) T i i d X W X  ，i 1,2,.c 。 （4-12） 为了区分出其中的某一个类别 i ，则需要 k 个判决函数( k  c )，判别规则为 如果 ( ) ( ) i j d X d X  ， j  i ，则 X i 。 （4-13） 上述判决规则也可以有另一种表示形式为 如果 1,2, , ( ) max { ( )} i j j k d X d X   ，则 X i （4-14） 显然，对不同的 i ，k 的取值不尽相同， k 值的选择与类别之间的相邻关系密切相关。 下面举例说明，如图4-4所示，特征空间里有一个五类问题，五个不同的类别可用分段线性 函数分开。从图中可以看出，类别 1 与其余4个类别均相邻， 2 分别与 1 和 3 相邻， 5 分 别与 1 、3 和 4 相邻。 k 的选取取决于所考察的类型与其相邻类别的个数，如： 1 ，k  4 ； 2 ， k  2 ；对 5 ，k  3。 1 2 3 4 5 图4-4 五类问题 下面进一步讨论，该类方法与 /  i j 两分法的区别，假定c=3，且已建立3个判决函数， 满足最大值判决规则。 1 1 2 2 3 3 ( ) ( ) ( ) T T T d X W X d X W X d X W X         三个类型区域均相邻，有 12 1 2 1 2 12 ( ) ( ) ( ) ( ) T T T d X d X d X W W X W X      同理 13 13 ( ) T d X W X  ， 23 23 ( ) T d X W X  。 又由 23 1 1 2 3 d X d X d X d X d X ( ) ( ) ( ) ( ) ( )     1 3 1 2     [ ( ) ( )] [ ( ) ( )] d X d X d X d X

= 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)。若要将两类模式正确分类，则需设计一个一维样本的分类器，满足如下性能(Xa,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  函数值。也可以看出，对于两类问题，可按两类样本到决策面距

离的正负号确定其类别。对于式（4-22），当X在原点时，d(X)=Wa+1，原点到超平面的距离为Wd+l(4-33)ro=II WII该式说明超平面的位置是由权值wa+决定的，当wa+=0时，该决策面过特征空间坐标系原点，而wa++0时，则wa+/W。表示了坐标原点到该决策面的距离。如果wa+>0，原点在超平面的正侧；如果wa+10, i=1,2,.,p(4-29)d(X2)0, i=1,2,.",p(4-30)[d(-X2.)>0, i=1,2,,q这样就可以不管原样本的类别属性，将两类模式分开的条件可统一写为d(X)>0，其中

离的正负号确定其类别。 对于式（4-22），当 X 在原点时， 1 ( ) d d X w  ，原点到超平面的距离为 1 0 0 || || wd r W   （4-33） 该式说明超平面的位置是由权值 wd 1 决定的，当 1 0 wd   时，该决策面过特征空间坐标系 原点，而 1 0 wd   时，则 1 0 / w W d  表示了坐标原点到该决策面的距离。如果 1 0 wd   ，原 点在超平面的正侧；如果 1 0 wd   ，原点在超平面的负侧。 O W0 + － X1 X2 (X1－X2) d(X)=0 x2 x1 － O W0 + Xp d(X)=0 x2 X R x1 （a） (b) 图 4-7 点到超平面的距离 2）权空间与权向量解 在模式识别过程中经常将判别函数绘制在权向量空间中。设有式（4-21）的线性判别 函数 1 1 2 2 1 ( ) n n n d X w x w x w x w       则以 1 2 1 , , , , w w w w  n n 为坐标变量构成的空间称为权空间。在权空间里， n1 维增广权向 量 1 2 1 [ , , , , ]T W w w w w   n n 对应该空间中的一个点，可以用从原点出发到这个点的一条有 向线段来表示。 当样本类别线性可分时，判别函数形式 d X( ) 已确定，用知已训练样本确定 d X( ) 的 任务归结为确定符合条件的权向量 1 2 1 [ , , , , ]T W w w w w   d d 。下面以两类问题为例，讨论 线性判别函数形式 d X( ) 权向量的求解问题。 设 1 类有 X11，X12 ，.，X1p p 个增广样本向量， 2 类的 X21，X22 ，.，X2q q 个增广样本向量。建立判别函数的任务是确定 d X  把 1 类和 2 类分开，若线性判别函 数为   T d X W X  ，则有如下不等式成立 1 2 ( ) 0, 1,2, , ( ) 0, 1,2, , i i d X i p d X i q        （4-29） 式（4-29）共包含 p q  个不等式， 如果将 2 的 q 个增广模式都乘以（－1），则式（4-29） 可写为 1 2 ( ) 0, 1,2, , ( ) 0, 1,2, , i i d X i p d X i q         （4-30） 这样就可以不管原样本的类别属性，将两类模式分开的条件可统一写为 d X( ) 0  ，其中