Title :
M-Isomap: Orthogonal Constrained Marginal Isomap for Nonlinear Dimensionality Reduction
Author :
Zhao Zhang ; Chow, Tommy W. S. ; Mingbo Zhao
Author_Institution :
Dept. of Electron. Eng., City Univ. of Hong Kong, Kowloon, China
Abstract :
Isomap is a well-known nonlinear dimensionality reduction (DR) method, aiming at preserving geodesic distances of all similarity pairs for delivering highly nonlinear manifolds. Isomap is efficient in visualizing synthetic data sets, but it usually delivers unsatisfactory results in benchmark cases. This paper incorporates the pairwise constraints into Isomap and proposes a marginal Isomap (M-Isomap) for manifold learning. The pairwise Cannot-Link and Must-Link constraints are used to specify the types of neighborhoods. M-Isomap computes the shortest path distances over constrained neighborhood graphs and guides the nonlinear DR through separating the interclass neighbors. As a result, large margins between both interand intraclass clusters are delivered and enhanced compactness of intracluster points is achieved at the same time. The validity of M-Isomap is examined by extensive simulations over synthetic, University of California, Irvine, and benchmark real Olivetti Research Library, YALE, and CMU Pose, Illumination, and Expression databases. The data visualization and clustering power of M-Isomap are compared with those of six related DR methods. The visualization results show that M-Isomap is able to deliver more separate clusters. Clustering evaluations also demonstrate that M-Isomap delivers comparable or even better results than some state-of-the-art DR algorithms.
Keywords :
constraint handling; data reduction; data visualisation; graph theory; pattern clustering; visual databases; CMU Pose; CMU pose databases; Irvine; M-Isomap; University of California; YALE; benchmark real Olivetti Research Library; clustering evaluations; constrained neighborhood graphs; data clustering power; expression databases; geodesic distances; illumination databases; interclass clusters; intraclass clusters; manifold learning; nonlinear DR method; nonlinear dimensionality reduction; nonlinear manifolds; orthogonal constrained marginal isomap; pairwise Cannot-Link constraints; pairwise Must-Link constraints; shortest path distances; state-of-the-art DR algorithms; synthetic data set visualisation; Benchmark testing; Coordinate measuring machines; Data visualization; Databases; Euclidean distance; Joining processes; Manifolds; Isomap; manifold learning; nonlinear dimensionality reduction (DR); pairwise constraints (PCs); visualization;
Journal_Title :
Cybernetics, IEEE Transactions on
DOI :
10.1109/TSMCB.2012.2202901