《特征提取和选择》PPT课件

Chapter6第6章,Featureextractionandselection(特征提取和选择),特征提取和选择的目的(ThePurposeofFeatureextractionandselection),维数灾难(Curseofdimensionality)计算复杂度(Computationalcomplexity)使分类器具有较好的推广能力(Goodgeneralizationpropertiesoftheclassifier),维数灾难(Curseofdimensionality),在低维空间里很复杂的决策面，在高维空间里可以成为线性的：,维数灾难(Curseofdimensionality),如果增加一些特征，会增加样本到类别均值的距离。,在高维空间里或用更加复杂的决策面可以改进分类性能。,维数灾难(Curseofdimensionality),但在实际中这种性能的提高却是行不通的。如只有n6个样本，维数d2，样本是线性可分的。,维数灾难(Curseofdimensionality),当样本数达到n10。与之对应的分布图如图所示。用二次函数解决。,维数灾难(Curseofdimensionality),当n=30时，其分布情况如图所示。,维数灾难(Curseofdimensionality),在样本数和特征数相比较小时，即运用一个低维数比率n/d时，在训练集合上得到的分类器将会是完全错误的。在设计分类器时需要多少个样本，就是说训练集合的最少样本数是多少？,维数灾难(Curseofdimensionality),在d维空间里基于每个样本的位置提炼出一个规则从而训练分类器，从某种意义上讲，这实际上是神经网络的工作过程。为了得到有效的方法，可以人为地将每个特征值的范围分成m个间隔；在每个md超立方体中估计每个样本的位置。,维数灾难(Curseofdimensionality),由于这种超立方体的个数呈现指数增长，所以对于一个不是很小的d值，必须在一个稀疏空间里找到对应的映射，此时映射的代表意义不是很好。这种现象通常称之为维数灾难。,TheTaskofFeatureextraction,存在大量特征，怎样选择最重要的特征使特征数减少同时尽可能地保证特征的分类判别信息？(Givenanumberoffeature,howcanoneselectthemostimportantofthemsoastoreducetheirnumberandatthesametimeretainasmuchaspossibleoftheirclassdiscriminatoryinformation?),基本概念,特征选择和提取方法的优劣强烈地影响到分类器的设计及其性能，是模式识别中的关键问题之一。特征选择和提取的基本任务是如何从许多原始特征中找出那些最有效、数目最少的特征。一般首先制定特征提取和选择的准则，可以直接以反映类内类间距离的函数作为准则，以误判概率最小为准则，以类别判别函数为准则等。,类别可分离性判据,特征选择与提取的任务是求出一组对分类最有效的特征。因此需要一个定量的准则(或称判据)来衡量特征对分类的有效性。这些判据应能反映各类在特征空间的中的分布情况，刻画各特征分量在分类识别中的重要性或贡献。希望可分性判据满足下列几条要求：,与错误概率有单调关系,与错误概率P(e)(或错误概率的上界及下界)有单调关系。这样使判据取最大值的效果一般说来其错误概率也较小，即测度，P(e),当特征独立时有可加性,即,这里Jij是第i类和第j类的可分性准则函数，Jij愈大，两类的分离程度就愈大，x1，x2，xd是一定类别相应特征的随机变量。,度量特性,判据具有“距离”的某些特性：Jij0，当ij时Jij=0，当i=j时Jij=Jji,单调性,即加入新的特征时，判据不减小。Jij(x1，x2，xd)Jij(x1，x2，xd，xd+1)所构造的可分性判据不一定同时具有上述四个性质。,可分性判据,基于距离的可分性判据基于概率的可分性判据基于熵函数的可分性判据,基于距离的可分性判据(1),各类样本可以分开是因为它们位于特征空间中的不同区域，显然这些区域之间距离越大类别可分性就越大。对于空间中两个点之间的距离度量d(x，y)=|xy|求如何表示两个类区之间的距离。,基于距离的可分性判据(2),对于两类1及2情况，1中任一点与2中的每一点都有一个距离，把所有这些距离相加求平均，可用这个均值来代表这两类之间的距离。假设x是1类中的某个点；Al=al，l=1，2，N2，是2类的点集，d为维数。,（共有Ni个距离）,基于距离的可分性判据(3),其均方距离,对于多类1，2，c情况，令，分别为i类及j类中的d维特征向量，为这两个向量间的距离，,则各类特征向量之间的平均距离为：,基于距离的可分性判据(4),多维空间中两个向量之间有许多距离度量，在欧氏空间有：,用mi表示第i类样本集的均值向量：,用m表示所有各类的样本集总平均向量：,基于距离的可分性判据(5),其中(mi-m)T(mi-m)是第i类的均值向量与总体均值向量m间的平方距离，用先验概率加权平均后可以代表各类均值向量的平均平方距离：,也可以用类内和类间离散度矩阵定义Jd(x)的表达式：,令,基于距离的可分性判据(6),则,上面的推导是建立在有限样本集上的，式中的mi，m，是对类均值、总体均值，类间离散度矩阵Sb，和类内离散度矩阵Sw在样本基础上的估计值，、，Sb，Sw的表达式如下：,基于距离的可分性判据(7),各类之间的平均距离也可表示为：Jd(x)=tr(Sw+Sb),基于概率的可分性判据(1),距离准则是直接从各类样本间的距离算出的，没有考虑各类的概率分布，不能确切表明各类交叠的情况，因此与错误概率没有直接关系。优点是计算方便、直观、概念清楚。对于两类问题，如图6.1，其中(a)为完全可分的情况，(b)为完全不可分的情况。,基于概率的可分性判据(2),假设先验概率相等，若对所有使p(x|2)0的点有p(x|1)=0，如图6.1(a)，则两类完全可分；相反，如果对所有x，都有p(x|1)=p(x|2)，如图6.1(b)所示，则两类完全不可分。,基于概率的可分性判据(3),分布密度的交叠程度可用分布密度函数p(x|1)和p(x|2)之间的距离Jp来度量，任何满足下述条件的函数都可作为类分离性的概率距离量度。Jp为非负，即Jp0。当两类完全不交叠时，Jp取最大值，若对所有x有p(x|2)0时有p(x|1)=0，则Jp=Jpmax。当两类分布密度相同时，Jp应为零，即若p(x|2)=p(x|1)，则Jp=0。,基于概率的可分性判据(4),离散度用来量度两类概率分布的模式之间的不一致性，得到最大离散度可成为使两类样本很好地区别开而选取特征的准则。两类密度函数的似然比或负对数似然比对分类来说是一个重要的度量。设有两类i及j，其对数似然比为：,基于概率的可分性判据(5),它可以提供i对j类的可分性信息，对i类的平均可分性信息为：,同样对j类的平均可分性信息为：,基于概率的可分性判据(6),定义离散度JD为区分i类和j类的总的平均信息，它等于两类平均可分信息之和：,离散度满足类别可分离性判据的条件。,设i、j两类都是d维的正态分布，即：,基于概率的可分性判据(7),对数似然比为：,基于概率的可分性判据(8),对于这两类的平均可分性信息为：,基于概率的可分性判据(9),两类间的离散度为：,上式中利用了迹的性质：trBAT=ATB（A、B是向量）。,基于概率的可分性判据(10),当两类的协方差矩阵相等时，即当i=j=时，,对一维正态分布（d=1）时,特征提取的关键技术(KeytechniquesoftheFeatureextraction),线性变换(LinerTransforms)主成分分析(ThePrincipalComponentsAnalysisorKLtransform)奇异值分解(TheSingularValueDecomposition)离散傅立叶变换(TheDiscreteFourierTransform)离散余弦和正弦变换(TheDiscreteCosineandSineTransforms)小波变换(WaveletTransform),特征提取主成分分析(Featureextraction-PCA),PrincipalComponentsAnalysis,什么是主成分分析(Whatisit?),主成分分析(PCA)是在最小均方误差意义上寻找最能代表原始数据的投影方向，目的是减少数据集的维数。(Principalcomponentanalysis(PCA)isseekingaprojectionthatbestrepresentsthedatainaleast-squaressense.Thepurposeistoreducethedimensionalityofadataset(sample).,Example1,体重和身高是相关的，收缩压和心率也是相关的(Weightandheightareprobablyhighlycorrelated,andsbp(systolicbloodpressure)andheartratemayberelated.)用2个新变量pc1和pc2分别表示体重和身高的组合、收缩压、年龄和心率的组合(Imagine2newvariables,pc1andpc2,wherepc1isacombinationofweightandheightwhilepc2isacombinationofsbp,ageandheartrate.),Example1(cont),因此，在信息损失很少的情况下，变量数从5个减少到2个。(Hence,thenumberofvariablescouldbereducedfrom5to2withlittlelossofinformation.)这些新变量是从原始变量中提取的，称作主成分。(Thesenewvariables,derivedfromtheoriginalvariables,arecalledcomponents.),Example1(cont),这样，主成分分析的目的就是在信息损失最小的前提下，减少特征维数。通过变量间的相互关系，把数据投影到较少的维数空间。(Thus,themainaimofPCAistoreducedimensionalitywithaminimumlossofinformation.Thisisachievedbyprojectingthedataontofewerdimensionsthatarechosentoexploittherelationshipsbetweenthevariables.),Example2,鹫是3维，但其照片是2维的，如图所示。(Thegoldeneagleis3-dimensional,butitsphotographis2-dimensional.),Example3,考虑这些鱼的例子(Considerthesefish.),Example3(cont),用每条鱼的长度和宽度作为鱼的度量。(Wecouldmeasure,foreachfish,itslengthandbreadth.),Example3(cont),设测量50条鱼，如图所示。(Supposethat50fishweremeasured,thefollowingplotmightbeobtained.),Example3(cont),移动坐标轴使坐标原点位于x和y值中心点(Movetheaxessothattheiroriginsarenowcenteredonthecloudofpoints,i.e.0,0isatthemeanofxandthemeanofy.),Example3(cont),在这种情况下，从每一个值中减去相应的均值(Inthiscasetherelevantmeansweresubtractedfromeachvalue.),Example3(cont),将坐标轴沿新坐标原点旋转。旋转实现了特定的目的。(Thenaxeswillberotatedabouttheirneworigin.Thisrotationhasbeencarriedouttofulfillaparticularobjective.),Example3(cont),目的就是确定一个轴，此轴占据数据变化的最大比例。(Theobjectiveistopositiononeaxisinsuchawaythatitaccountsforthelargestproportionofthedatasvariance.),Example3(cont),它可以被看作是数据的投影方向数据从不同角度的投影。(Itmaybethoughtofasadata-projection-literallylookingatthedatafromadifferentangle.),Example3(cont),这个新轴称作什么呢？(Whatmightthisnewaxisbecalled?)考虑一下左下角和右上角的数据点有什么样的关系？这些鱼的外表特征是怎样的？(Thinkabouttherelationshipsbetweenthedatapointatthebottomleftandthedatapointatthetopright,whatwouldthesefishlooklike?),Example3(cont),虽然具有相同的形状，但左下角的鱼小，右上角的鱼大。有效的主轴是个新变量size。(Thebottomleftfishwouldbesmall,whilethetoprightfishislarge,albeitwiththesameshape.Ineffectthemajoraxisisanewvariable,size.),Example3(cont),最简单的形式是(Atitssimplest)size=length+breadth也就是已有变量在相同的权值下的线性组合。(i.e.alinearcombinationofthetwoexistingvariables,whicharegivenequalweighting.),Example3(cont),然而，也可以确定哪一个变量更重要。(However,wecouldmakeoneofthevariablesmoreimportant.)假设确定size时长度比宽度重要(Supposethatweconsiderlengthtobemoreimportantthanbreadthinthedeterminationofsize.),Example3(cont),在这种情况下将使用权值或系数将样本的不同贡献表示出来。(Inthiscasewecouldusedweights,orcoefficientstointroducedifferentialcontributions.)例如(forexample)size=0.75xlength+0.25xbreadth,Example3(cont),假设长度和宽度是归一化的，即具有零均值和1方差，则上式表明长度比宽度重要的程度是3倍。(Forexample,assumethatlengthandbreadthhadbeennormalizedsothateachhasameanof0andavarianceof1wecanconcludethatlengthisthreetimesmoreimportantthanbreadthintheconstructionofthesizevariable(coefficientsof0.75and0.25).),Example3,如果系数都为0.5，则对于size的贡献是等同的。(Ifbothhad0.5coefficientswewouldconcludethattheywereequallyimportantwithrespecttosize.),Example3(cont),假设平均长度是平均宽度的4倍，若使二者对size的贡献是等同的，系数应该分别是0.2和0.8。(Supposethatonaveragelengthvalueswerefourtimesgreaterthanthebreadthvalues;tomakethemequallyimportantintheconstructionofthesizevariabletheywouldneedcoefficientsof0.2(length)and0.8(breadth).),Example3(cont),为了方便，常将x轴作为水平轴这样常常旋转数据点，而不是坐标轴。(Forconveniencewewouldnormallyplotthegraphwiththexaxishorizontal,thiswouldgivetheappearanceofrotatingthepointsratherthantheaxes.),Example3(cont),除了size上述例子中的鱼还有其他的不同吗?(Apartfromsize,howelsedotheabovefishdiffer?)答案是只在形状上有较小的不同。(Theanswerisnotmuch,apartfromsomeminordifferencesinshape.),Example3(cont),如果丢掉次轴的信息，只损失关于形状不同的信息，但这些鱼在形状上很相似，所以只损失了很少的信息。(Ifwediscardthesecondaxiswewouldloseinformationaboutthedifferentshapes,butsincetheyareallverysimilarinshapelittleinformationwouldbelost.),Example3(cont),这样，在上面的例子中，在很少信息损失的前提下，将数据从2维减少到一维。(Thus,intheaboveexamplewecanreducethedatasdimensionalityfromtwo(lengthandbreadth)toone(size),withlittleinformationloss.),PrincipalComponentsAnalysis,ddimensionaldatavectorxRecordnobservationsx1,x2,xn,Mean,Covariance,PrincipalComponentsAnalysis,考虑n个d维的样本x1,xn，如何能够用一个d维向量x0最好地代表这n个样本。(Considertheproblemofrepresentingallofvectorsliesinasetofnddimensionallinearspacesamplesx1，xnbyasinglex0.)定义平方误差准则函数J0(x0)(Definethesquared-errorcriterionfunctionJ0(x0)by),PrincipalComponentsAnalysis,寻找能够使J0(x0)最小化的d维向量J0(x0)。(Seekthevalueofx0thatminimizesJ0.)这个问题的解答就是x0=m.(Itissimpletoshowthatsolutiontothisproblemisgivenbyx0=m.),PrincipalComponentsAnalysis,x0=m,Minimize！,证明如下(Thiscanbeeasilyverifiedbywriting),PrincipalComponentsAnalysis,样本均值是样本数据集的零维表达。它非常简单，但缺点是不能反映出样本之间的不同(Thesamplemeaniszero-dimensionalrepresentationofthedataset.Itissimplebutitdoesnotrevealanyofthevariabilityinthedata.)通过把全部样本向通过样本均值的一条直线做投影，能够得到代表全部样本的一维向量。(Wecanobtainone-dimensionalrepresentationbyprojectingthedataontoalinerunningthroughthesamplemean.),PrincipalComponentsAnalysis,让e表示这条通过样本均值的直线上的单位向量。(Letebeaunitvectorinthedirectionoftheline.)这条直线的方程可以表示为：(Thentheequationofthelinecanbewrittenas)x=m+ae其中a为实数标量，表示直线上的某个点离开点m的距离。(Wherethescalaracorrespondstothedistanceofanypointxfromthemeanm.),PrincipalComponentsAnalysis,如果用m+ake来代表xk，则通过最小化平方误差准则函数，能得到一组最优的ak的集合，其过程如下：(Ifrepresentxkbym+ake,wecanfindan”optimal”setofcoefficientsakbyminimizingthesquared-errorcriterionfunction),PrincipalComponentsAnalysis,由于|e|=1，通过对ak求偏导，并且令结果为0，得到(|e|=1,partiallydifferentiatingwithrespecttoak,andsettingthederivativetozero,weobtain)ak=eT(xkm)几何上，这个结果只需要把向量xk向通过样本均值的直线e作垂直投影就得到了最小方差结果。(Geometrically,thisresultmerelyobtainaleast-squaressolutionbyprojectingthevectorxkontothelineinthedirectionofethatpassesthroughthesamplemean.),PrincipalComponentsAnalysis,如何找到直线e的最优方向。(Howtofindthebestdirectionefortheline?)定义散布矩阵(或称离散度矩阵)DefinethescattermatrixS,是样本协方差矩阵的n-1倍。,PrincipalComponentsAnalysis,Then,PrincipalComponentsAnalysis,使J1最小的那个向量e，能够使eTSe最大。(ThevectoreminimizesJ1alsomaximizeseTSe.)HowdoweoptimizeeTSe?LagrangeMultipliers!,PrincipalComponentsAnalysis,Inparticular,because,为了最大化eTSe，选取散布矩阵最大的本征值对应的本征值对应的那个本征值作为投影直线e的方向。(InordertomaximizeeTSe,selecttheeigenvectorcorrespondingtothelargesteigenvalueofscattermatrix.),PCAAlgorithm,1.Computethemeanofthedata,2.Computethecovarianceofthedata,PCAAlgorithm,3.ComputeeigenvectorsuiandcorrespondingeigenvaluesiofC,sortedaccordingtothemagnitudeofi4.Foradesiredapproximationdimensiond(dd)xcanbewrittenas,Selectingtheapproximationdimensiond?,TheproportionofvarianceinthedatacapturedwhenwetruncateatagivendisProportionofvariancecaptured,Selectingtheapproximationdimensiond?,Twostrategies:1st:Specifythedesiredthresholde.g.99%2nd:Lookatthemagnitudesofi/i+1Insomeproblemsitwillexhibitasharpvalueatsomevalueofi“Intrinsicdimension”oftheproblem,仿真,Matlabexample,Applications,AlmostallcomputervisionandpatternrecognitionEspeciallyfacerecognition,tracking,etc.,Eigenfaces,Developedin1991byM.TurkBasedonPCARelativelysimpleFastRobust,Eigenfaces，thealgorithm,AssumptionsImageswithWH=N2MisthenumberofimagesinthedatabasePisthenumberofpersonsinthedatabase,Eigenfaces，thealgorithm,database,Eigenfaces，thealgorithm,Wecomputetheaverageface,WhereM=8.,Eigenfaces，thealgorithm,Thensubtractitfromthetrainingfaces,Eigenfaces，thealgorithm,NowwebuildthematrixwhichisN2byM,A=abcdefgh,ThecovariancematrixwhichisN2byN2,Cov=AA,Eigenfaces，thealgorithm,FindeigenvaluesofthecovariancematrixThematrixisverylargeThecomputationaleffortisverybigWeareinterestedinatmostMeigenvaluesWecanreducethedimensionofthematrix,Eigenfaces，thealgorithm,ComputeanothermatrixwhichisMbyMFindtheMeigenvaluesandeigenvectorsEigenvectorsofCovandLareequivalentBuildmatrixVfromtheeigenvectorsofLL=AA,Eigenfaces，thealgorithm,EigenvectorsofCovarelinearcombinationofimagespacewiththeeigenvectorsofLEigenvectorsrepresentthevariationinthefacesU=AV,Eigenfaces，thealgorithm,Computeforeachfaceitsprojectionontothefacespace,Computethethreshold,forj=1,2,M,Eigenfaces，thealgorithm,Torecognizeaface,Subtracttheaveragefacefromit,Eigenfaces，thealgorithm,Computeitsprojectionontothefacespace,Computethedistanceinthefacespacebetweenthefaceandallknownfaces,fori=1.M,Eigenfaces，thealgorithm,Reconstructthefacefromeigenfaces,Computethedistancebetweenthefaceanditsreconstruction,Eigenfaces，thealgorithm,Distinguishbetween,Ifthenitsnotaface,Ifandthenitsanewface(i=1,M),Ifandthenitsaknownface,Eigenfaces，thealgorithm,Distinguishbetween,Ifthenitsnotaface,Ifandthenitsanewface(i=1,M),Ifandthenitsaknownface,Eigenfaces，thealgorithm,Distinguishbetween,Ifthenitsnotaface,Ifandthenitsanewface(i=1,M),Ifandthenitsaknownface,Eigenfaces，thealgorithm,Eigenfaces，thealgorithm,Distinguishbetween,Ifthenitsnotaface,Ifandthenitsanew(i=1,M),Ifandthenitsaknownface,Eigenfaces，thealgorithm,Distinguishbetween,Ifthenitsnotaface,Ifandthenitsanew(i=1,M),Ifandthenitsaknownface,Eigenfaces，thealgorithm,ProblemswitheigenfacesDifferentilluminationDifferentheadposeDifferentalignmentDifferentfacialexpression,KernelPrincipalComponentAnalysis,TheKernelPrincipalComponentAnalysis(KernelPCA)isthenon-linearextensionoftheordinarylinearPCA.TheinputtrainingvectorsX=x1,.,xl,xiXRn,aremappedby:XFtoahighdimensionalfeaturespaceF.ThelinearPCAisappliedonthemappeddataT=(x1),.,(xl).,KernelPCA,Thecomputationoftheprincipalcomponentsandtheprojectiononthesecomponentscanbeexpressedintermsofdotproductsthusthekernelfunctionsk:XXRcanbeemployed.ThekernelPCAtrainsthekerneldataprojectionz=ATk(x)+b,KernelPCA,suchthatthereconstructionerror,Thereconstructedvector(x)isgivenasalinearcombinationofthemappeddata,isminimized.,KernelPCA,IncontrasttothelinearPCA,theexplicitprojectionfromthefeaturespaceFtotheinputspaceXusuallydonotexist.TheproblemistofindthevectorxXitsimage(x)Fwellapproximatesthereconstructedvector(x)F.,KernelPCA,Theprocedureconsistsofthefollowingstep:ProjectinputvectorxinRnontoitslowerdimensionalrepresentationzRmusingz=ATk(x)+bComputesvectorxoutRnwhichisgoodpreimageofthereconstructedvector(xin),suchthat,Example:KernelPCA,TheexampleshowsusingthekernelPCAfordatadenoising.Theinputdataaresyntheticallygenerated2-dimensionalvectorswhichlieonacircleandarecorruptedbytheGaussiannoise.ThekernelPCAmodelwithRBFkernelistrained.TheresultisvisualizedinFigure.,Example:KernelPCA,TheexampleshowsusingthekernelPCAfordatadenoising.Theinputdataaresyntheticallygenerated2-dimensionalvectorswhichlieonacircleandarecorruptedbytheGaussiannoise.ThekernelPCAmodelwithRBFkernelistrained.TheresultisvisualizedinFigure.,GreedyKernelPCA,TheGreedyKernelPrincipalAnalysis(GreedykernelPCA)isanefficientalgorithmtocomputetheordinarykernelPCA.LetX=x1,.,xl,xiRnbethesetofinputtrainingvectors.Thegoalistotrainthekerneldataprojectionz=ATkS(x)+b,GreedyKernelPCA,whereAdmistheparametermatrix,bm1istheparametervectorandkS=k(x,s1),.,k(x,sl)TarethekernelfunctionscenteredinthevectorsTS=s1,.,sd.ThevectorsetTSisasubsetoftrainingdataX.,GreedyKernelPCA,IncontrasttotheordinarykernelPCA,thesubsetTSdoesnotcontainallthetrainingvectorsX，thusthecomplexityoftheprojectionz=ATkS(x)+bisreducedcomparedtoz=ATk(x)+b.,GreedyKernelPCA,TheobjectiveoftheGreedykernelPCAistominimizethereconstructionerror,whilethesizedofthesubsetTSiskeptsmall.,Example:Gre