CoChat
Sign Up
Cited by 1,311Artificial Intelligence in HealthcareGene expression and cancer classificationMachine Learning and Data Classification

Relief-based feature selection: Introduction and review

Open access
Urbanowicz, Ryan J., Meeker, Melissa, La Cava, William, Olson, Randal S., Moore, Jason H.·2018·Journal of Biomedical Informatics
DOI 10.1016/j.jbi.2018.07.014PMC PMC6299836
Open this paper in CoChat — free accountOpen PDF

Abstract

Feature selection plays a critical role in biomedical data mining, driven by increasing feature dimensionality in target problems and growing interest in advanced but computationally expensive methodologies able to model complex associations. Specifically, there is a need for feature selection methods that are computationally efficient, yet sensitive to complex patterns of association, e.g. interactions, so that informative features are not mistakenly eliminated prior to downstream modeling. This paper focuses on Relief-based algorithms (RBAs), a unique family of filter-style feature selection algorithms that have gained appeal by striking an effective balance between these objectives while flexibly adapting to various data characteristics, e.g. classification vs. regression. First, this work broadly examines types of feature selection and defines RBAs within that context. Next, we introduce the original Relief algorithm and associated concepts, emphasizing the intuition behind how it works, how feature weights generated by the algorithm can be interpreted, and why it is sensitive to feature interactions without evaluating combinations of features. Lastly, we include an expansive review of RBA methodological research beyond Relief and its popular descendant, ReliefF. In particular, we characterize branches of RBA research, and provide comparative summaries of RBA algorithms including contributions, strategies, functionality, time complexity, adaptation to key data characteristics, and software availability.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1016/j.jbi.2018.07.014

Cites

64 of 64 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 56

  1. [1]Agre G, Dzhondzhorov A, 2016. A weighted feature selection method for instance-based classification. In: International Conference on Artificial Intelligence: Methodology, Systems, and Applications Springer, pp. 14– 25.
  2. [3]Almuallim H, Dietterich TG, 1991 Learning with many irrelevant features. In: AAAI. Vol. 91 pp. 547– 552.
  3. [4]Arauzo-Azofra A, Benitez JM, Castro JL, 2004 A feature set measure based on relief. In: Proceedings of the fifth international conference on Recent Advances in Soft Computing pp. 104– 109.
  4. [8]Bins J, Draper BA, 2001 Feature selection from huge feature sets. In: Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on. Vol. 2 IEEE, pp. 159– 165.
  5. [9]Bins J, Draper BA, 2002 Evaluating feature relevance: Reducing bias in relief. In: JCIS. pp. 757– 760.
  6. [10]Blessie EC, Karthikeyan E, 2011 Relief-disc: An extended relief algorithm using discretization approach for continuous features. In: Emerging Applications of Information Technology (EAIT), 2011 Second International Conference on IEEE, pp. 161– 164.
  7. [13]Bradley PS, Mangasarian OL, 1998 Feature selection via concave minimization and support vector machines. In: ICML. Vol. 98 pp. 82– 90.
  8. [14]Breiman L, Friedman J, Stone CJ, Olshen RA, 1984 Classification and regression trees. CRC press.
  9. [15]Cai H, Ng M, 2012 Feature weighting by relief based on local hyperplane approximation In: Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, pp. 335– 346.
  10. [16]Callan JP, Fawcett T, Rissland EL, 1991 Cabot: An adaptive approach to case-based search. In: IJCAI. Vol. 12 pp. 803– 808.
  11. [17]Challita N, Khalil M, Beauseroy P, 2015 New technique for feature selection: Combination between elastic net and relief. In: Technological Advances in Electrical, Electronics and Computer Engineering (TAEECE), 2015 Third International Conference on IEEE, pp. 262– 267.
  12. [20]Chen T, Guestrin C, 2016 Xgboost: A scalable tree boosting system. In: Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining ACM, pp. 785– 794.
  13. [22]Cortizo JC, Giraldez I, 2006 Multi criteria wrapper improvements to naive bayes learning In: IDEAL. Vol. 4224 Springer, pp. 419– 427.
  14. [24]Dash M, Ong Y-S, 2011 Relief-c: Efficient feature selection for clustering over noisy data. In: Tools with Artificial Intelligence (ICTAI), 2011 23rd IEEE International Conference on IEEE, pp. 869– 872.
  15. [28]Demšar J, Curk T, Erjavec A, Gorup Č, Hočevar T, Milutinovič M, Možina M, Polajnar M, Toplak M, Starič A,, 2013 Orange: data mining toolbox in python. The Journal of Machine Learning Research 14 (1), 2349– 2353.
  16. [30]Dorani F, Hu T, 2018 Feature selection for detecting gene-gene interactions in genome-wide association studies. In: International Conference on the Applications of Evolutionary Computation. Springer, pp. 33– 46.
  17. [31]Draper B, Kaito C, Bins J, 2003 Iterative relief In: Computer Vision and Pattern Recognition Workshop, 2003. CVPRW’03. Conference on. Vol. 6 IEEE, pp. 62–62.
  18. [33]Eppstein MJ, Haake P, 2008 Very large scale relieff for genome-wide association analysis In: Computational Intelligence in Bioinformatics and Computational Biology, 2008. CIBCB’08. IEEE Symposium on. IEEE, pp. 112– 119.
  19. [36]Gore S, Govindaraju V, 2016 Feature selection using cooperative game theory and relief algorithm In: Knowledge, Information and Creativity Support Systems: Recent Trends, Advances and Solutions. Springer, pp. 401– 412.
  20. [37]Granizo-Mackenzie D, Moore JH, 2013 Multiple threshold spatially uniform relieff for the genetic analysis of complex human diseases In: European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics. Springer, pp. 1– 10.
  21. [38]Greene CS, Himmelstein DS, Kiralis J, Moore JH, 2010 The informative extremes: using both nearest and farthest individuals can improve relief algorithms in the domain of human genetics In: European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics. Springer, pp. 182– 193.
  22. [40]Guyon I, Bitter H-M, Ahmed Z, Brown M, Heller J, 2003 Multivariate non-linear feature selection with kernel multiplicative updates and gram-schmidt relief In: BISC Flint-CIBI 2003 Workshop Berkeley pp. 1– 11.
  23. [41]Guyon I, Bitter H-M, Ahmed Z, Brown M, Heller J, 2005 Multivariate non-linear feature selection with kernel methods In: Soft computing for information processing and analysis. Springer, 313– 326.
  24. [42]Guyon I, Elisseeff A, 2003 An introduction to variable and feature selection. Journal of machine learning research 3 (Mar), 1157– 1182.
  25. [44]Holland JH, 1992 Adaptation in natural and artificial systems. 1975. Ann Arbor, MI: University of Michigan Press and.
  26. [46]Hunt EB, Marin J, Stone PJ, 1966 Experiments in induction. Academic Press.
  27. [50]Jin X, Xu A, Bie R, Guo P, 2006 Machine learning techniques and chi-square feature selection for cancer classification using sage gene expression profiles In: International Workshop on Data Mining for Biomedical Applications. Springer, pp. 106– 115.
  28. [52]Kira K, Rendell LA, 1992 The feature selection problem: Traditional methods and a new algorithm. In: AAAI. Vol. 2 pp. 129– 134.
  29. [57]Kong D, Ding C, Huang H, Zhao H, 2012 Multi-label relieff and f-statistic feature selections for image annotation. In: Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on IEEE, pp. 2352– 2359.
  30. [58]Kononenko I, 1994 Estimating attributes: analysis and extensions of relief In: European conference on machine learning. Springer, pp. 171– 182.
  31. [59]Kononenko I, 1995 On biases in estimating multi-valued attributes. In: Ijcai. Vol. 95 pp. 1034– 1040.
  32. [65]Lee K-Y, Liu P, Leung K-S, Wong M-H, 2015 Very large scale relieff algorithm on gpu for genome-wide association study. In: Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA). The Steering Committee of The World Congress in Computer Science, Computer Engineering and Applied Computing (WorldComp), p. 78.
  33. [66]Li L, 2014 Relief for regression with missing data in variable selection. Ph.D. thesis, Citeseer.
  34. [67]Liu X, Wang X, Su Q, 2015 Feature selection of medical data sets based on rs-relieff. In: Service Systems and Service Management (ICSSSM), 2015 12th International Conference on IEEE, pp. 1– 5.
  35. [73]Mhamdi F, Mhamdi H, 2013 A new algorithm relief hybrid (hrelief) for biological motifs selection. In: Bioinformatics and Bioengineering (BIBE), 2013 IEEE 13th International Conference on IEEE, 1– 5.
  36. [75]Mlambo N, Cheruiyot WK, Kimwele MW, 2016 A survey and comparative study of filter and wrapper feature selection techniques. International Journal of Engineering and Science (IJES) 5 (8), 57– 67.
  37. [77]Moore JH, White BC, 2007 Tuning relieff for genome-wide genetic analysis In: European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics. Springer, pp. 166– 175.
  38. [79]Ni W, 2012 A review and comparative study on univariate feature selection techniques. Ph.D. thesis, University of Cincinnati.
  39. [81]Park H, Kwon H-C, 2007 Extended relief algorithms in instance-based feature filtering. In: Advanced Language Processing and Web Information Technology, 2007. ALPIT 2007. Sixth International Conference on IEEE, pp. 123– 128.
  40. [82]Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, Prettenhofer P, Weiss R, Dubourg V, Vanderplas J, Passos A, Cournapeau D, Brucher M, Perrot M, Duchesnay E, 2011 Scikit-learn: Machine learning in Python. Journal of Machine Learning Research 12, 2825– 2830.
  41. [83]Pupo OGR, Morell C, Soto SV, 2013 Relieff-ml: an extension of relieff algorithm to multi-label learning In: Iberoamerican Congress on Pattern Recognition. Springer, pp. 528– 535.
  42. [84]Qamar AM, Gaussier E, 2012 Relief algorithm and similarity learning for k-nn. International Journal of Computer Information Systems and Industrial Management Applications (IJCISIM) 4, 445– 458.
  43. [89]Robnik-Šikonja M, Kononenko I, 1997 An adaptation of relief for attribute estimation in regression. In: Machine Learning: Proceedings of the Fourteenth International Conference (ICML97) pp. 296– 304.
  44. [90]Robnik-Šikonja M, Kononenko I, 2001 Comprehensible interpretation of reliefs estimates In: Machine Learning: Proceedings of the Eighteenth International Conference on Machine Learning (ICML2001), Williamstown, MA, USA. San Francisco: Morgan Kaufmann. pp. 433– 40.
  45. [103]Sun Y, Li J, 2006 Iterative relief for feature weighting. In: Proceedings of the 23rd international conference on Machine learning ACM, pp. 913– 920.
  46. [105]Sun Y, Wu D, 2008 A relief based feature extraction algorithm. In: Proceedings of the 2008 SIAM International Conference on Data Mining SIAM, pp. 188– 195.
  47. [107]Tang J, Alelyani S, Liu H, 2014 Feature selection for classification: A review. Data Classification: Algorithms and Applications, 37.
  48. [109]Todorov A, 2016 Statistical Approaches to Gene × Environment Interactions for Complex Phenotypes MIT Press, Ch. An Overview of the RELIEF Algorithm and Advancements, pp. 95– 116.
  49. [110]Urbanowicz RJ, Bertasius G, Moore JH, 2014 An extended michigan-style learning classifier system for flexible supervised learning, classification, and data mining In: International Conference on Parallel Problem Solving from Nature. Springer, pp. 211– 221.
  50. [111]Urbanowicz RJ, Granizo-Mackenzie D, Moore JH, 2012 Using expert knowledge to guide covering and mutation in a michigan style learning classifier system to detect epistasis and heterogeneity In: International Conference on Parallel Problem Solving from Nature. Springer, pp. 266– 275.
  51. [114]Van Laarhoven PJ, Aarts EH, 1987 Simulated annealing. In: Simulated annealing: Theory and applications. Springer, pp. 7– 15.
  52. [117]Yang J, Li Y-P, 2006 Orthogonal relief algorithm for feature selection In: International Conference on Intelligent Computing. Springer, pp. 227– 234.
  53. [119]Yu L, Liu H, 2004 Efficient feature selection via analysis of relevance and redundancy. Journal of machine learning research 5 (Oct), 1205– 1224.
  54. [120]Zafra A, Pechenizkiy M, Ventura S, 2010 Feature selection is the relieff for multiple instance learning. In: Intelligent Systems Design and Applications (ISDA), 2010 10th International Conference on IEEE, pp. 525– 532.
  55. [122]Zeng X, Wang Q, Zhang C, Cai H, 2013 Feature selection based on relieff and pca for underwater sound classification. In: Computer Science and Network Technology (ICCSNT), 2013 3rd International Conference on IEEE, pp. 442– 445.
  56. [124]Zhou Q, Ding J, Ning Y, Luo L, Li T, 2014 Stable feature selection with ensembles of multi-relieff. In: Natural Computation (ICNC), 2014 10th International Conference on IEEE, pp. 742– 747.

Cited by

Sorted by citations

Related

Authors
Urbanowicz, R. J., Meeker, M., La Cava, W., Olson, R. S., & Moore, J. H.
Affiliations
  • University of Pennsylvania (US)
  • Ursinus College (US)
Corresponding author
Urbanowicz, Ryan J.
ORCID
Venue
Journal of Biomedical Informatics
Publisher
Elsevier BV
Published
2018-09
Volume
85
Pages
189-203
ISSN
1532-0464 (ISSN-L)
DOI
10.1016/j.jbi.2018.07.014
PMC
PMC6299836
OpenAlex
W2769474643
Cited by
1,311
References
64
Citations by year
2026: 103 · 2025: 197 · 2024: 199 · 2023: 225 · 2022: 212 · 2021: 180 · 2020: 110 · 2019: 68 · 2018: 17
FWCI
17.34
Type
journal article
Language
en
Open access
Licence
Locations
  • Journal of Biomedical Informatics (publishedVersion)
  • PubMed (publishedVersion)
  • Europe PMC (PubMed Central) (acceptedVersion)
  • PubMed Central (acceptedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University) (cc-by)
Funders
National Institutes of Health (ES013508, LM009012, HL134015, EY022300, LM011360, DK112217, TR001263, AI116794, LM010098)
Topics
  • Health Sciences › Health Professions › Health Information Management › Artificial Intelligence in Healthcare
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Gene expression and cancer classification
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
Keywords
Relief algorithm, ReliefF, filter-based feature selection, feature interaction, feature weights, medical data mining, high-dimensional data, classification and regression, algorithm comparison
MeSH terms
Algorithms, Humans, Regression Analysis, Software, Models, Statistical, Computational Biology, Data Mining

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review