“Dad, look! Is this a mussel or a whelk? It’s half buried in the sand, and I can’t tell.”
“Then let’s ask its neighbors.”
“Shells have neighbors?”
“Everything has neighbors, if you draw it the right way.”
Dad took a stick and drew two axes in the wet sand. As always, there was a tape measure in his backpack.
“Measure everything we collected today: length and width. I’ll do the drawing.”
Shells in the Sand
Half an hour later, a picture appeared in the sand, very much like the one you saw in Chapter 15. Across — the length of the shell; up — its width. Each shell is one dot. Dad marked the mussels with little circles and the rapa whelks with crosses.
And once again, the dots aren’t scattered at random. The mussels — long and narrow — gathered at the bottom right. The whelks — wider — at the top left. Two camps, each in its own corner.
The numbers we use to describe an object (here, length and width) are called features. And the name “mussel” or “whelk” is a label, or a class. The task of putting a new object into one of the classes — “mussel or whelk,” “spam or not,” “cat or dog” — is called classification.
The six shells are the same as in the program from “Under the hood.” Try k = 5: the answer changes.
Now for the new shell. Veronica measures it — and a question mark appears in the sand. What next? Dad draws a circle around it so that it takes in the three nearest dots. Two of them are mussels, one is a whelk. A vote: two against one. So it’s most likely a mussel.
That’s the whole method. It’s called k-nearest neighbors (kNN): find the k most similar familiar examples and see which class there are more of. Here k = 3.
How Many Neighbors Should You Ask?
We choose the number k ourselves, and a lot depends on it. If k = 1, a single nearest neighbor decides everything. But what if that one was a mistake: a whelk measured wrong, or put in the wrong camp? Then the answer will be wrong too.
If k is too big — say, all forty shells — the whole beach gets a vote, and whichever class simply has more members wins. So k is chosen somewhere in the middle. And when there are two classes, people pick an odd k, so the votes can’t split evenly.
“Dad, does this method take long to learn?”
“It doesn’t learn at all. It just remembers all the shells. And it only thinks when you bring a new one.”
That’s true. In Chapter 15, we “squeezed” all the dots into a single line and then used only the line. kNN doesn’t squeeze anything: it keeps all the examples in memory and compares each new one with every one of them. For forty shells, that’s nothing; for a billion photos, it’s very slow.
The method was described in 1951 by the American statisticians Evelyn Fix and Joseph Hodges — in a report for the U.S. Air Force School of Aviation Medicine. Today it’s one of the very first things almost everyone learns when they start machine learning.
“So it’s a mussel,” said Veronica, and finally pulled the shell out of the sand. It was long, narrow, and dark.
“The neighbors didn’t lie,” Dad smiled.
“This time. Because I measured them carefully.”
