Clustering Redemption-Beyond the Impossibility of Kleinberg's Axioms
Kleinberg [20] stated three axioms that any clustering procedure should satisfy and showed there is no clustering procedure that simultaneously satisfies all three. One of these, called the consistency axiom, requires that when the data is modified in a helpful way, i.e. if points in the same cluster are made more similar and those in different ones made less similar, the algorithm should output the same clustering. To circumvent this impossibility result, research has focused on considering clustering procedures that have a clustering quality measure (or a cost) and showing that a modification of Kleinberg's axioms that takes cost into account lead to feasible clustering procedures. In this work, we take a different approach, based on the observation that the consistency axiom fails to be satisfied when the "correct" number of clusters changes. We modify this axiom by making use of cost functions to determine the correct number of clusters, and require that consistency holds only if the number of clusters remains unchanged. We show that single linkage satisfies the modified axioms, and if the input is well-clusterable, some popular procedures such as k-means also satisfy the axioms, taking a step towards explaining the success of these objective functions for guiding the design of algorithms.
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. The authors define the optimal number of clusters using the commonly used elbow heuristic. The remainder of the paper analyzes prevalent clustering algorithms and objectives like single linkage and k-center variants and shows under what conditions they do or do not satisfy Kleinberg’s first two axioms and refined consistency.  The work has several strengths. The work positively contributes to the line of work on the impossibility of clustering, which helps to explain why clustering algorithms are effective in practice even when they are shown to be difficult to optimize--or impossible to optimize--in practice. The main new axiomatic ideas are simple, intuitive and crisp.  For the most part, the writing makes the high-level concepts easy to understand. The theoretical results contribute to our understanding of common clustering objectives and are an important research thread to pursue. I think that researchers interested in a theoretical understanding of clustering will be interested in this work.  The main issues with this paper seem to be easily corrected. In the proof of theorem 4.1 for the case of k-center, the authors claim that the optimal cost for k=1 cluster is 2\gamma - 4\epsilon, which they claim is achieved by opening a center at u_3, but I think this is incorrect; to me it seems that opening a center at u_3 incurs a cost of 2\gamma - 3\epsilon + 1. A better cost is achieved by opening a center at u_2 which incurs a cost of of 2\gamma - 4\epsilon (like what is claimed).  Also given that in the example gamma == 1.5 and epsilon == 0.1, the final line in the proof, which claims that \gamma + epsilon <= 1.5 is incorrect.  Perhaps what is meant is \gamma - \epsilon <= 1.5? Or perhaps that inequality should be eliminated?  The writing of the proof of theorem 4.2 should be simplified.  One thing that might help is a table showing what the various clusterings are, i.e., C1 = …, C1’ = …, C1’’ = …., C2 = …, etc. and their corresponding costs under the original and perturbed instances.  Again, I think there is an issue in this proof: on line 341 there is a claim that OPT^o_2 < OPT^p(C2), which I think is incorrect based on the values of x and y given. However, this incorrect claim doesn’t invalidate the proof.  Like in section 4, I think that the work would be strengthened by visual aids for a handful of the proofs in the supplement.  There are a handful of grammatical errors and notational sloppiness in this paper which make understanding the technical arguments much more cumbersome.  For example: in the first paragraph of 3.1 the optimal k is defined differently than the optimal k defined before axiom 2.4; on line 237 the authors write k \in {1, …, n-1} but then say that k cannot be 1; I think that k* and k^\star refer to the same thing--be consistent; after Theorem 3.4, the link to Axiom 2.3 should actually link to Axiom 2.4 (line 259); on line 274, it seems like \Gamma refers to a partition of the instances rather than a cost function--as it did in the beginning of the work; the supplement refers to Theorem 3.5 but I think this should be Lemma 3.5. There are other examples as well.  There are some grammatical errors as well; for example, in the paragraph starting on line 138.  Be sure to correct all of these mistakes.   The introduction makes it seem like the theorems presented will be in terms of stable clusterings. Clearly connecting stability to \alpha-center proximity will improve the presentation. There is no conclusion. While I think it would improve the paper to include a conclusion--even if very short--I don’t find it absolutely necessary.  As mentioned above, all of these issues can be corrected via a more diligent revision.