模式识别郝旷荣Chap4(MSSB-HKR)20081104

1、 4.1 引言4.2 线性分类器4.3 非线性判别函数4.4 近邻法4.5 支持向量机5 本章小结第四章 非参数判别分类方法1学习目的(1) 通过本章学习掌握模式识别中最重要的非参 数判别分类法的原理(2) 掌握机器自学习的原理，自学习功能已不仅 在模式识别中应用，目前经常用机器学习这 个词以涉及更为广泛的内容。(3) 学习线性分类器的三种典型算法，这三种算法各自 形成体系，分别形成了传统模式识别、人工神经元 网络以及统计学习理论(4) 用近邻法进行分类(5) 通过相应数学工具的运用进一步提高运用数学的本领 第四章 非参数判别分类方法2本章要点(1) 非参数判别分类器的基本原理，与参数判别分类

2、方法的比较(2) 线性分类器的三种典型方法以Fisher准则为代表的传统模式识别方法，以感知准则函数为代表的机器自学习方法，以及支持向量机代表的统计学习理论。(3) 近邻法的工作原理及其改进(4) 线性分类器扩展到非线性分类器，两类别分类方法与多类别分类方法 第四章 非参数判别分类方法3本章难点(1) Fisher准则函数，其中用到向量点积，带约束条件的拉格朗日乘子法以及矩阵的特征值、特征向量等数学工具。(2) 感知器准则函数提出利用错误提供信息实现叠代修正的学习原理(3) 支持向量机方法设计约束条件为不等式的极值优化问题(4) 三种不同典型方法的优缺点比较(5) 近邻法的改进 第四章 非参数

3、判别分类方法4贝叶斯决策理论和统计判别方法-“最优”分类器设计方法。从原理上说贝叶斯决策理论采用了在d维特征空间中样本分布的最一般描述方式，即统计分布来描述，并且采用分类器中最重要的指标错误率作为产生判别函数和决策面的依据，对各种不同的分类器设计技术在理论上都有指导意义。但用贝叶斯决策理论需要先得到有关样本总体分布的知识，从而可以计算出样本的后验概率P(1|X)，并以此作为产生判别函数的必要数据，设计出相应的判别函数与决策面。 4.1引言5按贝叶斯决策理论设计分类器-参数判别方法实际问题中并不一定具备获取准确统计分布的条件:非参数判别分类方法，主要是判别函数、决策面方程的确定过程改成： 4.1

4、引言6非参数方法的分类器设计技术:直接采用贝叶斯决策方法并不是一种有效的手段。为此人们针对各种不同的情况，使用不同的准则函数，设计出满足这些不同准则要求的分类器。在非参数判别方法的设计中, 使用什么典型的分类决策方法却要预先由设计者确定，然后利用训练样本集提供的信息确定这些函数中的参数。非参数判别分类方法选择函数类型与确定参数是两个过程，因此以下先对最简单的线性分类器进行讨论学习。 4.1引言7 4.2线性分类器8设样本d维特征空间中描述，则两类别问题中线性判别函数的一般形式可表示成 (4-1) 其中 而0是一个常数，称为阈值权。相应的决策规则 4.2.1 线性判别函数的基本概念9决策面方程:

5、g(X)0 在线性判别函数条件下它对应d维空间的一个超平面 (4-3) 为了说明向量W的意义，假设在该决策平面上有两个特征向量X1与X2，则应有 (4-4) 因此W就是该超平面的法线向量。g(X)也就是d维空间中任一点X到该决策面距离的代数度量，该决策平面将这两类样本按其到该面距离的正负号确定其类别。 坐标原点到该决策面的距离。 4.2.1 线性判别函数的基本概念10线性判别函数是形式最为简单的判别函数，但是它不能用于稍复杂一些的情况，例如,欲设计这样一个一维样本的分类器，使其性能如图。则用线性判别函数显然就无能为力了。 4.2.2广义线性判别函数11如果设计这样一个判别函数g(x)(x-a)

6、(x-b)(4-6)及其相应的决策规则 (4-7) 就能达到(3-5)所要求的分类效果。此时g(x)不再是x的线性函数，而是一个二次函数。由于线性判别函数具有形式简单，因此人们希望能将其用适当方式扩展至原本适宜非线性判别函数的领域。一种方法是选择一种映射XY，即将原样本特征向量X映射成另一向量Y，从而可以采用线性判别函数的方法。 4.2.2广义线性判别函数12对于二次函数情况，其一般式可表示成 (4-8)如果我们采用映射xY，使 则判别函数g(x)又可表示成 (4-9) 4.2.2广义线性判别函数13g(x)被称为广义线性判别函数， 称为广义权向量。因此一个原属二次函数的分类问题就可转化为一个

7、线性判别函数问题。按照这种原理，任何形式的高次判别函数都可转化成线性判别函数来处理。譬如将非线性函数g(x)用级数展开，并截取其有限项，使之成为高次多项式，然后转化成广义线性判别函数。这种处理非线性分类器的方法，在支持向量机中得到充分的研究。我们将在本章后面讲述支持向量机。 4.2.2广义线性判别函数14将非线性函数用映射的方法变成线性函数的形式，问题是维数会增加。传统方法处理模式识别问题是希望降低维数，而不希望增加维数，因此不提倡使用。支持向量机却注重它能将非线性分类问题转化为线性分类问题，因而主张采用(见4.5.3节)。这将在后面学习过程中进一步说明。在目前，先把(4-10)至(4-14)

8、将样本向量增加一维的做法搞清楚，它的用处及好处在下面很快会看到。 4.2.2广义线性判别函数15这里我们要讨论一种特殊的映射方法，这种映射将X增广至 (4-10)将g(x)中的W向量与w0统一表示成 (4-11) 4.2.2广义线性判别函数16 (4-12)这是广义线性判别函数的一个特例。 被称为增广样本向量， 称为增广权向量。(4-12)式称为线性判别函数的齐次简化。它使特征空间增加了一维，但保持了样本间的欧氏距离不变，对于分类效果也与原决策面相同，只是在Y空间中决策面是通过坐标原点的，这在分析某些问题时具有优点，因此经常用到。 4.2.2广义线性判别函数17例一个一维特征空间的分类器，其决

9、策面方程为：x-c=0(4-13) (4-14)此时在二维空间中决策面为一过原点的直线，直线以 为法线向量，它对1维子空间的划分与原决策面完全相同。 4.2.2广义线性判别函数18线性分类器设计任务是在给定样本集， 确定线性判别函数的各项系数 w0,wd，以期对待测样本进行分类时，能满足相应的准则函数J为最优的要求。 然后用最优化技术确定准则函数的极值解 和 ，或增广权向量 。这种方法的具体过程可大致分为 1 按需要确定一准则函数J。2 确定准则函数J达到极值时 及 的具体数值，从而确定判别函数，完成分类器设计。 4.2.3线性分类器设计步骤 191、Fisher准则函数 2、最佳W值的确定3

10、、判别函数的确定 4.2.4Fisher线性判别函数 201、Fisher准则函数 设计线性分类器首先要确定准则函数，然后再利用训练样本集确定该分类器的参数，以求使所确定的准则达到最佳。 在使用线性分类器时，样本的分类由其判别函数值决定，而每个样本的判别函数值是其各分量的线性加权和再加上一阈值w0。 如果我们只考虑各分量的线性加权和，则它是各样本向量与向量W的向量点积。如果向量W的幅度为单位长度，则线性加权和又可看作各样本向量在向量W上的投影。Fisher准则的基本原理，就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。21Fisher准则函数的基本思路

11、: 即向量W的方向选择应能使两类样本投影的均值之差尽可能大些，而使类内样本的离散程度尽可能小。 4.2.4Fisher线性判别函数 22样本在d维特征空间的一些描述量(1) 各类样本均值向量mi (4-15)(2) 样本类内离散度矩阵Si与总类内离散度矩阵Sw (4-16) (4-17)(3) 样本类间离散度矩阵Sb (4-18) 4.2.4Fisher线性判别函数 23在一维Y空间(1)各类样本均值 (4-19) (2)样本类内离散度 和总类内离散度 (4-20) (4-21) 4.2.4Fisher线性判别函数 24在定义了上述一系列描述量后，可以用这些量给出Fisher准则的函数形式。根

12、据Fisher选择投影方向W的原则，即:使原样本向量在该方向上的投影能兼顾类间分布尽可能分开，类内样本投影尽可能密集的要求，用以评价投影方向W的函数为： (4-22) 这个函数称为Fisher准则函数 4.2.4Fisher线性判别函数 25这个函数称为Fisher准则函数 ,需进一步化为W的显函数。为此需对 等项进一步演化： (4-23) 因而(4-22)分子项又可写成 (4-23)同样 4.2.4Fisher线性判别函数 26因此： （4-25） （4-26）思路是,由于一个样本到一向量上的投影是一维实数空间，因此先定义在一维空间分布的表示方法(4-19)到(4-21)然后将Fisher的

13、思想用到(4-22)式定义的准则上。接着将投影运算代入(4-22)式中各个量，经过(4-23)至(4-25)式最后得到(4-26)，有了(4-26)式才能解出所需的W。 4.2.4Fisher线性判别函数 272、最佳W值的确定对(4-26)求取其达极大值时的 。可以采用拉格朗日乘子算法解决，譬如保持(4-26)式分母为一非零常数c的条件下, 求其分子项的极大值。为此可设计一拉格朗日函数 （4-27） 拉格朗日乘子法是用来求带约束条件的极值问题的，这是把 作为要求极值的目标函数，而保持 为一常数c，因此按拉格朗日乘子标准方法构造拉格朗日函数得(4-27)。然后通过对拉格朗日函数分别对W及乘子求

14、导并置为0来求解W。 4.2.4Fisher线性判别函数 282、最佳W值的确定这里对向量的求导(或偏导)的定义是：如： 则：其中为拉格朗日乘子，按拉格朗日算法对(4-27)式求对W的偏导数，且令其在 时为零，得 则有 （4-28） 4.2.4Fisher线性判别函数 292、最佳W值的确定由于Sw非奇异 （4-29） 这是一个求矩阵 的特征值问题，但在此可利用(4-18)式对 的定义，而得到 (4-30) 其中 是一个数量，可用数值R表示，则(4-30)式可写成 4.2.4Fisher线性判别函数 302、最佳W值的确定 代入(4-29)式可得 （4-31） 实际上我们关心的只是向量 的方向

15、，其数值大 小对分类器没有影响。因此在忽略了数值因子 后，可得 (4-32) (4-32)是使用Fisher准则求最佳法线向量的解，该式比较重要。 4.2.4Fisher线性判别函数 312、最佳W值的确定向量 就是使Fisher准则函数 达极大值的解，也就是按Fisher准则将d维X空间投影到一维Y空间的最佳投影方向， 的各分量值是对原d维特征向量求加权和的权值。 4.2.4Fisher线性判别函数 322、最佳W值的确定由(4-32)表示的最佳投影方向是容易理解的，因为其中一项(m1-m2)是一向量，对与(m1-m2)平行的向量投影可使两均值点的距离最远。但是如从使类间分得较开，同时又使类

16、内密集程度较高这样一个综合指标来看，则需根据两类样本的分布离散程度对投影方向作相应的调整，这就体现在对 向量按 作一线性变换，从而使Fisher准则函数达到极值点。 4.2.4Fisher线性判别函数 333、判别函数的确定以上讨论了线性判别函数加权向量W的确定方法，并讨论了使Fisher准则函数极大的d维向量 的计算方法，但是判别函数中的另一项w0尚未确定，一般可采用以下几种方法确定w0如 (4-33) 或 (4-34) 4.2.4Fisher线性判别函数 343、判别函数的确定或当 与 已知时可用 (4-35) 为了确定具体的分界面，还要指定线性方程的常数项。在实际工作中还可以对W0进行逐

17、次修正的方式，选择不同的W0值，计算其对训练样本集的错误率，找到错误率较小的W0值。4.2.4Fisher线性判别函数 353、判别函数的确定其中(4-33)算式中只考虑采用均值连线中点作为阈值点，相当于贝叶斯决策中先验概率 与 相等的情况，而(4-34)与(4-35)则是以不同方式考虑 与 不等的影响，以减小先验概率不等时的错误率。其中(4-34)以样本的不同数量N1与N2 来估计 与 。当W0确定之后，则可按以下规则分类， （4-36） 4.2.4Fisher线性判别函数 363、判别函数的确定使用Fisher准则方法确定最佳线性分界面的方法是一个著名的方法，尽管提出该方法的时间比较早，仍

18、见有人使用。但是与这一节要讨论的感知器准则函数方法相比，感知器准则函数方法的影响要大的多.感知器: 它采用类似于人认知错误、纠正错误、通过自学习改善自己认识事物本领的过程，使用这种方法的分类器称为感知器，它是人工神经元网络中应用最广泛，影响最大的一种网络雏形，要在本章重点学习。 4.2.4Fisher线性判别函数 37感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。 4.2.5感知准则函数38实际上从(4-37)到

19、(4-39)式的作用是将前面常用的线性决策面方程， 改写成 其中:线性可分是说该训练样本集中的两类样本可以用一个线性分界面正确无误的分开。为了讨论原理方便，这一节在线性可分条件下讨论问题，并且只谈两类识别问题。 4.2.5感知准则函数39在线性可分条件下，广义权向量a合适的话应有：为了使问题说得更简洁，又对问题的表达作进一步的改变。为了方便起见，如果我们令规范化增广样本向量 则合适的a能使所有的Y满足aTY 0. 4.2.5感知准则函数40感知准则函数方法的思路：先随意找一个初始向量 ，写作 ，然后用训练样本集中的每个样本来计算。一旦发现有的Y 使aTY 0，则只要 为正 (步长系数) ，则必

20、有 ,就有趋势做到使 a(k+1)TY0。 当然，修改后的a(k+1)还可以使某些Y出现a(k+1)TY0的情况，理论证明，只要训练样本集线性可分，无论a(0)的初值是什么，经过有限次叠代，都可使(4-39)式得到满足。41感知准则函数使用增广样本向量与增广权向量，即用(4-10)中的d+1维向量表示样本的齐次化向量，用(4-11)将判别函数中的权向量W与阈值权 组合成增广权向量。而判别函数则表示成(4-12)，即 (4-37) 在两类别情况下，判别准则是： (4-38) 4.2.5感知准则函数42为简单起见，我们不考虑g(X)0的情况。由于采用增广样本向量，特征空间为d1维，而决策面是经过坐

21、标原点的超平面。图4.5(a)表示了在一个二维增广特征空间两类样本分布及其决策面的情况。为了计算方便起见，我们可将第二类样本都取其反向向量，即令 (4-38)则对于那些能将所有样本正确分类的决策面来说，应有 (4-39) 4.2.5感知准则函数43反之，若发现出现 的情况，则意味着这些样本 被该决策面错误分类。(4-38)式的增广样本向量又称为规范化增广样本向量。图4.5(b)表示用规范化增广样本向量正确分类的情况。如果对一个样本集N，总能找到一个增广权向量 ，对该样本集所有样本实现正确分类，则这种情况称为具有线性可分性。以下我们只讨论线性可分性的情况。 4.2.5感知准则函数1/2，则ZK区

22、域为1的决策域；2 如果L1/2，则ZK区域为2的决策域；3 如果L1/2，以及N1(ZK)、N2(ZK)很小，则对ZK内 样本可作拒绝决策；4 如果L1/2，但N1(ZK)与N2(ZK)数量不可忽略，则对此区 域，用该子集的样本再次进行局部训练法训练，以获得 其进一步划分。重复上述过程，直至对所有区域都能合 理地确定为哪一类的决策域，或拒识区域为止。 4.3.4 局部训练法904.3.4.3 分段线性分类器检验一个决策规则的确定 图4.16中的样本采用上述方法后，决策平面由两个(H1、H2)增至三个，即H、H2与H3组成。至于对每类样本的决策规划，可用上面提到的m维向量作决策。例如图4.16

23、(b)中Z向量为(1，1，1)、(1，1，0)以及(0，1，0)的区域为2的决策域，而(0，1，1)(0，0，0)及(0，0，1)区域则为1的决策域。 4.3.4 局部训练法91模式识别或者通俗一点讲自动分类的基本方法有两大类：一类是将特征空间划分成决策域，这就要确定判别函数或确定分界面方程。而另一种方法则称为模板匹配，即将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。上面我们讨论的方法可以说都是将特征空间划分为决策域，并用判别函数或决策面方程表示决策域的方法。而近邻法则在原理上属于模板匹配。 它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较

24、，看与哪个模板最相似(即为近邻),就按最近似的模板的类别作为自己的类别。 4.4 近邻法92譬如A类有10个训练样本，因此有10个模板，B类有8个训练样本，就有8个模板。任何一个待测试样本在分类时与这18个模板都算一算相似度，如最相似的那个近邻是B类中的一个，就确定待测试样本为B类，否则为A类。因此原理上说近邻法是最简单的。但是近邻法有一个明显的缺点就是计算量大，存储量大，要存储的模板很多，每个测试样本要对每个模板计算一次相似度，因此在模板数量很大时，计算量也很大的。 那么有一个如此明显缺点的方法还有没有存在的必要性呢？这就要看其是否有优点，所以对近邻法的优点也要弄清楚。结论是:在模板数量很大

25、时其错误率指标还是相当不错的。这就是说近邻法有存在的必要。 4.4 近邻法93那么能否趋利避害，保留其优点，克服或改进其缺点呢？改进的办法：剪辑近邻法与压缩近邻法就是两种有代表性的改进方法。几个要点：(1) 弄清楚近邻法的定义(包括k近邻法)，与基本做法(2) 弄清“近邻法性能好”是在什么意义上讲的。知道渐 进平均错误率的定义(3) 快速搜索方法是使用怎样的原理？(4) 剪辑近邻法的原理是什么? 而压缩近邻法与剪辑近 邻法有什么不同之处？ 4.4 近邻法94将与测试样本最近邻样本的类别作为决策的方法称为最近邻法。对一个C类别问题，每类有Ni个样本，i1，C，则第i类i的判别函数，k1，Ni (

26、4-61)其中Xik表示是i类的第k个样本。以(4-61)式为判别函数的决策规则为： 如果 则决策Xj (4-62)由此可见最近邻法在原理上最直观，方法上也十分简单，只要对所有样本(共NNi)进行N次距离运算，然后以最小距离者的类别作决策。在(4-61)与(4-62)式中用表示距离，其实这是一个象征性的表示，你可以采用任何一种相似性的度量，在这课文中一般以欧氏距离为相似性度量。 4.4.1.1 最近邻法决策规划95最近邻法可以扩展成找测试样本的k个最近样本作决策依据的方法。其基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数表示成ki, i1，c则决策规划是： 如果

27、则决策Xj (4-63) k近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。 4.4.1.2 k-近邻法决策规则96其实近邻法的错误率是比较难算的，因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。譬如图中 4.4.2.1 最近邻法错误率分析97红点表示A类训练样本，蓝点表示B类训练样本，而绿点O表示待测样本。假设以欧氏距离来衡量，O的最近邻是A3，其次是B1，因此O应该属于A类，但若A3被拿开，O就会被判为B类。最近邻法的错误率会有偶然性，也就是指与具体的训练样本集有关。计算错误率的偶然性会因训练样本数量的增大而减小。因此人们就利用训练

28、样本数量增至极大，来对其性能进行评价。这要使用渐近概念，以下都是在渐近概念下来分析错误率的。 4.4.2.1 最近邻法错误率分析98 4.4.2.1 最近邻法错误率分析。99当最近邻法所使用的训练样本数量N不是很大时，其错误率是带有偶然性的。为了说明这一点我们拿图4.17所示一个在一维特征空间的两类别情况来讨论。图中X表示一待测试样本，而X是所用训练样本集中X的最邻近者，则错误是由X与X分属不同的类别所引起的。由于X与所用训练样本集有关，因此错误率有较大偶然性。当所用训练样本集N时，可以想像X将趋向于X，或者说处于以X为中心的极小邻域内，此时分析错误率问题就简化为在X样本条件下X与一个X(X的

29、极限条件)分属不同类别的问题。如果样本X的两类别后验概率分别为P(1|X)与P(2|X)，那么对X值，在N条件下，发生错误决策的概率为： 4.4.2.1 最近邻法错误率分析100当训练样本数量无限增多时，一个测试样本X的最近邻在极限意义上讲就是X本身。如果在X处对某一类的的后验概率为P(1|X)，则另一类为1- P(1|X)。那么当前测试样本与它的最近邻都属于同一类才能分类正确，故正确分类率 为 ，故有(4-64)式。 而在这条件下的平均错误率 (4-65) P称为渐近平均错误率，是PN(e)在N的极限。 4.4.2.1 最近邻法错误率分析101为了与基于最小错误率的贝叶斯决策方法对比，下面写

30、出贝叶斯错误率的计算式。基于最小错误率贝叶斯决策的错误率是出错最低限，因此要与它作比较。 （4-66） （4-67） 而 （4-68） 4.4.2.1 最近邻法错误率分析102如果用图4.17中的例子，则从(4-67)可得 (4-69) 而从(4-64)得 (4-70) 如果用(4-70)减去(4-69)，并写成P，则有 （4-71） 从(4-71)式可见在一般情况下P是大于零的值，只要P(1|X)P(2|X)0。有以下两种例外情况P0，这两种情况是P(1|X)1的情况或P(1|X)P(2|X)1/2。 4.4.2.1 最近邻法错误率分析103什么情况下P(1|X)1或P(2|X)=1? P(

31、1|X)= P(2|X)会出现什么什么情况？答：一般来说，在某一类样本分布密集区，某一类的后验概率接近或等于1。此时，基于最小错误率贝叶斯决策基本没错，而近邻法出错可能也很小。而后验概率近似相等一般出现在两类分布的交界处，此时分类没有依据，因此基于最小错误率的贝叶斯决策也无能为力了，近邻法也就与贝叶斯决策平起平坐了。从以上讨论可以看出，当N时，最近邻法的渐近平均错误率的下界是贝叶斯错误率，这发生在样本对某类别后验概率处处为1的情况或各类后验概率相等的情况。 4.4.2.1 最近邻法错误率分析104在其它条件下，最近邻法的错误率要高于贝叶斯错误率，可以证明以下关系式成立 (4-72) 4.4.2

32、.1 最近邻法错误率分析105即最近邻法的渐近平均错误率的上下界分别为贝叶斯错误率 及 。图4.18表示了这种关系。由于一般 情况下 很小，因此(4-72)又可粗略表示成 因此可以说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内。从这点说最近邻法是优良的，因此它是模式识别重要方法之一。 4.4.2.1 最近邻法错误率分析106以上我们从定性分析的角度讨论了最近邻法错误率问题，下面以同样的方法更简略地讨论k-近邻法的渐近平均错误率。对于两类别问题，式(4-64)可以改写成 (4-73)推广到k-邻域的情况，则错误出现在k个邻域样本中，正确的类别所占样本未过半数，得到 (4-74) 其中 4.4

33、.2.2 k-近邻法错误率分析107k邻域出错是指某类样本的k近邻中同类训练样本占少数，仅占一个两个，至多(k-1)/2个，因此这些情况都要考虑，计算就相当复杂了。将(4-74)与(4-73)相比较，(4-73)相当于(4-74)中k1的情况，而在(4-74)中当k增大时 是单调递减的。因此可以得出结论，在N的条件下，k-近邻法的错误率要低于最近邻法，图4-19图示了不同k值时的错误率情况。 4.4.2.2 k-近邻法错误率分析108从图中也可看出，无论是最近邻法，还是k-近邻法，其错误率的上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。 4.4.2.2 k-近邻法错误率分析109近邻法的

34、一个严重弱点是需要存储全部训练样本，以及繁重的距离计算量。但以简单的方式降低样本数量，只能使其性能降低，这也是不希望的。为此要研究既能减少近邻法计算量与存储量，同时又不明显降低其性能的一些改进算法。改进的方法大致分为两种原理。一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。另一种原理则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。 4.4.3 改进的近邻法110这种方法着眼于减少计算量，但没有达到减少存储量的要求。其基本思想是将样本集按邻近关

35、系分解成组，给出每组的质心所在，以及组内样本至该质心的最大距离。这些组又可形成层次结构，即组又分子组，因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。为了简单先从最近邻法讨论起。 4.4.3.1 快速搜索近邻法111一、样本集分级分解 先对样本集进行分级分解，分级分解过程可列举如下。首先将整个样本分成l个子集，每个子集又分为它的l个子集，如此进行若干次就能建立起一个样本集的树形结构。分成子集的原则是该子集内的样本尽可能聚成堆，这可用聚类方法实现。结点参数： 树形结构，每个结点表示一样本子集，描述该子集的参数是： 4.4.3.1 快速搜

36、索近邻法112一、样本集分级分解图4.20是一个树形结构样本集，其中分支数l3。 4.4.3.1 快速搜索近邻法113二、快速搜索算法要实现快速搜索近邻，需要有方法快速判断某个样本子集是否是该待识样本的可能近邻样本集，从而可将无关的样本子集尽快排除。另一方面在某样本子集内寻找哪个样本是近邻时，需快速排除不可能为近邻的样本。这两个快速判别算法可用以下两个规则表示： 4.4.3.1 快速搜索近邻法114二、快速搜索算法规则1： 如果存在 (4-75)则 不可能是X的近邻。其中B是待识别样本在搜索近邻过程中的当前近邻距离，B在搜索过程中不断改变与缩小。算法开始可将B设为无穷大。 表示待识样本X到结点

37、 的均值点距离。这个规则的证明是显而易见的，图4.21表示一待识样本及其当前近邻与一样本子集的关系。如果以X为圆心，B为半径作圆，则圆与样本子集 的分布圆不会相交，因而 中任一样本不可能比X的当前近邻更靠近X。 4.4.3.1 快速搜索近邻法115二、快速搜索算法规则2： 如果 (4-76) 其中Xi ，则Xi不可能是X的近邻。规则2的证明同规则1。 由此可见，只要将每个样本子集 中的每个样本Xi到其均值Mp的距离D(Xi,Mp)存入存储器中，就可利用上式将许多不可能成为测试样本近邻的训练样本排除。 4.4.3.1 快速搜索近邻法116二、快速搜索算法 4.4.3.1 快速搜索近邻法图 4.2

38、1117下面讨论如何运用这两个规则设计一个近邻的快速搜索算法： 当搜索树形样本集结构由高层次向低层次深入时，对同一层次的所有结点，可以利用规则1排除掉一些不可能包含待识别样本的近邻的结点(样本子集)。但是这往往不能做到只留下唯一的待搜索结点，因此必须选择其中某一结点先深入搜索，以类似于深度优先的方法确定搜索路径直至叶结点。然而在该叶结点中找到的近邻并不能保证确实是全样本集中的最近邻者，所找到的该近邻样本需要在那些有可能包含最近邻的样本子集中核对与修正，直至找到真正的最近邻样本为止。 4.4.3.1 快速搜索近邻法118树搜索算法。1： 初始化置B，L1(当前层次)，p0(当前结点)。2： 置后

39、选待搜索结点把当前结点的所有直接后继结点放入层的一目录表中，并对这些结点计算D(X，Mp)。3： 排除无关结点对层目录表中的每个结点P，用规则1将与近邻无缘的结点从目录表中清除。4： 路径选择如该层次目录表中有不止一个结点，选其中D(X，Mp)最小者，将该结点从目录表中删除，如该结点是叶结点转 5，否则LL+1，转2；如该层次目录表中无结点待搜索，则LL-1，如L0则停止，否则转3。5： 近邻样本搜索对现在执行结点p中的每个样本Xi，用规则2作如下检验： 如果D(X，Mp)D(Xi,Mp)+B则Xi不是X的最近邻，否则计算D(X，Xi)，若D(X，Xi)B，置NNi和BD(X,Xi)。对当前执

40、行结点中所有Xi被检验后，转3。在算法结束时，输出X的最近邻XNN及两者间距离 。 4.4.3.1 快速搜索近邻法119k-近邻法的快速计算k-近邻法快速计算是搜索待测样本的k个最近邻，以做到最后在这k个最近邻中计算占多数的训练样本类别。因此只要发现有一个训练样本比当前第k个近邻的距离要小，就把当前第k个近邻剔除出当前k近邻组。k-近邻法的快速计算法与上述过程大体相同，只是B值修改为当前第k个近邻的距离值。然后在步骤5中，对所计算的距离要与该k个当前的近邻比较，若比其中某个距离小，则删除最大者。除了以上两点修正外，其它算法与最近邻快速算法一样。以上是快速算法的原理与计算过程。至于树结构的层次与

41、叶结点内样本个数的选择在设计时根据中间结点计算与叶结点计算的综合平衡考虑。 4.4.3.1 快速搜索近邻法120以上讨论的快速算法只是研究如何减少计算量的问题，而不考虑存储量的压缩。实际上由于对样本进行分层次分组，并附有一些参数，实际的存储量还有可能增加。本节讨论的算法着眼于如何减少模板样本数目，从而可同时减少分类时的计算量及模板样本的存储量，同时还能进一步改进分类器的性能，如降低错误率等要求。本节讨论的剪辑近邻法除了在样本数量上有一定程度的减少外，更主要的优点是错误率的降低。 4.4.3.2 剪辑近邻法121剪辑近邻法的基本思想: 即当不同类别的样本在分布上有交迭部分的，分类的错误率主要来自

42、处于交迭区中的样本。当我们得到一个作为识别用的参考样本集时，由于不同类别交迭区域中不同类别的样本彼此穿插，导致用近邻法分类出错。因此如果能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。为此可以利用现有样本集对其自身进行剪辑。 4.4.3.2 剪辑近邻法122假设现有一个样本集N，样本数量为N。我们将此样本集分成两个互相独立的样本子集。一个被当作考试集 ，另一个作为参考集 ，数量分别为NT与NR，NT+NRN。将 中的样本表示成 ，而在 中的样本表示为 。将一个样本集分成两个相互独立的样本子集是指，分完以后的两个子集具有相同的分布例如将一个样本集分成两个相

43、互独立的对等子集，则在每个特征空间的子区域，两个子集都有相同的比例，或说各类数量近似相等。要注意指出的是每个子区域(从大空间到小空间)实际做时要用从总的集合中随机抽取的方式进行。 4.4.3.2 剪辑近邻法123剪辑的过程是： 首先对 中每一个Xi在 中找到其最近邻的样本Yi(Xi)，用Yi(Xi)表示Yi是Xi的最近邻参考样本。如果Yi与Xi不属于同一类别，则将Xi从 中删除，最后从 中得到一个经过剪辑的样本集，称为剪辑样本集 。 可用来取代原样本集 ，作为参考样本集对待识别样本进行分类。 经过剪辑后, 要作为新的训练样本集，则 是对其性能进行测试的样本，如发现 中的某个训练样本对分类不利，

44、就要把它剪辑掉。 4.4.3.2 剪辑近邻法124实际上剪辑样本的过程也可以用k-近邻法进行，即对 中的每个样本Xi，找到在 中的k个近邻，用k-近邻法判断Xi是否被错分类。从而决定其取舍，其它过程与前述方法完全一样。剪辑近邻法也可用到多类别情况。剪辑过程也可不止一次。重复多次的称为重复剪辑近邻法。图6.5到图6.8是一个两类正态分布样本的重复剪辑结果(教材149-151)。 4.4.3.2 剪辑近邻法125所使用的重复剪辑算法步骤如下：1. 将样本集 随机划分为S个子集，即 2. 用最近邻法，以 为参考集，对 中的样本进行分类，其中i1，s。 3. 去掉步骤2中被错分类的样本。4. 用所有留

45、下的全部样本构成新的样本集 。5. 如该次剪辑过程中没有样本被删除，则停止，否则 转步骤1。 4.4.3.2 剪辑近邻法126由此可见每次迭代过程都要重新对现有样本集进行重新随机划分，以保证了剪辑的独立性。从图6.5到图6.8可以看出，剩下的样本集形成了两个很好的聚类，并且在每个聚类中的样本都属同一类。前面我们已经提到，用近邻法容易出错的区域是在两类的交界处，这时某个训练样本存在与否就会影响到某些测试分类的结果。因此剪辑的效果往往把这些处于交界的训练样本给剪辑掉了。另一个问题是对剪辑近邻法错误率的分析。这里我们只给出简单的结论： 4.4.3.2 剪辑近邻法1271.利用最近邻法剪辑后得到的样本

46、集进行分类，其错误率总小于原样本集， (4-77)其中P(e)表示用原样本的渐近平均错误率。在P(e)很小，如P(e)0，其余都为0)，则最佳的权向量w也就可以利用(4-90)式定下来，它们是这些支持向量数据的线性求和。 如果知道哪些数据是支持向量，哪些不是，则问题就简单了。问题在于哪些数据是支持向量事先并不能确定，因此这只有通过求(4-84)式的极大值来求解。 4.5.1 线性可分条件下的支持向量机 最优分界面145从(4-85)可以看出，只要最佳的ai求得(表示成 )，则 (4-90)为了求出最佳的ai，拉格朗日理论中引入一种对偶函数，与(4-84)式相对偶的函数的构造方法是：对L(W,a

47、) 分别求它对W及w0的偏微分，并置为零，然后再代回到(4-84)式中，从而得到 (4-91) 4.5.1 线性可分条件下的支持向量机 最优分界面146拉格朗日理论证明：满足上述条件(4-85)到(4-89)时，找(4-91)式极大值的解就是(4-84)式的条件极小值，因此由(4-91)可求得各个最佳值 ，代入(4-90)即可得到 ，在W确定之后w0值也可利用(4-88)对某个 的数据求出。对(4-91)式的来源不要求弄懂，只需知道，它的极大值解与(4-84)式的极小值解是一致的就行了。因为后面还要用(4-91)说明一些问题。 4.5.1 线性可分条件下的支持向量机 最优分界面147对于线性不

48、可分的情况下，如果仍要使用线性分界面，则必然有部分训练样本向量被错分。在线性分界面条件下，被错分的样本从本类别训练样本占主导的决策域，进入了对方的决策域。在这种条件下，严格意义上的隔离带已不存在，(4-92)或(4-93)式也对一些数据不适用。但是仍然可以保留求最宽隔离带的框架，但允许有些数据能进入隔离带，甚至到对方的决策域中。但是对这部分数据的数量要严加控制。为了实行控制，可以采用的一种方法是对(4-81)作一些改动，增加一种起缓冲作用的量， )称为缓冲量。 4.5.2 线性不可分条件下的广义最优线性分界面148此时可将(4-81)式改成 (4-92) 对比(4-81)， (4-81) 或合

49、并写成 (4-93)对比(4-83)，看看有哪些不同 (4-83) 4.5.2 线性不可分条件下的广义最优线性分界面149有了缓冲量的定义后，我们可以通过要求缓冲量的总和，或缓冲量平方的总和等为最小的方式，实现对错分类数量的控制。因此目标函数中除了包含使 为极小这一目标外，还要包含 或 的项，下面讨论采用 的方法，因此目标函数可写为 c是一个人为确定的常数，而相应的拉格朗日函数可写成 (4-94) 4.5.2 线性不可分条件下的广义最优线性分界面150有了缓冲量的定义后，我们可以通过要求缓冲量的总和，或缓冲量平方的总和等为最小的方式，实现对错分类数量的控制。因此目标函数中除了包含使 为极小这一

50、目标外，还要包含 或 的项，下面讨论采用 的方法，因此目标函数可写为 c是一个人为确定的常数，而相应的拉格朗日函数可写成 (4-94) 与(4-84)对比，看看差别在哪里？ 4.5.2 线性不可分条件下的广义最优线性分界面151在线性 不可分条件下，在原目标函数中增加了 这一项，体现出对错分类总数要加以控制。这是因为在增加了 缓冲量i后，如对i的总量不加限制，就会使控制 最小没有意义，若对i总量没有限制，那么 可以变得很小(原意义上的隔离带很宽)，但 越小，则错分类的 数量体现在 上可以很大，因此必须对此加以考虑对错 分类要加以惩罚。因而 是一项惩罚项，合理地选择c 值，可以使 小与 小这两者

51、之间取得比较合适的平衡。 4.5.2 线性不可分条件下的广义最优线性分界面152由于(4-94)仍满足KKT条件，因此其充要条件是 (4-95) (4-99) (4-96) (4-100) (4-97) (4-101) (4-98) (4-102) 4.5.2 线性不可分条件下的广义最优线性分界面153问题：思考一下，这一堆式子与线性可分条件下的解相比， 哪些式子是增加的？哪些式子略有改变？ 4.5.2 线性不可分条件下的广义最优线性分界面154答：(4-97)是增加的，它对ai的值有了限制。(4-100)是增加的，(4-102)是增加的，它们都与i有关。(4-98)及(4-99)没有明显变化

52、。 4.5.2 线性不可分条件下的广义最优线性分界面155由(4-97)式与(4-102)式联合的结果，应有 (4-103)因此可以看到在线性不可分条件下，硬要用线性分类器，因此必然有的样本会被错分类，表现出来就是走到线性分界面另一类样本的区域。这样一来，对这些错误的总量要加以控制，目标函数就从 变成增加缓冲项。目标函数变了，但使用拉各朗日乘子方法的框架不变，因此原理上两者没有什么不同，只是要控制的量增加了。一些细节不要求，只要弄清楚在线性不可分条件下的处理方法就行了。 4.5.2 线性不可分条件下的广义最优线性分界面156 4.5.2 线性不可分条件下的广义最优线性分界面157对需要非线性分

53、类界面的情况，支持向量机采用的方法与前面提到的方法很不相同，支持向量机提出的方法是利用特征映射方法，使非线性分类的问题可以利用线性分类的计算框架来实现。利用特征映射方法的原理示意图如图4-31所示，其中左图表示的是在原特征空间两类需要非线性分界面的情况，而右图则表示采用特征映射后，样本X在新的特征空间中表示，而两类样本之间的分界面可以用线性分界面方程。这就是这一节要讨论的问题。 4.5.3 特征映射法、解决非线性判别分类问题158 4.5.3 特征映射法、解决非线性判别分类问题159在本章开始4.2.2中提到一种广义线性判别函数，我们曾举了一个二次函数的例子，现在再举一个利用二次曲面的例子，假

54、设对一个二维空间的分类问题，想用一个二次函数作为判别函数，则二次曲线函数的一般式可写成 如果希望采用广义线性方程的方法，可以定义 作为映射后的特征向量，而相应的广义权向量 ，则一个线性方程就可写成 其中w0=f 4.5.3 特征映射法、解决非线性判别分类问题160这样一来，线性分类方法就可以直接采用。这条路子在传统的模式识别技术中并没有持续研究下去，因为一个突出的问题是维数会急剧增加，在高维的空间中进行计算是传统方法所忌讳的。但支持向量机方法的提出者们对这个问题进行了更深入一步的研究，他们坚持了利用特征映射的方法，从而保留了线性划分的计算框架。 4.5.3 特征映射法、解决非线性判别分类问题1

55、61支持向量机利用特征映射的思想，可以回顾一下支持向量机中的以下两个式子： (4-104)(原(4-90)式)其中 是以下式子求极大值的解 (4-105)(原4-91式)从这个式子可以看到，计算上式的极大值只用到训练样本数据间的点积，而使用的分类器判别函数中权向量的作用也是通过权向量与样本的点积体现出来的，而从(4-104)式中看出来，权向量是训练样本中的支持向量的线性组合，因此WTX值的计算可写成 (4-106) 4.5.3 特征映射法、解决非线性判别分类问题162由此可以设想，如果我们将原特征向量用映射的方式转换成 ，则相应的式子只需改变成 (4-107)分类界面方程 (4-108)其中w

56、0*为相应的常数项。 4.5.3 特征映射法、解决非线性判别分类问题163由于特征进行了映射，从x变成了f(x)，因此问题是在另一个映射后的空间讨论的。设原空间维数为d，即 ，而新空间为m维，即 ，则一般m维要比d维大得多。权向量的维数也是m维，它是在映射后空间中的支持向量的线性求和 。但是支持向量机的提出者进一步发现，并不一定要求出这个权向量，因为分类判别函数中只关心权向量与样本向量之间的点积。因此，又引出了所谓核函数K(xi, x)。 4.5.3 特征映射法、解决非线性判别分类问题164其实(4-107)和(4-108)这两个式子中只用到有关数据的点积，因此如果能确定某种函数k(xix)的

57、确是xi与x这两个样本数据某种映射的内积(比点积更广泛一些，点积只是内积的一种)，就可用它来设计支持向量机，而不必知道对应哪一个函数f(*)。因此支持向量机采用了巧妙的特征映射方法, 将线性分类计算框架，扩展到非线性分类的领域。相应的式子可写成 (4-109)与(4-107)式对比，看看差别在哪里。分类界面方程 (4-110) 4.5.3 特征映射法、解决非线性判别分类问题165这样一来，如果我们选择了一种函数k(a,b), 其中a和b是原特征空间的两个数据点，那么只要这种函数是反映了特征映射后数据的内积，线性分类器的框架就都可以用了。因此选择合适的 函数就成为设计中的重要问题。 4.5.3

58、特征映射法、解决非线性判别分类问题166对(4-110)式可以用一种图(4-32)所示的结构来表示 4.5.3 特征映射法、解决非线性判别分类问题167那么什么样的函数k(,)与内积函数值等价呢？我们把具备这种条件的函数称为核函数。理论上的研究对核函数的充分必要条件进行了研究，并已得出一些主要结论(如Mercer条件)，但由于这些成果还不能具体地确定哪些函数具备这种条件，因此目前常用的核函数还局限于以下三种函数形式。多项式类型的函数 (4-111)核函数型式的函数 (4-112)S形函数，如 (4-113) 4.5.3 特征映射法、解决非线性判别分类问题168 一、参数判别分类方法与非参数判别分类方法的区别二、非参数分类判别方法的基本做法三、决策面方程的显式表示和隐式表示四、基于相似度的分类判别方法五、Fisher准则 六、感知准则函数方法七、近邻法八、支持向量机本章小结169一、参数判别分类方法与非参数判别分类方法的区别 参数判别方法，它的前提是对特征空间中的各类样本的分布清楚，因此一旦要测试分类样本的特征向量值X已知，就可以确定X对各类的后验概率，也就可按相应的准则计算与分类。如果这种分布可以用正态分布等描述，那么决策域的判别函数与分界面方程就可用函数的形式确