Benchmarking Relief-Based Feature Selection Methods for Bioinformatics Data Mining

In plain words

Biomedical datasets can have very large numbers of measurements, and only a few of them may matter for the outcome. Some of the important ones matter only in combination, or only for part of the population. Simple methods that score each measurement on its own miss these cases.

The Relief family of methods looks at the data from a different angle. For each example, it finds the most similar examples that have the same outcome and the most similar ones that have a different outcome. A measurement that separates a person from their look-alikes with different outcomes, but not from look-alikes with the same outcome, gets a higher score. Because the comparison is local, these methods can pick up interactions that single-feature tests miss.

This paper compares several members of this family on many simulated datasets where the right answer is known. It also introduces MultiSURF, a new variant. Its neighbour cut-off adapts to each example, and it ignores examples that sit close to the cut-off. The authors report that it works reliably across the widest set of conditions they tested, and that it has no setting that must be tuned.

TL;DR

• Relief-based algorithms (RBAs) score each feature by comparing every training instance with its nearest hits (same class) and misses (other class) §2.1 alg. 1.
• The paper benchmarks five core RBAs from the ReBATE package against five other feature-selection methods on 2280 simulated datasets §2.2 tab. 1.
• MultiSURF uses a per-instance threshold with a dead band and drops far-instance scoring §2.1.5 alg. 2.
• All core RBAs are extended to multi-class, continuous endpoints, missing values and mixed feature types §2.1.6–§2.1.8.
• Author-reported: MultiSURF is the most reliable across configurations; MultiSURF* is best for pure 2-way epistasis; MultiSURF fails 4-way and 5-way XOR §3.1 §3.6 §5.
• The official code (MIT) is the scikit-rebate package. It agrees with the paper on the core update rules, but differs in several places; see Paper vs code.

Problem

• Biomedical feature selection must handle large feature spaces, noise, interactions between features (epistasis), mixed feature types and heterogeneous associations §1 §1.2.
• Relief-based methods can detect feature interactions, which most filter methods cannot, but the family had been validated mainly on clean binary problems with discrete features §1 §2.1.
• Data-type extensions (continuous features, regression, multi-class, missing values) had been proposed earlier but not validated experimentally §2.1.
• No large comparison of core RBAs existed against other feature-selection methods over dataset characteristics such as noise, missingness, imbalance and feature count §1.2.
• The paper addresses only core (single-pass) RBAs. Iterative expansions such as TuRF are out of scope; the authors expect very large feature spaces to need an iterative method on top §1.1 §3.5.

Method

Notation: n is the number of training instances, a the number of features, W[A] the score of feature A, R_i the target instance, H its nearest hits and M its nearest misses §2.1.1.

Common structure (ReBATE). Every core RBA runs in three stages: pre-process the data, pre-compute the full n × n distance array, then choose neighbours and update the weight vector alg. 1 §2.1. Distances are Manhattan. Continuous features are pre-normalised to the range 0 to 1 for the distance computation §2.1.

Per-feature difference. Discrete features contribute 0 when the two values are equal and 1 otherwise eq. 1. Continuous features contribute the absolute difference divided by the feature's range (max − min) eq. 2 §2.1.1.

ReliefF. For each target instance, take the k nearest hits and the k nearest misses. Each hit lowers W[A] by its diff, and each miss raises it, with both sums divided by n·k alg. 1 §2.1.1. The paper states that dividing by n and k keeps the final scores within [−1, 1] regardless of class imbalance §2.1.1.

SURF. Replace the k cut-off with a radius T equal to the average distance over all instance pairs. Instances closer than T are the neighbours §2.1.2.

SURF*. Keep the SURF radius. Instances closer than T are "near" and instances farther than T are "far". Far instances are scored with the opposite sign of the near rule: for a far hit, a feature difference adds to the score, and for a far miss, a difference subtracts §2.1.3 fig. 1.

MultiSURF*. Replace the global T with a per-instance threshold T_i, the mean distance from the target to all other instances. Add a dead band of width σ_i, the standard deviation of those distances. Near means closer than T_i − σ_i/2 and far means farther than T_i + σ_i/2 §2.1.4. For far instances, the paper describes using the same-value rule instead of the difference rule, and the sign convention that goes with it is discussed in Paper vs code §2.1.4 tab. 5.

MultiSURF (proposed). Keep the MultiSURF* threshold and dead band, but drop far scoring. Only near instances with distance below T_i − σ_i/2 contribute §2.1.5. Hits and misses are counted (h and m). Each hit term is divided by n·h and each miss term by n·m alg. 2 §2.1.5. The paper says the counts account for imbalanced hit and miss numbers for each target §2.1.5.

# Feature difference for one target and one neighbour  [eq. 1] [eq. 2]
def diff(feature, first, second):
    # discrete feature: 0 if equal, 1 otherwise  [eq. 1]
    if is_discrete[feature]:
        if X[first, feature] == X[second, feature]:
            return 0.0
        return 1.0
    # continuous feature: normalised absolute difference  [eq. 2]
    gap = abs(X[first, feature] - X[second, feature])
    return gap / (max_value[feature] - min_value[feature])

# MultiSURF, binary endpoint  [alg. 2] [§2.1.5]
# Input:  X (n, a) feature values; y (n,) classes; dist (n, n) Manhattan
# Output: W (a,) feature scores in [-1, 1]
def multisurf(X, y, dist):
    n = number of training instances
    W = zeros(a)
    for i in range(n):
        # threshold and dead band from distances to all other instances
        others = all j != i, dist[i, j]
        T_i = mean(others)
        sigma_i = std(others)
        # only instances clearly inside the threshold are neighbours
        near = all j != i where dist[i, j] < T_i - sigma_i / 2
        hits = [j in near where y[j] == y[i]]
        misses = [j in near where y[j] != y[i]]
        h = len(hits)
        m = len(misses)
        for A in range(a):
            # hits lower the score, misses raise it; each sum is averaged
            hit_term = sum(diff(A, i, j) for j in hits) / (n * h)
            miss_term = sum(diff(A, i, j) for j in misses) / (n * m)
            W[A] = W[A] - hit_term + miss_term
    return W

The pseudocode above omits the empty-set case (h = 0 or m = 0), which the paper does not state. The code handles it differently; see Pitfalls.

Multi-class endpoint. The paper's ReliefF variant averages the miss contributions of each other class, weighted by that class's share of the selected misses (m_C / m) eq. 4. The original ReliefF weighting by prior probability P(C) eq. 3 is replaced because the radius in SURF-type methods can leave some miss classes out entirely. The same m_C / m weighting is used for SURF, MultiSURF and the near side of SURF* and MultiSURF* eq. 5 §2.1.6. For far instances in SURF* and MultiSURF*, the paper says the hit term is added and the miss term subtracted §2.1.6.

Regression (continuous endpoint). No change to the scoring formulas. A hit is an instance whose endpoint differs from the target's by less than σ_E, the standard deviation of the endpoint §2.1.7. A miss is any instance with |C_i − C_j| ≥ σ_E §2.1.7. The paper says this is a simpler alternative to RReliefF and does not compare the two §3.8 §5.

Missing data ("agnostic" treatment). Distances are computed over the features present in both instances and normalised by how many were compared. Missing values in a neighbour are skipped in weight updates for that feature, which also adjusts the h and m counts. If the target's own value is missing, its contribution for that feature is zero §2.1.8. The paper contrasts this with ReliefC, which uses the ReliefB approach to give a non-zero diff for a missing value and is only partly agnostic §2.1.8.

Mixed discrete and continuous features. The paper describes a ramp function from the literature, which needs two user thresholds, and says it is left as future work. The released code and the paper's conclusions describe a different, automatic version §2.1 §3.8 tab. 9. See Paper vs code.

Evaluation. Thirteen methods are compared: five core RBAs (ReliefF, SURF, SURF*, MultiSURF*, MultiSURF), three ReliefF neighbour settings beyond 10 NN (100 neighbours, 10% and 50% of instances), chi-squared, ANOVA F-test, mutual information, ExtraTrees and RFE ExtraTrees §2.2.1 §2.2.2.

Simulation design. 76 dataset configurations, 30 random replicates each, for 2280 datasets in total §2.2.3 tab. 1. Groups cover pure 2-way and 3-way epistasis, main effects, additive effects, heterogeneity, continuous and mixed features, continuous endpoints, missing data, imbalance, multi-class endpoints, XOR (2- to 5-way) and multiplexer (6- to 135-bit) problems tab. 1 §2.2.3.

Power analysis. For each replicate, rank all features by score. Find where the lowest-scoring relevant feature falls in that ranking. Power at a given percentile is the share of the 30 replicates in which all relevant features fall within it. Power of 0.8 or higher is treated as the success threshold §2.2.4 fig. 2. A random-shuffle control is included §2.2.4.

Hyperparameters

Results

Author-reported. Setup: simulated SNP and continuous datasets, 2280 in total, 13 methods, power analysis across percentiles of the feature ranking §2.2. Most results are shown only as heatmaps; the text gives no numeric values for them, so the table below uses the text's own words.

Paper vs code

Code: EpistasisLab/scikit-rebate at commit fc5ea5c85410c4df2d2de5741f06e45095fd8d1e (MIT). Repository links from the paper footnotes §2.1. Code citations are relative to the clone at raw/code/1711.08477/. The code was checked by reading it, not by running it.

• Far-instance sign for MultiSURF* (same-value rule). The paper's text says same-value far hits receive +1 and same-value far misses receive −1 §2.1.4. Its tables say the opposite: hits −1, misses +1 tab. 4 tab. 5. The code follows the tables: the far branch subtracts for same-valued hits and adds for same-valued misses scoring_utils.py and sums the far term with a plus sign scoring_utils.py. The text is internally inconsistent; the card uses the tables and the code.
• Multi-class formula. The code stores the summed difference for each miss class, not its mean scoring_utils.py. It then multiplies each class's sum by its share of the misses and by the number of other classes, and divides by m once more scoring_utils.py. Eq. 4 and eq. 5 weight each class's mean by m_C / m with no extra factor eq. 4 eq. 5. The code's form does not reduce to the paper's; this is read from the code and not tested.
• Default k. The paper calls k = 10 the widely adopted default §2.1. The code's default is 100 relieff.py. The percent rule matches the paper's example relieff.py §2.2.1.
• Mixed-data ramp. The paper's Methods describe a ramp with two user parameters and leave it for future work §2.1 §3.8. Its conclusions and tab. 9 say the authors implemented their own ramp §5. The code applies a ramp only when the data type is mixed: a difference counts as 1 if it exceeds the feature's standard deviation, and otherwise as the normalised difference scoring_utils.py. The paper does not describe this rule in Methods.
• Regression bound. Hits and misses follow the paper scoring_utils.py relieff.py. The code estimates σ_E with the sample standard deviation (ddof = 1) relieff.py. MultiSURF's dead band uses the population standard deviation (ddof = 0) multisurf.py. The paper does not specify either.
• SURF radius. The paper defines T as the average over all instance pairs §2.1.2. The code averages the full n × n distance matrix, which includes n zero self-distances on the diagonal surf.py relieff.py. That scales T by (n − 1)/n relative to the mean over distinct pairs. The effect is small for large n.
• Endpoint and feature type detection. The paper says ReBATE detects discrete and continuous types automatically §2.1 but does not give the rule. The code treats a feature or endpoint with more than 10 unique values as continuous surf.py. A 9-class endpoint is multi-class, and an 11-class endpoint is treated as continuous.
• Empty hit or miss set. The paper's formulas divide by h and by m alg. 2 §2.1.5. The code handles a zero count by keeping only the non-empty term, divided by n scoring_utils.py. The paper does not state this.
• Code version. The clone is the HEAD of the default branch at clone time. The paper's results were produced with an earlier version; the code's commit date is not the paper's date. This card does not check which version produced the published figures.
• Not checked. The benchmark datasets and analysis notebook in the separate rebate-benchmark repository §2.2.3 §2.2.4 were not cloned. The simulation generators (GAMETES and custom scripts) were not read, so the dataset descriptions in tab. 1 are taken from the paper only.

No other discrepancies found in the core RBA neighbour selection and per-feature difference rules.

Pitfalls

• Far-instance sign. Implementing MultiSURF* from the text gives the opposite sign for same-valued far instances than the tables and the code do. Follow the tables and the code; see Paper vs code.
• ReliefF k is per class. k counts hits and misses separately. With n = 200 and balanced classes, k = 100 uses every instance, which turns ReliefF into a myopic method. The paper reports that this setting fails at n = 200 §3.1.
• Empty neighbourhoods. MultiSURF's dead band can leave h or m at zero for some targets. The paper's formula then divides by zero. The code uses only the non-empty side scoring_utils.py. An implementation should decide this explicitly.
• Distance matrix cost. The method needs the full n × n distance matrix alg. 1 §2.1. The paper gives time in terms of n² but states no memory figure. For large n the matrix dominates memory.
• Standard deviations. Three different σ conventions are in use (regression bound, MultiSURF dead band, SURF mean). Pick one per term and test it; the difference is small for large n but not zero.
• Missing values. A missing target value contributes zero for that feature. A missing neighbour value is dropped from both the sum and the count scoring_utils.py scoring_utils.py. The paper notes that scikit-learn's feature-selection methods could not run on missing data, so preprocessing is needed for those baselines §3.8.
• Feature count. Table 1 gives 20 total features for the core groups tab. 1. The text describes 1000 features for the earlier-study setup §2.2.3. The card uses Table 1; confirm against the benchmark repository before reproducing.
• Redundancy. RBAs do not remove correlated features §1. A redundant pair scores both features highly, so a correlation filter is needed for a clean subset tab. 9.
• Multiplexer and XOR results. These are clean, noise-free synthetic benchmarks §3.6 §3.7. The paper says higher-order interactions are problematic for RBAs unless few neighbours are used in scoring §3.6.
• Iterative expansions. For very large feature spaces (over 10,000 features) the paper recommends an iterative method on top, such as TuRF; it was not benchmarked here §3.5 tab. 9.

Lineage

• Builds on: Relief and ReliefF (ReliefF is the basis for ReBATE's neighbour and diff rules) §2.1.1; SURF and SURF* (radius-based neighbours and far scoring) §2.1.2 §2.1.3; MultiSURF* (per-instance threshold and dead band) §2.1.4; TuRF, an iterative expansion §1.1.
• Compared against: chi-squared, ANOVA F-test and mutual information (filters); ExtraTrees and RFE ExtraTrees (random-forest wrappers) §2.2.2.
• Companion survey of Relief-based methods, cited in §1. Not checked against this wiki.
• Superseded by: not known from this wiki's content.