The feature selection problem: traditional methods and a new algorithm

TLDR

Feature selection is crucial for real‑world concept learning to accelerate learning and improve concept quality. The study introduces and theoretically examines a new algorithm, Rellef, that selects relevant features using a statistical method. The authors review prior feature‑selection methods, then introduce the Rellef algorithm that selects relevant features statistically, propose remedies for its limitations, and report comparative test results against other algorithms. Rellef is heuristic‑free, accurate with interacting features, noise‑tolerant, runs in linear time, though it may produce non‑optimal feature set sizes, and empirical comparisons confirm its theoretical advantages, making it a practical choice for real‑world feature selection.

Abstract

For real-world concept learning problems, feature selection is important to speed up learning and to improve concept quality. We review and analyze past approaches to feature selection and note their strengths and weaknesses. We then introduce and theoretically examine a new algorithm Rellef which selects relevant features using a statistical method. Relief does not depend on heuristics, is accurate even if features interact, and is noise-tolerant. It requires only linear time in the number of given features and the number of training instances, regardless of the target concept complexity. The algorithm also has certain limitations such as nonoptimal feature set size. Ways to overcome the limitations are suggested. We also report the test results of comparison between Relief and other feature selection algorithms. The empirical results support the theoretical analysis, suggesting a practical approach to feature selection for real-world problems.