A RELIEF Based Feature Extraction Algorithm

Published 24 April 2008

Yijun Sun, Dapeng Wu

DOI10.1137/1.9781611972788.17

Citations72

TL;DR

A novel feature extraction algorithm, referred to as LFE, is proposed, as a natural generalization of RELIEF, which collects discriminant information through local learning, and is solved as an eigenvalue decomposition problem with a closed-form solution.

Abstract

RELIEF is considered one of the most successful algorithms for assessing the quality of features due to its simplicity and effectiveness. It has been recently proved that RELIEF is an online algorithm that solves a convex optimization problem with a margin-based objective function. Starting from this mathematical interpretation, we propose a novel feature extraction algorithm, referred to as LFE, as a natural generalization of RELIEF. LFE collects discriminant information through local learning, and is solved as an eigenvalue decomposition problem with a closed-form solution. A fast implementation is also derived. Experiments on synthetic and real-world data are presented. The results demonstrate that LFE performs significantly better than other feature extraction algorithms in terms of both computational efficiency and accuracy.

Keywords

Computer Science

Springer series in statisticsThe Elements of Statistical Learning

24,344 Citations2001Trevor Hastie, J. Friedman +1 more

View PDF

Artificial IntelligenceWrappers for feature subset selection

8,925 Citations1997Ron Kohavi, George H. John

The wrapper method searches for an optimal feature subset tailored to a particular algorithm and a domain and compares the wrapper approach to induction without feature subset selection and to Relief, a filter approach tofeature subset selection.

Journal of Machine Learning ResearchDistance Metric Learning for Large Margin Nearest Neighbor Classification

4,253 Citations2009Kilian Q. Weinberger, Lawrence K. Saul

This paper shows how to learn a Mahalanobis distance metric for kNN classification from labeled examples in a globally integrated manner and finds that metrics trained in this way lead to significant improvements in kNN Classification.

Pattern Recognition LettersFloating search methods in feature selection

3,070 Citations1994Pavel Pudil, Jana Novovičová +1 more

Elsevier eBooksA Practical Approach to Feature Selection

2,954 Citations1992Kenji Kira, Larry Rendell

Comparison with other feature selection algorithms shows Relief's advantages in terms of learning time and the accuracy of the learned concept, suggesting Relief's practicality.

Lecture notes in computer scienceEstimating attributes: Analysis and extensions of RELIEF

2,950 Citations1994Igor Kononenko

In the context of machine learning from examples this paper deals with the problem of estimating the quality of attributes with and without dependencies among them and is analysed and extended to deal with noisy, incomplete, and multi-class data sets.

Neighbourhood Components Analysis

1,729 Citations2004Jacob Goldberger, Geoffrey E. Hinton +2 more

A novel method for learning a Mahalanobis distance measure to be used in the KNN classification algorithm that directly maximizes a stochastic variant of the leave-one-out KNN score on the training set.

Distance Metric Learning for Large Margin Nearest Neighbor Classification

1,707 Citations2005Kilian Q. Weinberger, John Blitzer +1 more

IEEE Antennas and Propagation MagazineAn Introduction to Optimization

880 Citations1996E.K.P. Chong, Stanisław H. Żak

Artificial Intelligence ReviewA Review and Empirical Evaluation of Feature Weighting Methods for a Class of Lazy Learning Algorithms

718 Citations1997Dietrich Wettschereck, David W. Aha +1 more

A class of weight-setting methods for lazy learning algorithms which use performance feedback to assign weight settings demonstrated three advantages over other methods: they require less pre-processing, perform better in the presence of interacting features, and generally require less training data to learn good settings.