External Clustering Validation by the Homogeneity-Parsimony Trade-off

Abstract:Scalar metrics are often used to evaluate clusterings against known classes, but they can obscure a fundamental trade-off: clusterings should be informative about class labels while avoiding unnecessary fragmentation. Here we describe normalized scores of cluster homogeneity and parsimony that quantify this trade-off. These scores build on the information bottleneck principle, modified to not reward lossy compression. We show by example and mathematical proof that our definitions of these scores have the intuitive property of varying monotonically under cluster refinement in contrast to related proposals. Extending the information-theoretic framework beyond Shannon entropies, we furthermore derive set-matching and pair-based counterparts of the homogeneity and parsimony scores. These unify commonly used evaluation criteria and show that, in the pair-based setting, the homogeneity-parsimony trade-off recovers the receiver operating characteristic of binary classifiers. We demonstrate the framework's utility for feature selection and algorithm comparison, illustrating how considering scores jointly can clarify clustering operating points and identify Pareto-optimal solutions.

Machine Learning (cs.LG); Information Theory (cs.IT); Methodology (stat.ME)

arXiv:2607.20799 [cs.LG]

(or arXiv:2607.20799v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2607.20799 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.