The Feature Selection Problem: Traditional Methods and a New Algorithm

Kenji KiraLarry Rendell

article1992AAAI2,312 citations

Introduces the Relief algorithm, a noise-tolerant feature selection method that identifies relevant attributes in linear time without relying on heuristics, even when strong feature interactions are present.

Listen

In real-world machine learning and data analysis, raw data typically contains numerous candidate features, many of which are irrelevant or redundant. Including these uninformative variables slows down learning systems due to high dimensionality and degrades predictive accuracy. Traditional feature selection methods face severe trade-offs: standard learning algorithms and heuristic searches struggle when features interact, while exhaustive search methods become computationally impossible as the number of candidate variables grows.

The article evaluates and demonstrates Relief, a novel feature selection algorithm designed to efficiently isolate relevant variables using statistical weight updates. The primary objective is to introduce a method that reliably handles complex feature interactions, tolerates noise, and remains computationally efficient for practical, large-scale problems.

The approach relies on an instance-based statistical technique. The algorithm repeatedly samples instances from the training data, identifies their nearest neighbors within the same class (near-hits) and from the opposite class (near-misses), and updates feature relevance weights based on how well each variable distinguishes between them. The authors validated the method through formal statistical bounding analysis using Chebyshev's inequality and through empirical benchmark experiments on challenging parity problems, comparing Relief against standalone decision tree learners and exhaustive search methods across varying feature set sizes and noise levels.

The findings show that Relief operates with linear time complexity relative to the number of features and training instances, avoiding exponential computational slowdowns. When data contains noise, pairing Relief with standard decision tree learners produces higher predictive accuracy than exhaustive search techniques, which degrade in the presence of noise. Furthermore, standard heuristic learners alone fail completely on tasks involving strong feature interactions, whereas Relief successfully detects interacting relevant features without requiring human intervention or arbitrary subset size limits.

These results indicate that automated systems can substantially reduce data processing costs and training timelines without sacrificing predictive quality in complex, noisy environments. By bridging the gap between slow exhaustive searches and inaccurate single-feature heuristics, the algorithm provides a scalable preprocessing foundation for automated analytics pipelines.

Organizations handling high-dimensional classification tasks should consider deploying Relief as a filtering step prior to applying inductive learning models. If a strictly minimal feature set is required, teams should implement a hybrid strategy: use Relief first to filter out the bulk of irrelevant features, followed by downstream subset optimization or native learner pruning. Further development should also adapt the algorithm for multi-class classification and continuous target prediction.

Confidence in these findings is high for two-class classification settings with sufficient data density. However, stakeholders should note key operational limitations: Relief does not automatically eliminate redundant features among relevant variables, and sparse training data across complex target distributions can degrade nearest-neighbor quality and lead to suboptimal selections.

classifiers feature selection problem genetic selection feature selection Relief algorithm instance-based learning

Kira et al (1992).pdf

Paper: Small Sample Size Effects in Statistical Pattern Recognition: Recommendations for Practitioners, Sarunas J. Raudys et al. (1991). This paper establishes the foundational statistical challenges of sample size limitations, peaking effects, and dimensionality in pattern recognition that motivate the need for efficient feature selection algorithms like Relief.

Paper: Theoretical and Empirical Analysis of ReliefF and RReliefF, Marko Robnik-Šikonja et al. (2003). This work directly extends the original Relief algorithm to multiclass and regression domains (ReliefF and RReliefF) while providing comprehensive theoretical and probabilistic formulations of its weighting mechanism.
Paper: Irrelevant Features and the Subset Selection Problem, George H. John et al. (1994). This seminal paper formally defines feature relevance and contrasts wrapper methods against filter-based subset selection approaches like Relief.
Paper: Correlation-based Feature Selection for Discrete and Numeric Class Machine Learning, Mark A. Hall (1999). This paper introduces Correlation-based Feature Selection (CFS) as an alternative filter method designed to evaluate subsets rather than individual features, benchmarking directly against ReliefF.
Paper: Feature Selection for High-Dimensional Data: A Fast Correlation-Based Filter Solution, Lei Yu et al. (2003). This paper develops a fast correlation-based filter that explicitly addresses feature redundancy, evaluating its computational and classification performance directly against ReliefF.
Paper: Efficient Feature Selection via Analysis of Relevance and Redundancy, Lei Yu et al. (2004). This work decouples relevance analysis from redundancy elimination to overcome the limitation of relevance-only filter methods such as Relief in ultra-high-dimensional datasets.
Paper: Benchmarking Attribute Selection Techniques for Discrete Class Data Mining, Mark A. Hall et al. (2003). This study provides a broad empirical benchmark comparing ReliefF alongside major filter, consistency, and wrapper techniques across diverse induction algorithms.
Paper: Toward Optimal Feature Selection, Daphne Koller et al. (1996). This paper advances filter-based feature selection through an information-theoretic Markov blanket framework that removes redundant variables that individual feature-weighting algorithms retain.
Paper: Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy, Hanchuan Peng et al. (2003). This paper formulates the minimal-redundancy-maximal-relevance (mRMR) framework to bridge the gap between individual feature relevance estimation and optimal subset dependency.
Paper: An Introduction to Variable and Feature Selection, Isabelle M Guyon et al. (2003). This comprehensive tutorial and survey structures the entire feature selection landscape into ranking filters, wrappers, and embedded methods, building directly on the principles established by early filter algorithms like Relief.
Paper: Laplacian Score for Feature Selection, Xiaofei He et al. (2005). This paper generalizes nearest-neighbor graph structures and locality preservation into the unsupervised Laplacian Score for feature evaluation.

Cover for The Feature Selection Problem: Traditional Methods and a New Algorithm

Abstract

For real-world concept learning problems, feature selection is important to speed up learning and to improve concept quality. We review and analyze past approaches to feature selection and note their strengths and weaknesses. We then introduce and theoretically examine a new algorithm Relief which selects relevant features using a statistical method. Relief does not depend on heuristics, is accurate even if features interact, and is noise-tolerant. It requires only linear time in the number of given features and the number of training instances, regardless of the target concept complexity. The algorithm also has certain limitations such as non-optimal feature set size. Ways to overcome the limitations are suggested. We also report the test results of comparison between Relief and other feature selection algorithms. The empirical results support the theoretical analysis, suggesting a practical approach to feature selection for real-world problems.

Topics

classifiers feature selection problem genetic selection

Keywords

feature selection Relief algorithm instance-based learning decision trees redundant features irrelevant features feature interaction heuristic search exhaustive search predictive accuracy

2.4 Feature weight based approaches
3 Relief Algorithm
Theoretical Analysis
4.2 Threshold ̂̈̇̆̅̄̃̂́̀̈z
5 Empirical Evaluation
Acknowledgements
References

Knowls

Knowl 1 — The Relief Algorithm for Feature Selection
algorithm
The Relief algorithm is an instance-based feature selection method for two-class classification problems that estimates the statistical relevance of candidate features by evaluating how well their values distinguish between instances that are close to each other in instance space.
Input: Training set $S$ of $n$ instances, sample size $m$ , relevancy threshold $\tau \in [0, 1]$
Output: Set of selected relevant features
Separate $S$ into $S^+ = \{X \in S \mid \text{class}(X) = +\}$ and $S^- = \{X \in S \mid \text{class}(X) = -\}$
Initialize weight vector $W = (0, 0, \ldots, 0)$ of length $p$
for $i = 1$ to $m$ do
    Pick an instance $X \in S$ uniformly at random
    Pick at random one of the positive instances closest to $X$ , $Z^+ \in S^+$ (using Euclidean distance)
    Pick at random one of the negative instances closest to $X$ , $Z^- \in S^-$ (using Euclidean distance)
    if $X \in S^+$ then
         $\text{Near-hit} = Z^+$
         $\text{Near-miss} = Z^-$
    else
         $\text{Near-hit} = Z^-$
         $\text{Near-miss} = Z^+$
    end if
    for $j = 1$ to $p$ do
         $W_j = W_j - \text{diff}(X_j, \text{Near-hit}_j)^2 + \text{diff}(X_j, \text{Near-miss}_j)^2$
    end for
end for
$\text{Relevance} = \frac{1}{m} W$
SelectedFeatures $= \emptyset$
for $j = 1$ to $p$ do
    if $\text{Relevance}_j \ge \tau$ then
        Add feature $f_j$ to SelectedFeatures
    end if
end for
return SelectedFeatures
Here, $\text{Near-hit}$ is the nearest neighbor to $X$ possessing the same class label, $\text{Near-miss}$ is the nearest neighbor to $X$ possessing the opposite class label, and $\text{diff}(x_j, y_j)$ denotes the normalized feature difference.
Knowl 2 — Relief Feature Difference Metric
definition
In the Relief algorithm, the difference $\text{diff}(x_k, y_k)$ between the feature values of feature $f_k$ for two instances $X = (x_1, \ldots, x_p)$ and $Y = (y_1, \ldots, y_p)$ is defined based on the attribute scale type:

For nominal (including boolean) features: $\text{diff}(x_k, y_k) = \begin{cases} 0 & \text{if } x_k = y_k \\ 1 & \text{if } x_k \neq y_k \end{cases}$

For numerical (integer or real-valued) features: $\text{diff}(x_k, y_k) = \frac{x_k - y_k}{nu_k}$ where $nu_k$ is a normalization unit chosen to scale the difference into the interval $[0, 1]$ (e.g., the maximum value range of feature $f_k$ across the dataset).
Knowl 3 — Expected Relevance Level for Relevant versus Irrelevant Features in Relief
theoretical result
Let $\delta_i = -(x_i - \text{near-hit}_i)^2 + (x_i - \text{near-miss}_i)^2$ denote the weight update component for feature $f_i$ corresponding to an instance $X$ , its nearest same-class neighbor $\text{near-hit}$ , and its nearest opposite-class neighbor $\text{near-miss}$ . The relevance level $\text{relevance}_i$ computed by Relief over $m$ sampled instances is the sample mean estimating $\mathbb{E}[\delta_i]$ .
1. For a relevant feature $f_i$ : An instance $X$ and its same-class neighbor $\text{near-hit}$ are expected to have nearly identical feature values in the local neighborhood ( $x_i \approx \text{near-hit}_i$ ), while $X$ and its opposite-class neighbor $\text{near-miss}$ must differ on one or more relevant features. Consequently, $\mathbb{E}[(x_i - \text{near-hit}_i)^2] < \mathbb{E}[(x_i - \text{near-miss}_i)^2]$ , which implies: $\mathbb{E}[\delta_i] \gg 0$
2. For an irrelevant feature $f_i$ : The random variables $x_i$ , $\text{near-hit}_i$ , and $\text{near-miss}_i$ do not depend on class membership or on one another. Since $\text{near-hit}_i$ and $\text{near-miss}_i$ follow the same distribution, $\mathbb{E}[(x_i - \text{near-hit}_i)^2] = \mathbb{E}[(x_i - \text{near-miss}_i)^2]$ , yielding: $\mathbb{E}[\delta_i] = 0$ (In practice, because $X$ cannot be identical to $\text{near-hit}$ during neighbor selection, $\mathbb{E}[\delta_i]$ tends to be slightly negative for irrelevant features.)
Thus, Relief statistically separates relevant from irrelevant features by the expected sign and magnitude of $\mathbb{E}[\delta_i]$ , even in domains with complex feature interactions.
Knowl 4 — Chebyshev-Based Derivation of the Relevancy Threshold in Relief
theoretical result
Relief determines feature relevance by testing the null hypothesis $H_0: \mathbb{E}[\delta_i] = 0$ (that feature $f_i$ is irrelevant). A feature is classified as relevant if its average weight $\text{relevance}_i = \frac{1}{m}\sum_{k=1}^m \delta_{i,k}$ satisfies $\text{relevance}_i \ge \tau$ .

Because instance differences are normalized in $[0, 1]$ , each individual update variable satisfies $-1 \le \delta_i \le 1$ . Under $H_0$ , $\mathbb{E}[\delta_i] = 0$ and the standard deviation satisfies $\sigma(\delta_i) \le 1$ . For the sample average over $m$ instances, the standard deviation is bounded by: $\sigma(\text{relevance}_i) = \frac{\sigma(\delta_i)}{\sqrt{m}} \le \frac{1}{\sqrt{m}}$

Applying Chebyshev's inequality to enforce that the Type I error probability (rejecting $H_0$ when $f_i$ is irrelevant) does not exceed $\alpha$ : $P(|\text{relevance}_i| \ge h \cdot \sigma(\text{relevance}_i)) \le \frac{1}{h^2} \le \alpha$ Setting $h = 1 / \sqrt{\alpha}$ yields the threshold criterion: $\tau = \frac{1}{\sqrt{\alpha m}}$ Choosing $\tau = \frac{1}{\sqrt{\alpha m}}$ guarantees that the probability of erroneously selecting an irrelevant feature is at most $\alpha$ , without requiring any parametric assumptions on the underlying feature distributions.
Knowl 5 — Computational Complexity of the Relief Algorithm
theoretical result
For a dataset with $n$ training instances and $p$ features, running Relief with sample size $m$ requires: $\Theta(p \cdot m \cdot n)$ operations. For each of the $m$ sampled instances, finding the nearest hit and nearest miss requires evaluating $p$ -dimensional distances over the remaining $n$ instances, costing $\Theta(p n)$ per sample. Updating the weight vector across $m$ triplets takes $\Theta(p m)$ , and the final thresholding takes $\Theta(p)$ .

When the sample size $m$ is treated as a fixed constant independent of $n$ and $p$ , the overall time complexity is linear in both the feature dimension and the number of instances: $\Theta(p \cdot n)$ This complexity is independent of the target concept's logical complexity or the degree of interaction among features.
Knowl 6 — Empirical Performance of Relief on Interacting Features and Noisy Data
empirical result
Relief combined with ID3 was empirically evaluated against ID3 alone and FOCUS combined with ID3 on a boolean parity concept ( $f_1 \oplus f_2 = 1$ ) with total feature set size $p$ varied from 2 to 15 (where $p - 2$ features were irrelevant):
1. Noise-Free Data:
  - Both FOCUS + ID3 and Relief ( $m=40, \tau=0.1$ ) + ID3 achieved 100% predictive classification accuracy for all feature counts $p \in [2, 15]$ .
  - ID3 alone suffered steady degradation in predictive accuracy as irrelevant features were added, dropping from 100% at $p=2$ to approximately 80% at $p=15$ .
  - Learning time for FOCUS + ID3 increased exponentially with $p$ (surpassing 100 seconds at $p=15$ ), whereas Relief + ID3 learning time scaled strictly linearly, remaining under 20 seconds.
2. Noisy Data (10% Feature Noise):
  - Relief + ID3 maintained high predictive accuracy near the theoretical upper bound (~84%), whereas FOCUS + ID3 degraded significantly (falling below 70% accuracy at higher feature counts) because noise prevented FOCUS from identifying small, consistent feature subsets.
  - FOCUS + ID3 learning time escalated exponentially (approaching 500 seconds by $p=14$ ), while Relief + ID3 learning time grew linearly and remained under 25 seconds.
Knowl 7 — Limitations of the Relief Algorithm
limitation
The Relief algorithm has three primary operational limitations:
1. Inability to Filter Redundant Features: Relief estimates the relevance of individual features rather than subset minimality. If multiple redundant features are correlated with the target concept, Relief assigns high weights to all of them and selects them, failing to isolate a minimal sufficient subset.
2. Restriction to Two-Class Classification: The standard formulation of Relief is defined only for two-class problems; applying it to multi-class classification requires decomposing the problem into multiple two-class subproblems.
3. Sensitivity to Data Sparsity in Disjunctive Concepts: When training instances are sparsely distributed, the Euclidean nearest instance of the same class (Near-hit) is more likely to be drawn from a different peak or disjunct of the concept representation rather than the true local neighborhood of the query instance. Sampling Near-hits across disjunct boundaries introduces large feature differences between instances of the same class, degrading the accuracy of the relevance estimation.

Coverage note — Background reviews and complexity analyses of prior existing feature selection algorithms (Sequential Forward Selection, Sequential Backward Selection, STAGGER, CABOT, and FOCUS) from Section 2 were omitted as they are not the paper's original contributions.

References

1.Aha, D. W. Incremental Instance-Based Learning of Independent and Graded Concept Descriptions, Proceedings of the Sixth International Workshop on Machine Learning.
2.Aha, D. W. Incremental Constructive Induction: An Instance-Based Approach, Proceedings of the Eighth International Workshop on Machine Learning.
3.Aha, D. W., Kibler, D. & Albert, M. K. Instance-Based Learning Algorithms. Machine Learning, 6, 37-66.
4.Aha, D. W. & McNulty, D. M. Learning Relative Attribute Weights for Instance-Based Concept Descriptions, Proceedings of the Eleventh Annual Conference of the Cognitive Science Society.
5.Almuallim, H. & Dietterich, T. G., Learning With Many Irrelevant Features, Proceedings of the Ninth National Conference on Artificial Intelligence, 1991, 547-552.
6.Bareiss, R., Exemplar-Based Knowledge Acquisition : A Unified Approach to Concept Representation, Classification, and Learning, Academic Press.
7.Breiman, L., Friedman, J. H., Olshen, R. A. & Stone, C. J., Classification and Regression Trees, Wadsworth, 1984.
8.Callan, J. P., Fawcett, T. E. & Rissland, E. L., CABOT : An Adaptive Approach to Case-Based Search, Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, 1991, 803-808.
9.Devijver, P. A. & Kittler, J., Pattern Recognition : A Statistical Approach, Prentice Hall.
10.Kira, K. & Rendell, L. A., A Practical Approach to Feature Selection, Machine Learning : Proceedings of the Ninth International Conference (ML92), 1992.
11.Matheus, C. & Rendell, L. A. Constructive Induction on Decision Trees. Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, 1989, 645-650.
12.Pagallo, G., Learning DNF by Decision Trees, Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, 1989, 639-644.
13.Porter, B. W., Bareiss, R. & Holte, R. C. Concept Learning and Heuristic Classification in Weak-Theory Domains, Artificial Intelligence, 45, 229-263.
14.Quinlan, J. R. Learning Efficient Classification Procedures and Their Application to Chess End Games. Machine Learning : An Artificial Intelligence Approach, 1983, 463-482.
15.Rendell, L. A., Cho, H. H. & Seshu, R. Improving the Design of Similarity-Based Rule-Learning Systems. International Journal of Expert Systems, 2, 97-133.
16.Rendell, L. A. & Seshu, R. Learning Hard Concepts through Constructive Induction: Framework and Rationale. Computational Intelligence, Nov., 1990.
17.Schlimmer, J. C., Learning and Representation Change, Proceedings of the Fifth National Conference on Artificial Intelligence.
18.Schlimmer, J. C. & Granger, R. H. Jr., Incremental Learning from Noisy Data, Machine Learning 1, 317-354.
19.Yang, D-S., Blix, G. & Rendell, L. A. The Replication Problem: A Constructive Induction Approach, Proceedings of European Working Session on Learning, march, 1991.

Citation

MLA

Kira, K., and L. A. Rendell. “The Feature Selection Problem: Traditional Methods and a New Algorithm”. National Conference on Artificial Intelligence, 1992, pp. 129–34, https://ci.nii.ac.jp/naid/10000073076.

APA

Kira, K., & Rendell, L. A. (1992). The feature selection problem: traditional methods and a new algorithm. National Conference on Artificial Intelligence, 129–134. https://ci.nii.ac.jp/naid/10000073076

Chicago

Kira, K., and L. A. Rendell. 1992. “The Feature Selection Problem: Traditional Methods and a New Algorithm”. National Conference on Artificial Intelligence, 129–34. https://ci.nii.ac.jp/naid/10000073076.

Harvard

Kira, K. and Rendell, L.A. (1992) “The feature selection problem: traditional methods and a new algorithm”, National Conference on Artificial Intelligence, pp. 129–134. Available at: https://ci.nii.ac.jp/naid/10000073076.

Vancouver

1. Kira K, Rendell LA (1992) The feature selection problem: traditional methods and a new algorithm. National Conference on Artificial Intelligence 129–134

BibTeX

@article{kira1992the,
  title = {The feature selection problem: traditional methods and a new algorithm},
  author = {Kira, Kenji and Rendell, Larry A.},
  year = {1992},
  journal = {National Conference on Artificial Intelligence},
  pages = {129-134},
  url = {https://ci.nii.ac.jp/naid/10000073076}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

The Feature Selection Problem: Traditional Methods and a New Algorithm

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — The Relief Algorithm for Feature Selection

Knowl 2 — Relief Feature Difference Metric

Knowl 3 — Expected Relevance Level for Relevant versus Irrelevant Features in Relief

Knowl 4 — Chebyshev-Based Derivation of the Relevancy Threshold in Relief

Knowl 5 — Computational Complexity of the Relief Algorithm

Knowl 6 — Empirical Performance of Relief on Interacting Features and Noisy Data

Knowl 7 — Limitations of the Relief Algorithm

References

Citation

BibTeX

Access the Paper