5
$\begingroup$

I have read that the k-means algorithm tries to minimize the within cluster sum of squares (or variance). With some brainstorming, a question popped up. Why is it that k-means or any other clustering algorithm that has within cluster variance as its objective to minimize, chose this as the objective function to minimize? What is it about within cluster variance that helps you decide that this is what you want to focus while clustering? - And especially clustering?

Let me put the question in another way (This question can be a sub-question or another way of putting the same question). Why would you say that minimizing within cluster variance is the right way of clustering (referring to the algorithms that minimize it)? Can there be other objective functions that can be minimized (or maximized or anything) for clustering?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Minimizing within-cluster variance automatically maximizes between-cluster variance. Although this duality does not necessarily hold for other measures of similarity/dissimilarity, it motivates the generalizations. $\endgroup$
    – whuber ♦
    May 14, 2013 at 17:42
  • $\begingroup$ Have a look at the classes of clustering algorithms listed on wikipedia. There are a number of different over-arching goals. In particular linkage-based clustering aims to make sure that all samples in a cluster a close to at least $k$ other samples in the cluster. This can end up with clusters that are definitely not variance minimising. $\endgroup$
    – naught101
    Mar 12, 2014 at 2:09

2 Answers 2

Reset to default
7
$\begingroup$

Within-cluster-variance is a simple to understand measure of compactness (there are others, too).

So basically, the objective is to find the most compact partitioning of the data set into $k$ partitions.

K-Means, in the Lloyd version, actually originated from 1d PCM data as far as I know. So assuming you have a really bad telephone line, and someone is bleeping a number of tones on you, how do you assign frequencies to a scale of say 10 tones? Well, you can tell the other to just send a bulk of data, store the frequencies in a list, and then try to split it into 10 bins, such that these bins are somewhat compact and separated. Even when the frequencies are distorted by the transmission, there is a good chance they will still be separable with this approach.

This is also why k-means usually comes out best when you evaluate clusterings with any other measure of compactness. Because it's just two different measures for a similar concept.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The primary assumption in textbook k-means is that variances between clusters are equal. Because it assumes this in the derivation, the algorithm that optimizes (or expectation maximizes) the fit will set equal variance across clusters. $\endgroup$
    – EngrStudent
    Aug 6, 2014 at 19:59
5
$\begingroup$

There are several questions here at very different levels. In essence every text on cluster analysis is an answer. You have to keep reading!

Variance is at one level just one statistical standard which statistical people find convenient to think about. Roughly, minimising variance encourages -- nay, enforces -- clusters as relatively tight balls. What can be a limitation in much of statistics, the sensitivity of means and variances to squared deviations, can be a virtue in cluster analysis in so far as clusters are tight and compact.

But yes, there are many, many other ways of finding clusters, some but not all of which can be posed as minimising or maximising an objective function.

For every enthusiastic account of cluster analysis you read, you should try to impute an opposite statistical view, namely that cluster analysis is a vaguely posed problem to which there can be no well-defined answer, and that it is oversold to the desperate and the clueless as a way of finding structure which may or may not exist. (The meta-assumption that data must clump, somehow, cannot be well tested by any method whose very purpose is to identify clusters.)

There have been attempts to show that one method of cluster analysis is "the right way", but it's my impression that people never get past arguing about the first principles. If you can give a precise definition of what you desire about a clustering, someone expert can guide you on methods to achieve that.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Agreed on the last 2 paragraphs! One doubt: What can be a limitation in much of statistics, the sensitivity of means and variances to squared deviations, can be a virtue in cluster analysis in so far as clusters are tight and compact. Can you be a little more elaborate on this? What sensitivity are you talking about? $\endgroup$
    – Prateek Kulkarni
    May 15, 2013 at 11:26
  • $\begingroup$ Means and variances will change whenever any value changes. Look at any book or review paper on robust statistics if the point is not clear from introductory courses. The opposite is true of (e.g.) medians and interquartile ranges. (Various small qualifications, too small to write in the margin here.) $\endgroup$
    – Nick Cox
    May 15, 2013 at 16:08
  • $\begingroup$ re: "the attempts to show that one method of cluster analysis is 'the right way,'" I read somewhere or another that there are mathematical proofs to the effect that there can never be a "best" clustering algorithm. I can't remember the source(s) for this, but I know that they exist. If I remember right, it boils down to the fact that a cluster is a subjective definition; just as "pattern recognition" depends entirely on what we define as a "pattern," a "cluster" depends on what questions we choose to ask. Whether or not a cluster qualifies once we've chosen the definition is clear-cut though. $\endgroup$
    – SQLServerSteve
    Jun 14, 2017 at 4:35
  • $\begingroup$ I don't see that a proof is needed. If people can't agree in principle on what is best, then whether a best exists in practice is not discussable. Jardine and Sibson argued that single link clustering was the only kind to satisfy certain criteria, but few people seem convinced by the criteria. $\endgroup$
    – Nick Cox
    Jun 14, 2017 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.