Reviews: Clustering Redemption–Beyond the Impossibility of Kleinberg's Axioms

This paper extends Kleinberg's work on the impossibility of clustering. That is, Kleinberg introduced 3 axioms that any clustering procedure should satisfy and then showed that it is impossible to satisfy all three simultaneously. This work suggests a refinement of Kleinberg's 3rd axiom having to do with consistency. In the original axiom, if the clustering distance function is perturbed such that all within-cluster distances do not increase and all across cluster distances do not decrease, then the optimal clustering should be the same with respect to both the perturbed and unperturbed distance functions. The refined consistency axiom proposed in this work says that under the perturbed distance function, the optimal clustering may be different so long as the number of clusters in the optimal partition is different as well.