@article{Wang_Moseley_2020, title={An Objective for Hierarchical Clustering in Euclidean Space and Its Connection to Bisecting K-means}, volume={34}, url={https://ojs.aaai.org/index.php/AAAI/article/view/6099}, DOI={10.1609/aaai.v34i04.6099}, abstractNote={<p>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 <em>every tree</em> 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.</p><p>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.</p><p>The paper builds a theoretical connection between this objective and the bisecting <em>k</em>-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 <em>k</em>-means algorithm optimizes a natural global objective over the entire tree.</p>}, number={04}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Wang, Yuyan and Moseley, Benjamin}, year={2020}, month={Apr.}, pages={6307-6314} }