LDA线性判别分析ppt课件.pptx
,Linear Discriminant Analysis(LDA)线性判别分析,目录,LDA扩展,LDA简介,线性判别分析（linear discriminant analysis），也叫Fisher线性判别分析，是特征提取中最为经典和广泛使用的方法之一。LDA是由R.A Fisher于1936年提出来的方法【1】,主要是用来解决生物问题（ Taxonomic Problems ）的分类问题。它是在1996年由Belhumeur【2】引入模式识别和人工智能领域的.,R.A Fisher(1890-1962),LDA思想,线性判别分析（LDA）的基本思想是将高维的模式样本投影到最佳鉴别矢量空间，以达到抽取分类信息和压缩特征空间维数的效果，投影后保证模式样本在新的子空间有最大的类间距离和最小的类内距离，即模式在该空间中有最佳的可分离性。因此，它是一种有效的特征抽取方法。,两类的线性判别问题,两类的线性判别问题可以看作是把所有的样本都投影到一个方向上，然后在这个一维空间中确定一个分类的阈值。过这个阈值点且与投影方向垂直的超平面就是两类的分类面。,如何确定投影方向？,两类的线性判别问题,从直观上看，右图的分类效果比较好，同类之间样本聚集，不同类之间相聚较远,训练样本集：X=x1.xN,每个样本是d维向量，其中w1类的样本是H1=x11.xN1， w2类的样本是H1=x12.xN2，寻找一个投影方向w（d维向量），,两类的线性判别问题,定量分析：投影以后样本变成： i=1,2.N原样本每类样例的均值向量： ( i=1,2) 投影后每类样例的均值： 投影后的均值就是样本中心 点的投影,= 1 , = 1 = 1 =,= ,什么是最佳直线（W）？1.能够是投影后的两类样本的中心点尽量的分离的直线是好的直线，定量表示： J(w)越大越好，但是只考虑J(w)是不行的,两类的线性判别问题,如左图所示，样本点均匀分布在椭圆里，投影到横轴x1上时能够获得更大的中心点间距J(w)，但是由于有重叠，x1不能分离样本点。投影到纵轴x2上，虽然J(w)较小，但是能够分离样本点。因此我们还需要考虑样本点之间的方差，方差越大，样本越分散，样本点越难以分离,两类的线性判别问题,散列值（scatter）,几何意义是样本点的密集程度，值越大，越分散，值越小，越集中。投影前类内离散度矩阵： 总类内离散度矩阵：Sw=S1+S2类间离散度矩阵：,= i=1.2,=(12) 12 ,= , = = =, = ) 2 i=1.2, = 1 + 2, = 1 2 2,投影后：类内离散度：总类内离散度：类间离散度：,两类的线性判别问题,我们希望寻找的投影方向使投影以后两类尽可能分开，而各类内部又尽可能聚集，这一目标可以表示成 Finsher 准则函数目标是求得是上式最大的投影方向wJF(w)是广义的Rayleigh熵,max()= , = = 1 2 2 1 + 2,两类的线性判别问题,当Sw非奇异时，求解转化为Sw-1Sb的特征值问题，使J(w)最大的变换矩阵W由Sw-1Sb的特征值所对应的特征向量组成,多类的线性判别问题,训练样本集：X=x1.xN,每个样本是d维向量，分别属于c个类别从类内离散度和内间离散度来考虑：（假设样本是二维的，从几何意义上考虑）,多类的线性判别问题,最后还归结到了求矩阵的特征值上来了。首先求出 的特征值，然后取前K个特征向量组成W矩阵即可。 注意：由于 中的 秩为1，因此 的秩至多为C（矩阵的秩小于等于各个相加矩阵的秩的和）。由于知道了前C-1个 后，最后一个 可以有前面的 来线性表示，因此 的秩至多为C-1。那么K最大为C-1，即特征向量最多有C-1个。,多类的线性判别问题,实例：,将3维空间上的球体样本点投影到二维上，W1相比W2能够获得更好的分离效果。,PCA选择样本点投影具有最大方差的方向，LDA选择分类性能最好的方向。,LDA扩展,LDA存在限制：1.存在秩限制，即对c类问题最多只能提取c-1个最优鉴别矢量。2. 面对人脸识别等高维小样本问题时，类内离散度矩阵奇异，无法通过最优化规则函数求得最优鉴别矢量集,PCA+LDA【2】 1996,在人脸识别等小样本问题，需要面对的一个难题就是类内散度矩阵Sw总是奇异的，这是由于训练集N中的的图像数是远远小于每幅图像中的像素数的，为了解决这个问题，Belhumecour等人先做一次PCA算法的降维，消除样本的冗余度，解决Sw的奇异问题，然后应用LDA将维数降到c-1维。,PCA的步骤可能会丢弃一些重要的信息,借鉴 准则思想,DLDA【5】2000,主要思想：直接优化Fisher准则，核心就是寻找一个矩阵来同时对角化Sw和Sb,丢弃Sb包含无用信息的零空间，保持含有重要分类信息的Sw的零空间。,在原始维数空间中求解最优鉴别矢量集计算量太大，求解困呐,借鉴 准则思想,MFLDA【4】2007,在高光谱遥感图像中使用经典的LDA算法来进行降维主要存在以下问题：没有足够的训练集，在一个图像场景上不能知道所有现有的类别（例如背景类的个数和特征）。所以对LDA进行改进就提出了MFLDA，改进后只需知道需要的类的信息即可，不需要知道所有的类的信息。分类结果使用MFLDA-transformed 的数据来显示，所需的类的信息被很好的保存并且在低维空间中很容易的被分离出来。,借鉴 准则思想,MFLDA,总离散度矩阵,只知道类的特征S1,S2.Sp,可以把它当作类均值，即M=u1,u1upS1,S2.Sp,Sb等价于：,所有的像素点,借鉴 准则思想,MFLDA,忽略数据中存在的类别，用 代替 代表了一种极端情况：所有的像素被分到他们所属的类中并且被选为样本；用 代替SB代表另一种极端情况：每个类中只有一个样本使用 的好处：在一个图像场景中所有的类的真实数目Pt是远远大于p的,处理所有的这些类是困难的（尤其是背景类），一种理想情况是，图像中所有的像素点都被分到这Pt个类中，这样 ,这就意味着在不知道这些类的信息的情况下，所有的类都被很好的分开。,MLDA【3】 2010,为了解决经典LDA遇到的小样本问题，提出了LDA的改进算法-MLDA。该算法在原始的Fisher准则的基础上对类内离散度矩阵经行标量化处理，避免对类内离散度矩阵求逆，保证Sw在任何情况下都存在。类间离散度矩阵和类内离散度矩阵分别标量化处理，样本空间各维加权后的下式：K表示样本空间的维度，Wk(k=1d)为样本空间各维的权重,各维在样本空间中的重要程度,借鉴 准则思想,MLDA,借鉴 Fisher准则思想,就是要找使上两式之比最大的w值，即：,借鉴 准则思想,MLDA,基本流程：,首先将人脸数据库根据一定规则分为训练样本和测试样本；然后用MLDA对训练样本进行投影后， 得到最佳投影方向； 接着将测试样本投影到该最佳投影方向上，得到投影后的测试样本；最后将投影后的测试样本通过最近邻分类器与训练样本进行特征识别， 得到识别结果.,借鉴 准则思想,MLDA,大样本情况下，验证MLDA的有效性,借鉴 准则思想,MLDA,小样本情况下，验证MLDA的有效性,借鉴 准则思想,MLDA,优点：MLDA彻底改变了以矢量为基本单位的处理方法，把标量作为基本单位对问题求解，使最佳映射方向的确定不受类内离散度矩阵奇异的制约，从而有效的解决了在高维多类模式下特征提取中的小样本问题；降低了运算难度，提高了运算效率缺点：在识别率方面与PCA+LDA方法相比要低一些，算法稳定性受参数 的影响较大。,参考文献,1. A.,F.R.,Theuseofmultiplemeasurementsintaxonomicproblems.Annalsofeugenics,1936.7(2):p.179-188.2. Belhumeur,P.N.,J.P.Hespanha,andD.J.Kriegman,Eigenfacesvs.Fisherfaces:RecognitionUsingClassSpecificLinearProjection.TRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,1997.19(7):p.711-720.3. Yu,H.andJ.Yang,AdirectLDAalgorithmforhigh-dimensionaldata-withapplicationtofacerecognition.PatternRecognition,2000.32(2001):p.2067-2070.4. Du,Q.,ModifiedFishersLinearDiscriminantAnalysisforHyperspectralImagery.GEOSCIENCEANDREMOTESENSINGLETTERS,2007.4:p.503-507.5. 刘忠宝and王士同,一种改进的线性判别分析算法MLDA.计算机科学,2010.37(11):p.239-242.6. Shu,X.,Y.Gao,andH.Lu,Efficientlineardiscriminantanalysiswithlocalitypreservingforfacerecognition.PatternRecognition,2012.45(5):p.1892-1898.,Thank you！,
