Text categorization with many redundant features: using aggressive feature selection to make SVMs competitive with C4.5

ABSTRACT

Text categorization algorithms usually represent documents as bags of words and consequently have to deal with huge numbers of features. Most previous studies found that the majority of these features are relevant for classification, and that the performance of text categorization with support vector machines peaks when no feature selection is performed. We describe a class of text categorization problems that are characterized with many redundant features. Even though most of these features are relevant, the underlying concepts can be concisely captured using only a few features, while keeping all of them has substantially detrimental effect on categorization accuracy. We develop a novel measure that captures feature redundancy, and use it to analyze a large collection of datasets. We show that for problems plagued with numerous redundant features the performance of C4.5 is significantly superior to that of SVM, while aggressive feature selection allows SVM to beat C4.5 by a narrow margin.

REFERENCES

• 1: Bekkerman, R. (2003). Distributional clustering of words for text categorization. Master's thesis, CS Department, Technion---Israel Inst. of Technology.
• 2: Brank, J., Grobelnik, M., Milic-Frayling, N., & Mladenic, D. (2002). Interaction of feature selection methods and linear classification models. Workshop on Text Learning held at ICML-2002.
• 3: Soumen Chakrabarti , Mukul M. Joshi , Kunal Punera , David M. Pennock, The structure of broad topics on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511480]
• 4: Doron Cohen , Michael Herscovici , Yael Petruschka , Yoëlle S. Maarek , Aya Soffer, Personalized pocket directories for mobile devices, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511528]
• 5: 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]
• 6: Duda, R., & Hart, P. (1973). Pattern classification and scene analysis. John Wiley and Sons.
• 7: Susan Dumais , John Platt , David Heckerman , Mehran Sahami, Inductive learning algorithms and representations for text categorization, Proceedings of the seventh international conference on Information and knowledge management, p.148-155, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288651]
• 8: Fellbaum, C. (Ed.). (1998). Wordnet: An electronic lexical database. MIT Press.
• 9: George Forman, An extensive empirical study of feature selection metrics for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 10: 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
• 11: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 12: Lang, K. (1995). Newsweeder: Learning to filter net-news. ICML'95 (pp. 331--339).
• 13: 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]
• 14: 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
• 15: Dunja Mladenic, Feature Subset Selection in Text-Learning, Proceedings of the 10th European Conference on Machine Learning, p.95-100, April 21-23, 1998
• 16: Mladenic, D., & Grobelnik, M. (1998). Word sequences as features in text-learning. Proc. of 7th Electrotech. and Comp. Sci. Conf. (pp. 145--148).
• 17: Bo Pang , Lillian Lee , Shivakumar Vaithyanathan, Thumbs up?: sentiment classification using machine learning techniques, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.79-86, July 06, 2002 [doi>10.3115/1118693.1118704]
• 18: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 19: Reuters (1997). Reuters-21578 text categorization test collection, Distribution 1.0. Reuters. http://www.daviddlewis.com/resources/testcollections/reuters21578.
• 20: Monica Rogati , Yiming Yang, High-performing feature selection for text classification, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584911]
• 21: Sam Scott , Stan Matwin, Feature Engineering for Text Classification, Proceedings of the Sixteenth International Conference on Machine Learning, p.379-388, June 27-30, 1999
• 22: 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]
• 23: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 24: Stefan Wermter , Chihli Hung, Selforganizing classification on the Reuters news corpus, Proceedings of the 19th international conference on Computational linguistics, p.1-7, August 24-September 01, 2002, Taipei, Taiwan [doi>10.3115/1072228.1072315]
• 25: 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]
• 26: 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
• 27: Yiming Yang , Seán Slattery , Rayid Ghani, A Study of Approaches to Hypertext Categorization, Journal of Intelligent Information Systems, v.18 n.2-3, p.219-241, March-May 2002 [doi>10.1023/A:1013685612819]