线性判别函数课件

1、线性判别函数和决策面感知准则函数和梯度下降法固定增量法及其收敛性最小平方误差准则函数多类情况下的线性判别函数分段线性判别函数Fisher 线性判别函数支持向量机第二章 线性判别函数2.1 线性判别函数和决策面 模式的表示 在分类识别方法中，首先应该把代表事物的那些特征抽取出来，构成代表这个模式的特征向量。 现在假定已经抽取到模式的若干特征： 如果这 个特征能够较好地描述原始的待识别的事物，则可以用 维空间的一个列向量来代表：1.问题与解决思路问题： 设有由N个待分类的两类别模式组成的一个样本集， 如何实现对样本集中的两类样本分类？ 在一般情况下样本在特征空间的分布情况：（二维两类别模式的例子）

2、二维三类别模式的例子可以看出: 不同类别的典型样本在特征空间中明显处于不同的区域。 表明: 由于相同类别的模式具有相似或相近的特征，因而一类模式在特征空间中的某一区域分布，而另一类则在另外区域分布。 我们可以得到启发: 用已知类别的模式样本产生一个代数表示的分界面 ，将特征空间分成两个互不重叠的区域，使不同类别的模式样本位于不同的区域，再用 作为判别函数，对待识别的模式进行分类。 在特征空间可看作一个决策面。归纳解决问题的思路:(1)分类问题 特征空间的分布 寻找 子区域的分界面 确定判别函数(2)待识别模式 判别函数 分类解决方法？代入 判别 判别函数 可以有多种形式，哪种形式最简单呢？ 线

3、性函数 在二维空间是一条直线；在三维空间是一个平面；在高维空间也是一个平面，由于是非直观的，称为超平面。 线性判别函数是所有模式特征的线性组合。 或 式中 是特征的系数，称为权， 称为阈值权。用什么方法来确定 呢？2. 线性判别函数的确定方法设有已知类别的两类别样本集，分布如下： 线性判别函数可以写成：参数 决定了 的方向和位置如何根据已知样本确定 ？ 由于要用 对两类样本在特征空间正确划分两类模式的区域，我们可以假定一个规则： 当样本为一个类别时， 使 当样本为另一个类别时，使 对全部样本都按这个规则来做，不满足时，调整 ，最终可以找到一个 ，使全部样本都满足这个规则。 这个过程称为训练学习

4、，已知类别的样本称为训练样本。 用训练学习的方法确定线性判别函数。如何训练学习？3.线性判别函数的一般表示 对于n维模式向量 ，其线性判别函数是所有模式特征的线性组合，即 可以写成其中， 称为权向量。4. 在向量空间的几何表示 取 作为决策面。 如果两个向量 和 都在决策面上，则有： 或写成 由于 和 是决策面上的任意两点，所以 也是在决策面上的任意向量。 表明了什么？ 两个n维向量相互正交的充要条件是两向量的内积为零。即 所以, 表明: 权向量和决策面上的任一向量正交。所以权向量的方向就是决策面的法线方向。 在两维模式下，决策面 把模式空间分成两个子空间，分别是对 类的决策域 和对 类的决策

5、域 。 如果我们规定： 在 中， ；在 中， ，决策面的法向量的方向指向 。 我们可以把向量 表示为： 待求的距离 决策面 上一点 与 有什么样的关系? 则有： 或判别函数值 是 到决策面的距离的度量。同理，可以得出：从原点到决策面 的距离为 。 如果 ，原点在 的正面； 如果 ，原点在 的反面； 如果 ，判别函数有齐次形式 决策面通过原点。二类模式的线性分类器的决策法则是： 如果 则决策 ，即把 归到 类； 如果 则决策 ，即把 归到 类；对于线性判别函数，关键的问题是求如何求？ 2.2 感知准则函数和梯度下降法1.感知准则函数 由前面介绍的知识，我们知道，对于一组两类别样本集：我们可以设线

6、性判别函数为：决策面方程为：即 求得权向量 ，就可确定决策面方程。 由数学知识，知 的齐次形式比较容易。能否将 变换成齐次形式呢？ 令 ，则， n维X空间 （n+1）维Y空间 Y称为增广模式向量，A称为增广权向量 经过这样的变换，求解的问题就变为：设有一组两类模式的增广模式向量样本集，利用这些样本确定一个线性判别函数的权向量 ，使 能够对 正确分类。训练规则为：对于属于 类的所有样本，有: 对于属于 类的所有样本，有: 注意到 和能否使 ？ 在属于 类的样本前加上负号，则这样处理后，问题变为：求使对于所有训练样本都满足： ， 的权向量如何求 ？ 是一个线性不等式组，而 是 维的，样本数量为 ，

7、一般 比 大的多， 这样， 的解不唯一。 为了解线性不等式组 ，需要构造一个准则函数，并希望构造的准则函数有极值的形式。 是由于使用权向量 而被误分类的样本集合。当一个样本 被误分类时，就有 ,所以 。仅当 时， 达到最小值。 我们称为感知准则函数。有了准则函数之后，我们就可以用最优化方法寻找使准则函数达到极小值的解权向量 。 如何求 ？2. 梯度下降法 梯度的定义 梯度是函数 的一阶偏导数组成的向量, 记为 二元函数的等值线 定义:坐标面上函数相等的各点的连线叫等值线,也称等高线。 函数 为不同值时，得到一系列的等值线，构成 的等值线族 。 在极值处的等值线聚成一点，并位于等值线的中心，当该

8、中心为极小值时，离开它越远， 值越大，反之，若该中心为极大值时，离开它越远， 的值越小。 梯度方向 由梯度的定义知， 梯度的方向就是函数的法线的方向。 梯度方向的性质:沿梯度方向，函数值增长最快，为最速上升方向；沿负梯度方向，函数值下降最快，为最速下降方向。梯度下降法的基本思想：函数 在某点 的梯度 是一个向量，它的方向与过点 的等量面 的法线方向重合，指向 增加的一方，是准则函数变化率最大的方向。反之，负梯度的方向则是函数 减少的最快的方向。所以在求准则函数 的极小值时，沿负梯度方向搜索有可能最快的找到最小值。 梯度下降法的实现： 先任意选择一个初始的权向量 ，计算 上的梯度 ，从 出发在最

9、陡方向（即负梯度方向）上移动一个距离以得到下一个权向量 。可采用下面的迭代方法从 推出 。 比例因子，叫做步长或增量 因为 的第 个梯度分量是 。 所以，可得到梯度下降法的迭代公式： 当第 步迭代用权向量 来分类时被误分类的样本集合 这种寻找解权向量的梯度下降法简述如下: 把第 次的权向量加上被误分类的样本的和与某个常数 的乘积，就得到第 次的权向量。 优点：只要二类样本线性可分的，这个算法总可收敛。 缺点：每次迭代必须遍历全部样本，才能得到当前权向量 下的误分样本集 ，从而再对 的值进行修正。 用训练样本集求线性决策面方法要点：求线性决策面函数转化成齐次形式感知准则函数梯度下降法迭代公式2.

10、3 固定增量算法及其收敛性 针对梯度下降法的缺点，作以下两点改变，得到固定增量算法： （1）把全部样本看作是一个序列，每当前一步迭代的权向量把某个样本错误分类时，就对这一个权向量作一次修正，而不是等当前权向量 对全部样本计算后再找出错分类样本集 去进行修改。（2）考虑每次迭代时 保持不变。二类模式下用固定增量法求解权向量： 设已知二类模式的样本集 和 ，这些样本都已被变成增广模式向量的形式，要求用固定增量的方法决定一个超平面 ，使它能正确划分样本集 和 。 开始时可以任意假定 和 位于决策面的哪一边。同样可以任意选择广义向量 的初始值 。 然后把训练集 和 中的增广模式向量 依次取出，计算 与

11、 的内积 。假定 在 的正面， 在它的反面权向量 用以下规则调整：如果 ，而 ，则用 代替 ；如果 ，而 ，则用 代替 ；如果 ，而 ，则 保持不变。如果 ，而 ，则 保持不变。 把属于 和 的全部模式都用上述方法处理一遍，称为一次迭代。 这个算法重复执行，直至权向量 不再变化，则 ，即求得解权向量 。 2.7 Fisher 线性判别函数 在应用统计方法进行模式识别时，许多问题涉及维数，在低维空间行得通的方法，往往在高维空间行不通。因此，发展了一些降低特征空间维数的方法，Fisher线性判别函数就是其中之一。 在介绍Fisher线性判别函数之前，先补充介绍要用到的Lagrange乘子法一种带等

12、式约束的函数极值求解方法。 Lagrange乘子法一. 等式约束最优化问题二. Lagrange乘子的概念 极值点必须满足两个条件:1.目标函数 沿约束曲线 的切线方向 的方向导数 , 即2.约束函数 沿约束曲线 的切线 方向 的方向导数 , 即比较上述两式可以得到:令可得: 为待定系数,解这个联立 方程可以求出 , 为问题的极小点， 极小值为 。 设 对各变量分别求偏导数并令其等于0,可得到： 实际上是求函数 的极值这个形式与前述形式一样。 三、二维情况下的Lagrange乘子法 对于等式约束优化函数 构造Lagrange函数： 使 达到极小值， 称为Lagrange乘子。 用Lagrang

13、e乘子法可以将等式约束优化问题转化为无约束优化问题。四、对于 维的情况 数学模型 首先由情况引入Lagrange系数 ，构造Lagrange函数： Fisher方法的基本思想： 把 维空间的所有模式投影到一条过原点的直线上，就可以把维数压缩到1。 过原点的直线有无数条，投影到那条直线好呢？x1x2 我们的目标就是找到这样一条直线，使得模式样本在这条直线上的投影最有利于分类。 设给定两类模式样本集， 和 ， 它们各有 和 个 维样本。设 为这条直线正方向的单位向量， 。将样本集中的样本向直线投影，相应地得到集合 和 。每个 就是 在单位向量 上的投影。 有： 这样，就得到了一个一维样本集合，样本

14、数量为 下面要解决的问题是什么？ 确定最好的投影方向 的 为了找到最好的 ，需要建立一个准则函数，这个准则函数要能反映不同类别模式在这条直线上投影分离程度的好坏。 在确定建立准则函数之前，先介绍几个有关参数。 1.在d维X空间 （1）各类样本的均值向量 （2）样本类内离散度，总类内离散度 （3）样本类间离散度2.在一维Y空间 （1）各类样本的均值 （2）样本类内离散度，总类内离散度 我们希望投影后，在一维Y空间两类样本尽可能分得开一些，即 （1）两类样本离得越远越好,也就是，两类均值之差 越大越好， （2）各类样本内部越密集越好，也就是，类内离散度越小越好， 越小越好。 因此，可以构造准则函数

15、为： 我们的目标是使 尽可能大的 作为投影方向，但在上式中不显含 ，因此，要将 变成 的显函数。准则函数的分子项：准则函数的分母项：因此，准则函数 可改写为： (2.43)这就是Rayleigh比，它有如下性质：（1） 是一个实数。（2） 的极值与大小无关，只与 的方向有关。 因此， 可以用Lagrange乘数法求极值。由性质(2)，可令式(2.43)分母为非零常数，即构造Lagrange函数 极大值的条件为：即 如果 非奇异，左乘 ，则有 解这个式子，就是求矩阵 的本征值。 考虑到我们求解问题的特殊性（只确定方向 ），其中 是常数，所以 总是在 的方向上。从而 所以略去比例因子 ，它不影响直

16、线的方向，得： 这就是使准则函数 极大的解。 就是使模式样本的投影在类间最分散，类内最集中的最优解。有了 后，得 就可将各样本由维空间投影到一维空间，即直线上，变成一维样本，它们给出较好的分类结果。 此类方法有一定的局限性：只对准则函数最优；没有利用样本的分布信息，错误概率不能达到最小。 2.8 支持向量机 Support Vector Machine SVM 回顾：用线性判别函数方法解决分类问题的方法1.思路（1）训练样本集 特征空间划分 决策面 线性判别函数（2）待识别模式 判别2.问题核心： 求线性判别函数的权向量3.求解方法：感知准则函数，梯度下降法，固定增量法求得权向量=确定了特征空

17、间的两类分界面（决策面） 一. 最优分界面 从线性判别函数的讨论中，我们已经知道，对于线性可分的两类样本，总可以找到一个分界面，将两类样本正确分类，而且，这样的分界面不是唯一的。H1和H2都可以将两类训练样本正确分类，但是，对于训练样本以外的样本，以哪个作为分界面，分类效果更好呢？H1H2因为：H2产生错误分类的可能性更小。 这就提出了分类器设计中一个很重要的问题： 分类器的通用性，也称分类器的推广能力即： 用训练样本设计的分类器，对训练样本以外的样本能够正确分类的能力。 哪一个分界面可以使分类器具有最好的通用性？ H1是两类各自最近样本距离相同的分界面， H2也是两类各自最近样本距离相同的分

18、界面.H1H2最优分界面： 在样本空间中，使两类样本正确分类，而且两类样本分开的间隔最大的分界面为最优分界面。 最优分界面可以使分类器具有最好的通用性（推广能力）。 如何求最优分界面？ 二. 支持向量对于给定的线性可分训练样本集， 如果 则 如果 则 可以得到分界面。 由于两类样本之间总有间隔存在，所以可以有： 如果 则 如果 则 其中 是一个正数。为了方便，训练样本集的样本用二元对来表示： 其中 和 分别是样本模式向量和它的相应的类别表示， 假定当 时， 。而当 时 。 设给定的有穷训练样本集可以被超平面 正确分开。 使每类离开分界超平面最近的样本向量与超平面之间的距离最大，位于间隔中间的超

19、平面是最优的。我们已经知道，在模式向量空间，任何一个模式向量到决策面的距离为：对于决策面方程 ， 和 并不是唯一的。设想：可以将 和 进行某种比例缩放，总可以找到一个 和 ，使 到决策面的距离最小，为 ， 这样，两类模式的分类规则可以写成：合并这两个式子，写成：这时两类模式间隔的距离为：为了使间隔最大，应当使 最小，等价于使 最小，所以，使 最小，且满足的分界面就是最优分界面，距离最优分界面最近的模式向量就是支持向量。可以看出，寻找支持向量，就是寻找最优分界面。 设目标函数为：将寻找最优分界面问题转化为有约束优化问题： 如何求解？ 构造Lagrange函数： 其中 为Lagrange乘子， 达到极值的必要条件为： (1) , 得(2) , 得 而对于最优分界面，解 必须满足：(1)(2) 最优分界面的解权向量是训练样本集中模式向量的线性组合. 对于约束条件,等号在支持向量下才成立，也就是说，只有支持向量可以在 的展开中具有非零系数 ，因此有 其中 是支持向量集。 如何知道哪些样本是支持向量呢? 求最优分类超平面问题： 等价转换对偶问题 这是一个二次函数优化问题，存在唯一解，解中不为零的 所对应的样本就是支持向量。 求得支持向量后，可求得权向量 和 式中 表示属于第一类的支持向量，而 表示属于第二类的支持向量。这样，由 和 就确定了最优超平面。 举例： 设有四个两类样本， 类有两