The impossibility theorem for clustering Advances in Neural Information Processing Systems Kleinberg J

Introduction
The paper discusses about how formalizing clustering can be difficult in most situations. In most situation when there are a heterogeneous collection of objects the need for clustering arises. When processing the heterogeneous set of objects it is obvious that the user would tend to fall back to the technique of clustering. Clustering mostly falls under a persuasive destination. Even though the goal of clustering is clear and persuasive goal it has become very hard to construct a unified framework when we are looking for cognition at a technical level. The numerous approaches towards clustering also hasn’t helped this cause. The paper proves that with the help of a certain impossibility theorem as a medium. A set of three simple properties have been taken into consideration and we show that there is no clustering function satisfying all three of the properties. The observation has been that some relaxation in the operation of these properties exposed some trade-offs in well-known clustering techniques.

Analysis of clustering
The main technique the author uses is the analysis of clustering is exploring the properties and also the impossibility theorem to identify the drawbacks and trade-offs in well-known clustering techniques. The limitations and sensitivities of clustering are being identified by using the impossibility theorem. At the level of concrete methods and algorithm one identifies anomalies within different clustering techniques. The anomalies are mainly due to clustering techniques not satisfying similar properties. In a real life situation if given a dataset, there is no clear concrete solution as to which clustering method to use. This is because that the different algorithms can give alarmingly different results. Axiomatic framework for clustering The paper followed an axiomatic approach towards clustering by using pairwise distance methods between the points. Then the clustering function where made to be evaluated by checking their acceptance to certain properties. The first result from this is branded as the basic impossibility theorem.
1. Scale-invariance
2. Richness requirement and
3. A consistency condition
These were the 3 properties that were considered. The test showed that it was literally not possible to construct a clustering function that satisfied all three of the above mentioned properties. Only when some relaxations were made on these properties the leading versions of clustering techniques satisfied the properties. This indicated that there were always some inherent trade-offs between the clustering techniques. The paper talks about some of the other clustering techniques that were considered by other researchers. The results in general strike chord with the observations that were made by the Jon Kleinberg. To prove his findings , the author used the impossibility theorem and tested them against the various clustering techniques while keeping in mind the collection of properties that can solved by all clustering functions. Set theory was used to prove the claim that no clustering function can satisfy all the rules.

Observations
Some of the observations/ inferences that the author makes from the paper are listed below
• From the impossibility theorem the author took into consideration when n > =2. He found that the number of clustering functions that satisfied the properties of Consistency, Scale Invariance and richness was zero. The author used K-cluster stopping condition, distance –t stopping condition and scale ἀ stopping condition as the stopping conditions. When considering these stop conditions the author observed a qualitative trade off of the properties in the theorem that was mentioned above. He finally concluded that by using this theorem we can use appropriate choice of one of these conditions to satisfy atleast two of the three properties in the theorem
• In another variation of the single linkage theorem the author uses single linkage with the three stopping conditions.
a) K cluster stopping condition – If we consider any k , K >=1 and n > = k , the single linkage with K-cluster stopping conditions were observed to satisfy the condition of scale invariance and consistency
b) Scale ἀ stopping condition – When considering a scale ἀ stopping condition, for any ἀ<1 and n >=3 , single linkage with this stopping condition satisfies the richness and scale invariance.
c) Distance-r stopping condition – Single linkage with this stopping condition satisfies the property of richness and consistency for any r > 0 and n >=2
• The author considers the axiomatic approaches of clustering. He highlights clustering techniques like hierarchical clustering and other techniques carried out by researchers like Sibson, Hofmann and Buhmann. From the results of those authors he tries to prove that his claim about different clustering techniques not satisfying all properties at the same time.
• Antichain of partition – The author proves the strengthening of the impossibility result with antichains of partitions. For a clustering function f the Range (f) is antichain when it satisfies the properties of Self variance and Consistency. The author proves this a partition and uses the distant function d to prove that they satisfy self-variance and Consistency.
• The author also takes centroid based clustering into account and analyzes it for the satisfaction of the properties of self-variance, consistency and richness.
• On final part of the analysis the author simply relaxes the properties and he comes out with the clustering function that can satisfy them. Thus he effectively infers that no clustering algorithm can as such satisfy all the properties. He brings out his inference that when the properties are relaxed the clustering functions can effectively satisfy them.

Quality of the paper
The paper effectively proved its objective by considering a series of systematic observations and analysis. The quality of the information stated was clear and concise. The author’s flow of presenting information kept the reader engaged.

Critique analysis The overall quality of the paper. When considering clustering techniques it would have been even more apt for the author to use graphical methods to better enunciate and prove his claims. Real time data examples would have effectively proved the author’s claim.

Strengths
• Proving the paper’s claim based on instances when clustering functions can satisfy two or three properties was effective.
• Considering previous work by other researches and selecting appropriate instance which match the claim was brilliant.
• There were no breakdowns in the author’s analysis. His method of imposing continuous analysis on set theory proved the effectiveness of his claim

Weakness
• Though the logic of considering fewer clustering techniques sounded reasonable , there were no proofs as to why only these three properties were considered for evaluation
• There are no datasets that actually help us to visualize and analyze the claims of this paper.
• There were not enough numbers to prove that a certain clustering algorithm failed a property.
• The paper doesnot research as to why the clustering algorithms satisfy the rules when the properties are relaxed. Extensive further analysis might be needed to prove this claim.

References
[1] M. Anderberg, Cluster Analysis for Applications, Academic Press, 1973.
[2] K. Arrow, Social Choice and Individual Values, Wiley, New York, 1951.
[3] M. Bern, D. Eppstein, “Approximation algorithms for geometric prolems,"
in Approximation Algorithms for NP-Hard Problems, (D. Hochbaum, Ed.), PWS Publishing, 1996.