Unsupervised document classification using sequential information maximization

ABSTRACT

We present a novel sequential clustering algorithm which is motivated by the Information Bottleneck (IB) method. In contrast to the agglomerative IB algorithm, the new sequential (sIB) approach is guaranteed to converge to a local maximum of the information with time and space complexity typically linear in the data size. information, as required by the original IB principle. Moreover, the time and space complexity are significantly improved. We apply this algorithm to unsupervised document classification. In our evaluation, on small and medium size corpora, the sIB is found to be consistently superior to all the other clustering methods we examine, typically by a significant margin. Moreover, the sIB results are comparable to those obtained by a supervised Naive Bayes classifier. Finally, we propose a simple procedure for trading cluster's recall to gain higher precision, and show how this approach can extract clusters which match the existing topics of the corpus almost perfectly.

REFERENCES

• 1: Ron Bekkerman , Ran El-Yaniv , Naftali Tishby , Yoad Winter, On feature distributional clustering for text categorization, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.146-153, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383976]
• 2: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 3: Koji Eguchi, Adaptive cluster-based browsing using incrementally expanded queries and its effects (poster abstract), Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.265-266, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312688]
• 4: R. El-Yaniv and O. Souroujon. Iterative Double Clustering for Unsupervised and Semi-supervised Learning. In Proc. of Neural Information Processing Systems (NIPS-14), 2002, to appear.
• 5: Marti A. Hearst , Jan O. Pedersen, Reexamining the cluster hypothesis: scatter/gather on retrieval results, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.76-84, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243216]
• 6: Nir Friedman , Ori Mosenzon , Noam Slonim , Naftali Tishby, Multivariate Information Bottleneck, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.152-161, August 02-05, 2001
• 7: K. Lang. Learning to filter netnews. In Proc. of the 12th Int. Conf. on Machine Learning, 1995.
• 8: J. Lin. Divergence Measures Based on the Shannon Entropy. IEEE Transactions on Information theory, 37(1), 1991.
• 9: Radford M. Neal , Geoffrey E. Hinton, A view of the EM algorithm that justifies incremental, sparse, and other variants, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 10: Fernando Pereira , Naftali Tishby , Lillian Lee, Distributional clustering of English words, Proceedings of the 31st annual meeting on Association for Computational Linguistics, p.183-190, June 22-26, 1993, Columbus, Ohio [doi>10.3115/981574.981598]
• 11: G. Salton. Developments in Automatic Text Retrieval. Science, Vol. 253, pages 974--980, 1990.
• 12: A. Schriebman, R. El-Yaniv, S. Fine and N. Tishby. On the two-sample problem and the Jensen-Shannon divergence for Markov sources. In preparation.
• 13: N. Slonim and N. Tishby. Agglomerative Information Bottleneck. In Proc. of Neural Information Processing Systems (NIPS-12), 1999.
• 14: Noam Slonim , Naftali Tishby, Document clustering using word clusters via the information bottleneck method, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.208-215, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345578]
• 15: N. Slonim and N. Tishby. The power of word clusters for text classification. In 23rd European Colloquium on Information Retrieval Research (ECIR), 2001.
• 16: N. Slonim, N. Friedman and N. Tishby. Multivariate Agglomerative Information Bottleneck. In Proc. of Neural Information Processing Systems (NIPS-14), 2002, to appear.
• 17: N. Tishby, F. Pereira, and W. Bialek. The Information Bottleneck method. In Proc. 37th Allerton Conference on Communication and Computation. 1999.
• 18: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 19: Oren Zamir , Oren Etzioni, Web document clustering: a feasibility demonstration, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.46-54, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290956]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms, Experimentation, Performance, Theory