第三章 线性判别分析_非参数判别分类方法-第二次课

线性判别分析（LinearDiscriminantAnalysis，LDA）⼀、LDA的基本思想线性判别式分析(Linear Discriminant Analysis, LDA)，也叫做Fisher线性判别(Fisher Linear Discriminant ,FLD)，是模式识别的经典算法，它是在1996年由Belhumeur引⼊模式识别和⼈⼯智能领域的。

线性鉴别分析的基本思想是将⾼维的模式样本投影到最佳鉴别⽮量空间，以达到抽取分类信息和压缩特征空间维数的效果，投影后保证模式样本在新的⼦空间有最⼤的类间距离和最⼩的类内距离，即模式在该空间中有最佳的可分离性。

如下图所⽰，根据肤⾊和⿐⼦⾼低将⼈分为⽩⼈和⿊⼈，样本中⽩⼈的⿐⼦⾼低和⽪肤颜⾊主要集中A组区域，⿊⼈的⿐⼦⾼低和⽪肤颜⾊主要集中在B组区域，很显然A组合B组在空间上明显分离的，将A组和B组上的点都投影到直线L上，分别落在直线L的不同区域，这样就线性的将⿊⼈和⽩⼈分开了。

⼀旦有未知样本需要区分，只需将⽪肤颜⾊和⿐⼦⾼低代⼊直线L的⽅程，即可判断出未知样本的所属的分类。

因此，LDA的关键步骤是选择合适的投影⽅向，即建⽴合适的线性判别函数（⾮线性不是本⽂的重点）。

⼆、LDA的计算过程1、代数表⽰的计算过程设已知两个总体A和B，在A、B两总体分别提出m个特征，然后从A、B两总体中分别抽取出、个样本，得到A、B两总体的样本数据如下：和假设存在这样的线性函数（投影平⾯），可以将A、B两类样本投影到该平⾯上，使得A、B两样本在该直线上的投影满⾜以下两点：（1）两类样本的中⼼距离最远；（2）同⼀样本内的所有投影距离最近。

我们将该线性函数表达如下：将A总体的第个样本点投影到平⾯上得到投影点，即A总体的样本在平⾯投影的重⼼为其中同理可以得到B在平⾯上的投影点以及B总体样本在平⾯投影的重⼼为其中按照Fisher的思想，不同总体A、B的投影点应尽量分开，⽤数学表达式表⽰为，⽽同⼀总体的投影点的距离应尽可能的⼩，⽤数学表达式表⽰为，，合并得到求从⽽使得得到最⼤值，分别对进⾏求导即可，详细步骤不表。

判别分析公式Fisher线性判别二次判别判别分析是一种常用的数据分析方法，用于根据已知的类别信息，将样本数据划分到不同的类别中。

Fisher线性判别和二次判别是两种常见的判别分析方法，在实际应用中具有广泛的应用价值。

一、Fisher线性判别Fisher线性判别是一种基于线性变换的判别分析方法，该方法通过寻找一个合适的投影方向，将样本数据投影到一条直线上，在保持类别间离散度最大和类别内离散度最小的原则下实现判别。

其判别函数的计算公式如下：Fisher(x) = W^T * x其中，Fisher(x)表示Fisher判别函数，W表示投影方向的权重向量，x表示样本数据。

具体来说，Fisher线性判别的步骤如下：1. 计算类别内离散度矩阵Sw和类别间离散度矩阵Sb；2. 计算Fisher准则函数J(W)，即J(W) = W^T * Sb * W / (W^T * Sw * W)；3. 求解Fisher准则函数的最大值对应的投影方向W；4. 将样本数据投影到求得的最优投影方向上。

二、二次判别二次判别是基于高斯分布的判别分析方法，将样本数据当作高斯分布的观测值，通过估计每个类别的均值向量和协方差矩阵，计算样本数据属于每个类别的概率，并根据概率大小进行判别。

二次判别的判别函数的计算公式如下：Quadratic(x) = log(P(Ck)) - 0.5 * (x - μk)^T * Σk^-1 * (x - μk)其中，Quadratic(x)表示二次判别函数，P(Ck)表示类别Ck的先验概率，x表示样本数据，μk表示类别Ck的均值向量，Σk表示类别Ck的协方差矩阵。

具体来说，二次判别的步骤如下：1. 估计每个类别的均值向量μk和协方差矩阵Σk；2. 计算每个类别的先验概率P(Ck)；3. 计算判别函数Quadratic(x)；4. 将样本数据划分到概率最大的类别中。

判别分析公式Fisher线性判别和二次判别是常见的判别分析方法，它们通过对样本数据的投影或概率计算，实现对样本数据的判别。

1. 问题之前我们讨论的PCA、ICA也好，对样本数据来言，可以是没有类别标签y的。

回想我们做回归时，如果特征太多，那么会产生不相关特征引入、过度拟合等问题。

我们可以使用PCA 来降维，但PCA没有将类别标签考虑进去，属于无监督的。

比如回到上次提出的文档中含有“learn”和“study”的问题，使用PCA后，也许可以将这两个特征合并为一个，降了维度。

但假设我们的类别标签y是判断这篇文章的topic是不是有关学习方面的。

那么这两个特征对y几乎没什么影响，完全可以去除。

再举一个例子，假设我们对一张100*100像素的图片做人脸识别，每个像素是一个特征，那么会有10000个特征，而对应的类别标签y仅仅是0/1值，1代表是人脸。

这么多特征不仅训练复杂，而且不必要特征对结果会带来不可预知的影响，但我们想得到降维后的一些最佳特征（与y关系最密切的），怎么办呢？2. 线性判别分析（二类情况）回顾我们之前的logistic回归方法，给定m个n维特征的训练样例（i从1到m），每个对应一个类标签。

我们就是要学习出参数，使得（g 是sigmoid函数）。

现在只考虑二值分类情况，也就是y=1或者y=0。

为了方便表示，我们先换符号重新定义问题，给定特征为d维的N个样例，，其中有个样例属于类别，另外个样例属于类别。

现在我们觉得原始特征数太多，想将d维特征降到只有一维，而又要保证类别能够“清晰”地反映在低维数据上，也就是这一维就能决定每个样例的类别。

我们将这个最佳的向量称为w（d维），那么样例x（d维）到w上的投影可以用下式来计算这里得到的y值不是0/1值，而是x投影到直线上的点到原点的距离。

当x是二维的，我们就是要找一条直线（方向为w）来做投影，然后寻找最能使样本点分离的直线。

如下图：从直观上来看，右图比较好，可以很好地将不同类别的样本点分离。

接下来我们从定量的角度来找到这个最佳的w。

首先我们寻找每类样例的均值（中心点），这里i只有两个由于x到w投影后的样本点均值为由此可知，投影后的的均值也就是样本中心点的投影。

线性判别函数5.1引言在第三章中我们假设概率密度函数的参数形式已知,于是可以使用训练样本来估计概率密度函数的参数值.在本章中,我们将直接假定判别函数的参数形式已知,而用训练的方法来估计判别函数的参数值.我们将介绍求解判别函数的各种算法,其中一部分基于统计方法,而另一些不是.这里都不要求知道有关的概率密度函数的确切的(参数)形式,从这种意义上来说,它们都属于非参数化的方法.在这一章中,我们将关注以下形式的判别函数:它们或者是X的各个分量的线性函数,或者是关于以X为自变量的某些函数的线性函数.线性判别函数具有许多优良的特性,因而便于进行分析.就像我们在第二章看到的一样,如果内在的概率密度函数恰当的话,那么采用线性判别函数是最优的,比如通过适当的选择特征提取方法,可以使得各个高斯函数具有相等的协方差矩阵.即使它们不是最优的,我们也愿意牺牲一些分类准确率,以换取处理简便的优点.线性判别函数的计算是相当容易的,另外,当信息比较缺乏时,线性分类器对处于最初的.尝试阶段的分类器来说也是很有吸引力的选择.它们所展示的一些非常重要的原理在第6章的神经网络中将得到更充分的应用.寻找线性差别函数的问题将被形式为极小化准则函数的问题.以分类为目的的准则函数可以是样本风险,或者是训练误差,即对训练样本集进行分类所引起的平均损失.但在这里我们必须强调的是:尽管这个准则是很有吸引力的,但它却有很多的问题.我们的目标是能够对新的样本进行分类,但一个小的训练误差并不能保证测试误差同样的小-------这是一个吸引人而又非常微妙的问题,我们将在第9章中进一步论述这个问题.这里我们将看到,准确的计算极小风险判别函数通常是困难的,因此我们将考查一些有关的更易于分析的准则函数.我们的注意力将在很大程度上放在收敛性用各种应用于极小化准则函数的梯度下降法的计算复杂度上,它们当中一些方法的是很相似的,这使得清晰地保持它们之间的不同变得困难,因此,我们在后面的章节里会作出总结.5.2线性判别函数的判定面一个判别函数是指X的各个分量的线性组合而成的函数g(x)=w’x+w0 (1)这里W是权向量,w0被称为阈值权或偏置.和我们在第二章所看到的一样,一般情况下有C个这样的判别函数,分别对应C类的一类.我们在后面将讨论这样的情况,但首先考虑中人两个类别的简单情况.5.2.1两类情况对具有式(1)形式的判别函数的一个两类线性分类器来说,要求实现以下判定规则:如果G(x)>0则判定w1,如果g(x)<0,那么x可以被随意归到任意一类,但是在本章我们将它们归为未定义的.图5-1给出了一个典型的系统实现结构,是第二章所讨论的典型的模式识别系统结构的一个例子.图5-1一个简单线性分类器,有d个输入的单元,每个对应一个输入向量在各维上的分量值.每个输入特征值xi被乘以它对应的权wi, 输出单元为这些乘积的和∑wixi.因此这d个输入单元都是线性的,产生的是它对应的特征的值.惟一的一个偏差单元总是产生常数 1.0.如果w’x+w0>0的话,输出单元输出a+1,反之为a-1方程g(x)=0定义了一个判定面,它把归类于w1的点与归类于w2的眯分开来.当g(x)是线性的,这个平面被称为超平面.如果x1和x2都在判定面上,则w’x1+w0=w’x2+w0或W’(x1-x2)=0这表明,w和超平面上的任意向量正交.通常,一个超平面H将特征空间分成两个半空间,即对应于W1类的决策域R1和对应于W2的决策域R2.因为当X在R1中时,g(x)>0,所以判定面的法向量W指向R1,因此,有时称R1中的任何X在H的”正侧”,相应地,称R2中的任何向量在H的负侧.判别函数g(x)是特征空间中某点X到超平面的距离的一种代数度量.或许这一点最容易从表达式X=xp+r(w/IIwII)看出来,这里的XP是X在H上的投影向量,r是相应的算术距离------如果为正,表示X在H的正侧;如果为负,表示X在H的负侧.于是,由于g(xp)=0,有g(x)=w’x+w0=rIIwII或R=g(X)/IiwII特别,从原点到H的距离为W0/IiwII.如果W0>0表明原点在H的正侧,w0<0表明原点在H的负侧.如果W0=0,那么g(x)有齐次形式w’x,说明超平面H通过原点.图5---2对这些代数结果给出了几何解释.总之,线性判别函数利用一个超平面判定面把特征空间分割成两个区域.超平面的方向由法向量W确定,它的位置由阈值权W0确定.判别函数g(x)正比于x点到超平面的代数距离(带正负号).当X在H正侧时,g(x)>0,在负侧时,g(x)<0.5.2.2多类的情况利用线性判别函数设计多类分类器有多种方法,例如,可以把C类问题转化为C个两类问题,其中第I个问题是用线性判别函数把属于WI类的点与不属于W1类的分开.更复杂一些的方法是用c(c-1)/2个线性判别函数,把样本分为C个类别,每个线性判别函数只对其中的两个类别分类,如图5-3所示.这两种方法都会产生如无法确定其类型的区域.为此,我们采用在第二章采用的方法,通过定义C个判别函数Gt(x)=wt’xt+wi0 i=1......c (2)5.4二类线性可分的情况假设我们在一个包含N个样本的集合y1,y2,……yn,一些标记为w1,另一些标记为w2.我们希望用这样的样本确定一个判别函数g(x)=a’y的权向量a.假设我们有理由相信存在一个解,它产生错误的概率非常小.那么一个很合理的想法是寻找一个能将所有这些样本正确分类的权向量.如果这个权向量存在,这些样本就被称为线性可分的.对于一个样本yi,如果有a’yi>0就标记为w1,如果小于0,就标记为w2.这样,我们可以用一种规范化操作来简化二类样本的训练过程,也就是说对属于W2的样本,用负号表示而不是标记W2.有了规范化,我们可以忘掉这些标记,而寻找一个对所有样本都有a’yi>0的权向量a.这样的向量被称为分离向量,更正规的说法是解向量.5.4.1几何解释和术语求解权向量的过程可认为是确定权空间中的一点.每个样本都对解向量的可能位置给出限制.等式a’yi=0确定一个穿过权空间原点的超平面,yi为其法向量.解向量-----如果存在的话,必须在每个超平面的正侧.也就是说,解向里如果存在,必在N个正半空间的交叠区,而且该区中的任意向量都是解向量.我们称这样的区域为解区域,注意不要将它和任何特定类对应的特征空间的判决区域相混淆.对于二维问题.我们用图5.8说明解区域的情况,其中包含了规范化样本和未规范化样本.从以上讨论可知,解向量如果存在的话,通常不是惟一的.有许多方法引入一些附加要求来对解向量进行限制.一种可能的方法是找到一个单位长度的权向量,它使得从样本到分类平面最小距离达到最大.另一种方法是在所有I中寻找满足a’yi>=b的有最小长度的权向量,这里的b是被称为边沿裕量或间隔的正常数.正如图5—9所示的,新的解区域位于由a’yi>=b>0所产生的正半空间的交叠区,它是在原解区之中,且它和原解区边界被隔开的距离为b/IIyiII.我们一般试图在解区域的中间位置来寻找解向量,这背后的动机是一个自然的信念,认为这样的解更能将新测试样本正确地分类.但在大多数情况下,我们对解区域中的任何解都感到满意.而主要关心的是任何一种可行的递归算法,只是它的递归过程能够不收敛到边界点上即可.这个问题可通过引入一个边沿裕量来解决,比如要求对所有的I都有a’yi>=b>0.5.7不可分的情况当样本是线性可分的时候,感知器法和松弛法给我我们许多寻找分类向量的简单方法.这些都被称为误差校正方法,这是因为它们只在遇到错分样本时才对权向量进行校正.它们对可分问题的成功之处在于对求得一个无解进行坚持不懈的摸索.实际上只有在有理由认为最优线性判别函数的误差率比较低的时候才会考虑使用这些方法.当然,即使对训练样本的分离向量已经找到,也不能保证它对独立的测试数据都能很好地分类.我们感觉有种直觉印象,它表明数目少于2d的样本集很可能是线性可分的----我们会在第九章再次考察这一点.因此有人可能会想到:对设计好的样本集使用多次,综合多种因素来获得分类器,并由此确保它在训练和实际数据上的分类性能是相同的.不幸的是,如果使用非常多的数据的话,它们往往不是线性可分的.这样,当样本不是线性可分时了解误差校正方法的效果如何就变得非常重要了.由于不存在可以将不可分数据集中的样本都能正确分类的权向量(由定义可知),显然误差校正过程永远不会结束.这些算法都将产生一个无限的权向量序列,所有的成员都有可能或者不可能得到有用的解.在一些特殊的例子中,这些算法在不可分的情况下的行为被全面的研究过.比如,固定增量算法得到的权向量的幅值波动的趋势.从理论的观点来看,如果样本的分量是整数值的话,固定增量算法将产生一个有限状态过程.如果校正过程停在任意一个状态上,权向量可能正处于,也可能不处于好的状态上.如果对校正算法得到的权向量求均值的话,就可以降低偶然选到处于不好状态上的坏向量的风险.有许多类似的启发式规则被用于修改误差校正算法,并进行了实验研究.修改的目的是在不可分的问题中得到令人接受的结果,同时保持它对可分问题仍能正确分类的性质.最普通的想法是使用变增量Q(K),且当K趋向无穷大时Q(K)趋向0.Q(K)趋向0的速度是相当重要的.如果它太慢的话,得到的结果对那些使得集合为不可分的样本仍然敏感.如果太快,权向量在还没有得到最优结果的时候就收敛了.一种选择Q(K)的方法是今它为当前性能的函数,也即当性能提高的时候减小Q(K).另一种方法是选择Q(K)=Q(1)/K.当研究随机逼近技术的时候,我们发现后一种方法是一种类似问题的理论解.但在展开这个主题之前,我们先考一种在可分和不可分情况下都有很好性能的折中方法,它不再试图直接获取分离向量.本章小结本章给出了一些判别函数,它们都是某个参数集的线性函数,而这些参数一般被称为权系数.在所有两类样本集的情况下这些判别都能确定一个判定超平面,它可能是位于样本自身的原始特征空间中,也可能是位于原始特征通过一个非线性函数(通常是线性判别式)映射而得到的空间.从更广的角度看.感知器算法是一类技术是通过调整参数来提高与W1的样本的内积,而降低与W2的样本的内积.一个更通用的方法是构造准则函数进行梯度下降.不同的准则函数在计算复杂度和收敛性方面各有不同的优缺点,没有哪个方法说是比别的方法都好.我们也可以通过线性代数运算来直接求得权(参数).比如对小型问题采用伪逆的方法.在支持向量机中,输入被非线性函数映射到一个更高维的空间,最优超平面就是具有最大“间隔”(margin)的平面.支持向量就是用来确定间隔的(变换后的)样本,它们通常是那些最难被分类,却能给分类器提供最多信息的样本.分类器期望误差率的上界线性依赖于支持向量的期望个数.对多类问题,线性机产生了由一些部分超平面构成的判定面.为了证明多类算法的收敛性可先将它们转化成两类算法再用两类法的证明.单纯型算法用来寻找由(不等式)约束的一个线性函数的优化.它也能被用来训练线性分类器.线性判别函数虽然很有用,对任意的很具挑战性的模式识别问题却不有足够的通用性(比如那些包含多模的或非凸密度的问题),除非能找到一个适当的非线性映射(Q函数).这一章我们没有给出如何选择这些函数的原则,但我们会在第六章讲述这个主题.文献的历史评述因为线性判别函数是易于分析的,在这方面有极大量的文章,尽管它的内容有限而不值得有这么多的文章.历史上,所有这方面的工作都是从ronald A.Fisher(5)的经典论文开始的.文献9很好描述了线性判别函数在模式识别中的应用,它提出了最优化(最小风险)线性判别问题并建议采用适当的梯度下降从样本中求得解.然而,在不知道内在的分布时,我们对这些方法的适用程度的了解是很有限的,即使是有条件的分析也是很复杂的.用两类方法来设计多类分类器来自于文献16.Minsky和papert的感知器一书强有力地指出了线性分类器的弱点------但可以用我们将在第六章中学习的方法来解决.无差错情况下的Winnow算法10以及更一般情况下的后续工作在计算(机器)学习领域是非常有用,它们都允许导出收敛的界.虽然这些工作都是基于统计的,许多从其他观点出发的模式识别的文章出现在20世纪50年代末和60年代初.其中一种观点是神经网络的,每一个单独的神经无被建模成阈值元----即两类的线性机,这些工作都是从McCulloch和Pitts12的著名的论文开始的.。

第三章判别函数与确定性分类器引言♦第二章主要讨论了在概率密度或概率函数的基础上设计分类器。

在有些情况下，分类器等价于一组线性判别函数。

♦本章主要讨论线性分类器的设计，最主要的是了解它在模式识别技术中所处的地位。

这种方法绕过统计分布状况的分析，绕过参数估计这一环，而对特征空间实行划分，称为非参数判别分类法，即不依赖统计参数的分类法。

这是当前模式识别中主要使用的方法，并且涉及到人工神经元网络与统计学习理论等多方面，是本门课最核心的章节之一。

线性分类器主要的优点是简单和可计算性。

♦从这一章起，假设来自于已知类的所有特征向量都可以用线性分类器正确分类，我们将研究相应的线性函数的计算方法，然后讨论更一般问题。

对于不能将所有向量正确分类的线性分类器，我们寻找通过采用应的优化规则设计最优线性分类器的方法。

♦贝叶斯方法与线性、非线性分类器的关系与比较图4．1理想的概率分布♦ 学习这一章要体会模式识别中以确定准则函数并实现优化的计算框架。

第一节 线性判别函数与广义线性判别函数判别函数有线性和非线性之分，而非线性判别函数又可以转化为线性形式，故首先讨论线性判别函数。

一、 两类判别问题假定有1ω和2ω两类模式，在二维模式特征空间，可用一直线将其分开，如图3—1—1所示。

假定这一直线方程为d(x )=1250x x +-=，那么很明显，凡使d(x )>0的模式i x 必属于1ω类；反之，使d(x )<0的模式i x 必属于2ω类。

于是将d(x )=125x x +-作为判别函数。

一般说来，这种将直线作为界线的判别函数的形式为：式中，i w 为参数，1x 、2x 为模式样本的特征值。

，将此判别函数推广到n 维，且用向量12(,,...,)T n x x x =x 表示模式样本，则有内积形式12()n +...++n n 2d w x w w w x x x +=+11 （3-1-2）T 0n w w x +=+1式中w =)(,,...,T l w w w 12叫权向量，w 0是阈值，若将x 和w 写成增广向量，则121(,,...,,)T n n w w w w +=w ，12(,,...,,1)T n x x x =x则式（3-1-2）可以写成更简练的形式()d T x w x = （3-1-3）判别函数及决策超平面在n 维特征空间中，在线性可分得情况下，决策超曲面是一个超平面。