Feature selection with conditional mutual information maximin in text categorization

ABSTRACT

Feature selection is an important component of text categorization. This technique can both increase a classifier's computation speed, and reduce the overfitting problem. Several feature selection methods, such as information gain and mutual information, have been widely used. Although they greatly improve the classifier's performance, they have a common drawback, which is that they do not consider the mutual relationships among the features. In this situation, where one feature's predictive power is weakened by others, and where the selected features tend to bias towards major categories, such selection methods are not very effective. In this paper, we propose a novel feature selection method for text categorization called <i>conditional mutual information maximin</i> (CMIM). It can select a set of individually discriminating and weakly dependent features. The experimental results show that CMIM can perform much better than traditional feature selection methods.

REFERENCES

• 1: Michael W. Berry , Susan T. Dumais , Gavin W. O'Brien, Using linear algebra for intelligent information retrieval, SIAM Review, v.37 n.4, p.573-595, Dec. 1995 [doi>10.1137/1037127]
• 2: Maria Fernanda Caropreso , Stan Matwin , Fabrizio Sebastiani, A learner-independent evaluation of the usefulness of statistical phrases for automated text categorization, Text databases & document management: theory & practice, Idea Group Publishing, Hershey, PA, 2001
• 3: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 4: Mark Craven , Dan DiPasquo , Dayne Freitag , Andrew McCallum , Tom Mitchell , Kamal Nigam , Seán Slattery, Learning to extract symbolic knowledge from the World Wide Web, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.509-516, July 1998, Madison, Wisconsin, United States
• 5: S. Deerwester, S. Dumais, G. Furnas, T. Landauer, and R. Harshman. Indexing by latent semantic indexing. Jounal of the American Socity for Information Science, 1990.
• 6: 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]
• 7: Ted Dunning, Accurate methods for the statistics of surprise and coincidence, Computational Linguistics, v.19 n.1, March 1993
• 8: F. Fleuret. Binary feature selection with conditional mutual infomration. Technical Report, 2003.
• 9: Luigi Galavotti , Fabrizio Sebastiani , Maria Simi, Experiments on the Use of Feature Selection and Negative Evidence in Automated Text Categorization, Proceedings of the 4th European Conference on Research and Advanced Technology for Digital Libraries, p.59-68, September 18-20, 2000
• 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: T. Joachims. A probabilistic analysis of the rocchio algorithm with tfidf for text categorization. In Procedings 4th European Conference on Reaserch and Advanced Technology for Digital Libraries (ECDL'00), 2000.
• 12: D. Lewis and M. Ringuette. Comparison of two learning algorithms for text categorization. In Procedings of the 3rd Annual Symposium on Document Analysis and Information Retrieval (SDAIR'94), 1994.
• 13: Dunja Mladenic, Feature Subset Selection in Text-Learning, Proceedings of the 10th European Conference on Machine Learning, p.95-100, April 21-23, 1998
• 14: I. Moulinier. Is learning bias an issue on the text categorization problem? Technical report, 1997.
• 15: K. Nigam, J. Lafferty, and A. McCallum. Using maximum entropy for text classification. In IJCAI-99 Workshop on Machine Learning for Information Filtering, 1999.
• 16: J. Platt. Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods, 2000.
• 17: 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]
• 18: Fabrizio Sebastiani, Machine learning in automated text categorisation, Centre National de la Recherche Scientifique, Paris, France, 1999
• 19: I. Tsamardinos, C. Aliferis, and A. Statnikov. Algorithms for large scale markov blanket discovery. In Proceedings of the 16th International Florida Artificial Intelligence Research Society Conference(FLAIRS), 2003.
• 20: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 21: E. Wiener, J. Pedersen, and A. Weigend. A neural network approach to topic spotting. In Procedings of the 4th Annual Symposium on Document Analysis and Information Retrieval (SDAIR'95), 1995.
• 22: H. Yang and J. Moody. Feature selection based on joint mutual information. In Proceedings of International ICSC Symposium on Advances in Intelligent Data Analysis, 1999.
• 23: Yiming Yang , Christopher G. Chute, A Linear Least Squares Fit mapping method for information retrieval from natural language texts, Proceedings of the 14th conference on Computational linguistics, August 23-28, 1992, Nantes, France [doi>10.3115/992133.992139]
• 24: 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

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
          Subjects: Induction
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing

Keywords:
Naïve Bayes, SVMs, classification, conditional mutual information, feature selection, text categorization