K-Nearest Neighbors (KNN)

How can you tell the species of a wildflower you've never seen before? If its petal length and width are similar to flowers you've already observed, is it likely to be the same species? And if different species are mixed together nearby, what should you base your judgment on?

K-nearest neighbors (KNN) is a method that finds the data points closest to a new observation and predicts its species from the information of those neighbors. Rather than working out a complicated classification formula in advance, it calculates distances to the stored training data.

Discriminant analysis assumes a distribution for each group and derives a decision boundary, and SVM optimizes the margin that separates the groups. KNN, by contrast, classifies by looking directly at which species are gathered around the new flower and how many of each. The results can change with the number of neighbors K and how distance is defined.

KNN can be used for biological classification, grouping similar customers, pattern recognition, recommendations, simple baseline prediction models and more. In this article we'll use wildflower measurements to look at how KNN works, how to set K, distance and standardization, how to read classification results, how it differs from other models and what to watch out for in the analysis.

The training data record the petal length and width and sepal length and width of flowers whose species is already known. When a new flower comes in, KNN looks for training examples with similar values on these four measurements. In classification, the basic approach is to compare the species of the K closest flowers and predict the species that appears most often.

KNN doesn't necessarily require a linear boundary or an assumption of normality. But the distance measure that decides what counts as close, and the units of the variables, directly affect the results.

Even if flower species can't be cleanly separated by petal length alone, looking at several measurements together can bring flowers of the same species close to each other. KNN uses this kind of local structure for classification.

It is easy to understand as a first comparison model and can classify several species at once, but when the training data are very large, searching for neighbors for every new flower can get computationally expensive. There's also the problem that distance becomes less meaningful as the number of dimensions grows.

① Represent the flower measurements as coordinates

The lengths and widths of the petals and sepals are the input variables. To make it easier to follow, the figure shows only the two petal variables; an actual classification can use all four variables together.

② Calculate the distance between the new flower and the training data

With Euclidean distance, you square the differences on each variable, add them up and take the square root. You can use other distance measures as well, and the input variables should be on similar scales.

③ Pick the K closest flowers

With K=5, you find five neighbors and check each neighbor's species. If you set up distance-based weights, closer neighbors can also get more votes.

④ Predict the species with the most votes

For example, if the five flowers are 1 of species A, 3 of B and 1 of C, the new flower is classified as B. You also need to set a rule for handling ties.

Suppose a researcher collected 180 hypothetical wildflowers. There are 60 flowers of each of the three species A, B and C, and the petal length and width and sepal length and width of each flower were recorded.

Of the 180 flowers, 135 are used as training data and 45 as the final test data. Assume a stratified split so that each species contributes 15 flowers to the test data. The classification results below are hypothetical figures constructed to explain the concepts.

① Define the target and the measurement variables

Set species as the correct label and the four petal and sepal measurements as input variables.

② Split into training and test data

Set aside the 45 test flowers for the final check, and choose settings by cross-validation within the 135 training flowers.

③ Decide on standardization, distance and weighting

You can compare standard Euclidean distance, Manhattan distance, equal weights and distance weights.

④ Choose K by cross-validation

Evaluate several values of K with the same cross-validation procedure, and look at both validation performance and stability.

⑤ Check performance on the final test data

After K is chosen, use the held-out test data once to calculate the confusion matrix and per-species precision and recall.

A small K isn't always more accurate, and an odd K isn't always right. With three species, ties can occur even with an odd K. In this example, assume K=5 was chosen by cross-validation within the training data.

These are the results of classifying the 45 hypothetical test flowers with K=5. Rows are actual species and columns are predicted species.

Overall accuracy is 86.7% (39/45). Recall is 93.3% (14/15) for species A, 80.0% (12/15) for B and 86.7% (13/15) for C. Some B and C flowers are confused with each other, a difference that accuracy alone can't reveal.

For example, if petal length is a few cm and some additional sensor value is measured in the hundreds, the sensor value can largely dictate similarity under plain Euclidean distance. Standardization puts the variables on the same scale, but it can also give meaningless variables the same weight, so variable selection matters too.

What matters for the classification is not the absolute size of the distances themselves but which observations are chosen as nearest neighbors. If you change the variables or the distance method, choose K again by cross-validation.

Did you standardize using the test data too?

If you standardize with statistics from the full data and then split, information from the test data leaks into the training process.

Are there too many dimensions?

As the number of variables grows, the distances between most observations can become similar. Consider selecting meaningful variables or reducing dimensions.

Did you try only one K?

K=1 or K=5 isn't always appropriate. Compare a range of candidates in cross-validation.

Are the same specimens in both training and test data?

If repeated measurements of the same flower appear on both sides, classification performance can be inflated. Consider splitting by specimen or by collection site.

Will it work for flowers from other regions?

Flower size can vary with the time and place of collection. And even for a new species outside the range of the training data, KNN will still pick one of the existing species.

Besides classification, there is also KNN regression, which averages the outcomes of nearby observations. What we cover here, though, is KNN classification, which chooses a species.

Actual results should include the sample size, the number in each species, the measurement variables used, the standardization method, the distance measure, the number of neighbors and weighting, the cross-validation scheme and the per-species errors on the independent test data. Where possible, also present the uncertainty in performance.

Stating that the transformation and the choice of K were done within cross-validation, and that the final test data were not reused for model selection, makes the results easier to reproduce and evaluate.

When choosing KNN, it's good to check not only whether it can classify, but also whether the data are representative enough, whether distances to new observations are meaningful for the real problem and whether prediction is fast enough.

When classifying wildflower species, KNN finds flowers with similar petal and sepal measurements and judges the new flower's species from them. You don't need to assume a complicated formula first, but which variables you use and how you calculate distance change who the nearest neighbors are. If K is too small, the result becomes sensitive to noise in individual observations; if it is too large, small differences between species can be missed.

So when using KNN, compute preprocessing parameters from the training data only, choose K and the distance method by cross-validation, and then check classification errors on separate test data. Looking at per-species recall and the confusion matrix in addition to overall accuracy also shows which flowers are hard to tell apart. Checking whether similarity in the data really reflects similarity between species is also an essential part of interpreting the results.