一种更具拓扑稳定性的ISOMAP算法

ISOMAP算法能否被成功运用,很大程度上依赖于邻域大小的选取是否合适.然而,如何有效地选取合适的邻域大小,目前还是一个尚未解决的难题.根据"短路"边会途经相对的低密度区域这一特点,能够有效删除邻域图中可能存在的"短路"边,提出了P-ISOMAP(pruned-ISOMAP)算法,这极大地削弱了ISOMAP算法对邻域大小的依赖程度,从而使其更具拓扑稳定性.由于避免了邻域大小难以有效选取的问题,P-ISOMAP算法能够更容易地对数据进行可视化.实验结果很好地验证了该算法的有效性.     

一种新的基于ISOMAP的数据可视化算法

作为古典MDS算法的一个非线性扩展,ISOMAP算法能较好地对嵌入在高维欧氏空间中的低维非线性流形进行可视化.然而,ISOMAP算法不但要求数据具有良好抽样且位于单一流形之上,而且还依赖于难以有效选取的邻域大小,这极大地限制了该算法的实际应用.为此提出了一种改进算法--GISOMAP,它采用MDS算法的一个变种来减弱长测地距离和"短路"边对距离保持的影响,不但能更好地对具有多聚类结构的数据进行可视化,而且对邻域大小也不再敏感,从而能更容易地得到实际应用.     

基于随机游走的流形学习与可视化

现有的全局流形学习算法都敏感于邻域大小这一难以高效选取的参数,它们都采用了基于欧氏距离的邻域图创建方法,从而使邻域图容易产生“短路”边。本文提出了一种基于随机游走模型的全局 流形学习算法(Random walk-based isometric mapping,RW-ISOMAP)。和欧氏距离相比,由随机游走模型得到的通勤时间距离是由给定两点间的所有通路以概率为权组合而成的,不但鲁棒性更高,而且还能在一定程度上度量具有非线性几何结构的数据之间的相似性。因此采用通勤时间距离来创建邻域图的RW-ISOMAP算法将不再敏感于邻域大小参数,从而可以更容易地选取邻域大小参数,同时还具有更高的鲁棒性。最后的实验结果证实了该算法的有效性。     

ISOMAP算法参数的递增式选取

ISOMAP算法能否被成功应用依赖于其唯一参数——邻域大小的选取是否合适,然而,如何高效地选取一个合适的邻域大小目前还是一个难题。当邻域大小变得不合适时,短路边将会出现在邻域图中,从而严重破坏与之相关的最短路径距离对测地距离的逼近能力。和非短路边不同,短路边的两个端点虽然在欧氏空间中相距较近,但在流形上却相距甚远。基于短路边的这一特点,采用序来近似度量一条边的两个端点在流形上的远近程度,因而能够递增式地对邻域大小进行合适的选取。和基于残差的参数选取方法不同,该方法只需递增式地运行广度优先搜索算法,而无需就每一个可能的邻域大小分别运行整个ISOMAP算法,从而具有比较高的运行效率。最终的实验结果证实了该方法的可行性。     

基于邻域距离ISOMAP算法的高光谱遥感降维算法

提出一种以邻域距离改进ISOMAP的算法(Neighborhood Distance ISOMAP,ND\|ISOMAP),该方法采用邻域距离逐步逼近流形距离来表达高维数据的流形结构。同时针对ISOMAP算法的计算复杂度高、运算时间长的特点,提出了一种基于矩阵分块和自动调图的ISOMAP算法(Block\|matrix and Auto\|color ISOMAP,BA\|ISOMAP)以提高运算速率。通过对高光谱遥感影像进行分类比较算法优劣性,基于邻域距离的ISOMAP算法较原始的ISOMAP算法降维效果有了较大的提升,最高分类精度达到97.36%,而原始的ISOMAP算法仅能达到75.01%的分类精度,而基于矩阵分块与自动调图ISOMAP与邻域距离相结合降维后精度达到89.61%,但是其计算速率得到了较大提升,为原始ISOMAP算法的近40倍。     

基于最优邻域图的等距映射流形学习算法

现有的等距映射算法对邻域参数的选择较为敏感,而且对噪声干扰缺乏足够的鲁棒性。基于平均最短路径与邻域参数的变化关系与平均最短路径梯度提出了一种构建最优邻域图的方法,基于该方法构建的邻域图几乎没有短路边;可以根据每个数据点的不同特性采用可变的邻域参数;对数据点间的测地距有更好的逼近。实验表明：算法不仅对均匀采样、无噪声干扰的数据集有更好的降维性能,而且对噪声干扰的数据集有较强的鲁棒性与拓扑稳定性。     

一种用于人脸识别的有监督核化多类多流形ISOMAP算法

在核等测距映射（kernel ISOMAP）和多类多流形ISOMAP算法的基础上,提出一种针对人脸识别任务的有监督核化多类多流形ISOMAP算法.该算法保持了kernel ISOMAP算法的泛化特性,同时又能完成分类任务,解决了ISOMAP-C在对具有高维小样本特性的人脸数据集识别时,所要调整的神经网络权值数目将随输入维度呈指数增长,且易出现过拟合现象的问题.在多种人脸数据集上的实验结果表明了该算法的有效性,且对训练样本集的大小有较好的鲁棒性.     

一种改进的有间隔流形ISOMAP算法

ISOMAP算法成功应用的潜在条件是要求数据集均匀抽样于单个的内在流形。如果数据集均匀采样于某个内在流形,但内部出现了一个间隔,ISOMAP算法可能失效。提出了G-ISOMAP(ISOMAP with a Gap)算法,该算法充分利用了数据集中的间隔特性。首先检测被间隔的子流形间最短欧氏距离对应的数据点,然后将这些数据点互相设置为邻域点,最后用ISOMAP算法找到低维嵌入结果。对G-ISOMAP与ISOMAP算法的区别与联系进行了详细的理论说明,得出ISOMAP算法是G-ISOMAP算法的一个特例,G-ISOMAP算法是ISOMAP算法扩充的结论。实验结果验证了该算法比其他常用的流形学习算法在有间隔的数据集上更有效。     

基于自组织映射的流形学习与可视化

针对自组织映射(SOM)在学习和可视化高维数据内在的低维流形结构时容易产生“拓扑缺陷”的这一问题,提出了一种新的流形学习算法--动态自组织映射(DSOM)。该算法按照数据的邻域结构逐步扩展训练数据集合,对网络进行渐进训练,以避免局部极值,克服“拓扑缺陷”问题;同时,网络规模也随之动态扩展,以降低算法的时间复杂度。实验表明,该算法能更加真实地学习和可视化高维数据内在的低维流形结构;此外,与传统的流形学习算法相比,该算法对邻域大小和噪声也更加鲁棒。所提算法的网络规模和训练数据集合都将按照数据内在的邻域结构进行同步扩展,从而能更加简洁并真实地学习和可视化高维数据内在的低维流形结构。     

任意无向加权图K点连通扩充的模拟退火算法

首先研究了任意无向不加权图情况下的极小K点连通扩充算法,在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理.最终推出了任意无向加权图K点连通最小扩充的模拟退火算法.     

Semi-supervised learning through adaptive Laplacian graph trimming

Graph-based semi-supervised learning (GSSL) attracts considerable attention in recent years. The performance of a general GSSL method relies on the quality of Laplacian weighted graph (LWR) composed of the similarity imposed on input examples. A key for constructing an effective LWR is on the proper selection of the neighborhood size K or ε on the construction of KNN graph or ε-neighbor graph on training samples, which constitutes the fundamental elements in LWR. Specifically, too large K or ε will result in “shortcut” phenomenon while too small ones cannot guarantee to represent a complete manifold structure underlying data. To this issue, this study attempts to propose a method, called adaptive Laplacian graph trimming (ALGT), to make an automatic tuning to cut improper inter-cluster shortcut edges while enhance the connection between intra-cluster samples, so as to adaptively fit a proper LWR from data. The superiority of the proposed method is substantiated by experimental results implemented on synthetic and UCI data sets.     

应用于不完整流形的ISOMAP算法

等距特征映射(ISOMAP)算法要求数据位于单一流形之上且具有良好采样,而当数据采样于一个不完整流形时,该算法将会产生“过聚类”问题。为此,提出了一种改进算法--WISOMAP,它采用多维尺度分析(MDS)算法的一个变种--WMDS来降低逼近精度相对较差的多边测地距离在MDS距离保持中的主导作用,使逼近精度相对较好的少边测地距离能够得到更好的保持,从而能在一定程度上缓解“过聚类”问题。实验结果表明WISOMAP算法能更好地对采样于不完整流形的数据进行可视化。     

MiMAG: mining coherent subgraphs in multi-layer graphs with edge labels

Detecting dense subgraphs such as cliques or quasi-cliques is an important graph mining problem. While this task is established for simple graphs, today’s applications demand the analysis of more complex graphs: In this work, we consider a frequently observed type of graph where edges represent different types of relations. These multiple edge types can also be viewed as different “layers” of a graph, which is denoted as a “multi-layer graph”. Additionally, each edge might be annotated by a label characterizing the given relation in more detail. By simultaneously exploiting all this information, the detection of more interesting subgraphs can be supported. We introduce the multi-layer coherent subgraph model, which defines clusters of vertices that are densely connected by edges with similar labels in a subset of the graph layers. We avoid redundancy in the result by selecting only the most interesting, non-redundant subgraphs for the output. Based on this model, we introduce the best-first search algorithm MiMAG. In thorough experiments, we demonstrate the strengths of MiMAG in comparison with related approaches on synthetic as well as real-world data sets.     

The inner and outer approaches to the design of recursive neural architectures

Feedforward neural network architectures work well for numerical data of fixed size, such as images. For variable size, structured data, such as sequences, d dimensional grids, trees, and other graphs, recursive architectures must be used. We distinguish two general approaches for the design of recursive architectures in deep learning, the inner and the outer approach. The inner approach uses neural networks recursively inside the data graphs, essentially to “crawl” the edges of the graphs in order to compute the final output. It requires acyclic orientations of the underlying graphs. The outer approach uses neural networks recursively outside the data graphs and regardless of their orientation. These neural networks operate orthogonally to the data graph and progressively “fold” or aggregate the input structure to produce the final output. The distinction is illustrated using several examples from the fields of natural language processing, chemoinformatics, and bioinformatics, and applied to the problem of learning from variable-size sets.     

Visual Inspection of Multivariate Graphs

Most graph visualization techniques focus on the structure of graphs and do not offer support for dealing with node attributes and edge labels. To enable users to detect relations and patterns in terms of data associated with nodes and edges, we present a technique where this data plays a more central role. Nodes and edges are clustered based on associated data. Via direct manipulation users can interactively inspect and query the graph. Questions that can be answered include, “which edge types are activated by specific node attributes?” and, “how and from where can I reach specific types of nodes?” To validate our approach we contrast it with current practice. We also provide several examples where our method was used to study transition graphs that model real‐world systems.