高小方,刘杰飞

(山西大学 计算机与信息技术学院,山西 太原 030006)

面向等维独立多流形的增量学习算法IMM-ISOMAP

高小方,刘杰飞

(山西大学 计算机与信息技术学院,山西 太原 030006)

流形学习是机器学习与数据挖掘领域的一个重要研究方向。其经典算法总是假设高维数据批量存在于单一流形,且不能有效处理增量式出现的高维多流形数据。针对等维独立多流形提出一种增量学习算法IMM-ISOMAP。首先在对新样本增量地更新动态邻域时,仅修改关键路径,避免重新计算全部邻域关系,以提高算法整体效率。然后通过扩展切空间的方法将新样本依次划分到各子流形,实现新样本的增量式分类算法。最后对各子流形计算低维嵌入并进行合并。实验结果表明,该算法可以有效地应用于人造多流形数据和实际得多流形图像数据。

流形学习;增量学习;等维独立多流形;动态邻域;切空间;IMM-ISOMAP

0 引言

流形学习是目前机器学习与数据挖掘领域中一个重要的研究课题,其目的在于根据有限的离散样本学习和发现嵌入在高维空间中的低维光滑流形,实现非线性维数约简。但是,其经典算法,比如ISOMAP[1]、LLE[2]等,总是假设高维数据位于单一流形上,且不能处理增量式出现的高维数据。在现实生活中,大量的高维数据位于多流形上。比如数字识别中每个数字的手写体均会在特征空间中各自形成不同于其他数字的独特流形;再比如人脸图像识别中不同的人脸图像在特征空间中也总是位于不同的流形上。而且这些高维数据往往是连续获得、不断增加的,例如视频监控数据与语音识别数据。目前,流形学习的研究并没有实现对大数据环境下不断增长的高维多流形数据的非线性维数约简,但是针对多流形识别[4-12]和增量学习[14-20]分别提出了一些算法。

多流形的识别在流形学习研究中是一个重要的组成。大多数针对多流形的识别方法是基于聚类[4-7]或者Manifold Clustering[8-10]的思想,并没有考虑基于流形的拓扑结构,而且必须事先知道存在的流形个数。Fan等人[12]则是利用MPE算法的梯度下降法来进行多流形的降维,但是并不能进行子流形的识别。而面向等维独立多流形的DC-ISOMAP算法[11],是基于扩展切空间的思想,依据流形自身的拓扑结构来分解子流形,有效地解决了等维独立多流形的识别问题。增量学习是流形学习从研究走向实用化的关键问题之一。尤其是在大数据环境下,数据样本动态变化,将原来已经计算得到的信息丢弃掉再重新计算,不仅造成计算资源的极大浪费,而且其处理方式也是不现实的[3]。为了尽量避免对海量数据的重复计算,一些针对经典流形学习算法的增量学习算法[14-20]被提出。这些算法虽然能够有效地实现增量数据的计算和更新,但由于邻域关系和特征矩阵的计算量巨大,其效率并不高。Li等人提出的incremental k-VC方法[20]会严重受其模型算法如网络流算法的影响。在基于动态K-NN的ISOMAP增量学习算法[3]中,动态K-NN算法和“短路”识别算法能够快速有效地更新邻域关系,Dijkstra算法和冲突路径更新算法也能近似无损地计算和更新测地距离矩阵,高效地实现ISOMAP的增量学习能力。

本文基于DC-ISOMAP算法[11]和基于动态K-NN的ISOMAP增量学习算法[3],提出了面向等维独立多流形的增量学习算法IMM-ISOMAP。首先通过动态邻域算法[13]计算新增样本的邻域关系,并且通过扩展切空间的方法将新样本依次划分到各子流形。然后计算每个新子流形的低维嵌入,同时检测并更新各子流形中新增样本可能造成的“短路”或者冲突路径。最后依据各子流形的邻接关系拼接出整个样本集合的低维嵌入,实现其数据集的可视化。

1 相关工作

经典的流形学习算法通常包括三个步骤:构建邻域关系图以近似模拟流形的拓扑结构、构建特征矩阵以保留高维数据的特征信息、计算低维嵌入结果。

1.1 面向等维独立多流形的DC-ISOMAP算法

面向等维独立多流形的DC-ISOMAP算法[11]主要从构建邻域关系图着手,由计算动态邻域形成的切空间扩展子流形,以识别出不同的子流形,直至等维独立多流形全数分解。然后对各子流形分别构建特征矩阵并计算低维嵌入,最后依据各子流形的邻近关系合并低维嵌入。

本论文在前期工作中提出了通过采样密度和曲率计算切空间并确定动态邻域的算法[13]。首先通过样本数的正比关系估算出仅包含xi的d维超球半径T1(xi):

(1)

如果xi的邻近点xj与其切空间T1(M)的夹角为θj,θj的定义如下:

(2)

当θj小于一个较小的阈值时,认为xj属于xi的近邻。在逐个增加xi的近邻时,其切空间不断更新,直到

(3)

在DC-ISOMAP算法中,节点xi和xj之间的切空间偏差可以定义为:

(4)

xj=argminj(vij) .

(5)

1.2 基于动态K-NN的ISOMAP增量学习算法

在增量学习算法中,随着数据的不断积累,充分利用原始数据的计算结果,并提高大规模数据的算法效率成为首要任务。基于动态K-NN的ISOMAP增量学习算法[3]仍然是基于单流形的假设,在充分保留并利用原有的中间结果的同时,如邻域矩阵、测地距离矩阵、前置矩阵,计算新增批量数据的低维嵌入。相对于经典的ISOMAP算法,基于动态K-NN的ISOMAP增量学习算法增加了三个主要功能:动态K-NN、“短路”判断算法judgeShortCircuits和冲突路径判断算法updateShortCircuits。

动态K-NN算法是基于K-NN的动态邻域算法。当获取新增批量数据后,在原有邻域关系中增加新的K-NN关系,使得邻域关系包含新增K-近邻,但是并不删除不属于新K-NN的原有邻域关系。也就是说,在动态K-NN邻域关系中,样本点的近邻个数大于等于K,而不是一定等于K。同时,为了保证在增加新样本后,动态K-NN算法能够具有与K-NN算法一样的克服原有“短路”的能力,该增量学习算法给出了短路判断算法judgeShortCircuits[3]。该“短路”判断算法主要针对“邻域切片”中增加新样本C为近邻的旧样本A。如果该新近邻C到该旧样本A的其他一个旧近邻B的距离CB大于原距离AB与“邻域切片”最大“半径”之和,则判断旧样本A、B之间存在短路。动态K-NN算法和“短路”判断算法保证了增量学习算法中邻域关系的快速更新,而且尽量保证原有邻域关系避免发生变动。这是整个增量学习算法的基础,因为每一组邻域关系的变动,都可能会引发多条测地距离的更新,但并不一定会大幅提高整体算法的精度。

所有的测地距离都是由邻域关系计算出最短路径的距离估计而得。在邻域关系中增加了新样本点后,测地距离矩阵中的数据需要重新计算。虽然大多数被更新的“测地距离”使得距离实际距离更“近”了一点,但并不能大幅提高整体算法的精度,而且时间复杂度将会随着样本点的增大而大幅增加。这些需要更新的测地距离中只有以下两种是必须的:由“短路”计算出的错误距离、冲突路径计算出的距离。冲突路径,即从样本I到J的路径信息与从J到I的路径信息不一致,主要由新增样本引发。基于动态K-NN的ISOMAP增量学习算法中仅更新了这两种测地距离,虽然使得测地距离矩阵的计算精度在一定程度上受到了损失,但提高了整体算法的效率。

2 面向等维独立多流形的增量学习算法IMM-ISOMAP

本文提出的面向等维独立多流形的增量学习算法IMM-ISOMAP主要实现多流形数据的增量学习能力并进行多流形识别和非线性维数约简。顾名思义,增量学习就是在有新增数据情况下能够利用原有计算结果对新增数据进行学习。不需要对整个数据集重新计算,仅做由新增数据引起的更新。整个增量学习的时间代价通常远低于重新计算整个数据集所需的代价。

在算法IMM-ISOMAP中,首先通过动态邻域算法[13]计算新增样本的动态邻域;然后找到与原始子流形具有较小切空间偏差的新样本,并将新样本划分到对应子流形,形成新的子流形;最后计算每个新子流形的低维嵌入,同时利用DC-ISOMAP算法[11]中合并嵌入结果的方法计算各个新子流形的邻近关系以确定各新子流形的位置关系,拼接出整体数据的最终嵌入结果。具体算法参见算法1。

算法1：IMM-ISOMAP算法描述

if∃xj(xj∈X)∩(xj∈Ninew)∩(xj∈sXk) if∃s(s∈X)∩(s∈Ninew)∩(s∈sXg) sXk=sXk∪sXg;sXg=ø;sXk=sXk∪{xinew}; 扩展xinew的新增样本近邻; else sXk=sXk∪{xinew} 扩展xinew的新增样本近邻; endif;else 选择下一个被扩展的新样本点xinew和原有样本xj; ifxj不存在 在剩余所有新样本中建立新的子流形集合sXi; endif; endif;4.增量计算新样本低维嵌入: 调用judgeShortCircuits检测sXi中的“短路”并在N、G、P中删除与其相关的信息; 利用Dijkstra算法计算被删除的测地距离及其相关信息; 调用updateShortCircuits更新sXi中的冲突路径; 计算各子流形sXi的低维嵌入sYi;5.计算各子流形的邻近关系并将各子流形的sYi拼接成Y={y1…yn+m};

2.1 更新邻域关系

为了得到较准确的拓扑流形结构,邻域关系要在整体数据集上进行计算,不仅包含原数据集,还要包含新增样本数据。由于多流形数据混杂在一起,由K-NN算法计算邻域关系时,无法避免不同子流形上的点邻域关系混杂在一起，IMM-ISOMAP算法采用基于采样密度和曲率的动态邻域方法来计算邻域和切空间[13]，以进一步提高算法精度。

2.2 更新子流形的划分

整个划分的过程是从与原样本具有最小切空间偏差的新增样本开始,因为切空间偏差最小可以保证起始样本的划分出错概率最小。

当新增样本的两个或两个以上近邻(原样本)分别属于不同子流形时,说明随着样本的增加,原来不相连的子流形拼接成一个新的子流形,即子流形相融合;当新增样本存在的近邻仅属于同一个子流形时,将该新增样本划分到同一子流形中;否则该新样本或者因为其新样本近邻被扩展,或者与其他新样本构建成独立的子流形。

2.3 更新低维嵌入

基于动态K-NN的ISOMAP增量学习算法[3]在更新邻域关系时,采用了动态K-NN。在更新测地距离矩阵时,仅更新了短路引起的错误测地距离和存在冲突路径的测地距离。IMM-ISOMAP算法对每个子流形做同样处理。

针对每个子流形,如果有新增样本的加入,则邻域关系已经发生变化。由新增样本引发的“短路”和冲突路径可以通过judgeShortCircuits和updateShortCircuits算法[3]检测和修正。如果没有新增样本的加入,则原计算结果无须更新。如果是新增子流形,则通过经典ISOMAP算法计算。

2.4 更新最终嵌入结果

在计算出所有子流形的低维嵌入后,要利用DC-ISOMAP算法[11]对这些嵌入结果拼接合并。首先要选出每个子流形的一些标准点以确定该子流形在整体数据集合中的位置关系。然后通过ISOMAP算法对这些标准点计算出最终嵌入结果的“框架”。最后利用这些标准点将各个子流形坐标转化,“嵌”入最终嵌入结果中。

2.5 时间复杂度分析

假定原样本集合有n个数据,新样本集合有m个数据。基于经典的ISOMAP算法提出的DC-ISOMAP算法,首先需要在原样本与新样本的基础上通过扩展切空间分解子流形,重新构建近邻图,再重新计算全部样本之间的新的测地距离,最后通过各子流形的低维嵌入与外层节点信息确定子流形的位置关系并最终组合得到新的低维嵌入。因此其时间复杂度为Ο((n+m)log(n+m)+(n+m)+k(n+m)2log(n+m)+(n+m)3),其中k为邻域大小所设定的参数;而IMM-ISOMAP算法在计算动态邻域时只需要计算新样本的动态邻域,其时间复杂度为Ο(mlog(n+m))。在将新样本重新划分到新子流形及处理新子流形中可能出现的“短路”情况或冲突路径时,其时间复杂度为Ο(mn+m(nq+nq2)+|C|+|S|log|S|+q|S|),其中q为增加新节点后邻域图上所有点的最大的度,其中|C|,|S|分别为冲突路径与“短路”路径的数量,且|S|一般较小可忽略。最后计算新子流形的低维嵌入时其时间复杂度为Ο((n+m)2)。故IMM-ISOMAP算法整体的时间复杂度近似为Ο(mlog(n+m)+mn+mnq2+|C|+(n+m)2)。由于新样本集的规模一般是远远小于原样本集的规模,即m≪n,则IMM-ISOMAP算法的时间复杂度要小于重新运行全部数据的DC-ISOMAP算法的时间复杂度。

3 实验结果及分析

分别进行了三组实验,第一组实验通过数据比较了IMM-ISOMAP算法通过扩展切空间分解多流形与K-means、D-C[4]、SMMC[5]、DC-ISOMAP[11]等算法分解相同多流形数据的精度及所需的时间。第二组实验是随着多流形数据的不断增长,可视化地展示了IMM-ISOMAP算法与ISOMAP、D-C和DC-ISOMAP算法得到的低维嵌入结果之间的差异。第三组实验则可视化地比较了IMM-ISOMAP算法与ISOMAP、D-C和DC-ISOMAP算法分别在UMist-Cropped人脸数据集上的结果以及随着多流形数据的不断增加,运行以上算法分解子流形的精度变化和所消耗时间的变化。由于除了IMM-ISOMAP算法具有增量能力,其余算法均不具有增量能力,因此在计算这些算法所消耗的时间时采用的是这些算法单次执行所消耗的时间。

3.1 分解子流形的精度及效率实验

表1中的数据展示了IMM-ISOMAP算法与其他算法分解多流形数据的精度以及各自所消耗的运行时间之间的比较。表中的三组数据分别是从Swiss-roll、UMist-Cropped与ORL-Cropped裁剪后作为实验数据集,由于实验环境的限制,其中UMist-Cropped与ORL-Cropped数据集分别是从UMist人脸数据集与ORL人脸数据集上选择部分人脸数据通过手工剪裁来作为实验数据。

实验结果显示:(1)IMM-ISOMAP算法与DC-ISOMAP、SMMC算法在分解精度方面比其他算法明显要高,可以精确的分解开子流形;(2)K-means算法不适用于高维非线性数据,因此精度较低。另外精度虽然较高的SMMC算法,却需要事先设定聚类的个数,而且由表中数据可知SMMC算法在处理维度较高的数据时其运算所需时间会急剧增大,因此也不适用于高维增量数据;(3)IMM-ISOMAP算法不仅不需要预先设定子流形个数,而且可以像DC-ISOMAP算法一样准确分解子流形。另外由于DC-ISOMAP算法不具备增量能力,在处理新数据时需要将全部数据集重新计算,浪费了大量的计算资源,使得其在运行时会消耗大量的时间;(4)相比于其他不具备增量能力的算法,IMM-ISOMAP算法可以在保障较高分解精度的情况下,其运算所消耗的时间与新增样本数据之间呈线性相关。实验结果还显示,相对于维度更高的数据UMist-Cropped与ORL-Cropped,IMM-ISOMAP算法消耗的时间相对更少,也就是说IMM-ISOMAP算法更适用于高维数据。这也就证明了IMM-ISOMAP算法有很高的效率,可以很好的应用于大规模数据。

3.2 人造数据上的增量学习实验

Swiss-rollwith5parts数据集是从Swiss-roll数据集中截取的五块相互之间独立的子流形数据集。从Swiss-rollwith5parts中随机选取1 400个点,其中900个点作为原始数据集,其余500个点分为五个子集作为新增数据集。分别运行IMM-ISOMAP算法与ISOMAP、D-C方法与DC-ISOMAP四种算法,随着多流形数据的不断增加,不同算法运行得到的低维嵌入结果的可视化结果如图1显示。图2显示了随着多流形数据的不断增加,ISOMAP、D-C、DC-ISOMAP及IMM-ISOMAP算法在Swiss-rollwith5parts数据集上分解子流形精度的变化以及所消耗时间的变化。

表1 比较三组数据分解子流形的精度(均值 标准差，后面括号中为最高精度)和平均运算时间(s)

Fig.1 Comparison of ISOMAP,D-C,DC-ISOMAP and algorithm IMM-ISOMAP on the embedded results of Swiss-roll block dataset图1 ISOMAP、D-C方法、DC-ISOMAP与算法IMM-ISOMAP对Swiss-roll分块数据的嵌入结果的比较

Fig.2 Comparison between ISOMAP,D-C,DC-ISOMAP and algorithm IMM-ISOMAP on the accuracy and consumption time of sub-manifolds on the Swiss-roll block dataset图2 ISOMAP、D-C、DC-ISOMAP与算法IMM-ISOMAP在Swiss-roll分块数据上分解子流形精度与消耗时间的比较

结果显示:(1)从图2中分解精度的比较可以看出,相较于其他算法,ISOMAP算法的分解精度是最低的,这是由于ISOMAP算法并不考虑子流形之间的位置关系,使得新子流形的低维嵌入相互重叠,如图1所示。因此ISOMAP算法实际上无法有效的分解子流形;(2)D-C方法主要用来分解多聚类流形,但是当多聚类流形中出现折叠扭曲、易于发生“短路”的情况时,该方法就不太适用。而且根据图1中实验结果来看,随着多流形数据的不断增加,该算法并不能很好的处理子流形之间的融合。而且由于没有考虑各子流形间的位置关系,使得最终的低维嵌入并不能很好地展现出数据本身的流形拓扑结构;(3)从图2分解精度的比较可以看出,D-C方法相较于其他算法,随着多流形数据的增加,其分解子流形的精度有一定的提高,但这种精度的提高是建立在消耗大量时间的代价上的,因此并不适合大规模数据环境。而且从图2可以看出随着多流形数据的增加,D-C方法的分解精度在降低;(4)DC-ISOMAP与IMM-ISOMAP算法都能通过各自的方法计算出各子流形之间的全局相对位置并得到各子流形的低维嵌入。图1 显示随着多流形数据的增加,这两种算法都可以得到很好的可视化结果,不仅展现出等维独立多流形数据本身的拓扑结构,而且很好地处理了子流形间的融合情况;(5)从图2中分解精度的比较可以看出IMM-ISOMAP算法的分解精度始终稍低于DC-ISOMAP算法,这是由于IMM-ISOMAP算法在处理新增数据的时候,并不是在全部数据集上重新构建近邻图,因此造成了精度上的损失;(6)从图2中消耗时间的比较可以看出,ISOMAP算法、D-C方法、DC-ISOMAP算法由于不具有增量能力,随着多流形数据的不断增加,其消耗的时间会大幅增加。其中DC-ISOMAP算法由于计算复杂度最高,其消耗的时间最高。而IMM-ISOMAP算法在多流形数据线性增加的情况下,其消耗的时间基本保持不变。也就是说IMM-ISOMAP算法比DC-ISOMAP算法有更高的效率,更适用于大规模数据。

此实验证明了IMM-ISOMAP算法在多流形增量数据集上,随着多流形数据的不断增加,不仅能够准确分解子流形,而且相较于其他算法消耗的时间更少,大大提高了算法的效率,验证了算法在增量数据上的可行性。

3.3 实际人脸数据上的增量实验

从UMist数据上剪裁来的UMist-Cropped人脸数据,每张图片像素为112×92,因此每个图像可以认为是112×92维的高维空间中的一个点。由于实验环境的限制,从UMist-Cropped数据中仅选出其中的8组人脸数据作为实验数据,图3分别显示了ISOMAP、D-C、DC-ISOMAP及IMM-ISOMAP算法在UMist-Cropped数据集上运行的可视化实验结果。图4显示了随着多流形数据的不断增加,ISOMAP、D-C、DC-ISOMAP及IMM-ISOMAP算法在UMist-Cropped数据集上分解子流形精度的变化以及所消耗时间的变化。

Fig.3 Comparison of ISOMAP, D-C , DC-ISOMAP and IMM-ISOMAP algorithm for low dimensional embedding of UMist_Cropped data with incremental variation图3 ISOMAP、D-C、DC-ISOMAP与算法IMM-ISOMAP对增量变化的UMist_Cropped数据的低维嵌入结果比较

Fig.4 Comparison of ISOMAP,D-C,DC-ISOMAP and algorithm IMM-ISOMAP in incremental variation of UMist_Cropped data on the accuracy of the sub-manifold and consumption time图4 ISOMAP、D-C方法、DC-ISOMAP与算法IMM-ISOMAP在增量变化的UMist_Cropped数据上分解子流形精度与消耗时间的比较

结果显示:(1)从图3分解结果看出ISOMAP算法并不能将8组人脸数据准确地分解成8个单一人脸的子流形拓扑结构,只能得到一个简单的无实际意义的低维嵌入。从图4中分解精度的比较中也可以看出ISOMAP算法的分解精度最低;(2)D-C方法在该数据集上的分解结果与其参数有关,实验表明在参数较大时候,分解效果反而不好。图3的可视化结果是在参数最小即k=3的情况下得到的,结果显示其中仍有部分人脸的数据没有分解开。而且D-C方法分解得到的子流形大量聚集在中心部分,相互交叉折叠严重,其可视化效果并不好。(3)从图4中分解精度的比较也可以看出,随着多流形数据的增加,D-C方法的精度会慢慢降低。从图4中消耗时间的比较也可以看出,D-C方法消耗的时间要少于DC-ISOMAP算法,这是由于D-C方法是基于K-NN构建近邻图,因此其计算复杂度要小于基于动态邻域构建近邻图的DC-ISOMAP算法;(4)图3显示DC-ISOMAP算法与IMM-ISOMAP算法都能够将人脸数据集准确地分解成8个相互独立的子流形,各个子流形用不同的颜色与线型加以区分,可以看出其分解效果要明显优于ISOMAP算法与D-C方法;(5)从图4中分解精度的比较可以看出DC-ISOMAP算法的分解精度要高于IMM-ISOMAP算法,这是由于IMM-ISOMAP算法在处理新数据时,并不在全部数据集上重新计算近邻关系,造成了精度上的些微损失,但是这样大大提高了IMM-ISOMAP算法的效率。从图4中消耗时间的比较中可以很明显地看出DC-ISOMAP算法在多流形数据线性增加的时候,其消耗的时间几乎呈指数级增加。如此高的计算成本,很难满足目前大规模数据的计算需求;(6)从图4中消耗时间的比较可以看出IMM-ISOMAP算法在多流形数据不断增加的情况下,消耗的时间基本不变。

此实验进一步证明IMM-ISOMAP算法在实际数据的情况下,随着多流形数据的不断增加,仍能够准确分解的子流形,而且相较于其他算法消耗的时间更少。也就是说IMM-ISOMAP算法具有更高的效率,可以更好地应用于大规模数据环境，验证了算法在实际增量数据上的可行性。

4 结论

本文针对等维独立多流形提出了增量学习算法IMM-ISOMAP。该算法首先对新样本计算动态邻域,通过扩展切空间的方法将新样本依次划分到各子流形,实现对新样本的分类并计算最终的低维嵌入。

实验结果表明IMM-ISOMAP算法在人造数据集与实际数据集上均验证了其算法的有效性。相较于其他多流形识别方法,IMM-ISOMAP算法对于等维独立多流形数据能保证一个较高的分解精度。相较于目前一些针对经典流形学习算法提出的增量算法,IMM-ISOMAP算法可以有效处理等维独立多流形数据。该算法的增量学习能力,使得算法的时间复杂度大大降低,未来可以很好的应用于大数据环境。但是IMM-ISOMAP算法目前仍有一点不足在于对相交多流形数据的处理,其效果并不理想。该算法将继续改进,以致最终能够实现准确分解相交多流形数据、非线性维数约简及其增量学习算法。

[1]TenenbaumJB,DeSV,LangfordJC.AGlobalGeometricFrameworkforNonlinearDimensionalityReduction[J].Science,2000,290(5500):2319-2323.DOI:10.1126/science.290.5500.2319.

[2]RoweisST,SaulLK.NonlinearDimensionalityReductionbyLocallyLinearEmbedding[J].Science,2000,290(5500):2323-6.

[3]GaoX,LiangJ.AnImprovedIncrementalNonlinearDimensionalityReductionforIsometricDataEmbedding[J].Information Processing Letters,2015,115(4):492-501.DOI:http:∥dx.doi.org/10.1016/j.ipl.2014.12.004.

[4]MengD,LeungY,FungT,et al.NonlinearDimensionalityReductionofDataLyingontheMulticlusterManifold[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society,2008,38(4):1111-1122.DOI:10.1109/TSMCB.2008.925663.

[5]WangY,JiangY,WuY,et al.SpectralClusteringonMultipleManifolds[J].IEEE Transactions on Neural Networks,2011,22(7):1149-1161.DOI:10.1109/TNN.2011.2147798.

[6]WangY,JiangY,WuY,et al.LocalandStructuralConsistencyforMulti-manifoldClustering[C]∥InternationalJointConferenceonArtificialIntelligence.AAAIPress, 2011:1559-1564.DOI: 10.5591/978-1-57735-516-8/IJCAI11-262.

[7]AllabK,LabiodL,NadifM.Multi-ManifoldMatrixTri-FactorizationforTextDataClustering[M]∥NeuralInformationProcessing,2015.DOI:10.1007/978-3-319-26532-2-78.

[8]CaiW.AManifoldLearningFrameworkforBothClusteringandClassification[J].Knowledge-Based Systems,2015,89(C):641-653.DOI:10.1016/j.knosys.2015.09.010.

[9]SouvenirR,PlessR.ManifoldClustering[C]∥TenthIEEEInternationalConferenceonComputerVision.IEEEComputerSociety,2005:648-653Vol. 1.DOI:10.1109/ICCV.2005.149.

[10]BabaeianA,BabaeeM,BayestehtashkA,et al.NonlinearSubspaceClusteringusingCurvatureConstrainedDistances☆[J].Pattern Recognition Letters,2015,68:118-125.http:∥dx.doi.org/10.1016/j.patrec.2015.09.001.

[11] 高小方,梁吉业.基于等维度独立多流形的DC-ISOMAP算法[J].计算机研究与发展,2013，50(8):1690-1699.

[12]FanM,ZhangX,QiaoH,et al.EfficientIsometricMulti-manifoldLearningbasedontheSelf-organizingMethod[J].Information Sciences,2016,345(C):325-339.DOI:10.1016/j.ins.2016.01.069.

[13]GaoX,LiangJ.TheDynamicalNeighborhoodSelectionbasedontheSamplingDensityandManifoldCurvatureforIsometricDataEmbedding[J].Pattern Recognition Letters,2011,32(2):202-209.DOI:10.1016/j.patrec.2010.08.005.

[14]KouroptevaO,OkunO,PietikäinenM.IncrementalLocallyLinearEmbeddingAlgorithm[J].Pattern Recognition,2005,38(10):1764-1767.DOI:10.1007/11499145-53.

[15]LawMHC,JainAK.IncrementalNonlinearDimensionalityReductionbyManifoldLearning[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2006,28(3):377-391.DOI:10.1109/TPAMI.2006.56.

[16]JiaPeng,YinJunsong.IncrementalLaplacianEigemapsbyPreservingAdjacentInformationbetweenDataPoints[J].Pattern Recognition Letters,2009,30:1457-1463.

[17]LiuX,YinJ,FengZ,et al.IncrementalManifoldLearningViaTangentSpaceAlignment[J].Lecture Notes in Computer Science,2006,4087:107-121.DOI:10.1007/11829898-10.

[18]LiH,JiangH,BarrioR,et al.IncrementalManifoldLearningbySpectralEmbeddingMethods[J].Pattern Recognition Letters,2011,32(10):1447-1455.DOI:10.1016/j.patrec.2011.04.004.

[19]ZhaoD,YangL.IncrementalIsometricEmbeddingofHigh-DimensionalDataUsingConnectedNeighborhoodGraphs[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2008,31(1):86-98.DOI:10.1109/TPAMI.2008.34.

[20]YangL,WangX.OnlineAppearanceManifoldLearningforVideoClassificationandClustering[M].ComputationalScienceandItsApplications2016.SpringerInternationalPublishing,2016.DOI:10.1007/978-3-319-42108-7-43.10.

Incremental Learning Algorithm IMM-ISOMAP for Well-separated Multi-manifolds with Same Intrinsic Dimension

GAO Xiaofang,LIU Jiefei

(School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China)

Manifold learning is an important research issne in the fields of machine learning and data mining. The classical algorithms always assume that the high dimensional batched data exist in a single manifold, and can not effectively deal with the high dimensional multi-manifold data.We propose an incremental learning algorithm IMM-ISOMAP for equal dimension independent multi-manifolds.The algorithm computes the dynamic neighborhood of the new sample, and then divides the new samples into sub-manifolds by extending the tangent space.Finally it realizes the classification of the new samples and calculates the final low dimensional embedding.The experimental results show that the proposed algorithm can be effectively applied to artificial data and real image data.

manifold learning;incremental learning;equal dimension independent multi-manifolds;dynamic neighborhood;tangent space;IMM-ISOMAP

10.13451/j.cnki.shanxi.univ(nat.sci.).2017.02.008

2016-10-09；

2016-11-28

国家自然科学基金(61303091；61201453)；高等学校博士学科点专向科研基金(20131401120004)；山西省回国留学人员科研资助项目(2016-002)；山西省自然科学基金(2015021091)；山西省基础研究计划项目(2014021022-2)；山西省高校科技创新项目(2015108；2015109)

高小方(1978-),女,山西安泽人,博士,副教授,主要研究方向:数据挖掘与机器学习,E-mail:gxfhtp@sxu.edu.cn

TP181

A

0253-2395(2017)02-0234-10