第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
.382 智能系统学报 第7卷 3)更新已存在样本点的低维嵌人坐标.若已存 习更新的计算复杂度较低，允许在线增量学习，并获 在样本点的邻域由于x+1的插人而改变，除了计算 得准确的函数近似及足够的一般性。 y+1,它们的嵌人坐标也需要被更新.这里使用局部 局部加权回归映射(locally weighted projection 线性重构机制来加入新的邻接信息，并修改已存在 regression,.LWPR)[35]是高维空间中具有冗余输人维 样本的低维嵌入结果.更新分为2步：首先找到每个 度的增量非线性近似函数的新算法，其核心是应用 已有点x:周围的k个最近邻点并计算重构权重来 局部线性模型的非参数化回归.为了保持计算效率 最小化耗费函数e;然后基于这些权重来找每个点 和数量的鲁棒性，每个局部模型以部分最小二乘回 的低维坐标y:·这里，某个点有可能不能立即得到精 归意义，在输人空间里用所选方向的一个单边变化 确的低维嵌入坐标，但随着增量学习的更新步骤，低 回归的较小数，预先形成了回归分析.Sethu等讨论 维坐标可不断被调整，直到近似最优化， 了局部学习技术是如何成功地用在高维空间中，并 该算法的增量模式可以被一般化到其他非线性 回顾了各种局部维数约减技术，提出了LWPR算 流形学习算法中去，例如LLE和Isomap.与一般迭 法.LWPR的特点是：1)应用基于增量训练的第二顺 代算法不同的是，增量拉普拉斯特征映射算法很简 序学习法快速学习：2)使用统计上有效的随机 单，当依次观测样本时可以实现在线学习， leave--one-out交叉确认来学习，无需存储训练数据； 2.7增量等距嵌入算法 3)仅依赖于局部信息来调整其加权核，最小化增量 Zha0等提出了增量等距嵌入的方法33341，通过 学习负面干扰的危险；4)具有与输人数量呈线性的 只映射新的数据点，并调整存在的嵌人结果，用增量 计算复杂度：5)可以处理大量的（可能是冗余的）输 的方法来产生新的嵌人结果.此外，这些方法也可以 入，例如上升到90维的数据集中的各种经验估计， 删除已存在的数据点并相应地调整嵌入的结果，通 般解释为产生了预变异和信任距离。 过在数据流上建立“滑动窗口”并嵌入增量数据，来 文献[35]提出，LWPR是第一个真正的增量空 约减一个无界数据流的维数 间局部学习方法，可以成功并有效地用于非常高维 2.8增量校准算法 的空间中 与已有流形学习算法相比，为保持度量，避免陷 2.10增量流形学习算法小结 入局部最小的问题，Han等提出了增量校准算 1)技术分类 法20.该算法属于局部保持映射，其主要思想是增 ①邻接矩阵的更新.更新邻接信息矩阵对于增 量地校准输入数据的局部坐标，通过成块地对齐邻 量学习来说是必不可少的步骤.一些增量算法如增 域信息，迭代产生整个高维数据集的低维映射.该方 量LLE、增量拉普拉斯特征映射和增量LTSA等，保 法包括2个步骤：增量和校准.第1个步骤增量地寻 持数据集内部的局部邻接信息并通过已存在样本的 找邻域块用于接下来的校准；第2个步骤迭代地对齐 邻接信息取得低维的嵌入， 邻域的低维坐标，产生整个数据集的低维嵌入.该算 ②迭代的使用.增量校准算法是一种典型的代 法与增量LTSA算法和增量等距嵌人算法都具有一定 表，它在找到邻域块之后，对齐它们的低维坐标，多 的相似性，都是通过局部校准邻域信息来增量学习高 次使用迭代的方法来达到增量学习的目的， 维数据，从而得到其低维的嵌入坐标.这种增量校准算 2)算法的区别和相似性. 法能适应不断增加的观测数据集的处理需求，对在线 ①全局和局部的区别.增量[somap保持了原 数据流处理、图像检索等方面具有良好的应用价值， Isoma即算法的全局性质，而增量LLE仍然是研究新 2.9高维增量在线学习 样本点与邻域之间的局部关系，这一点在增量拉普 在最近的统计学习中，高维输入数据的非线性 拉斯特征映射和增量LTSA中的第2、第3步也有体 近似函数是一个重要的问题，特别是在增量和实时 现，基于局部线性映射的增量学习算法36]也属于这 的情况中.越来越多的问题领域中，增量和实时这2 种类型 个特性都很重要.例如动态进程的在线模型，由可视 ②步骤的相似性.通过上面几种主要增量流形 化监督所观测，高级计算机接口的用户模型和数值 学习降维算法的阐述，可以看出，增量Isoma即算法、 函数学习，控制模型特别是在高维移动系统如人类 增量LTSA和增量拉普拉斯特征映射都包括3个步 或仿真机器人的背景中.针对这些任务的理想算法 骤.其中增量Isomap包括：首先更新测地线距离；接 需要避免潜在数量上的问题，如输入数据的冗余，消 着更新坐标；最后寻找新样本x+1的坐标.增量拉普 除不恰当的输入维数，在数据保持有效的情况下学 拉斯特征映射为：第1步，更新邻接矩阵w;第2步
第5期 谈超，等：增量与演化流形学习综述 ·383 在低维空间映射新点；第3步，更新已存在样本点的 并且由于新点的特征值没有更新，随着新增样本数 嵌入结果.增量LTSA首先根据新数据点x+1更新 目的增加，新点与已知点的前d个最小的特征值间 已有数据点的局部几何信息；接着使用x+1相对于 的差值会越来越大，从而导致误差会越来越大.表3 已有数据点的局部几何信息估计全局低维坐标：最 对部分增量流形学习算法的优缺点及适用范围进行 后更新所有数据点的全局低维坐标.可以看出，增量拉 了整体的概括和评价 普拉斯特征映射和增量LTSA的步骤非常类似. 表2增量流形学习算法的对比分析 ③处理数据的类型以及数学表达的方式.增量 Table 2 Comparative analysis of incremental manifold Isomap是等距嵌入的算法，它主要是从保持测地线 learning algorithms 的角度来处理新加入的样本.增量LE是通过解协 全局/ 处理数据 算 数学表达 法 方差矩阵的特征值和特征向量来求新点在低维坐标 局部 类型 方式 下的映射.增量拉普拉斯特征映射和增量LTSA都 增量Isomap全局性保持测地线 等距嵌入 是从数据点的局部几何信息出发，根据新点与其相 增量LE 局部性 协方差矩阵 最优化问题 邻的已有点之间的邻接关系来估计其全局坐标，是 动态增殖流 局部性拓扑几何结构 分治和嵌入 通过研究邻域关系进行的嵌入算法.表2对上文提 形学习算法 到的增量流形学习算法进行了对比分析！ 数据点局部几何 增量LTSA局部性 嵌人算法 3)主要存在的问题 信息 Isomap的测地线计算是一个全局的算法，因 数据点局部几何 增量LE 局部性 嵌入算法 此，增量Isomap算法并非是完全在线的，对任何样 信息 本，在找到其坐标之前需要考虑它是如何与其他样 Incremental 局部性 局部邻域信息 等距嵌入 本相互影响的；增量LLE牵涉到最优化问题，LLE K-MST 输入空间所选方部分最小二乘回 本身是将最优化问题转化为求解矩阵特征向量的问 LWPR 局部性 向的较小数 归 题，而增量LLE实际上又重新回到了最优化问题， 表3部分增量流形学习算法的评价及适用范围 Table 3 Evaluation and applicable field of incremental learning methods 算 法 优势 缺陷 适用范围 增量Isomap 属于全局算法，并非完全基于可视化数据流进行增量 能够发现流形结构演化的过程 在线 的流形学习 基于正交迭代的增量LE算法 增量LLE(分为LLE和基 对于最优化问题处理不便，针对现实世界的非线性流形 于正交迭代的增量LE 有效利用原处理结果，避免重复 计算，降低了数据的运算量，提高 误差会随着新增样本数目的 学习，处理非均匀分布的数 算法) 增加而增大 了处理速度 据集 实现容易，当样本依次被观测时 增量拉普拉斯特征映射 时间复杂度高 适用于在线学习 可以实现在线学习 时间复杂度较高，为提高算 局部化算法，使矩阵的更新更简 能检测数据流中的渐进变 增量LTSA 法教率需使用Rayleigh-Ritz 单，新数据点的影响更局部化 化，适合数据的逐步获取 acceleration方法加速 3演化流形学习 演化学习是在时间进化数据上的学习问题，学 习任务包括静态状态和时间进化机制的学习，可分 3.1演化学习的概念 为半监督学习（分类/回归）和非监督学习（聚类/密 实际系统往往是动态的，数据沿着时间不断变 度估计)等. 化，静态数据上的常规学习并不适合.针对动态问题 1)增量学习：根据有限内存或在线设备，数据 的解法包括：1)在数据集上应用静态算法；2)在每 组织成批量或流状模型.与演化学习的不同在于：增 个时间点上对数据应用静态算法，包括时间进化机 量学习假设所有数据来自同一分布，对整个数据集 制和动态预测 的输出单一，如分类、回归、数据分类或密度模型.增
384 智能系统学报 第7卷 量算法的期望对数据顺序敏感，因此不对临时数据 流形学习的必要性，下面将从非监督和半监督2个 进行推进 方面来对演化流形学习算法进行讨论。 2)在线学习：实际学习环境中的一种特殊类 3.2非监督演化学习 型，即连续循环的一组序列.当在时间t预测时，学 近年来演化聚类成为数据挖掘中提取信息的一 习者只能观察到t为止的样本，故动态地更新以寻 项新的研究热点.在流形学习领域，聚类是一个基本 求较低的遗憾值(regret).与演化学习不同，在每个 的问题941].传统的聚类算法，如K-means21和谱 时间点t,在线学习观察单个样本，而演化学习观察 聚类[3]都是基于静态数据，并假设所有数据是独立 一组样本，故演化学习可以在线或离线地处理数 同分布(independent and identically-distributed,I.I. 据73.在线学习要求每个样本点的回馈，而演化 D)的，即样本来自同一个潜在的分布.在这种数据 学习中，一组样本可能是标记的、未标记的、或部分 上的聚类任务产生出了演化聚类问题4].此外，与 标记的.最小化在线学习与离线学习相应的遗憾值 增量演化聚类[4不同的是，由于数据的分布时刻彼 在每个时间点不存在一般化问题.而演化学习旨在 此相邻，沿着时间顺序的聚类结果应该是连续的.演 达到2个目标：在每个时间点的损失一般化及时间 化聚类的目标包括：对每个时间点t,输出，上的一 进化机制的学习 个分布π：保持分类的质量和沿t分布{π：：=，的光 演化学习与增量学习、在线学习35]的比较如表 滑性；聚类追踪等.演化聚类的意义在于：可解释机 4所示。 器学习及数据挖掘算法；保持沿着时间的聚类结果 表4演化学习算法与其他学习算法的比较 的连贯性，特别是在可视化方面；聚类追踪为动 Table 4 Comparison of evolution learning algorithms with 态网络行为的分析提供有力对策.由于种种原因，例 other learning methods 如数据大小的变化、聚类数目的变化、聚类沿着时间 算法 算法思想 性能特点 的动态行为（出生、交叉和死亡等），演化聚类具有 假设所有数据来自同一 很大的挑战性.前面一节提到，当数据分布移动时， 分布，对整个数据集的 采用传统的聚类算法处理整体数据时，不能保留聚 增量 基于流形学习的增量方输出单一，如分类、回 类结果沿着时间的连贯性.故将演化聚类用在流形 学习中，对于处理动态高维数据集的低维流形并得 学习 法，对动态增量的数据归、数据分类或密度模 流模型进行学习 型.不对临时数据进行 出其聚类结果具有积极意义， 推进，增量算法期望对 演化谱聚类和演化聚类是2种基本的数据组成 数据顺序敏感. 方式[6们.目前研究的主要问题包括：1)什么是演 当在时间t预测时，学 化；2)光滑代表什么；3)演化K-均值、演化GMM等 习者只观察到t为止的 在线 要求每个样本点的回 方法是否有一般化的方法；4)聚类行为；5)聚类数 学习 样本，动态地更新来寻 馈，观察单个样本 目和数据大小的变化： 求较低的遗憾值(e Zhang等提出了在线演化幂簇混合算法(online gret) evolutionary exponential family mixture)[s],该方法提 在时间t对样本x的分 出了对聚类问题的密度估计的观点，针对幂簇混合 布P进行学习.可以在 模型(K均值模型和多项式混合模型)进行密度估 演化在时间进化数据上的线或离线处理数据，在 计，属于非监督的算法.它采用了期望-最大化(ex 学习学习 每个时间点上对数据应 pectation-maximization,EM)方法进行计算：E步属 用静态算法，包括时间 于幂簇混合(exponential family mixture,EFM)的聚 进化机制和动态预测. 类问题；M步使用EFM的闭合形式解法.Z☑hang等 前面提到，演化学习是一种基于演化发展的最 还提出了2个框架：第1个框架依赖历史数据，即当 优化方法，可以用于解决机器学习中的最优化问题， 前的模式分布近似于历史数据的分布；第2个框架 用在流形学习中，为发现高维数据集的低维流形提 依赖于历史模型，即当前的模型分布近似于历史模 供了新的途径.首先，当数据分布移动时，可能不适 型分布.这2种框架都基于EFM模型41，该方法用 合采用传统的聚类算法来处理整体数据；其次，如果 于流形学习中，对动态高维数据集进行数据降维以 对每个新样本点独立使用传统的聚类算法，不能保 后的聚类，属于演化流形学习的非监督方法，有待解 留聚类结果沿着时间的连贯性，这里就体现出演化 决的是聚类追踪的问题
第5期 谈超，等：增量与演化流形学习综述 ·385 3.3半监督演化学习 现有流形学习算法主要面临的问题是在线环境 演化分类是指学习一条针对不同时期的演化分 下的误差、优化及收敛性等问题.这与邻域图上各点 类链.它的意义在于当使用历史分类器或所有历史 邻域点的选取、坐标映射过程中方程的求解以及算 数据都无用的情况下，历史分类信息可能有助于分 法收敛性等方面都有一定关系.未来工作可以从这 布缓慢进化，可以使用而不是抛弃历史标记.Ja等 几个方面展开，以解决存在的这些问题.另外还有以 提出了半监督演化分类算法(semi-supervised evolu- 下几个方面值得进一步地研究 tionary cafication)[9],将一般学习问题中的光滑 1)减少算法中参数的依赖性.目前的增量流形 假设扩展到演化数据中.光滑假设是指：若2个数据 学习算法中近邻数是变量，如何依据要处理的问题 点靠得很近，容易有近似的标记.而演化光滑假设是 和数据的分布自适应地选择适当的局部近邻数值得 指：若时间点t1和t2靠得很近，两分类函数f和f 进一步研究 容易近似.实现以上假设的直接方法是对时间积 2)目前的增量流形学习算法大多属于非监督 分，当t不连续时，用反向差异来近似以上积分，这 学习，如何提高新增样本点的学习能力是一个重要 是学习算法的一种时间调整， 的问题.虽然标记点技术已用于增量Isomap和增量 学习数据的自然演化信息在机器学习研究中是 LTSA等算法中，但它们还不具有监督意义.可以考 种新的挑战.上述算法属于演化流形学习的半监 虑将监督算法与增量流形学习领域的算法相结合， 督方法，应用在真实世界的流形学习中，处理经过降 提高在线学习的能力， 维以后的实时数据，并对数据集学习了一系列演化 3)提高算法的效率.增量流形学习一般比批量 的分类函数，无论是稳定性还是精确性方面都产生 算法的时间复杂度更高，如何对已有算法进行加速， 了更好的性能. 使之应用到对计算时间要求较高的新领域，也是值 3.4演化流形学习小结 得深人研究的问题 一种超越了独立同分布假设(I.I.D)[24的学 4)当样本点包含噪声点时，原始的流形学习算 习问题的新类型称为演化学习.最近又提出了一些 法（如ISOMAP和LLE)受到了很大的影响，增量 非监督算法[03]、半监督算法「451和有监督的流形 Isomap算法也存在类似的问题.如何减少噪声干扰 学习算法6可，在线增量学习的向量量化策略] 在增量流形学习中也是一个重要的问题： 以及增量谱聚类9]等演化流形学习算法，取得了令 5)就目前来看，许多实际应用中的数据集都存 人满意的结果.但这些仅仅是探索工作，未提供理论 在规律性，因此研究流形与数据集的关系成为了一 分析.演化学习主要是基于模仿生物演化行为而发 个重要领域.在将来的工作中，必须找到一个行之有 展的最优化算法，用于学习高维流形时，可以帮助人 效的方法来分析高度相关、复杂分布的数据集的内 们解决许多困难的流形学习问题.无论是非监督演 在结构.最近Zhang等提出的自适应流形学习算法 化聚类还是半监督演化分类，都是建立在已有监督 通过自适应地选择局部邻域结构，将局部结构拼接 或非监督学习算法之上，引进了时间进化的条件，相 在一起产生全局参数信息，解决了局部依赖问 信通过进一步的理论探索，无论是增量学习、在线学 题[].怎样使用增量流形的性质来模拟未知的概念 习还是演化学习都将在流形学习领域产生新的研究 和设计新的算法是今后研究的另一个方向， 点和研究价值 6)演化学习的产生是为了解决现有学习算法 4总结与展望 与实际系统中的困境，目前出现的成果还仅是一些 探索工作，包括非监督演化学习及半监督演化学习. 目前，流形学习在许多领域都有广泛的应用，例 对这些算法进行更深入的理论分析，并在更多的数 如模式识别、统计回归、智能控制、生物信息、数据挖 据集上进行实验来评价算法的性能和价值，是值得 掘、数据压缩、时间序列分析等，是近年来机器学习 进一步探讨的问题， 领域的研究热点.而增量流形学习能发现大规模海 量数据集的内在低维信息，更好地解决在线和增量 参考文献： 的问题；演化学习在流形学习中的应用，解决了传统 [1]LAW M,ZHANG Nan,JAIN A K.Nonlinear manifold 流形学习存在的不足，比如观察数据集的移动分布， learning for data stream[C]//Proceedings of the Fourth SI- 及时间连贯性等问题，学习数据的自然演化信息，建 AM Interational Conference on Data Mining.Lake Buena 立更接近真实世界的优化模型 Vista,USA,2004:3344
.386. 智能系统学报 第7卷 [2]徐蓉，姜峰，姚鸿勋，等.流形学习概述[J].智能系统学 duction methods for wood surface inspection[C]//Proceed- 报，2006,1(1)：44-51 ings of the 6th International Conference on Quality Control by XU Rong,JIANG Feng,YAO Hongxun,et al.Overview of Artificial Vision.Gatlinburg,USA,2003:178-188. manifold learning[J].CAAI Transactions on Intelligent Sys- [16]KRUSKAL J B,WISH M.Multidimensional scaling[M]. tems,2006,1(1):4-51. Beverly Hills,USA:Sage Publications,1977. [3]SEUNG H,LEE D.The manifold ways of perception[J]. [17]ZHANG Zhenyue,ZHA Hongyuan.Principal manifolds Science,2000,290(5500):2268-2269 and nonlinear dimensionality reduction via tangent space [4]PEARSON K.On lines and planes of closest fit to systems alignment [J].SIAM Journal of Scientific Computing, of points in space[J].Philosophical Magazine,1901,2 2004,26(1):313-338. (6):559-572. [18]LU Ke,HE Xiaofei.Image retrieval based on incremental [5]TENENBAUM J,DE SILVA V,LANGFORD J.A global subspace learing[J].Pattern Recognition,2005,38 geometric framework for nonlinear dimensionality reduction (11):2047-2054. [J].Science,2000,290(5500):2319-2323. [19]YE Jieping,LI Qi,XIONG Hui,et al.IDR/QR:an in- [6]BELKIN M,NIYOGI P.Laplacian eigenmaps for dimen- cremental dimension reduction algorithm via OR decompo- sionality reduction and data representation J].Neural sition[J].IEEE Transactions on Knowledge and Data En- Computation,2003,15(6):1373-1396. gineering,2005,17(9):1208-1222. [7]ROWEI S,SAUL L.Nonlinear dimensionality reduction by [20]HAN Zhi,MENG Deyu,XU Zongben,et al.Incremental locally linear embedding[J].Science,2000,290(5500): alignment manifold learning[J].Journal of Computer Sci- 2323-2326. ence and Technology,2011,26(1):153-165. [8]曾宪华，罗四维.动态增殖流形学习算法[J].计算机研 [21]LI Housen,JIANG Hao,BARRIO R,et al.Incremental 究与发展，2007,44(9)：1462-1468. manifold leaming by spectral embedding methods[J].Pat- ZENG Xianhua,LUO Siwei.A dynamically incremental tem Recognition Letters,2011,32(10):1447-1455. manifold learning algorithm[J].Joumal of Computer Re- [22]KOUROPTEVA O,OKUN O,PIETIKAINEN M.Incre- search and Development,2007,44(9):1462-1468. mental locally linear embedding algorithm[C]//Proceed- [9]DE SILVA V,TENENBAUM J B.Global versus local meth- ings of the 14th Scandinavian Conference Image Analysis. ods in nonlinear dimensionality reduction M]//BECKER Joensuu,Finland,2005:521-530. S,THRUN S,OBERMAYER K.Advances in Neural Infor- [23 LAW M H C,JAIN A K.Incremental nonlinear dimen- mation Processing Systems.Cambridge,USA:The MIT sionality reduction by manifold learning[J].IEEE Trans- Press,2003:721-728. actions on Pattern Analysis and Machine Intelligence, [10]BERGER M,GOSTIAUX B.Differential geometry:mani- 2006,28(3):337-391. folds,curves and surfaces[M].[S.1.]Springer-Verlag, [24]GOLUB G H,VAN LOAN C F.Matrix computations[M]. 1988:474. Baltimore,USA:Johns Hopkins University Press,1996: [11]PLESS R,SOUVENIR R.A survey of manifold leaming 1-694. for images[J].IPSJ Transactions on Computer Vision and [25]SHI Lukui,YANG Qingxin,LIU Enhai,et al.An incre- Applications,2009,1:83-94. mental manifold leamning algorithm based on the small [12]BREGLER C,OMPHUNDRO S M.Nonlinear manifold world model [C]//Proceedings of the 2010 International leaming for visual speech recognition[C]//Proceedings of Conference on Life System Modeling and Intelligent Com- the 5th International Conference on Computer Vision. puting,and 2010 Intemational Conference on Intelligent Washington,DC,USA:IEEE Computer Society,1995: Computing for Sustainable Energy and Environment. 494499. Wxi,China,2010:324-332. [13]HADID A,KOUROPTEVA O,PIETIKANINEN M.Unsu- [26]SAUL L K,ROWEIS S T.Think globally,fit locally:unsu- pervised leaming using locally linear embedding:experi- pervised learning of low dimensional manifolds[].Journal of ments in face pose analysis[C]//Proceedings of the 16th Machine Leaming Research,2003,4:119-155. Interational Conference on Patter Recognition.Quebec [27]KOUROPTEVA O,OKUN O,PIETIKANEN M.Incre- City,Canada,2002:111-114. mental locally linear embedding[J].Patter Recognition, [14]JENKINS O C,MATARIC M J.A spatiotemporal exten- 2005,38(10):1764-1767. sion to Isomap nonlinear dimension reduction[C]/Pro- [28]朱明旱，罗大庸，易励群，等.基于正交迭代的增量E ceedings of the 21th International Conference on Machine 算法[J].电子学报，2009,37(1)：132-136， Leaming.New York,USA,2002:2551-2556. ZHU Minghan,LUO Dayong,YI Liqun,et al.Incremen- [15]NISKANEN M,SILVEN O.Comparison of dimensionality re- tal locally linear embedding algorithm based on orthogonal