Objective-Based Hierarchical Clustering of Deep Embedding Vectors

Authors

  • Stanislav Naumov ITMO University
  • Grigory Yaroslavtsev Indiana University, Bloomington
  • Dmitrii Avdiukhin Indiana University, Bloomington

Keywords:

Clustering

Abstract

We initiate a comprehensive experimental study of objective-based hierarchical clustering methods on massive datasets consisting of deep embedding vectors from computer vision and NLP applications. This includes a large variety of image embedding (ImageNet, ImageNetV2, NaBirds), word embedding (Twitter, Wikipedia), and sentence embedding (SST-2) vectors from several popular recent models (e.g. ResNet, ResNext, Inception V3, SBERT). Our study includes datasets with up to 4.5 million data points with embedding dimensions up to 2048. In order to address the challenge of scaling up hierarchical clustering to such large datasets we propose a new practical hierarchical clustering algorithm B++&C. It gives a 5%/20% improvement on average for the popular Moseley-Wang (MW)/ Cohen-Addad et al. (CKMM) objectives (normalized) compared to a wide range of classic methods and recent heuristics. We also introduce a theoretical algorithm B2SAT&C which achieves a 0.74-approximation for the CKMM objective in polynomial time. This is the first substantial improvement over the trivial 2/3-approximation achieved by a random binary tree. Prior to this work, the best poly-time approximation of ≈2/3 + 0.0004 was due to Charikar et al. (SODA’19)

Downloads

Published

2021-05-18

How to Cite

Naumov, S., Yaroslavtsev, G., & Avdiukhin, D. (2021). Objective-Based Hierarchical Clustering of Deep Embedding Vectors. Proceedings of the AAAI Conference on Artificial Intelligence, 35(10), 9055-9063. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17094

Issue

Section

AAAI Technical Track on Machine Learning III