Simple kNN example

Question

Can someone explain, in very simple way, how can kNN algorithms predict classes of set of points? Is there any resource for beginners to understand algorithms with graph?

Answer 1

Using the Anderson's Iris data set available in the iris {datasets} in R, I worked on a makeshift function (simply to make sure I got the idea) to predict three species of Iris based on different botanical measurements in the dataset:

We want to predict the actual species Iris (Iris setosa, Iris virginica and Iris versicolor) based on the measurement of the sepals and petals. Since the species are categorical levels, this is a ML classification problem.

It would be very easy to visualize if there were only two dimensions (or variables) being measured as the predictors. For instance, if we were just measuring sepal length and sepal width:

Each point could be considered as a vector from the origin, and the distance to other adjacent points be calculated simply as $\small \sqrt{\displaystyle\sum_{\text{coord}\,=\,x}^{\text{coord}\,=\,y}(\text{coord}_i - \text{coord}_j)^2}$, corresponding to the length of the vector spanning from one point to its adjacent entry in the dataset. You could simply say that you are measuring the Euclidean distance between any given point and $k$ adjacent points, and then tabulating the number of setosa, versicolor and virginica, winner takes all - whichever species with the highest number of counts among the closest $k$ points is used as the predicted label. In case of a tie, a coin can be flipped to select the winner.

The reason for the vector notion is that in this case there are more than two variables used to predict the species. It looks like this:

So we have to just imagine every point as a vector in a 4-dimensional hyperspace - Dali could paint this data cloud levitating on a hypercube over the Mediterranean; R, not so sure... Fortunately, linear algebra doesn't require much creative inspiration: each variable measured for each data point forms a vector, and the distance to other vectors is simply calculated as the length of the vector extending from one point to its $k$ neighboring entries.

I have put together a function in R to do just that for this dataset not so much to rediscover the wheel, but to make sure I had to work through all the hurdles of putting into practice this intuitive system. It is data-specific, but easy to adapt to other datasets. The code is here. The results on the testing set with $k=13$ are not too far off the built-in function in R, knn {class}, and look quite on target on this tabulation of the results:

> print(table(predicted = data_test[,6], actual = data_test[,5]))
            actual
predicted    setosa versicolor virginica
  setosa         22          0         0
  versicolor      0         11         0
  virginica       0          4        23
> mean(data_test[,6] == data_test[,5]) # Accuracy rate
[1] 0.9333333

---

As a related counterpoint in unsupervised ML, if we didn't have the labels identifying the species, we could have run instead a k-means clustering, for which, and as a conceptual exercise, I include the code here. Serving as a mere illustrative extension of the original answer, I didn't split the data into training and testing. The plots were virtually identical to the ones above, albeit without the pertinent species labels.

If instead we resort to the available R packages, and plotting the clusters after performing PCA dimensionality reduction, we get the following separation just using the first two components (clusplot with labeled examples):

The color shading parallels the overlap between virginica and versicolor on the original scatterplot matrix above, with setosa more clearly separable.

Answer 2

I assume you've read the Wikipedia kNN Entry? (It has a diagram illustrating how it works in 2 dimensions.)

As a simple example, assume you're looking to classify homes by "Well-maintained" or "Not well-maintained". You have a map and you are able to stick pins on this map: green for "Well-maintained" and red for "Not well-maintained". You go online and find some recent photos of a couple dozen houses in your section of the town and as you look at each one, you place either a red or green pin in your map at the location of the house.

Then your realtor friend calls you and says, "Hey, I have a call about a house at such-and-such address and I hear you are researching how well-maintained houses are. Is this one likely to be well-maintained?" So you find that address on your map and look at the 10 nearest pins and 8 out of 10 are green. So you tell your friend, "It looks like there's a fairly high chance that it's well-maintained."

In this example, $k=10$, and the distance was the literal distance (based on lat/lon) of houses. We're making the assumption that blocks, streets, neighborhoods tend to be well-maintained or not, which is somewhat plausible but of course there are always exceptions.

So, to generalize a bit, you first gather a set of points that you know the classification of already. These will be your exemplars. When you have a new point that comes in and you want to classify it, you look at the $k$ exemplars that are closest to the new point and the most common classification is what you decide your new point must be. Obviously, if all $k$ nearest exemplars are from one class, you're pretty certain of your new classification. And if the $k$ nearest exemplars fall into $k$ different classes you really can't make a decision at all. Between those two extremes, you have varying levels of confidence.

With $k=1$, the new point is considered to be of the same class as its nearest exemplar, no voting necessary. But you're more likely to make mistakes because of the exceptions I mentioned. Larger $k$ allows more votes and in general that leads to more stable outcomes, but you also end up with more distant exemplars voting and you homogenize out local variations.

In real problems, you will not have lat/lon of houses, but a lot of facts/measurements for each data point. For a person, maybe height, weight, age, smoker/non-smoker, etc. The distance between people is more abstract, but you can come up with such a distance and do the same thing -- in as many dimensions as facts/measurements.