New XKCD Forums

Suppose you're trying to get a computer to recognize the difference between cats and dogs. One way to do it is with supervised machine learning, which means that you tell the computer that these photos are cats, those photos are dogs, and it'll try to pick out what it is that the cat photos have in common that the dog photos don't. Another way is with unsupervised machine learning, which means that you just give the program a bunch of photos, but don't tell it which is which, and ask it to split the photos into two groups. Maybe it'll split them into cats vs. dogs, or maybe it'll split them into big vs. small, or light fur vs. dark, or you'll get two groups where it claims to have found some pattern but you don't really know what it is.

For k-means, in particular, you have to tell the computer how many different kinds of things it should look for; that's what the k is. So if k = 2, that means that it's looking for two kinds of things, k = 3 it's looking for three kinds of things, and so on. Setting k higher than the number of groups you're actually looking for can make sense, because maybe it'll have an easier time if, for instance, it can treat big dogs and small dogs as different kinds of thing.

I wrote an implementation of k-means for a class a while back. I gave it a bunch of handwritten digits and told it to look for 10 different digits (k = 10) and 30 different digits (k = 30), and here are the best results from each (this shows what it thinks each digit looks like, on average; bottom row is the final answer, everything above that is intermediate steps):