Classification assigns documents to categories that someone defined in advance, using examples someone labeled. Clustering assumes neither. Given a collection and a notion of similarity, it finds groups of documents that are more similar to one another than to the rest, and leaves it to people to decide what the groups mean. It is the most common form of unsupervised learning in text processing, because unlabeled text is plentiful and labels are expensive.
Clustering serves retrieval in several ways. It can organize a result list into topics, giving a searcher an overview of an ambiguous query. It can structure a collection for browsing. It can speed up or improve retrieval by searching clusters instead of individual documents. All of these rest on the cluster hypothesis, that documents similar to each other tend to be relevant to the same needs, and this topic begins by testing that hypothesis on real relevance judgments.
The central algorithm is K-means: choose $K$ cluster centers, assign each document to its nearest center, move each center to the mean of its documents, and repeat until nothing changes. The algorithm is short, but using it well requires decisions it does not make: how to start, how many clusters to look for, how to measure similarity, and how to tell whether the result is any good. The topic covers each, compares K-means with hierarchical clustering on Reuters news stories, and ends with the reviewer clustering from my course project.
Articles
The idea
- Clustering and the cluster hypothesis: what clustering is for, hard and soft, flat and hierarchical clustering, and the cluster hypothesis tested on Cranfield four ways: nearest neighbors, similarity distributions, one query traced, and K-means clusters.
K-means
- The K-means algorithm: the objective, the two alternating steps, six points traced by hand, the proof that each step lowers RSS, local minima, an interactive demo, and its cost.
- K-means in practice: initialization and restarts, k-means++ worked out exactly on small examples, choosing K, feature scaling, and spherical K-means for text, with experiments on Reuters.
Judging and comparing
- Evaluating clusterings: internal and external criteria, purity, normalized mutual information, the Rand index, the adjusted Rand index, and the F measure, computed step by step on the textbook's example, and what each makes of degenerate and random clusterings.
- Hierarchical clustering: agglomerative clustering traced by hand under single, complete, average, and centroid linkage, dendrograms, chaining and inversions, the priority-queue algorithm, and a comparison with K-means.
A project
- Clustering Goodreads reviewers: the reviewer features, the five clusters, and how review length shaped them.
Related topics
- Text classification solves the supervised version of the same problem.
- Cosine similarity provides the similarity measure most text clustering uses.
- Search applications describes clustering of search results and topic detection.
- Topic modeling generalizes clustering by letting a document belong partly to several topics.
Course materials
The reviewer clustering in our term project, written by my partner James R. Brown, is in the Goodreads repository. The experiments on Reuters and Cranfield were written for this site.
References
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapters 16–17. Cambridge University Press.
- Jain, A. K. (2010). Data clustering: 50 years beyond K-means. Pattern Recognition Letters, 31(8), 651–666.