武汉理工大学：《模式识别》课程授课教案（讲义）第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>ods<od>o,d>o.d.dg<odz.d<ted(X)=0IR，可能IR，可能属于或属于或Xdy>0,d.dz<od(X)=0图4-20/の两分法在二维空间里，图4-2给出了3个类型的决策面d（X）=0（i=1,23），图中出现了4个不确定区。由于不确定区的存在，仅有d(X)>0不能做出最终判决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