Efficient Spectral Feature Selection with Minimum Redundancy

Zheng Zhao, Lei Wang, Huan LiuAAAI 2010 · DOI

Abstract

Traditional spectral feature selection (SFS) methods are effective at preserving data structure but often suffer from redundancy because they evaluate features independently. This paper introduces MRSF (Minimize feature Redundancy for Spectral Feature selection), an algorithm that utilizes sparse multi-output regression to select features jointly. By framing feature selection as a reconstruction task of the similarity matrix's leading eigenvectors, MRSF effectively eliminates redundancy while significantly improving classification accuracy and computational efficiency.

Introduction

In high-dimensional data environments, such as genomics or high-resolution imaging, the number of features often vastly exceeds the number of samples—a challenge known as the "curse of dimensionality." Spectral Feature Selection (SFS) is a widely used technique to mitigate this by identifying features that preserve the underlying manifold structure of the data. However, standard SFS approaches typically rank features individually, failing to account for correlations between them. This results in redundant feature sets that increase computational overhead and can degrade the performance of downstream learning algorithms.

Methodology

The proposed MRSF algorithm addresses the redundancy issue by evaluating features jointly. The core innovation lies in framing feature selection as a Sparse Multi-output Regression problem.

  1. Structural Reconstruction: The goal is to find a minimal subset of features whose linear combination can best reconstruct the leading eigenvectors of the data's similarity matrix. These eigenvectors represent the essential geometric structure of the dataset.
  2. Group Sparsity Constraint: To ensure a compact feature set, an $L_{2,1}$-norm constraint is applied to the regression weights. This "group sparsity" penalty encourages the model to use as few features as possible to explain the data structure.
  3. Efficient Path-Following Solver: To avoid the high cost of grid-searching for optimal regularization parameters, the authors developed a path-following solver. This algorithm starts with an empty feature set and strategically adds features to an "active set," utilizing "warm starts" from previous steps to accelerate convergence.

Experimental Results

The researchers evaluated MRSF against six baseline algorithms (including ReliefF, Fisher Score, and mRMR) across six high-dimensional benchmark datasets, including image data (AR10P, PIE10P, PIX10, ORL10P) and microarray data (TOX, CLL-SUB).

Classification Performance

MRSF achieved significantly higher classification accuracy across all tested datasets. On average, it outperformed the baselines by approximately 11%, demonstrating the benefit of joint feature evaluation.

Table 1: Comparison of classification accuracy across various datasets. MRSF consistently achieves the highest scores (bolded).

Computational Efficiency

Despite the added complexity of joint feature evaluation, the MRSF solver proved to be highly efficient. By utilizing the path-following approach, it bypassed the need for exhaustive parameter tuning.

Figure 1: Comparison of run time (seconds) between the Nesterov optimization method and the proposed MRSF solver across different datasets.

As shown in the runtime comparison, MRSF was consistently faster than the state-of-the-art Nesterov optimization method, averaging 23.33 seconds across the datasets compared to 37.46 seconds for the competitor.

Conclusion

MRSF represents a significant advancement in spectral feature selection by integrating redundancy minimization directly into the selection process. By leveraging sparse multi-output regression and an efficient path-following solver, it provides a robust framework for handling high-dimensional data, offering superior accuracy and faster processing times than traditional ranking-based methods. Future research may explore non-linear extensions to capture more complex feature dependencies.

Summary updated

BibTeX
@inproceedings{zhao2010efficient,
  author = {Zheng Zhao and Lei Wang and Huan Liu},
  title = {{Efficient Spectral Feature Selection with Minimum Redundancy}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7671},
}
Figure