学位论文 > 优秀研究生学位论文题录展示

网络数据降维与Kirchhoff电阻

作　者: 韩濛
导　师: 白峰杉
学　校: 清华大学
专　业: 数学
关键词: 数据降维流形学习 Kirchhoff电阻距离 Isomap改进算法
分类号: TP301.6
类　型: 硕士论文
年　份: 2013年
下　载: 11次
引　用: 0次
阅　读: 论文下载

内容摘要

为了应对大规模高维数据带来的“维数灾难”，通过寻求数据的本征维度或本征结构，将高维数据映射到低维空间的降维方法已经成为现今处理大规模高维数据的主要方法。已有的降维方法包括MDS、Isomap、LLE等，在其各自适用的数据结构中有着很好的应用，但都存在各自的局限性，并没有一种降维方法能够适用于所有高维数据结构。特别地，在流形学习领域，大多数降维算法对于有洞的流形数据都无能为力。本文提出了一种Isomap的改进算法，即将数据集所对应的赋权图看作一张纯电阻网络，通过计算出任意两个节点间的有效电阻得到相应的电阻距离矩阵，用两点间电阻距离对其最短路距离做修正。电阻距离可以通过简单的代数运算获取，但它与目标流形的几何性质以及拓扑性质相结合，在一定范围内能够更深刻的反映图中顶点之间真正的距离关系，所以用电阻距离修正测地线距离能在降维过程中保留更多的流形或数据信息。本文的算法基于传统的Isomap降维方法，应用电阻距离并选择合适的修正函数对测地线距离进行修正，不仅能够处理常规的流形降维，对于有洞或是变异的流形也有较好的降维效果。本改进方法主要依赖以下三个参数，分别是在构建邻接图过程中选择邻域点的个数n，电阻距离矩阵R对最短路距离矩阵D_s的修正函数Func(R,D_s)中，修正函数值与两点间最短路距离相差的峰值参数peak，以及电阻距离矩阵R对最短路距离矩阵D_s的影响范围大小参数var。经Matlab数值试验证明：在选择好合适的峰值参数peak，以及R对最短路距离矩阵D_s的影响范围大小参数var之后，可以在一定程度上降低算法对在构建邻接图过程中选择邻域点的个数参数n的敏感依赖程度。通过对算法的复杂度分析，本文发现如果只调整峰值参数peak以及范围参数var，可以避免对图上最短路距离的重复计算，而这恰恰是算法中计算成本最大的一部分，从而本改进Isomap算法有效减小了算法在调节参数过程中付出的代价。在数值模拟试验部分，本文将改进算法与传统Isomap的降维结果进行了比较，结果显示应用电阻距离修正的Isomap算法针对一些变异流形的降维确实取得了更好的降维效果。

全文目录

摘要  3-4
Abstract  4-7
第1章引言  7-12
  1.1 降维基本问题  7-8
  1.2 基本概念和记号  8-9
  1.3 问题的研究背景及意义  9-10
  1.4 本文的主要内容  10-12
第2章研究领域综述  12-22
  2.1 降维方法综述  12-17
    2.1.1 线性降维方法  13-14
    2.1.2 非线性降维方法  14-15
    2.1.3 算法适用领域、局限性以及算法复杂度分析  15-17
      2.1.3.1 降维算法使用领域及局限性分析  15-16
      2.1.3.2 降维算法复杂度比较分析  16-17
  2.2 Kirchhoff 电阻距离的计算公式  17-22
第3章改进的 Isomap 算法  22-26
  3.1 模型的构建  22
  3.2 算法描述  22-25
  3.3 算法复杂性分析  25-26
第4章算法实现  26-39
  4.1 一些三维流形的降维结果  26-33
  4.2 算法参数比较  33-36
  4.3 算法复杂度分析  36-39
第5章与 Isomap 降维结果比较  39-44
  5.1 变异的 Swiss Roll  39-41
  5.2 不同参数下进一步结果  41-44
第6章总结  44-46
参考文献  46-48
致谢  48-50
个人简历、在学期间发表的学术论文与研究成果  50

网络数据降维与Kirchhoff电阻

内容摘要

全文目录

相似论文