QAOA-based MRMR Algorithm for Feature Selection

As the volume of data for classification tasks in machine learning grows, feature selection plays an increasingly crucial role in enhancing the efficiency and effectiveness of these tasks. Existing classical feature selection algorithms often encounter challenges, such as high computational complexity and vulnerability to local optima. Quantum algorithms have been proposed to overcome these limitations. Here, our work proposes a new approach that combines the Quantum Approximate Optimization Algorithm (QAOA) with the classical feature selection algorithm Maximum Relevance-Minimum Redundancy (MRMR). First, we transform the feature selection problem into the Quadratic Unconstrained Binary Optimization (QUBO) problem. Then, we map the QUBO formulation to Hamiltonian with the Ising model. Finally, we employ QAOA with a shallow circuit to search this Hamiltonian's ground state, which matches the specific solution for feature selection. We conducted numerical experiments on eight real-world datasets for classification tasks from diverse domains, including finance, medicine, and natural hazards. Experiment results suggest that QAOA-selected feature subsets size are typically less than half the complete set while achieving comparable or better classification accuracy than classical MRMR, demonstrating its preference for smaller, more efficient feature subsets.