04线性分类器

2020/4/27西安电子科技大学计算机学院1第四章线性分类器尚凡华提纲2020/4/27西安电子科技大学计算机学院2线性判别函数Fisher线性判别分析感知器最小平方误差判别线性支持向量机多类线性分类器线性判别函数2020/4/27西安电子科技大学计算机学院3线性判别函数2020/4/27西安电子科技大学计算机学院4线性判别函数的基本概念2020/4/27西安电子科技大学计算机学院5线性判别函数2020/4/27西安电子科技大学计算机学院6x点到决策面的距离grxwprwxxw00TTppgwrwgrrxwxwwxwxww距离线性判别函数2020/4/27西安电子科技大学计算机学院7x点到决策面的距离grxwprwxxw00TTppgwrwgrrxwxwwxwxww距离线性判别函数的基本概念2020/4/27西安电子科技大学计算机学院8线性判别函数的几何意义要寻找一个最佳的投影方向w；投影后将原分类问题转化为一维数据的分类问题。线性判别函数2020/4/27西安电子科技大学计算机学院9广义线性判别函数2020/4/27西安电子科技大学计算机学院10广义线性判别函数2020/4/27西安电子科技大学计算机学院11Fisher线性判别分析2020/4/27西安电子科技大学计算机学院12线性判别分析(LinearDiscriminantAnalysis,LDA)Ref1:AleixM.Martinez,AvinashC.Kak.“PCAversusLDA”.IEEETransactionsonPatternAnalysisandMachineIntelligence,23(2):228-233,2001.3062Ref2:JiepingYe,RaviJanardan,QiLi.“Two-DimensionalLinearDiscriminantAnalysis”.AdvancesinNeuralInformationProcessingSystems(NIPS),pp.1569-1576,2004.587Ref3:PeterN.Belhumeur,Joa~oP.Hespanha,andDavidJ.Kriegman.Eigenfacesvs.Fisherfaces:RecognitionUsingClassSpecificLinearProjection.IEEETransactionsonPatternAnalysisandMachineIntelligence,19(7):711-720,1997.12816Ref4:XiaofeiHe,ShuichengYan,YuxiaoHu,ParthaNiyogi,andHong-JiangZhang.FaceRecognitionUsingLaplacianfaces.IEEETransactionsonPatternAnalysisandMachineIntelligence,27(3):328-340,2005.3342Fisher线性判别分析2020/4/27西安电子科技大学计算机学院13Fisher线性判别分析2020/4/27西安电子科技大学计算机学院14基本概念Fisher线性判别分析2020/4/27西安电子科技大学计算机学院15基本概念Fisher线性判别分析2020/4/27西安电子科技大学计算机学院16基本概念Fisher线性判别分析2020/4/27西安电子科技大学计算机学院17基本概念Fisher线性判别分析2020/4/27西安电子科技大学计算机学院18基本概念Fisher线性判别分析2020/4/27西安电子科技大学计算机学院19Fisher线性判别分析2020/4/27西安电子科技大学计算机学院20Fisher线性判别分析2020/4/27西安电子科技大学计算机学院21Fisher线性判别分析2020/4/27西安电子科技大学计算机学院22Fisher线性判别分析2020/4/27西安电子科技大学计算机学院23Fisher线性判别分析2020/4/27西安电子科技大学计算机学院24Fisher线性判别分析2020/4/27西安电子科技大学计算机学院25主成分分析(PCA)2020/4/27西安电子科技大学计算机学院26主成分分析(PCA)2020/4/27西安电子科技大学计算机学院27主成分分析(PCA)2020/4/27西安电子科技大学计算机学院28主成分分析(PCA)2020/4/27西安电子科技大学计算机学院29EigenfacesExample2020/4/27西安电子科技大学计算机学院30MeanfaceEigenfacesExample2020/4/27西安电子科技大学计算机学院31Facereconstruction:−M.Turk,A.Pentland,EigenfacesforRecognition,JournalofCognitiveNeuroscience,vol.3,no.1,pp.71-86,1991.EigenfacesExample2020/4/27西安电子科技大学计算机学院32BawBawFrog-PCAof16HabitatVariables0.01.02.03.04.05.06.07.012345678910PCAxisNumberEigenvalue主成分分析(PCA)2020/4/27西安电子科技大学计算机学院33PCA方法的优点:1.仅仅需要以方差衡量信息量，不受数据集以外的因素影响；2.各主成分之间正交，可消除原始数据成分间的相互影响的因素;3.计算方法简单，主要运算是特征值分解，易于实现。PCA方法的缺点:1.主成分各个特征维度的含义具有一定的模糊性，不如原始样本特征的解释性强；2.方差小的非主成分也可能含有对样本差异的重要信息，因降维丢弃可能对后续数据处理有影响。主成分分析(PCA)2020/4/27西安电子科技大学计算机学院34PCA的各种变种：1.SparsePCA2.OnlinePCA3.RobustPCA4.ProbabilisticPCA鲁棒主成分分析(RobustPCA)2020/4/27西安电子科技大学计算机学院35鲁棒主成分分析(RobustPCA)2020/4/27西安电子科技大学计算机学院36鲁棒主成分分析(RobustPCA)2020/4/27西安电子科技大学计算机学院37鲁棒主成分分析(RobustPCA)2020/4/27西安电子科技大学计算机学院38鲁棒主成分分析(RobustPCA)2020/4/27西安电子科技大学计算机学院39鲁棒主成分分析(RobustPCA)2020/4/27西安电子科技大学计算机学院40鲁棒主成分分析(RobustPCA)2020/4/27西安电子科技大学计算机学院41LDAvsPCA2020/4/27西安电子科技大学计算机学院42相同点:1.两者均可以对数据进行降维；2.两者在降维时均使用了矩阵特征分解的思想；3.两者都假设数据符合高斯分布。不同点:1.LDA是有监督的降维方法，而PCA是无监督的降维方法；2.LDA降维最多降到类别数C-1的维数，而PCA没有这个限制；3.LDA除了可以用于降维，还可以用于分类；4.LDA选择分类性能最好的投影方向，而PCA选择样本点投影具有最大方差的方向。LDAvsPCA2020/4/27西安电子科技大学计算机学院43LDAvsPCA2020/4/27西安电子科技大学计算机学院44LDA方法的优点:1.在降维过程中可以使用类别的先验知识经验，而像PCA这样的无监督学习则无法使用类别先验知识；2.LDA在样本分类信息依赖均值而不是方差的时候，比PCA之类的算法较优。LDA方法的缺点:1.LDA不适合对非高斯分布样本进行降维，PCA也有这个问题；2.LDA降维最多降到类别数C-1的维数，如果我们降维的维度大于C-1，则不能使用LDA。当然目前有一些LDA的进化版算法可以绕过这个问题；3.LDA在样本分类信息依赖方差而不是均值的时候，降维效果不好；4.LDA可能过度拟合数据。LaplacianEigenmaps2020/4/27西安电子科技大学计算机学院45XiaofeiHe,ShuichengYan,YuxiaoHu,ParthaNiyogi,andHong-JiangZhang.FaceRecognitionUsingLaplacianfaces.IEEETransactionsonPatternAnalysisandMachineIntelligence,27(3):328-340,2005.3342LaplacianEigenmaps2020/4/27西安电子科技大学计算机学院46LaplacianEigenmaps2020/4/27西安电子科技大学计算机学院47算法：LaplacianEigenmaps2020/4/27西安电子科技大学计算机学院48Laplacianfaces2020/4/27西安电子科技大学计算机学院49LaplacianEigenmaps2020/4/27西安电子科技大学计算机学院50提纲2020/4/27西安电子科技大学计算机学院51线性判别函数Fisher线性判别分析感知器(Perceptron)最小平方误差判别线性支持向量机多类线性分类器基本概念:1．线性可分性对一组样本y1,…,yN(增广表示)，假定来自两类，若存在一个权向量a，使得当时，有2iy时，有0iTya则称这组样本是线性可分的。感知器1iy0iTyaywxwxgTT0)(xy1ww0增广样本向量增广权向量例子:线性可分与不可分的情况感知器若样本是线性可分的，则总存在权向量a能把每个样本正确分类，即使得2．样本的规范化1iy0iTya2iy，对，对对第二类的样本，若在yi前加一负号，则。感知器0iTya0iTyiiyy即若令这时问题就化为找一个a，使对所有的，有。上述的处理称为规范化。称为规范化的增广样本。感知器.if,,if,21iiiiiyyyyyiy0iTyiy3.解向量和解区在线性可分的情况下，满足aTyi0，i=1,2,…,N的a称为权向量，记为a*。方程aTyi=0中的a和yi的作用是对偶的。一个权向量a是权空间中的一个点。每个样本yi对a的可能位置都起到限制作用。即要满足aTyi0。对所有样本满足aTyi0的a即为一个解。感知器方程aTyi=0确定了权空间中过原点的一个超平面Hi，它的法向量是yi。解应在Hi的正侧(因为要求aTyi0)正半空间。N个样本确定了权空间中的N个平面，每个平面把权空间分成了三部分，正侧、负侧和平面本身。感知器所以，如果解存在，则必定在N个超平面的正半空间的相交区。这个区域称为解区。区域中的每个向量都是解向量a*。感知器为使所得的a*对新的样本也能正确分类，a*最好位于解区的中央。为提高泛化能力，使解更可靠，引入余量b0，寻找满足aTyi=b,i=1,2,…,N的解区(带余量的解区)。显然，满足aTyi=b0的解区位于原aTyi0的解区之内，且离原解区边界的距离为4．对解区的限制。iyb感知器。二．感知准则函数及其梯度下降算法设有一组样本y1,…,yN（规范的增广样本向量）。目的是求一a*，使得a*Tyi0,i=1,2,…,N。感知器iyb。构造一个准则函数：eYyTpyaaJ)()(Ye：被a所错分的样本集合。即aTy=0的（错分）。此时-aTy=0。∴0)(aJp感知器∴只有当Ye为空集时，不存在错分样本，才有))(min()(*aJaJpp这一准则函数是Rosenblat在五十年代末提出来的，用来模拟人脑神经细胞的模型，所以一般称为感知器准则函数。感知器可以用梯度下降法求使Jp(a)最小的a*。