A comparative study of nonlinear manifold learning methods for cancer microarray data classification

The paper presents an empirical comparison of the most prominent nonlinear manifold learning techniques for dimensionality reduction in the context of high-dimensional microarray data classification. In particular, we assessed the performance of six methods: isometric feature mapping, locally linear embedding, Laplacian eigenmaps, Hessian eigenmaps, local tangent space alignment and maximum variance unfolding. Unlike previous studies on the subject, the experimental framework adopted in this work properly extends to dimensionality reduction the supervised learning paradigm, by regarding the test set as an out-of-sample set of new points which are excluded from the manifold learning process. This in order to avoid a possible overestimate of the classification accuracy which may yield misleading comparative results. The different empirical approach requires the use of a fast and effective out-of-sample embedding method for mapping new high-dimensional data points into an existing reduced space. To this aim we propose to apply multi-output kernel ridge regression, an extension of linear ridge regression based on kernel functions which has been recently presented as a powerful method for out-of-sample projection when combined with a variant of isometric feature mapping. Computational experiments on a wide collection of cancer microarray data sets show that classifiers based on Isomap, LLE and LE were consistently more accurate than those relying on HE, LTSA and MVU. In particular, under different experimental conditions LLE-based classifier emerged as the most effective method whereas Isomap algorithm turned out to be the second best alternative for dimensionality reduction.     

一种新的有监督流形学习方法

提出了一种新的有监督流形学习方法,目的是提供将流形学习降维方法高效应用于有监督学习问题的全新策略.算法的核心思想是集成流形学习方法对高维流形结构数据的降维有效性与支撑向量机(SVM)在中小规模分类数据集上的优良特性实现高效有监督流形学习.算法具体实现步骤为:首先利用SVM在流形学习降维数据中选出对分类决策最重要的数据集,即支撑向量集;按标号返回可得到原空间的支撑向量集;在这个集合上再次使用SVM即可得到原空间的分类决策,从而完成有监督流形学习.在一系列人工与实际数据集上的实验验证了方法的有效性.     

Continuum Isomap for manifold learnings

Recently, the Isomap algorithm has been proposed for learning a parameterized manifold from a set of unorganized samples from the manifold. It is based on extending the classical multidimensional scaling method for dimension reduction, replacing pairwise Euclidean distances by the geodesic distances on the manifold. A continuous version of Isomap called continuum Isomap is proposed. Manifold learning in the continuous framework is then reduced to an eigenvalue problem of an integral operator. It is shown that the continuum Isomap can perfectly recover the underlying parameterization if the mapping associated with the parameterized manifold is an isometry and its domain is convex. The continuum Isomap also provides a natural way to compute low-dimensional embeddings for out-of-sample data points. Some error bounds are given for the case when the isometry condition is violated. Several illustrative numerical examples are also provided.     

Dimensionality reduction-based spoken emotion recognition

To improve effectively the performance on spoken emotion recognition, it is needed to perform nonlinear dimensionality reduction for speech data lying on a nonlinear manifold embedded in a high-dimensional acoustic space. In this paper, a new supervised manifold learning algorithm for nonlinear dimensionality reduction, called modified supervised locally linear embedding algorithm (MSLLE) is proposed for spoken emotion recognition. MSLLE aims at enlarging the interclass distance while shrinking the intraclass distance in an effort to promote the discriminating power and generalization ability of low-dimensional embedded data representations. To compare the performance of MSLLE, not only three unsupervised dimensionality reduction methods, i.e., principal component analysis (PCA), locally linear embedding (LLE) and isometric mapping (Isomap), but also five supervised dimensionality reduction methods, i.e., linear discriminant analysis (LDA), supervised locally linear embedding (SLLE), local Fisher discriminant analysis (LFDA), neighborhood component analysis (NCA) and maximally collapsing metric learning (MCML), are used to perform dimensionality reduction on spoken emotion recognition tasks. Experimental results on two emotional speech databases, i.e. the spontaneous Chinese database and the acted Berlin database, confirm the validity and promising performance of the proposed method.     

Phoneme recognition using an adaptive supervised manifold learning algorithm

To effectively handle speech data lying on a nonlinear manifold embedded in a high-dimensional acoustic space, in this paper, an adaptive supervised manifold learning algorithm based on locally linear embedding (LLE) for nonlinear dimensionality reduction is proposed to extract the low-dimensional embedded data representations for phoneme recognition. The proposed method aims to make the interclass dissimilarity maximized, while the intraclass dissimilarity minimized in order to promote the discriminating power and generalization ability of the low-dimensional embedded data representations. The performance of the proposed method is compared with five well-known dimensionality reduction methods, i.e., principal component analysis, linear discriminant analysis, isometric mapping (Isomap), LLE as well as the original supervised LLE. Experimental results on three benchmarking speech databases, i.e., the Deterding database, the DARPA TIMIT database, and the ISOLET E-set database, demonstrate that the proposed method obtains promising performance on the phoneme recognition task, outperforming the other used methods.     

基于鲁棒的全局流形学习方法

非线性降维在数据挖掘、机器学习、图像分析和计算机视觉等领域应用广泛。等距映射算法(Isomap)是一种全局流形学习方法,能有效地学习等距流形的“低维嵌入”,但它对数据中的离群样本点缺乏鲁棒性。针对这种情况,该文提出一种离群点检测方法,基于Isomap的基本思想,给出一种鲁棒的全局流形学习方法,提高Isomap处理离群样本点的能力。数值实验表明了该方法的有效性。     

Learning eigenfunctions links spectral embedding and kernel PCA

In this letter, we show a direct relation between spectral embedding methods and kernel principal components analysis and how both are special cases of a more general learning problem: learning the principal eigenfunctions of an operator defined from a kernel and the unknown data-generating density. Whereas spectral embedding methods provided only coordinates for the training points, the analysis justifies a simple extension to out-of-sample examples (the Nystr?m formula) for multidimensional scaling (MDS), spectral clustering, Laplacian eigenmaps, locally linear embedding (LLE), and Isomap. The analysis provides, for all such spectral embedding methods, the definition of a loss function, whose empirical average is minimized by the traditional algorithms. The asymptotic expected value of that loss defines a generalization performance and clarifies what these algorithms are trying to learn. Experiments with LLE, Isomap, spectral clustering, and MDS show that this out-of-sample embedding formula generalizes well, with a level of error comparable to the effect of small perturbations of the training set on the embedding.     

Supervised local spline embedding for medical diagnosis

A common difficulty of intelligent medical diagnosis is the high dimensionality of medical data. Manifold learning provides an elegant way to solve this problem by mapping the high-dimensional data into the low-dimensional embedding. However, traditional manifold learning algorithms fail to fully utilize the supervised information in medical diagnosis. To overcome this problem, in this paper we propose a novel Supervised Local Spline Embedding (SLSE) algorithm, which incorporates the supervised information into the local spline manifold embedding. SLSE not only preserves the local neighborhood structure, but also utilizes the global manifold shape through spline interpolation. Moreover, SLSE leverages the supervised information by maximizing the inter-class scatterness and minimizing the intra-class scatterness in the low-dimensional embedding. The promising experimental results on real-world medical datasets illustrate the superiority of our proposed approach in comparison with the existing popular manifold learning algorithms.

     

Supervised Distance Preserving Projections

In this work, we consider dimensionality reduction in supervised settings and, specifically, we focus on regression problems. A novel algorithm, the supervised distance preserving projection (SDPP), is proposed. The SDPP minimizes the difference between pairwise distances among projected input covariates and distances among responses locally. This minimization of distance differences leads to the effect that the local geometrical structure of the low-dimensional subspace retrieved by the SDPP mimics that of the response space. This, not only facilitates an efficient regressor design but it also uncovers useful information for visualization. The SDPP achieves this goal by learning a linear parametric mapping and, thus, it can easily handle out-of-sample data points. For nonlinear data, a kernelized version of the SDPP is also derived. In addition, an intuitive extension of the SDPP is proposed to deal with classification problems. The experimental evaluation on both synthetic and real-world data sets demonstrates the effectiveness of the SDPP, showing that it performs comparably or superiorly to state-of-the-art approaches.     

Nonlinear Dimensionality Reduction by Locally Linear Inlaying

High-dimensional data is involved in many fields of information processing. However, sometimes, the intrinsic structures of these data can be described by a few degrees of freedom. To discover these degrees of freedom or the low-dimensional nonlinear manifold underlying a high-dimensional space, many manifold learning algorithms have been proposed. Here we describe a novel algorithm, locally linear inlaying (LLI), which combines simple geometric intuitions and rigorously established optimality to compute the global embedding of a nonlinear manifold. Using a divide-and-conquer strategy, LLI gains some advantages in itself. First, its time complexity is linear in the number of data points, and hence LLI can be implemented efficiently. Second, LLI overcomes problems caused by the nonuniform sample distribution. Third, unlike existing algorithms such as isometric feature mapping (Isomap), local tangent space alignment (LTSA), and locally linear coordination (LLC), LLI is robust to noise. In addition, to evaluate the embedding results quantitatively, two criteria based on information theory and Kolmogorov complexity theory, respectively, are proposed. Furthermore, we demonstrated the efficiency and effectiveness of our proposal by synthetic and real-world data sets.      

Inductive manifold learning using structured support vector machine

Most manifold learning techniques are used to transform high-dimensional data sets into low-dimensional space. In the use of such techniques, after unseen data samples are added to the data set, retraining is usually necessary. However, retraining is a time-consuming process and no guarantee of the transformation into the exactly same coordinates, thus presenting a barrier to the application of manifold learning as a preprocessing step in predictive modeling. To solve this problem, learning a mapping from high-dimensional representations to low-dimensional coordinates is proposed via structured support vector machine. After training a mapping, low-dimensional representations of unobserved data samples can be easily predicted. Experiments on several datasets show that the proposed method outperforms the existing out-of-sample extension methods.     

自适应邻域选择的数据可分性降维方法

针对现有基于流形学习的降维方法对局部邻域大小选择的敏感性,且降至低维后的数据不具有很好的可分性,提出一种自适应邻域选择的数据可分性降维方法。该方法通过估计数据的本征维度和局部切方向来自适应地选择每一样本点的邻域大小;同时,使用映射数据时的聚类信息来汇聚相似的样本点,保证降维后的数据具有良好的可分性,使之实现更好的降维效果。实验结果表明,在人工生成的数据集上,新方法获得了较好的嵌入结果;并且在人脸的可视化分类和图像检索中得到了期望的结果。     

利用图像距离的监督LLE头部姿态估计方法

局部线性嵌入(LLE)是一种经典流形学习方法,直接应用这种非监督的传统LLE估计图像中的头部姿态存在两点不足:未考虑图像像素空间信息和未利用样本标记信息.因此,本文结合图像欧式距离和偏置LLE流形学习方法,对头部姿态图像降维,并通过广义回归神经网络(GRNN)和多元线性回归的方法,估计头部图像的姿态.在FacePix头部姿态数据库的对比实验表明,本方法具有较好的头部姿态估计效果.     

Human action segmentation and classification based on the Isomap algorithm

Visual analysis of human behavior has attracted a great deal of attention in the field of computer vision because of the wide variety of potential applications. Human behavior can be segmented into atomic actions, each of which indicates a single, basic movement. To reduce human intervention in the analysis of human behavior, unsupervised learning may be more suitable than supervised learning. However, the complex nature of human behavior analysis makes unsupervised learning a challenging task. In this paper, we propose a framework for the unsupervised analysis of human behavior based on manifold learning. First, a pairwise human posture distance matrix is derived from a training action sequence. Then, the isometric feature mapping (Isomap) algorithm is applied to construct a low-dimensional structure from the distance matrix. Consequently, the training action sequence is mapped into a manifold trajectory in the Isomap space. To identify the break points between the trajectories of any two successive atomic actions, we represent the manifold trajectory in the Isomap space as a time series of low-dimensional points. A temporal segmentation technique is then applied to segment the time series into sub series, each of which corresponds to an atomic action. Next, the dynamic time warping (DTW) approach is used to cluster atomic action sequences. Finally, we use the clustering results to learn and classify atomic actions according to the nearest neighbor rule. If the distance between the input sequence and the nearest mean sequence is greater than a given threshold, it is regarded as an unknown atomic action. Experiments conducted on real data demonstrate the effectiveness of the proposed method.     

基于有监督增量式等距离映射的人脸识别

针对等距离映射（Isomap）算法无法对后续采集的测试样本单独进行降维处理和未能利用样本点分类信息的不足,提出了一种有监督的增量式等距离映射算法（SIIsomap）,并采取小波变换对图像进行预处理。通过对ORL数据库实验证明,SIIsomap算法与Isomap算法相比大大降低了处理新增样本点的计算时间,并且提高了识别精度。     

基于Isomap的流形结构重建方法

已有的流形学习方法仅能建立点对点的降维嵌入,而未建立高维数据流形空间与低维表示空间之间的相互映射.此缺陷已限制了流形学习方法在诸多数据挖掘问题中的进一步应用.针对这一问题,文中提出了两种新型高效的流形结构重建算法:快速算法与稳健算法.其均以经典的Isomap方法内在运行机理为出发点,进而推导出高维流形空间与低维表示空间之间双向的显式映射函数关系,基于此函数即可实现流形映射的有效重建.理论分析与实验结果证明,所提算法在计算速度、噪音敏感性、映射表现等方面相对已有方法具有明显优势.     

1D representation of Isomap for united video coding

This paper proposes a 1D representation of isometric feature mapping (Isomap) based united video coding algorithms. First, 1D Isomap representations that maintain distances are generated which can achieve a very high compression ratio. Next, embedding and reconstruction algorithms for the 1D Isomap representation are presented that can transform samples from a high-dimensional space to a low-dimensional space and vice versa. Then, dictionary learning algorithms for training samples are proposed to compress the input samples. Finally, a unified coding framework for diverse videos based on a 1D Isomap representation is built. The proposed methods make full use of correlations between internal and external videos, which are not considered by classical methods. Simulation experiments have shown that the proposed methods can obtain higher peak signal-to-noise ratios than standard highly efficient video coding for similar bit per pixel levels in the low bit rate situation.     

一种鲁棒的监督流形学习算法及其在植物叶片分类中的应用

结合数据点的类别信息、局部信息和数据点的可信度,给出一种测地距离定义。在此基础上,提出一种改进的鲁棒性监督等度规映射算法,并应用于植物叶片分类中。首先利用改进的等度规映射将叶片图像投影到低维流形空间。然后采用支持向量机分类器进行植物叶片图像分类与识别。最后利用20种实际植物叶片图像进行植物叶片图像分类实验。实验结果表明该方法是有效可行的。     

流形学习与非线性回归结合的头部姿态估计

流形学习的目的是发现非线性数据的内在结构,可用于非线性降维。广义回归网络是人工神经网络的一种,可用于非线性回归。基于流形学习和非线性回归,提出了用于解决头部姿态估计的ManiNLR方法。该方法首先用流形学习对图像数据进行降维,然后用非线性回归的方法将数据映射到线性可分空间,利用非线性回归的结果对人脸的头部姿态进行估计。实验结果表明,ManiNLR算法能够较好地估计图像中的头部姿态,并具有较快的速度和较高的鲁棒性。     

Robust kernel Isomap

Isomap is one of widely used low-dimensional embedding methods, where geodesic distances on a weighted graph are incorporated with the classical scaling (metric multidimensional scaling). In this paper we pay our attention to two critical issues that were not considered in Isomap, such as: (1) generalization property (projection property); (2) topological stability. Then we present a robust kernel Isomap method, armed with such two properties. We present a method which relates the Isomap to Mercer kernel machines, so that the generalization property naturally emerges, through kernel principal component analysis. For topological stability, we investigate the network flow in a graph, providing a method for eliminating critical outliers. The useful behavior of the robust kernel Isomap is confirmed through numerical experiments with several data sets.