第7卷第5期 智能系统学报 Vol.76.5 2012年10月 CAAI Transactions on Intelligent Systems 0ct.2012 D0I:10.3969/i.issn.16734785.201204028 网络出版t地址：htp://www.cnki.net/kcma/detail/23.1538.TP.20120917.1702.002.html 增量与演化流形学习综述 谈超，关佶红，周水庚23 (1.同济大学计算机科学与技术系，上海201804；2.复旦大学计算机学院，上海200433；3.复旦大学上海市智能信 息处理重点实验室，上海200433) 摘要：流形学习的目标是发现观测数据嵌入在高维数据空间中的低维光滑流形.近年来，在线或增量地发现内在 低维流形结构成为流形学习的研究热点.从增量学习和演化学习2个方面入手，对该领域已有研究进展进行综述 增量流形学习较之传统的批量流形学习方法具有动态增量的能力，而演化流形学习能够在线地发现海量动态数据 的内在规律，有利于进行维数约简和数据分析.文中对主要的增量与演化流形学习算法的基本原理、特点进行了阐 述，分析了各自的优点与不足，指出了该领域的开放问题，并对进一步的研究方向进行了展望. 关键词：流形学习；增量流形学习；演化流形学习 中图分类号：TP181文献标志码：A文章编号：16734785(2012)050377-12 Incremental and evolutionary manifold learning:a survey TAN Chao',GUAN Jihong',ZHOU Shuigeng2 (1.Department of Computer Science and Technology,Tongji University,Shanghai 201804,China;2.School of Computer Science,Fudan Universi- ty,Shanghai 200433,China;3.Shanghai Key Laboratory of Intelligent Information Processing,Fudan University,Shanghai 200433,China) Abstract:Manifold learning is to find the low-dimensional smooth manifold of observation data embedded in high- dimensional data space.In recent years,exploring the intrinsic low-dimensional manifold structure online or incre- mentally becomes a hot research topic in manifold learning area.This paper surveys the state of the art of incremen- tal and evolutionary manifold learning,including the mechanisms and features of major existing incremental and ev- olutionary manifold learning methods,their advantages and disadvantages,and highlights the open research issues and future research directions. Keywords:manifold learning;incremental manifold learning;evolutionary manifold learning. 流形学习是近10余年来发展起来的一种非线 展开观测空间中卷曲的流形或发现内在的主要变 性维数约简方法，旨在发现嵌入在高维非线性数据 量，可以对数据集进行降维2].流形学习的意义在 空间的低维光滑流形的内在几何结构或内在维数， 于把人的认知流形规律引入到机器学习研究之 便于对数据的深层理解和进一步处理.近年来，流形 中3].当采样数据处于高维流形空间时，要从采样 学习在许多研究领域，包括数据挖掘、机器学习、图 数据中学习并发现低维流形的内在几何结构，这意 像处理和计算机视觉等都引起了广泛的关注.基于 味着流形学习比传统的维数约减方法更能体现出事 流形学习的非线性维数约减方法成为了机器学习中 物的本质规律， 的研究热点.流形学习的基本前提是：观测空间 近10余年来出现了一些知名的线性与非线性 中的点在高维观测空间张成一个流形，通过有效地 的数据降维算法，如主成分分析(principle compo- nent analysis,PCA)[4]、等距映射(isometric map- 收稿日期：2012-0502.，网络出版日期：201209-17 基金项目：国家自然科学基金资助项目(61173118) ping,Isomap)S、拉普拉斯特征映射(Laplacian 通信作者：关佶红.E-mail:jhguan(@tongji.cdu.cn. eigenmap,LE)、局部线性嵌入(local linear em-
·378 智能系统学报 第7卷 bedding,LLE)[]等.尽管这些算法的提出大大推动 流形学习的数学定义：设YCR,f:Y→RM是 了流形学习的发展，但它们都不具有动态增量处理 一个光滑嵌套，M>d,流形学习的目标是基于R 数据的能力，难以满足计算效率的实际需求 上的一个给定被观测数据集合{x:}恢复Y与f,在Y 为了从高维数据流和大规模海量数据集中探索 中隐藏的数据{y:}被映射到观测空间R“,使得：= 有价值的信息，人们迫切需要增量地发现内在低维 f(y:)1 流形结构.许多实际应用如数据流挖掘、视频监控和 1.2传统流形学习算法 语音识别都要求高维数据的实时嵌入.一个简单的 近年来，流形学习领域出现了很多研究成果，在 做法是：每当一个新数据点进来时，在所有已存在数 包括数据挖掘、机器学习、图像处理]和计算机视 据点上运行数据嵌人算法.考虑到大多数数据嵌入 觉等领域得到了广泛应用[2-5].流形学习中的很多 算法具有至少需要O(n2)的时间复杂度(n是数据 典型算法都是针对线性和非线性降维来进行的.主 点的数量)，因此其时间复杂度过高，运算量过大 成分分析算法(PCA)是线性降维方法中的代表；非 增量学习方法就是为了解决上述问题而提出的.实 线性方法中，发表在2000年《Science》上的等距映 施增量流形学习主要考虑以下2个方面的问题：1) 射算法(Isomap)[S]和局部线性嵌入算法(LLE)[是 如何保证在线状态下实时动态地处理增量数据；2) 2个著名的流形学习降维算法.Isomap算法使用最 如何有效地处理大规模海量数据的嵌入「8]，当前， 近邻图中的最短路径得到近似的测地线距离，代替 增量地处理新加入样本是流形学习和动态数据流分 不能表示内在流形结构的欧氏距离，然后用多尺度 析的研究热点 分析i6(multidimensional scaling analysis,MDS)进 行处理，得到嵌入在高维空间中的低维坐标.LLE能 流形学习的主要目的是对高维数据集的观察或 实现高维输入数据映射到一个全局低维坐标系中， 测量值建立预测模型，当有新的输入值时，这些预测 同时保留了邻接点之间的关系和固有的非线性结 模型就可以预测出相对的输出值.多数流形学习算 构.另外还有拉普拉斯特征映射算法(LE)、局部切 法都是通过优化某个代价函数来求得输出坐标，而 空间排列算法(local tangent space alignment,.LT 演化学习是基于模仿生物演化行为而发展的最优化 SA)]等一系列著名的流形学习算法，在非线性降 方法，可以适用于许多最优化问题；因此可以用于解 维方面均取得了显著的效果 决许多困难的机器学习问题，比如用在流形学习中 目前，流形学习中的非线性维数约减算法大部 的演化流形学习，为发现高维观察值的低维流形提 分都是应用于数据可视化，并已在人脸图像处理、手 供了新的途径 写数字图像及语言处理等方面取得了良好的效果。 本文立足于流形学习，对增量流形学习和演化 1.3传统流形学习算法分类 流形学习的最新进展进行综述.首先，对流形学习的 按原始观察空间与经过仿射变换后的嵌人空间 研究背景和现状进行简要介绍，在此基础上，对增量 保持邻域结构的不同方式，传统流形学习算法可划 流形学习算法进行分类，并对增量流形学习的主要 分为全局嵌入法和局部嵌入法， 算法进行综合对比与分析.然后介绍了流形学习的 1)全局嵌入法.如等距离映射算法(Isomap), 另外一个方向：演化流形学习，概括了该领域的主要 将流形上邻近的点映射到低维空间中的邻近点，同 算法，包括非监督演化学习及监督演化学习.最后讨 时将流形上距离远的点映射到低维空间中距离远的 论了增量流形学习及演化流形学习可扩展和待解决 点，从而保持低维空间中点之间的距离关系及流形 的问题，以及进一步的研究方向 的结构 1流形学习：概念与方法 2)局部嵌人法.如局部线性嵌入算法(LLE)、拉 普拉斯特征映射算法(LE)、局部切空间排列算法 1.1流形学习的基本概念 (LTSA)等，这些方法将流形上距离近的点映射到低 流形学习的主要目标是发现嵌入在高维数据空 维空间中的邻近点，得到局部空间的低维坐标，再通 间中观测数据的低维光滑流形.流形学习对维数约 过线性嵌入、拉普拉斯映射及切空间排列调准等方 减的过程可概括为：设数据是均匀采样于一个高维 法得到全局的低维坐标，从而实现流形学习降维， 欧氏空间中，流形学习就是找到高维空间中的低维 1.4传统流形学习算法的不足 流形，并求出相应的嵌入映射，以实现维数约减9]， 传统流形学习方法在寻找规模不断增加的数据
第5期 谈超，等：增量与演化流形学习综述 ·379· 集的内在规律时，新数据集到来后不是利用已经获 表1主要的增量流形学习算法 得的低维流形结构，而是把新数据集和已有数据集 Table 1 Major incremental manifold learning algorithms 合并成更大规模的数据集，通过重新学习来发现整 分类 核心思想 主要算法 个数据集的低维流形8].这些方法的共同特点是以 从已经存在或是一个 样本 IDR、谱嵌入增量流形 批量或者离线的方式处理数据，不具有增量学习的 新的种类中计算新样 独立 学习算法、增量PCA算 能力.因此，传统流形学习算法不适用于增量学习. 本的低维嵌入，是子空 训练 法、增量【somap算法 间方法的增量版本。 2增量流形学习 保持数据集内部的局IAM、增量LE算法、基 样本 增量流形学习是针对传统批量流形学习算法的 部邻接信息，通过已存 于正交迭代的增量山E 依赖 不足而发展起来的一种新兴流形学习算法，它在动 在样本的邻接信息取算法、增量Laplacian映 训练 态数据处理过程中新数据加入后，构建与原来数据 得低维的嵌入. 射算法、增量LISA算法 集之间的邻域关系，重新表达加入新数据点后的高 2.2针对数据流的增量Isomap算法 维数据集的嵌入空间，从而揭示高维空间中数据点 考虑数据流的特点，Law等提出了增量式的 之间的本质关系 Isomap算法1,3]，增量式学习不仅能够更有效地计 增量流形算法的一个优点是可以将数据流形的 算，同时能够发现流形结构演化的过程， 演化进行可视化.当获得越来越多数据点时，流形变 2.2.1增量ls0map算法 化的可视化能显示出数据流的一些性质.适应性也 增量Isomap的思想是通过更新坐标来保持最 佳的测地距，其算法主要过程分为以下几步山 是增量流形学习的一个优点一算法可以在数据逐 1)更新测地距.就Isoma即算法而言，对每个新 渐变化中调整流形.例如，假设学习N个个体的面 增的数据点yn+1都将引入一个新的顶点v.+1到图G 部图像的流形.经过一段时间后，不同人的脸部逐渐 中.然而，新增的顶点不仅会改变原有的邻域结构和 改变，这称为时间效应，是人脸识别中一个最具挑战 一些已知的最短路径，也增加了新的路径.在算法 性的研究工作，如果面部图像的流形可以根据这些 中，首先增加或移去某条与v+1相关的边.点对之间 面部变化调整，系统的性能就能提高).实际应用 的测地距离需要重新计算，这里使用一种改进的Di- 中大量流数据的产生为增量流形学习提供了广阔的 jkstra算法.对于增加的边，需要检查是否存在新的 发展前景.在数据挖掘中，数据通常是从一个数据流 最短路径；对于移去的边，需要重新计算所有曾经基 中有序地收集.在这种情况下，如果能用新增数据点 于该边来计算的点对： 对已有学习结果进行有效的更新，那将会非常有用.例 2)寻找新样本+1的坐标.匹配其与最接近目 如在图像检索8]、人脸识别、数据可视化等应用领域， 标值的样本：的内积形式，尽可能与目标值接近来 该技术能更好地描述图像的内蕴结构和语义关系。 确定其相应的位置， 2.1增量流形学习的分类 3)全局坐标校准.根据调整后的测地距离矩阵 目前增量流形学习方法主要可以分为2种：样 Gw,更新内在低维空间的数据点坐标.这里存在2 本独立训练和样本依赖训练.前者将新样本嵌人到 种更新方法，一种是对损失函数构造梯度下降算法 新构建的子空间中，是全局嵌入法的增量形式；而后 来更新；另一种是子空间迭代，直接对调整后的矩阵 者则侧重保持局部的邻域结构，求解在局部邻接信 作相应的特征分解，可视为求解增量的特征值问题， 通过特征分解得到坐标， 息约束下的优化问题.前者的优势是易于从理论角 2.2.2增量Isomap算法的不足、扩展与改进 度进行理解，在表达数据全局结构的基础上进行新 当加人一个样本点，可能会引起“短路边”出 样本点的增量嵌入；后者一般只需要进行增量谱方 现，样本点对之间的测地距发生很大的变化，导致点 法的计算，计算量上具有一定的优势.表1所列为现 的坐标产生很大的偏差.一些扩展和改进增量Is0 有主要的增量流形学习方法，如IDR(incremental di- map算法的研究包括如下23] mension reduction algorithm)[i9]、增量IAM(incre- 1)一个增量的测地距更新规则.该测地距被用 mental alignment method)[oj、谱嵌入增量流形学习 在增量Isomap中，通过改变测地距的稀疏性来提高 算法21门及增量LLE算法2]等.本文分别对其中主 坐标更新的效率 要的方法进行详细介绍. 2)增量地更新拓扑空间坐标的方法.使用子空
·380 智能系统学报 第7卷 间迭代方法来增量地更新插入新点以后的全局坐 特征值与原代价矩阵M的前d个最小的特征值近 标，并使用Rayleigh-Ritz加速[24.该方法独立于测 似相等，随着新增样本数目的增加，它们之间的差值 地结构的定义，故也可以被用在其他增量非线性维 将越来越大，从而导致特征值和特征向量解的误差 数约减方法中 对微小的扰动非常敏感. 3)对已有的增量式方法的改进2a1.由于Isomap 2)朱明旱等提出的一种基于正交迭代的增量 的测地线计算是全局算法，因此，改进的算法并非是 LLE算法[28 完全在线的.Isomap是一个全局的算法，对任何新 该算法分为2步：首先更新代价矩阵，在这个步 样本，需要考虑它是如何与其他样本相互影响的，为 骤中避免了一些重复的权值计算；然后不断地利用 了找到其坐标，需要将所有数据点的几何信息都保 前一次的处理结果来计算各样本的投影值，避免了 存起来，不适宜在大数据集上使用.解决该问题有2 新样本加入时的重复计算，并将求投影坐标时所需 种方法：一种办法是当累积了足够数量的样本时忽 的对高阶矩阵的分解转化为对低阶矩阵的分解.此 略最旧的样本点，这给算法带来了适应性的优势；另 方法降低了分解矩阵的阶数和数据的运算量，从而 一种是维持一组固定大小的“标记点”(landmark 提高了计算效率，较好地解决了在新样本不断加入 points),并只考虑新样本点与标记点之间的关系，最 的情况下总体流形不断更新的问题， 后，可以通过沿着流形的高斯分布来压缩数据点集， 2.4动态增殖流形学习算法 无需存储额外的信息 对于不断增加的海量观测数据集序列，不可能 在文献[25]中，作者提出了一种基于小世界模 一次获得嵌入到高维数据空间上的所有数据点集， 型的增量流形学习算法，将Isomap算法应用于增量 对于新来的观测数据子集，如何把其包含的几何信 处理新样本中.首先，对于新样本点，在训练集中找 息融合到以前所获信息中去是一个要解决的问题 出它的k近邻点及一些距离较远的点，接下来通过 对于已获得的观测数据集，要对整个数据集进行流 保持新样本和周围这些点的测地距离来获得新样本 形学习以发现其内在规律.目前的流形学习算法对 点的低维嵌入·从而新样本可以有效地映射到低维 于海量观测数据往往计算复杂度过高.流形学习的 空间中，该算法具有较低的复杂度， 增量非线性维数约减和增量LE是对新增单个数 2.3针对LLE的2种增量算法 据点进行逐个更新，但逐点更新计算代价较高，并且 L.K.Sal等提出的线性化的LLE算法假设流 新的观测区域数据的出现会破坏原有的几何结构， 形是局部线性的，训练样本的投影值不会因新样本 为了解决以上问题，曾宪华等提出了一种动态 的加入而发生改变[，这是一种线性近似的方法， 增殖流形学习算法8].这是通过整合重叠邻域中的 实际上，当新样本点加入时，由于原始数据集中一些 信息来发现全局几何结构的一种方法，保证嵌入空 样本的k近邻点会发生改变，它们投影以后的值也 间和内在低维空间对应数据点与局部邻域内的点保 会随之改变.故LE不适用于顺序到来的实时数 持相同的序关系，任何数据点和它的近邻点具有旋 据.另外LLE进行降维的原始数据集必须是数量固 转、平移与伸缩不变性.先用LE计算各子集的流 定的，当新点加入时，LE必须在扩展后的数据集上重 形，再将各子集的流形整合，得到整体流形结构，这 新运行，对新点不具有一般性，这使得LE不能用于动 是一种分批处理的思想.利用这一思想，增殖流形学 态系统的高维数据集，时间复杂度过高.针对LLE的这 习算法处理不断增加的数据集时，对稠密的近邻或重 些不足，近年来出现了2种方法来实现增量计算 叠数据子集（稠密是指该子集中的点能够反映嵌入流 )O.Kouropteva等提出的一种增量LLE算 形上某一部分的内在几何结构)分块，发现其低维流形 法12 结构.然后固定一块，对另一块施加平移、旋转和伸缩 当加人新样本点后，假设新代价矩阵Mm与原 变换，使得两者的低维流形具有观察数据子集间相同 代价矩阵M的前d个最小特征值近似相等，通过最 的近邻关系，这样随着观测数据集的增多，通过平移、 小化(YpeMT-diag(入1，入2，…，Aa))求出所有 旋转及伸缩变换整合得到的流形更加逼近高维数据空 样本的低维映射.该算法成功地求解了增量特征问 间的内在低维全局结构.这是一个增殖并保持原有信 题，但是存在2个缺点：①最优化问题.LLE已将最 息的过程，因此称之为动态增殖流形学习. 优化问题转化为求解矩阵特征向量的问题，而这种 增殖流形学习利用分治的方法和嵌入机理，把 增量LE方法又重新回到了求解最优化问题，处理 大任务分成多个不同的小任务，利用一种或多种流 不便：②病态条件下的特征问题.由于假设M的 形学习算法实现，用于实际应用中大数据集或超大
第5期 谈超，等：增量与演化流形学习综述 ·381· 数据集的内在几何结构及其内在规律的动态发现和 的特征值与特征向量不会产生大的变化.这使得重 整合，通过不断动态发现局部数据集的内在几何结 用当前的变换矩阵和坐标来更新更加有效.更确切 构，拓扑成几何结构更加完善的低维流形.这种动态 地说，因为LTSA算法中的排列矩阵B更具有局部 拓扑低维流形的方法是在线或者增量的方法，可以 性，新数据点的影响也更局部化，使得矩阵的更新更 克服现有流形学习算法存在的缺陷8] 简单[9].相对于文献[23]中增量式的Isomap算法， 该算法学习所需的数据子集必须是相邻或重叠 LTSA的增量式算法不需要费时的图重构过程而显 的，否则发现的低维流形将有较大的扭曲，即整个数 得更有效.不过，相对于原始LTSA算法时间复杂度 据集是非稠密的.非稠密的数据集上的增殖流形学 较高，增量LTSA算法使用了Rayleigh-Ritz加速方法 习是该算法进一步的研究方向 来提高算法效率 2.5增量LTSA算法 2)带标记点的增量LTSA算法， 如前所述，等距映射(Isomap)[5)1、局部线性嵌 在标记点Isomap算法[2a]中，寻找保持一组标 入(LLE)]和局部切空间调准(LTSA)[]等算法在 记点的测地距的映射，代替所有成对点的测地距，减 一些人工合成的数据集上取得了满意的可视化效 少计算复杂度.标记点增量LTSA算法与之类似，令 果，并在一些分类问题中得到了应用.但上述方法都 最先的山个点为标志点，在其中找k个最小距离的 是批处理模式，即在降维时所有数据都要准备好.而在 近邻点，构建局部切空间.新数据点的局部切空间使 监控等应用中，图像数据是逐步得到的，批处理模式需 用标记点的局部几何信息构建，新点的低维全局坐 要大量的计算量，重复地进行批处理降维极其耗时]， 标通过最小二乘问题求解.此方法解决了测地距离 针对批处理模式算法的不足，国内外学者开始 矩阵存储空间大及计算复杂度高的问题，为在大数 考虑增量式的流形学习算法，这里讨论的是非监督 据集上的使用提供了便利. 式的非线性流形降维问题，对于属于非参数化的增 2.6增量拉普拉斯特征映射算法 量流形学习算法来说，很适合数据的逐步获取.增量 Jia等提出的增量拉普拉斯特征映射算法[32]， 式算法的另一个好处是能检测数据流中的渐进变 通过一定意义上局部邻域信息的理想化保持计算数 化，可以很容易地修改以达到“遗忘”的效果).增 据集的低维表示，提出子流形分析算法及线性增量 量Isomap及标志点的增量式Isomap方法[2s]可以降 的模式来增量地学习新样本点并将其映射到低维空 低在处理新数据点时的时间复杂度.通过使用标志 间.该算法将局部线性重构机制用于更新已存在样 点，可以降低Isomap算法的空间要求，能较好地支 本的低维嵌入结果，并加入新的邻接信息.更新机制 持大数据量的应用.但由于Isomap算法基于最短测 类似于迭代算法，每当观测到一个新样本，只更新邻 地距，在处理新数据时，需要进行耗时的图重构，时 域发生变化的样本点，局部地改进现有样本的嵌入 间复杂度依然比较高9].iu等提出的增量LTSA 结果.算法的主要步骤如下. 算法能快速处理新数据点，通过最小化新数据点与 1)更新邻接矩阵w.构造新样本点x.+1与已知 已有数据点的低维坐标的最小重构误差，得到新数 样本点之间的权重，重构样本点之间因新点插入而 据点的低维嵌入坐标3o].受标志点Isomap算法的 改变的权重。 启发，Yin等的标志点LTSA算法能降低对内存的要 2)在低维空间映射新点.这里作者给出了2种 求.下面介绍几种对应的增量式算法。 方法，第1种是线性增量法，最小化加权距离目标函 1)增量LTSA算法[30) 数从而得到新点的低维映射y+1·第2种是在新点 假设给定n个数据点x:的全局低维坐标t:,对 的k个最近邻域即子流形上应用拉普拉斯映射，通 于新观测到的样本点x.+1,更新现有的坐标并给 过构建子邻接矩阵并计算特征值和特征向量来得到 出xn+1的映射+，算法由3步组成：首先，对于新数 新点在子流形中的低维坐标.接着计算新点的全局 据点xm+1,更新已有数据点的局部几何信息；接着使 坐标y。+1,计算过程可看作是坐标变换问题，通过变 用x+1相对于已有数据点的局部几何信息估计 换保持新点与其k个最近邻点之间的关系.通过在 t.+1;最后更新所有数据点的全局低维坐标t.算法 子流形上使用拉普拉斯映射，算法检测到新点x。+ 具体步骤见文献[30].根据文献[30]，增量LTSA 与已知点之间的内在结构信息，再计算它们之间的 算法最大的运算量是计算实对称半正定的排列矩阵 约束权重矩阵来最小化重构误差.服从该约束的最 B的最小特征向量集.当新数据点到达时，只改变部 佳权重可通过解最小二乘问题得到，再由权向量得 分数据点的近邻结构，而受轻度扰动的实对称矩阵 出xm+1的全局坐标ya+1