Iterative RELIEF for feature weighting

ABSTRACT

We propose a series of new feature weighting algorithms, all stemming from a new interpretation of RELIEF as an online algorithm that solves a convex optimization problem with a margin-based objective function. The new interpretation explains the simplicity and effectiveness of RELIEF, and enables us to identify some of its weaknesses. We offer an analytic solution to mitigate these problems. We extend the newly proposed algorithm to handle multiclass problems by using a new multiclass margin definition. To reduce computational costs, an online learning algorithm is also developed. Convergence theorems of the proposed algorithms are presented. Some experiments based on the UCI and microarray datasets are performed to demonstrate the effectiveness of the proposed algorithms.

REFERENCES

• 1: Dietterich, T. G. (1997). Machine learning research: Four current directions. AI Magazine, 18, 97--136.
• 2: Ran Gilad-Bachrach , Amir Navot , Naftali Tishby, Margin based feature selection - theory and algorithms, Proceedings of the twenty-first international conference on Machine learning, p.43, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015352]
• 3: Kenji Kira , Larry A. Rendell, A Practical Approach to Feature Selection, Proceedings of the Ninth International Workshop on Machine Learning, p.249-256, July 01-03, 1992
• 4: Igor Kononenko, Estimating attributes: analysis and extensions of RELIEF, Proceedings of the European conference on machine learning on Machine Learning, p.171-182, May 1994, Catania, Italy
• 5: Kress, R. (1998). Numerical analysis. New York: Springer-Verlag.
• 6: Kushner, H., & Yin, G. (2003). Stochastic approximation and recursive algorithms and applications. New York: Springer-Verlag. 2 edition.
• 7: Alexander Statnikov , Constantin F. Aliferis , Ioannis Tsamardinos , Douglas Hardin , Shawn Levy, A comprehensive evaluation of multicategory classification methods for microarray gene expression cancer diagnosis, Bioinformatics, v.21 n.5, p.631-643, March 2005 [doi>10.1093/bioinformatics/bti033]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Convex programming
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Algorithms, Theory