《子空间降维算法研究与应用》

内容简介

　　《子空间降维算法研究与应用》结合作者近几年的相关研究工作,全面系统地介绍子空间降维的概念?主要原理?经典方法和国内外有关研究的最新成果?第1~2章介绍子空间降维的基本内容包括发展概述与基本方法;第3~6章介绍作者关于子空间降维的最新研究成果;第7章引入一些秩极小化方法?《子空间降维算法研究与应用》选取一些经典方法进行介绍,并结合作者的研究成果加以论述,较好地反映了该研究领域的全貌,并具有一定的关联性与层次性,便于初学者学习和使用?

目录

精彩书摘

　　第1章绪论
　　随着数据存取技术的快速发展，数据库中积累了大量数据，面临着如何从海量数据中提取有用知识的问题，数据挖掘[1，2]的出现，为人们提供了一条解决"数据丰富而知识贫乏"的有效途径数据挖掘的定义有含义相同描述不同的多个版本，比较多的一种定义是"在海量数据中识别出有效的新颖的潜在有用的最终可理解的模式的非平凡过程"从定义中可以看出，数据挖掘是数据库技术和机器学习的交叉，利用数据库技术对数据进行存储和管理，利用机器学习技术对数据进行分析数据挖掘技术已经在多学科中得到广泛的应用，特别是在计算机视觉和生物信息等学科已经成为最流行的技术
　　数据挖掘最初被认为是数据库中知识发现(KnowledgeDiscoveryinDatabases，KDD)的一个阶段[3]后来，数据挖掘被看成KDD的同义词数据挖掘是一门多学科交叉的学科，用到了人工智能机器学习数据库统计学等领域的技术和方法，吸引了许多计算机工作者[4-23]投入这方面的研究中
　　数据挖掘中面临的一个重要的问题是如何处理海量高维非线性的数据高维数据的大量涌现，对数据挖掘和机器学习提出了挑战，高维数据不但会提高存储和计算代价，而且会导致维数灾难[24]也就是说，随着维数的增加，为了保持分类器的性能，样本的数量需呈指数增加维数灾难现象的几何现象是空空间现象，即高维空间本质上是稀疏空间当样本的数量远小于样本的维数时，将导致小样本问题高维数据的另一个困难是难以被人理解，行之有效的方法就是空间降维数据降维不但是解决高维数据分析的有效手段，也是高维数据可视化的重要途径因此，对数据进行降维成为机器学习和数据挖掘的重要研究课题
　　降维包括特征选择和特征提取两种途径特征选择是指在所有特征中选择最具代表性一些特征，得到原有特征的一个真子集特征提取是指通过对原始特征进行线性组合，得到更有意义的低维投影在《子空间降维算法研究与应用》中所讨论的算法都基于特征提取方法，通过变换将数据从高维空间变换到低维特征空间
　　根据不同的分类标准，子空间降维算法可有不同分类
　　(1)根据所处理数据的分布，降维算法可分为线性和非线性典型的线性算法有主成分分析(PrincipalComponentAnalysis，PCA)[25]线性判别分析(LinearDiscriminantAnalysis，LDA)[26]等非线性算法有等距映射(IsometricFeatureMapping，ISOMAP)[27]和拉普拉斯特征映射(LaplacianEigenmaps，LE)[28]等
　　(2)根据是否利用标签信息，降维算法可分为有监督算法和无监督算法两类
　　PCA[25]局部保持映射(LocalPreservingProjections，LPP)[29]和局部线性嵌入(LocallyLinearEmbedding，LLE)[30]等是无监督降维学习算法LDA[26]和最大间隔准则(MaximumMarginCriterion，MMC)[31]等是有监督降维学习算法无监督降维学习算法的目标是使数据在降维后信息损失最小，而有监督降维学习算法的目标是最大化各类别之间的鉴别信息
　　(3)根据算法是否计算每个数据点与所有其他数据点的关系，降维算法可分为局部和全局降维算法近邻保持嵌入(NeighborhoodPreservingEmbedding，NPE)[32]和LPP[29]等均为局部降维算法PCA[25]和LDA[26]等为全局降维算法尽管将子空间学习算法按照上述方式进行了分类，但是，它们又是相互融合互相交叉的，如LDA是一种有监督全局线性算法子空间方法(subspacemethod)的基本思想是把高维空间数据，通过线性或非线性变换到低维的子空间中，使数据在低维空间中更利于分类，降低计算复杂度在线性降维算法中，最著名的算法有PCA[25]LDA[26]典型相关分析(CanonicalCorrelationAnalysis，CCA)[33]多维尺度分析(MultidimensionalScaling，MDS)[34]非负矩阵分解(Non-negativeMatrixFactorization，NMF)[35]等PCA是无监督学习算法，算法的原理是寻找一组最佳的正交基向量，使重构误差达到最小LDA是有监督学习算法，算法的原理是寻找一个投影方向使得沿着该方向同类样本之间的离散度最小，而异类样本之间的离散度最大在分类问题上，LDA比PCA更具优势，但是LDA要求样本为高斯分布CCA是一种无监督方法，算法的目标是求得一对基向量，使得两数据集之间的相关最大，它只关注成对样之间的相关性，并将相关作为不同空间中样本之间的相关性度量MDS的基本思想是寻找高维数据的低维表示，忠实地保持输入模式内积的低维描述，也就是降维后低维空间中任意两点之间的距离应该与原高维空间中的距离尽量接近NMF的基本思想是在非负性约束下，对非负矩阵进行非负分解，采用简单有效的乘性迭代算法，通过学习得到基向量中含有关于物体的局部特征信息NMF反映局部和整体之间的关系，整体是局部的非负线性组合，局部特征在构成整体时不会出现正负抵消的情况
　　线性降维算法只能发现数据中的全局线性结构，无法揭示数据内在的非线性结构为了解决这一问题，研究人员提出了许多非线性降维算法具有代表性的有两类，分别是核方法和流形学习方法核方法的基本思想是首先将数据从原始的非线性空间映射到一个更高维甚至是无限维的特征空间，然后再利用传统的线性方法在该特征空间中对数据进行处理利用核技巧，大多数传统线性降维方法都可以推广到非线性的情况，典型的有核主成分分析(KernelPrincipleComponentAnalysis，KPCA)[36]核Fisher判别分析(KernelFisherDiscriminantAnalysis，KFDA)[37]和核典型相关分析(KernelCanonicalCorrelationAnalysis，KCCA)[38]等核方法的一个缺点就是如何选择合适的核函数和核函数中的参数，核函数和参数的变化会隐式地改变从输入空间到特征空间的映射，进而影响分类效果，影响核方法的性能;另一个缺点是核方法往往依赖于某种隐式映射，不易直观地理解其降维机理[39]
　　另一类非线性的降维方法是基于流形学习的方法，流形是描述许多自然现象的一种空间形式，是欧氏空间在大尺度分析情况下的推广，而欧氏空间是它的特例流形在局部上与欧氏空间存在着同胚映射，因此，从局部上看，流形与欧氏空间几乎一样2000年Science上发表的ISOMAP[27]LLE[30]和感知的流形假说[30]，被认为是流形学习的研究热潮开始的标志，以后又相继发现许多流形学习算法，包括LE[28]局部切空间排列(LocalTangentSpaceAlignment，LTSA)[40]最大方差展开(MaximumVarianceUnfolding，MVU)[41]黑塞局部线性嵌入(HessianLocallyLinearEmbedding，HLLE)[42]和局部坐标排列(LocalCoordinatesAlignment，LCA)[43]等流形学习的一个缺点导致"外样本"问题[44]，对于新的样本，算法无法直接得到它在低维空间中对应的坐标针对这个问题，多个线性化版本被提出，如基于LLE的ONPP(OrthogonalNeighborhoodPreservingProjection)[45]NPE[32]，基于LE的LPP[29]和基于LTSA的线性局部切空间排列(LinearLocalTangentSpaceAlignment，LLTSA)等流形学习的另一个缺点是由于算法是基于样本的局部结构的，都涉及邻域选择问题
　　经典的流形学习算法是无监督的学习算法，不适用于分类问题在流形学习算法中引入标签信息，许多学者提出了一些针对分类目的的监督流形学习算法监督流形学习算法也包括非线性算法和线性算法前者只定义在训练集上，可以做数据分析的工具;后者能够提供显式的线性映射，可用于模式识别中的特征提取引入监别信息的非线性算法有Supervised-LLE[46]LFE(LocalFisherAnalysis)[47]1-DA(localDiscriminantAnalysis)[48]线性有监督流形学习算法的典型算法有LDE(LocalDiscriminantEmbedding)[45]和MFA(MarginalFisherAnalysis)[49]MFA与LDE并无本质上的差异在LDE和MFA中，目标函数定义的形式不同，但它们可以转化为同样形式的广义特征值问题以后又相继出现半监督判别分析(Semi-SupervisedDiscriminantAnalysis，SDA)[50]正交局部保持投影(OrthogonalLocalityPreservingProjections，OLPP)[45]判别局部线性嵌入(DiscriminantLocallyLinearEmbedding，DLLE)[51]等这些方法同时利用了样本的局部几何结构和数据的判别信息，因而具有很好的判别性能
　　上面所提出的大多数算法或者是监督学习算法，或者是无监督学习算法，对于分类问题，通常有监督算法能够取得较好的效果然而实际问题中通常只能取得少量的有标签的数据和大量未知标签的数据，如果对大量数据进行标记，可能要花费大量的人力和物力一种可行的办法是同时利用少量的有标签数据和大量半监督学习是基于流形假设和聚类假设的:
　　①流形假设，数据分布在高维欧氏空间中的低维流形上;②聚类假设，即距离相近的数据很可能具有同样的标签基本思想是利用无标签的数据提供数据集的几何信息，同时利用有标签的数据指导分类
　　模式是模式识别的基本操作对象，传统子空间学习方法总是将模式转换成对应的向量来处理[56]，但向量化表示并非总是有效的前面所介绍的PCALDALPP等经典的子空间学习算法都是向量表示方法，将高维向量空间数据降维到低维向量空间对于人脸识别和其他图像识别问题，数据的内在表示模式是矩阵或张量，模式向量化会产生如下问题:一方面，向量化模式使得模式的结构遭到破坏[57，58];另一方面，模式在向量化后将成高维数据，导致高的计算复杂度和存储代价，产生维数灾难[59]和小样本问题作为向量模式表示的扩展和补充，研究人员提出了各种基于矩阵或张量模式的学习算法，并在模式识别数据挖掘机器学习计算机视觉等领域引起了广泛关注[60]向量表示线性降维算法大多数已被推广到矩阵或张量模式，典型的有二维主成分分析(Two-DimensionalPrincipalComponentAnalysis，2DPCA)[61]和二维线性判别分析(Two-DimensionalLinearDiscriminantAnalysis，2DLDA)[62]以后又相继提出基于PCA的多线性主成分分析(MultilinearPrincipalComponentAnalysis，MPCA)[63-65]LDA的高阶张量推广算法(DiscriminantAnalysiswithTensorRepresentation，DATER)[66，67]和广义张量判别分析(GeneralTensorDiscriminantAnalysis，GTDA)[68]最近，Yan等[49]提出了降维技术的统一框架，将降维算法归结为图构造及其嵌入方式
　　子空间学习算法通常根据一定的性能指标来寻找线性或非线性空间变换，把原始数据压缩到一个低维空间但是这些方法在矩阵进行分解的时候没有对分解的对象和分解结果进行非负
　　……