Linear Semi-Supervised Dimensionality Reduction with Pairwise Constraint for Multiple Subclasses

Bin TONG  Weifeng JIA  Yanli JI  Einoshin SUZUKI  

IEICE TRANSACTIONS on Information and Systems   Vol.E95-D   No.3   pp.812-820
Publication Date: 2012/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E95.D.812
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Artificial Intelligence, Data Mining
dimensionality reduction,  multiple subclasses,  pairwise constraints,  

Full Text: PDF(2.4MB)>>
Buy this Article

We propose a new method, called Subclass-oriented Dimensionality Reduction with Pairwise Constraints (SODRPaC), for dimensionality reduction. In a high dimensional space, it is common that a group of data points with one class may scatter in several different groups. Current linear semi-supervised dimensionality reduction methods would fail to achieve fair performances, as they assume two data points linked by a must-link constraint are close each other, while they are likely to be located in different groups. Inspired by the above observation, we classify the must-link constraint into two categories, which are the inter-subclass must-link constraint and the intra-subclass must-link constraint, respectively. We carefully generate cannot-link constraints by using must-link constraints, and then propose a new discriminant criterion by employing the cannot-link constraints and the compactness of shared nearest neighbors. The manifold regularization is also incorporated in our dimensionality reduction framework. Extensive experiments on both synthetic and practical data sets illustrate the effectiveness of our method.