Consensus group stable feature selection

ABSTRACT

Stability is an important yet under-addressed issue in feature selection from high-dimensional and small sample data. In this paper, we show that stability of feature selection has a strong dependency on sample size. We propose a novel framework for stable feature selection which first identifies consensus feature groups from subsampling of training samples, and then performs feature selection by treating each consensus feature group as a single entity. Experiments on both synthetic and real-world data sets show that an algorithm developed under this framework is effective at alleviating the problem of small sample size and leads to more stable feature selection results and comparable or better generalization performance than state-of-the-art feature selection algorithms. Synthetic data sets and algorithm source code are available at http://www.cs.binghamton.edu/~lyu/KDD09/.

REFERENCES

• 1: Annalisa Appice , Michelangelo Ceci , Simon Rawles , Peter Flach, Redundant feature elimination for multi-class problems, Proceedings of the twenty-first international conference on Machine learning, p.5, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015397]
• 2: Eric Bauer , Ron Kohavi, An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants, Machine Learning, v.36 n.1-2, p.105-139, July-August 1999 [doi>10.1023/A:1007515423169]
• 3: Xue-wen Chen , Jong Cheol Jeong, Minimum reference set based feature selection for small sample classifications, Proceedings of the 24th international conference on Machine learning, p.153-160, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273516]
• 4: Yizong Cheng, Mean Shift, Mode Seeking, and Clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.8, p.790-799, August 1995 [doi>10.1109/34.400568]
• 5: Chris Ding , Hanchuan Peng, Minimum Redundancy Feature Selection from Microarray Gene Expression Data, Proceedings of the IEEE Computer Society Conference on Bioinformatics, p.523, August 11-14, 2003
• 6: X. Z. Fern and C. Brodley. Random projection for high-dimensional data clustering: a cluster ensemble approach. In Proceedings of the twentieth International Conference on Machine Learning, pages 186--193, 2003.
• 7: George Forman, An extensive empirical study of feature selection metrics for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 8: T. R. Golub, D. K. Slonim, P. Tamayo, et al. Molecular classification of cancer: class discovery and class prediction by gene expression monitoring. Science, 286:531--537, 1999.
• 9: Isabelle Guyon , Jason Weston , Stephen Barnhill , Vladimir Vapnik, Gene Selection for Cancer Classification using Support Vector Machines, Machine Learning, v.46 n.1-3, p.389-422, 2002 [doi>10.1023/A:1012487302797]
• 10: Kees Jong , Jérémie Mary , Antoine Cornuéjols , Elena Marchiori , Michèle Sebag, Ensemble feature ranking, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.267-278, September 20-24, 2004, Pisa, Italy
• 11: Alexandros Kalousis , Julien Prados , Melanie Hilario, Stability of feature selection algorithms: a study on high-dimensional spaces, Knowledge and Information Systems, v.12 n.1, p.95-116, May 2007 [doi>10.1007/s10115-006-0040-8]
• 12: Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
• 13: 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]
• 14: Tao Li , Chengliang Zhang , Mitsunori Ogihara, A comparative study of feature selection and multiclass classification methods for tissue classification based on gene expression, Bioinformatics, v.20 n.15, p.2429-2437, October 2004 [doi>10.1093/bioinformatics/bth267]
• 15: H. Liu, J. Li, and L. Wong. A comparative study on feature selection and classification methods using gene expression profiles and proteomic patterns. Genome Informatics, 13:51--60, 2002.
• 16: Huan Liu , Lei Yu, Toward Integrating Feature Selection Algorithms for Classification and Clustering, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.491-502, April 2005 [doi>10.1109/TKDE.2005.66]
• 17: Thomas M. Mitchell, Machine Learning, McGraw-Hill, Inc., New York, NY, 1997
• 18: Andrew Y. Ng, On Feature Selection: Learning with Exponentially Many Irrelevant Features as Training Examples, Proceedings of the Fifteenth International Conference on Machine Learning, p.404-412, July 24-27, 1998
• 19: M. S. Pepe, R. Etzioni, Z. Feng, et al. Phases of biomarker development for early detection of cancer. J Natl Cancer Inst, 93:1054--1060, 2001.
• 20: E. F. Petricoin, A. M. Ardekani, B. A. Hitt, et al. Use of proteomic patterns in serum to identify ovarian cancer. Lancet, 359:572--577, 2002.
• 21: Yvan Saeys , Thomas Abeel , Yves Peer, Robust Feature Selection Using Ensemble Feature Selection Techniques, Proceedings of the European conference on Machine Learning and Knowledge Discovery in Databases - Part II, September 15-19, 2008, Antwerp, Belgium [doi>10.1007/978-3-540-87481-2_21]
• 22: Le Song , Alex Smola , Arthur Gretton , Karsten M. Borgwardt , Justin Bedo, Supervised feature selection via dependence estimation, Proceedings of the 24th international conference on Machine learning, p.823-830, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273600]
• 23: Alexander Strehl , Joydeep Ghosh, Cluster ensembles --- a knowledge reuse framework for combining multiple partitions, The Journal of Machine Learning Research, 3, p.583-617, 3/1/2003 [doi>10.1162/153244303321897735]
• 24: M. P. Wand and M. C. Jones. Kernel Smoothing. Chapman and Hall, 1995.
• 25: 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
• 26: Lei Yu , Chris Ding , Steven Loscalzo, Stable feature selection via dense feature groups, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401986]
• 27: Lei Yu , Huan Liu, Efficient Feature Selection via Analysis of Relevance and Redundancy, The Journal of Machine Learning Research, 5, p.1205-1224, 12/1/2004

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
ensemble, feature selection, high-dimensional data, small sample, stability