Automatic Cluster Stopping with Criterion Functions and the Gap Statistic

Ted Pedersen, Anagha KulkarniNAACL 2006

TL;DR

This paper introduces four novel methods (PK1, PK2, PK3, and an adaptation of the Gap Statistic) for automatically determining the optimal number of clusters in unsupervised learning tasks like word sense disambiguation and name discrimination. These methods are integrated into the SenseClusters system, offering a more robust solution than manually specifying the cluster count.

What Problem Does This Paper Address?

In many unsupervised learning scenarios, such as distinguishing between different meanings of a word (word sense disambiguation) or identifying unique individuals with the same name (name discrimination), we often need to group similar pieces of text (contexts) into clusters. Each cluster ideally represents a distinct sense or identity. A major challenge is that the "correct" number of clusters, often denoted as k, is usually unknown beforehand. Traditional approaches require users to pre-specify k, which is impractical in real-world applications. This paper addresses this gap by proposing and evaluating methods to automatically determine the optimal k without prior knowledge.

Methods

The paper presents four distinct methods for automatic cluster stopping, all implemented within the SenseClusters system:

  • PK1, PK2, and PK3: These methods are based on interpreting the trend of a clustering criterion function (specifically, the H2 criterion, which measures within-cluster similarity relative to between-cluster similarity) as the number of clusters (k) increases.
  • PK1: Adapts a technique that calculates a score for each k based on its deviation from the mean criterion function value, normalized by the standard deviation. A threshold is used to select k.
  • PK2: Examines the ratio of the criterion function at k to k-1. A ratio close to 1 indicates a plateau in improvement, suggesting k has reached its optimal point.
  • PK3: Uses a formula similar to the Dice Coefficient to compare the criterion function at k with its preceding and succeeding values. It aims to find a point where the criterion function's increase suddenly slows down.
  • Gap Statistic Adaptation: This method, inspired by Tibshirani et al. (2001), compares the clustering of the observed data with a "null reference distribution" (data generated to have no meaningful clusters). The k that maximizes the difference between the observed data's criterion function and the reference data's criterion function is chosen. This approach is distinct as it doesn't rely on finding a "knee point" in a single graph.

The paper uses K-means clustering as the underlying partitional clustering algorithm.

Datasets

The paper uses examples involving the name conflation of "Sonia Gandhi" and "Leonid Kuchma" to illustrate the methods. They also mention conducting experiments with words that have been manually sense-tagged and creating "name conflations" where multiple names are replaced by a single ambiguous name to simulate ambiguity. No specific large-scale datasets are explicitly listed or introduced as new benchmarks.

Key Insights and Ideas

  • The "knee point" problem: For many criterion functions, like the H2 statistic, simply looking for a sharp "knee" or elbow in the plot of the criterion function versus k is not always effective, as the curves can be gradual.
  • Criterion function trends are key: The proposed PK methods leverage the behavior of criterion functions as k changes, rather than just their absolute values, to infer the optimal number of clusters.
  • Gap Statistic offers a different perspective: The adapted Gap Statistic provides a more robust approach by comparing the observed data's clustering quality against a baseline of random noise, making it less susceptible to the shape of the criterion function curve.
  • Practical necessity: Automatically determining k is crucial for making unsupervised clustering methods practical for real-world applications where users lack prior knowledge of the data's inherent structure.

Key Results

The paper demonstrates the application of the four methods using the "Sonia Gandhi" and "Leonid Kuchma" example. For this specific case:

  • The H2 criterion plot shows a gradual curve, making it difficult to visually determine k.
  • The PK1, PK2, and PK3 measures all predict 2 senses for this name conflation.
  • The adapted Gap Statistic, when applied to the H2 criterion, predicts 3 senses for the same name conflation.

The authors note that the PK1 threshold might need empirical adjustment for different datasets.

Limitations and Future Work

  • PK1 threshold sensitivity: The paper acknowledges that the empirically determined threshold for PK1 (-0.70) might need adjustment for different datasets, suggesting it's not a universally fixed value.
  • PK3's critical region: The selection of k for PK3 involves identifying a value closest to (but greater than) the standard deviation of PK3, which could still involve some degree of interpretation.
  • Gap Statistic adaptation: While the paper presents an adaptation of the Gap Statistic, it's noted that the original formulation is based on within-cluster dispersion, and their adaptation allows for any criterion function. Further exploration of this flexibility might be beneficial.
  • Future work: The paper implicitly suggests that further evaluation and refinement of these methods across a wider range of datasets and tasks would be valuable. The integration into the SenseClusters system itself is a step towards practical application.

Summary updated

BibTeX
@inproceedings{pedersen2006automatic,
  author = {Ted Pedersen and Anagha Kulkarni},
  title = {{Automatic Cluster Stopping with Criterion Functions and the Gap Statistic}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2006},
}
Figure