An Objective for Hierarchical Clustering in Euclidean Space and Its Connection to Bisecting K-means

Authors

  • Yuyan Wang Carnegie Mellon University
  • Benjamin Moseley Carnegie Mellon University

DOI:

https://doi.org/10.1609/aaai.v34i04.6099

Abstract

This paper explores hierarchical clustering in the case where pairs of points have dissimilarity scores (e.g. distances) as a part of the input. The recently introduced objective for points with dissimilarity scores results in every tree being a ½ approximation if the distances form a metric. This shows the objective does not make a significant distinction between a good and poor hierarchical clustering in metric spaces.

Motivated by this, the paper develops a new global objective for hierarchical clustering in Euclidean space. The objective captures the criterion that has motivated the use of divisive clustering algorithms: that when a split happens, points in the same cluster should be more similar than points in different clusters. Moreover, this objective gives reasonable results on ground-truth inputs for hierarchical clustering.

The paper builds a theoretical connection between this objective and the bisecting k-means algorithm. This paper proves that the optimal 2-means solution results in a constant approximation for the objective. This is the first paper to show the bisecting k-means algorithm optimizes a natural global objective over the entire tree.

Downloads

Published

2020-04-03

How to Cite

Wang, Y., & Moseley, B. (2020). An Objective for Hierarchical Clustering in Euclidean Space and Its Connection to Bisecting K-means. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04), 6307-6314. https://doi.org/10.1609/aaai.v34i04.6099

Issue

Section

AAAI Technical Track: Machine Learning