l2,1-Norm Regularized Discriminative Feature Selection for Unsupervised Learning

TL;DR

This paper introduces a novel unsupervised feature selection method, UDFS, that simultaneously leverages discriminative information and feature correlations. By optimizing a joint objective function with an L2,1-norm regularization and an orthogonal constraint, UDFS effectively selects discriminative features in a batch mode, outperforming existing unsupervised methods in clustering tasks.

What Problem Does This Paper Address?

High-dimensional data is common in fields like computer vision and pattern recognition, making feature selection crucial for efficient and accurate data representation. While supervised feature selection methods excel at identifying discriminative features using labels, unsupervised settings lack this guidance. Traditional unsupervised methods often focus on preserving data distribution or manifold structure, neglecting discriminative information. This paper addresses the challenge of selecting truly discriminative features in an unsupervised manner, where labels are unavailable, by proposing a method that can infer discriminative power from the data itself.

Methods

The core of the proposed method, Unsupervised Discriminative Feature Selection (UDFS), lies in its objective function. It combines discriminative analysis with an L2,1-norm minimization, regularized by an orthogonal constraint (WTW=I). The L2,1-norm encourages sparsity in the rows of the weight matrix W, effectively selecting features. The orthogonal constraint prevents trivial solutions and arbitrary scaling.

The method incorporates local discriminative information by considering a local neighborhood around each data point. It defines local scatter matrices and uses a linear classifier assumption (Gi = WTxi) to infer discriminative scores for each data point. The optimization problem is solved using an iterative approach inspired by existing L2,1-norm minimization techniques, but adapted to handle the orthogonal constraint. This iterative process involves updating a weight matrix and a diagonal matrix, converging to an optimal solution. The selected features are then ranked based on the L2,1-norm of their corresponding rows in the weight matrix.

Datasets

The paper evaluates UDFS on six public datasets:

  • UMIST: Face image dataset.
  • FERET: Face image dataset.
  • YALEB: Face image dataset.
  • USF HumanID: Gait image dataset.
  • Isolet: Spoken letter recognition data.
  • USPS: Handwritten digit image dataset.

These datasets cover diverse data types and complexities, allowing for a comprehensive evaluation of the proposed method.

Key Insights and Ideas

  • Discriminative Information is Key, Even Unsupervised: The paper strongly argues that discriminative information, often overlooked in unsupervised settings, is crucial for effective feature selection.
  • Batch Mode Selection is Superior: Unlike many existing methods that select features one by one, UDFS selects features in a batch mode, which is shown to be more effective by considering feature correlations.
  • Local Structure Matters: Incorporating local neighborhood information, in addition to global data distribution, significantly improves feature selection performance.
  • L2,1-Norm for Feature Selection: The L2,1-norm is a powerful tool for inducing sparsity at the feature level, making it ideal for selecting a subset of features.
  • Orthogonal Constraint for Stability: The orthogonal constraint (WTW=I) is essential for preventing trivial solutions and ensuring a stable and meaningful feature representation.

Key Results

The experimental results demonstrate that UDFS consistently outperforms other unsupervised feature selection algorithms, including "All Features," "Max Variance," "Laplacian Score," "Feature Ranking," and "MCFS," across various datasets.

  • Clustering Accuracy (ACC): UDFS achieved the highest ACC on most datasets, with notable improvements on Isolet (66.0% ± 3.6) and USPS (65.8% ± 3.3).
  • Normalized Mutual Information (NMI): UDFS also showed superior performance in terms of NMI, indicating better agreement between the clustered labels and the ground truth. For instance, it achieved 25.4% ± 0.9 on YALEB and 78.1% ± 1.3 on Isolet.
  • Efficiency: While not explicitly quantified in terms of speedup, the batch mode selection and the proposed optimization algorithm are designed for efficiency.

Limitations and Future Work

  • Parameter Sensitivity: The paper notes that while the regularization parameter $\gamma$ is not highly sensitive for values less than 1, the performance is more sensitive to the number of selected features. Deciding the optimal number of features remains an open problem and is data-dependent.
  • Computational Complexity: The time complexity of computing the matrix M is O(n²), and the eigen-decomposition of Pt is O(d³), where d is the number of features. While efficient for optimization, these complexities might be a bottleneck for extremely large datasets.
  • Future Work: The authors suggest that future research could explore how to automatically determine the number of selected features and further investigate the theoretical properties of the proposed algorithm.

Summary updated

BibTeX
@inproceedings{2011l,
  title = {{l2,1-Norm Regularized Discriminative Feature Selection for Unsupervised Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.5591/978-1-57735-516-8/ijcai11-267},
}
Figure