Timezone: »

 
Poster
Approximation Bounds for Hierarchical Clustering: Average Linkage, Bisecting K-means, and Local Search
Benjamin Moseley · Joshua Wang

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #30
in Posters Tue »

Hierarchical clustering is a data analysis method that has been used for decades. Despite its widespread use, the method has an underdeveloped analytical foundation. Having a well understood foundation would both support the currently used methods and help guide future improvements. The goal of this paper is to give an analytic framework to better understand observations seen in practice. This paper considers the dual of a problem framework for hierarchical clustering introduced by Dasgupta. The main result is that one of the most popular algorithms used in practice, average linkage agglomerative clustering, has a small constant approximation ratio for this objective. Furthermore, this paper establishes that using bisecting k-means divisive clustering has a very poor lower bound on its approximation ratio for the same objective. However, we show that there are divisive algorithms that perform well with respect to this objective by giving two constant approximation algorithms. This paper is some of the first work to establish guarantees on widely used hierarchical algorithms for a natural objective function. This objective and analysis give insight into what these popular algorithms are optimizing and when they will perform well.

Keywords: Clustering · Theory
[ Paper]  [ Poster] 

Author Information

Benjamin Moseley (Carnegie Mellon University)
Joshua Wang (Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors