高维数据的涌现是模式识别面临的极大挑战,降维技术已成为处理高维数据,克服“维数灾难”的重要途径。研究表明多数降维方法可归结于图的构造及其嵌入方式。然而,现有许多典型的降维算法均依赖于人工预定义的近邻图,如局部保持投影(LPP)及其变体。虽然这类算法在很多实际问题中取得了良好性能,但存在诸如近邻参数选择、噪声敏感、判别力不足、无法自然地合并领域先验等一系列问题。本文围绕图的构建与优化对降维方法进行了研究,主要贡献有:(1)对全局保持和局部性保持(降维)策略的重新认识与评价。以几种典型的局部保持降维算法为例,通过与全局降维方法的对比,获得了一系列新的洞察(特别是,局部保持策略的不足)。进而,从图的构造角度分析了其深层原因,并给出了具体的改进策略和建议。这一方面,澄清了最近某些方法对局部和全局保持策略的误解,为模型选择提供了依据;另一方面,说明现有局部保持降维方法存在很大提升空间,成为本文研究工作的重要动机之一。(2)首次将稀疏表示引入图的构造,设计了稀疏保持投影(SPP)算法。由于采用全局策略构图,SPP在一定程度上克服了局部保持降维方法中近邻参数选择的困难;而SPP隐含的“近邻”通过l 1优化问题自动获取,很好地弥补了局部构图方法无视数据分布,所有样本使用同一近邻数的缺陷。另外,受益于稀疏表示自然的判别能力,SPP在人脸识别等问题上获得了较LPP等局部保持降维方法更优的性能。(3)提出了稀疏保持判别分析(SPDA)算法,并将其应用于单标号图像人脸识别问题。SPDA不仅是SPP的半监督推广,而且进一步将稀疏表示建图思想统一于贝叶斯学习的框架之下,使得先验知识能够自然地引入图的构造过程。此外,通过集成策略加速稀疏建图,设计了集成稀疏保持判别分析(enSPDA)算法。实验表明所提算法不仅较传统的半监督判别分析方法(如SDA)有效,并且需要更少的无标号样本。(4)提出了软局部保持投影(SLPP)方法。传统的局部保持降维技术中,近邻图起着至关重要的作用,但其构造依赖于人为定义,并独立于后续的降维过程。鉴于此,在LPP的基础上,提出了SLPP算法,将图的构造与投影学习整合于单个目标函数,通过交替优化,不仅使图学习过程简洁、高效、易于处理,并且获得了解析的,具有原则性指导意义的图更新公式。标准数据集上的实验表明了SLPP的有效性。(5)搭建了同时降维与图学习的统一框架。受SLPP的启发,提出了一个降维与图更新的同时学习框架,其思想可以应用于几乎所有基于图的降维技术。进一步,为验证此框架的可行性,基于此扩展了经典的LPP,提出了自助式局部保持投影(SdLPP)算法,并在数据可视化、聚类和分类等问题上验证了其有效性。