Unsupervised Feature Selection by Preserving Stochastic Neighbors

Xiaokai Wei, Philip S. Yu

Unsupervised Feature Selection by Preserving Stochastic Neighbors

In the era of big data, researchers often encounter datasets with thousands of features, many of which are redundant or noisy. This "curse of dimensionality" complicates machine learning by increasing computational costs and reducing model interpretability. While supervised learning can leverage labels to identify critical features, unsupervised feature selection remains a significant challenge. Traditional unsupervised methods often evaluate features in isolation or rely on potentially inaccurate "pseudo-labels" generated from initial clustering guesses.

The SNFS Approach

To address these limitations, researchers introduced Stochastic Neighbor-preserving Feature Selection (SNFS). Inspired by Stochastic Neighbor Embedding (SNE), SNFS models the local structure of data using a probabilistic neighborhood distribution. Instead of binary neighbor assignments, it calculates the probability of any two points being neighbors based on their similarity.

The core objective of SNFS is to select a feature subset that minimizes the Kullback-Leibler (KL) divergence between the neighborhood distribution in the original high-dimensional space and the reduced feature space. A key advantage of this approach is its "push-pull" property: the optimization process naturally pulls similar points together while pushing dissimilar ones apart, leading to more distinct clusters. To ensure scalability, the algorithm utilizes the Projected Quasi-Newton method (L-BFGS), allowing it to handle large-scale datasets efficiently.

Stability of SNFS accuracy across different perplexity values on the BBC dataset.

Experimental Results and Stability

The effectiveness of SNFS was evaluated across six real-world datasets, including news corpora (BBC, Guardian) and social media data (BlogCatalog). The results were significant; for instance, on the BlogCatalog dataset, SNFS achieved a 36.4% improvement in clustering accuracy while utilizing only 230 selected features compared to the full feature set.

A critical finding was the method's stability. Unlike many unsupervised techniques that require extensive parameter tuning, SNFS demonstrated high robustness to its internal "perplexity" parameter. As shown in Figure 1, accuracy remains consistently high across a wide range of perplexity values (typically 5–50). Furthermore, SNFS often outperformed state-of-the-art baselines even when those competitors were unfairly advantaged by tuning with ground-truth labels.

Clustering accuracy of SNFS compared to all features across four datasets (BBC, BBCSport, BlogCatalog, Guardian) relative to the regularization parameter λ.

Practical Implementation and Limitations

For practical engineering, SNFS offers a heuristic known as the $N_{0.9}$ guideline: users should retain features with an importance score exceeding 0.9. This reduces the need for manual "knob-turning" in real-world scenarios where labels are unavailable.

However, challenges remain. The $O(n^2)$ complexity of calculating pairwise neighborhood probabilities suggests that for datasets with millions of samples, further approximations or tree-based search methods will be necessary. Additionally, while highly effective for text data using inner-product similarity, future work may explore adapting the distance metrics for other domains such as image processing or time-series analysis.

Conclusion

SNFS represents a robust advancement in unsupervised feature selection. By preserving the stochastic neighborhood structure and evaluating features jointly, it captures non-linear relationships that traditional linear methods miss, providing a powerful tool for dimensionality reduction in complex, unlabeled datasets.

Summary updated

Abstract

Feature selection is an important technique for alleviating the curse of dimensionality. Unsupervised feature selection is more challenging than its supervised counterpart due to the lack of labels. In this paper, we present an effective method, Stochastic Neighbor-preserving Feature Selection (SNFS), for selecting discriminative features in unsupervised setting. We employ the concept of stochastic neighbors and select the features that can best preserve such stochastic neighbors by minimizing the Kullback-Leibler (KL) Divergence between neighborhood distributions. The proposed approach measures feature utility jointly in a non-linear way and discriminative features can be selected due to its ’push-pull’ property. We develop an efficient algorithm for optimizing the objective function based on projected quasi-Newton method. Moreover, few existing methods provide ways for determining the optimal number of selected features and this hampers their utility in practice. Our approach is equipped with a guideline for choosing the number of features, which provides nearly optimal performance in our experiments. Experimental results show that the proposed method outperforms state-of-the-art methods significantly on several real-world datasets.
BibTeX
@inproceedings{wei2016unsupervised,
  author = {Xiaokai Wei and Philip S. Yu},
  title = {{Unsupervised Feature Selection by Preserving Stochastic Neighbors}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
}
Figure