模式识别-线性判别函数.ppt

1、,模式识别Pattern Classification,第六章:线性判别函数,模式识别，第六章,3,线性判别函数,原理 利用判别函数将特征空间划分为若干个决策区域，然后根据待识别样本位于的决策区域来进行判类 是模式识别的重要方法之一,模式识别，第六章,4,线性判别函数,判别函数的概念 判别函数即是直接用来进行模式分类的准则函数 例如在Bayes决策方法中，对c类模式有： 这里的 即可视为模式分类的准则函数判别函数,模式识别，第六章,5,线性判别函数,在特征空间中，判别函数还具有特殊的几何意义和性质,模式识别，第六章,6,线性判别函数,对图（a）所示的两类模式，可以用一条直线（界面）将其分开，设

2、直线方程为： 则可令判别函数 则对 类模式有 对 类模式有,模式识别，第六章,7,线性判别函数,可用判别函数进行模式分类，即当待识样本X到来时 若 ，则判X属于 类 若 ，则判X属于 类,模式识别，第六章,8,线性判别函数,对图（b）所示的两类模式，用直线已不能将两类模式分开，分界线为二次曲线，判别函数为 此时分界面仍具有如下性质： 若 ，则判X属于 类 若 ，则判X属于 类,模式识别，第六章,9,线性判别函数,判界面 由 所决定的界面称为判别面，对判别面上（决策面）任一点均有 判别面正面、反面 的区域称为判别面的正面， 的区域称为判别界的反面,模式识别，第六章,10,线性判别函数,问题 判别

3、函数的形式（线性、非线性）？根据先验知识决定 判别函数中的系数？由已知类别的学习样本确定 多类问题？化解为多个二类问题,模式识别，第六章,11,线性判别函数及其几何性质,定义 d维特征空间中，若判别函数具有如下形式： 其中：,权向量,阀值,模式识别，第六章,12,线性判别函数及其几何性质,则称满足上述定义的函数 为线性判别函数 由线性判别函数决定的判别面（决策面）方程为：,模式识别，第六章,13,线性判别函数及其几何性质,若令 则线性判别函数可写为 ，此时决策面为过原点的超平面,模式识别，第六章,14,线性判别函数及其几何性质,线性可分 d维空间中的模式类如果能用线性判别函数将其分开，则称模式

4、类为线性可分的,线性可分,线性不可分,模式识别，第六章,15,线性判别函数及其几何性质,线性判别函数的几何性质,模式识别，第六章,16,线性判别函数及其几何性质,下面以二维二类情况为例，分析线性判别函数的几何性质 设 、 为判别面上的任意两点，则有 即：,模式识别，第六章,17,线性判别函数及其几何性质,性质一：权向量w与判别面上任一向量正交，即w决定了判别界的方向,模式识别，第六章,18,线性判别函数及其几何性质,设x为特征空间中的任一向量，则有： 其中：,模式识别，第六章,19,线性判别函数及其几何性质,将其代入 中有： 由于 为判别界上的点,故,模式识别，第六章,20,线性判别函数及其几

5、何性质,因此有： 性质二： 是以 为单位的X到判决面的距离。若在判别面的正面，则g(x)0, 若在判别面的反面，则g(x)0，判别界上g(x)=0。,模式识别，第六章,21,线性判别函数及其几何性质,对于原点x=0，则 性质三：线性判别函数中的阀值W0表征了原点到判别界的距离。若W0 0，则原点位于判别界的正面；反之原点位于判别界反面。,模式识别，第六章,22,多类情况下的线性判别函数,问题：多类情况下，如何用线性判别函数进行分类？ 解决方案：化为多个二类问题来解决！ 分三种情况来讨论,模式识别，第六章,23,多类情况下的线性判别函数,情况一 每个模式类均可用一个单独的线性判别界与其余模式类分

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

7、况下的线性判别函数,识别过程为：当待识样本到来时，若对所有的j均有 则判 该方法仍然存在不定区，对不定区待识样本，采用拒识策略,模式识别，第六章,29,多类情况下的线性判别函数,情况三 不考虑二类问题的线性判别函数，采用个线性判别函数将个模式分开。判别函数为： 识别准则为：对所有的 ，若 则判,模式识别，第六章,30,多类情况下的线性判别函数,该方法实际上是将特征空间划分为R1,， Rc 共C个判别区域，当模式在Ri中时, 具有最大的函数值 如果Ri与Rj相邻，则决策面是方程 的一部分 该方法不存在不定区,模式识别，第六章,31,多类情况下的线性判别函数,模式识别，第六章,32,小结,由上述分

8、析可得，应用线性判别函数的方法实际上是如何应用学习样本来确定线性判别函数参数的方法 由于多类问题可化为多个二类问题来处理，故以下介绍二类问题的线性判别函数学习算法,模式识别，第六章,33,线性判别函数的学习算法,线性判别函数一般具有如下一般形式： 现将其扩展到增广特征空间，即：,模式识别，第六章,34,线性判别函数的学习算法,则线性判别函数可写为： 判别面 为过原点的超平面 根据判别函数的性质，对于二类问题有： 若 ，则 类 若 ，则 类,模式识别，第六章,35,线性判别函数的学习算法,现对 类样本进行归一化处理，即令所有 类样本 则二类分类问题变为：由个学习样本，找到权向量，使得对所有的学习

9、样本有：,模式识别，第六章,36,线性判别函数的学习算法,满足上述条件的向量A称为解向量 可见每个学习样本都对解向量进行了限制，解向量并不唯一。 显然，若存在解向量A使得二类样本分类正确，则样本是线性可分的,模式识别，第六章,37,线性判别函数的学习算法,解向量并不唯一：解区域,模式识别，第六章,38,感知准则梯降法,欲求解向量，即是根据学习样本求解不等式组 直接求解不等式是困难的！,模式识别，第六章,39,感知准则梯降法,可将求的问题转化为标量准则函数求极值的问题，即定义一个标量函数J(A)，它具有如下的性质：J(A)的值越小，判别面的分割质量越高,模式识别，第六章,40,感知准则梯降法,求

10、标题函数对矢量的极值问题，可用优化方法中的梯度下降法来解决 标量函数J(A)关于矢量的的梯度是一个向量，即 ：,模式识别，第六章,41,感知准则梯降法,的方向是J(A)在向量处增加最快的方向 反之，负梯度 是J(A)在向量处减小得最快的方向 的值的大小 表示J(A)在处变化率的大小 梯度等于的点即是函数J(A)的极值点,模式识别，第六章,42,感知准则梯降法,标量函数关于向量的梯度,模式识别，第六章,43,感知准则梯降法,梯降法求解向量的一般思路： 定义一个标量准则函数J(A,Y)，该函数不仅与解向量A有关，还与学习样本Y有关 当准则函数达到极值时，判别界的质量最高 通过迭代的方法找到函数J(

11、A,Y)的极值点，即找到使得 J(A,Y)的最佳解向量A,模式识别，第六章,44,感知准则梯降法,如何用迭代方法求J(A,Y)极值点？ 如何定义标量函数？,模式识别，第六章,45,感知准则梯降法,迭代方法求J(A,Y)极值点 k=1，任意选取初始解向量 计算准则函数在Ak处的梯度 向负梯度方向跨一步，令 若 ，则显然 ，停止。 否则，令k=k+1，重复第二步，直到结束。,模式识别，第六章,46,感知准则梯降法,感知准则函数定义为： 其含义是选择了解向量后，被错分类的样本到判别面的距离之和 可见满足，其存在极小值，此时无错分类样本 达到极小值时的解向量即是欲求的解向量！,模式识别，第六章,47,

12、感知准则梯降法,如何求感知准则函数的梯度？ 即感知准则函数的梯度为选取解向量后，所有被错分类的样本之和的负值,模式识别，第六章,48,感知准则梯降法,则迭代公式为：,模式识别，第六章,49,感知准则梯降法,迭代方法求感知准则函数极值点 k=1，任意选取初始解向量 遍历所有样本，计算 找出选择后被错分类的样本（即的样本） 令： 若 ，则停止。 否则，令k=k+1，重复第三步，直到结束,模式识别，第六章,50,固定增量算法,感知准则算法需一次获取所有学习样本，并在迭代算法中一次遍历所有样本 在实际应用中，有时样本是分批获取 固定增量算法即是针对上述情况的改进感知准则算法 基本思想是：每次修改解向量

13、时，不需遍历所有的样本，而是将学习样本序贯输入，每考察一个样本就对修改一次。,模式识别，第六章,51,固定增量算法,固定增量迭代算法 任意选取初始解向量 顺序取出学习样本，计算 若，则不变 若，则 遍历所有样本，即，完成一次迭代 令k=k+1，重复上述迭代，直至,模式识别，第六章,52,固定增量算法,存在的问题 初始解向量的选择问题？ 步长的选取问题？ 收敛性问题？（感知收敛定理） 结论：只要二类样本是线性可分的，则固定增量算法一定收敛,模式识别，第六章,53,最小平方误差算法,原理 将求线性判别函数的不等式问题 转化为求解等式的问题，即令： 其中为任意指定的正常数,模式识别，第六章,54,最

14、小平方误差算法,方法 定义矩阵，其第 i 行是学习样本i 的各元素，即：,模式识别，第六章,55,最小平方误差算法,令： n为学习样本总数 则 等价于,模式识别，第六章,56,最小平方误差算法,假如 是非奇异矩阵，则可直接计算解向量 但通常情况下， 的行数常大于列数，即 是方程式数目大于未知数数目的矛盾方程，一般无精确解,模式识别，第六章,57,最小平方误差算法,此时可考虑寻找解向量，它使 与b之间的误差极小化 定义误差向量 将平方误差定义为准则函数 即,平方误差函数,模式识别，第六章,58,最小平方误差算法,具有极小值，此时即为 的解 如何求平方误差函数的极值?,伪逆法,梯降法,模式识别，第

15、六章,59,最小平方误差算法,伪逆法 则梯度 令即,模式识别，第六章,60,最小平方误差算法,伪逆法 可得 解得最佳解向量为： 称为的伪逆矩阵,模式识别，第六章,61,最小平方误差算法,伪逆法 特点：伪逆法要求为非奇异矩阵，其逆才存在 计算较为复杂,模式识别，第六章,62,最小平方误差算法,梯降法 由于 则梯降法的迭代公式为： 算法过程与感知准则梯降法相同,模式识别，第六章,63,isher 线性函数,基本思想：在d维特征空间中，将所有样本投影到一条过原点的直线上，将维数压缩到维 目标：找到一个最优的投影方向，使投影后的样本最易于分类,模式识别，第六章,64,isher 线性函数,模式识别，第

16、六章,65,isher 线性函数,设给定两类学习样本集和，共n个学习样本，其中类样本个，类样本个 现将任意学习样本与权向量作内积： 则即是在方向上投影后的样本,模式识别，第六章,66,isher 线性函数,是一标量，是坐标原点到投影点的距离,模式识别，第六章,67,isher 线性函数,类间离散度 两类样本投影前的均值：,模式识别，第六章,68,isher 线性函数,类间离散度 两类样本投影后的均值 ：,模式识别，第六章,69,isher 线性函数,类间离散度 类间离散度定义为： 反映了两类样本投影后的距离（差异）,模式识别，第六章,70,isher 线性函数,类内离散度 定义类内离散度为投影后样本的方差