PaperlayerView exact revision on arXiv

Source-linked AI summary

Benchmarking Relief-Based Feature Selection Methods for Bioinformatics Data Mining

Ryan J. Urbanowicz, Randal S. Olson, Peter Schmitt, Melissa Meeker, Jason H. Moore

arXiv:1711.08477v2cs.LG

TL;DR

Biomedical data mining needs feature-selection methods that handle large, noisy, and complex datasets across varied data types. This paper implements and extends Relief-Based Algorithms in ReBATE, evaluates them against established methods in genetic simulations, and reports reliable performance across diverse problem types while identifying specific algorithm limitations.

  • Problem

    Biomedical feature selection requires methods that handle large feature spaces, noise, complex associations, varied data types, and computational constraints.

  • Method

    The paper implements and extends Relief-Based Algorithms in ReBATE and evaluates them, including MultiSURF, against established feature-selection methods across genetic simulations.

  • Results

    RBAs show flexible feature-selection performance across diverse dataset configurations, while the study identifies limitations of specific algorithms.

  • Takeaways & Limitations

    MultiSURF* performs best for explicitly identifying pure 2-way interactions, whereas MultiSURF provides the most reliable performance across a wide range of problem types.

  • Takeaways & Limitations

    The study recommends expanding the diversity of simulation studies in future work.

Abstract

from arXiv · show

Modern biomedical data mining requires feature selection methods that can (1) be applied to large scale feature spaces (e.g. `omics' data), (2) function in noisy problems, (3) detect complex patterns of association (e.g. gene-gene interactions), (4) be flexibly adapted to various problem domains and data types (e.g. genetic variants, gene expression, and clinical data) and (5) are computationally tractable. To that end, this work examines a set of filter-style feature selection algorithms inspired by the `Relief' algorithm, i.e. Relief-Based algorithms (RBAs). We implement and expand these RBAs in an open source framework called ReBATE (Relief-Based Algorithm Training Environment). We apply a comprehensive genetic simulation study comparing existing RBAs, a proposed RBA called MultiSURF, and other established feature selection methods, over a variety of problems. The results of this study (1) support the assertion that RBAs are particularly flexible, efficient, and powerful feature selection methods that differentiate relevant features having univariate, multivariate, epistatic, or heterogeneous associations, (2) confirm the efficacy of expansions for classification vs. regression, discrete vs. continuous features, missing data, multiple classes, or class imbalance, (3) identify previously unknown limitations of specific RBAs, and (4) suggest that while MultiSURF* performs best for explicitly identifying pure 2-way interactions, MultiSURF yields the most reliable feature selection performance across a wide range of problem types.

1. Introduction

The paper motivates Relief-Based Algorithms (RBAs) as flexible filter methods for complex biomedical feature-selection problems and evaluates core algorithms across diverse data configurations. It focuses on identifying reliable methods for heterogeneous associations, interactions, and challenging feature spaces.

  • Relief-Based Algorithms: RBAs retain filter-method advantages: relatively fast computation and feature selections independent of the induction algorithm.Their asymptotic time complexity is O(instances^2 · features).
  • Relief-Based Algorithms: RBAs are the only known filter methods able to capture feature dependencies, including gene-gene interactions, when predicting outcomes.Relief’s nearest-neighbor instances support the calculation of feature weights used to detect these dependencies.
  • Motivation: Many RBA implementations were limited to clean binary-classification problems with discrete features, restricting applications to gene expression, quantitative traits, and integrated omics data.The paper addresses classification, regression, missing data, multiple classes, class imbalance, and discrete or continuous features.
  • Research Questions: The study asks which core Relief algorithm is most effective and reliable, while noting that iterative expansions for very large feature spaces require future investigation.The work focuses exclusively on the first question because core algorithms underpin iterative expansions.
  • Bioinformatics Context: The paper addresses a lack of guidance and large-scale comparisons across RBAs for noisy, high-dimensional, mixed-type, incomplete, imbalanced, epistatic, and heterogeneous datasets.These characteristics are common in genetic association problems and complicate feature-selection evaluation.
  • Study Contributions: The authors implement ReBATE, introduce MultiSURF, extend algorithms across data types, and compare 13 feature-selection methods using 2280 simulated datasets.The comparison includes eight RBAs, three traditional filter methods, and two wrapper methods.

2. Methods

The methods section describes ReBATE, the proposed MultiSURF algorithm, data-type extensions, comparison methods, simulation design, and evaluation metrics.

  • ReBATE: ReBATE implements established Relief-Based Algorithms and the proposed MultiSURF algorithm.The methods also describe strategies for extending the algorithms to varied data types.
  • Evaluation: The evaluation compares filter- and wrapper-based feature-selection methods.The section covers the comparison methods, simulation study design, and evaluation metrics.

2.1. ReBATE

ReBATE restructures Relief-Based algorithms into a modular, data-type-flexible framework and introduces MultiSURF alongside extensions for regression and missing data. The framework preserves computational efficiency while supporting broader data types and endpoints.

  • Data-type flexibility: ReBATE preserves support for continuous features, multi-class endpoints, regression, and missing data while restructuring earlier implementations for efficiency and modularity.Earlier Java implementations handled complete discrete binary data, whereas later extensions supported broader data types but were less computationally efficient.
  • Framework and algorithms: ReBATE implements five core RBAs, including the proposed MultiSURF, in a modular framework designed for efficient development and application.The core algorithms are ReliefF, SURF, SURF*, MultiSURF*, and MultiSURF.
  • Data preprocessing: The framework automatically detects feature and endpoint types, class structure, numerical ranges, and missing-data indicators to adapt each RBA.This preprocessing distinguishes discrete from numerical variables and binary from multi-class endpoints.
  • ReliefF procedure: ReliefF updates feature weights using differences between each target instance and nearest same-class hits or opposite-class misses.All training instances are used as targets, and scores range from -1 to +1.
  • MultiSURF: MultiSURF retains MultiSURF* features but removes the far-instance scoring introduced in SURF*.The proposed variant is closely related to MultiSURF* while changing how far instances contribute to scoring.
  • Extensions: The study proposes a simpler regression approach than RReliefF’s standard method and an agnostic missing-data strategy that integrates with all RBAs and data-type extensions.The authors describe the missing-data strategy as the first fully agnostic approach implemented and tested in RBAs.

2.2. Evaluation

The evaluation compares Relief-Based and established feature-selection methods across a broad simulation panel designed to vary association patterns, data types, noise, and endpoint structure. It uses known simulation ground truth to assess how reliably methods rank relevant features.

  • Study design: The study compares 13 feature-selection approaches across 2280 simulated datasets representing varied problems and data types.The comparison includes five ReBATE algorithms, three ReliefF settings, and five established non-RBA methods.
  • ReliefF settings: The benchmark includes ReliefF neighbor settings from fixed k values to dataset-dependent percentages, testing how neighbor counts affect performance.For 1000 instances, ReliefF 10% NN uses 100 total neighbors, corresponding to k = 50 hits and 50 misses.
  • Comparator methods: Established comparators include ExtraTrees, RFE ExtraTrees, chi-squared, ANOVA F-value, and mutual information.RFE ExtraTrees iteratively recalculates importance after removing features and is expected to be the most computationally expensive evaluated method.
  • Evaluation rationale: Simulation ground truth identifies relevant features, association patterns, signal magnitude, and achievable downstream accuracy, enabling power analyses over dataset replicates.This allows direct evaluation of feature-selection success rates.
  • Simulation conditions: The simulations vary main effects, 3-way interactions, genetic heterogeneity, continuous and mixed features, multi-class and continuous endpoints, missingness, and class imbalance.The design extends beyond core pure 2-way epistatic SNP datasets.
  • Illustrative result: RFE ExtraTrees ranks all relevant features within the top 67% of features for at least 80% of datasets in the noisy 3-way interaction example.The result is reported from the Figure 2 analysis.

3. Results

Across core 2-way epistatic datasets, algorithm power varies with problem difficulty, neighborhood settings, and scoring strategy. MultiSURF is competitive with SURF, while far-scoring variants generally perform better on difficult epistatic problems.

  • Core 2-way epistasis: The three myopic filters—chi square, ANOVA F-test, and mutual information—fail to rank relevant 2-way interaction features.Their performance is described as being on par with the random shuffle negative control.
  • Core 2-way epistasis: Power generally decreases with lower heritability, smaller training sets, and harder model architectures.The simulation spans configurations from easy cases at the upper right to difficult cases at the lower left.
  • ReliefF settings: ReliefF 100 NN fails when n = 200, whereas k = 100 performs well for sample sizes from 400 to 1600.The appropriate neighborhood size depends on the dataset size.
  • ReliefF settings: ReliefF using all instances as neighbors becomes unable to detect 2-way interactions because it effectively removes neighborhood proximity.This behavior is empirically verified in the core interaction results.

3.2. Main Effects

Main-effect datasets expose a contrast between myopic filters and far-scoring RBAs. Standard ReliefF, SURF, and MultiSURF succeed broadly, whereas SURF* and MultiSURF* lose performance, especially on easy main-effect models.

  • Single-feature main effects: Chi square, ANOVA F-test, and mutual information generally identify single-feature main effects.Mutual information is least successful when heritability is low and the model is hard.
  • Main-effect algorithm comparison: SURF* and MultiSURF* show substantial performance loss on main effects, including easy models and additive multi-feature effects.The loss is particularly notable because these are the two algorithms using far scoring.
  • Main-effect algorithm comparison: ReliefF, SURF, and MultiSURF are completely successful on the reported single-feature main-effect datasets.This contrasts with the losses observed for SURF* and MultiSURF*.
  • Main-effect algorithm comparison: Across main-effect datasets, MultiSURF* loses less performance than SURF*.The comparison applies to both single-feature and additive main-effect analyses reported here.

3.3. Genetic Heterogeneity

The study evaluates Relief-Based algorithms on heterogeneous associations between independent 2-way interactions. RBAs handle these heterogeneous epistatic patterns, whereas other tested methods fail or perform poorly.

  • Heterogeneity definition: The simulations model two independent 2-way interactions whose relevance changes across subsets of training instances.Each subset contains a different relevant interacting feature pair.
  • Motivation: Heterogeneous association patterns are treated as an important feature-selection target because they are recognized in biomedical problems and can confound traditional machine-learning approaches.The paper motivates evaluating methods that can account for these patterns.
  • Heterogeneous associations: All tested RBAs handle heterogeneity concurrently modeled with epistatic interactions, while all other methods fail or fail to perform nearly as well.The paper identifies this as its first formal evaluation of RBAs on heterogeneous association patterns.
  • Algorithm comparison: With a 75:25 heterogeneity ratio, MultiSURF* and MultiSURF perform best, with SURF* and ReliefF using larger k settings close behind.The ratio indicates the proportion of instances in which each interaction is relevant.

3.4. 3-way Epistasis

For 3-way epistatic datasets, only RBAs using the smallest neighborhoods succeed, including MultiSURF. The results reinforce that neighborhood size relative to sample size matters for higher-order interactions.

  • Simulation scope: The section examines RBA performance on epistatic interactions with dimensionality higher than 2.The study explicitly extends beyond 2-way interactions to 3-way interactions.
  • Simulation scope: The 3-way simulations use heritability = 0.2 because GAMETES could not generate a 3-way dataset with heritability 0.4.This constraint follows from mathematical limitations of the simulation software.
  • 3-way epistasis: Only ReliefF with 10 or 100 nearest neighbors, ReliefF with 10% NN, and MultiSURF succeed on the 3-way interaction problem.Myopic methods and ExtraTrees wrappers fail to perform well on this problem.
  • Neighborhood size: The successful 3-way methods use the smallest numbers of neighbors in scoring.This pattern is consistent with the preceding 2-way interaction findings.
  • Neighborhood size: ReliefF performs well with 10, 100, or 80 nearest hits and misses at n = 1600 but completely fails with 400.The results support using a low neighbor count relative to n.

3.5. Number of Features

As feature spaces grow, performance diverges: myopic methods miss interactions, some wrappers become impractical, and MultiSURF* remains comparatively strong at 10,000 features.

  • Myopic approaches fail to detect 2-way interactions, while random forest wrappers are the next methods to fail as feature-space size increases.
  • At 10,000 features, ReliefF with k = 10 begins to fail, suggesting few neighbors perform less well in noisy, expanding feature spaces.
  • At 10,000 features, MultiSURF* appears to perform slightly better than the rest.
  • At 100,000 features, none of the methods perform particularly well on their own, although they remain better than a random shuffle.
  • Most RBAs demonstrate > 80% power to rank predictive features above the 60th percentile, while MultiSURF* alone has significant power above the 50th percentile.
  • MultiSURF achieves full power at approximately the 80th percentile, and iterative approaches can remove low-ranking features without losing relevant features.

3.6. XOR Benchmarks

On clean XOR benchmarks, non-myopic methods generally detect lower-order interactions, but higher-order interactions expose strong dependence on neighborhood size and method choice.

  • All non-myopic methods solve the 2-way XOR with little trouble, whereas 3-way XOR success favors RBAs using fewer neighbors and ExtraTrees.
  • For 3-way, 4-way, and 5-way analyses, RBAs using larger neighbor proportions consistently ranked relevant features with the lowest overall scores.
  • In specific high-order interaction problems, relevant features receive the most negative score updates rather than random-shuffle-like scores.
  • The only method able to solve all XOR problems is RFE ExtraTrees, with ReliefF using 10 neighbors next best.
  • MultiSURF fails on the 4-way and 5-way XOR problems, indicating that higher-order interactions can challenge RBAs unless they use few neighbors.

3.7. Multiplexer Benchmarks

Multiplexer benchmarks test whether methods can rank address bits above register bits when all features are predictive in at least one training subset.

  • Multiplexer power measures ranking address bits, important across all instances, above register bits, important only within subsets.
  • ReliefF with 10% NN performs perfectly across all multiplexer datasets, followed by MultiSURF*, SURF*, and MultiSURF.
  • All features are technically predictive, particularly in the 6-bit problem, making the results difficult to interpret as simple relevance detection.
  • MultiSURF* feature weighting facilitated solving the 135-bit multiplexer benchmark directly and had previously ranked address bits above other features.
  • The results emphasize that RBAs can detect relevant features amid both feature interactions and heterogeneous patterns.

3.8. Data Types

RBAs accommodate several endpoint, class, missing-data, and feature-type configurations, but mixed feature types and some neighborhood choices remain problematic.

  • All RBAs succeeded across most tested data-type configurations, while random forest methods performed slightly worse than RBAs for continuous endpoints.
  • All feature-selection methods solved the multi-class configurations, indicating efficacy of the Relief multi-class expansion adopted in ReBATE.
  • For continuous endpoints with underlying 2-way interactions, all but myopic methods ranked features ideally, supporting the proposed continuous-feature diff function.
  • Scikit-learn methods could not complete missing-data analyses because scikit-learn does not handle missing data without preprocessing such as removal or imputation.
  • At 90:10 class imbalance, ReliefF with 50% neighbors failed, while other RBAs generally performed optimally despite slight deficits for ReliefF with 100 NN and SURF.
  • With 50% missing data, all ReliefF methods performed optimally except ReliefF 10 NN, suggesting more neighbors improve resilience to missingness.
  • None of the methods handled mixed discrete and continuous features optimally; MultiSURF* performed best, followed by MultiSURF, SURF*, and selected ReliefF variants.

4. Discussion

The discussion explains how Relief-Based algorithms generate score contributions and why far-neighbor scoring improves pure 2-way interaction detection but can impair main-effect detection.

  • 4.1. 2-way Epistastis Performance Gains: Table 3 traces each target instance’s nearest and farthest hits and misses, recording feature differences and shared values relevant to ReBATE scoring.Ties receive half credit because only one tied instance can contribute at a time.
  • 4.1. 2-way Epistastis Performance Gains: All five scoring approaches assign positive scores to interacting features A1 and A2 and a negative score of −8 to irrelevant feature A3.Thus, each method can distinguish relevant from irrelevant features in this pure 2-way interaction example.
  • 4.1. 2-way Epistastis Performance Gains: Far scoring in SURF* and MultiSURF* increases the score difference between relevant and irrelevant features by reinforcing interacting-feature scores through a larger scoring sample size.The example attributes this gain to far-neighbor contributions in the context of 2-way interactions.
  • 4.1. 2-way Epistastis Performance Gains: The example does not explain performance differences between SURF* and MultiSURF* for detecting 2-way interactions, which may involve MultiSURF*’s threshold calculation and/or scoring.The passage presents these as likely explanations rather than established causes.
  • 4.2. Main Effects Performance Losses: The conceptual main-effect scenario explains these losses using expected combinations of distance, class, and feature-value agreement to estimate instance-type frequencies.It distinguishes high, medium, and low frequencies according to the number of likely and unlikely combinations.
  • 4.2. Main Effects Performance Losses: For main effects, ReliefF, SURF, and MultiSURF are expected to perform as well as or better than SURF* and MultiSURF* because far scoring can introduce negative contributions.The stated failure mechanisms are farthest-miss different-value or farthest-hit same-value contributions.

5. Conclusions and Future Study

The study presents ReBATE and MultiSURF, then uses broad comparisons to characterize when Relief-based algorithms succeed, fail, and remain computationally practical. MultiSURF is the most generally flexible and successful method, while MultiSURF* is strongest for explicitly detecting 2-way epistasis.

  • Contributions: The authors introduced ReBATE as an open-source, user-friendly, data-type-flexible software package for Relief-based feature selection.The framework implements and expands multiple Relief-based algorithms and supports comparison with established feature-selection methods.
  • Contributions: The study compared Relief-based algorithms with established feature-selection methods across diverse simulated dataset configurations.The comparisons included different feature-selection methods, data types, endpoints, and dataset problems.
  • General conclusions: MultiSURF* performs best for detecting 2-way epistatic interactions, whereas far scoring improves 2-way interaction detection but can hinder simple main-effect detection.The study identifies a trade-off between interaction detection and main-effect detection for SURF* and MultiSURF*.
  • General conclusions: MultiSURF and ReliefF detect main effects, heterogeneous associations, and 2- or 3-way interactions, while only selected lower-neighbor methods detect 3-way interactions.ReliefF 10 NN and MultiSURF are identified as methods capable of detecting 3-way interactions.
  • General conclusions: MultiSURF is the most generally flexible and successful method, while ReliefF requires a user-specified k parameter that can dramatically affect success.The impact of k depends on noise, heritability, training-instance count, feature-space size, heterogeneity, interaction dimensionality, and missing data.
  • Practical implications: MultiSURF scales competitively as feature-space size increases, and its core computational complexity is slightly lower than MultiSURF* while RBAs have asymptotic complexity O(n^2 · a).The paper translates these findings into general recommendations for applying RBA feature selection.
  • Future study: The authors identify unresolved directions involving missing data, mixed feature types, higher-dimensional interactions, adaptive neighbor selection, and scaling to very large feature spaces.Future work also targets practical feature-space boundaries where RBA performance becomes unreliable.
Loading 1711.08477v2…