Unsupervised document classification using sequential information maximization
Noam Slonim, Nir Friedman, Naftali Tishby · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · 2002
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.
Cited by 249 works. doi:10.1145/564376.564401
Authors
References
- Elements of Information Theory
- A View of the Em Algorithm that Justifies Incremental, Sparse, and other Variants
- Distributional clustering of English words
- NewsWeeder: Learning to Filter Netnews
- Divergence measures based on the Shannon entropy
- Developments in Automatic Text Retrieval
- The information bottleneck method
- Reexamining the cluster hypothesis
- Web document clustering
- Agglomerative Information Bottleneck