The Price of Explainability for Clustering

Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson +1

Given a set of points in $d$-dimensional space, an explainable clustering is one where the clusters are specified by a tree of axis-aligned threshold cuts. Dasgupta et al. (ICML 20…