Nearest neighbor

Hi! I’m sitting here in New Zealand. It’s on the globe behind me. That’s New Zealand, at the top of the world, surrounded by water. But that’s not where I’m from originally. I moved here about 20 years ago. Here on this map, of course, this is New Zealand – Google puts things with the north at the top, which is probably what you’re used to. I came here from the University of Calgary in Canada, where I was for many years. I used to be head of computer science for the University of Calgary. But, originally, I’m from Belfast, Northern Ireland, which is here in the United Kingdom. So, my accent actually is Northern Irish, not New Zealand.

This is not a New Zealand accent. We’re going to talk about another machine learning method called the nearest neighbor, or instance-based, machine learning method. When people talk about rote learning, they just talk about remember stuff without really thinking about it. It’s the simplest kind of learning. Nearest neighbor implements rote learning. It just remembers the training instances, and then, to classify a new instance, it searches the training set for one that is most like the new instance. The representation of the knowledge here is just the set of instances. It’s a kind of lazy learning. The learner does nothing until it has to do some predictions. Confusingly, it’s also called instance-based learning. Nearest neighbor learning and instance-based learning are the same thing.

Here is just a little picture of 2-dimensional instance space. The blue points and the white points are two different classes – yes and no, for example. Then we’ve got an unknown instance, the red one. We want to know which class it’s in. So, we simply find the closest instance in each of the classes and see which is closest. In this case, it’s the blue class. So, we would classify that red point as though it belonged to the blue class. If you think about this, that’s implicitly drawing a line between the two clouds of points. It’s a straight line here, the perpendicular bisector of the line that joins the two closest points. The nearest neighbor method produces a linear decision boundary.

Actually, it’s a little bit more complicated than that. It produces a piece-wise linear decision boundary with sometimes a bunch of little linear pieces of the decision boundary. Of course, the trick is what do we mean by “most like”. We need a similarity function, and conventionally, people use the regular distance function, the Euclidean distance, which is the sum of the squares of the differences between the attributes. It’s the square root of the sum of the squares, but since we’re just comparing two instances, we don’t need to take the square root. Or, you might use the Manhattan or city block distance, which is the sum of the absolute differences between the attribute values. Of course, I’ve been talking about numeric attributes here.

If attributes are nominal, we need the difference between different attribute values. Conventionally, people just say the distance is 1 if the attribute values are different and 0 if they are the same. It might be a good idea with nearest neighbor learning to normalize the attributes so that they all lie between 0 and 1, so the distance isn’t skewed by some attribute that happens to be on some gigantic scale. What about noisy instances. If we have a noisy dataset, then by accident we might find an incorrectly classified training instance as the nearest one to our test instance. You can guard against that by using the k-nearest-neighbors.

k might be 3 or 5, and you look for the 3 or the 5 nearest neighbors and choose the majority class amongst those when classifying an unknown point. That’s the k-nearest-neighbor method. In Weka, it’s called IBk (instance-based learning with parameter k), and it’s in the lazy class. Let’s open the glass dataset. Go to Classify and choose the lazy classifier IBk.

Let’s just run it. We get an accuracy of 70.6%. The model is not really printed here, because there is no model. It’s just the set of training instances. We’re using 10-fold cross-validation, of course. Let’s change the value of k, this kNN is the k value. It’s set by default to 1. (The number of neighbors to use.) We’ll change that to, say, 5 and run that. In this case, we get a slightly worse result, 67.8% with k as 5. This is not such a noisy dataset, I guess. If we change it to 20 and run it again. We get 65% accuracy, slightly worse again.

If we had a noisy dataset, we might find that the accuracy figures improved as k got little bit larger. Then, it would always start to decrease again. If we set k to be an extreme value, close to the size of the whole dataset, then we’re taking the distance of the test instance to all of the points in the dataset and averaging those, which will probably give us something close to the baseline accuracy. Here, if I set k to be a ridiculous value like 100. I’m going to take the 100 nearest instances and average their classes. We get an accuracy of 35%, which, I think is pretty close to the baseline accuracy for this dataset.

Let me just find that out with ZeroR, the baseline accuracy is indeed 35%. Nearest neighbor is a really good method. It’s often very accurate. It can be slow. A simple implementation would involve scanning the entire training dataset to make each prediction, because we’ve got to calculate the distance of the unknown test instance from all of the training instances to see which is closest. There are more sophisticated data structures that can make this faster, so you don’t need to scan the whole dataset every time. It assumes all attributes are equally important. If that wasn’t the case, you might want to look at schemes for selecting or weighting attributes depending on their importance.

If we’ve got noisy instances, than we can use a majority vote over the k nearest neighbors, or we might weight instances according to their prediction accuracy. Or, we might try to identify reliable prototypes, one for each of the classes. This is a very old method. Statisticians have used k-nearest-neighbor since the 1950’s. There’s an interesting theoretical result. If the number (n) of training instances approaches infinity, and k also gets larger in such a way that k/n approaches 0, but k also approaches infinity, the error of the k-nearest-neighbor method approaches the theoretical minimum error for that dataset. There is a theoretical guarantee that with a huge dataset and large values of k, you’re going to get good results from nearest neighbor learning.