APPROXIMATION BOUNDS FOR CLUSTERING: AVERAGE LINKAGE, BISECTING K-MEANS

Abstract

Hierarchical clustering is a widely used method to analyze data. See Murtagh and Contreras (2012); 
Krishnamurthy et al. (2012); Heller and Ghahramani (2005) for an overview and pointers to 
relevant work. In a typical hierarchical clustering problem, one is given a set of n data points and 
a notion of similarity between the points.  The output is a hierarchy of clusters on the input. 
Specifically, a dendrogram (tree) is constructed where the leaves correspond to the n input data 
points and the root corresponds to a cluster containing all data points. Each internal node of the 
tree corresponds to a cluster of the data points in its subtree. The clusters (internal nodes) become 
more refined as we move down the tree. The goal is to construct the tree so that these deeper 
clusters contain points that are relatively more similar.