A Branch and Bound Algorithm for Feature Subset Selection

1977/09/01 by Narendra, Fukunaga · 1,249 citations
Computer Science · Mathematics · #Advanced Image and Video Retrieval Techniques #Algorithm #Artificial intelligence #Branch and bound #Computational complexity theory #Computer science #Feature (linguistics) #Feature selection #Machine Learning and Data Classification #Mathematics #Metaheuristic Optimization Algorithms Research #Pattern recognition (psychology) #Selection (genetic algorithm) #Set (abstract data type)

paper · doi:10.1109/tc.1977.1674939

published in IEEE Transactions on Computers C-26(9), 917-922 (Institute of Electrical and Electronics Engineers)

openalex publication_date 1977/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/27

Abstract

A feature subset selection algorithm based on branch and bound techniques is developed to select the best subset of m features from an n-feature set. Existing procedures for feature subset selection, such as sequential selection and dynamic programming, do not guarantee optimality of the selected feature subset. Exhaustive search, on the other hand, is generally computationally unfeasible. The present algorithm is very efficient and it selects the best subset without exhaustive search. Computational aspects of the algorithm are discussed. Results of several experiments demonstrate the very substantial computational savings realized. For example, the best 12-feature set from a 24-feature set was selected with the computational effort of evaluating only 6000 subsets. Exhaustive search would require the evaluation of 2 704 156 subsets.

Cited by

• Higher-Order Chemical Sensing
• Wrappers for feature subset selection
• Biological shape characterization for automatic image recognition and diagnosis of protozoan parasites of the genus Eimeria
• A survey on feature selection methods
• Scalable branch-and-bound model selection with non-monotonic criteria including AIC, BIC and Mallows's C_p
• Hybrid genetic algorithms for feature selection
• Convex Relaxations for Subset Selection
• Quantum Adiabatic Feature Selection
• Provable Approximations for Constrained ℓ_p Regression
• MINERVA: Mutual Information Neural Estimation for Supervised Feature Selection
• Constrained Machine Learning: The Bagel Framework
• New crossover operators for multiple subset selection tasks
• HyEdge: Optimal Request Scheduling in Hybrid Edge Computing Environment
• Interactive Reinforcement Learning for Feature Selection with Decision Tree in the Loop
• Hybrid beamforming with dynamic subarrays and low-resolution PSs for mmWave MU-MISO systems
• Deep Learning Based Joint Resource Scheduling Algorithms for Hybrid MEC Networks
• Positive region preserved random sampling: an efficient feature selection method for massive data
• A General System for Heuristic Solution of Convex Problems over Nonconvex Sets
• Detecting Events and Patterns in Large-Scale User Generated Textual Streams with Statistical Learning Methods
• FSinR: an exhaustive package for feature selection
• Review and Evaluation of Feature Selection Algorithms in Synthetic Problems
• Stacked Auto Encoder Based Deep Reinforcement Learning for Online Resource Scheduling in Large-Scale MEC Networks
• A Novel Cross Entropy Approach for Offloading Learning in Mobile Edge Computing
• Optimal Transmit Antenna Selection Algorithm in Massive MIMOME Channels
• Distributed Resource Scheduling for Large-Scale MEC Systems: A Multi-Agent Ensemble Deep Reinforcement Learning with Imitation Acceleration
• Efficient Reinforced Feature Selection via Early Stopping Traverse Strategy
• Simplifying Reinforced Feature Selection via Restructured Choice Strategy of Single Agent
• A Distance-Based Branch and Bound Feature Selection Algorithm
• Continuous Optimization for Feature Selection with Permutation-Invariant Embedding and Policy-Guided Search
• A Novel Feature Selection Method for High-Dimensional Biomedical Data Based on an Improved Binary Clonal Flower Pollination Algorithm
• Multivariate Discretization for Set Mining
• Cache-Aided NOMA Mobile Edge Computing: A Reinforcement Learning Approach
• Gradient-based Sample Selection for Faster Bayesian Optimization
• IVFS: Simple and Efficient Feature Selection for High Dimensional Topology Preservation
• Elitist Binary Wolf Search Algorithm for Heuristic Feature Selection in High-Dimensional Bioinformatics Datasets. [europepmc]
• Multipass Target Search in Natural Environments. [europepmc]
• Monitoring ratio of carbon to nitrogen (C/N) in wheat and barley leaves by using spectral slope features with branch-and-bound algorithm. [europepmc]
• Orbit Angular Momentum MIMO with Mode Selection for UAV-Assisted A2G Networks. [europepmc]
• EEG Channel-Selection Method for Epileptic-Seizure Classification Based on Multi-Objective Optimization. [europepmc]
• Feature Selection based on the Local Lift Dependence Scale. [europepmc]
• Conditional MaxRS Query for Evolving Spatial Data. [europepmc]
• Benchmarking Analysis of the Accuracy of Classification Methods Related to Entropy. [europepmc]
• Use of relevancy and complementary information for discriminatory gene selection from high-dimensional gene expression data. [europepmc]
• An ontology-based approach to the analysis of the acid-base state of patients at operative measures. [europepmc]
• GMLM-CNN: A Hybrid Solution to SWIR-VIS Face Verification with Limited Imagery. [europepmc]
• Efficient cross-validation traversals in feature subset selection. [europepmc]
• Designing an Embedded Feature Selection Algorithm for a Drowsiness Detector Model Based on Electroencephalogram Data. [europepmc]
• A Comprehensive Review of Bio-Inspired Optimization Algorithms Including Applications in Microelectronics and Nanophotonics. [europepmc]
• Exploration of Alloying Elements of High Specific Modulus Al-Li Alloy Based on Machine Learning. [europepmc]
• Identification of Risk Factors for Relapse in Childhood Leukemia Using Penalized Semi-parametric Mixture Cure Competing Risks Model. [europepmc]
• EEG-Based Detection of Mild Cognitive Impairment Using DWT-Based Features and Optimization Methods. [europepmc]
• Integrating GWAS and machine learning for disease risk prediction in the Taiwanese Hakka population. [europepmc]

Related

• Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
• Review and Evaluation of Feature Selection Algorithms in Synthetic Problems
• A branch-and-bound feature selection algorithm for U-shaped cost functions
• Selecting Efficient Features via a Hyper-Heuristic Approach
• A Semidefinite Programming Based Search Strategy for Feature Selection with Mutual Information Measure