Relief-based feature selection

Overview

Relief-based algorithms (RBAs) score each feature from the local neighbourhood of every training instance. For a target instance, the nearest instances with the same endpoint are its hits, and the nearest with a different endpoint are its misses. A feature gains score when it differs between the target and its misses, and loses score when it differs between the target and its hits 1711.08477 §2.1 alg. 1.

The invariant all variants share is that hits lower a feature's score and misses raise it, with each sum scaled by the number of instances alg. 1 alg. 2. The authors state that ReliefF's scaling keeps the scores within −1 to 1 regardless of class imbalance 1711.08477 §2.1.1.

Because scores come from neighbours, not from a single feature's association with the endpoint, the paper says these methods can detect feature interactions that most filter methods cannot 1711.08477 §1. No classifier is trained during scoring.

Only one card on this wiki covers this concept so far, so this page describes one paper's family of variants. Its results are simulated, and the paper's contradictions are listed below.

Variants

All variants share the diff function. For discrete features it is 0 when the two values match and 1 otherwise. For continuous features it is the absolute difference divided by the feature's range, with features first scaled to 0–1 1711.08477 §2.1.1 eq. 1 eq. 2. Distance is Manhattan 1711.08477 §2.1.

ReliefF

Takes a fixed number k of nearest hits and k nearest misses for each target. Both sums are divided by n·k 1711.08477 §2.1.1 alg. 1. The paper calls k = 10 the widely adopted default 1711.08477 §2.1. Because k is counted separately for hits and misses, a small sample can use nearly every instance. The paper reports that k = 100 fails at n = 200 1711.08477 §3.1. Card: Urbanowicz et al., 2017.

SURF

Replaces k with a radius T, the average distance over all instance pairs. Instances closer than T are neighbours 1711.08477 §2.1.2. Card: Urbanowicz et al., 2017.

SURF*

Keeps the SURF radius and adds far scoring. Instances farther than T are "far" and scored with the opposite rule from near instances [arxiv:1711.08477 §2.1.3] fig. 1. SURF* is the only core variant that uses all instances in every update 1711.08477 §2.1.3. The paper reports a loss of power for SURF* and MultiSURF* on main-effect models, more so for easy models 1711.08477 §3.2. Card: Urbanowicz et al., 2017.

MultiSURF*

Replaces the global T with a per-instance threshold T_i, the mean distance from the target to all other instances. It adds 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 1711.08477 §2.1.4. Far instances use the same-value rule, because the authors expect differences to be more common among far instances 1711.08477 §2.1.4. The sign for that rule is contradictory in the paper; see Contradictions. Card: Urbanowicz et al., 2017.

MultiSURF (proposed)

Keeps the MultiSURF* threshold and dead band, but drops far scoring. Only near instances closer than T_i − σ_i/2 contribute 1711.08477 §2.1.5. The number of hits h and misses m can differ for each target, so each hit term is divided by n·h and each miss term by n·m alg. 2 1711.08477 §2.1.5. The authors describe this normalisation as accounting for imbalanced hit and miss counts 1711.08477 §2.1.5. Card: Urbanowicz et al., 2017.

Extensions to other data types

The paper extends all core variants to four cases. The scoring formulas stay the same in each case; what changes is how neighbours and weights are defined.

• Multi-class endpoints. The ReliefF weighting by class prior eq. 3 is replaced by a weighting by each miss class's share of the selected misses, m_C / m eq. 4 eq. 5. The paper says the prior weighting can leave a miss class out entirely under a radius rule, so the new weighting is used for all variants 1711.08477 §2.1.6. Card: Urbanowicz et al., 2017.
• Continuous endpoints. A hit is an instance whose endpoint differs from the target's by less than σ_E, the standard deviation of the endpoint. A miss is any instance at least σ_E away 1711.08477 §2.1.7. The paper calls this simpler than RReliefF and does not compare the two 1711.08477 §3.8 §5.
• Missing values. Distances use only the features present in both instances. A missing value in a neighbour is skipped for that feature, and a missing target value contributes zero 1711.08477 §2.1.8.
• Mixed discrete and continuous features. The Methods describe a ramp function with two user thresholds, left as future work. The conclusions state the authors implemented their own version 1711.08477 §2.1 §5 tab. 9. See Contradictions.

When to use which

The paper compares the variants on simulated data, so each row names the constraint and the paper's result for it.

Reported results

Author-reported throughout. The study uses 2280 simulated datasets from 76 configurations with 30 replicates each, and it compares 13 methods using a power analysis over percentiles of the feature ranking 1711.08477 §2.2 tab. 1. Most results appear only as heatmaps, so the text gives rankings, not numbers 1711.08477 §3.

Implementation sketch

The loop below is the common core of the variants. The neighbour rule is the only part that changes between them. Comments cite the source of each step. The empty-set guard is our choice; the paper's formula divides by h and m with no guard alg. 2.

# Relief-family scoring, common loop  [alg. 1] [alg. 2] [§2.1]
# Input:  X (n, a) feature values; y (n,) endpoint labels
# Output: W (a,) feature scores
def relief_scores(X, y, dist, neighbour_rule):
    n = number of training instances
    W = zeros(a)
    for i in range(n):
        # the variant decides hits and misses for target i:
        #   ReliefF:    k nearest of each class           [§2.1.1]
        #   SURF:       dist < T (mean over all pairs)    [§2.1.2]
        #   MultiSURF:  dist < T_i - sigma_i/2            [§2.1.5]
        hits, misses = neighbour_rule(i, dist, y)
        h = len(hits)
        m = len(misses)
        for A in range(a):
            # hits lower the score; misses raise it       [alg. 2]
            if h > 0:
                W[A] -= sum(diff(A, i, j) for j in hits) / (n * h)
            if m > 0:
                W[A] += sum(diff(A, i, j) for j in misses) / (n * m)
    return W

For MultiSURF, neighbour_rule computes T_i as the mean distance from instance i and sigma_i as its standard deviation, then keeps the instances closer than T_i − sigma_i/2 §2.1.5. ReliefF divides by n·k rather than n·h and n·m alg. 1. Far scoring in SURF* and MultiSURF* adds a second term with the opposite sign; see Contradictions before implementing it.

Contradictions

• Far-instance sign (MultiSURF* and SURF*). The text gives same-valued far hits +1 and same-valued far misses −1 1711.08477 §2.1.4, and gives differing far hits +1 and differing far misses −1 for SURF* 1711.08477 §2.1.3. The tables give the opposite signs for same-valued far hits and misses 1711.08477 tab. 4 tab. 5. The paper does not say which is meant. The released code follows the tables, not the text scoring_utils.py (see the paper-vs-code bullets below).
• Multi-class formula (paper vs code). Eq. 4 and eq. 5 weight each class's mean miss difference by m_C / m 1711.08477 §2.1.6 eq. 4 eq. 5. The code stores the summed difference per miss class, and then applies extra factors before dividing by m once more scoring_utils.py scoring_utils.py. The code's form does not reduce to the paper's. This comes from reading the code, not from running it.
• Mixed-data ramp (paper vs code). The Methods describe a two-threshold ramp left for future work 1711.08477 §2.1 §3.8. The conclusions and table 9 say the authors implemented their own ramp 1711.08477 §5 tab. 9. The code uses a rule that counts a difference as 1 when it exceeds the feature's standard deviation, and as the normalised difference otherwise scoring_utils.py. The paper's Methods do not describe this rule.
• Default k (paper vs code). The paper calls k = 10 the widely adopted default 1711.08477 §2.1. The code's default is 100 relieff.py.
• Feature count (within the paper). Table 1 gives 20 total features for the core groups 1711.08477 tab. 1. The prior-study description in the text gives 1000 features for an earlier setup 1711.08477 §2.2.3. The paper does not reconcile the two.
• Empty hit or miss sets (paper vs code). The paper's formulas divide by h and m with no guard 1711.08477 alg. 2 §2.1.5. The code keeps the non-empty side and divides it by n only scoring_utils.py.

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.
• ReliefF k is per class. k counts hits and misses separately. With n = 200 and balanced classes, k = 100 uses every instance, which makes ReliefF myopic 1711.08477 §3.1.
• Empty neighbourhoods. MultiSURF's dead band can leave h or m at zero. The paper's formula then divides by zero. Decide the rule explicitly.
• Standard deviations. Three σ conventions appear. The code uses the sample standard deviation for the regression bound relieff.py and the population standard deviation for the MultiSURF dead band multisurf.py. The paper specifies neither. The effect is small for large n but not zero.
• SURF radius. The paper defines T over all instance pairs. The code's average includes the n zero self-distances on the diagonal, which scales T by (n − 1)/n surf.py. The effect is small for large n.
• Type detection. The paper says types are detected automatically but does not give the rule. The code treats features and endpoints with more than 10 unique values as continuous surf.py. An 11-class endpoint is then treated as continuous.
• Redundancy. RBAs do not remove correlated features 1711.08477 §1. A correlation filter is needed for a clean subset tab. 9.
• Clean benchmarks. The XOR and multiplexer results come from noise-free synthetic data 1711.08477 §3.6 §3.7.
• Iterative expansions. The paper does not benchmark TuRF. It recommends an iterative method for feature spaces above 10,000 features 1711.08477 §3.5.

Papers

• Urbanowicz et al., 2017: benchmarks ReliefF, SURF, SURF*, MultiSURF* and the new MultiSURF on 2280 simulated genetic datasets against eight other feature-selection methods. Results are author-reported, mostly as heatmaps.