K-Nearest Neighbors: Finding Similar Data Points

When an on-call engineer sees a strange alert, the first question is often “have we seen one like this before, and what was it?” K-nearest neighbors (KNN) turns that habit into an algorithm. To classify a new point, it finds the k training points most similar to it and lets them vote. There is no equation to fit and no tree to grow. The training data is the model.

That simplicity makes KNN easy to explain and a useful baseline, and the idea behind it, finding similar items quickly, now powers recommendation systems and the vector search behind retrieval-augmented generation. It also has sharp edges: it depends entirely on how you measure distance, it slows down as data grows, and it degrades quickly when you add features that don’t matter.

This article follows support vector machines in the series and uses the same toy points and synthetic alert data, so the results line up with the earlier models. It assumes you know train and test splits, cross-validation and ROC AUC; model training and evaluation covers them.

How KNN makes a prediction

KNN has no training step in the usual sense. fit stores the data, and possibly builds an index to search it faster. All the work happens at prediction time:

1. Measure the distance from the new point to every training point.
2. Take the k closest.
3. For classification, return the most common label among them. For regression, return the average of their target values.

flowchart LR
    N["New point"] --> D["Distance to each training point"]
    D --> S["Sort by distance"]
    S --> K["Keep the k nearest"]
    K --> V{"Task?"}
    V -->|"Classification"| C["Majority vote"]
    V -->|"Regression"| R["Average of targets"]

Because it postpones all computation until a query arrives, KNN is called a lazy learner. Logistic regression, trees and SVMs are eager: they spend effort up front to build a compact model, then predict cheaply. KNN reverses that trade.

Here are the ten alerts from the SVM article, two features each, and a new alert to classify:

import numpy as np
from sklearn.neighbors import KNeighborsClassifier

# x0 = error rate (percent), x1 = p95 latency (hundreds of ms)
X = np.array([
    [0.5, 1.5], [1.0, 2.0], [1.5, 1.0], [0.8, 3.0], [2.0, 2.2],   # noise
    [3.0, 5.0], [3.5, 4.0], [4.0, 6.0], [2.8, 6.5], [4.5, 5.0],   # incidents
])
y = np.array([0, 0, 0, 0, 0, 1, 1, 1, 1, 1])

new = np.array([[2.6, 3.4]])
knn = KNeighborsClassifier(n_neighbors=3).fit(X, y)
dist, idx = knn.kneighbors(new)
for d, i in zip(dist[0], idx[0]):
    print(f"neighbor {X[i].tolist()}  label={y[i]}  distance={d:.3f}")
print("predicted:", knn.predict(new)[0])
print("probability of incident:", knn.predict_proba(new)[0, 1].round(3))

neighbor [3.5, 4.0]  label=1  distance=1.082
neighbor [2.0, 2.2]  label=0  distance=1.342
neighbor [3.0, 5.0]  label=1  distance=1.649
predicted: 1
probability of incident: 0.667

Two of the three nearest alerts were incidents, so the prediction is “incident” and predict_proba reports two thirds. That probability is just the vote share, which matters later: with k=3 the only possible values are 0, 1/3, 2/3 and 1.

Notice that the second neighbor, [2.0, 2.2], is one of the SVM’s two support vectors. Both models are interested in the points near the boundary. The SVM keeps only those points; KNN keeps everything and decides which points matter afresh for each query.

Measuring distance

“Nearest” needs a definition. scikit-learn’s default is the Minkowski distance with p=2, which is ordinary straight-line Euclidean distance. The common choices:

Euclidean distance squares each difference, so one feature that differs a lot dominates the total. Manhattan distance adds differences linearly, which spreads the influence more evenly across features. On the alert data below, Manhattan does slightly better for exactly that reason.

Cosine distance ignores vector length and compares direction only. That is why it is the usual choice for embeddings, the vectors a language model produces to represent the meaning of a piece of text: two documents about the same subject point the same way regardless of their length.

Choosing k

k is the one setting that matters most. A small k means each prediction depends on a few nearby points, so the boundary follows every noisy label. A large k averages over a wide region, so the boundary is smooth but can wash out real structure. In bias and variance terms, small k is low bias and high variance; large k is the reverse.

On the two-moons data from the SVM article, two interleaving half circles with noise:

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

X, y = make_moons(n_samples=1000, noise=0.3, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.5, random_state=0)

for k in [1, 3, 5, 15, 31, 75, 151, 499]:
    knn = KNeighborsClassifier(n_neighbors=k).fit(X_train, y_train)
    print(f"k={k:<4} train={knn.score(X_train, y_train):.3f}  test={knn.score(X_test, y_test):.3f}")

k=1    train=1.000  test=0.876
k=3    train=0.938  test=0.900
k=5    train=0.928  test=0.908
k=15   train=0.926  test=0.906
k=31   train=0.920  test=0.894
k=75   train=0.916  test=0.898
k=151  train=0.880  test=0.870
k=499  train=0.508  test=0.492

With k=1, training accuracy is always perfect, because every training point is its own nearest neighbor. That number tells you nothing; the test score shows the overfitting. From k=5 to k=75 the test accuracy is flat at about 90 percent, the same level the tuned RBF SVM reached on this data. At k=499, every query sees almost the entire training set of 500 points, so the model predicts the majority class everywhere and drops to a coin flip.

A few practical rules for k:

• Choose it by cross-validation, not by training accuracy.
• For two classes, an odd k avoids tied votes. scikit-learn breaks ties by taking the class that comes first in sorted order, which is arbitrary.
• Expect the best k to grow with the size of the dataset. A larger dataset can afford to average over more neighbors while still staying local.

Weighting closer neighbors

By default each of the k neighbors gets one vote. With weights="distance", each vote is weighted by 1 / distance, so a neighbor twice as close counts twice as much. That reduces the sensitivity to k, because adding a few far neighbors changes little, and it gives smoother probabilities. It also means a training point at distance zero, an exact duplicate of the query, decides the prediction alone.

KNN on the alert data

The moons have two features on the same scale. The alert data from the random forest article has 5,000 alerts and eight features on very different scales, with curved effects, interactions and one feature, the hour of day, that has no effect at all. Save the data-generating code from that article as alerts.py to run the examples below.

Scaling is not optional

Distance adds up differences across features, so a feature measured in hundreds of milliseconds overwhelms one measured in percent. Compare the same model with and without scaling:

from sklearn.metrics import roc_auc_score
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import MinMaxScaler, StandardScaler
from alerts import X, y

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, stratify=y, random_state=0
)

models = {
    "no scaling": KNeighborsClassifier(n_neighbors=15),
    "StandardScaler": make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=15)),
    "MinMaxScaler": make_pipeline(MinMaxScaler(), KNeighborsClassifier(n_neighbors=15)),
}
for name, model in models.items():
    model.fit(X_train, y_train)
    auc = roc_auc_score(y_test, model.predict_proba(X_test)[:, 1])
    print(f"{name:<15} accuracy={model.score(X_test, y_test):.3f}  ROC AUC={auc:.3f}")

no scaling      accuracy=0.717  ROC AUC=0.570
StandardScaler  accuracy=0.822  ROC AUC=0.864
MinMaxScaler    accuracy=0.831  ROC AUC=0.879

Without scaling, the neighbors are effectively chosen by latency and minutes since deploy, the two features with the largest numeric ranges. An AUC of 0.57 is barely better than random ranking. Either scaler fixes it. As with the SVM, put the scaler inside a pipeline so it is fitted only on training folds.

Scaling decides how much each feature counts. Standardizing gives every feature equal weight, which is a choice, not a law. If you know one feature matters more, multiplying its scaled values by a constant makes the model pay more attention to it.

Tuning k, weights and the metric

Search the three settings together with cross-validation:

from sklearn.metrics import accuracy_score
from sklearn.model_selection import GridSearchCV, train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from alerts import X, y

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, stratify=y, random_state=0
)

pipe = Pipeline([("scale", StandardScaler()), ("knn", KNeighborsClassifier())])
grid = GridSearchCV(
    pipe,
    {
        "knn__n_neighbors": [5, 15, 31, 51, 75, 101, 151],
        "knn__weights": ["uniform", "distance"],
        "knn__p": [1, 2],
    },
    cv=5,
    scoring="roc_auc",
    n_jobs=-1,
)
grid.fit(X_train, y_train)
print("best params:", grid.best_params_)
print(f"cross-validated AUC: {grid.best_score_:.3f}")
print(f"test AUC:            {grid.score(X_test, y_test):.3f}")
print(f"test accuracy:       {accuracy_score(y_test, grid.predict(X_test)):.3f}")

best params: {'knn__n_neighbors': 101, 'knn__p': 1, 'knn__weights': 'distance'}
cross-validated AUC: 0.899
test AUC:            0.894
test accuracy:       0.832

The cross-validated AUC scores from grid.cv_results_ for distance weighting show the shape of the search:

Three things stand out. The default k=5 is far too small for 3,750 noisy training rows. Above about 50 neighbors, the score is flat, so any value in that range works. And Manhattan distance beats Euclidean by about a point once k is large. Uniform weighting scored within 0.003 of distance weighting throughout, so the weighting barely matters here.

Irrelevant features hurt

The hour feature has no effect on incidents, yet it counts as much as any other feature in the distance. A tree or a regularized linear model learns to ignore a useless feature. KNN can’t: it has no parameters to learn, so every feature you include shapes the neighborhoods. To see how much this costs, drop hour, then go the other way and add columns of pure noise:

import numpy as np
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from alerts import X, y

rng = np.random.default_rng(0)
model = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=51))

without_hour = np.delete(X, 5, axis=1)
print(f"8 features:              AUC={cross_val_score(model, X, y, cv=5, scoring='roc_auc').mean():.3f}")
print(f"7 features (no hour):    AUC={cross_val_score(model, without_hour, y, cv=5, scoring='roc_auc').mean():.3f}")
for extra in [5, 20, 50]:
    noisy = np.hstack([X, rng.normal(size=(len(X), extra))])
    auc = cross_val_score(model, noisy, y, cv=5, scoring="roc_auc").mean()
    print(f"8 + {extra:<2} noise features:    AUC={auc:.3f}")

8 features:              AUC=0.889
7 features (no hour):    AUC=0.894
8 + 5  noise features:    AUC=0.874
8 + 20 noise features:    AUC=0.854
8 + 50 noise features:    AUC=0.812

Removing one useless feature helps, and each batch of noise features makes things steadily worse. With 50 noise columns, most of every distance is noise, and the neighbors are close to a random sample. Feature selection, domain knowledge about what matters, or a dimensionality reduction step such as PCA (covered later in this series) often does more for KNN than any tuning of k.

How it compares

On the same split as the earlier articles in the series:

logistic regression  accuracy=0.821  ROC AUC=0.873
KNN, defaults        accuracy=0.807  ROC AUC=0.829
RBF SVM, tuned       accuracy=0.829  ROC AUC=0.890
KNN, tuned           accuracy=0.832  ROC AUC=0.894
random forest        accuracy=0.854  ROC AUC=0.902

Default KNN is the weakest model in the series so far. Tuned, with scaling, a large k and Manhattan distance, it slightly beats the tuned SVM, and the random forest stays ahead. Both KNN and the RBF SVM make predictions from similarity to stored training points, so their similar scores are not a coincidence. The forest wins for the reason given in the SVM article: the data has sharp thresholds, which trees capture directly and distance-based models only approximate.

Probabilities and explanations

A KNN probability is the (optionally weighted) share of neighbors in each class. That makes it easy to explain: you can show someone the actual past alerts the prediction was based on. Here is the same alert the random forest and SVM articles examined, with moderate errors, high latency 12 minutes after a deploy, and four replicas:

import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from alerts import X, y

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, stratify=y, random_state=0
)
tuned = make_pipeline(
    StandardScaler(), KNeighborsClassifier(n_neighbors=101, weights="distance", p=1)
).fit(X_train, y_train)

# error_rate, latency_ms, since_deploy, cpu_util, queue_depth, hour, retries, replicas
alert = np.array([[1.5, 780, 12, 55, 18, 14, 2, 4]])
print(f"probability: {tuned.predict_proba(alert)[0, 1]:.2f}")

dist, idx = tuned[-1].kneighbors(tuned[0].transform(alert), n_neighbors=5)
for d, i in zip(dist[0], idx[0]):
    print(X_train[i].round(1).tolist(), y_train[i], round(d, 2))

probability: 0.34
[1.4, 786.2, 59.8, 54.5, 23.0, 15.0, 2.0, 5.0] 0 2.41
[1.5, 853.0, 35.7, 46.3, 18.0, 7.0, 1.0, 4.0] 0 2.72
[0.4, 842.6, 7.6, 41.2, 20.0, 10.0, 2.0, 3.0] 1 2.99
[1.3, 608.3, 0.7, 52.7, 17.0, 14.0, 0.0, 5.0] 0 3.11
[0.8, 776.0, 3.4, 32.4, 21.0, 21.0, 2.0, 4.0] 1 3.11

The generating formula gives this alert a 0.63 chance of being an incident. The forest said 0.57, the SVM 0.32, and KNN 0.34. The neighbor list shows why. The closest match has the same error rate and latency, but its deploy was nearly an hour earlier and it has five replicas; in this data, the post-deploy latency risk fades within about an hour, and the queue risk only applies below five replicas. A plain distance can’t know that 12 minutes and 60 minutes since a deploy are very different situations while 15:00 and 14:00 UTC are irrelevant. Both differences simply add to the total.

This is the most useful thing about KNN as a diagnostic: when it is wrong, you can see which “similar” examples misled it, and that usually points at a feature that needs rescaling, transforming or removing.

With k=101, the probabilities have plenty of possible values, and the test Brier score is 0.124, compared with 0.117 for the calibrated SVM and 0.108 for the forest. With a small k, probabilities are coarse, and you may want to calibrate them with CalibratedClassifierCV, as in the SVM article.

The curse of dimensionality

The noise-feature experiment above is one face of a general problem. In high dimensions, distances between random points concentrate: the nearest point is barely closer than the farthest one. Try it with 1,000 random points in a unit cube:

import numpy as np

rng = np.random.default_rng(0)
for d in [2, 10, 100, 1000]:
    points = rng.uniform(size=(1000, d))
    query = rng.uniform(size=d)
    dist = np.linalg.norm(points - query, axis=1)
    print(f"d={d:<5} nearest={dist.min():6.2f}  farthest={dist.max():6.2f}  ratio={dist.max() / dist.min():5.2f}")

d=2     nearest=  0.01  farthest=  1.33  ratio=135.62
d=10    nearest=  0.47  farthest=  2.11  ratio= 4.48
d=100   nearest=  3.35  farthest=  4.65  ratio= 1.39
d=1000  nearest= 12.17  farthest= 13.55  ratio= 1.11

In two dimensions the nearest point is over a hundred times closer than the farthest. In a thousand dimensions, it is only 11 percent closer, so “nearest” barely means anything. The fix is not more data in the same space, since the amount needed grows exponentially with dimension, but fewer, more meaningful dimensions.

That is why KNN works well on embeddings despite their hundreds of dimensions. Their values are not independent noise: a trained model has arranged them so that distance reflects meaning, and the data lies close to a much lower-dimensional structure. On raw, unprocessed features with hundreds of columns, KNN usually struggles.

Making neighbor search fast

Prediction cost is KNN’s practical problem. Brute-force search compares each query with every training point, so it grows linearly with the size of the training set, and every prediction pays it again. scikit-learn offers two tree indexes that prune the search, the k-d tree and the ball tree, and picks among the three methods automatically with algorithm="auto". Here they are on 200,000 random points, each answering 2,000 queries for the 10 nearest neighbors, on a 4-core machine:

import time
import numpy as np
from sklearn.neighbors import NearestNeighbors

rng = np.random.default_rng(0)
for d in [3, 8, 50]:
    data = rng.normal(size=(200_000, d))
    queries = rng.normal(size=(2_000, d))
    for algorithm in ["brute", "kd_tree", "ball_tree"]:
        start = time.perf_counter()
        index = NearestNeighbors(n_neighbors=10, algorithm=algorithm).fit(data)
        built = time.perf_counter() - start
        start = time.perf_counter()
        index.kneighbors(queries)
        searched = time.perf_counter() - start
        print(f"d={d:<3} {algorithm:<10} build={built:5.2f}s  query={searched:5.2f}s")

In three dimensions the k-d tree answers in a thirtieth of the brute-force time. By eight dimensions the advantage is gone, and at 50 dimensions the trees are a hundred times slower than brute force, which runs as optimized matrix arithmetic. This is the curse of dimensionality again: when all points are about equally far away, a tree can’t rule out any branch and ends up visiting nearly everything. Your timings will differ, but the crossover pattern holds.

Approximate nearest neighbors

For millions or billions of high-dimensional vectors, even brute force is too slow per query. Approximate nearest neighbor (ANN) indexes give up a little accuracy, occasionally missing a true neighbor, in exchange for queries that are orders of magnitude faster. Two families dominate:

• Graph-based (HNSW): hierarchical navigable small world graphs link each vector to a few close neighbors in layered graphs. A query starts at a coarse layer and greedily walks toward closer nodes. Fast and accurate, but memory-hungry.
• Cluster-based (IVF), often with product quantization (PQ): the vectors are partitioned into clusters, and a query searches only the few closest clusters. PQ compresses the vectors to save memory at some cost in accuracy.

The usual measure of an ANN index is recall: the share of the true k nearest neighbors it returns. You tune the index to trade recall against latency and memory.

flowchart TD
    A["Need nearest neighbors"] --> B{"Under about 10 dimensions?"}
    B -->|"Yes"| C["k-d tree or ball tree"]
    B -->|"No"| D{"Up to about a million points?"}
    D -->|"Yes"| E["Exact brute-force search"]
    D -->|"No"| F{"Fits in memory?"}
    F -->|"Yes"| G["ANN with HNSW"]
    F -->|"No"| H["ANN with IVF and PQ compression"]

The thresholds in the diagram are rough guides, not rules; benchmark on your own data and query rate.

KNN in the cloud

Plain KNN classification on a few thousand rows runs fine in scikit-learn on a laptop, as in the simple ML project setup. In the cloud, nearest-neighbor search shows up in two places.

Amazon SageMaker AI has a built-in k-NN algorithm for classification and regression. Its required hyperparameters are k, feature_dim, predictor_type (classifier or regressor) and sample_size, the number of training points to keep. It can optionally reduce dimensions with a random projection (dimension_reduction_type of sign or fjlt) and builds a FAISS index, with index_type set to faiss.Flat for exact search or faiss.IVFFlat and faiss.IVFPQ for the approximate cluster-based indexes described above. A hyperparameter configuration looks like this:

{
  "feature_dim": "7",
  "k": "101",
  "predictor_type": "classifier",
  "sample_size": "3750",
  "index_type": "faiss.Flat"
}

Vector search is where most nearest-neighbor queries now run. Amazon OpenSearch Service supports exact k-NN and approximate search with HNSW and IVF indexes, and Google Cloud and Azure offer managed vector search in their AI and search services. These systems store embeddings and answer “find the most similar items” for semantic search, recommendations and retrieval-augmented generation. The AWS generative AI services article shows how Bedrock Knowledge Bases uses such a vector store to find the document chunks most relevant to a question. That is KNN with cosine distance and an ANN index, without the voting step.

For further reading, see the scikit-learn nearest neighbors guide, the SageMaker k-NN hyperparameters and how the k-NN algorithm works, and the Amazon OpenSearch Service vector database overview.

KNN compared with other classifiers

The last row is a real advantage. A KNN model absorbs new labeled examples immediately, with no retraining, which suits systems where the reference data changes daily. The same machinery does regression with KNeighborsRegressor, which averages the neighbors’ target values. Its predictions can never go outside the range of the training targets, so it can’t extrapolate a trend.

When to use KNN

KNN is a good choice when:

• the dataset is small to medium, or you can use a fast index
• you have few, meaningful, numeric features, or good embeddings
• you want to justify predictions by showing similar past cases
• the reference data changes often and retraining is inconvenient
• you need a quick, assumption-free baseline

Look elsewhere for mixed tabular data with thresholds and many irrelevant columns (a random forest or gradient boosting), for low-latency predictions on very large training sets without an ANN index (logistic regression or a tree ensemble), or for readable rules (decision trees).

Key takeaways

• KNN predicts by finding the k most similar training points and taking a vote, or an average for regression. Training only stores the data; the cost moves to prediction time.
• The distance metric defines similarity. Euclidean is the default; Manhattan is often better with many features, and cosine is standard for text and embeddings.
• Choose k by cross-validation. Small k overfits, very large k predicts the majority class. On the alert data, the default k=5 was far too small, and anything above about 50 worked.
• Always scale features in a pipeline. Without scaling, KNN on the alert data scored an AUC of 0.57; with scaling and tuning, 0.894.
• Every feature counts equally in the distance, so irrelevant features hurt directly. Selecting or reducing features often helps more than tuning k.
• In high dimensions, distances concentrate and tree indexes stop helping. Use brute force for moderate sizes and approximate indexes such as HNSW or IVF for large vector collections.
• The same nearest-neighbor search powers vector databases, semantic search and retrieval-augmented generation.