第八章-特征选择与提取

特征选择与特征提取1问题1、为什么要做特征选择和特征提取？2、特征选择和特征提取的区别在哪儿？3、怎么做特征选择和特征提取？2目录•背景•特征选择简介•特征子集搜索与子集评估•特征提取•特征选择与特征提取讨论•总结3背景好瓜还是坏瓜?分类任务西瓜特征分类器(SVM,Beyes,KNN….)好瓜坏瓜原始特征:西瓜{颜色,根蒂,敲声,纹理,触感…}以往研究，是特征固定，研究重点是分类器特征是否适合我们的任务？4背景举例:对于一个有经验的瓜农，怎么判断西瓜是好还是坏？5特征结果颜色：绿色根蒂：蜷缩敲声：清脆纹理：清晰触感：光滑好瓜根蒂：蜷缩敲声：清脆纹理：清晰好瓜颜色：绿色①相比②，部分特征冗余，需要选择特征①②③背景特征:{根蒂，敲声，纹理}好瓜or坏瓜注意：原始特征是已知的6特征:西瓜{颜色,根蒂,敲声,纹理,触感…}除此之外，还有一种处理特征的方式，叫特征提取从原始特征中选择出部分和任务相关的特征，是特征选择•特征选择：从原始特征中选择出和任务相关的特征•特征提取：将原始特征通过线性或者非线性组合的方式转化为新的特征表示Forexample:𝑌=𝑤𝑖𝑥𝑖𝑛𝑖=1作用:降维特征优化提升分类性能7背景目录•背景•特征选择简介•特征子集搜索与子集评估•特征提取•特征选择与特征提取讨论•总结8特征选择特征：对象所具有的属性例如:西瓜{颜色,根蒂,敲声,纹理,触感…}根蒂:蜷缩敲声:清脆纹理:清晰恩，这是一个好瓜9有经验瓜农判断：特征选择相关特征:和任务相关的属性，且属性之间互相不相关比如：{根蒂、敲声、纹理}无关特征:和任务不相关的属性比如：{颜色、触感…}特征选择：从所有的已知属性中选择出和任务相关，且相互之间不相关的属性10好而不同特征选择分类器原始特征集合子集搜索子集评估是否满足停止条件是否11一般来说，特征选择步骤如下，主要包括子集搜索和子集评估目录•背景•特征选择简介•特征子集搜索与子集评估•特征提取•特征选择与特征提取讨论•总结12子集搜索1)前向搜索:依次在候选集合中增加相关特征2)后向搜索:在候选集合中，依次去除不相关特征Question:Howtoevaluatethesearchedfeature?⇒𝑎2⟹𝑎2,𝑎4…..Optimalfeature:Optimalfeature:子集评估13Thesestrategiesaregreedy,onlyconsideroptimizationofthisround这些方法是贪心的策略，因为是在上一轮的基础上考虑本轮最优，所以不一定得到最优特征组合其他子集搜索方法：子集评估类可区分性判据(SeparationCriterion)用于评估特征子集的类别区分性的能力基于距离的类可区分性判据Distancebasedseparationcriterion基于概率分布的类可区分性判据Probabilitydistributionsbasedseparationcriterion基于熵的类可区分性判据Entropybasedseparationcriterion14•搜索一个特征子集，我们希望:样本类内的距离尽可能小样本类间距离尽可能大基于距离的判据15Faraway…Faraway…Class1Class2基于距离的判据1,(1,2)iixDiuxiN()(),(1,2)iTiiixDSxuxui1212()()TbSuuuu样本均值向量:协方差矩阵:类内散度矩阵:类间散度矩阵:类可区分性判据:𝑴𝒂𝒙𝑡𝑟(𝑆𝑏)𝑡𝑟(𝑆𝑤)16注：协方差矩阵的迹等同于方差基于概率密度的判据17Class1Class2类条件概率密度曲线重叠分离xx𝑃𝑥𝜔1𝑃𝑥𝜔2根据搜索到的特征子集，分析一下两个类的类条件概率密度曲线分布情况类条件概率密度Class1Class2𝑃𝑥𝜔1𝑃𝑥𝜔2类条件概率密度基于概率密度的判据𝐽=𝑔[𝑃𝑥𝜔1,𝑃𝑥𝜔2,𝑃1,𝑃2]𝑑𝑥18重叠度J：两个概率密度分布曲线的重叠程度类条件概率先验概率J满足的条件:1)𝐽≥02)If𝑃𝑥𝜔1=0&𝑃𝑥𝜔2≠0,𝑜𝑟𝑃𝑥𝜔2=0&𝑃𝑥𝜔1≠0,J=max3)𝐼𝑓𝑃𝑥𝜔1=𝑃𝑥𝜔2,𝐽=0;19•满足以上条件的任何函数都可以作为基于概率密度的类可区分性判据的距离度量!!!•概率密度距离的常用函数:1)巴氏距离（Bhattacharyyadistance）2)Chernoff界限（Chernoffbound）3)散度（Divergence）参考书:边肇祺《模式识别》第8章基于概率密度的判据22熵（Entropy）:基于熵的判据熵值越大，说明样本的类别不确定性越大2k1()logYkkEntDpp𝑃𝑘=1,𝐸𝑛𝑡=0;𝑃𝑘1,𝐸𝑛𝑡0;样本类别确定：样本类别不确定：23贝叶斯分类器中，分类的结果由后验概率确定对于一个样本，如果所有类的后验概率是相同的，则分类结果不可知例如:𝑖𝑓𝑃𝑤𝑖𝑥=1𝐶,𝐶𝑖𝑠𝑛𝑢𝑚𝑏𝑒𝑟𝑜𝑓𝑐𝑎𝑡𝑒𝑔𝑜𝑟𝑖𝑒𝑠分类错误率:𝑒=1−1𝐶=𝐶−1𝐶𝑖𝑓𝑃𝑤𝑖𝑥=1,𝑃𝑤𝑗𝑥=0,𝑗≠𝑖分类错误率:𝑒=0基于熵的判据熵值可以度量后验概率的分布!24平方熵（SquareEntropy）:基于熵的判据𝐽𝐶2=𝑃𝑤1𝑥,𝑃𝑤2𝑥,…𝑃𝑤𝑐𝑥=2[1−𝑃2(𝑤𝑖|𝑥)𝑐𝑖=1]后验概率分散性越大，熵值越大，分类错误率越高香农熵（ShannonEntropy）:𝐸𝐷=−𝑃(𝑤𝑖|𝑥)log2𝑃(𝑤𝑖|𝑥)𝐶𝑖=1特征选择•过滤式(Filter)•包裹式（Wrapper）•嵌入式（Embedding）特征选择策略:特征子集搜索和子集评估组合起来的过程25特征选择过滤式：特征选择发生在训练过程之前（无训练过程）代表性方法:Relief包裹式：直接将分类器的性能作为特征选择中的子集评估方法（无训练过程）代表性方法:LVW（拉斯维加斯算法）嵌入式：特征选择和学习器训练同时嵌入到一个优化过程中，特征选择在学习器训练过程中完成（有训练过程）211min()mTiiiyxL1norm易获得稀疏解，是一种嵌入式特征选择方法26过滤式过滤式：特征选择发生在训练过程之前Relief(RelevantFeatures)[KiraandRendell,1992]•给定‘相关统计量’，度量特征的重要性•设置一个阈值t,如果某一个特征的相关统计量大于阈值t,那么就将其加入特征子集•特征子集的重要性等于特征子集相关统计量的和27包裹式包裹式：直接将分类器的性能作为特征选择中的子集评估方法LVW(LasVegasWrapper)是一种典型的包裹式算法1）在候选特征集中自由选择特征子集2）在特征子集表示的数据集上，运行学习算法3）用分类的错误率来评估特征子集的好坏30包裹式连续T次不更新，就停止31循环的条件终止条件分类错误率比上一轮减小分类错误率跟上一轮相等，但特征维数减少包裹式•LVW可以减少特征的维数，并且提高分类的准确率•由于每次都要运行分类器，复杂性高•算法运行速度慢32特点：嵌入式嵌入式：特征选择和学习器训练同时嵌入到一个优化过程中，特征选择在学习器训练过程中完成目标函数2221min()mTiiiyxL2norm211min()mTiiiyxL1norm易获得稀疏解，是一种嵌入式特征选择方法L1范数比L2范数更易获得稀疏解33特征选择+特征提取并行的思路嵌入式34总结•背景•特征子集搜索方法前向搜索，后向搜索，双向搜索•特征子集评估方法基于距离的判据，基于概率密度的判据，基于熵的判据•特征选择的策略过滤式，包裹式，嵌入式35目录•背景•特征选择介绍•特征子集搜索与子集评估•特征提取•特征选择与特征提取讨论•总结36特征提取•特征提取不同于特征选择•特征提取是将原始特征通过组合转换到新的特征空间•特征提取是特征工程的一种37特征提取的方法•线性方法•PrincipalComponentAnalysis(PCA)[Pearson,1901]•LinearDiscriminantAnalysis(LDA)[RonaldFisher,1936][Belhumeur,1996]•非线性方法•MultidimensionalScaling(MDS)[Torgerson,W.S.etal.,1958]•Kernelprincipalcomponentanalysis(KPCA)[Scholkopfetal.,1998]•PrincipalCurves[Hastie,1989]•Self-OrganizingFeatureMap(SOM)[Kohonenetal.,1995]•Generativetopographicmap(GTM)[Bishopetal.,1998]•ManifoldLearning：Isomap,LLE,LE…….•......3839PCAPCA:(主成分分析法)PCA𝑧=𝑤1∗𝑥1+𝑤2∗𝑥2x1x2Z是1维的数值W是投影向量x=(x1;x2)是一个向量w未知Question：如何求得最好的W𝑧=𝑤𝑇𝑥线性组合就相当于几何中的投影PCA40𝑠𝑎𝑚𝑝𝑙𝑒𝑥=(𝑥1;𝑥2;𝑥3;….;𝑥𝑛)𝑍=WT𝑥,Z=𝑧1;𝑧2;…;𝑧𝑑,𝑑≪𝑛𝑊=(𝑤1；𝑤2；𝑤3；….；𝑤d)Question:W和Z如何计算呢?Where，Z=𝑧1;𝑧2;…;𝑧𝑑是主成分,zi是个标量wj=(wj1,wj2,….,wjn)是个向量W是d*n的矩阵注：1)每个主成分都是原始特征的线性组合2)主成分的数量小于原始特征维数3)主成分可以保留原始特征的最大信息量4)主成分之间互相不相关41目标函数：max()..TTTWtrWXXWstWWITXXWW目标：最大可分性特征值分解PCA求解：特征值分解𝑊=(𝑤1；𝑤2；𝑤3；….；𝑤d)前d个最大的特征值𝜆对应的特征向量组成W方差最大化拉格朗日乘子法min𝑊−𝑡𝑟𝑊𝑇𝑋𝑋𝑇𝑊+𝜆(𝑊𝑇𝑊−𝐼)𝜆(可理解成向量)对应的是信息量的大小，w对应的是投影方向PCAAlgorithmX•Letbethemeanvector(takingthemeanofallrows)X•AdjusttheoriginaldatabythemeanX=X–•ComputethecovariancematrixXXTofadjustedX•FindtheeigenvectorsandeigenvaluesofXXT•GetamatrixWconsistedofdorderedeigenvectors•𝑍=𝑊T𝑥istheresultthatwanttoget42max()..TTTWtrWXXWstWWITXXWW去中心化中心化PCA以2维的数据集为例：43PCAPCA保证新空间中特征之间不相关的情况下，使变换后的特征维数更少，实现降维和特征提取.(不包含类别区分性)局限：无监督被忽略掉的成分可能也包含一些相对独立的信息44优点:•LDA（线性判别分析）•LDA是Fisher线性判别分析的一般形式，通过特征的线性组合实现两类或者多类数据的分离。LDA在统计、模式识别和机器学习中具有广泛应用线性判别分析4546线性判别分析2维映射到1维2维映射到1维线性判别分析数据集:：第一类数据样本集：第一类数据样本个数：第二类数据样本集：第二类数据样本个数{(,)}1iimDxyi{1,2}iy1D2D47N2