4.1 4.1 引言引言4.2 4.2 线性分类器线性分类器4.3 4.3 非线性判别函数非线性判别函数4.4 4.4 近邻法近邻法4.5 4.5 支持向量机支持向量机5 5 本章小结本章小结第四章第四章 非参数判别分类方法非参数判别分类方法1uu学习目的学习目的 (1) (1) 通过本章学习掌握模式识别中最重要的通过本章学习掌握模式识别中最重要的非参非参 数判别分类法数判别分类法的原理的原理 (2) (2) 掌握掌握机器自学习的原理机器自学习的原理，自学习功能已不仅，自学习功能已不仅 在模式识别中应用，目前经常用机器学习这在模式识别中应用，目前经常用机器学习这 个词以涉及更为广泛的内容。个词以涉及更为广泛的内容。 (3) (3) 学习线性分类器的学习线性分类器的三种典型算法三种典型算法，这三种算法各自，这三种算法各自 形成体系，分别形成了传统模式识别、人工神经元形成体系，分别形成了传统模式识别、人工神经元 网络以及统计学习理论网络以及统计学习理论 (4) (4) 用用近邻法近邻法进行分类进行分类 (5) (5) 通过相应数学工具的运用进一步提高运用数学的本领通过相应数学工具的运用进一步提高运用数学的本领 第四章第四章 非参数判别分类方法非参数判别分类方法2uu本章要点本章要点 (1) (1) 非参数判别分类器的基本原理，与参数判别非参数判别分类器的基本原理，与参数判别 分类方法的比较分类方法的比较 (2) (2) 线性分类器的三种典型方法线性分类器的三种典型方法以以FisherFisher准准 则则为代表的传统模式识别方法，以为代表的传统模式识别方法，以感知准则函感知准则函 数数为代表的机器自学习方法，以及为代表的机器自学习方法，以及支持向量机支持向量机 代表的统计学习理论。代表的统计学习理论。 (3) (3) 近邻法的工作原理及其改进近邻法的工作原理及其改进 (4) (4) 线性分类器扩展到非线性分类器，两类别分线性分类器扩展到非线性分类器，两类别分 类方法与多类别分类方法类方法与多类别分类方法第四章第四章 非参数判别分类方法非参数判别分类方法3uu本章难点本章难点 (1) Fisher(1) Fisher准则函数，其中用到向量点积，带约准则函数，其中用到向量点积，带约 束条件的拉格朗日乘子法以及矩阵的特征值、束条件的拉格朗日乘子法以及矩阵的特征值、 特征向量等数学工具。特征向量等数学工具。 (2) (2) 感知器准则函数提出利用错误提供信息实现感知器准则函数提出利用错误提供信息实现 叠代修正的学习原理叠代修正的学习原理 (3) (3) 支持向量机方法设计约束条件为不等式的极支持向量机方法设计约束条件为不等式的极 值优化问题值优化问题 (4) (4) 三种不同典型方法的优缺点比较三种不同典型方法的优缺点比较 (5) (5) 近邻法的改进近邻法的改进第四章第四章 非参数判别分类方法非参数判别分类方法4uu贝叶斯决策理论和统计判别方法贝叶斯决策理论和统计判别方法-“-“最优最优” ”分类分类 器设计方法器设计方法。从原理上说贝叶斯决策理论采用。从原理上说贝叶斯决策理论采用 了在了在d d维特征空间中样本分布的最一般描述方维特征空间中样本分布的最一般描述方 式，即式，即统计分布统计分布来描述，并且采用分类器中最来描述，并且采用分类器中最 重要的指标重要的指标错误率作为产生判别函数和决错误率作为产生判别函数和决 策面的依据，对各种不同的分类器设计技术在策面的依据，对各种不同的分类器设计技术在 理论上都有指导意义。理论上都有指导意义。uu但用贝叶斯决策理论需要先得到有关样本总但用贝叶斯决策理论需要先得到有关样本总 体分布的知识，从而可以计算出样本的后验概体分布的知识，从而可以计算出样本的后验概 率率P(1|X)P(1|X)，并以此作为产生判别函数的必要并以此作为产生判别函数的必要 数据，设计出相应的判别函数与决策面。数据，设计出相应的判别函数与决策面。4.14.1引言引言5uu按贝叶斯决策理论设计分类器按贝叶斯决策理论设计分类器- -参数判别方法参数判别方法uu实际问题中并不一定具备获取准确统计分布实际问题中并不一定具备获取准确统计分布 的条件的条件: :非参数判别分类方法非参数判别分类方法，主要是判别函，主要是判别函 数、决策面方程的确定过程改成：数、决策面方程的确定过程改成： 4.14.1引言引言6uu非参数方法的分类器设计技术非参数方法的分类器设计技术: :直接采用贝叶直接采用贝叶 斯决策方法并不是一种有效的手段。为此人们斯决策方法并不是一种有效的手段。为此人们 针对各种不同的情况，使用不同的准则函数，针对各种不同的情况，使用不同的准则函数， 设计出满足这些不同准则要求的分类器。设计出满足这些不同准则要求的分类器。uu在非参数判别方法的设计中在非参数判别方法的设计中, , 使用什么使用什么典型的典型的 分类决策方法却要预先由设计者确定分类决策方法却要预先由设计者确定，然后利，然后利 用训练样本集提供的信息确定这些函数中的参用训练样本集提供的信息确定这些函数中的参 数。非参数判别分类方法数。非参数判别分类方法选择函数类型选择函数类型与与确定确定 参数参数是两个过程，因此以下先对最简单的线性是两个过程，因此以下先对最简单的线性 分类器进行讨论学习。分类器进行讨论学习。4.14.1引言引言74.24.2线性分类器线性分类器8uu设样本设样本d d维特征空间中描述，则两类别问题中线性判维特征空间中描述，则两类别问题中线性判 别函数的一般形式可表示成别函数的一般形式可表示成 (4-1) (4-1) 其中其中而而00是一个常数，称为阈值权。相应的决策规则是一个常数，称为阈值权。相应的决策规则4.2.1 4.2.1 线性判别函数的基本概念线性判别函数的基本概念9uu决策面方程决策面方程:g(X):g(X)0 0 在线性判别函数条件下它对应在线性判别函数条件下它对应d d 维空间的一个超平面维空间的一个超平面 (4-3)(4-3)为了说明向量为了说明向量WW的意义，假设在该决策平面上有两个的意义，假设在该决策平面上有两个 特征向量特征向量X1X1与与X2X2，则应有则应有 (4-4)(4-4)因此因此WW就是该超平面的法线向量。就是该超平面的法线向量。uug(X)g(X)也就是也就是d d维空间中任一点维空间中任一点X X到该决策面距离的代数到该决策面距离的代数 度量，该决策平面将这两类样本按其到该面距离的正度量，该决策平面将这两类样本按其到该面距离的正 负号确定其类别。负号确定其类别。 坐标原点到该决策面的距离。坐标原点到该决策面的距离。4.2.1 4.2.1 线性判别函数的基本概念线性判别函数的基本概念10uu线性判别函数是线性判别函数是 形式最为简单的形式最为简单的 判别函数，但是判别函数，但是 它不能用于稍复它不能用于稍复 杂一些的情况，杂一些的情况， 例如例如, , 欲设计这样一个欲设计这样一个 一维样本的分类一维样本的分类 器，使其性能如器，使其性能如 图。图。uu则用线性判别函则用线性判别函 数显然就无能为数显然就无能为 力了。力了。4.2.24.2.2 广义线性判别函数 广义线性判别函数11uu如果设计这样一个判别函数如果设计这样一个判别函数g(x)g(x)(x-a)(x-b)(x-a)(x-b) (4-6)(4-6) 及其相应的决策规则及其相应的决策规则(4-7)(4-7)就能达到就能达到(3-5)(3-5)所要求的分类效果。所要求的分类效果。uu此时此时g(x)g(x)不再是不再是x x的线性函数，而是一个二次函数的线性函数，而是一个二次函数 。由于线性判别函数具有形式简单，因此人们希。由于线性判别函数具有形式简单，因此人们希 望能将其用适当方式扩展至原本适宜非线性判别望能将其用适当方式扩展至原本适宜非线性判别 函数的领域。一种方法是选择一种映射函数的领域。一种方法是选择一种映射XYXY，即即 将原样本特征向量将原样本特征向量X X映射成另一向量映射成另一向量Y Y，从而可以从而可以 采用线性判别函数的方法。采用线性判别函数的方法。4.2.24.2.2 广义线性判别函数 广义线性判别函数12uu对于二次函数情况，其一般式可表示成对于二次函数情况，其一般式可表示成(4-8)(4-8)如果我们采用映射如果我们采用映射xYxY，使使 则判别函数则判别函数g(x)g(x)又可表示成又可表示成 (4-9)(4-9)4.2.24.2.2 广义线性判别函数 广义线性判别函数13uug(x)g(x)被称为被称为广义线性判别函数广义线性判别函数， 称为称为广义权向广义权向 量量。因此一个原属二次函数的分类问题就可转化。因此一个原属二次函数的分类问题就可转化 为一个线性判别函数问题。为一个线性判别函数问题。uu按照这种原理，按照这种原理，任何形式的高次判别函数都可转任何形式的高次判别函数都可转 化成线性判别函数来处理化成线性判别函数来处理。譬如将非线性函数。譬如将非线性函数 g(x)g(x)用级数展开，并截取其有限项，使之成为高用级数展开，并截取其有限项，使之成为高 次多项式，然后转化成广义线性判别函数。次多项式，然后转化成广义线性判别函数。uu这种处理非线性分类器的方法，在支持向量机中这种处理非线性分类器的方法，在支持向量机中 得到充分的研究。我们将在本章后面讲述支持向得到充分的研究。我们将在本章后面讲述支持向 量机。量机。4.2.24.2.2 广义线性判别函数 广义线性判别函数14uu将非线性函数用映射的方法变成线性函数的形式将非线性函数用映射的方法变成线性函数的形式 ，问题是，问题是维数会增加维数会增加。uu传统方法处理模式识别问题是传统方法处理模式识别问题是希望降低维数希望降低维数，而，而 不希望增加维数，因此不提倡使用。不希望增加维数，因此不提倡使用。uu支持向量机却注重它能将非线性分类问题转化为支持向量机却注重它能将非线性分类问题转化为 线性分类问题，因而主张采用线性分类问题，因而主张采用( (见见4.5.34.5.3节节) )。这将。这将 在后面学习过程中进一步说明。在目前，先把在后面学习过程中进一步说明。在目前，先把(4-(4- 10)10)至至(4-14)(4-14)将样本向量增加一维的做法搞清楚，将样本向量增加一维的做法搞清楚， 它的用处及好处在下面很快会看到。它的用处及好处在下面很快会看到。4.2.24.2.2 广义线性判别函数 广义线性判别函数15uu这里我们要讨论一种特殊的映射方法，这种映射这里我们要讨论一种特殊的映射方法，这种映射 将将X X增广至增广至(4-10)(4-10)将将g(x)g(x)中的中的WW向量与向量与w0w0统一表示成统一表示成(4-11)(4-11)4.2.24.2.2 广义线性判别函数 广义线性判别函数16(4-12)(4-12)uu这是广义线性判别函数的一个特例。这是广义线性判别函数的一个特例。 uu 被称为被称为增广样本向量增广样本向量， 称为称为增广权向量增广权向量。uu(4-12)(4-12)式称为线性判别函数的式称为线性判别函数的齐次简化齐次简化。它使。它使特征空特征空 间增加了一维间增加了一维，但保持了样本间的欧氏距离不变，但保持了样本间的欧氏距离不变， 对于分类效