Subspace Learning for Feature Selection via Rank Revealing QR Factorization: Unsupervised and Hybrid Approaches with Non-negative Matrix Factorization and Evolutionary Algorithm

Amir Moslemi, Arash AhmadianarXiv 2022 · OpenReview

Abstract

The selection of most informative and discriminative features from high-dimensional data has been noticed as an important topic in machine learning and data engineering. Using matrix factorization-based techniques such as nonnegative matrix factorization for feature selection has emerged as a hot topic in feature selection. The main goal of feature selection using matrix factorization is to extract a subspace which approximates the original space but in a lower dimension. In this study, rank revealing QR (RRQR) factorization, which is computationally cheaper than singular value decomposition (SVD), is leveraged in obtaining the most informative features as a novel unsupervised feature selection technique. This technique uses the permutation matrix of QR for feature selection which is a unique property to this factorization method. Moreover, QR factorization is embedded into non-negative matrix factorization (NMF) objective function as a new unsupervised feature selection method. Lastly, a hybrid feature selection algorithm is proposed by coupling RRQR, as a filter-based technique, and a Genetic algorithm as a wrapper-based technique. In this method, redundant features are removed using RRQR factorization and the most discriminative subset of features are selected using the Genetic algorithm. The proposed algorithm shows to be dependable and robust when compared against state-of-the-art feature selection algorithms in supervised, unsupervised, and semi-supervised settings. All methods are tested on seven available microarray datasets using KNN, SVM and C4.5 classifiers. In terms of evaluation metrics, the experimental results shows that the proposed method is comparable with the state-of-the-art feature selection.

Introduction

In fields like bioinformatics, researchers often deal with the "curse of dimensionality"—datasets where the number of features (e.g., thousands of genes) vastly outweighs the number of samples. Traditional dimensionality reduction techniques like Singular Value Decomposition (SVD) are powerful but computationally heavy. Meanwhile, methods like Non-negative Matrix Factorization (NMF) often require tedious hyperparameter tuning to perform well.

This research aims to bridge the gap between computational efficiency and selection accuracy. It tackles the challenge of identifying a "subspace"—a smaller subset of the original data—that retains the most informative and discriminative features without the overhead of traditional matrix decomposition methods.

Methodology

The authors propose three distinct approaches centered around QR factorization. To assist in navigating the various algorithms and mathematical formulations, the following tables provide a reference for abbreviations and notations used throughout the study.

Table of Abbreviations

1. Unsupervised RRQR

Unlike SVD, which provides a low-rank representation but doesn't directly point to specific columns, RRQR uses a permutation matrix. This matrix acts as a roadmap, identifying which specific columns (features) are linearly independent and most informative.

2. NMF-QR

The authors embed QR factorization into the NMF objective function. This version incorporates a Graph Laplacian to preserve the local geometric structure of the data and an $\ell_{2,1/2}$ norm to ensure global sparsity. Essentially, it keeps similar data points close together in the reduced space while aggressively pruning useless features.

3. Hybrid QR-GA

This is a two-phase "Filter-Wrapper" approach:

  • Phase 1 (Filter): RRQR quickly removes redundant features.
  • Phase 2 (Wrapper): A Genetic Algorithm (GA) searches for the absolute best subset of features from the remaining pool and simultaneously tunes the hyperparameters of the classifier (like an SVM).
Mathematical Notations

Experimental Evaluation

The methods were evaluated on eight microarray datasets, which are standard benchmarks for high-dimensional feature selection: Ovarian, Colon, Breast, Prostate, SMK, Lung, GLI, and Leukemia. These datasets are notoriously difficult because they contain thousands of features but very few instances (often fewer than 100-200).

Key Results

  • Efficiency: RRQR proved to be significantly faster than SVD and NMF-based methods, making it more suitable for "big data" applications.
  • Accuracy: The hybrid QR-GA approach consistently outperformed standalone RRQR. For example, on the Ovarian dataset, QR-GA achieved 98% accuracy compared to RRQR's 85%.
  • Robustness: The proposed methods were tested against three different classifiers (KNN, SVM, and C4.5). The results showed that the RRQR-based selection was dependable across different learning models and particularly strong in terms of G-mean, a metric that measures performance on imbalanced data.

Discussion and Conclusion

The biggest takeaway is the realization that RRQR is a viable, faster alternative to SVD for feature selection. While SVD is the "gold standard" for subspace learning, RRQR provides the unique benefit of the permutation matrix, which maps directly back to the original features. Furthermore, by using RRQR as a pre-filter, the authors solve a common problem with Genetic Algorithms: the massive search space. Removing redundant features first prevents the GA from getting stuck in "local optima" and speeds up convergence.

Future work could involve adaptive structure learning for the NMF-QR approach, allowing the affinity matrix to update automatically during the optimization process, and exploring multi-class high-dimensional data beyond binary datasets.

Summary updated

Abstract

The selection of most informative and discriminative features from high-dimensional data has been noticed as an important topic in machine learning and data engineering. Using matrix factorization-based techniques such as nonnegative matrix factorization for feature selection has emerged as a hot topic in feature selection. The main goal of feature selection using matrix factorization is to extract a subspace which approximates the original space but in a lower dimension. In this study, rank revealing QR (RRQR) factorization, which is computationally cheaper than singular value decomposition (SVD), is leveraged in obtaining the most informative features as a novel unsupervised feature selection technique. This technique uses the permutation matrix of QR for feature selection which is a unique property to this factorization method. Moreover, QR factorization is embedded into non-negative matrix factorization (NMF) objective function as a new unsupervised feature selection method. Lastly, a hybrid feature selection algorithm is proposed by coupling RRQR, as a filter-based technique, and a Genetic algorithm as a wrapper-based technique. In this method, redundant features are removed using RRQR factorization and the most discriminative subset of features are selected using the Genetic algorithm. The proposed algorithm shows to be dependable and robust when compared against state-of-the-art feature selection algorithms in supervised, unsupervised, and semi-supervised settings. All methods are tested on seven available microarray datasets using KNN, SVM and C4.5 classifiers. In terms of evaluation metrics, the experimental results shows that the proposed method is comparable with the state-of-the-art feature selection.
BibTeX
@misc{moslemi2022subspace,
  author = {Amir Moslemi and Arash Ahmadian},
  title = {{Subspace Learning for Feature Selection via Rank Revealing QR Factorization: Unsupervised and Hybrid Approaches with Non-negative Matrix Factorization and Evolutionary Algorithm}},
  year = {2022},
  eprint = {2210.00418},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.00418},
}
Figure