Invariant optimal feature selection: A distance discriminant and feature ranking based solution

ABSTRACT

The goal of feature selection is to find the optimal subset consisting of m features chosen from the total n features. One critical problem for many feature selection methods is that an exhaustive search strategy has to be applied to seek the best subset among all the possible nm feature subsets, which usually results in a considerably high computational complexity. The alternative suboptimal feature selection methods provide more practical solutions in terms of computational complexity but they cannot promise that the finally selected feature subset is globally optimal. We propose a new feature selection algorithm based on a distance discriminant (FSDD), which not only solves the problem of the high computational costs but also overcomes the drawbacks of the suboptimal methods. The proposed method is able to find the optimal feature subset without exhaustive search or Branch and Bound algorithm. The most difficult problem for optimal feature selection, the search problem, is converted into a feature ranking problem following rigorous theoretical proof such that the computational complexity can be greatly reduced. The proposed method is invariant to the linear transformation of data when a diagonal transformation matrix is applied. FSDD was compared with ReliefF and mrmrMID based on mutual information on 8 data sets. The experiment results show that FSDD outperforms the other two methods and is highly efficient.

REFERENCES

• [1]: Anil K. Jain , Robert P. W. Duin , Jianchang Mao, Statistical Pattern Recognition: A Review, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.1, p.4-37, January 2000 [doi>10.1109/34.824819]
• [2]: Isabelle Guyon , André Elisseeff, An introduction to variable and feature selection, The Journal of Machine Learning Research, 3, 3/1/2003
• [3]: Dash, M. and Liu, H., Feature selection for classification. Intelligent Data Anal. v1. 131-156.
• [4]: 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]
• [5]: Quah, K.H. and Quek, C., MCES: a novel Monte Carlo evaluative selection approach for objective feature selections. IEEE Trans. Neural Networks. v18 i2.
• [6]: Jennifer G. Dy , Carla E. Brodley, Feature Selection for Unsupervised Learning, The Journal of Machine Learning Research, 5, p.845-889, 12/1/2004
• [7]: Zheng Zhao , Huan Liu, Spectral feature selection for supervised and unsupervised learning, Proceedings of the 24th international conference on Machine learning, p.1151-1157, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273641]
• [8]: Lior Wolf , Amnon Shashua, Feature Selection for Unsupervised and Supervised Inference: The Emergence of Sparsity in a Weight-Based Approach, The Journal of Machine Learning Research, 6, p.1855-1887, 12/1/2005
• [9]: Ron Kohavi , George H. John, Wrappers for feature subset selection, Artificial Intelligence, v.97 n.1-2, p.273-324, Dec. 1997 [doi>10.1016/S0004-3702(97)00043-X]
• [10]: S. Aeberhard , O. Y. de Vel , D. H. Coomans, New Fast Algorithms for Error Rate-Based Stepwise Variable Selection in Discriminant Analysis, SIAM Journal on Scientific Computing, v.22 n.3, p.1036-1052, 2000 [doi>10.1137/S1064827596300784]
• [11]: Kumar, R., Jayaraman, V.K. and Kulkarni, B.D., An SVM classifier incorporating simultaneous noise reduction and feature selection: illustrative case examples. Pattern Recognition. v38 i1. 41-49.
• [12]: Fast Branch & Bound Algorithms for Optimal Feature Selection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.7, p.900-912, July 2004 [doi>10.1109/TPAMI.2004.28]
• [13]: Anil Jain , Douglas Zongker, Feature Selection: Evaluation, Application, and Small Sample Performance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.2, p.153-158, February 1997 [doi>10.1109/34.574797]
• [14]: P. Pudil , J. Novovičová , J. Kittler, Floating search methods in feature selection, Pattern Recognition Letters, v.15 n.11, p.1119-1125, Nov. 1994 [doi>10.1016/0167-8655(94)90127-9]
• [15]: Kudo, M. and Sklanshy, J., Comparison of algorithm that select features for pattern classifiers. Pattern Recognition. v33. 25-41.
• [16]: Joaquín Pacheco , Silvia Casado , Laura Núñez , Olga Gómez, Analysis of new variable selection methods for discriminant analysis, Computational Statistics & Data Analysis, v.51 n.3, p.1463-1478, December, 2006 [doi>10.1016/j.csda.2006.04.019]
• [17]: Marko Robnik-Šikonja , Igor Kononenko, Theoretical and Empirical Analysis of ReliefF and RReliefF, Machine Learning, v.53 n.1-2, p.23-69, October-November 2003 [doi>10.1023/A:1025667309714]
• [18]: Liu, H., Li, J. and Wong, L., A comparative study on feature selection and classification methods using gene expression profiles and proteomic patterns. Genome Inf. v13. 51-60.
• [19]: Hanchuan Peng , Fuhui Long , Chris Ding, Feature Selection Based on Mutual Information: Criteria of Max-Dependency, Max-Relevance, and Min-Redundancy, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.8, p.1226-1238, August 2005 [doi>10.1109/TPAMI.2005.159]
• [20]: Available at {http://www.ics.uci.edu/mlearn/databases/}.
• [21]: Available at {http://lib.stat.cmu.edu/datasets/}.
• [22]: Friedman, M. and Kandel, A., Introduction to Pattern Recognition: Statistical, Structural, Neural and Fuzzy Logic Approaches. 1999. World Scientific Publishing, Singapore.
• [23]: Li, H., Jiang, T. and Zhang, K., Efficient and robust feature extraction by maximum margin criterion. IEEE Trans. Neural Networks. v17 i1. 157-165.
• [24]: Nojun Kwak , Chong-Ho Choi, Input Feature Selection by Mutual Information Based on Parzen Window, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.12, p.1667-1671, December 2002 [doi>10.1109/TPAMI.2002.1114861]
• [25]: Chow, T.W.S. and Huang, D., Estimating optimal feature subsets using efficient estimation of high-dimensional mutual information. IEEE Trans. Neural Networks. v16 i1.
• [26]: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• [27]: Floriana Esposito , Donato Malerba , Giovanni Semeraro, A Comparative Analysis of Methods for Pruning Decision Trees, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.5, p.476-491, May 1997 [doi>10.1109/34.589207]
• [28]: Available at {http://www.csie.ntu.edu.tw/cjlin/libsvm}.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures; Computations on discrete structures

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Design

Keywords:
Distance discriminant, Feature ranking, Optimal feature selection