Extremely fast text feature extraction for classification and indexing

ABSTRACT

Most research in speeding up text mining involves algorithmic improvements to induction algorithms, and yet for many large scale applications, such as classifying or indexing large document repositories, the time spent extracting word features from texts can itself greatly exceed the initial training time. This paper describes a fast method for text feature extraction that folds together Unicode conversion, forced lowercasing, word boundary detection, and string hash computation. We show empirically that our integer hash features result in classifiers with equivalent statistical performance to those built using string word features, but require far less computation and less memory.

REFERENCES

• 1: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 2: Beate Commentz-Walter, A String Matching Algorithm Fast on the Average, Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.118-132, July 16-20, 1979
• 3: George Forman, An extensive empirical study of feature selection metrics for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 4: George Forman , Shyamsundar Rajaram, Scaling up text classification for large file systems, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401923]
• 5: Ganchev, K. and Dredze, M. 2008. Small statistical models by random feature mixing. In Workshop on Mobile Language Processing, Annual Meeting of the Association for Computational Linguistics (June 20, 2008). ACL'08.
• 6: Erik Hatcher , Otis Gospodnetic, Lucene in Action (In Action series), Manning Publications Co., Greenwich, CT, 2004
• 7: Thorsten Joachims, Training linear SVMs in linear time, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150429]
• 8: Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
• 9: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 10: B. J. McKenzie , R. Harries , T. Bell, Selecting a hashing algorithm, Software—Practice & Experience, v.20 n.2, p.209-224, February 1990 [doi>10.1002/spe.4380200207]
• 11: Mladenic, D. and Grobelnik, M. 1998. Word sequences as features in text-learning. In Proc. 17th Electrotechnical and Computer Science Conference (ERK98), Slovenia.
• 12: Shyamsundar Rajaram , Martin Scholz, Client-Friendly Classification over Random Hyperplane Hashes, Proceedings of the European conference on Machine Learning and Knowledge Discovery in Databases - Part II, September 15-19, 2008, Antwerp, Belgium [doi>10.1007/978-3-540-87481-2_17]
• 13: Leena Salmela , Jorma Tarhio , Jari Kytöjoki, Multipattern string matching with q-grams, Journal of Experimental Algorithmics (JEA), 11, 2006 [doi>10.1145/1187436.1187438]
• 14: CORPORATE The Unicode Consortium, The Unicode standard, version 2.0, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 15: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
bag-of-words, document categorization, feature engineering, feature extraction, text indexing, text mining, text tokenization