Abstract
In Natural Language Processing (NLP), unsupervised name discrimination is the task of grouping mentions of an ambiguous name into clusters that represent distinct real-world entities. A primary challenge in this field is the "cluster stopping problem"—determining the optimal number of clusters ($k$) without prior knowledge. This paper evaluates three automated measures for identifying $k$ based on the "knee" of a clustering criterion function. Experimental results on artificial name conflations demonstrate that a simple ratio-based measure ($PK2$) is highly effective, correctly identifying the number of entities in the majority of cases.
Introduction
When a search engine or information retrieval system encounters a common name like "John Smith," it must navigate the inherent ambiguity of human nomenclature. Without manual intervention, how can a system determine if a corpus contains two, five, or twenty different individuals sharing that name? This problem, known as unsupervised name discrimination, is critical for building accurate knowledge graphs and improving search relevance.
While clustering techniques based on contextual similarity have long been used to group related documents, they typically require a human-in-the-loop to specify the number of clusters ($k$) in advance. In 2006, Anagha Kulkarni and Ted Pedersen addressed this limitation by proposing and evaluating automated "cluster stopping" measures designed to let the data reveal its own underlying structure.
Methodology
Contextual Similarity and Clustering
The authors' approach is rooted in the principle of contextual similarity: mentions of the same individual are likely to appear near similar words. For example, mentions of a historical "John Smith" might cluster around terms like "colony" or "Jamestown," while a contemporary musician of the same name would be associated with "guitar" or "album."
To evaluate clustering quality, the authors utilize a hybrid criterion function, $H2$. This function seeks to maximize two primary metrics:
- Internal Similarity ($I2$): Ensuring that members within a single cluster are as similar as possible.
- External Similarity ($E1$): Ensuring that different clusters are as distinct as possible.
Proposed Stopping Measures
The core of the research involves identifying the "knee" of the $H2$ curve—the point where increasing the number of clusters yields diminishing returns in quality. The authors propose three measures to locate this point:
- PK1: Based on Mojena’s (1977) method, this uses a z-score-like calculation to identify outliers in clustering scores. It requires a manually defined threshold.
- PK2: A simple ratio of two successive $H2$ scores. It identifies the point where the improvement gained by adding a new cluster drops significantly.
- PK3: A more complex measure using three consecutive $H2$ scores to detect where the curve loses linearity and begins to plateau.
Experimental Setup
To validate these measures, the authors employed "artificial name conflations" (pseudo-words) using the English GigaWord Corpus. By taking unambiguous names (e.g., "Tony Blair" and "Bill Clinton") and replacing them with a single token (e.g., "Blair_Clinton"), the researchers created a dataset with a known "ground truth." They conducted 44 experiments across 22 different conflations, testing the measures against both simple unigram features and more complex bigrams weighted by log-likelihood ratios.
Results and Discussion
Performance of Measures
The experimental results identified PK2 as the most robust measure. It correctly predicted the number of clusters in 31 out of 44 experiments. Notably, PK2 is entirely unsupervised and does not require the manual thresholding necessary for PK1.
- PK2: 31/44 correct
- PK3: 24/44 correct
- PK1: 15/44 correct (even with a tuned threshold)
Graceful Failure and Labeling
An important finding was the nature of the errors. When $PK2$ failed to identify the exact number of entities, it was almost always off by only one ($+/- 1$). This "graceful failure" suggests that the measure effectively captures the general structure of the data even when the contextual signals are slightly ambiguous.
Furthermore, the system attempts to provide human-readable labels for the resulting clusters. By identifying the most frequent and unique word pairs within a cluster, the system can suggest descriptive tags, transforming a raw cluster into an identifiable entity, such as "Captain John Smith (1580-1631)."
Conclusion
Kulkarni and Pedersen demonstrate that the cluster stopping problem in name discrimination can be effectively addressed using simple ratio-based measures like $PK2$. By eliminating the need for a pre-specified $k$, this approach moves unsupervised name discrimination closer to a fully autonomous process. While the study relied on artificial conflations, it provides a framework for future research into real-world ambiguity and more mathematically rigorous stopping criteria, such as the Gap Statistic.
Summary updated