Feature selection methods for text classification

ABSTRACT

We consider feature selection for text classification both theoretically and empirically. Our main result is an unsupervised feature selection strategy for which we give worst-case theoretical guarantees on the generalization power of the resultant classification function f with respect to the classification function f obtained when keeping all the features. To the best of our knowledge, this is the first feature selection method with such guarantees. In addition, the analysis leads to insights as to when and why this feature selection strategy will perform well in practice. We then use the TechTC-100, 20-Newsgroups, and Reuters-RCV2 data sets to evaluate empirically the performance of this and two simpler but related feature selection strategies against two commonly-used strategies. Our empirical evaluation shows that the strategy with provable performance guarantees performs well in comparison with other commonly-used feature selection strategies. In addition, it performs better on certain datasets under very aggressive feature selection.

REFERENCES

• 1: 20 Newsgroups Dataset. J. Rennie. http://people.csail.mit.edu/jrennie/20Newsgroups/.
• 2: 20 Newsgroups Dataset. UCI KDD Archive. http://kdd.ics.uci.edu/databases/20newsgroups/20newsgroups.html.
• 3: Deepak K. Agarwal, Shrinkage estimator generalizations of Proximal Support Vector Machines, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775073]
• 4: Avrim L. Blum , Pat Langley, Selection of relevant features and examples in machine learning, Artificial Intelligence, v.97 n.1-2, p.245-271, Dec. 1997 [doi>10.1016/S0004-3702(97)00063-5]
• 5: Avrim L. Blum , Ronald L. Rivest, Training a 3-node neural network is NP-complete, Neural Networks, v.5 n.1, p.117-127, 1992 [doi>10.1016/S0893-6080(05)80010-3]
• 6: M. Charikar , V. Guruswami , R. Kumar , S. Rajagopalan , A. Sahai, Combinatorial feature selection problems, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.631, November 12-14, 2000
• 7: A. Das and D. Kempe. Algorithms for subset selection in linear regression. Manuscript.
• 8: Anirban Dasgupta , Petros Drineas , Boulos Harb , Ravi Kumar , Michael W. Mahoney, Sampling algorithms and coresets for ℓ_p regression, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.932-941, January 20-22, 2008, San Francisco, California
• 9: Dmitry Davidov , Evgeniy Gabrilovich , Shaul Markovitch, Parameterized generation of labeled datasets for text categorization based on a hierarchical directory, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009036]
• 10: James Demmel , Krešimir Veselic, Jacobi's method is more accurage than QR, SIAM Journal on Matrix Analysis and Applications, v.13 n.4, p.1204-1245, Oct. 1992 [doi>10.1137/0613074]
• 11: Petros Drineas , Michael W. Mahoney , S. Muthukrishnan, Sampling algorithms for l₂ regression and applications, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1127-1136, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109682]
• 12: T. Evgeniou, M. Pontil, and T. Poggio. Regularization networks and support vector machines. Advances in Computational Mathematics, 13(1):1--50, 1999.
• 13: George Forman, An extensive empirical study of feature selection metrics for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 14: Dimitris Fragoudis , Dimitris Meretakis , Spiros Likothanassis, Integrating feature and instance selection for text classification, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775120]
• 15: Glenn Fung , Olvi L. Mangasarian, Proximal support vector machine classifiers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.77-86, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502527]
• 16: Evgeniy Gabrilovich , Shaul Markovitch, Text categorization with many redundant features: using aggressive feature selection to make SVMs competitive with C4.5, Proceedings of the twenty-first international conference on Machine learning, p.41, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015388]
• 17: Isabelle Guyon , André Elisseeff, An introduction to variable and feature selection, The Journal of Machine Learning Research, 3, 3/1/2003
• 18: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 19: Hyunsoo Kim , Peg Howland , Haesun Park, Dimension Reduction in Text Classification with Support Vector Machines, The Journal of Machine Learning Research, 6, p.37-53, 12/1/2005
• 20: 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]
• 21: K. Lang. Newsweeder: Learning to filter netnews. In Proceedings of the 12th International Conference on Machine Learning, pages 331--339, 1995.
• 22: Edda Leopold , Jörg Kindermann, Text Categorization with Support Vector Machines. How to Represent Texts in Input Space?, Machine Learning, v.46 n.1-3, p.423-444, 2002 [doi>10.1023/A:1012491419635]
• 23: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 24: 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
• 25: T. Poggio and S. Smale. The mathematics of learning: Dealing with data. Notices of the AMS, 50(5):537--544, May 2003.
• 26: Ryan Michael Rifkin , Tomaso Poggio, Everything old is new again: a fresh look at historical approaches in machine learning, Massachusetts Institute of Technology, 2002
• 27: R. Rifkin, G. Yeo, and T. Poggio. Regularized least-squares classification. In J. A. K. Suykens, G. Horvath, S. Basu, C. Micchelli, and J. Vandewalle, editors, Advances in Learning Theory: Methods, Models and Applications, NATO Science Series III: Computer and Systems Sciences, pages 131--154. VIOS Press, 2003.
• 28: M. Rudelson and R. Vershynin. Sampling from large matrices: an approach through geometric functional analysis. Manuscript. Salton. Proceedings of the 14th Annual International ACM SIGIR Conference, pages 356--358, 1991.
• 29: Bernhard Schölkopf , Ralf Herbrich , Alex J. Smola, A Generalized Representer Theorem, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.416-426, July 16-19, 2001
• 30: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 31: G. W. Stewart and J. G. Sun. Matrix Perturbation Theory. Academic Press, New York, 1990.
• 32: J. A. K. Suykens , J. Vandewalle, Least Squares Support Vector Machine Classifiers, Neural Processing Letters, v.9 n.3, p.293-300, June 1999 [doi>10.1023/A:1018628609742]
• 33: A. N. Tikhonov and V. Y. Arsenin. Solutions of Ill-Posed Problems. W. H. Winston, Washington, D. C., 1977.
• 34: V. N. Vapnik. Statistical Learning Theory. Wiley, New York, 1998.
• 35: Yiming Yang, Noise reduction in a statistical approach to text categorization, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.256-263, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215367]
• 36: Y. Yang. Sampling strategies and learning efficiency in text categorization. In AAAI Spring Symposium on Machine Learning in Information Access, pages 88--95, 1996.
• 37: Yiming Yang , Xin Liu, A re-examination of text categorization methods, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.42-49, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312647]
• 38: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997
• 39: Jian Zhang , Yiming Yang, Robustness of regularized linear classification methods in text categorization, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860471]
• 40: Peng Zhang , Jing Peng, SVM vs Regularized Least Squares Classification, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 1, p.176-179, August 23-26, 2004 [doi>10.1109/ICPR.2004.882]
• 41: Tong Zhang , Frank J. Oles, Text Categorization Based on Regularized Linear Classification Methods, Information Retrieval, v.4 n.1, p.5-31, April 2001 [doi>10.1023/A:1011441423217]

INDEX TERMS

Primary Classification:
  E. Data
  E.m MISCELLANEOUS

Additional Classification:
  H. Information Systems
  H.m MISCELLANEOUS

General Terms:
Algorithms, Experimentation

Keywords:
feature selection, random sampling, regularized least squares classification, text classification