模式识别-线性判别函数

1、模式识别-线性判别函数第1页，共75页，2022年，5月20日，6点25分，星期四第六章:线性判别函数第2页，共75页，2022年，5月20日，6点25分，星期四线性判别函数原理利用判别函数将特征空间划分为若干个决策区域，然后根据待识别样本位于的决策区域来进行判类是模式识别的重要方法之一第3页，共75页，2022年，5月20日，6点25分，星期四线性判别函数判别函数的概念判别函数即是直接用来进行模式分类的准则函数例如在Bayes决策方法中，对c类模式有：这里的 即可视为模式分类的准则函数判别函数第4页，共75页，2022年，5月20日，6点25分，星期四线性判别函数在特征空间中，判别函数还具有

2、特殊的几何意义和性质第5页，共75页，2022年，5月20日，6点25分，星期四线性判别函数对图（a）所示的两类模式，可以用一条直线（界面）将其分开，设直线方程为： 则可令判别函数 则对 类模式有 对 类模式有第6页，共75页，2022年，5月20日，6点25分，星期四线性判别函数可用判别函数进行模式分类，即当待识样本X到来时 若 ，则判X属于 类 若 ，则判X属于 类第7页，共75页，2022年，5月20日，6点25分，星期四线性判别函数对图（b）所示的两类模式，用直线已不能将两类模式分开，分界线为二次曲线，判别函数为 此时分界面仍具有如下性质： 若 ，则判X属于 类 若 ，则判X属于 类第

3、8页，共75页，2022年，5月20日，6点25分，星期四线性判别函数判界面由 所决定的界面称为判别面，对判别面上（决策面）任一点均有判别面正面、反面 的区域称为判别面的正面， 的区域称为判别界的反面 第9页，共75页，2022年，5月20日，6点25分，星期四线性判别函数问题判别函数的形式（线性、非线性）？根据先验知识决定判别函数中的系数？由已知类别的学习样本确定多类问题？化解为多个二类问题第10页，共75页，2022年，5月20日，6点25分，星期四线性判别函数及其几何性质 定义 d维特征空间中，若判别函数具有如下形式：其中：权向量阀值第11页，共75页，2022年，5月20日，6点25分

4、，星期四线性判别函数及其几何性质则称满足上述定义的函数 为线性判别函数由线性判别函数决定的判别面（决策面）方程为：第12页，共75页，2022年，5月20日，6点25分，星期四线性判别函数及其几何性质若令 则线性判别函数可写为 ，此时决策面为过原点的超平面 第13页，共75页，2022年，5月20日，6点25分，星期四线性判别函数及其几何性质线性可分d维空间中的模式类如果能用线性判别函数将其分开，则称模式类为线性可分的线性可分线性不可分第14页，共75页，2022年，5月20日，6点25分，星期四线性判别函数及其几何性质线性判别函数的几何性质 第15页，共75页，2022年，5月20日，6点2

5、5分，星期四线性判别函数及其几何性质下面以二维二类情况为例，分析线性判别函数的几何性质 设 、 为判别面上的任意两点，则有 即： g(X)=0WX1X2第16页，共75页，2022年，5月20日，6点25分，星期四线性判别函数及其几何性质性质一：权向量w与判别面上任一向量正交，即w决定了判别界的方向第17页，共75页，2022年，5月20日，6点25分，星期四线性判别函数及其几何性质设x为特征空间中的任一向量，则有： 其中：第18页，共75页，2022年，5月20日，6点25分，星期四线性判别函数及其几何性质将其代入 中有： 由于 为判别界上的点,故第19页，共75页，2022年，5月20日，

6、6点25分，星期四线性判别函数及其几何性质因此有：性质二： 是以 为单位的X到判决面的距离。若在判别面的正面，则g(x)0, 若在判别面的反面，则g(x)0，则原点位于判别界的正面；反之原点位于判别界反面。 第21页，共75页，2022年，5月20日，6点25分，星期四多类情况下的线性判别函数问题：多类情况下，如何用线性判别函数进行分类？解决方案：化为多个二类问题来解决！分三种情况来讨论第22页，共75页，2022年，5月20日，6点25分，星期四多类情况下的线性判别函数情况一每个模式类均可用一个单独的线性判别界与其余模式类分开 第23页，共75页，2022年，5月20日，6点25分，星期四多

7、类情况下的线性判别函数共需c个判别函数，且具有如下性质：第24页，共75页，2022年，5月20日，6点25分，星期四多类情况下的线性判别函数当待识样本到来时，若 ，且 对所有的 j， ，则判 该方法实质上是在特征空间中划分出c个区域，并根据待识样本落入的区域来决定属于哪一类模式。 但该方法存在失效区或不定区，如图中阴影部分，即存在多于一个的判别函数大于，或所有的判别函数都小于。第25页，共75页，2022年，5月20日，6点25分，星期四多类情况下的线性判别函数情况二线性判别界只能将模式类两两分开 第26页，共75页，2022年，5月20日，6点25分，星期四多类情况下的线性判别函数则需 个

8、判别函数 具有如下性质： 显然，应有：第27页，共75页，2022年，5月20日，6点25分，星期四多类情况下的线性判别函数识别过程为：当待识样本到来时，若对所有的j均有 则判该方法仍然存在不定区，对不定区待识样本，采用拒识策略第28页，共75页，2022年，5月20日，6点25分，星期四多类情况下的线性判别函数情况三不考虑二类问题的线性判别函数，采用个线性判别函数将个模式分开。判别函数为：识别准则为：对所有的 ，若 则判第29页，共75页，2022年，5月20日，6点25分，星期四多类情况下的线性判别函数该方法实际上是将特征空间划分为R1,， Rc 共C个判别区域，当模式在Ri中时, 具有最

9、大的函数值如果Ri与Rj相邻，则决策面是方程 的一部分该方法不存在不定区 第30页，共75页，2022年，5月20日，6点25分，星期四多类情况下的线性判别函数R1R2R3R4g1(X)g4(X)g3(X)g2(X)第31页，共75页，2022年，5月20日，6点25分，星期四小结由上述分析可得，应用线性判别函数的方法实际上是如何应用学习样本来确定线性判别函数参数的方法由于多类问题可化为多个二类问题来处理，故以下介绍二类问题的线性判别函数学习算法第32页，共75页，2022年，5月20日，6点25分，星期四线性判别函数的学习算法 线性判别函数一般具有如下一般形式：现将其扩展到增广特征空间，即：

10、第33页，共75页，2022年，5月20日，6点25分，星期四线性判别函数的学习算法 则线性判别函数可写为：判别面 为过原点的超平面根据判别函数的性质，对于二类问题有： 若 ，则 类 若 ，则 类第34页，共75页，2022年，5月20日，6点25分，星期四线性判别函数的学习算法 现对 类样本进行归一化处理，即令所有 类样本则二类分类问题变为：由个学习样本，找到权向量，使得对所有的学习样本有：第35页，共75页，2022年，5月20日，6点25分，星期四线性判别函数的学习算法 满足上述条件的向量A称为解向量可见每个学习样本都对解向量进行了限制，解向量并不唯一。显然，若存在解向量A使得二类样本分

11、类正确，则样本是线性可分的第36页，共75页，2022年，5月20日，6点25分，星期四线性判别函数的学习算法 解向量并不唯一：解区域 第37页，共75页，2022年，5月20日，6点25分，星期四感知准则梯降法 欲求解向量，即是根据学习样本求解不等式组直接求解不等式是困难的！第38页，共75页，2022年，5月20日，6点25分，星期四感知准则梯降法可将求的问题转化为标量准则函数求极值的问题，即定义一个标量函数J(A)，它具有如下的性质：J(A)的值越小，判别面的分割质量越高第39页，共75页，2022年，5月20日，6点25分，星期四感知准则梯降法求标题函数对矢量的极值问题，可用优化方法中

12、的梯度下降法来解决标量函数J(A)关于矢量的的梯度是一个向量，即 ：第40页，共75页，2022年，5月20日，6点25分，星期四感知准则梯降法 的方向是J(A)在向量处增加最快的方向反之，负梯度 是J(A)在向量处减小得最快的方向 的值的大小 表示J(A)在处变化率的大小梯度等于的点即是函数J(A)的极值点 第41页，共75页，2022年，5月20日，6点25分，星期四感知准则梯降法标量函数关于向量的梯度 第42页，共75页，2022年，5月20日，6点25分，星期四感知准则梯降法梯降法求解向量的一般思路：定义一个标量准则函数J(A,Y)，该函数不仅与解向量A有关，还与学习样本Y有关当准则函

13、数达到极值时，判别界的质量最高通过迭代的方法找到函数J(A,Y)的极值点，即找到使得J(A,Y)的最佳解向量A第43页，共75页，2022年，5月20日，6点25分，星期四感知准则梯降法如何用迭代方法求J(A,Y)极值点？如何定义标量函数？第44页，共75页，2022年，5月20日，6点25分，星期四感知准则梯降法迭代方法求J(A,Y)极值点k=1，任意选取初始解向量计算准则函数在Ak处的梯度 向负梯度方向跨一步，令 若 ，则显然 ，停止。 否则，令k=k+1，重复第二步，直到结束。第45页，共75页，2022年，5月20日，6点25分，星期四感知准则梯降法感知准则函数定义为：其含义是选择了解

14、向量后，被错分类的样本到判别面的距离之和可见满足，其存在极小值，此时无错分类样本达到极小值时的解向量即是欲求的解向量！第46页，共75页，2022年，5月20日，6点25分，星期四感知准则梯降法如何求感知准则函数的梯度？即感知准则函数的梯度为选取解向量后，所有被错分类的样本之和的负值第47页，共75页，2022年，5月20日，6点25分，星期四感知准则梯降法则迭代公式为：第48页，共75页，2022年，5月20日，6点25分，星期四感知准则梯降法迭代方法求感知准则函数极值点k=1，任意选取初始解向量遍历所有样本，计算 找出选择后被错分类的样本（即的样本）令： 若 ，则停止。 否则，令k=k+1

15、，重复第三步，直到结束第49页，共75页，2022年，5月20日，6点25分，星期四固定增量算法感知准则算法需一次获取所有学习样本，并在迭代算法中一次遍历所有样本在实际应用中，有时样本是分批获取固定增量算法即是针对上述情况的改进感知准则算法基本思想是：每次修改解向量时，不需遍历所有的样本，而是将学习样本序贯输入，每考察一个样本就对修改一次。第50页，共75页，2022年，5月20日，6点25分，星期四固定增量算法固定增量迭代算法任意选取初始解向量顺序取出学习样本，计算若，则不变若，则遍历所有样本，即，完成一次迭代令k=k+1，重复上述迭代，直至 第51页，共75页，2022年，5月20日，6点

16、25分，星期四固定增量算法存在的问题初始解向量的选择问题？步长的选取问题？收敛性问题？（感知收敛定理）结论：只要二类样本是线性可分的，则固定增量算法一定收敛 第52页，共75页，2022年，5月20日，6点25分，星期四最小平方误差算法 原理将求线性判别函数的不等式问题转化为求解等式的问题，即令：其中为任意指定的正常数第53页，共75页，2022年，5月20日，6点25分，星期四最小平方误差算法方法定义矩阵，其第 i 行是学习样本i 的各元素，即：第54页，共75页，2022年，5月20日，6点25分，星期四最小平方误差算法令：n为学习样本总数则 等价于第55页，共75页，2022年，5月20

17、日，6点25分，星期四最小平方误差算法假如 是非奇异矩阵，则可直接计算解向量但通常情况下， 的行数常大于列数，即 是方程式数目大于未知数数目的矛盾方程，一般无精确解第56页，共75页，2022年，5月20日，6点25分，星期四最小平方误差算法此时可考虑寻找解向量，它使 与b之间的误差极小化定义误差向量 将平方误差定义为准则函数 即平方误差函数 第57页，共75页，2022年，5月20日，6点25分，星期四最小平方误差算法 具有极小值，此时即为 的解如何求平方误差函数的极值?求平方误差函数极值方法伪逆法梯降法第58页，共75页，2022年，5月20日，6点25分，星期四最小平方误差算法伪逆法则梯

18、度令即第59页，共75页，2022年，5月20日，6点25分，星期四最小平方误差算法伪逆法可得解得最佳解向量为：称为的伪逆矩阵第60页，共75页，2022年，5月20日，6点25分，星期四最小平方误差算法伪逆法特点：伪逆法要求为非奇异矩阵，其逆才存在计算较为复杂第61页，共75页，2022年，5月20日，6点25分，星期四最小平方误差算法梯降法由于则梯降法的迭代公式为：算法过程与感知准则梯降法相同第62页，共75页，2022年，5月20日，6点25分，星期四isher 线性函数基本思想：在d维特征空间中，将所有样本投影到一条过原点的直线上，将维数压缩到维目标：找到一个最优的投影方向，使投影后的样本最易于分类 第63页，共75页，2022年，5月20日，6点25分，星期四isher 线性函数WW第64页，共75页，2022年，5月20日，6点25分，星期四isher 线性函数设给定两类学习样本集和，共n个学习样本，其中类样本个，类样本个现将任意学习样本与权向量作内积：则即是在方向上投影后的样本第65页，共75页，2022年，5月20日，6点25分，星期四isher 线性函数是一标量，是坐标原点