降维特征提取流形学习方法介绍

特征提取方法介绍报告人：张妍01020304背景介绍Background经典流形学习算法Classicalmanifoldlearningmethods流形学习新方法Newmethodsofmanifoldlearning后续工作展望Follow-upProspectsCONTENT01背景介绍BackgroundPARTONE1.降维降维的动机：原始观察空间中的样本具有极大的信息冗余样本的高维数引发分类器设计的“维数灾难”数据可视化、特征提取、分类与聚类等任务需求1.降维降维的动机：解决办法：选取尽可能多的,可能有用的特征,然后根据需要进行特征/维数约简.特征选择特征约简特征提取依据某一标准选择性质最突出的特征实验数据分析，数据可视化（通常为2维或3维）等也需要维数约简经已有特征的某种变换获取约简特征2.特征提取特征提取的主要任务04特征：一个数字图像中“有趣”的部分•是许多计算机图像分析算法的起点•一个算法是否成功往往由它使用和定义的特征决定•降维•提取具有鉴别性的描述3.特征提取方法分类特征提取方法有监督方法/无监督方法全局方法/局部方法线性方法/非线性方法基于线性/非线性变换3.特征提取方法分类特征提取线性方法非线性方法PCALDAMDS……基于核函数的降维方法流形学习方法kernelPCAGDA……IsomapLLENPE……4.线性特征提取方法线性特征提取方法通过特征的线性组合来降维本质上是把数据投影到低维线性子空间线性方法相对比较简单且容易计算线性特征提取方法的不足原始数据无法表示为特征的简单线性组合•比如：PCA无法表达Helix曲线流形1-DHelix曲线流形-1-0.500.51-1-0.500.51051015204.线性特征提取方法线性特征提取方法的不足真实数据中的有用信息不能由线性特征表示•比如：如何获取并表示多姿态人脸的姿态信息4.线性特征提取方法5.流形学习一类借鉴了拓扑流形概念的降维方法目的：从高维采样数据中恢复低维流形结构，降维，数据可视化流形：局部与欧式空间同胚的空间，在局部具有欧氏空间的性质直观上好比一个d维空间，在一个D(Dd)维空间中被扭曲之后的结果02经典流形学习算法ClassicalmanifoldlearningmethodsPARTTWO经典流形学习算法Isomap等距离映射算法[1]通过改造一种原本适用于欧式空间的算法——多维缩放(MultidimensionalScaling，MDS)，达到将流形映射到一个欧式空间的目的2,min,,ijGijYijdyydxxIsomap目标函数：使得降维之后的点两两之间距离尽量不变测地距离[1]J.B.Tenenbaum,V.deSilva,andJ.C.Langford.“Aglobalgeometricframeworkfornonlineardimensionalityreduction,”Science,vol.290,no.5500,pp.2319-2323,2000.经典流形学习算法Isomap等距离映射算法•将MDS中原始空间中距离的计算从欧氏距离换为了流形上的测地距离。•通过将数据点连接起来构成一个邻接Graph来离散地近似原来的流形，而测地距离也相应地通过Graph上的最短路径来近似经典流形学习算法11LLE(LocallyLinearEmbedding)局部线性嵌入算法[2]2:,jiTiijjjxNNxYiMinyWySubjYYI[2]S.Roweis,andL.K.Saul,“Nonlineardimensionalityreductionbylocallylinearembedding,”Science,vol.290,no.5500,pp.2323-2326,2000.假设：任一数据点均可以利用其近邻点进行线性加权组合重构得到目标：低维空间中保持每个邻域中的重构权值不变保持局部近邻结构最小化重构误差目标函数：经典流形学习算法NPE(NeighborhoodPreservingEmbedding)邻域保持嵌入算法[3]•是LLE的线性化方法•不仅可以映射训练集样本，还可以将新的测试数据映射到低维空间[3]X.He,D.Cai,S.Yan.“Neighborhoodpreservingembedding,”In:ProceedingsoftheIEEEInternationalConferenceonComputerVision,pp.1208-1213,2005.TiiixyAx存在的问题局限于训练样本，如果要得到新增测试样本的低维坐标，必须将新增样本点带入原数据集，重新计算所有点的低维表示。解决：LLE→NPE(邻域保持嵌入)，LE→LPP（局部保持映射）03流形学习新方法NewmethodsofmanifoldlearningPARTTHREEMMD-Isomap模型建立[4]采用成对约束：ML(MustLink)&CL(CannotLink)最小化类内距离，最大化类间距离[4]B.Yang,M.Xiang,Y.Zhang.“Multi-manifoldDiscriminantIsomapforvisualizationandclassification,”PatternRecognition,vol.55,pp.215-230,2016.目标函数：PairwiseconstraintsMust-linkconstraintCannot-linkconstraintSSMM-Isomap模型建立SSMM-Isomap目标函数,22min,1,YPTMLCLFFJYPYPJJYYWPXYMLCL近邻保持项特征近似错误项近邻保持项：保持局部近邻信息特征近似错误项：学习得到线性投影P用以解决样本外数据训练问题SSMM-Isomap聚类可视化实验-3-2-10123-3.5-3-2.5-2-1.5-1-0.500.511.5-2-1.5-1-0.500.51-3-2-101234-8-6-4-20246-6-4-20246-3-2-1012345-5-4-3-2-101234-6-4-202468-4-3-2-1012345-0.5-0.4-0.3-0.2-0.100.10.2-0.4-0.200.20.40.60.811.2-0.24-0.22-0.2-0.18-0.16-0.14-0.12-0.1-0.08-0.06-0.24-0.22-0.2-0.18-0.16-0.14-0.12-0.1-0.08-0.06-2.4-2.3-2.2-2.1-2-1.9-1.8-1.7-1.6x10-12-2.3-2.2-2.1-2-1.9-1.8-1.7-1.6x10-12a.PCAb.LDAc.LapLDAd.SSLDAe.SSMMCf.Isomapg.MMD-Isomaph.SSMM-IsomapFig.1COIL20哥伦比亚目标数据集上的数据可视化结果对比人脸识别实验17AR-male人脸数据集Fig.2AR-male人脸数据集上，每类有标签样本数分别为8（左）、10（中）、12（右）时的分类准确度随所降维度的变化情况36912151821240102030405060708090100ReducedDimensionalityAccuracyPCAIsoPLDASSLDASSMMCLapLDASSMM-Isomap1SSMM-Isomap236912151821240102030405060708090100ReducedDimensionalityAccuracyPCAIsoPLDASSLDASSMMCLapLDASSMM-Isomap1SSMM-Isomap236912151821240102030405060708090100ReducedDimensionalityAccuracyPCAIsoPLDASSLDASSMMCLapLDASSMM-Isomap1SSMM-Isomap2目标识别实验COIL-20哥伦比亚图像数据集Fig.3COIL-20数据集上，每类有标签样本数分别为20（左）、25（中）、30（右）时的分类准确度随所降维度的变化情况23456789556065707580859095100ReducedDimensionalityAccuracyPCAIsoPLDASSLDASSMMCLapLDASSMM-Isomap1SSMM-Isomap223456789556065707580859095100ReducedDimensionalityAccuracyPCAIsoPLDASSLDASSMMCLapLDASSMM-Isomap1SSMM-Isomap22345678950556065707580859095100ReducedDimensionalityAccuracyPCAIsoPLDASSLDASSMMCLapLDASSMM-Isomap1SSMM-Isomap2感谢各位聆听ThanksforListening20