Source-linked AI summary
Relief-Based Feature Selection: Introduction and Review
Ryan J. Urbanowicz, Melissa Meeker, William LaCava, Randal S. Olson, Jason H. Moore
TL;DR
High-dimensional biomedical data make feature selection computationally burdensome, while methods must retain sensitivity to complex associations such as interactions. This paper introduces and reviews Relief-based algorithms, synthesizing their behavior, methodological branches, computational properties, data adaptations, and software availability.
Problem
High-dimensional feature spaces increase modeling difficulty and computational burden, motivating efficient feature selection that remains sensitive to informative complex associations.
Method
The paper situates Relief-based algorithms within feature selection, introduces Relief and its interpretation, and reviews RBA methodological research and comparative algorithm properties.
Results
RBAs generally detect univariate effects and 2-way interactions, scale linearly with feature count, and scale quadratically with training-instance count.
Takeaways & Limitations
RBAs offer a filter-style approach that combines interaction sensitivity with favorable scaling in the number of features, while supporting comparative evaluation across data characteristics and implementations.
Takeaways & Limitations
RBA performance deteriorates when irrelevant features become large in number, and interpreting whether a high score reflects a linear effect or an interaction is left to downstream modeling.
Abstract
from arXiv · showhide
Feature selection plays a critical role in biomedical data mining, driven by increasing feature dimensionality in target problems and growing interest in advanced but computationally expensive methodologies able to model complex associations. Specifically, there is a need for feature selection methods that are computationally efficient, yet sensitive to complex patterns of association, e.g. interactions, so that informative features are not mistakenly eliminated prior to downstream modeling. This paper focuses on Relief-based algorithms (RBAs), a unique family of filter-style feature selection algorithms that have gained appeal by striking an effective balance between these objectives while flexibly adapting to various data characteristics, e.g. classification vs. regression. First, this work broadly examines types of feature selection and defines RBAs within that context. Next, we introduce the original Relief algorithm and associated concepts, emphasizing the intuition behind how it works, how feature weights generated by the algorithm can be interpreted, and why it is sensitive to feature interactions without evaluating combinations of features. Lastly, we include an expansive review of RBA methodological research beyond Relief and its popular descendant, ReliefF. In particular, we characterize branches of RBA research, and provide comparative summaries of RBA algorithms including contributions, strategies, functionality, time complexity, adaptation to key data characteristics, and software availability.
1. Background
Feature selection identifies informative features within a data-mining pipeline, reducing dimensionality and computational burden while avoiding removal of features that matter. Methods differ in how they interact with model induction, motivating focused review of Relief-based approaches.
- Motivation: Feature selection identifies relevant features while discarding irrelevant ones that increase modeling difficulty and computational burden.Poor selection can remove relevant features and create downstream consequences.
- Types of Feature Selection: Filter methods score features independently of model induction, whereas wrapper and embedded methods depend more directly on a chosen modeling algorithm.Filters are generally faster and reusable across modeling algorithms; wrappers retrain models for candidate subsets, while embedded methods integrate selection into model execution.
- Types of Feature Selection: Wrapper methods can target the best feature set for a specific model but are typically iterative and computationally intensive.Each subsequent feature subset requires training a new model, and computational complexity limits efficient use to simpler modeling methods.
- Relief-Based Feature Selection: Relief-based algorithms are reviewed as a family of filter-style methods designed to retain filter efficiency while detecting feature interactions without exhaustively evaluating feature combinations.Exhaustive subset searches quickly become computationally intractable in larger feature spaces.
- Scope of the Review: The review introduces Relief and ReliefF, organizes later RBA research into methodological branches, and compares algorithms by strategy, functionality, complexity, data adaptation, evaluation, and software availability.The paper also examines RBA evaluations and summarizes available software.
2. Introduction to Relief
Relief is a filter-style feature-selection algorithm that scores features by comparing randomly selected target instances with nearest hits and misses. Its scores can detect interactions without explicitly evaluating feature combinations, but performance depends on data characteristics and algorithm settings.
- Weight interpretation: Relief weights range from −1 to +1 and estimate a feature’s relevance to predicting the endpoint.The diff function supplies a proxy statistic for discrete and continuous feature comparisons.
- Algorithm: Relief samples m training instances, identifies each target’s nearest hit and miss, and updates feature weights from their value differences.Nearest hits share the target’s class; nearest misses have the opposite class.
- Weight updates: Differences from nearest misses increase a feature’s score, whereas differences from nearest hits decrease it.For the illustrated discrete-feature case, each update changes the weight by 1/m.
- Strengths and limitations: Relief has time complexity O(a·m·n), or O(a·n) when m < n, but its original form handled only binary classification and no missing data.Insufficient training cycles, noise affecting nearest neighbors, higher-order interactions, non-monotonic features, and many irrelevant features constrain performance.
- Interaction detection: Relief can identify interacting features through local comparisons without evaluating feature combinations.In a Boolean example, A1 had an estimated responsibility of 0.75, while interacting A2 and A3 each had 0.1875.
- Interaction detection: In a 2-way interaction example, Relief assigned final scores of 4 to relevant A1 and A2 and −8 to irrelevant A3.Nearest-hit comparisons showed differences for A3, while nearest-miss comparisons showed differences for A1 and A2.
3. A Review of Relief-based Algorithms
The review traces Relief-based algorithm development from Relief and ReliefF through adaptations for neighbors, iterations, efficiency, and data types, while comparing algorithmic strategies and computational costs.
- Relief and ReliefF: ReliefF became the most utilized RBA after extending Relief with k nearest hits and misses, improving weight-estimate reliability in noisy problems.A value of k = 10 was suggested from preliminary empirical testing and widely adopted.
- Relief and ReliefF: Relief variants addressed incomplete data through ReliefB–D and multi-class endpoints through ReliefE–F, with ReliefD and ReliefF selected as the preferred approaches.ReliefD uses a class-conditional probability when a feature value is missing; ReliefF aggregates misses across other classes using prior class probabilities.
- Efficiency and complexity: Under m = n, core Relief algorithms have asymptotic time complexity O(n^2 · a), and precomputing pairwise distances is more efficient than recalculating them for each target.The review decomposes runtime into initialization, pairwise distances, neighbor finding, and feature-weight updates.
- RBA research directions: Core RBA development focused on selecting or weighting neighbors, while another major direction extended scoring beyond a single pass through iterative implementations.The review organizes these directions alongside additional adaptations and efficiency approaches.
- Data-type adaptations: Most RBA variations target discrete-valued features with binary endpoints, while relatively little research has adapted RBAs to regression problems.The review also notes that many contributions were application-driven.
4. Conclusion
This review places Relief-based algorithms within feature selection, introduces their core concepts, and organizes methodological advances into four research branches. It concludes that RBAs balance complex-pattern detection, data-type flexibility, and computational efficiency, while identifying priorities for future improvement.
- Review scope: The review contextualizes RBAs within feature selection, introduces Relief and ReliefF, and distinguishes four thematic branches of RBA research.It also compares algorithms by contributions, strategies, functionality, complexity, data adaptation, and software availability.
- Conclusions about RBAs: RBAs generally detect both univariate effects and 2-way interactions without evaluating feature combinations.Their individual feature weights can also probabilistically guide downstream machine-learning methods.
- Conclusions about RBAs: RBAs scale linearly with the number of features but quadratically with the number of training instances.Their asymptotic time complexity is O(instances^2 · features), making large-instance problems computationally demanding.
- Conclusions about RBAs: Iterative and efficiency approaches offer solutions for scaling RBAs to very large feature spaces, and RBAs can operate as anytime algorithms.These strategies address the computational burden associated with larger feature spaces.
- Conclusions about RBAs: RBA success depends critically on selecting instance neighbors, while the family has been adapted to diverse data types and application domains.Implementations of a variety of RBAs are available, and ReliefF remains the family’s longstanding staple despite subsequent advances.
- Future research: Future research should improve instance weighting, neighbor selection, large-scale strategies, domain adaptation, parameter usability, and ensemble feature selection.The review specifically identifies temporal data, reduced user-defined parameters, and new ensemble strategies as development areas.