Elsevier

Pattern Recognition

Volume 55, July 2016, Pages 215-230
Pattern Recognition

Multi-manifold Discriminant Isomap for visualization and classification

https://doi.org/10.1016/j.patcog.2016.02.001Get rights and content

Highlights

  • Preserve the geometrical structure and enhance the discriminating capability.

  • SMACOF algorithm is introduced to solve the optimization problem.

  • Two metrics are designed to evaluate dimensionality reduction methods.

  • Experiments show the effectiveness of the method in visualization and classification.

Abstract

Isomap aims to recover the intrinsic geometric structure of manifold by preserving geodesic distances between all pairs of data points. However it is an unsupervised dimensionality-reduction method. Usually, using class label information can increase the discriminating capability, hence a new supervised Isomap is proposed in this paper, dubbed Multi-manifold Discriminant Isomap (MMD-Isomap). First, data points are partitioned into different manifolds according to their class label information. Then, MMD-Isomap aims at seeking an optimal nonlinear subspace to preserve the geometrical structure of each manifold according to the Isomap criterion, meanwhile, to enhance the discriminating capability by maximizing the distances between data points of different manifolds. Finally, the corresponding optimization problem is solved by using a majorization algorithm. Furthermore, two new numerical metrics are designed to measure the performance of dimensionality-reduction method. In both visualization and classification experiments, MMD-Isomap achieves improved performance over many state-of-the-art methods.

Introduction

Dimensionality reduction is to get a compact representation of data by reducing the number of variables under consideration. Since many real-world applications usually suffer from the curse of dimensionality, such as text mining, image matching, gene expressing, etc., dimensionality reduction is a fundamental problem in pattern recognition and machine learning.

Principal Component Analysis (PCA) [1] and Linear Discriminant Analysis (LDA) [2], due to their relative effectiveness and simplicity, have been the two classical dimensionality reduction methods. In addition, many new frameworks or methods [3], [4], [5] for dimensionality reduction have been presented. In particular, some manifold learning methods have attracted a lot of attention in the past few years, e.g., Multi-Dimensional Scaling (MDS) [6], [7], Locally Linear Embedding (LLE) [8], Isomap [9], and Locality Preserving Projection (LPP) [10]. Manifold learning methods assume that the real-world data observed in high dimensional spaces is usually generated by a process with relatively few degrees of freedom [11], and data is intended for embedding into a lower dimensional space with the geometrical structures preserved [12]. These manifold learning methods are generally not devised for classification use, hence they are unsupervised methods, in nature. By considering discriminating information, many supervised methods have been proposed, which broadly fall into two categories. The first category׳s methods define a new distance metric to relatively increase the distances between interclass points in the original dimensional space, and then use corresponding unsupervised manifold learning methods to preserve the prescribed distance relationships, such as Supervised LLE (SLLE) [13], Supervised LPP (SLPP) [14], WeightedIso [15], and Supervised Isomap (S-Isomap) [16]. The second category׳s methods adopt the graph embedding framework [17] to encode the interclass and intraclass structures of data as graph relationships, such as Marginal Fisher Analysis (MFA) [17], Local Discriminant Embedding (LDE) [18], Exponential LDE (ELDE) [19], Discriminant Locally Linear Embedding (DLLE) [20], Discriminant Neighborhood Embedding (DNE) [21], and Linear Discriminant Projections (LDP) [22]. Recently, a supervised method namely Marginal Isomap (M-Isomap) [23], has been proposed. M-Isomap employs local pairwise constraints to construct the intrinsic and penalty graphs and then adopts the graph embedding framework to conduct the final optimization criterion. Despite M-Isomap yielding encouraging results on several data sets, from analysis of this paper, it can be observed that M-Isomap has several shortcomings in theory and implementation.

In this paper, we propose a novel supervised Isomap method called Multi-manifold Discriminant Isomap (MMD-Isomap) for visualization and classification. For visualization, in general, the embedding results in R2 or R3 space should preserve the intrinsic structures of data as much as possible. Whereas for the visual discriminant analysis [24], besides preserving the structures, the results should also produce large margins between the data of different classes. For classification, large margins can also increase the accuracy of the classification [19]. Hence, MMD-Isomap preserves the geodesic distances between the data points of the same class and separates the data points of different classes. MMD-Isomap can be seen as a refinement of M-Isomap, since MMD-Isomap and M-Isomap have similar aims, but MMD-Isomap adopts a more rational and efficient way to achieve them. First, MMD-Isomap adopts global pairwise constraints to conduct the optimization objectives, which can make the entire algorithm preserve the global structures uniformly. Conversely, M-Isomap adopts local pairwise constraints that makes the embedding results of the non-local data points non-directly controllable. Second, MMD-Isomap enhances the discriminating capability in a direct and effective manner, that maximizes the distances between data points of different classes in the lower dimensional space. In contrast, M-Isomap maximizes the difference between the Euclidean distances in the lower dimensional space and the geodesic distances in the original dimensional space. Third, MMD-Isomap considers the data of different classes lies on different manifolds, i.e., multi-manifolds. Hence MMD-Isomap computing the geodesic distances only use intraclass data points that reduces the computation time of algorithm markedly. By contrast, M-Isomap uses all data points to compute geodesic distances, no matter whether they are in same class or not. Last, MMD-Isomap adopts an elegant algorithm called Scaling by MAjorizing a COmplicated Function (SMACOF) to solve the optimization problem in a trace difference form, while M-Isomap uses eigenvalue decomposition iteratively to solve the optimization problem in a trace ratio form. Although SMACOF has been used with relative success in previous works [25], [26], [27], relating to its use in this paper, besides the processes of SMACOF, we also give some theories and corresponding proofs used in SMACOF. Thus explaining how our optimization problem can be solved effectively by SMACOF.

In visualization, to avoid comparing different results individually through examining the figures to point out which “looks” better, some numerical criteria have been designed in previous works. The clustering evaluation metrics [23], [28] could describe the interclass separability and intraclass compactness, but they cannot present structures preserving capability. In addition, the clustering evaluation metrics are heavily dependent on the performance of clustering algorithms, hence different initializations of clustering algorithms will conduce different metric results. Another metric is the correlation coefficient between distance vector in the original space and that in lower dimensional space, which is used in [16] to measure the structures preserving capability, whereas it cannot express the discriminating capability. Therefore in this paper, we design two new numerical metrics in a direct manner, i.e., Average Intruding Rate (AIR) and Average Preserving Rate (APR) to evaluate the capabilities of discriminating and preserving, respectively.

The rest of this paper is organized as follows. In Section 2, related works are briefly introduced. In Section 3, MMD-Isomap is proposed. In Section 4, some experimental results are reported. Finally, some concluding remark is included in Section 5.

This paper is an extended version of the work initially published in IJCNN 2015 [29]. Novel contributions over [29] include the details of the solution (Section 3.3) and some extensions of experiments (Section 4).

Section snippets

Related work

There have been a series of Isomap methods, including Isomap [9], WeightedIso [15], S-Isomap [16] and M-Isomap [23], which will be briefly reviewed in the following.

Motivation

Before going into the details of our proposed method, let’s reiterate the analysis and discussion of the shortcomings of M-Isomap.

  • 1.

    M-Isomap only preserves the local geodesic distances. But Isomap is a global method, whose purpose is to preserve the geodesic distances between all pairs of data points. Therefore M-Isomap contradicts the original intention of Isomap. Moreover, M-Isomap also only focuses on enlarging the distances between local interclass points, but not the holistic interclass

Experiments

In order to investigate the performance of our proposed method, a set of experiments are presented in this section. These experiments consist of two parts: visualization and classification. In visualization experiments, we compare MMD-Isomap with some unsupervised methods including PCA, LLE [8], Isomap [9], and t-Stochastic Neighbor Embedding (t-SNE) [47], [48], as well as several supervised approaches including LDA, SLLE [13], WeightedIso [15], S-Isomap [16], and M-Isomap [23] on one

Conclusions

A new supervised nonlinear dimensionality reduction method, namely MMD-Isomap is presented in this paper. MMD-Isomap using the global pairwise constraints derived from the label information of data set to construct optimization objective, guides a discriminant Multi-manifold learning by maximizing the distances between data points of different classes as well as preserving the geodesic distances between data points of the same class. To solve the problems of MMD-Isomap efficiently, an elegant

Bo Yang received the B.Eng. degree in computer science and technology from Xi׳an University of Posts & Telecommunication, Xi׳an, China, in 2005, and received the M.Eng. degree in computer system architecture from Xidian University, Xi׳an, China, in 2009. He is currently a Ph.D. candidate in the department of computer science and technology, Xi׳an Jiaotong University, Xi׳an, China. His current research interests mainly include manifold learning, pattern recognition and machine learning.

References (54)

  • R. Hettiarachchi et al.

    Multi-manifold LLE learning in pattern recognition

    Pattern Recognit.

    (2015)
  • J. Schmidhuber

    Deep learning in neural networks: an overview

    Neural Netw.

    (2015)
  • W.K. Härdle et al.

    Multivariate Statistics

    (2015)
  • T. Cacoullos

    Discriminant Analysis and Applications

    (2014)
  • T.F. Cox et al.

    Multidimensional Scaling

    (2000)
  • I. Borg et al.

    Modern Multidimensional Scaling: Theory and Applications

    (2005)
  • S.T. Roweis et al.

    Nonlinear dimensionality reduction by locally linear embedding

    Science

    (2000)
  • J.B. Tenenbaum et al.

    A global geometric framework for nonlinear dimensionality reduction

    Science

    (2000)
  • X. He, P. Niyogo, Locality preserving projections, in: Proceedings of the Neural Information Processing Systems,...
  • N. Zheng et al.

    Statistical Learning and Pattern Analysis for Image and Video Processing

    (2009)
  • T. Lin et al.

    Riemannian manifold learning

    IEEE Trans. Pattern Anal. Mach. Intell.

    (2008)
  • D.D. Ridder et al.

    Supervised locally linear embedding

    Proceedings of Artificial Neural Networks and Neural Information Processing

    (2003)
  • W.K. Wonga et al.

    Supervised optimal locality preserving projection

    Pattern Recognit.

    (2012)
  • M. Vlachos, C. Domeniconi, D. Gunopulos, G. Kollios, N. Koudas, Non-linear dimensionality reduction techniques for...
  • X. Geng et al.

    Supervised nonlinear dimensionality reduction for visualization and classification

    IEEE Trans. Syst. , Man, Cybern. B, Cybern.

    (2005)
  • S. Yan et al.

    Graph embedding and extensions: a general framework for dimensionality reduction

    IEEE Trans. Pattern Anal. Mach. Intell.

    (2007)
  • H.T. Chen, H.W. Chang, T.L. Liu, Local discriminant embedding and its variants, in: Proceedings of IEEE International...
  • Cited by (0)

    Bo Yang received the B.Eng. degree in computer science and technology from Xi׳an University of Posts & Telecommunication, Xi׳an, China, in 2005, and received the M.Eng. degree in computer system architecture from Xidian University, Xi׳an, China, in 2009. He is currently a Ph.D. candidate in the department of computer science and technology, Xi׳an Jiaotong University, Xi׳an, China. His current research interests mainly include manifold learning, pattern recognition and machine learning.

    Ming Xiang received the B.Eng. and Ph.D. degrees from Northwestern Polytechnical University, Xi׳an, China, in 1987 and 1999 respectively, and currently works as an associate professor in the department of computer science and technology in Xi׳an Jiaotong University, Xi׳an, China. His current research interests mainly include information fusion, pattern recognition and machine learning.

    Yupei Zhang received the B.Eng. degree in computer science and technology from East China Institute of Technology, Fuzhou, China, in 2009, and received the M.Eng. degree in computer software and theory from Zhengzhou University, Zhengzhou, China, in 2013. He is currently a Ph.D. candidate in the department of computer science and technology, Xi׳an Jiaotong University, Xi׳an, China. His current research interests mainly include sparse representation, pattern recognition and machine learning.

    View full text