Foundations of Comparison-Based Hierarchical Clustering
This addresses a practical problem in crowdsourcing where direct similarity measures are unavailable, offering incremental improvements to existing methods.
The paper tackles hierarchical clustering using only comparisons of object similarities, common in crowdsourcing, and develops variants of average linkage without relying on ordinal embedding, providing statistical guarantees and empirical results on datasets.
We address the classical problem of hierarchical clustering, but in a framework where one does not have access to a representation of the objects or their pairwise similarities. Instead, we assume that only a set of comparisons between objects is available, that is, statements of the form "objects $i$ and $j$ are more similar than objects $k$ and $l$." Such a scenario is commonly encountered in crowdsourcing applications. The focus of this work is to develop comparison-based hierarchical clustering algorithms that do not rely on the principles of ordinal embedding. We show that single and complete linkage are inherently comparison-based and we develop variants of average linkage. We provide statistical guarantees for the different methods under a planted hierarchical partition model. We also empirically demonstrate the performance of the proposed approaches on several datasets.