K-Nearest Neighbors (KNN): The Complete 2026 Guide

Most students study KNN on a flower dataset of 150 entries and never find out why it fails on a dataset of 10 million entries. The difference between those two is the area this guide belongs to.

KNN is the first algorithm introduced in machine learning courses, and that’s not just because it’s simple to implement – it’s the simplest algorithm to grasp without being a mathematician. You will see how it operates, how to tune its only parameter, and, most importantly, what happens when your dataset outgrows it.

What Is the KNN Algorithm?

The algorithm classifies the unknown point based on the label of the nearest points in the database. There is no training process and there is no fitting of any internal model to the dataset. It saves your data and then predicts labels based on distance and voting of the points.

That’s the reason for the name of the method being “lazy learning”. Other algorithms develop a model during the training period, either set of weights, decision tree, function etc. But KNN doesn’t do any of these and just memorizes the data, and does all the real work while making predictions.

That’s why KNN is a non-parametric model, since it doesn’t assume anything about the distribution of your data, and that’s why it can work in a wide range of situations, including spam filters, recommendation engines, diagnostic systems etc.

Imagine yourself a plot, where you see two clusters of points, green circles and red squares, and you throw a point somewhere and want KNN to determine its label. It calculates the distance to the nearest neighbors and sees which label occurs more often among them. That’s the essence of the whole method.

A Quick History — Who Actually Invented KNN?

KNN isn’t an old concept wrapped in fancy new packaging either; the nearest-neighbor technique was first proposed in a 1951 technical report written by Evelyn Fix and Joseph Hodges for the US Air Force School of Aviation Medicine. They wanted to find a way to classify data points that made no assumptions about the distribution of the underlying statistics; this was quite progressive thinking back then.

But Thomas Cover took their idea a step further. In his paper titled “Nearest Neighbor Pattern Classification,” co-written with Peter Hart, Cover proved something quite valuable: the maximum bound on the 1-nearest-neighbor error rate when the number of data points approaches infinity is at most twice that of the optimal classifier’s error rate for that problem.

And the part most people don’t know about is this: Fix and Hodges’ technical report remained mostly uncited for more than a decade… before Thomas Cover brought it back into the limelight in his paper.

How the KNN Algorithm Works

The whole algorithm reduces to four steps.

Step 1: Choose K

K is the number of neighbors the algorithm checks before making a decision. If K=5, it looks at the five closest points. That’s the only setting you really need to tune in basic KNN.

Step 2: Calculate Distance

The algorithm computes the distance between the new sample point being classified and all other points already present in your data set. By default, the KNN uses the Euclidean Distance method, but there are many others that are equally significant.

Step 3: Find the Nearest Neighbors

Sort all those distances from smallest to largest. The K smallest distances point to your K nearest neighbors.

Step 4: Vote or Average

In the case of classification, each neighbor “voters” for itself class label and the resulting label of the new point would be a majority label among all votes. In regression, KNN computes the average of the labels of K nearest neighbors.

There is no gradient descent, there is no backpropagation, there is no loss function. That’s why it is perfect to start your machine learning journey with, and that’s why people underestimate it.

Distance Metrics in KNN

Distance is the entire engine of KNN. Get the metric wrong for your data type, and every prediction downstream inherits that mistake.

Euclidean Distance

This represents the direct distance between the two points, and is the shortest distance possible to travel from one point to the other if walking in a straight line. This is the default in most implementations of KNN algorithms and is appropriate for situations where the features are continuous.

$$d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i – y_i)^2}$$

Manhattan Distance

It is also known as the taxicab distance, as it calculates the route taken by someone who can travel only along the grid lines, much like a taxi that travels in a city and cannot travel straight through buildings.

$$d(x, y) = \sum_{i=1}^{n}|x_i – y_i|$$

Manhattan distance tends to handle high-dimensional data a little better than Euclidean. Worth trying if Euclidean isn’t giving you clean separation.

Minkowski Distance

Minkowski distance is the general formula both of the above are special cases of, controlled by a single parameter, p.

$$d(x, y) = \left(\sum_{i=1}^{n}|x_i – y_i|^p\right)^{1/p}$$

Set p=2 and you get Euclidean distance. Set p=1 and you get Manhattan distance. Scikit-learn’s KNeighborsClassifier uses Minkowski with p=2 by default, which is just Euclidean distance wearing a more general name.

Hamming Distance

If we are talking about binary or categorical variables, then none of the metrics described earlier would make any sense. The direct distance cannot be calculated between “red” and “blue”. Instead, the Hamming Distance takes into account the number of places where two strings or vectors have different elements.

For example, when comparing “10101” and “10011” it becomes clear that the third and fourth digits are not the same, and therefore, the Hamming Distance is 2.

Why Feature Scaling Matters for KNN

This is the fatal flaw that causes more KNN models to fail than any other single thing, and it goes largely ignored in most KNN tutorials. Since KNN is totally driven by distance, any variable with a greater numeric scale will weigh far heavier in the distance calculation, regardless of whether the variable is actually more relevant to your prediction.

Take a case where you are predicting credit risk with variables like age (say 18 to 80) and yearly income (say 20,000 to 200,000). Use Euclidean distance on un-normalized numbers, and differences in income will overwhelm differences in age simply due to scale. This isn’t because the algorithm thinks income is more relevant.

The fix is feature scaling, applied before you fit the model, not after.

from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()

X_train_scaled = scaler.fit_transform(X_train)

X_test_scaled = scaler.transform(X_test)

StandardScaler centers each feature around a mean of 0 with a standard deviation of 1. MinMaxScaler squeezes every feature into a 0–1 range instead. Either works; what matters is doing it at all. Skip this step and you haven’t built a KNN model. You’ve built a model of whichever feature happened to have the biggest numbers.

I think this is the single most underrated step in the entire KNN workflow. Most articles bury it in a footnote. It deserves its own warning label.

How to Choose the Right Value of K

The Overfitting vs. Underfitting Tradeoff

If you choose K=1, then your model will overfit because your model simply memorizes the training data including the noise present in the data and will fail on any unseen data.

On the other hand, if you set K too large, your model will underfit because it averages over a very large neighborhood and no local pattern is recognizable when K=number of total training points. Every prediction will be of the majority class.

Cross-Validation for K Selection

K-fold cross-validation is the accepted method of determining it. Take your training set and divide it up into k parts, which coincidentally also happens to be the same letter used in K-in-KNN (another unfortunate naming convention with no relation). Use some of the folds to train and the rest to validate, repeat, and take the average of the accuracies.

from sklearn.model_selection import cross_val_score

import numpy as np

k_range = range(1, 21)

cv_scores = []

for k in k_range:

    knn = KNeighborsClassifier(n_neighbors=k)

    scores = cross_val_score(knn, X_train_scaled, y_train, cv=5)

    cv_scores.append(scores.mean())

best_k = k_range[np.argmax(cv_scores)]

The Elbow Method

Plot error rate against K. Error usually drops fast at first, then levels off. The bend in the curve, where additional K stops buying you meaningfully lower error, is your candidate K.

Why Odd K Values Help (and Where They Still Don’t)

Odd K does not have the problem of ties when doing binary classifications. In case of K = 4 and 2-2 classification of two classes, there is no apparent win, and it ends up using a random tie breaker, which is generally the first class to appear in sorted order. Definitely not something that you would like your classifier to use in making important decisions.

However, something interesting that I did not see anyone mentioning is that odd K does not guarantee anything in multi-class classification. For instance, in the case of 3 classes and K=9, it is possible to end up with 3-3-3 division without a clear majority. When doing multi-class classification, prepare for tie-breaks. In scikit-learn, the tie is broken based on the proximity (closest class among the tied classes).

A Quick Starting Rule of Thumb

If you would like to begin with a number to experiment with rather than just guessing randomly, one often used rule of thumb would be k ≈ √n, where n is the number of your training data. If your data consists of 10,000 lines, then it would be around K=100, which means it is large enough to filter noise but small enough to respond to any local pattern.

KNN vs. K-Means — Don’t Confuse These

They share a letter and basically nothing else, and the name collision trips up more beginners than it should.

	KNN	K-Means
Learning type	Supervised	Unsupervised
Goal	Classify/predict using labeled data	Group unlabeled data into clusters
What “K” means	Number of neighbors to check	Number of clusters to create
Output	A label or value for a new point	Cluster assignments for all points

If your data comes pre-labeled and you are predicting a class, then go for KNN. But if your data doesn’t have any labels and you are trying to figure out clusters from it, then K-means is the choice. They cannot be used interchangeably because “K” represents two entirely different things in both of them.

Implementing KNN in Python

From Scratch

Building it yourself once is worth more than reading about it ten times. Here’s a working version using nothing but NumPy and the standard library:

import numpy as np

from collections import Counter

def euclidean_distance(point1, point2):

    return np.sqrt(np.sum((np.array(point1) – np.array(point2))**2))

def knn_predict(training_data, training_labels, test_point, k):

    distances = []

    for i in range(len(training_data)):

        dist = euclidean_distance(test_point, training_data[i])

        distances.append((dist, training_labels[i]))

    distances.sort(key=lambda x: x[0])

    k_nearest_labels = [label for _, label in distances[:k]]

    return Counter(k_nearest_labels).most_common(1)[0][0]

training_data = [[1, 2], [2, 3], [3, 4], [6, 7], [7, 8]]

training_labels = [‘A’, ‘A’, ‘A’, ‘B’, ‘B’]

test_point = [4, 5]

k = 3

prediction = knn_predict(training_data, training_labels, test_point, k)

print(prediction)

Output: A. The function calculates distance from the test point to every training point, sorts by distance, grabs the K closest labels, and returns whichever label appears most often. Three lines of actual logic, once you strip out the bookkeeping.

Using Scikit-Learn

For anything beyond a learning exercise, use scikit-learn. It’s faster, better tested, and handles edge cases your from-scratch version probably doesn’t.

from sklearn.neighbors import KNeighborsClassifier

from sklearn.metrics import accuracy_score

knn = KNeighborsClassifier(n_neighbors=5)

knn.fit(X_train_scaled, y_train)

y_pred = knn.predict(X_test_scaled)

print(f”Test Accuracy: {accuracy_score(y_test, y_pred):.2f}”)

Five neighbors, scaled features, one prediction line. That’s a complete, production-reasonable KNN classifier. (If you work in R, the class library’s knn() function does the same job in one call, with normalization handled manually since base R doesn’t ship a built-in scaler.)

Scaling KNN — KD-Trees, Ball Trees, and Approximate Search

Brute-force KNN, comparing your query point against every single training point, runs in O(n·d) time per prediction, where n is your training rows and d is your features. That’s fine at 10,000 rows. At 10 million rows with 50 features, you’re doing 500 million distance calculations for a single prediction. That’s the wall every “KNN doesn’t scale” warning is actually talking about.

The fix is to stop comparing against everything. A KD-Tree organizes your training data into a binary tree, recursively splitting the space along alternating dimensions, so a new query can skip entire branches that are too far away to matter. In low-to-moderate dimensions, this drops query time toward O(log n). A genuinely massive improvement.

from sklearn.neighbors import KNeighborsClassifier

# Scikit-learn picks the algorithm automatically based on your data,

# but you can force it explicitly:

knn_fast = KNeighborsClassifier(n_neighbors=5, algorithm=’kd_tree’)

knn_fast.fit(X_train_scaled, y_train)

Ball Trees are another alternative, using nested hyperspheres as opposed to hyperplanes, and generally perform better when the number of dimensions rises above 20 or so, which is when KD-Trees become slower anyway, essentially reverting to brute force. Curse of dimensionality strikes again, this time in the indexing domain rather than in the metric space domain.

Then there is always the case of the tree-based approaches not being fast enough, especially in vector databases in 2026. If that’s true for your specific case, then approximate algorithms such as HNSW (Hierarchical Navigable Small World graphs) are the way to go. These sacrifice a bit of precision for an enormous gain in speed and are the foundation of current vector search solutions.

Real-World Applications of KNN

Recommendation systems. Locate users who have had similar behavior in the past, and recommend the items that those users enjoyed. The “customers who bought this item also bought” recommendation system is ultimately based on KNN.

Spam filtering. Compare the characteristics of a newly received email with examples of known spam emails and examples of non-spam emails to determine which type it belongs to.

Credit Risk Assessment. Banks will compare potential loan applicants against their history of customers with different histories of repaying loans. However, credit risk analysis usually uses multiple models, and KNN is just one of them.

Healthcare diagnostics. KNN has been used for predicting disease likelihood through comparison of gene expression or clinical parameters of the patients to similar data of known disease cases.

Pattern recognition. Comparison of a picture of an unknown handwritten digit to labeled samples from a training set is one of the classic use cases of the KNN algorithm.

Anomaly detection. This application never seems to be mentioned. If a point’s nearest neighbors are very far away, it is a sign that the point does not belong to any of the clusters. It is exactly how fraud detection systems work.

Advantages and Disadvantages of KNN

Advantages

• Genuinely simple. Hyperparameters? No. Architecture design? Not required. Just K and a distance measure.
• Training step unnecessary. New points can be incorporated immediately, without any re-training at all.
• Flexible. The same underlying algorithm is used for both classification and regression tasks.
• Multi-class by nature. In contrast to most classifiers, which must use techniques such as one-vs-rest, KNN finds five classes just as easy as two.

Disadvantages

• Doesn’t scale alone. The brute force algorithm has an O(n·d) runtime: okay for small datasets but really slow after a couple hundred thousand instances without using a tree-based index.
• Performs poorly in high dimensional spaces. With an increasing number of features, the distance between the closest point and the most distant one approaches each other, making “nearest neighbor” meaningless. For over 15 or 20 features, use dimensionality reduction such as PCA.
• Vulnerable to irrelevant features. All features affect the distance measure, regardless of their predictive power. It’s more important for distance algorithms than tree-based classifiers.
• Memory intensive. All training instances must be kept in memory because there is no compressed representation of the data.

When Should You NOT Use KNN?

Go through the below checklist before you proceed with your choice:

• If your data is over a couple of hundred thousand records without the intention of creating a tree-based index, give this second thought or be ready for implementing KD-Trees / Ball Trees.
• If you have over 20 features without dimensionality reduction, the curse of dimensionality will negatively affect accuracy more than tuning of K.
• If your classes are severely imbalanced, for example 95%/5%, then the KNN voting mechanism will default on choosing the class that makes up the vast majority of the population, unless distance weighting or resampling are applied prior to KNN prediction.
• If you need explanations of how particular records were classified by KNN, keep in mind that such explanations are simpler than those from a neural network and yet still more difficult to understand than decision trees’ if-then rules.

If you are facing two or more of the above-mentioned cases, then it’s time to rethink your algorithm choice.

Frequently Asked Questions

Conclusion

KNN is the algorithm that everybody gets introduced to but almost never learns how to scale properly. You have learned the two parts: how the flower-and-fruit example works and what happens when your dataset no longer fits into one screen. Next time someone says KNN does not scale, challenge them about their use of a Ball Tree.