Stability-Aware QUBO Feature Selection for Tabular Classification Under Repeated Nested Cross-Validation

Abstract

Quadratic Unconstrained Binary Optimization (QUBO) provides a principled framework for feature selection by encoding relevance–redundancy trade-offs and explicit constraints directly in a combinatorial objective. This study presents a stability-aware QUBO pipeline for tabular binary classification, evaluated on two standard benchmarks, namely Breast Cancer Wisconsin Diagnostic (569 samples, 30 features) and Pima Indians Diabetes (768 samples, 8 features; clinically invalid zeros treated as missing and imputed within folds). We study four QUBO variants spanning a base relevance–redundancy formulation, an exact-cardinality formulation enforcing a fixed budget k, a stability-regularized formulation that incorporates bootstrap uncertainty estimates of relevance and redundancy directly into the QUBO objective, and a performance-weighted relevance variant based on inner-CV univariate utility. All methods are assessed under repeated nested stratified cross-validation (5 outer folds × 3 repeats, n = 15 outer test evaluations), reporting AUC-ROC, AUC-PR, MCC, and Brier score with 95% confidence intervals, alongside selection stability via mean Jaccard similarity across outer-fold selected subsets. Results show that QUBO-based selection is competitive with strong classical baselines (RFECV, L1-logistic, permutation-importance ranking, and mutual information) while enabling strict budget control and transparent stability diagnostics. On the near-ceiling Breast Cancer benchmark, predictive differences are marginal and the main differentiators become subset-size control and stability; on Pima, QUBO-k remains competitive while enforcing strict cardinality constraints. These findings support QUBO as a practical framework when budgeted, interpretable, and reproducible feature selection is required, though evaluation is limited to low-dimensional tabular settings.