第1章 绪论
1.1 本书研究背景及意义
半个多世纪以来，计算机科学和信息技术的发展，给人类社会的生产、生活带来了巨大的变化。人们在现实生活中常常会接触到各种各样的数据，如互联网的网页、数字电影的帧图像、数码相机拍摄的数字图像、监控录像的视频、电话和唱片的录音、汽车导航的数字地图、数字天气预报的气象数据和股票市场的行情分析数据等。随着航空航天技术的发展，人类接触到范围更加广阔的数据，如来自局部地区、全球甚至外太空的数据。这些数据极大地提高了人们的生活质量，同时也给人类认知世界提供了科学依据，在国民经济和国防建设中发挥了重要的作用。
随着数据采集技术、数据存储技术和数据管理技术的日趋成熟，人类获取和收集数据的能力得到了极大的提升。在众多领域，诸如经济、工程、生物、遥感、多媒体和航空航天，人们收集到越来越庞大的数据，如果缺乏有效的分析和处理手段，就无法挖掘出数据中隐含的知识和规则，无法对未来的发展趋势做出准确预测，导致人类无法理解和利用如此丰富的数据资源，造成极大的浪费。人类自身无法从直观上分析和纷繁复杂的、海量数据中蕴含的客观规律，必须借助智能分析手段。
随着信息技术的进步，无论是科学领域还是社会生活的其他方面收集到的数据都正朝着精确化和高维化的方向发展，例如机器人视觉、互联网信息检索、视频检索、三维模型分类与检索、基因微阵列数据分析和基于生物特征的身份识别等应用中，数据都呈现出维数高的特点。在一个典型的图像分类问题中，假设图像尺寸是256×256，将图像像素值行或列排列成向量，那么向量的维数高达65536维。高维数据虽然能提供更为丰富和详细的信息，理论上可以帮助人类更加准确地认知世界，但是也给智能分析方法带来巨大困难。一方面，高维数据导致挖掘算法的计算量迅速上升；另一方面，维数的大幅度提升引发所谓维数危机[2]（Curse of Dimensionality），导致挖掘算法无法揭示数据中蕴含的知识。
现实世界中人们所获取的原始数据往往都是高维的，这些高维数据通常由潜在的多变量控制，例如人脸图像本质上可以由几个连续的变量如姿态、光照、表情来表示，难以直接被人理解、分析和处理。为了解决这一问题，首先要将数据映射到低维空间，然后对低维特征进行分析和处理，这种将高维数据映射到低维空间的过程称为数据降维（Dimensionality Reduction）。有效的数据降维技术能够从原始数据中挖掘出蕴含的内在结构和潜在的控制变量参数，不但可以消除数据间的冗余，简化数据，提高计算效率，而且能够去除噪声，改善数据质量，提高后续处理的效果。因此，数据降维已经成为机器学习和数据挖掘的重要课题，在很多应用中发挥重要作用。
数据降维有两种主要途径[3]：特征选择（Feature Selection）和特征提取（Feature Extraction）。特征选择是指在高维特征中选择具有代表性的特征，所选择的低维特征通常具有一定的物理意义。例如，蔬菜的特征包括品种、产地、价格、颜色、生产日期、运输成本、储存成本、营养成分等，人们在买菜时往往只关注品种、价格、生产日期和营养成分，该过程可以抽象成典型的特征选择过程。特征提取是指通过某种变换得到高维特征的更有意义的低维投影。通常情况下，在低维特征维数一致时特征提取比特征选择在后续分析中的效果好。本书讨论的数据降维算法属于特征提取，即通过学习得到低维空间的基，然后把高维数据投影到低维空间。
经过多年的努力，研究人员已经提出大量有效的数据降维算法。这些算法按照是否考虑样本标签信息，可分为无监督降维（Unsupervised Dimension Reduction）算法和有监督降维（Supervised Dimension Reduction）算法；按照所处理的数据分布性质不同，可分为线性降维（Linear Dimension Reduction）算法和非线性降维（Nonlinear Dimension Reduction）算法。线性降维算法假设数据采样自全局线性的高维空间，即各控制变量参数之间独立无关，典型的算法包括主成分分析[4]（Principal Component Analysis，PCA）、线性判别分析[5]（Fisher's Linear Discriminant Analysis，FLDA）和独立成分分析[6]（Indepent Component Analysis，ICA）。PCA通过保留数据分布方差较大的若干主分量达到降维的目的，在数据服从高斯分布的情况下，利用了数据的二阶统计信息；FLDA属于监督降维算法，它在数据服从同方差高斯分布的前提下，寻找Fisher判别信息最优的向量，使样本的类间散度最大而类内散度最小；ICA将线性混合的信号分解成若干相互独立的分量，与PCA不同，ICA可用于非高斯分布数据。这些线性降维算法可通过核方法[7]推广成非线性降维算法，如核主成分分析[8]（Kernel PCA，KPCA）、核独立成分分析[9]（Kernel ICA，KICA）和核Fisher判别分析[10]（Kernel Fisher Discriminant Analysis，KFDA），即把数据从原始非线性空间映射到更高维甚至无限维的特征空间，然后用线性方法对新的高维空间中的数据进行降维，这类方法的困难在于选择核函数的过程复杂。
非线性降维算法考虑数据中隐含的控制变量参数强相关的情况，目前流行的有基于流形的方法。基于流形的降维算法揭示数据中内在的非线性结构，寻找高维数据在低维空间的紧致嵌入。高维数据采样由少数几个隐含变量控制，基于流形的降维算法的思想非常直接。而且，心理学家认为人的认知过程是基于流形的和拓扑连续性的[11]，因此基于流形的降维思想与这一认知相一致。这些事实促使人们深入研究基于流形的降维算法，已经取得了大量研究成果，包括局部线性嵌入[12]（Local Linear Embedding，LLE）、ISOMAP[13]、线性嵌入[14]（Laplacian Eigenmaps，LE）、局部线性坐标变换[15]（Locally Linear Coordination，LLC）、海森局部线性嵌入[16]（Hessian LLE，HLLE）、最大方差展开[17]（Maximum Variance Unfolding，MVU）、局部切空间比对[18]（Local Tangent Space Alignment，LTSA）和大相关分析[19]（Large Correlation Analysis，LCA）。为了解决“Out-of-Sample”问题，得到显式的投影函数，提出了若干线性化的算法，如近邻保持嵌入（Neighborhood Preserving Embedding，NPE）[20]、正交近邻保持投影（Orthogonal Neighborhood Preserving Projection，ONPP）[21]、局部保持投影（Locally Preserving Projection，LPP）[21]、线性化局部切空间比对（Linearized Local Tangent Space Alignment，LLTSA）[22]和线性化大相关分析（Linearized Large Correlation Analysis，LLCA）[18]。为了利用样本标签信息，开发出了基于流形的监督降维算法，如边际Fisher分析（Marginal Fisher Analysis，MFA）[23]和判别局部配准（Discriminantive Locality Alignment，DLA）[24]。为了分析非线性降维算法的本质差异和相同点，提出了若干理论框架模型，最具代表性的包括图嵌入模型（Graph Embedding，GE）[25]和块配准模型（Patch Alignment，PA）[1]。这些工作取得非常重要的成果，在若干领域得到广泛的应用。
表1.1 数据降维算法分类
数据降维算法在手写体识别[26]、图像超分辨分析[27,28]、步态分析[29]、医学图像分割[30]等领域有着广泛的应用。然而，传统的数据降维算法只考虑了数据的分布性质，忽略了数据的符号性质。事实上，现实世界的大部分数据是非负的。例如，在图像处理和计算机视觉中，像素值是非负数据；彩色图像相当于三维的非负数据；视频相当于四维的非负数据，其中第四维是时间；网页、博客、微博的点击量、相互的链接次数是非负数据；在证券市场，股票、基金、期权、债券的交易量和交易员之间的交易次数等都是非负数据。而且在很多时候，只有非负的数据才有物理意义。例如，在股票分析应用中，由于概率分布是非负的，在降维过程中利用数据非负性质引入概率的概念，可为决策提供依据。因此，实际应用迫切需要对非负数据降维算法进行研究。表1.1列出传统数据降维算法和非负数据降维算法的分类情况，可见非负数据降维算法的研究刚刚起步，尚不成熟。
非负矩阵分解[31]是典型的非负数据降维算法，它把非负数据投影到由非负基向量张成的低维空间，且数据在低维空间的坐标是非负的。相对于传统降维算法，非负数据降维算法有两大优势：第一，由于低维空间坐标是非负的，数据被表示为基向量的加性叠加，所以基向量的能量分布相对集中，得到基于局部的数据表示，可以有效地抑制数据中的噪声；第二，由于基向量的能量相对集中，样本往往只需要少数几个维度的基即可表示，所以低维空间坐标中含有大量的零元素，得到天然的稀疏表示。例如，人脸图像的非负矩阵分解产生的基向量对应人脸的部分特征，即“额”“眉”“眼”“鼻”“口”等，意味着人脸图像采集时由这些部分控制，构成“姿态”“光照”“遮挡”“表情”等控制因素的补充，而这些因素恰好可由传统的基于流形的线性降维算法表征[12,13]。因此，非负数据降维算法结合数据的分布性质和数据的非负性质，可能挖掘数据中蕴含的内在结构。目前已经开发出多种非负数据降维算法，如LNMF[32]、DNMF[33]和GNMF[34]等。然而，现有的非负数据降维算法都是研究人员根据具体任务和自身经验而设计的，缺乏统一的理论框架，难以认清问题的本质，而且有些非负数据降维算法得到的解受误差影响很大，给实际应用带来困难。因此，本书的目的就是深入研究和比较现有非负数据降维算法，提出统一的理论框架模型，用以分析现有非负数据降维算法之间的本质差异、设计新的非负数据降维算法，力求开发出稳健、高效的非负数据降维算法框架和新方法。
非负数据降维研究具有重要的应用价值和广阔的应用前景，本书提出的算法框架不是针对具体任务而设计的，因此对不同的非负数据降维问题具有统一的理论框架。除了所要讨论的非负数据降维问题，本书研究的方法可以很容易地推广到基于核方法的非线性非负数据降维问题。除了所要进行的人脸识别、文本挖掘、图像标注等应用，本书所介绍的算法框架还可以帮助设计适用于其他特定应用的非负数据降维算法的数学模型，如视频监控、医学图像分析、光谱数据分析、地质数据分析等。同时，本书研究的方法也可为其他信息处理领域的研究和发展提供借鉴，如地理信息系统、遥感图像处理等。