Semi-Supervised Dimensionality Reduction

Dimensionality reduction is among the keys in mining high-dimensional data. This paper studies semi-supervised dimensionality reduction. In this setting, besides abundant unlabeled examples, domain knowledge in the form of pairwise constraints are available, which specifies whether a pair of instances belong to the same class (must-link constraints) or different classes (cannot-link constraints). We propose the SSDR algorithm, which can preserve the intrinsic structure of the unlabeled data as well as both the must-link and cannot-link constraints defined on the labeled examples in the projected low-dimensional space. The SSDR algorithm is efficient and has a closed form solution. Experiments on a broad range of data sets show that SSDR is superior to many established dimensionality reduction methods.