Part of a brief series that started here.

A follow-on to the last post on k-Means — this time, we use different criteria to determine “closeness” and to adjust where we move things around.

The Idea

For this behavior, we add a “view direction” to each mean point (the pointer): it can only consider the points in front of it, each like a little fish-eyed security camera.

Overall the method is much like before, but with a bit more frenetic results:

• Look at every point, and mark it “owned” by the closest “mean” that’s aimed towards that point.
• Adjust the aim of each mean toward the middle of its “owned” points, and move it slightly “back” from the middle of their location.
• Repeat, repeat, repeat.

The Example Code

It always fascinates me that simple rules can give rise to the sorts of complex behaviors that we usually ascribe to animals or other agents with some “intelligence.” I would be remiss not to point out the impact this idea has had in the sciences ever since it was first pointed out by my friend and occasional colleague Craig Reynolds, all the way back at Siggraph of 1987 or so.

In the current case, the mean objects behave as if they are “tending” or “herding” their data. “Mine!” There’s even an illusion of cooperation and competition, like hummingbirds at a feeder or wasps buzzing around a nest. This (illusion of) organization occurs even though there’s no explicit connection between the different means “agents” — except for implicit contraints on the sizes of their own “flocks” of sample points, each mean-agent is unaware of the others.

It’s also true, unlike the previous example, that there will often be sample points that are unseen entirely by any mean-agent — indicated by faint gray.

Each of these examples in self-contained in the HTML for the post. You can review it either by selection “View Page Source” in your browser, or (easier!) viewing this page on GitHub. Everything’s contained in the object kmSample2

Suggested soundtrack: Philip Glass, Einstein on the Beach.

Next up: didn’t I say this would get around to photography?