模式识别 线性判别函数

模式识别第三次学习总结陈书燊线性判别函数1引言2Fisher线性判别函数3感知器准则函数4最小错分样本数准则5最小平方误差准则6本章小结引言▷Bayes决策规则尽管是最优的，但是实现困难。原因就是要求已知类条件概率密度和先验概率。▷上一章所讲基于样本的两步贝叶斯决策而设计的分类器是在已知类条件概率密度的参数表达式和先验概率的情况下，利用样本估计类条件概率密度的参数，再用贝叶斯公式将其转换成后验概率，并根据后验概率的大小进行分类决策的方法。但在实际问题中也很难确定样本特征空间的类条件概率密度的形式，利用窗函数法或者近邻法又往往需要大量样本，而且随着特征空间维数的增加所需样本数急剧增加。引言▷模式识别的最终任务是分类，在实际问题中往往不去恢复类条件概率密度，而是利用样本集直接设计分类器。具体的说就是先给定某个判别函数类，然后利用样本集确定判别函数中的未知参数。▷最简单的判别函数是线性函数，最简单的分界面是超平面，采用线性判别函数所产生的错误率或风险虽然可能比贝叶斯分类器来的大。不过，它简单，容易实现，而且需要的计算量和存储量小。因此，可以认为，线性判别函数是统计模式识别的基本方法之一，也是实际应用中最常用的方法之一。线性判别函数的基本概念线性判别函数的一般形式为：其中X是一个d维特征向量,W。是一个常数，称为阈值权，W称为权向量。线性判别函数的基本概念00线性判别函数g(x)=0定义了一个超平面H，称为决策面，即分界面，它把特征空间分成了两个半空间。广义的线性判别函数若给定一个一维的模式空间，希望的划分是Xa或Xb，则决策X∈ω1；若aXb，则决策X∈ω2。ab广义的线性判别函数通过对上图的分析，可以建立如下的一个二次判别函数：（X-a）（X-b）决策规则为：若该函数的值大于0，则决策X∈ω1；若该函数的值小于0，则决策X∈ω2。广义的线性判别函数上述的二次判别函数写成如下的一般形式，便有像这样的函数不是线性的，但通过适当的变换可以转换为线性判别函数：广义的线性判别函数则是y的线性函数设计线性分类器的主要步骤1.要有一组具有类别标志的样本集，如果在样本被抽出后，把它看作一个确定的观察值，则这组样本集称为确定性样本集；若是一个随机变量，则这组样本集称为随机样本集。2.要根据实际情况确定一个准则函数J，它必须满足：①J是ω或a的函数；②J的值反映分类器的性能，它的极值解则对应于“最好”的决策。3.用最优化技术求出准则函数的极值解。Fisher线性判别由于线性判别函数易于分析，考虑把d维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维。若把它们投影到一条任意的直线上，就可能使几类样本混合在一起而无法识别，但在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分开的最好。问题是如何根据实际情况找到这条最好的,最易于分类的投影线，这就是Fisher法所要解决的基本问题。Fisher线性判别要找一个最好的投影方向b，使下面的准则函数达到最大值。其中感知准则函数1．线性可分性对一组样本集y1,…,yN，假定来自两类，若存在一个权向量a，使得当时，有时，有则称这组样本是线性可分的感知准则函数2.样本的规范化若样本是线性可分的，则总存在权向量a能把每个样本正确分类。即使得，对，对对第二类的样本，若在yj前加一负号yj’=-yj，则aTyi’0感知准则函数，当，当即若令这时问题就化为找一个a，使对所有的yn，有aTyn0，上述的处理称为规范化，称为规范化的增广样本。感知准则函数3.解向量和解区在线性可分的情况下，满足aTyi0，i=1,2,…,N的a称为权向量，记为a*。一个权向量a是权空间中的一个点，每个样本yi对a的可能位置都起到限制作用。即要满足aTyi0，对所有样本满足aTyi0的a即为一个解。感知准则函数方程aTyi=0确定了权空间中过原点的一个超平面Hi，它的法向量是yi。解应在Hi的正侧（因为要求aTyi0）正半空间。N个样本确定了权空间中的N个平面，每个平面把权空间分成了三部分，正侧、负侧和平面本身。所以，如果解存在，则必定在N个超平面的正半空间的相交区,这个区域称为解区，区域中的每个向量都是解向量a*。最小错分样本数准则由于感知准则函数及其梯度下降算法只适用于线性可分情况，对于线性不可分情况，迭代过程永远不会终结，即算法不收敛。但在实际问题中往往无法事先知道样本集是否线性可分，因此，希望找到一种既适用于线性可分情况，又适用于线性不可分情况的算法。这里介绍的最小错分样本数准则就是为解决上述问题而提出的，其中有一下两种优化方法：.解线性不等式组的共轭梯度法.解线性不等式组的搜索法最小平方误差准则对于规范化的增广样本向量，yi=1,…,N，要找a，使得aTyi0,i=1,…,N。这是求N个不等式组解的问题。若线性可分：线性不等式组是一致的，有解--能求出a，使aTyi0,i=1,…,N；若线性不可分：线性不等式组不一致，无解--求一个a，比如说使正确分类的样本数最多，使成立的不等式的个数最多。最小平方误差准则平方误差准则函数求使极小的a作为问题的解。这是矛盾方程组的最小二乘解,称为最小平方误差准则函数（MSE）。定义一个误差向量最小平方误差准则)(aJs下面推导在MSE下的解对求梯度令得本章小结由上述分析可得，应用线性判别函数的方法实际上是如何应用学习样本来确定线性判别函数参数的方法。线性判别函数是形式最简单的判别函数，因它具有设计简单，在一定条件下能实现最优分类的性质，因此在实际中得到了广泛的应用。很多情况下，虽然所研究的问题并不是线性可分的，但因受到维数高，样本数有限等实际情况的限制，仍需要使用线性分类器，即容许有一定误差率的合理性选择，即便使用更复杂的分类器也不一定有很好的效果。