Hierarchical Clustering for Euclidean Data
arXiv:1812.10582
Abstract
Recent works on Hierarchical Clustering (HC), a well-studied problem in exploratory data analysis, have focused on optimizing various objective functions for this problem under arbitrary similarity measures. In this paper we take the first step and give novel scalable algorithms for this problem tailored to Euclidean data in R^d and under vector-based similarity measures, a prevalent model in several typical machine learning applications. We focus primarily on the popular Gaussian kernel and other related measures, presenting our results through the lens of the objective introduced recently by Moseley and Wang [2017]. We show that the approximation factor in Moseley and Wang [2017] can be improved for Euclidean data. We further demonstrate both theoretically and experimentally that our algorithms scale to very high dimension d, while outperforming average-linkage and showing competitive results against other less scalable approaches.
Cited by in corpus (6)
- From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering
- Hierarchical Clustering: a 0.585 Revenue Approximation
- Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT
- Unsupervised Embedding of Hierarchical Structure in Euclidean Space
- An Objective for Hierarchical Clustering in Euclidean Space and its Connection to Bisecting K-means
- Hierarchical Clustering via Sketches and Hierarchical Correlation Clustering