Timezone: »

Foundations of Comparison-Based Hierarchical Clustering
Debarghya Ghoshdastidar · Michaël Perrot · Ulrike von Luxburg

Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #31

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.

Author Information

Debarghya Ghoshdastidar (Technical University Munich)
Michaël Perrot (Max Planck Institute for Intelligent Systems)
Ulrike von Luxburg (University of Tübingen)

More from the Same Authors