A Hierarchical Algorithm for Extreme Clustering
Lists
Only you see this
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...