Extracting key-substring-group features for text classification

ABSTRACT

In many text classification applications, it is appealing to take every document as a string of characters rather than a bag of words. Previous research studies in this area mostly focused on different variants of generative Markov chain models. Although discriminative machine learning methods like Support Vector Machine (SVM) have been quite successful in text classification with word features, it is neither effective nor efficient to apply them straightforwardly taking all substrings in the corpus as features. In this paper, we propose to partition all substrings into statistical equivalence groups, and then pick those groups which are important (in the statistical sense) as features (named key-substring-group features) for text classification. In particular, we propose a suffix tree based algorithm that can extract such features in linear time (with respect to the total number of characters in the corpus). Our experiments on English, Chinese and Greek datasets show that SVM with key-substring-group features can achieve outstanding performance for various text classification tasks.

REFERENCES

• 1: A. N. Aizawa. Linguistic techniques to improve the performance of automatic text categorization. In Proceedings of the 6th Natural Language Processing Pacific Rim Symposim (NLPRS), pages 307--314, Tokyo, Japan, 2001.
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 4: Michael A. Bender , Martin Farach-Colton, The LCA Problem Revisited, Proceedings of the 4th Latin American Symposium on Theoretical Informatics, p.88-94, April 10-14, 2000
• 5: A. Bratko and B. Filipic. Spam filtering using compression models. Technical Report IJS-DP-9227, Department of Intelligent Systems, Jozef Stefan Institute, Ljubljana, Slovenia, 2005.
• 6: Nicola Cancedda , Eric Gaussier , Cyril Goutte , Jean Michel Renders, Word sequence kernels, The Journal of Machine Learning Research, 3, 3/1/2003
• 7: C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001.
• 8: Chia-Hui Chang , Shao-Chen Lui, IEPAD: information extraction based on pattern discovery, Proceedings of the 10th international conference on World Wide Web, p.681-688, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372182]
• 9: W. I. Chang and E. L. Lawler. Sublinear approximate string matching and biological applications. Algorithmica, 12(4/5):327--344, 1994.
• 10: Stanley F. Chen , Joshua Goodman, An empirical study of smoothing techniques for language modeling, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.310-318, June 24-27, 1996, Santa Cruz, California [doi>10.3115/981863.981904]
• 11: Lee-Feng Chien, PAT-tree-based keyword extraction for Chinese information retrieval, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.50-58, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 12: Kenneth Ward Church , Patrick Hanks, Word association norms, mutual information, and lexicography, Proceedings of the 27th annual meeting on Association for Computational Linguistics, p.76-83, June 26-29, 1989, Vancouver, British Columbia, Canada [doi>10.3115/981623.981633]
• 13: J. G. Cleary and W. J. Teahan. Unbounded length contexts for PPM. The Comput Journal, 40(2-3):67--75, 1997.
• 14: J. G. Cleary and I. H. Witten. Data compression using adaptive coding and partial string matching. IEEE Transactions on Communication, 32(4):396--402, 1984.
• 15: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 16: Douglass R. Cutting , David R. Karger , Jan O. Pedersen , John W. Tukey, Scatter/Gather: a cluster-based approach to browsing large document collections, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-329, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133214]
• 17: 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]
• 18: Eibe Frank , Chang Chui , Ian H. Witten, Text Categorization Using Compression Models, Proceedings of the Conference on Data Compression, p.555, March 28-30, 2000
• 19: 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]
• 20: J. Goodman. A bit of progress in language modeling, extended version. Technical report, Microsoft Research, 2001.
• 21: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 22: J. He, A.-H. Tan, and C.-L. Tan. A comparative study on Chinese text categorization methods. In PRICAI'2000 International Workshop on Text and Web Mining, pages 24--35, Melbourne, Australia, 2000.
• 23: Ji He , Ah-Hwee Tan , Chew-Lim Tan, On Machine Learning Methods for Chinese Document Categorization, Applied Intelligence, v.18 n.3, p.311-322, May-June 2003 [doi>10.1023/A:1023202221875]
• 24: Ralf Herbrich, Learning Kernel Classifiers: Theory and Algorithms, MIT Press, Cambridge, MA, 2001
• 25: D. Holmes and R. Forsyth. The federalist revisited: New directions in authorship attribution. Literary and Linguistic Computing, 10(2):111--127, 1995.
• 26: C.-W. Hsu and C.-J. Lin. A comparison of methods for multi-class support vector machines. IEEE Transactions on Neural Networks, 13(2):415--425, 2002.
• 27: P. Jackson and I. Moulinier. Natural Language Processing for Online Applications: Text Retrieval, Extraction, and Categorization. John Benjamins Publishing Co, 2002.
• 28: Tony Jebara , Risi Kondor , Andrew Howard, Probability Product Kernels, The Journal of Machine Learning Research, 5, p.819-844, 12/1/2004
• 29: 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
• 30: 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]
• 31: Thorsten Joachims, Learning to Classify Text Using Support Vector Machines: Methods, Theory and Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 32: Daniel Jurafsky , James H. Martin, Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 33: Brett Kessler , Geoffrey Numberg , Hinrich Schütze, Automatic detection of text genre, Proceedings of the 35th annual meeting on Association for Computational Linguistics, p.32-38, July 07-12, 1997, Madrid, Spain
• 34: Donald Ervin Knuth, The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 35: John Lafferty , Guy Lebanon, Diffusion Kernels on Statistical Manifolds, The Journal of Machine Learning Research, 6, p.129-163, 9/1/2005
• 36: John Lafferty , Chengxiang Zhai, Document language models, query models, and risk minimization for information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.111-119, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383970]
• 37: Ming-Jer Lee , Lee-Feng Chien, Automatic acquisition of phrasal knowledge for English-Chinese bilingual information retrieval, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.351-352, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291041]
• 38: Yong-Bae Lee , Sung Hyon Myaeng, Text genre classification with genre-revealing and subject-revealing features, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564403]
• 39: C. S. Leslie, E. Eskin, and W. S. Noble. The spectrum kernel: A string kernel for SVM protein classification. In Proceedings of the 7th Pacific Symposium on Biocomputing (PSB), pages 566--575, Lihue, HI, 2002.
• 40: David D. Lewis, Naive (Bayes) at Forty: The Independence Assumption in Information Retrieval, Proceedings of the 10th European Conference on Machine Learning, p.4-15, April 21-23, 1998
• 41: Huma Lodhi , Craig Saunders , John Shawe-Taylor , Nello Cristianini , Chris Watkins, Text classification using string kernels, The Journal of Machine Learning Research, 2, p.419-444, 3/1/2002
• 42: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 43: Y. Marton, N. Wu, and L. Hellerstein. On compression-based text classification. In Proceedings of the 27th European Conference on IR Research (ECIR), pages 300--314, Santiago de Compostela, Spain, 2005.
• 44: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 45: R. M. Pampapathi, B. Mirkin, and M. Levene. A suffix tree approach to email filtering, 2005.
• 46: A. Papoulis. Probability, Random Variables, and Stochastic Processes. McGraw Hill, New York, 2nd edition, 1984.
• 47: Fuchun Peng , Dale Schuurmans , Shaojun Wang, Augmenting Naive Bayes Classifiers with Statistical Language Models, Information Retrieval, v.7 n.3-4, p.317-345, September-December 2004 [doi>10.1023/B:INRT.0000011209.19643.e2]
• 48: Jay M. Ponte , W. Bruce Croft, A language modeling approach to information retrieval, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.275-281, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291008]
• 49: Dana Ron , Yoram Singer , Naftali Tishby, The power of amnesia: learning probabilistic automata with variable memory length, Machine Learning, v.25 n.2-3, p.117-149, Nov./Dec. 1996 [doi>10.1007/BF00114008]
• 50: R. Rosenfeld. Two decades of statistical language modeling: Where do we go from here? Proceedings of the IEEE, 88(8):1270--1278, 2000.
• 51: R. E. Schapire. The boosting approach to machine learning: An overview. In MSRI Workshop on Nonlinear Estimation and Classification, Berkeley, CA, 2002.
• 52: Robert E. Schapire , Yoram Singer, BoosTexter: A Boosting-based Systemfor Text Categorization, Machine Learning, v.39 n.2-3, p.135-168, May-June 2000 [doi>10.1023/A:1007649029923]
• 53: B. Scholkopf and A. J. Smola. Learning with Kernels. MIT Press, Cambridge, MA, 2002.
• 54: 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]
• 55: John Shawe-Taylor , Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, 2004
• 56: Noam Slonim , Gill Bejerano , Shai Fine , Naftali Tishby, Discriminative Feature Selection via Multiclass Variable Memory Markov Model, Proceedings of the Nineteenth International Conference on Machine Learning, p.578-585, July 08-12, 2002
• 57: Efstathios Stamatatos , George Kokkinakis , Nikos Fakotakis, Automatic text categorization in terms of genre and author, Computational Linguistics, v.26 n.4, p.471-495, December 2000 [doi>10.1162/089120100750105920]
• 58: W. J. Teahan and D. J. Harper. Using compression based language models for text categorization. In J. Callan, B. Croft, and J. Lafferty, editors, Workshop on Language Modeling and Information Retrieval, pages 83--88, Carnegie Mellon University, 2001.
• 59: E. Ukkonen. On-line construction of suffix-trees. Algorithmica, 14:249--260, 1995.
• 60: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 61: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 62: S. Vishwanathan and A. Smola. Fast kernels for string and tree matching. In K. Tsuda, B. Scholkopf, and J. Vert, editors, Kernels and Bioinformatics. MIT Press, Cambridge, MA, 2004.
• 63: I. H. Witten. Applications of lossless compression in adaptive text mining. In Proceedings of the 34th Annual Conference on Information Sciences and Systems (CISS), Princeton University, New Jersey, 2000.
• 64: Ian H. Witten , Zane Bray , Malika Mahoui , Bill Teahan, Text Mining: A New Frontier for Lossless Compression, Proceedings of the Conference on Data Compression, p.198, March 29-31, 1999
• 65: Mikio Yamamoto , Kenneth W. Church, Using suffix arrays to compute term frequency and document frequency for all substrings in a corpus, Computational Linguistics, v.27 n.1, p.1-30, March 2001 [doi>10.1162/089120101300346787]
• 66: J. Yang and W. Wang. CLUSEQ: Efficient and effective sequence clustering. In Proceedings of the 19th International Conference on Data Engineering (ICDE), pages 101--112, Bangalore, India, 2003.
• 67: 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]
• 68: 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
• 69: Oren Zamir , Oren Etzioni, Grouper: a dynamic clustering interface to Web search results, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1361-1374, May 17, 1999
• 70: C. Zhai. Risk Minimization and Language Modeling in Information Retrieval. PhD thesis, Carnegie Mellon University, 2002.
• 71: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to information retrieval, ACM Transactions on Information Systems (TOIS), v.22 n.2, p.179-214, April 2004 [doi>10.1145/984321.984322]
• 72: Dell Zhang , Xi Chen , Wee Sun Lee, Text classification with kernels on the multinomial manifold, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076081]
• 73: D. Zhang and Y. Dong. Semantic, hierarchical, online clustering of web search results. In Proceedings of the 6th Asia Pacific Web Conference (APWEB), Hangzhou, China, 2004.
• 74: G. K. Zipf. Human Behaviour and the Principle of Least Effort. Addison-Wesley, Cambridge, MA, 1949.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

  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; Feature evaluation and selection

General Terms:
Algorithms, Experimentation

Keywords:
feature extraction, machine learning, suffix tree, text classification, text mining