Abstract
In high-dimensional data analysis, feature selection is critical for reducing noise and redundancy. This paper introduces Unsupervised Discriminative Feature Selection (UDFS), a framework that identifies discriminative features without manual labels. By combining local discriminative analysis with $\ell_{2,1}$-norm regularization, UDFS captures latent class structures from local neighborhoods and selects a sparse, non-redundant subset of features in a single optimization step. Evaluation across six public datasets shows that UDFS consistently achieves superior clustering accuracy and normalized mutual information compared to existing methods.
Introduction
High-dimensional data, such as images or gene sequences, often contains significant noise and redundant information that can degrade the performance of machine learning models. Feature selection aims to mitigate this by identifying the most relevant variables. While supervised feature selection uses labels to find discriminative features, unsupervised learning lacks this guidance. Traditional unsupervised methods often focus on preserving the data's manifold (geometric shape), but this does not necessarily identify features that distinguish between underlying classes. UDFS addresses this by leveraging local structures to "hallucinate" discriminative information.
Methodology
The UDFS algorithm is built upon three primary pillars:
- Local Discriminative Analysis: In the absence of global labels, UDFS examines the $k$-nearest neighbors of each data point. It assumes that local clusters represent latent classes and seeks to maximize the discriminative score within these neighborhoods.
- Linear Classifier Assumption: The model assumes that latent class labels can be predicted using a linear classifier $W$. By optimizing $W$ to separate local structures, the algorithm identifies the features most responsible for that separation.
- $\ell_{2,1}$-Norm Regularization: This mathematical approach induces row-sparsity in the weight matrix $W$. Unlike standard regularization, the $\ell_{2,1}$-norm encourages entire rows to become zero, effectively discarding irrelevant features. This allows for "batch mode" feature selection, considering the joint contribution of features rather than evaluating them individually.
The authors also present an efficient iterative algorithm to solve the resulting non-convex optimization problem, with proven convergence to an optimal solution.
Experimental Evaluation
The researchers evaluated UDFS on six diverse public datasets, including face images (UMIST, FERET, YALEB), gait analysis (USF HumanID), speech recognition (Isolet), and handwritten digits (USPS).
Key Results and Insights
UDFS was compared against several baselines, including Laplacian Score (LS) and Multi-Cluster Feature Selection (MCFS). Across all datasets, UDFS consistently achieved the highest Clustering Accuracy (ACC) and Normalized Mutual Information (NMI).
On the YALEB face dataset, UDFS achieved an accuracy of 14.7%, outperforming Feature Ranking (13.3%) and the manifold-based MCFS (12.4%). Furthermore, the algorithm demonstrated remarkable stability regarding the regularization parameter $\gamma$. Performance remains relatively constant for $\gamma$ values below 1, simplifying practical deployment as exhaustive hyperparameter tuning is less critical.
Discussion and Future Work
While UDFS offers significant advantages, it has certain limitations:
- Computational Complexity: The optimization involves an eigen-decomposition step with a complexity of approximately $O(d^3)$, where $d$ is the number of features. This may be a bottleneck for ultra-high-dimensional data.
- Linearity: The assumption of a linear classifier may not hold for data where discriminative features are related through complex non-linear transformations.
- Neighborhood Sensitivity: Performance depends on the choice of $k$ (number of neighbors). While $k=5$ was effective in these experiments, automated selection of $k$ remains an open challenge.
In conclusion, UDFS provides a robust, integrated approach to unsupervised feature selection by combining local discriminative hints with joint sparsity constraints.
Summary updated