# K-Nearest Neighbors (KNN): Algorithm and Examples

The k nearest neighbor algorithm classifies a new data point by looking at the k labeled points closest to it and taking a majority vote. It is one of the simplest machine learning methods to understand and implement, because training consists of storing the data and prediction consists of measuring distances. This article explains the mechanics, walks through a complete example with real numbers, and covers the mistakes that trip people up.

## Quick Answer

- KNN is a supervised learning algorithm that predicts the label of a new point from the labels of its k closest training points.
- "Closest" is measured with a distance function, most often Euclidean distance.
- For classification, the prediction is the majority class among the k neighbors. For regression, it is the average of their values.
- There is no real training phase. The model is the stored dataset, so prediction is where all the work happens.
- The choice of k changes the result. Small k follows noise, large k smooths away local structure.

## What K-Nearest Neighbors Means

In plain terms, k nearest neighbor answers a simple question: who are the k most similar known examples to this new one, and what do they say? If you want to guess the label of a point, you look at the labels of the points sitting closest to it and go with the majority.

The precise definition: given a training set of labeled points, a distance metric $d$, and a positive integer $k$, the predicted label of a query point $x$ is the most frequent label among the k training points with the smallest $d(x, x_i)$. Ties are broken by a rule you choose, such as the smallest distance or the lowest class label. The method is non-parametric, meaning it makes no assumption about the shape of the underlying distribution, and it is an instance-based or lazy learner, meaning it defers computation until prediction time.

The same neighbor idea appears elsewhere in data analysis. Mutual nearest neighbors, where two points are each other's closest match, are used to align single-cell datasets in [batch effect correction workflows](/knowledge/bioinformatics/mutual-nearest-neighbors-mnn-for-batch-effect-correction-a-step-by-step-guide-to-aligning-single-cel), which shows how flexible the concept is.

## How It Works

The algorithm has three moving parts: a distance metric, a value of k, and a voting rule.

For two points $p$ and $q$ with $n$ features, Euclidean distance is:

$$d(p, q) = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}$$

Each symbol means the following:

- $p_i$ and $q_i$ are the values of feature $i$ for the two points.
- $n$ is the number of features.
- The sum runs over every feature, so each feature contributes equally.
- The square root converts the squared distance back to the original units.

The procedure for a new point $x$:

1. Compute $d(x, x_i)$ for every training point $x_i$.
2. Sort the distances from smallest to largest.
3. Take the first k points.
4. For classification, count the labels and return the majority. For regression, average the target values.

Two details matter in practice. First, features on larger scales dominate the distance, so you normally standardize or normalize features before using KNN. Second, k should be an odd number for two-class problems so a majority always exists.

## Worked Example

The dataset is 10 points with two features (x, y) and a binary class label, split evenly between class 0 and class 1. We want to classify the new point (3, 4) with k = 3.

| Point | x | y | Class |
|---|---|---|---|
| P1 | 1 | 2 | 0 |
| P2 | 2 | 1 | 0 |
| P3 | 2 | 3 | 0 |
| P4 | 3 | 2 | 0 |
| P5 | 1 | 4 | 0 |
| P6 | 6 | 5 | 1 |
| P7 | 7 | 7 | 1 |
| P8 | 8 | 6 | 1 |
| P9 | 7 | 8 | 1 |
| P10 | 6 | 7 | 1 |

Step 1: compute the Euclidean distance from (3, 4) to every point.

| Point | Class | Calculation | Distance |
|---|---|---|---|
| P1 | 0 | sqrt((1-3)² + (2-4)²) = sqrt(8) | 2.8284 |
| P2 | 0 | sqrt((2-3)² + (1-4)²) = sqrt(10) | 3.1623 |
| P3 | 0 | sqrt((2-3)² + (3-4)²) = sqrt(2) | 1.4142 |
| P4 | 0 | sqrt((3-3)² + (2-4)²) = sqrt(4) | 2.0000 |
| P5 | 0 | sqrt((1-3)² + (4-4)²) = sqrt(4) | 2.0000 |
| P6 | 1 | sqrt((6-3)² + (5-4)²) = sqrt(10) | 3.1623 |
| P7 | 1 | sqrt((7-3)² + (7-4)²) = sqrt(25) | 5.0000 |
| P8 | 1 | sqrt((8-3)² + (6-4)²) = sqrt(29) | 5.3852 |
| P9 | 1 | sqrt((7-3)² + (8-4)²) = sqrt(32) | 5.6569 |
| P10 | 1 | sqrt((6-3)² + (7-4)²) = sqrt(18) | 4.2426 |

Step 2: sort the distances.

1.4142, 2.0000, 2.0000, 2.8284, 3.1623, 3.1623, 4.2426, 5.0000, 5.3852, 5.6569

Step 3: take the three nearest neighbors.

- P3, class 0, distance 1.4142
- P4, class 0, distance 2.0000
- P5, class 0, distance 2.0000

Step 4: count the votes. Class 0 gets 3 votes, class 1 gets 0 votes.

Step 5: the prediction is the majority class, which is 0.

Here is the same computation in Python.

```python
import numpy as np
X = np.array([[1,2],[2,1],[2,3],[3,2],[1,4],[6,5],[7,7],[8,6],[7,8],[6,7]])
y = np.array([0,0,0,0,0,1,1,1,1,1])
new = np.array([3,4]); k = 3
d = np.sqrt(((X - new)**2).sum(axis=1))
idx = np.argsort(d)[:k]
labels = y[idx]
pred = np.bincount(labels).argmax()
print(pred)  # 0
```

Output:

```
0
```

The code reproduces the manual result exactly. If you are new to this kind of array work, the [Python for machine learning guide](/blog/data-analysis/python-for-machine-learning-guide) covers the NumPy basics used above.

## How to Interpret It

The prediction is a local decision. It tells you what the neighborhood around (3, 4) looks like, not what the whole dataset looks like. In this example the three closest points all belong to class 0, so the vote is unanimous and the confidence is high. A 2-to-1 split would still predict class 0 but with much weaker support.

The distances themselves carry information. The nearest neighbor sits at 1.4142, and the closest class 1 point sits at 3.1623. That gap suggests the new point is comfortably inside class 0 territory. If the nearest class 1 point were at 1.5, the boundary would be much tighter and the prediction less trustworthy.

You can also read k as a smoothness dial. With k = 1, the prediction follows the single closest point and the decision boundary is jagged. With larger k, the boundary becomes smoother and less sensitive to individual points.

## When to Use It (and when not to)

Use KNN when:

- The dataset is small or medium sized and you want a quick baseline.
- The decision boundary is irregular and you do not want to assume a functional form.
- You need a method that is easy to explain to a non-technical audience.
- You are working with a similarity-based problem, such as recommending items close to what a user already likes.

Avoid it when:

- The dataset is very large. Every prediction compares the query against every training point, so cost grows with the number of rows.
- You have many features. In high dimensions, distances between points become similar and the nearest neighbors stop being meaningfully near.
- Features have very different scales and you cannot standardize them.
- You need fast predictions on a system with tight latency budgets.

If you want a method that builds an explicit model and handles many features more gracefully, compare KNN with [support vector machines](/blog/data-analysis/support-vector-machines-svm) or a [random forest](/blog/data-analysis/what-is-random-forest).

## KNN vs K-Means Clustering

These two are often confused because both use k and both involve neighbors. They solve different problems.

| Aspect | K-Nearest Neighbors | K-Means Clustering |
|---|---|---|
| Learning type | Supervised | Unsupervised |
| What k means | Number of neighbors to consult | Number of clusters to form |
| Uses labels | Yes | No |
| Output | Predicted class or value | Cluster assignments |
| Training phase | None, data is stored | Iterative centroid updates |
| Typical use | Classification, regression | Grouping unlabeled data |

If your goal is to group unlabeled points, read [K-means clustering](/blog/data-analysis/k-means-clustering-how-it-works) instead. If your goal is to predict a known label, KNN is the right family.

## Common Mistakes

- **Forgetting to scale features.** A feature measured in thousands will dominate one measured in single digits. Fix: standardize or normalize all features before computing distances.
- **Choosing k without testing.** Picking k = 5 because it sounds reasonable ignores your data. Fix: evaluate several values of k with cross-validation and pick the one with the best held-out score.
- **Using an even k on a two-class problem.** A 2-2 tie has no majority. Fix: use an odd k, or define an explicit tie-breaking rule.
- **Evaluating on the training data.** KNN with k = 1 predicts every training point perfectly, which tells you nothing. Fix: always evaluate on data the model has not seen.
- **Mixing distance metrics carelessly.** Euclidean distance assumes comparable, continuous features. Fix: use a metric suited to your data, such as Hamming distance for binary features.
- **Ignoring the curse of dimensionality.** Adding many weak features can make all distances similar. Fix: reduce dimensions or select features before running KNN.

## Limitations

KNN cannot tell you which features matter. Every feature enters the distance calculation with equal weight unless you weight them yourself, so an irrelevant feature can pull neighbors in the wrong direction. It also stores the entire training set, which means memory grows linearly with your data, and prediction time grows the same way.

The method is sensitive to the local density of your data. In regions where training points are sparse, the "nearest" neighbors may be far away and unrepresentative, yet the algorithm still returns a confident-looking vote. Class imbalance compounds this: if one class has far more points, it will dominate most neighborhoods. KNN also gives no probability calibration by default. A 3-0 vote and a 2-1 vote both return a single label, and the raw vote fraction is not a well-calibrated probability.

## Frequently Asked Questions

### What is the best value of k?

There is no universal best value. Start with the square root of the number of training samples, rounded to an odd number, then test a range of values with cross-validation. Small k values fit local detail and noise. Large k values produce smoother boundaries but can blur genuine structure.

### Does KNN need training?

No. KNN is a lazy learner, so it stores the training data and does all its work at prediction time. This makes "training" instant but makes each prediction relatively expensive, since the query must be compared against every stored point.

### How does KNN handle more than two classes?

The same way it handles two. Count the labels among the k nearest neighbors and return the most frequent one. With three or more classes, ties become more likely, so pick an odd k and define a clear tie-breaking rule.

### Can KNN be used for regression?

Yes. Instead of a majority vote, average the target values of the k nearest neighbors. The prediction is a number rather than a class. The same scaling and k-selection advice applies.

### Why does KNN perform poorly with many features?

As the number of dimensions grows, the distance between any two points tends toward a similar value, so the concept of a "nearest" neighbor loses meaning. This is the curse of dimensionality. Reducing the number of features or applying dimensionality reduction usually helps more than tuning k.

## References

This article draws on the standard references listed under Further Reading.

## Further Reading

- [1.14. Semi-supervised learning, scikit-learn 1.9.1 documentation](https://scikit-learn.org/stable/modules/semi_supervised.html)
- [Lever J, Krzywinski M, Altman N (2016). Classification evaluation. Nature Methods](https://doi.org/10.1038/nmeth.3945)
- [scikit-learn User Guide](https://scikit-learn.org/stable/user_guide.html)
- [Wilson G, Bryan J, Cranston K et al. (2017). Good enough practices in scientific computing. PLOS Computational Biology](https://doi.org/10.1371/journal.pcbi.1005510)
- [Lever J, Krzywinski M, Altman N (2016). Model selection and overfitting. Nature Methods](https://doi.org/10.1038/nmeth.3968)
- [Saito T, Rehmsmeier M (2015). The Precision-Recall Plot Is More Informative than the ROC Plot When Evaluating Binary Classifiers on Imbalanced Datasets. PLOS ONE](https://doi.org/10.1371/journal.pone.0118432)

## Related Articles

- [K-Means Clustering: How It Works With a Worked Example](/blog/data-analysis/k-means-clustering-how-it-works)
- [Python for Machine Learning: A Beginner's Guide](/blog/data-analysis/python-for-machine-learning-guide)
- [Bayesian Classifiers: How Naive Bayes Works](/blog/data-analysis/bayesian-classifiers-naive-bayes)
- [Support Vector Machines (SVM): Definition and Examples](/blog/data-analysis/support-vector-machines-svm)
- [What Is Random Forest? Algorithm and Examples](/blog/data-analysis/what-is-random-forest)
- [Introduction To Statistical Learning](/blog/guides/introduction-to-statistical-learning)
- [Elements Of Statistical Learning](/blog/guides/elements-of-statistical-learning)
- [Mutual Nearest Neighbors (MNN) for Batch Effect Correction: A Step-by-Step Guide to Aligning Single-Cell Datasets](/knowledge/bioinformatics/mutual-nearest-neighbors-mnn-for-batch-effect-correction-a-step-by-step-guide-to-aligning-single-cel)