the widely-used k-means procedure returns k clusters that have arbitrary convex shapes. in high dimension, such a clustering might not be easy to understand. a more interpretable alternative is to constraint the clusters to be the leaves of a decision tree with axis-parallel splits; then each cluster is a hyperrectangle given by a small number of features.

is it always possible to find clusterings that are intepretable in this sense and yet have k-means cost that is close to the unconstrained optimum? a recent line of work has answered this in the affirmative and moreover shown that these interpretable clusterings are easy to construct.

i will give a survey of these results: algorithms, methods of analysis, and open problems.