Online Hierarchical Clustering Approximations
  Hierarchical clustering is a widely used approach for clustering datasets at
multiple levels of granularity. Despite its popularity, existing algorithms
such as hierarchical agglomerative clustering (HAC) are limited to the offline
setting, and thus require the entire dataset to be available. This prohibits
their use on large datasets commonly encountered in modern learning
applications. In this paper, we consider hierarchical clustering in the online
setting, where points arrive one at a time. We propose two algorithms that seek
to optimize the Moseley and Wang (MW) revenue function, a variant of the
Dasgupta cost. These algorithms offer different tradeoffs between efficiency
and MW revenue performance. The first algorithm, OTD, is a highly efficient
Online Top Down algorithm which provably achieves a 1/3-approximation to the MW
revenue under a data separation assumption. The second algorithm, OHAC, is an
online counterpart to offline HAC, which is known to yield a 1/3-approximation
to the MW revenue, and produce good quality clusters in practice. We show that
OHAC approximates offline HAC by leveraging a novel split-merge procedure. We
empirically show that OTD and OHAC offer significant efficiency and cluster
quality gains respectively over baselines.
