Abstract: Automatic labeling of hierarchical document clusters is essential for navigating large information spaces. However, standard methods often fail to provide labels that distinguish a cluster from its parent or siblings. This paper introduces DScore, a linear ranking model that incorporates hierarchical features to select descriptive and discriminative labels. By measuring "ranking boosts"—the relative change in a term's importance between a parent and child cluster—the model identifies highly specific labels. Evaluation using the Open Directory Project (ODP) shows that DScore achieves a Mean Reciprocal Rank (MRR) of 0.51 and exhibits remarkable robustness to clustering errors, maintaining performance even with 30% document misplacement.
Introduction
When organizing large document collections into hierarchies, such as folder trees or web directories, effective labels are crucial for navigation. Most automatic labeling methods focus on isolated clusters, selecting terms based on high frequency (TF) or uniqueness (TF-IDF). While these labels may be technically accurate, they often lack discriminative power. For instance, a sub-cluster of "Artificial Intelligence" labeled as "Computer Science" is correct but fails to differentiate it from its parent or sibling clusters. An ideal label must be both descriptive of the cluster's content and discriminative relative to its hierarchical context.
Methods
The authors propose DScore, a linear model designed to rank potential labels (unigrams, bigrams, and trigrams). The core innovation lies in the use of hierarchical features that compare a cluster ($S$) to its parent ($P$).
The model integrates three types of features:
- Cluster Features: Standard metrics like Document Frequency ($DF_S$) and TF-IDF within the target cluster.
- Parent Features: Corresponding metrics calculated for the parent cluster ($P$).
- Ranking Boosts: The most significant feature, calculated as the log-difference in a term's rank between the parent and child: $log(rank(DF_P)) - log(rank(DF_S))$. This captures the intuition that a term becoming significantly more prominent in a sub-cluster (e.g., jumping from rank 50 in the parent to rank 5 in the child) is a strong indicator of its specific relevance.
Additionally, the system employs an adaptive threshold to determine the number of labels displayed based on the distribution of top DScore values.
Experimental Results
The model was evaluated using 25,143 web pages from the Open Directory Project (ODP). Predicted labels were validated against human-curated ODP category names and WordNet synonyms.
Feature Performance
The experimental results confirm that context is vital for effective labeling. Features derived from the parent cluster were found to be significantly more powerful than those derived from the cluster in isolation. Specifically, the "ranking-boost" features were the single most effective predictors of high-quality labels.
Robustness to Noise
To simulate real-world conditions where clustering algorithms are imperfect, the authors tested the model on "messy" hierarchies by intentionally swapping documents between sibling clusters. The DScore model proved highly resilient; even when 30% of documents were misplaced, the MRR only decreased from 0.51 to 0.50. This suggests that the statistical signal of correct topical terms remains dominant despite significant noise.
Discussion and Future Work
While DScore provides a robust framework for hierarchical labeling, several areas for improvement remain. The authors noted that a simple linear combination of features may not be optimal, suggesting that non-linear models like decision trees could yield better results. Furthermore, the current model does not explicitly address label redundancy (e.g., displaying both "Neural Network" and "Neural Networks"). Future research could also explore qualitative human evaluations to supplement the strict, ODP-based "gold standard" used in this study.
Conclusion
This study demonstrates that hierarchical context is essential for generating effective cluster labels. By leveraging ranking boosts between parent and child clusters, the DScore model provides a practical and noise-tolerant solution for automatically organizing and labeling large-scale document hierarchies.
Summary updated