Feature space reduction method for ultrahigh-dimensional, multiclass data: Random forest-based multiround screening (RFMS)

Technical Summary: Random Forest-Based Multiround Screening (RFMS)

Problem Statement
The paper addresses the challenge of feature space reduction in ultrahigh-dimensional datasets containing hundreds of thousands of features and thousands of classes. While numerous screening methods exist for ultrahigh-dimensional data, most fail to handle multiclass response variables effectively. This specific problem arises frequently in biometric authentication (e.g., signature verification, gait analysis) and neuroscience, where prediction models must authenticate users based on multichannel data. Traditional variable selection methods often struggle to identify the optimal set of active predictors in such high-dimensional spaces, and dimensionality reduction techniques like Principal Component Analysis (PCA) have been reported to yield unsatisfactory results. Furthermore, existing screening methods often lack the capacity to examine higher-order interactive and nonlinear structures inherent in these datasets.

Methodology
The authors propose Random Forest-based Multiround Screening (RFMS), a novel algorithm designed to handle ultrahigh-dimensional, multiclass data. The method operates by dividing the feature space into smaller subsets and executing a series of partial model builds to iteratively distill a high-performing subset of features.

The algorithm proceeds as follows:

1. Preparation: The input feature vector $x$ (containing $n$ features) is randomly permuted and divided into $m$ subsets of size $\alpha$.
2. Iteration (Tournament-based Sorting): The algorithm processes these subsets sequentially. In each round $i$, it concatenates the current subset with the top $\beta$ features selected from the previous round ($z_{i-1}$). A Random Forest (RF) classifier is trained on this combined set to determine feature importance based on selection frequency (the number of times a feature appears in the classification forest).
3. Selection: The top $\beta$ most important features from the current round are retained and passed to the next iteration.
4. Result: After processing all subsets, the final set of $\beta$ features represents the most informative subset identified by the algorithm.

The method is implemented in a publicly available Julia package. To benchmark RFMS, the authors utilized BiometricBlender, a synthetic data generator that creates ultrahigh-dimensional, multiclass feature spaces with known ground truth and feature usefulness parameters. The test dataset consisted of 100 classes, 64 samples per class, 10,000 features (100 true, 300 fake, and others), and intercorrelated structures.

Key Contributions

• Novel Algorithm: Introduction of RFMS, a method specifically tailored for ultrahigh-dimensional, multiclass problems where traditional screening fails.
• Iterative Refinement: Unlike static screening, RFMS uses a tournament-style, round-based approach to iteratively refine feature selection, allowing for the identification of nonlinear and interactive structures.
• Transformation-Free Output: Unlike Factor Analysis (FA) or PCA, RFMS outputs a subset of the original features rather than a transformed feature space. This preserves interpretability and allows for the computation of only the selected features in production environments.
• Benchmarking: Comprehensive evaluation against industry-standard methods (PCA, FA, k-best) using synthetic biometric data and proprietary real-world biometric datasets.

Results
The study compared RFMS against PCA, FA, and k-best screening using three classifiers: k-Nearest Neighbors (kNN), Support Vector Classifier (SVC), and Random Forest (RF).

• Accuracy: RFMS and FA outperformed PCA and k-best. The highest accuracy (61.4%) was achieved by both the RFMS–SVC and FA–RF combinations. Notably, RFMS demonstrated superior robustness across different classifiers; while FA–RF performed well, FA combined with kNN or SVC yielded significantly lower accuracy (10% and 42%, respectively). In contrast, RFMS maintained high performance across all three classifiers (e.g., 38.1% for kNN, 61.4% for SVC).
• Robustness: RFMS showed greater stability regarding the number of screened features. Reducing the feature count from 500 to 100 only slightly decreased RFMS accuracy (from ~61% to 55.4%), whereas FA accuracy dropped precipitously (from ~61% to 25%) under similar reductions.
• Efficiency: While the initial screening time for RFMS was longer (approx. 11,000s) compared to FA or PCA, the authors note that screening is performed infrequently compared to model fitting. Furthermore, RFMS hyperparameters can be adjusted to reduce screening time significantly (e.g., to ~2,143s) with minimal impact on accuracy.
• Proprietary Data: On a proprietary dataset (10,000 classes, 81,000 samples), RFMS-filtered features achieved up to 93% classification accuracy, outperforming FA-transformed features (approx. 82%), though with a longer screening time.

Significance and Claims
The paper claims that RFMS is "on par with industry-standard feature screening methods" while offering distinct advantages in flexibility, robustness, and operation. The primary significance lies in its ability to effectively screen ultrahigh-dimensional, multiclass data—a domain where few existing methods are applicable.

The authors emphasize that RFMS provides a transformation-free solution, which is critical for production systems where computational cost and interpretability are paramount. By selecting a subset of original features, the method avoids the need to compute the full feature set for every new sample, potentially saving significant time and resources.

The paper concludes modestly, acknowledging that the synthetic data generator (BiometricBlender) does not yet fully reproduce all properties of real data that challenge feature screeners, particularly regarding Factor Analysis performance. Consequently, the authors suggest that future work should focus on refining the data generator and optimizing RFMS hyperparameters (e.g., automatic determination of feature retention, parallelization, and alternative tournament scoring) to further improve accuracy and computational efficiency.