fisher判别

模式识别线性分类器上海大学计算机工程与科学学院信息处理与多媒体研究所RonaldAylmerFisher(1890～1962)英国统计学家和遗传学家。1890年2月17日生于伦敦,1962年7月29日卒于澳大利亚阿德莱德。1912年毕业于剑桥大学数学系，后随英国数理统计学家J.琼斯进修了一年统计力学。他担任过中学数学教师，1918年任罗坦斯泰德农业试验站统计试验室主任。1933年，因为在生物统计和遗传学研究方面成绩卓著而被聘为伦敦大学优生学教授。1943年任剑桥大学遗传学教授。1957年退休。1959年去澳大利亚，在联邦科学和工业研究组织的数学统计部作研究工作。主要贡献有：①用亲属间的相关说明了连续变异的性状可以用孟德尔定律来解释，从而解决了遗传学中孟德尔学派和生物统计学派的论争。②论证了方差分析的原理和方法，并应用于试验设计，阐明了最大似然性方法及随机化、重复性和统计控制的理论，指出自由度作为检查K.皮尔逊制定的统计表格的重要性。此外，还阐明了各种相关系数的抽样分布，进行过显著性测验研究。③他提出的一些数学原理和方法对人类遗传学、进化论和数量遗传学的基本概念以及农业、医学方面的试验均有很大影响。例如遗传力的概念就是在他提出的可将性状分解为加性效应、非加性（显性）效应和环境效应的理论基础上建立起来的。④主要著作有：《根据孟德尔遗传方式的亲属间的相关》、《研究者用的统计方法》、《自然选择的遗传理论》、《试验设计》、《近交的理论》及《统计方法和科学推理》等。他在进化遗传学上是一个极端的选择论者，认为中立性状很难存在。他一生在统计生物学中的功绩是十分突出的。计算机工程与科学学院ShanghaiUniversity上海大学主要内容1.线性判别函数基本概念几何意义2.广义线性判别函数3.设计线性分类器的主要步骤4.Fisher线性判别问题的提出算法的实现Fisher线性判别实验计算机工程与科学学院ShanghaiUniversity上海大学引言训练样本集各类别在特征空间的分布表示成先验概率、类条件概率密度分布函数决策规则、判别函数、决策面方程选择最佳准则函数最一般情况下适用的“最优”分类器：错误率最小，对分类器设计在理论上有指导意义。需要首先得到有关样本总体分布的知识，包括各类先验概率P(ωi)及类条件概率密度P(X|ωi)，从而可以计算出样本的后验概率P(ωi|X)，并以此作为产生判别函数的必要数据，设计出相应的判别函数与决策面。获取统计分布及其参数很困难，实际问题中并不一定具备获取准确统计分布的条件。贝叶斯决策理论计算机工程与科学学院ShanghaiUniversity上海大学引言非参数判别方法：训练样本集选择最佳准则这种方法跳过了统计分布的参数估计，没有使用统计参数作为依据，因此称为非参数判别分类方法。而以贝叶斯决策方法为基础的方法则称为参数判别方法。Bayes决策尽管是最优决策，但实现困难。模式识别的任务是分类，可直接设计判别函数—即分类面。最简单的判别函数是线性函数，相应的分类面是超平面。这些准则的“最优”并不一定与错误率最小相一致：次优分类器。结论:决策规则：判别函数决策面方程不需要有关的概率密度函数的确切的参数形式计算机工程与科学学院ShanghaiUniversity上海大学非参数判别分类方法的基本原理——有监督学习方法线性分类器Fisher准则线性分类器感知准则函数线性分类器svm非线性分类器的扩展—分段线性多层感知器特征映射方式实现线性分类器近邻法改进的近邻法引言计算机工程与科学学院ShanghaiUniversity上海大学1212,,...,,...TdTdx=xxxw=()Tgxwxw设样本d维特征空间中描述，则两类别问题中线性判别函数的一般形式可表示成其中w0是一个常数，称为阈值权。g(x)＝0就是相应的决策面方程，在线性判别函数条件下它对应d维空间的一个超平面。12g0g0g0xxxxx(),则决策如果(),则决策()=,可将其任意分类或拒绝线性判别函数的基本概念相应的决策规则可表示成计算机工程与科学学院ShanghaiUniversity上海大学至于w0则体现该决策面在特征空间中的位置，当w0=0时，该决策面过特征空间坐标系原点，而时，则表示了坐标原点到该决策面的距离。为了说明向量w的意义，我们假设在该决策平面上有两个特征向量x1与x2，则应有其中(x1-x2)也是一个向量而g(x)也就是d维空间中任一点x到该决策面距离的代数度量，该决策平面将这两类样本按其到该面距离的正负号确定其类别。上式表明向量w与该平面上任两点组成的向量(x1-x2)正交，因此w就是该超平面的法向量。这就是向量w的几何意义。102102()0TTTwxwwxwwxx线性判别函数的基本概念计算机工程与科学学院ShanghaiUniversity上海大学令决策面(decisionboundary)H方程：g(x)=0向量w是决策面H的法向量g(x)是点x到决策面H的距离的一种代数度量ppg(x)=rwwx=x+r,wxwwxHxrwH是在上的投影向量是到的垂直距离是方向上的单位向量0()Tgxwxw线性判别函数的几何意义计算机工程与科学学院ShanghaiUniversity上海大学线性判别函数的几何意义令0()Tgxwxww=r000()wwxgxwHr若为原点，则原点到超平面的距离：000000wHwHwH原点在的正侧原点在的负侧通过原点总之，利用线性判别函数进行决策，就是用一个超平面把特征空间分割成两个决策区域。超平面的方向由权向量w确定，他的位置由阈值权w0确定。判别函数g(x)正比于x点到超平面的代数距离（带正负号）。当x在H正侧时，g(x)0；在负侧时，g(x)0。计算机工程与科学学院ShanghaiUniversity上海大学广义线性判别函数12()0()0gxxwgxxw决策决策线性判别函数是形式最为简单的判别函数，但是它不能用于稍复杂一些的情况。欲设计这样一个一维样本的分类器，使其性能为针对这种情况，如果设计这样一个判别函数:g(x)＝(x-a)(x-b)相应的决策规则:12xbxaxwbxaxw或决策决策此时,g(x)不再是x的线性函数，而是一个二次函数计算机工程与科学学院ShanghaiUniversity上海大学广义线性判别函数如果我们采用映射x→y，使则判别函数g(x)又可表示成此时g(x)被称为广义线性判别函数，a称为广义权向量。31()Tiiigxayay2012()gxccxcx11022123321yacyxacyxacya，选择一种映射x→y，即将原样本特征向量x映射成另一向量y，从而可以采用线性判别函数的方法。计算机工程与科学学院ShanghaiUniversity上海大学广义线性判别函数ˆY()ˆHTgxayraay空间任意一点到的距离为：线性判别函数的齐次简化：一种特殊映射方法：增广样本向量y与增广权向量a()TT0gx=wx+w=ay线性判别函数的齐次简化使特征空间增加了一维，但保持了样本间的欧氏距离不变，对于分类效果也与原决策面相同，只是在Y空间中决策面是通过坐标原点的，这在分析某些问题时具有优点，因此经常用到。计算机工程与科学学院ShanghaiUniversity上海大学广义线性判别函数例如一个一维特征空间的分类器，其决策面方程为x-c=0在一维空间中为一个点。经齐次简化后可得：此时在二维空间中决策面为一过原点的直线，如下页图所示。直线以为法线向量，它对1维子空间(y2空间)的划分与原决策面完全相同。计算机工程与科学学院ShanghaiUniversity上海大学广义线性判别函数由于样本向量在增加一维后变成了一个二维向量，因此原一维空间讨论的问题，转变成在二维空间讨论的问题，而原方程也变成了一条直线，它过二维空间的原点。计算机工程与科学学院ShanghaiUniversity上海大学设计线性分类器的主要步骤•在给定样本集条件下，确定线性判别函数的各项系数，以期对待测样本进行分类时，能满足相应的准则函数J为最优的要求。•用最优化技术确定权向量阈值权或增广权向量线性分类器设计任务是：计算机工程与科学学院ShanghaiUniversity上海大学设计线性分类器的主要步骤给定样本集X，确定线性判别函数的各项系数w和w0。步骤：收集一组具有类别标志的样本X={x1,x2,…,xN}按需要确定一准则函数J，其值反映分类器的性能，其极值解对应于“最好”的决策。用最优化技术求准则函数J的极值解w*和w0*，从而确定判别函数，完成分类器设计。*maxwwJ对于未知样本x，计算g(x)，判断其类别。这样就可以得到线性判别函数g(x)=w*T+w0*或g(x)=a*Ty计算机工程与科学学院ShanghaiUniversity上海大学Fisher线性判别•Fisher线性判别函数是研究线性判别函数中最有影响的方法之一。对线性判别函数的研究就是从R.A.Fisher在1936年发表的论文开始的。计算机工程与科学学院ShanghaiUniversity上海大学Fisher线性判别问题的提出：Fisher线性判别函数的提出：在用统计方法进行模式识别时，许多问题涉及到维数，在低维空间行得通的方法，在高维空间往往行不通。因此，降低维数就成为解决实际问题的关键。Fisher的方法，就是解决维数压缩问题。考虑把d维空间中的数据点投影到一条直线上去的问题，需要解决的两个问题：(1)怎样找到最好的投影直线方向；(2)怎样向这个方向实现投影，这个投影变换就是要寻求的解向量w*。这两个问题就是Fisher方法要解决的基本问题。对xn的分量做线性组合可得标量yn=wTxn,n=1,2,…,Ni这样便得到N个一维样本yn组成的集合。从而将多维转换到了一维。计算机工程与科学学院ShanghaiUniversity上海大学Fisher线性判别Fisher准则的基本原理：分析w1方向之所以比w2方向优越，可以归纳出这样一个准则，即向量w的方向选择应能使两类样本投影的均值之差尽可能大些，而使类内样本的离散程度尽可能小。这就是Fisher准则函数的基本思路。Fisher准则的基本原理，就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。计算机工程与科学学院ShanghaiUniversity上海大学Fisher线性判别几个必要的基本参量：1.样本在d维X空间11,2kiikxXimxin，(2)样本类内离散度矩阵Si与总类内离散度矩阵Sw(3)样本类间离散度矩阵Sb其中，Sw是对称半正定矩阵，而且当Nd时通常是非奇异的。Sb也是对称半正定矩阵，在两类情况下，它的秩最大等于1。Tb1212S=(m-m)(m-m)(1)各类样本均值向量mi计算机工程与科学学院ShanghaiUniversity上海大学Fisher线性判别几个必要的基本参量：1.样本在一维Y空间(2)样本类内离散度和总类内离散度1,1,2iiyYimyiN2(),1,2iiiyYSymi12wSSS212()bSmm(1)各类样本均值计算机工程与科学学院ShanghaiUniversity上海大学Fisher线性判别根据Fisher选择投影方向w的原则：使原样本向量在该方向上的投影能兼顾：类间分布尽可能分开，类内样本投影尽可能密集。用以评价投影方向w的函数为：2121212()()bFSmmJwSSSS这个函数称为Fisher准则函数。应该寻找使分子尽可能大，分母尽可能小的w作为投影向量。定义Fisher准则函数：计算机工程与科学学院ShanghaiUniversity上海大学Fishe