Scaling up text classification for large file systems

ABSTRACT

We combine the speed and scalability of information retrieval with the generally superior classification accuracy offered by machine learning, yielding a two-phase text classifier that can scale to very large document corpora. We investigate the effect of different methods of formulating the query from the training set, as well as varying the query size. In empirical tests on the Reuters RCV1 corpus of 806,000 documents, we find runtime was easily reduced by a factor of 27x, with a somewhat surprising gain in F-measure compared with traditional text classification.

REFERENCES

• 1: Aris Anagnostopoulos , Andrei Z. Broder , Kunal Punera, Effective and efficient classification on a search-engine model, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183648]
• 2: Andrei Z. Broder , David Carmel , Michael Herscovici , Aya Soffer , Jason Zien, Efficient query evaluation using a two-level retrieval process, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956944]
• 3: John R. Douceur , William J. Bolosky, A large-scale study of file-system contents, ACM SIGMETRICS Performance Evaluation Review, v.27 n.1, p.59-70, June 1999
• 4: George Forman, Quantifying trends accurately despite classifier error and class imbalance, 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.1150423]
• 5: George Forman, An extensive empirical study of feature selection metrics for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 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: Josef Kittler , Mohamad Hatef , Robert P. W. Duin , Jiri Matas, On Combining Classifiers, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.3, p.226-239, March 1998 [doi>10.1109/34.667881]
• 9: 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
• 10: Huitao Luo, Optimization Design of Cascaded Classifiers, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1, p.480-485, June 20-26, 2005 [doi>10.1109/CVPR.2005.266]
• 11: Jason Van Hulse , Taghi M. Khoshgoftaar , Amri Napolitano, Experimental perspectives on learning from imbalanced data, Proceedings of the 24th international conference on Machine learning, p.935-942, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273614]
• 12: Viola, P. and Jones, M. J. 2002. Robust real-time object detection. International Journal of Computer Vision.
• 13: 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:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process; Query formulation

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
document categorization, enterprise scalability, forensic search, information retrieval, machine learning, text classification