Higher order feature selection for text classification

ABSTRACT

In this paper, we present the MIFS-C variant of the mutual information feature-selection algorithms. We present an algorithm to find the optimal value of the redundancy parameter, which is a key parameter in the MIFS-type algorithms. Furthermore, we present an algorithm that speeds up the execution time of all the MIFS variants. Overall, the presented MIFS-C has comparable classification accuracy (in some cases even better) compared with other MIFS algorithms, while its running time is faster. We compared this feature selector with other feature selectors, and found that it performs better in most cases. The MIFS-C performed especially well for the breakeven and F-measure because the algorithm can be tuned to optimise these evaluation measures.

REFERENCES

• 1: Chidanand Apté , Fred Damerau , Sholom M. Weiss, Automated learning of decision rules for text categorization, ACM Transactions on Information Systems (TOIS), v.12 n.3, p.233-251, July 1994 [doi>10.1145/183422.183423]
• 2: 2. Bakus J, Kamel M (2003) Information theoretic feature selection for document classification. In: Proceedings of the Eighth Canadian Workshop on Information Theory, pp 147-150. Waterloo, Ontario, Canada
• 3: 3. Battiti R (1994) Using mutual information for selecting features in supervised neural net learning. IEEE Trans Neural Netw 5(4):537-550
• 4: 4. Devijver PA, Kittler J (1982) Pattern Recognition: A Statistical Approach. Prentice Hall, Englewood Cliffs, N J, USA
• 5: Pedro Domingos , Michael Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning, v.29 n.2-3, p.103-130, Nov./Dec. 1997 [doi>10.1023/A:1007413511361]
• 6: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 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: 8. Fano RM (1961) Transmission of Information: A Statistical Theory of Communication. MIT Press, Cambridge, MA
• 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: 10. Ghiselli EE (1964) Theory of Psychological Measurement. McGraw Hill, New York
• 11: Mark A. Hall, Correlation-based Feature Selection for Discrete and Numeric Class Machine Learning, Proceedings of the Seventeenth International Conference on Machine Learning, p.359-366, June 29-July 02, 2000
• 12: Thorsten Joachims, A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.143-151, July 08-12, 1997
• 13: Thorsten Joachims, A statistical learning learning model of text classification for support vector machines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.128-136, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383974]
• 14: Youngjoong Ko , Jungyun Seo, Automatic text categorization by unsupervised learning, Proceedings of the 18th conference on Computational linguistics, p.453-459, July 31-August 04, 2000, Saarbrücken, Germany [doi>10.3115/990820.990886]
• 15: 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]
• 16: 16. Koller D, Sahami M (1996) Toward optimal feature selection. In: Proceedings of the 13th International Conference on Machine Learning (ICML-96), pp 170-178. Bari, Italy
• 17: 17. Kwak N, Choi C-H (1994) Input feature selection for classification problems. IEEE Trans Neural Netw 13(1):143-159
• 18: David D. Lewis, An evaluation of phrasal and clustered representations on a text categorization task, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.37-50, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133172]
• 19: David Dolan Lewis, Representation and learning in information retrieval, University of Massachusetts, Amherst, MA, 1992
• 20: David D. Lewis , Robert E. Schapire , James P. Callan , Ron Papka, Training algorithms for linear text classifiers, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.298-306, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243277]
• 21: Huan Liu , Hiroshi Motoda, Feature Selection for Knowledge Discovery and Data Mining, Kluwer Academic Publishers, Norwell, MA, 1998
• 22: 22. McCallum A, Nigam K (1998) A comparison of event models for naive Bayes text classification. In: Proceedings of the 1998 AAAI/ICML Workshop on Learning for Text Categorization, pp 41-48. Madison, WI, USA
• 23: 23. MladenićD, Grobelnik M (1998) Word sequences as features in text-learning. In: Proceedings of the Seventh Electrotechnical and Computer Science Conference (ERK-98), pp 145-148. Ljubljana, Slovenia
• 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: 25. Press WH, Flannery BP, Teukolski SA, Vetterling WT (1988) Numerical Recipes in C. Cambridge University Press, Cambridge, UK
• 26: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 27: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 28: G. Salton , A. Wong , C. S. Yang, A vector space model for automatic indexing, Communications of the ACM, v.18 n.11, p.613-620, Nov. 1975 [doi>10.1145/361219.361220]
• 29: Hinrich Schütze , David A. Hull , Jan O. Pedersen, A comparison of classifiers and document representations for the routing problem, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.229-237, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215365]
• 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: 31. Sidlecki W, Sklanski J (1988) On automatic feature selection. Int J Pattern Recogn Artif Intell 2(2): 197-220
• 32: 32. van Rijsbergen CJ, Harper DJ, Porter MF (1981) The selection of good search terms. Inform Process Manage 17(2):77-91
• 33: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 34: 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
• 35: 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]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Design

Keywords:
feature selection, text classification