This is the first post in a brief series on algorithms — that is, methods of doing something, with or without a computer — that I think are neat. Each will have its own self-contained live demo.
This sample shows a method called k-Means. It used to be known as Lloyd’s method. It’s so simple that I’m surprised it’s not used more often.
The basic idea is to find a set of “best middles” — or “means” — for any given set of information. In the sample, we have a bunch of random, possibly-lumpy x’s on the canvas. The method tries to find some smaller number of categories (the “means,” marked by circles) that could best-represent that info.
The “k” is the number of categories we want to create.
The k-Means method doesn’t directly solve for “best.” It just keeps trying and adjusting, starting from completely random guesses as to where to put the means:
- Look at every point, and mark it “owned” by the closest “mean.”
- Move each mean to the middle of its “owned” points.
- Just keep doing those two steps, until either nothing changes each time or you run out of patience. If a mean has no points, just discard that mean. You didn’t need it.
In this sample, we let the means move around until they’re stable, then randomly take one away.
Pause/start the animation by clicking on the canvas.
You can decide what these results look like: Popping soap bubbles? Growing algae mats in time-lapse? Voting districts? That dream about insects eating your car? I suggest turning on some Cinematic Orchestra for your headphones and stare at this page for a long while to decide.
In the next example, we’ll try using k-Means in different ways. Some obvious questions might be:
- Are there better or different ways to decide which point belongs to which mean? What do we mean by “closeness”?
- What does this have to do with photography?