A Hierarchical Algorithm for Extreme Clustering

Ari Kobren, Nicholas Monath, Akshay Krishnamurthy, Andrew McCallum

Abstract

Many modern clustering methods scale well to a large number of data points, N , but not to a large number of clusters, K . This paper introduces PERCH, a new non-greedy, incremental algorithm for hierarchical clustering that scales to both massive N and K ---a problem setting we term extreme clustering . Our algorithm efficiently routes new data points to the leaves of an incrementally-built tree. Motivated by the desire for both accuracy and speed, our approach performs tree rotations for the sake of enhancing subtree purity and encouraging balancedness. We prove that, under a natural separability assumption, our non-greedy algorithm will produce trees with perfect dendrogram purity regardless of data arrival order. Our experiments demonstrate that PERCH constructs more accurate trees than other tree-building clustering algorithms and scales well with both N and K , achieving a higher quality clustering than the strongest flat clustering competitor in nearly half the time.
BibTeX
@inproceedings{kobren2017hierarchical,
  author = {Ari Kobren and Nicholas Monath and Akshay Krishnamurthy and Andrew McCallum},
  title = {{A Hierarchical Algorithm for Extreme Clustering}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2017},
  doi = {10.1145/3097983.3098079},
}

Loading related content...

Figure