A parallel learning algorithm for text classification

ABSTRACT

Text classification is the process of classifying documents into predefined categories based on their content. Existing supervised learning algorithms to automatically classify text need sufficient labeled documents to learn accurately. Applying the Expectation-Maximization (EM) algorithm to this problem is an alternative approach that utilizes a large pool of unlabeled documents to augment the available labeled documents. Unfortunately, the time needed to learn with these large unlabeled documents is too high. This paper introduces a novel parallel learning algorithm for text classification task. The parallel algorithm is based on the combination of the EM algorithm and the naive Bayes classifier. Our goal is to improve the computational time in learning and classifying process. We studied the performance of our parallel algorithm on a large Linux PC cluster called PIRUN Cluster. We report both timing and accuracy results. These results indicate that the proposed parallel algorithm is capable of handling large document collections.

REFERENCES

• 1: Rakesh Agrawal , John C. Shafer, Parallel Mining of Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.962-969, December 1996 [doi>10.1109/69.553164]
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Inderjit S. Dhillon , Dharmendra S. Modha, A Data-Clustering Algorithm on Distributed Memory Multiprocessors, Revised Papers from Large-Scale Parallel Data Mining, Workshop on Large-Scale Parallel KDD Systems, SIGKDD, p.245-260, August 15, 1999
• 4: Forman, G., and Zhang, B. Linear speed-up for a parallel non-approximate recasting of center-based clustering algorithms, including k-means, k-harmonic means, and EM. KDD Workshop on Distributed and Parallel Knowledge Discovery, 2000.
• 5: Goharian, N., El-Ghazawi, T., Grossman, D., and Chowdhury, A. On the enhancements of a sparse matrix information retrieval approach. Proceedings of the International Conference on Parallel and distributed Processing Techniques and Applications, 1999.
• 6: William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI (2nd ed.): portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1999
• 7: 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
• 8: ScalParC: A New Scalable and Efficient Parallel Classification Algorithm for Mining Large Datasets, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.573, March 30-April 03, 1998
• 9: Lewis, D., and Ringuette, M. A comparison of two learning algorithms for text categorization. In Third Annual Symposium on Document Analysis and Information Retrieval, pages 81--93, 1994.
• 10: McCallum, A., and Nigam, K. A comparison of events models for naive Bayes text classification. Papers from the AAAI Workshop, pages 41--48, 1998.
• 11: MeLachlan, G.J., and Krishnan, T. The EM algorithm and extensions. John Wiley & Sons, 1997.
• 12: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 13: Kamal Nigam , Andrew Kachites McCallum , Sebastian Thrun , Tom Mitchell, Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning, v.39 n.2-3, p.103-134, May-June 2000 [doi>10.1023/A:1007692713085]
• 14: Ridge, D., Becker D., and Merkey, P. 1997. Beowulf: Harnessing the power of parallelism in a Pile-of-PCs. Proceedings, IEEE Aerospace.
• 15: Anthony S. Ruocco , Ophir Frieder, Clustering and classification of large document bases in a parallel environment, Journal of the American Society for Information Science, v.48 n.10, p.932-943, Oct. 1997 [doi>10.1002/(SICI)1097-4571(199710)48:10<932::AID-ASI7>3.0.CO;2-2]
• 16: Rajeev Thakur , William Gropp , Ewing Lusk, Optimizing noncontiguous accesses in MPI – IO, Parallel Computing, v.28 n.1, p.83-105, January, 2002 [doi>10.1016/S0167-8191(01)00129-6]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Text analysis

General Terms:
Algorithms, Experimentation, Performance

Keywords:
cluster computing, naive Bayes, parallel expectation-maximization (EM) algorithm, text classification