An improved set covering problem for Isomap supervised landmark selection

作者：Orsenigo Carlotta^*

来源：Pattern Recognition Letters, 2014, 49: 131-137.

DOI：10.1016/j.patrec.2014.07.007

• Nonlinear dimensionality reduction
• Isometric feature mapping
• Landmark selection
• Set covering problem
• Classification

In this paper we present a novel method for supervised landmark selection to be framed within Landmark Isomap algorithm (L-Isomap). It is based on a weighted set covering problem aimed at finding a set of landmarks whose neighborhoods cover all the points at minimum cost. The cost associated to each neighborhood is a function of two indices measuring, respectively, the closeness of the points within the neighborhood and its class homogeneity. The resulting set covering problem is solved by means of a heuristic procedure based on Lagrangian relaxation with subgradient optimization. Computational tests performed on five labeled data sets showed the usefulness of L-Isomap combined with the new landmark selection technique. Indeed, it dominated effective competing methods and emerged as a valuable alternative to Isomap for efficient dimensionality reduction in supervised learning contexts.

• 出版日期2014-11-1