Why is the k-means algorithm minimizing the within cluster variance? 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?
 A: 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.
A: 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. 
