--- kind: concept slug: relief-feature-selection title: Relief-based feature selection summary: >- Scores each feature by comparing every instance with its nearest hits (same endpoint) and misses (other endpoint). Local comparison can catch interactions that single-feature tests miss. Variants: ReliefF, SURF, SURF*, MultiSURF* and MultiSURF, which sets a per-instance threshold and drops far scoring. Results are author-reported on simulated data. tags: [feature-selection, relief, epistasis, filter-methods, bioinformatics] papers: ["1711.08477"] related: [feature-selection, nearest-neighbor-search, feature-scaling] status: draft updated_at: 2026-11-06 --- ## 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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:1711.08477 §2.1.1] [eq. 1] [eq. 2]. Distance is Manhattan [arxiv: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 [arxiv:1711.08477 §2.1.1] [alg. 1]. The paper calls k = 10 the widely adopted default [arxiv: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 [arxiv:1711.08477 §3.1]. Card: [Urbanowicz et al., 2017](/papers/1711.08477). ### SURF Replaces k with a radius T, the average distance over all instance pairs. Instances closer than T are neighbours [arxiv:1711.08477 §2.1.2]. Card: [Urbanowicz et al., 2017](/papers/1711.08477). ### 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 [arxiv: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 [arxiv:1711.08477 §3.2]. Card: [Urbanowicz et al., 2017](/papers/1711.08477). ### 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 [arxiv:1711.08477 §2.1.4]. Far instances use the same-value rule, because the authors expect differences to be more common among far instances [arxiv:1711.08477 §2.1.4]. The sign for that rule is contradictory in the paper; see Contradictions. Card: [Urbanowicz et al., 2017](/papers/1711.08477). ### MultiSURF (proposed) Keeps the MultiSURF\* threshold and dead band, but drops far scoring. Only near instances closer than T_i − σ_i/2 contribute [arxiv: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] [arxiv:1711.08477 §2.1.5]. The authors describe this normalisation as accounting for imbalanced hit and miss counts [arxiv:1711.08477 §2.1.5]. Card: [Urbanowicz et al., 2017](/papers/1711.08477). ### 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 [arxiv:1711.08477 §2.1.6]. Card: [Urbanowicz et al., 2017](/papers/1711.08477). - **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 [arxiv:1711.08477 §2.1.7]. The paper calls this simpler than RReliefF and does not compare the two [arxiv: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 [arxiv: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 [arxiv: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. | Situation | Use | Why | |---|---|---| | Binary endpoint, discrete features, pure 2-way epistasis | MultiSURF\* | The authors rank it strongest in this setting. MultiSURF is on par with SURF [arxiv:1711.08477 §3.1] [fig. 3]. | | Unknown noise or heritability, and you want a method with no radius or k to set | MultiSURF | Its threshold and dead band come from the data, with no k or T to choose [arxiv:1711.08477 §2.1.4] [§2.1.5]. The authors report it as the most reliable across their configurations [arxiv:1711.08477 §5]. | | Mixed discrete and continuous features | MultiSURF\* | The paper reports it best on the mixed group, then MultiSURF, SURF\*, and ReliefF with 100 or 10% neighbours [arxiv:1711.08477 §3.8] [fig. 10]. | | Need to rank features that interact in a multiplexer-like structure | ReliefF with 10% neighbours | The paper reports this as the only method perfect on all multiplexer sets. MultiSURF\* is next [arxiv:1711.08477 §3.7] [fig. 8]. | | 4-way or 5-way XOR interactions | Not MultiSURF; consider ReliefF with 10 neighbours | MultiSURF fails 4-way and 5-way XOR. The paper says higher-order interactions are a problem for RBAs unless few neighbours are used in scoring [arxiv:1711.08477 §3.6]. | | Very many features (10,000 to 100,000) | Relief scores as a first pass, with an iterative method on top | The authors expect very large spaces to need an iterative RBA such as TuRF. Alone, MultiSURF reaches full power near the 80th percentile at 100,000 features [arxiv:1711.08477 §3.5] [tab. 9]. | | Continuous endpoint | Regression rule with σ_E | The paper reports RBAs succeed, but gives no comparison with RReliefF [arxiv:1711.08477 §3.8]. | | Missing data | Any variant, with the missing-value rule | RBAs handle missing values without imputation [arxiv:1711.08477 §2.1.8]. The paper notes that the scikit-learn baselines could not run on missing data without preprocessing [arxiv:1711.08477 §3.8]. | | Large n | Plan for the n × n distance matrix | The method needs the full matrix [alg. 1] [arxiv:1711.08477 §2.1]. The paper gives time as n² but no memory figure. | ## 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 [arxiv:1711.08477 §2.2] [tab. 1]. Most results appear only as heatmaps, so the text gives rankings, not numbers [arxiv:1711.08477 §3]. | Setting | Result in the text | Source | |---|---|---| | Core 2-way epistasis | MultiSURF\* strongest; MultiSURF on par with SURF; SURF\* and MultiSURF\* lead at high noise and small n | [arxiv:1711.08477 §3.1] [fig. 3] | | Main effects | SURF\* and MultiSURF\* lose power; ReliefF, SURF and MultiSURF succeed | [arxiv:1711.08477 §3.2] [fig. 4] | | Genetic heterogeneity | MultiSURF\* and MultiSURF best | [arxiv:1711.08477 §3.3] [fig. 5] | | 3-way epistasis (h = 0.2, 1600 instances) | ReliefF 10 NN, 100 NN, 10% NN and MultiSURF succeed; ReliefF with k = 400 fails | [arxiv:1711.08477 §3.4] [fig. 2] | | Clean XOR, 2- to 5-way | RFE ExtraTrees solves all, expected to fail above 20 features; MultiSURF fails 4- and 5-way | [arxiv:1711.08477 §3.6] [fig. 7] | ## 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]. ```pseudocode # 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 [arxiv:1711.08477 §2.1.4], and gives differing far hits +1 and differing far misses −1 for SURF\* [arxiv:1711.08477 §2.1.3]. The tables give the opposite signs for same-valued far hits and misses [arxiv:1711.08477 tab. 4] [tab. 5]. The paper does not say which is meant. The released code follows the tables, not the text [code: skrebate/scoring_utils.py#L250-L283] (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 [arxiv: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 [code: skrebate/scoring_utils.py#L334-L340] [code: skrebate/scoring_utils.py#L404-L420]. 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 [arxiv:1711.08477 §2.1] [§3.8]. The conclusions and table 9 say the authors implemented their own ramp [arxiv: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 [code: skrebate/scoring_utils.py#L158-L186]. The paper's Methods do not describe this rule. - **Default k (paper vs code).** The paper calls k = 10 the widely adopted default [arxiv:1711.08477 §2.1]. The code's default is 100 [code: skrebate/relieff.py#L48]. - **Feature count (within the paper).** Table 1 gives 20 total features for the core groups [arxiv:1711.08477 tab. 1]. The prior-study description in the text gives 1000 features for an earlier setup [arxiv: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 [arxiv:1711.08477 alg. 2] [§2.1.5]. The code keeps the non-empty side and divides it by n only [code: skrebate/scoring_utils.py#L288-L296]. ## 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 [arxiv: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 [code: skrebate/relieff.py#L178-L180] and the population standard deviation for the MultiSURF dead band [code: skrebate/multisurf.py#L68]. 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 [code: skrebate/surf.py#L125-L131]. 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 [code: skrebate/surf.py#L54-L61]. An 11-class endpoint is then treated as continuous. - **Redundancy.** RBAs do not remove correlated features [arxiv: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 [arxiv: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 [arxiv:1711.08477 §3.5]. ## Papers - [Urbanowicz et al., 2017](/papers/1711.08477): 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.