论文研究-面向等维独立多流形的增量学习算法IMM-ISOMAP .pdf

所需积分/C币:9 2019-08-16 12:07:13 676KB .PDF
50
收藏 收藏
举报

面向等维独立多流形的增量学习算法IMM-ISOMAP,高小方,刘杰飞,流形学习是机器学习与数据挖掘领域的一个重要研究方向。其经典算法总是假设高维数据批量存在于单一流形,且不能有效处理增量出现
山国武花论文在丝 断更新,直到 在 算法中,节点和之问的切空间偏差可以定义为: 其中σ是的最小奇异值。在迮择将要被扩展的下个节点吋,我们总是选择与当前节 点具有最小偏差的节点。即 基于动态 的 增量学习算法 在增量学习算法中,随着数据的不断积累,充分利用原始数据的计算结果,并提高大规 模数据的算法效率成为首要任务。基于动态的 增量学习算法仍然是基于单 流形的假设,在充分保留并利用原有的中间结果的同时,如邻域矩阵、测地距离矩阵、前置 矩阵,计算新增批量数据的低维嵌入。相对于经典的 算法,基于动态 的 增量学习算法增加了三个主要功能:动态、“短路”识别算法 和冲突路径判断算法 动态算法是基于的动态邻域算法。当获取新増批量数据后,在原有邻域关系 中增加新的关系,使得邻域关系包含新增近邻,但是并不删除不属于新的原 有邻域关系。也就是说,在动态邻域关系中,样木点的近邻个数大」等」,而不是 定等」。同时,为了保证在增加新样木后,动态算法能够具有与算法一样的 克服原有“短路”的能力,该增量学习算法给出了短路判断算法 该 路”判断算法主要针对“邻域切片”中增加新样本为近邻的样本。如果该新近邻到 该旧样本的其他一个旧近邻的距离大于原距离与“邻域切片”最大“半径”之和, 则判断旧样本、之间存在短路。动态算法和“短路”判淅算法保证了增量学习算法 中邻域关系的快速更新,而且尽量保证原有邻域关系避免发生变动。这是整个增量学习算法 的基础,因为每一组邻域关系的变动,都可能会引发多条测地距离的更新,但并不一定会人 幅提高整体算法的精度。所有的测地距离都是由邻域关系计算出最短路径的距离估计而得 在邻域关系中増加了新样本点后,泱地距离矩阵中的数据需要重新计算。虽然大多数被更新 的“测地距离”使得距离实际距离更“近”了一点,但并不能大幅提高整体算法的精度,而 且时间复杂度将会随着样木点的增大而大幅增加。这些需要更新的测地距离中只有以下两种 是必须的:由“短路”计算出的错误距窝、冲突路径计算出的距离。冲突路径,即从样本 到的路径信息与从到的路径信息不一致,主要由新增样本引发。基于动态的 增量学习算法中仅更新了这两种测地距离,虽然使得测地距离矩阵的计算精度在一定程度上 受到了损失,但提高了整体算法的效率 面向等维独立多流形的增量学习算法 本文提岀的面向等维独立多沇形的增量学习算法 主要实现对多流形数据 的增量学习能力并进行多流形识别和非线性维数约简。顾名思义,增量学习就是在有新增数 据情況下能够利用原冇计算结果对新増数据进行学习。不需要对整个数据集亘新计算,仅做 山国武技论文在丝 由新增数据引起的更新。整个增量学习的时间代价通常远低于重新计算整个数据集所需的代 价 在算法 中,首先通过动态邻域算法计算新增样本的动态邻域;然后找 到与原始子流形具有较小切空间偏差的新样本,并将新样本划分到对应子流形,形成新的子 流形;最后计算每个新子流形的低维嵌入,同时利用 算法中合并嵌入结果的 方法计算各个新子流形的邻近关系以确定冬新子流形的位置关系,拼接出整体数据的最终嵌 入结果。具体算法参见算法 算法1:IMM- ISOMAP算法描述 输入 …}原样本集合; {+…+}新增样本集合 },原子流形集合; },原低维嵌入;={…},原 邻域关系;={…},原切空间;G,原测地距离矩阵;P,原前置矩阵;本征维 数θ切空间偏差阈值;ξ松散系数; 输出 }新了流形;={…+}新低维嵌入;={…} 新邻域关系;={….+},新切空间;G,新测地距离矩阵;P,新前置矩阵; 1.调用动态邻域算法计算新增样本点的动态邻域 和切空间 2.利用公式()和(5)计算新増样本与整体样本集合的切空间偏差,并选择与原有样本具有最 小切空间偏差的新样本作为被扩展的初始样本 3.当有新增样本没有被扩展时 if彐 ∈ ∈ if彐 扩展的新增样木近邻 else 扩展的新增样本近邻 end if. else 选择下个被扩展的新样本点和原有样本; if不存在 在剩余所有新样本中建立新的子流形集合; end if; end if 4增量计算新样本低维嵌入 山国武花论文在丝 调用 检测中的“短路”并在、、中删险与其相关的信息; 利用 算法计算被删除的测地距离及其相关信息; 调用 更新中的冲突路径 计算各了流形的低维嵌入 5计算各了流形的邻近关系并将各了流形的拼接成={ 更新邻域关系 为了得到较准确的拓扑流形结构,邻域关系要在整体数据集上进行计算,不仅包含原数 据集,还要包含新增样本数据。由于多流形数据混杂在一起,由算法计算邻域关系时, 无法避兔不同子流形上的点邻域关系混杂在一起。因此 算法采用基于采样密 度和曲率的方法来计算动态邻域和切空间。 更新子流形的划分 整个划分的过程是从与原样本具有最小切空间偏差的新增样本开始,因为切空间偏差最 小可以保证起始样木的划分出错概率最小 当新增样本的两个或两个以上近邻(原样本)分别属于不同子流形时,说明随着样本的 增加,原来不相连的子流形拼接成一个新的子流形,即子流形相融合;当新增样本存在的近 邻仅属于同一个子流形时,将该新增样本划分到同一」流形中;否则该新样本或者因为其新 烊本近邻被扩展,或者与其他新样本构建成独立的子流形。 更新低维嵌入 基于动态的 增量学习算法在更新邻域关系时,采用了动态 在 更新测地距离矩阵时,仅更新了短路引起的错误测地距离和存在冲突路径的测地距离。 算法对每个子流形做同样处理。 针对每个子流形,如果有新增样木的加入,则邻域关系心经发生变化。由新增样木引发 的“短路”和冲突路径叮以通过 和 算法检测和修正。 如果没有新嶒样本的加入,则原计算结果无需更新。如果是新增了流形,则通过经典 算法计算。 更新最终嵌入结果 在计算出所有子流形的低维嵌入后,要利用 算法对这些嵌入结果拼接合 并。首先要选岀每个子流形的一些标准点以确定该子流形在整体数据集合中的位置关系。然 后通过 算法对这些标准点计算出最终嵌入结果的“框架”。最后利用这些标准点 将各个了流形坐标转化,“嵌”入最终嵌入结果中 时间复杂度分析 假定原样本集合有个数据,新样本集合有个数据。基于经典的 算法提出 算法,首先需要在原样本与新样本的基础上通过扩展切空间分解子流形,重 新构建近邻图,再重新计算全部样本之间的新的测地距离,最后通过各子流形的低维嵌入与 外层节点信息确定子流形的位置关系并最终组合得到新的低维嵌入。因此其时间复杂度为 其中为邻域大小所 设定的参数;而 算法在计算动态邻域时只需要计算新样本的动态邻域,其时 山国武花论文在丝 问复杂度为O 。在将新样木重新划分到新子流形及处理新子流形中可能出现 的“短路”情况或冲突路径时,其时间复杂度为 +||||+||,其中为增加新节点后邻域图上所有点的最 大的度,其中|,||分别为冲突路径与“短路”路径的数量,且一般较小可忽略。最 后计算新子流形的低维嵌入时其时间复杂度为O+。故 算法整体的 时间复杂度近似为O +|++ 由于新样本集的规模 般是远远小于原样本集的规模,即<<,则 算法的时间复杂度要小于重 新运行全部数据的 算法的时间复杂度。 实验结果分析 本节分别进行了三组实验,第一组实验通过数据比较了 算法通过扩展切 间分解多流形与 等算法分解相同多沇形数据 的精度及所需的时间。第二组灾验是随着多流形数据的不断增长,可视化地展示了 算法与 和 算法得到的低维嵌入结果之间的差异 第三组实验则可视化地比较了 算法与 和 算法分 别在 人脸数据集上的结果,以及随肴多流形数捃的不断増加,运行以上算法 分解子流形的精度变化和所消耗时间的变化 分解子流形的精度及效率实验 表中的数据展示了 算法与其他算法分解多流形数据的精度以及各自所 消耗的运行时间之间的比较。表中的三组数据分别是从 裁剪后作为实验数据集,由于实验环境的限制,其中 与 数据集分别是从 人脸数据集与人脸数据集上选择部分人脸数据通 过手工剪裁来作为实验数据。由于除了 算法只有增量能力,其余算法均不只 有增量能力,因此在计算这些算法所消耗的时间时采用的是这些算法单次执行所消耗的时 表比较三组数据分解子流形的精度(均值士标准差,后面括号中为最高精度)和平均运算时间(秒) 实验结果显示:() 算法与 算法在分解精度方面 山国武花论文在丝 比其他算法明显要高,可以精确的分解廾了流形;() 算法不适用于高维非线性 数据,因此精度较低。另外精度虽然较高的 算法,却需要事先设定聚类的个数,而 且由表中数据可知 算法在处理维度较髙的数据时其运算所需时间会急剧增大,因此 也不适用于高维增量数据;() 算法不仅不需要预先设定子流形个数,而且 可以像 算法一样准确分解子流形。另外由于 算法不具备增量能力, 在处理新数据时需要将仝部数据集重新计算,浪费了人量的计算资源,使得其在运行时会消 耗大量的时间;()相比于其他不具备增量能力的算法, 算法可以在保障较 高分解精度的情况下,其运算所消耗的时间与新増杵本数据之间呈线性相关。实验结果还显 小,相对于维度史高的数据 算法消耗的时 相对更少,也就是说 算法更适用于高维数据。这也就让明了 算法有很高的效率,可以很好的应用于大规模数据。 人造数据上的增量学习实验 数据集是从 数据集中截取的五块相互之间独立的子流形 数据集。从 中随机选取个点,其中个点作为原始数据集,其 余个点分为五个子集作为新增数据集。分别运行 算法与 方法与 四种算法,随着多流形数据的不断增加,不同算法运行得到的低维嵌入 结果的可视化结果如图显示。图显示了随着多流形数据的不断增加, 及 算法在 数据集上分解了流形精度的变化 以及所消耗时间的变化。由于除了 算法具有增量能力,其余算法均不具有增 量能力,因此在计算这些算法所消耗的时间时采用的是这些算法单次执行所消耗的时间。 结果显示:()从图中分解精度的比较可以看出,相较于其他算法, 算法 的分解精度是最低的,这是由于 算法并不考虑子流形之间位置关系,使得新子流 形的低维嵌入相互重叠,如图所示。因此 算法实际上无法有效的分解子流形 ()方法主要用来分解多棗类流形,但是当多聚类流形中出现折叠扭曲、易于发生“短 路”的情况时,该方法就不太适用。而且根据图中实验结果来看,随着多流形数据的不断 增加,该算法并不能很好的处理子流形之间的融合。而且由于没有考虑各子流形间的 山国武技论文在丝 ISOMAP(n=1000) SOMAPin=1100) ISOMAP(n=1200 ISCMAP(n=1300) ISOMAP(n=1400) DCn-1000 DC(n-1100) DC(n-1200 DCn-1300) DC(n-140) 呢 20 2 DC-ISOMAP(IE1000) DC-SOMAP(n=1100) DC-ISOMAPIF12C0) DC-ISOMAP(=1300) DC-SOMAP(nE 1400) 0 100-1n0-50 5n10n IMM-ISCMAPin=1C00 m=100) MM-ISOMAP(=1100 m=100)IMM-ISoMAP(n=1200 m=100)MM-SOMAPIn=1200 m=100)MM-ISOMAF(=1400 m=100) 2 205005021005006023 C0-50 方法 与算法 对 分块数据的嵌入结果的比较 - ISOMAP IMM-SIMAP ★一 IMMv-IS-MAH 1400 g 64 The iteration of running four approaches I he iteration ot nunning four apprcach 图 方法、 与算法 在 分块数据上分解子流形精度与 消耗时间的比较 位置关系,使得最终的低维嵌入并不能很好的展现出数据本身的流形拓扑结构;()从图 分解精度的比较可以看出,方法相较于其他算法,随着多流形数据的增加,其分解子 流形的精度有一定的提高,但这种精度的提高是建立在消耗人量时间的代价上的,因此并不 适合大规模数据环境ε而且从图可以看出随着多流形数据的增加,方法的分解凊度在 山国武花论文在丝 降低;() 算法都能通过各自的方法计算出各了流形之问的 仝局相对位置并得到各子流形的低维嵌λ。图显示随着多流形数据的增加,这两种算法 都可以得到很好的可视化结果,不仅展现出等维独立多流形数据本身的拓扑结构,而且很好 的处理了子流形间的融合情况;()从图中分解精度的比较可以看出 算 法的分解精度始终稍低于 算法,这是由于 算法在处理新增数据 的时候,并不是在仝部数据集上重新构建近邻图,因此造成了精度上的损失;()从图 中消耗时间的比较可以看出, 算法、方法、 算法由于不具有增量 能力,随着多流形数据的不断増加,其消耗的时间会大幅増加。其中 算法由于 计算复杂度最高,其消耗的时间最高。而 算法在多流形数据线性增加的情况 卜,其消耗的吋间基本保持不变。也就是说 算法比 算法有更高 的效率,更适用于大规模数据。 此实验证明了 算法在多流形增量数据集上,随着多流形数据的不断增加,不 仅能够准确分解子流形,而且相较于其他算法消耗的时间更少,大大提髙了算法的效率,验 证了算法在增量数据上的可行性。 实际人脸数据上的增量实验 从数据上剪裁来的 人脸数据,每张图片像素为×,因此每 个图像可以认为是×维的高维空间中的一个点。由于实验环境的限制,从 数据中仅选出其中的组人脸数据作为实验数据,图分别显示了 及 算法在 数据集上运行的可视化实验结 果。图显示了随着多流形数据的不断增加, 及 算法在 数据集上分解子流形凊度的变化以及所消耗时间的变化。由于狳了 算法具冇增量能力,其余算法均不具冇増量能力,因此在计算这些算法所消 耗的吋间时采用的是这些算法单次执行所消耗的时间。 结果显示:()从图分解结果看出 算法并不能将组人脸数据准确地分解 成个单一人脸的子流形拓扑结构,只能得到一个简单的无实际意义的低维嵌入。从图 中分解精度的比较中也可以看出 算法的分解精度最低;()方法在该数据集 上的分解结果与其参数有关,实验表明在参数较大时候,分解效果反而不好。图的可视化 结果是在参数最小即=的情况下得到的,结果显示其中仍有部分人脸的数据没有分解开。 而且方法分解得到的子流形大量聚集在中心部分,相可交叉折叠严重,其可视化效果 并不好。()从图中分解精度的比较也可以看出,随着多流形数据的增加,方法的 精度会慢慢降低。从图中消耗时间的比较也可以看出, 方法消耗的时间要少于 算法,这是由」方法是基」构建近邻图,因此其计算复杂度要小于 基于动态邻域构建近邻图的 算法;()图显示 算法与 算法都能够将人脸数据集准确地分解成个相互独立的了沇形,各个了流形 用不同的颜色与线型加以区分,可以看出其分解效果要明显优于 算法与方法; ()从图中分解精度的比较可以看出 算法的分解精度要高于 算法,这是由于 算法在处理新数据时,并不在全部数据集上重新计算近邻关 系,造成了精度上的些微损失,但是这样大大提高了 算法的效率。从图中 山国武技论文在丝 1J 3CMAPinF170 1 1 1DC(F140 10DC=170 和 a 1dc IsUM/P(n-1-4U) de 0I 1IC"Pr-iA nt 10 m=140m= MMISUMAF MM-SUMA(n=20 m=30) lum1SoMAP(n=240 m=20) 10 方法、 与算法 付增量变化的 数据的低维 嵌入结果比较 6030 EC-ISOMAP IMAN-ISOMAN ISCMAP - DC -IMM-ISOMAP 303J 20 8005 I hc iteration of running tour approa chos The iteration of rurning four approachcs 方法 与算法 在增量变化的 数据上分解 子流形精庋与消耗酎间的比较 消耗时间的比较中可以很明显的看出 算法在多流形数据线性增加的时候,其消 耗的时间几乎呈指数级增加。如此髙的计算戊本,很难满足目前大规模数据的计算需求;( 从图中消耗时间的比较可以看出 算法在多流形薮据不断增加的情况下,消

...展开详情
试读 11P 论文研究-面向等维独立多流形的增量学习算法IMM-ISOMAP .pdf
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-面向等维独立多流形的增量学习算法IMM-ISOMAP .pdf 9积分/C币 立即下载
1/11
论文研究-面向等维独立多流形的增量学习算法IMM-ISOMAP .pdf第1页
论文研究-面向等维独立多流形的增量学习算法IMM-ISOMAP .pdf第2页
论文研究-面向等维独立多流形的增量学习算法IMM-ISOMAP .pdf第3页

试读结束, 可继续读1页

9积分/C币 立即下载