Timezone: »

 
Poster
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
in Algorithms -- Clustering »

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.

Keywords: Clustering · Frequentist Statistics · Algorithms · Algorithms -> Ranking and Preference Learning; Theory
[ Paper]  [ Poster] 

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