基于集成的流形学习可视化_詹德川.pdf

计算机研究与发展ISSN 100021239 CN 1121777 TP Journal of Computer Research and Development42 9 1533 1537 2005 收稿日期 2005 06 14 基金项目 国家杰出青年科学基金项目 60325207 教育部优秀青年教师基金项目 霍英东基金项目 91067 基于集成的流形学习可视化 詹德川 周志华 南京大学软件新技术国家重点实验室 南京 210093 zhandc lamda1nju1edu1 cn Ensemble2Based Manifold Learning for Visualization Zhan Dechuan and Zhou Zhihua National Laboratory for Novel Sof tware Technology Nanjing University Nanjing210093 Abstract Manifold learning is helpful to the discovery of the intrinsic distribution and geometry structure of data1Current manifold learning algorithms are usually sensitive to noise and input parameters1The ap2 pearance of noise and the change of input parameters usually produce significantly different learning results1 In this paper a new method is proposed based on the manifold learning algorithm Isomap through introduc2 ing ensemble learning technique which enlarges the value range that the input parameters can take to gen2 erate good visualization effect and reduces the sensitivity to noise1 Key words machine learning manifold learning ensemble learning visualization 摘 要 流形学习有助于发现数据的内在分布和几何结构1 目前已有的流形学习算法对噪音和算法参 数都比较敏感 噪音使得输入参数更加难以选择 参数较小的变化会导致差异显著的学习结果1 针对I2 somap这一流形学习算法 提出了一种新方法 通过引入集成学习技术 扩大了可以产生有效可视化结 果的输入参数范围 并且降低了对噪音的敏感性1 关键词 机器学习 流形学习 集成学习 可视化 中图法分类号 TP181 1 引 言 常用的降维方法主要有主成分分析 PCA 多 维尺度变换 MDS 和判别分析 MDA 等 1 1 最近 流形学习方法如等度规映射 Isomap 2 3 局部线 性嵌套 LLE 4 拉普拉斯特征映射 Laplacian eigenmaps 5 6 核主成分分析 KPCA 7 等非线性 降维方法受到了机器学习界的重视 并在一些问题 上取得了较好的效果1 然而 几乎目前所有的流形 学习算法都对数据中存在的噪音敏感 噪音的出现 导致参数设置困难 会极大地影响流形学习的效果1 本文将集成学习 8 引入流形学习中 扩大了可以产 生有效可视化结果的输入参数范围 并且降低了对 噪音的敏感性1 本文第2节介绍流形学习算法Isomap 第3节 阐述流形学习进行可视化时可能出现的问题 第4 节介绍集成学习 并提出基于集成学习的ensemble2 Isomap算法 第5节给出实验结果 最后是结束语1 2 Isomap算法 由于流形局部上的一条路径的长度可以用欧氏 空间中的度量表示1 对于样本空间中的任意两点 它们之间的距离用它们的测地线 geodesic 距离度 量 而该距离度量的近似值可以使用最短路径算法 通过局部的邻域中欧氏距离来重构获得1 如图1所 示1 图 1 a 中的样本分布于一个Swiss2roll上 虚线 所表示的两点间的欧氏距离 虚线 不能表征两点间 的真实距离 而分布于流形面上的曲线是这两点的 测地线 在流形未知的情况下无法求得 可以通过最 短路径算法对邻域内的距离进行拼接近似地去重构 两点间的测地线距离 如图 1 b 中曲线所示1 图1 c 是使用Isomap降维后空间中两点和两条路径 分别对应测地线距离和短程距离拼接 的投影1 Fig11 Basic idea of Isomap 3 1 a Swiss2roll b Geodesic and c Low2dim1 图1 Isomap的基本思想 3 1 a 高维样本分布 b 测地线 c 低维投影 该算法首先找出每个样本的邻域 保留邻域内 样本之间的距离 邻域外样本到该样本不连通 然后 使用Dijkstra算法重构任意两个样本之间的距离矩 阵 最后对样本间的两两距离作为标准MDS的输 入 从而得到数据的低维映射1 Fig12 Isomap is unstable 8 1 a Swiss2roll with noise and b Result of Isomap1 图2 Isomap不稳定 8 1 a 带噪音样本 b Isomap算法结果 3 流形学习可视化的问题 Balasubramanian等人 8 指出 对于有噪音数据 I2 somap算法用于可视化时不稳定 取较大的邻域会产 生短路现象 short2circuit 如图 2 a 是受噪音干扰的 Swiss2roll 图 2 b 是使用Isomap进行投影以后的结 果1可以看出 由于噪音的引入干扰了邻域的选取 从 而导致Isomap出现不稳定 可视化的效果受到了很 大的影响 例如圈出的不同颜色深浅点混杂的区域 1 如果为了追求整体结构不发生变化 而选取较小的邻 域就会大量的出现图 1 c 中椭圆的圈标出的 空洞 或使最短路径算法重构的图不连通1 Tenenbaum等人 8 随后指出 如果能适当选取 邻域 就可以最大限度地使得算法稳定1 选取不同 的邻域会产生不同的残差 variance fraction 1 这里 的残差定义为12correlation DM DY 其中DY是 降维后样本之间的距离矩阵 DM是Dijkstra算法对 测地线距离估计得到的重构距离矩阵1correlation x y 是x y之间的相关系数1T enenbaum等人 8 提出使用两个约束来选取合适的邻域 在下文中称 这种方法为Opt2Isomap1 第1个约束是最大连通分 支中的样本数占样本总数的比例尽可能大 这一约 束会使绝大部分样本出现在同一个连通区域中 从 而可以抑制不连通区域的出现 第2个约束是残差 尽可能小 直观上来说 当出现短路现象时残差会比 较大 因此这一约束会抑制短路现象的出现1 然而 残差描述的是进行MDS过程中信息的不一致性1 虽然噪音会干扰MDS过程 但是噪音更大程度上 影响了邻域的选取 进而会影响到距离重构过程1 也就是如果只比较DY和DM并不能完全地展示噪 音的影响1 因此残差描述的其实只是MDS而不是 整个Isomap学习过程中信息的不一致性 所以使用 此约束未必能奏效1 4 Ensemble2Isomap算法 集成学习 7 使用多个学习器来解决问题 可以 取得比单一学习器更好的性能1 该技术不仅在预测 型学习中被广泛应用1 本文将集成学习的思想引入 流形学习 提出了Ensemble2Isomap算法 可以在一 定程度上减轻由于邻域选取不当而造成的可视化性 能不稳定性1 Ensemble2Isomap采用k近邻选取邻域1I2 somap在使用k近邻进行邻域选取时 可视化效果 稳定的k值往往集中于一个小的区间范围内 所以 在使用Isomap时事实上是在一个小的区间内随机 选取一个值 作为合理k值 对于Opt2Isomap 是在 一个可能使得算法产生稳定输出的区间内 随机选 取一个值作为起始点 然后基于残差最小化进行寻 优1Ensemble2Isomap和Isomap以及Opt2Isomap相 似 算法的输入是需要降维的数据X 数据X的本 真维数和邻域选取参数1 不同的是Ensemble2Isomap 的邻域参数是用户给出的一个合理区间K和一个 属于该区间的用户信任的邻域大小k 1 在给出区间 内的某些值是Isomap的合适参数 但是由于缺少足 够的先验知识去获取合适的参数值 Isomap在这样 的区间上随机选取参数往往表现不好 而Esemble2 4351计算机研究与发展 2005 42 9 Isomap缓解了Isomap对参数的敏感程度 只要在 邻域区间K内 k 附近存在对于Isomap较合理的 k值 Ensemble2Isomap往往就可以返回可视化效果 较好的结果1Ensemble2Isomap首先以k 为均值 以 1为方差做正态分布 倘若该分布拖尾超出输入的 区间K 则截取在区间内的部分1 然后 以该分布随 机选取n个k值 当n较大时 选取的k值很容易 重复 重复的次数作为权值累计在相应的k值上1 这样 显然k 附近的权值较大 这体现了用户对k 有较高的信任程度1 如果用户没有任何先验知识 则算法在区间内随机选取k 1 使用选取的不同k 值分别执行Isomap算法 这样 每次执行Isomap就 会得到样本在降维后的一个坐标 最后将这些坐标 加权平均就得到了最终结果1 图3给出Ensemble2I2 somap的算法描述 输入 输入样本X 样本本真维数d 邻域参数取值区间K 邻域参 数k 输出 降维后样本Y1 算法 如果k 没有给出 k rand K 3 生成区间内的一个随机 数 3 构造以k 为中心 以1为方差的正态分布F 截取F在K以 内的部分F 以F 分布随机选取n个邻域参数k1 k2 kn 对k1 k2 kn统计出不同的k值uk1 uk2 ukm 将它们出现的频 率作为权值w1 w2 wm Forj 1 tom Y ii Isomap X d ukj End Y m i 1 wiY i1 Fig13 Ensemble2Isomap1 图3 Ensemble2Isomap的算法 5 实验测试 511 实验设置 在真实数据集上 样本的内在分布通常难以取 得 从而难以获得样本在流形上的真实投影 所以本 文实验是在数据本真结构已知的数据集上进行的1 设空间中样本X x1 x2 xn RN Y y1 y2 yn Rd 是X经过Isomap降维后的样本 Z z1 z2 zn R d 是 X在其真实流形上的投 影 其中d N1 可以使用correlation DY DZ 来 评价Isomap的可视化效果 其中DY是Y中样本间 的距离 DZ是Z中样本之间的距离 但是这种方法 侧重投影后样本的距离信息1 由于流形学习算法寻 求样本在流形上投影的结构 并且成功的非线性降 维应该保持Y和Z中相应点的位置不变 所以文中 采取了一种新的评价方法 坐标相关性 coords2cor2 relation 直接使用correlation Y Z 来衡量可视化 效果 这样不仅仅能关注投影后样本间的距离信息 同时考虑了样本投影后的位置信息1 相关性越高流 形学习的可视化效果越好1 Fig14 Scurve and Cup1 a Scurve and b Cup1 图4 Scurve和手旋杯1 a S 形分布数据 b 手旋杯数据 本文使用了人工数据和手旋杯数据1 人工数据 是在二维平面上采样的1000个样本 经过扭曲嵌入 到3维空间分别成S曲面 S 2curve 如图4 a 和 Swiss2 roll 如图 1 a 和图2 a 然后分别加上不同 程度的噪音得到 一共6个数据集1 它们分别为 Scurve Scurven1 Scurven2 Scurven3 Swissn1和 Swissn2 其样本数目均为1000个 样本维度为3 维1对于同一系列人工数据 其噪音程度逐渐增大1 人造数据集具体情况如下 Scurve为无噪音数据 如图 4 a 所示 Scurve在x y z三个方向上的大 小分别为20 40 50 Scurven1是在Scurve的基础 上添加了各向同性 标准差为015的高斯噪音 Scurven2在Scurve的基础上添加了标准差为1的 噪音 Scurven3的噪音更大 在Scurve上添加了标 准差为115的高斯噪音 对于Swissn1和Swissn2 是在3个方向上大小分别为25 20 20的无噪音的 Swiss2roll上添加噪音得到 其噪音程度 标准差 分别为015和11 手旋杯数据由481张480 512像 素的图像构成1 手旋杯部分样本图像如图 4 b 所 示 它是真实数据集本身含有噪音1 手旋杯在0到 上进行旋转时只存在角度一个自由度 因此可以使 用Isomap将其投影至1维空间 直线 并且能保持 有序 即每张图中旋转的角度和它们在直线上投影 的坐标有着近似线性的关系1 本文实验中在进行流 形学习降维之前 已经将它们的大小放缩至240 256个像素 然后通过PCA将其降维至50维 再使 用Isomap进行投影 参数k在5 20之间选取 小 于5则出现不连通现象 本真维数为1 发现PCA 处理后的样本进行降维后手旋杯数据仍然基本保持 有序地分布于直线上 所以实验中作为输入的手旋 杯数据集是经过PCA降维后的 其维数是50维1 对 5351詹德川等 基于集成的流形学习可视化 于人造的6个数据集由于它们和二维平面上的点一 一对应 它们自然分布于一个二维流形面上1 本文 实验将Ensemble2Isomap和Opt2Isomap以及标准I2 somap进行了比较1 对于Ensemble2Isomap其邻域参数 K为 3 20 一共选出10个k值用于集成 n 10 1 Opt2Isomap的初始k值和Isomap的k值均在 3 20 内随机选取1 为了能够比较3种算法 Ensemble2I2 somap的k 也不加指定1 如果Isomap出现不连通现象 则输出坐标相关性为零1 512 实验结果 实验中记录了这3种算法分别相应于511中阐 述的坐标相关性 coords2correlation 和它们所花费 的时间 用于比较3种算法的性能1 为了得到这些 数据可靠的统计值 将分别使用这3种方法获得在 不同数据集上的3组相关性和3组时间称为一轮实 验获得的数据 一共进行了5000轮实验 然后分别 求得相关性的均值和标准差以及消耗时间的均值 如表1所示1 从表1中可以看出 Ensemble2Isomap 和Opt2Isomap在坐标相关性上都优于Isomap 而En2 semble2Isomap和Opt2Isomap的效果相当 在Scur2 ven2 3 Swissn1 2和旋转杯数据集上 Ensemble2I2 somap略优于Opt2Isomap1 虽然在Scurve和Scur2 ven1上Opt2Isomap优于Ensemble2Isomap 但是这 两个数据集上没有噪音或者噪音较小 并且在区间 3 20 上残差和坐标相关性都是单调的 最优的k 都在20左右取得 实验中也记录了各方法消耗的时 间 Opt2Isomap在这两个数据集上的时间消耗大约 是9 10倍于Isomap 这是因为此时寻优迭代步数的 期望值是101 尽管Opt2Isomap可以得到一定意义下 的最优 Ensemble2Isomap的表现也仅仅是略微差1 在Scurven2 Swissn1和旋转杯数据集上 Ensem2 ble2Isomap的标准差最低 说明在这几个数据集上 Ensemble2Isomap比其他两个方法稳定1 同样是因 为在Scurve和Scurven1上残差是单调的 几乎每 次Opt2Isomap都收敛于k 20 所以在这两个数据 集上Opt2Isomap的标准差最小 几乎为零1 在其他 数据上Opt2Isomap就可能每次陷入不同的局部最 优 从而导致标准差变大 效果也会降低 如图5所 示Isomap在不同k值下获得的残差和坐标相关性1 图中横坐标是k的取值 纵坐标为残差图 a 或坐标 相关性图 b Isomap在k 3时出现不连通 所以 在图中k从4开始有对应值1 图 5 a 中 残差存在 多个极小值 Opt2Isomap很容易陷入局部最小值1 在图5中同时反映了坐标相关性和对应的残差差异 很大1 另外如图 5 b 所示 Isomap如果想获取和 Ensemble2Isomap相近的效果 只能在 10 16 或者 18 20 上取值1 而Ensemble2Isomap的可视化效果 十分稳定 坐标相关性的标准差仅为010091 所以 Ensemble2Isomap的k 可以在 3 20 上任意取值 均可以获得较好的结果1 Fig15 Variance fraction and coords2correlation on Scruven21 a Variance fraction and b Coords2correlation1 图5 Isomap在Scurven2上的残差和坐标相关性1 a 残差 b 坐标 Table 2 Coords2Correlations 表2 三种方法的坐标相关性 mean std1 Algorithm DataScurveScurven1Scurven2Scurven3Swissn1Swissn2Cup Isomap01808 0114101762 0123501793 0113801798 0114101680 0124201544 0116801786 01388 Opt2Isomap01833 1e21301834 0100001816 0101301825 0100601792 0110401613 0112901977 01002 Ensemble2Isomap01832 1e20501834 0100101818 0100901826 0100601810 0106901648 0113901977 01002 6351计算机研究与发展 2005 42 9 6 结束语 本文使用集成学习思想来解决流形学习算法I2 somap效果对噪音敏感以及由于噪音导致的选取邻 域参数困难的问题 并且提出使用坐标相关性来度 量流形学习可视化效果1 研究结果表明 Ensemble2 Isomap比Isomap的参数鲁棒性好 比Opt2Isomap 的抗噪性好 而且其时间复杂度不明显高于Opt2I2 somap1 值得注意的是 坐标相关性只能用于度量本 真结构已知的数据集上的可视化效果 对本真结构 未知的数据 如何有效度量流形学习可视化的效果 仍然是一个需要进一步研究的问题1 参考文献 1R1O1Duda P1E1Hart D1G1Stork1Pattern Classification1 New York John Wiley Sons 2001 2V1D1Silva J1B1Tenenbaum1Global versus local methods in nonlinear dimensionality reduction1In Advances of Neural Infor2 mation Proceeding Systems 151Cambridge MA MIT Press 20021705 712 3J1B1Tenenbaum V1de Silva J1C1Langford1A global geo2 metric framework for nonlinear dimensionality reduction1Science 2000 90 5500 2319 2323 4S1T1Roweis K1S1Lawrance1Nonlinear dimensionality reduc2 tion by locally linear embedding1Science 2000 290 5500 2323 2326 5M1Belkin P1Niyogi1Laplacian eigenmaps for dimensionality re2 duction and data representation1Neural Computation 2001 151 6 1373 1396 6V1N1Vapnik1Statistical Learning Theory1New York John Wiley Sons 1998 7T1G1Dietterich1Ensemble learning1In The Handbook of Brain Theory and Neural Networks 2nd Edition1Cambridge MA MIT Press 2002 8M1Balasubramanian E1L1Schwartz J1B1Tenenbaum1The Isomap algorithm and topological stability1Science 2002 295 4 7a Zhan Dechuan born in 19821Master candi2 date at the Department of Computer Science Technology Nanjing University1His re2 search interests are manifold learning and machine learning1 詹德川 1982年生 硕士研究生 主要研究 方向为机器学习 数据挖掘1 Zhou Zhihua born in 19731Professor and Ph1D1supervisor at the Department of Computer Science Technology Nanjing University1His main research interests in2 clude machine learning data mining pat2 tern recognition information retrieval neu2 ral computi