FAST: a roc-based feature selection metric for small samples and imbalanced data classification problems

ABSTRACT

The class imbalance problem is encountered in a large number of practical applications of machine learning and data mining, for example, information retrieval and filtering, and the detection of credit card fraud. It has been widely realized that this imbalance raises issues that are either nonexistent or less severe compared to balanced class cases and often results in a classifier's suboptimal performance. This is even more true when the imbalanced data are also high dimensional. In such cases, feature selection methods are critical to achieve optimal performance. In this paper, we propose a new feature selection method, Feature Assessment by Sliding Thresholds (FAST), which is based on the area under a ROC curve generated by moving the decision boundary of a single feature classifier with thresholds placed using an even-bin distribution. FAST is compared to two commonly-used feature selection methods, correlation coefficient and RELevance In Estimating Features (RELIEF), for imbalanced data classification. The experimental results obtained on text mining, mass spectrometry, and microarray data sets showed that the proposed method outperformed both RELIEF and correlation methods on skewed data sets and was comparable on balanced data sets; when small number of features is preferred, the classification performance of the proposed method was significantly improved compared to correlation and RELIEF-based methods.

REFERENCES

• 1: Marlon Núñez, The Use of Background Knowledge in Decision Tree Induction, Machine Learning, v.6 n.3, p.231-250, May 1991 [doi>10.1023/A:1022609710832]
• 2: Casasent, D. and Chen, X.-W. 2003. New training strategies for RBF neural networks for X-ray agricultural product inspection. Pattern Recognition, 36(2), 535--547.
• 3: Floor Verdenius, A method for inductive cost optimization, Proceedings of the European working session on learning on Machine learning, p.179-191, March 1991, Porto, Portugal
• 4: Casasent, D. and Chen, X.-W. 2004. Feature reduction and morphological processing for hyperspectral image data. Applied Optics, 43 (2), 1--10.
• 5: Japkowicz, N. editor 2000. Proceedings of the AAAI'2000 Workshop on Learning from Imbalanced Data Sets. AAAI Tech Report WS-00-05.
• 6: Chawla, N., Japkowicz, N., and Kolcz, A. editors 2003. Proceedings of the ICML'2003 Workshop on Learning from Imbalanced Data Sets.
• 7: Gary M. Weiss, Mining with rarity: a unifying framework, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004 [doi>10.1145/1007730.1007734]
• 8: Kubat, M. and Matwin, S. 1997. Addressing the curse of imbalanced data set: One sided sampling. In Proc. of the Fourteenth International Conference on Machine Learning, 179--186.
• 9: Chen, X., Gerlach, B., and Casasent, D. 2005. Pruning support vectors for imbalanced data classification. In Proc. of International Joint Conference on Neural Networks, 3, 1883--1888.
• 10: Miroslav Kubat , Robert Holte , Stan Matwin, Learning When Negative Examples Abound, Proceedings of the 9th European Conference on Machine Learning, p.146-153, April 23-25, 1997
• 11: Chawla, N., Bowyer, K., Hall, L., and Kegelmeyer, P. 2002. SMOTE: Synthetic Minority Over-sampling Technique. Journal of Artificial Intelligence Research 16, 321--357.
• 12: Estabrooks, A., Jo, T., and Japkowicz, N. 2004. A multiple resampling method for learning from imbalanced data sets. Computational Intelligence, 20(1), 18--36.
• 13: Pedro Domingos, MetaCost: a general method for making classifiers cost-sensitive, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.155-164, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312220]
• 14: Elkan, C. 2001. The foundations of cost-sensitive learning. Proc. of the Seventeenth International Joint Conference on Artificial Intelligence, 973--978.
• 15: Tom Fawcett , Foster Provost, Adaptive Fraud Detection, Data Mining and Knowledge Discovery, v.1 n.3, p.291-316, 1997 [doi>10.1023/A:1009700419189]
• 16: Huang, K., Yang, H., King, I., Lyu, M., 2004. Learning classifiers from imbalanced data based on biased minimax probability machine. Proc. of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2(27), II-558 - II-563.
• 17: Ting, K. 1994. The problem of small disjuncts: its remedy on decision trees. Proc. of the Tenth Canadian Conference on Artificial Intelligence, 91--97.
• 18: Chawla, N., Lazarevic, A., Hall, L., and Bowyer, K. 2003. SMOTEBoost: Improving prediction of the minority class in boosting. Principles of Knowledge Discovery in Databases, LNAI 2838, 107--119.
• 19: Yanmin Sun , Mohamed S. Kamel , Yang Wang, Boosting for Learning Multiple Classes with Imbalanced Class Distribution, Proceedings of the Sixth International Conference on Data Mining, p.592-602, December 18-22, 2006 [doi>10.1109/ICDM.2006.29]
• 20: Bhavani Raskutti , Adam Kowalczyk, Extreme re-balancing for SVMs: a case study, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004 [doi>10.1145/1007730.1007739]
• 21: Xiong, H and Chen, X. 2006. Kernel-based distance metric learning for microarray data classification. BMC Bioinformatics, 7, 299.
• 22: George Forman, An extensive empirical study of feature selection metrics for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 23: Peter Van Der Putten , Maarten Van Someren, A Bias-Variance Analysis of a Real World Learning Problem: The CoIL Challenge 2000, Machine Learning, v.57 n.1-2, p.177-195, October-November 2004 [doi>10.1023/B:MACH.0000035476.95130.99]
• 24: 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]
• 25: Isabelle Guyon , André Elisseeff, An introduction to variable and feature selection, The Journal of Machine Learning Research, 3, 3/1/2003
• 26: Weston, J., Mukherjee, S., Chapelle, O. Pontil, M. Poggio, T. and Vapnik, V. 2000. Feature selection for support vector machines. In Advances in Neural Information Processing Systems.
• 27: 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]
• 28: Xue-wen Chen, An improved branch and bound algorithm for feature selection, Pattern Recognition Letters, v.24 n.12, p.1925-1933, August 2003 [doi>10.1016/S0167-8655(03)00020-5]
• 29: 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
• 30: 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]
• 31: Dunja Mladenic , Marko Grobelnik, Feature Selection for Unbalanced Class Distribution and Naive Bayes, Proceedings of the Sixteenth International Conference on Machine Learning, p.258-267, June 27-30, 1999
• 32: Zhaohui Zheng , Xiaoyun Wu , Rohini Srihari, Feature selection for text categorization on imbalanced data, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004 [doi>10.1145/1007730.1007741]
• 33: Ole Lund , Morten Nielsen , Claus Lundegaard , Can Kesmir , Søren Brunak, Immunological Bioinformatics (Computational Molecular Biology), The MIT Press, 2005
• 34: Kenji Kira , Larry A. Rendell, A practical approach to feature selection, Proceedings of the ninth international workshop on Machine learning, p.249-256, July 1992, Aberdeen, Scotland, United Kingdom
• 35: 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
• 36: McCallum, A. 1996. Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering. http://www.cs.cmu.edu/~mccallum/bow.
• 37: Pomeroy, S., Tamayo, P. Gaasenbeek, M., Sturla, L., Angelo, M., McLaughlin, M., Kim, J., Goumnerova, J., Black, P. Lau, C., Allen, J., Zagzag, D., Olson, J., Curran, T., Wetmore, C., Biegel, J., Poggio, T., Mukherjee, S., Rifkin, R., Califano, A., Stolovitzky, G., Louis, D., Mesirov, J., Lander, E. and Golub. T. 2002. Prediction of central nervous system embryonal tumour outcome based on gene expression. Nature, 415, 436--442.
• 38: Shipp, M., Ross, K., Tamayo, P., Weng, A. Kutok, J., Aguiar, R., Gaasenbeek, M., Angelo, M., Reich, M., Pinkus, G., Ray, T., Koval, M., Last, M., Norton, A., Lister, T., Mesirov, T., Neuberg, D., Lander, E., Aster, S., and Golub, T. 2002. Diffuse large b-cell lymphoma outcome prediction by gene expression profiling and supervised machine learning. Nature Medicine, 8, 68--74.
• 39: Petricoin, E., Ardekani, A., Hitt, B., Levine, P., Fusaro, V., Steinberg, S., Mills, G., Simone, C., Fishman, D., Kohn, E. and Liotta, L. 2002. Use of proteomic patterns in serum to identify ovarian cancer. The Lancet, 359, 572--577.
• 40: Petricoin, E., Ornstein, D., Paweletz, C., Ardekani, A., Hackett, P., Hitt, B., Velassco, A., Trucco, C., Wiegand, L., Wood, K., Simone, C., Levine, P., Linehan, W., Emmert-Buck, M., Steinberg, S., Kohn, E. and Liotta, A. 2002. Serum proteomic patterns for detection of prostate cancer. Journal of the National Cancer Institute, 94, 1576--1578.
• 41: Roweis, S. 2008. Personal website. http://www.cs.toronto.edu/ roweis.
• 42: MPS, 2006. Performance predition challenge - evaluation. http://www.modelselect.inf.ethz.ch/evaluation.php.
• 43: Jesse Davis , Mark Goadrich, The relationship between Precision-Recall and ROC curves, Proceedings of the 23rd international conference on Machine learning, p.233-240, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143874]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
ROC, feature selection, imbalanced data classification