Return to Answer

center http://varianceexplained.org/figs/2015-01-16-kmeans-free-lunch/anscombe-1.png

center http://varianceexplained.org/figs/2015-01-16-kmeans-free-lunch/non_spherical-1.png

center http://varianceexplained.org/figs/2015-01-16-kmeans-free-lunch/polar-1.png

center http://varianceexplained.org/figs/2015-01-16-kmeans-free-lunch/different_sizes-1.png

Well, yes, linear regression works by minimizing the sum of squared residuals. But that by itself is not the goal of a regression: what we're trying to do is draw a line that serves as a reliable, unbiased predictor of y based on x. The Gauss-Markov theorem tells us that minimizing the SSE accomplishes that goal- but that theorem rests on some very specific assumptions. If those assumptions are broken, you can still minimize the SSE, but it might not do anything. Imagine saying "You drive a car by pushing the pedal. The pedal can be pushed no matter how much gas in the tank. Therefore, even if the tank is empty, you can still push the pedal and drive the car."

This is my favorite made-up data: Anscombe's Quartet. Created in 1973 by statistician Francis Anscombe, this delightful concoction illustrates the folly of trusting statistical methods blindly. Each of the datasets has the same linear regression slope, intercept, p-value and $R^2$- and yet at a glance we can see that only one of them, I, is appropriate for linear regression. In II it suggests the wrong shape, in III it is skewed by a single outlier- and in IV there is clearly no trend at all!

Well, yes, linear regression works by minimizing the sum of squared residuals. But that by itself is not the goal of a regression: what we're trying to do is draw a line that serves as a reliable, unbiased predictor of y based on x. The Gauss-Markov theorem tells us that minimizing the SSE accomplishes that goal- but that theorem rests on some very specific assumptions. If those assumptions are broken, you can still minimize the SSE, but it might not do anything. Imagine saying "You drive a car by pushing the pedal: driving is essentially a 'pedal-pushing process.' The pedal can be pushed no matter how much gas in the tank. Therefore, even if the tank is empty, you can still push the pedal and drive the car."

This is in fact my favorite made-up data: Anscombe's Quartet. Created in 1973 by statistician Francis Anscombe, this delightful concoction illustrates the folly of trusting statistical methods blindly. Each of the datasets has the same linear regression slope, intercept, p-value and $R^2$- and yet at a glance we can see that only one of them, I, is appropriate for linear regression. In II it suggests the wrong shape, in III it is skewed by a single outlier- and in IV there is clearly no trend at all!

We'll consider two of your assumptions, and we'll see what happens to the k-means algorithm when those assumptions are broken. We'll stick to 2-dimensional data since it's easy to visualize. (Thanks to the curse of dimensionality, adding additional dimensions is likely to make these problems more severe, not less). We'll work with the statistical programming language R: you can find the full code here.

Unevenly sized clusters

We'll consider two of your assumptions, and we'll see what happens to the k-means algorithm when those assumptions are broken. We'll stick to 2-dimensional data since it's easy to visualize. (Thanks to the curse of dimensionality, adding additional dimensions is likely to make these problems more severe, not less). We'll work with the statistical programming language R: you can find the full code here (and the post in blog form here).

Broken Assumption: Unevenly Sized Clusters