Kevin Bjorke
Kevin Bjorke
1 min read

Categories

Tags

Live demo: Click to Pause/Resume

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.

The Idea

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.

The Example

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 see the source here on GitHub. The entire example is contained in a single Javascript module that’s imaginatively named “sample1.”

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: