Chapter overview

K-nearest neighbors (KNN) classifies a new observation by comparing it with labeled training observations. The algorithm locates the k closest examples under a chosen distance measure and combines their labels. This local, example-based logic is intuitive, but its performance depends strongly on feature scale, neighborhood size, irrelevant dimensions, and the way evaluation is organized.

This chapter moves from geometric intuition to a leakage-safe scikit-learn workflow. Students calculate distances manually, inspect neighbor votes and probabilities, compare uniform and distance weighting, study the bias–variance pattern across values of k, and complete a practical lab using the breast cancer dataset built into scikit-learn.

Learning objectives

• Explain why nearby observations can provide evidence for a class label.
• Describe KNN as an instance-based, non-parametric, and lazy learning method.
• Calculate and interpret Euclidean, Manhattan, and Minkowski distances.
• Explain how n_neighbors, weights, metric, and p change a prediction.
• Standardize numerical features inside a leakage-safe pipeline.
• Relate small and large values of k to bias, variance, noise, and underfitting.
• Evaluate training and validation performance across candidate values of k.
• Recognize computational and high-dimensional limitations of KNN.

Chapter map

Table 15.1. Questions answered in this chapter

Prerequisites

Students should understand features X, target y, classification, training and validation sets, and basic accuracy. Familiarity with pandas, NumPy, and scikit-learn pipelines is helpful. The practical lab supplies complete code and can be run in Jupyter Notebook, JupyterLab, Google Colab, or a Python script.

Running example

Imagine classifying a cell sample as benign or malignant from numerical measurements. A new sample is compared with labeled historical samples. If most nearby samples are malignant, that local evidence supports a malignant prediction. The lab uses scikit-learn’s breast cancer dataset, but the same workflow applies to many classification problems with meaningful feature-space similarity.

15.1 Basic principle

KNN rests on a local smoothness assumption: observations that are close in a useful feature space often share a label. The method turns that assumption into a repeatable prediction procedure.

Similar observations should have similar labels

Similarity is not discovered automatically; it is defined by the selected features, their representation, their scale, and the distance measure. Two customers may be similar in recent purchasing behavior but very different in age. Two images may be visually similar after feature extraction even though their raw pixel values are not. KNN succeeds when geometric closeness corresponds reasonably well to the class structure of the problem.

This assumption is local rather than global. The model does not require one straight line or one equation to describe every class boundary. Different regions can follow different patterns because every prediction is based on a neighborhood around the query point.

Table 15.2. The vocabulary of a KNN prediction

Figure 15.1. Prediction with k-nearest neighbors

Distance between observations

For two observations a and b with p features, a distance function converts feature-by-feature differences into one nonnegative number. Smaller values indicate greater similarity under that definition. A distance of zero means the represented feature values are identical, though duplicated feature vectors can still have conflicting labels.

A worked distance example

Suppose a = (2, 6) and b = (5, 2). Their coordinate differences are −3 and 4. The Euclidean distance is √(3² + 4²) = 5. The Manhattan distance is |−3| + |4| = 7. The ranking of candidate neighbors can change when the metric changes, especially in spaces with several dimensions or outliers.

Nearest neighbors

After distances are calculated, the training observations are ordered from smallest to largest distance. The first k observations form the neighborhood. Only these neighbors contribute to a standard KNN prediction. A point just outside the neighborhood contributes nothing with uniform weighting, even if its distance is almost identical to that of the kth neighbor.

Majority voting

With uniform weights, every neighbor contributes one vote. The predicted class is the class with the largest vote count. For k = 5, neighbor labels [A, A, B, A, B] produce class A because A receives three votes. In multiclass problems, the winner needs only more votes than every competing class; it does not always need more than half of all votes.

Table 15.3. Equal votes can disagree with inverse-distance votes

Uniform voting predicts B because B has two of the three votes. An inverse-distance rule predicts A because the single A neighbor is much closer. This example shows that weights change the decision rule, not merely the reported probability.

Class probabilities in scikit-learn

KNeighborsClassifier can return class-probability estimates through predict_proba(). With uniform weights, the probability for a class is its fraction of the k neighbors. With distance weights, it is the class’s normalized total weight. These are local vote proportions, not automatically calibrated probabilities; their reliability should be evaluated when decisions depend on probability quality.

Lazy learning and model fitting

KNN is often called a lazy learner because fitting does not estimate a compact predictive equation. The fit step mainly validates and stores the training data and prepares an internal neighbor-search structure when appropriate. Most computation occurs at prediction time, when distances or search queries are needed for new observations.

Table 15.4. Work performed during fitting and prediction

15.2 Main parameters

A KNN model is defined by the neighborhood size, the rule that weights neighbors, the distance metric, and search settings. These choices determine which examples influence a prediction and by how much.

Number of neighbors: n_neighbors

The parameter n_neighbors is k. A small k produces a highly local decision; a large k averages evidence over a broader region. The largest valid k cannot exceed the number of training observations available to the fitted model, and cross-validation folds may contain fewer training samples than the full dataset.

• k = 1 assigns the label of the single closest training observation.
• Increasing k usually smooths the decision boundary and reduces sensitivity to one noisy point.
• Very large k can make the majority class dominate and erase meaningful local structure.
• Odd values can reduce some two-class vote ties, but odd k is not a universal rule for multiclass or weighted voting.

Uniform versus distance weighting

Table 15.5. Neighbor weighting options

When weights='distance', scikit-learn gives nearer observations greater influence. If a query exactly matches one or more training points, zero-distance handling is special: the coincident points dominate rather than causing division by zero. Conflicting duplicates should still be investigated because they indicate label ambiguity or data-quality problems.

Distance metric and Minkowski power p

The default metric is Minkowski with p = 2, which corresponds to Euclidean distance. Setting p = 1 gives Manhattan distance. The metric controls the geometry of neighborhoods; it should reflect how feature differences combine in the application. The same k can produce different neighbors under different metrics.

Table 15.6. Common distance choices

Search algorithm, leaf_size, and n_jobs

KNeighborsClassifier also exposes implementation settings. algorithm='auto' lets scikit-learn select a suitable strategy among brute force, KD tree, and ball tree. The fastest choice depends on sample size, dimensionality, metric, and data representation. leaf_size affects tree construction, query speed, and memory, while n_jobs controls parallel work for neighbor searches where supported.

Table 15.7. Secondary implementation parameters

15.3 Importance of scaling

Distance compares numerical coordinates. If one feature spans thousands and another spans fractions, the large-range feature can dominate the neighborhood even when it is not more informative.

Why large ranges dominate

Consider two customer features: age in years and annual income in dollars. A difference of 10 years contributes 100 to squared Euclidean distance, while a difference of $20,000 contributes 400,000,000. Without scaling, income almost completely determines which customers are called close. The algorithm is responding to units, not necessarily importance.

Table 15.8. Scaling changes the meaning of a coordinate difference

Standardization before KNN

StandardScaler centers each numerical feature around its training mean and scales it by its training standard deviation. A difference of one transformed unit therefore represents approximately one training-set standard deviation. Standardization does not make a feature useful, remove outliers, or guarantee a normal distribution; it only places features on comparable statistical scales.

• Fit the scaler on training data only.
• Use the fitted scaler to transform validation, test, and future observations.
• Keep scaling and KNN together in one Pipeline so cross-validation refits preprocessing inside each training fold.
• Consider robust scaling or domain-specific transformations when extreme outliers distort means and standard deviations.

Leakage-safe pipeline

Applying fit_transform to the full dataset before splitting leaks information from the evaluation rows into the scaling statistics. A pipeline prevents this common error because fit is called separately within the appropriate training subset, while predict and score reuse the learned transformation.

A direct comparison: scaled versus unscaled

The following experiment uses the breast cancer dataset because its numerical features have very different ranges. Both models receive the same training and test rows and use the same k. Only the scaling step changes, so the comparison isolates the effect of feature scale.

Categorical, binary, and sparse features

KNN is naturally expressed in a numerical feature space. Nominal categories usually require encoding, but ordinary one-hot encoding plus Euclidean distance can give a categorical mismatch a geometry that may not reflect domain similarity. Mixed numerical and categorical data may require carefully weighted transformations, a suitable metric, or another model family.

Binary indicators already have comparable numerical ranges, but their relative influence still depends on how many indicators exist and how they are weighted. For sparse matrices, centering can destroy sparsity; StandardScaler(with_mean=False) or MaxAbsScaler may be more appropriate. Always test the complete representation, not one preprocessing step in isolation.

Table 15.9. Representation decisions before KNN

15.4 Bias–variance behavior

The value of k controls how much local detail the classifier follows. It therefore acts as a complexity parameter, even though KNN does not fit a traditional parametric equation.

Figure 15.2. The effect of k on model flexibility

Small k: flexible and potentially noisy

With k = 1, every training observation owns a local region and can determine predictions near itself. Training accuracy is often extremely high because each training point is its own nearest neighbor. This low-bias behavior can follow curved boundaries, but it also makes the classifier sensitive to mislabeled points, duplicates, sampling variation, and measurement noise.

Large k: smoother and potentially underfitted

As k increases, a prediction averages labels across a wider region. Local fluctuations matter less, which can reduce variance. If the neighborhood becomes too broad, distinct subgroups are blended together and the global majority class can dominate. Training and validation performance can then both decline, indicating underfitting.

Table 15.10. Interpreting training and validation curves

Generate a validation curve

A validation curve holds the evaluation method constant while varying one hyperparameter. The next example uses stratified five-fold cross-validation. Because k is nested inside a pipeline step named knn, the parameter path is knn__n_neighbors.

How to choose a useful k range

• Start with positive integer values that are smaller than every cross-validation training fold.
• Use a broad coarse range first; then examine a narrower range around promising values.
• Include both odd and even values when the task is multiclass or distance-weighted.
• Compare more than the maximum mean score: inspect variability, class-specific metrics, latency, and stability.
• If several neighboring values perform similarly, prefer a stable region rather than a fragile single peak.

15.5 Advantages and limitations

KNN is valuable because its logic is transparent and flexible. The same properties that make it simple also create memory, latency, dimensionality, and representation challenges.

Advantages

• Simple and intuitive: the prediction can be explained through nearby examples.
• No explicit training equation: there is no assumption of one global linear decision boundary.
• Nonlinear decision boundaries: local neighborhoods can follow complex class shapes.
• Natural multiclass support: the vote can include any number of class labels.
• Few central hyperparameters: k, weights, distance metric, and preprocessing provide a clear experimental starting point.
• Useful benchmark: a scaled KNN model can reveal whether local similarity contains predictive signal.

Limitations

• Sensitive to irrelevant features: every included coordinate can distort distance.
• Sensitive to scale and units: preprocessing is part of the model definition.
• Slow prediction on large datasets: neighbor search is performed for each query.
• Memory intensive: the reference training observations must be retained.
• Affected by high dimensionality: distances become less discriminative as dimensions grow.
• Limited extrapolation: KNN predicts from observed local labels rather than a learned structural law.
• Vulnerable to class imbalance and uneven density: local votes can favor common classes.
• Awkward with mixed or structured inputs: meaningful similarity may require specialized representations.

The curse of dimensionality

Adding features increases the volume of the feature space rapidly. Training observations become sparse, and the nearest point may no longer be meaningfully close. Distances can concentrate so that the closest and farthest observations have similar values. More data, careful feature selection, dimensionality reduction, or a different model family may be necessary.

Table 15.11. Failure signals and responses

When KNN is a sensible candidate

KNN is most attractive when the dataset is small or medium sized, features can be placed in a meaningful numerical space, prediction latency is not extremely constrained, and local similarity is plausible. It is less attractive when the data are enormous, very sparse, very high dimensional, strongly mixed-type, or when a compact equation and fast scoring are essential.

Table 15.12. A quick KNN suitability guide

Practical lab — Study the effect of k

In this lab, students build a scaled KNN classifier for the breast cancer dataset, compare training and validation performance across values of k, investigate distance and weighting choices, select one configuration using validation data, and evaluate it once on an untouched test set.

Lab objectives

• Create reproducible training, validation, and test subsets with stratification.
• Build a StandardScaler–KNN pipeline that prevents preprocessing leakage.
• Record training and validation accuracy for a controlled range of k values.
• Plot the two curves and interpret underfitting and overfitting behavior.
• Compare uniform versus distance weighting and Manhattan versus Euclidean distance.
• Freeze the selected configuration before the final test evaluation.

Dataset and experimental rules

Table 15.13. Practical lab design

Step 1 — Load and inspect the data

The target labels are 0 for malignant and 1 for benign in this dataset. Write the label meaning next to every class-specific metric so that a high recall value cannot be misinterpreted.

Step 2 — Create protected subsets

Step 3 — Audit the split

Step 4 — Sweep candidate values of k

Every candidate uses exactly the same split, scaler, metric, and weighting rule. Only k changes. This controlled design makes the curve interpretable.

Step 5 — Plot the training and validation curves

Questions for the curve

• At which k is training accuracy highest? Why is this expected?
• Which k values produce the strongest validation accuracy?
• Where is the training–validation gap largest?
• At what point do both curves begin to fall, if they do?
• Is the best result a broad plateau or a fragile isolated peak?

Step 6 — Select k without touching the test set

Step 7 — Compare weights and metrics

Use the selected k and vary one additional choice at a time. The test set remains protected. The following four configurations compare equal versus distance weighting and Manhattan versus Euclidean distance.

Step 8 — Freeze and evaluate the final model

Choose the final weights and p from the validation comparison. Then combine training and validation data, refit the complete pipeline, and evaluate once on the test set. The example below assumes the first row of the sorted comparison is selected.

Step 9 — Inspect the actual neighbors

A pipeline transforms the query before the KNN step can measure distance. The following code retrieves the five nearest development observations for one test case and displays their labels. This local evidence can support debugging, but it does not prove causality or clinical relevance.

Expected observations

• Training accuracy is usually greatest for the smallest k values.
• Validation accuracy often improves after moving away from k = 1, then stabilizes or falls.
• Scaling materially changes neighborhoods because the raw feature ranges differ.
• Uniform and distance weighting may rank configurations differently.
• Manhattan and Euclidean distance can produce different local neighborhoods.
• The final test score may be lower than the best validation score because selection favored validation noise.

Lab deliverables

• A reproducible notebook containing all code and outputs.
• A table of k, training accuracy, and validation accuracy.
• One labeled training-versus-validation curve.
• A comparison table for weights and p.
• A final confusion matrix and classification report.
• A 150–250 word interpretation explaining the selected k and the observed bias–variance behavior.

Extension challenges

• Replace the single validation set with StratifiedKFold cross-validation and report mean ± standard deviation.
• Compare the scaled model with an unscaled model using exactly the same data splits.
• Evaluate balanced accuracy, malignant-class recall, and F1 in addition to overall accuracy.
• Add deliberately irrelevant random features and measure how KNN performance changes.
• Time prediction for batches of increasing size and discuss deployment implications.

Common mistakes and corrections

Table 15.14. Frequent KNN errors

Knowledge check

Choose one answer for each question. Complete the questions before consulting the answer key.

1. What does KNN primarily use to classify a new observation?

• A. A fitted linear equation
• B. Labels of nearby training observations
• C. The global target mean
• D. Random class assignment

2. With uniform weights and k = 5, how is the class selected?

• A. The farthest label wins
• B. The class with the most neighbor votes wins
• C. All classes receive equal probability
• D. The smallest numeric label wins

3. Minkowski distance with p = 2 is equivalent to:

• A. Manhattan distance
• B. Cosine similarity
• C. Euclidean distance
• D. Hamming distance

4. Why is scaling especially important for KNN?

• A. KNN requires normal targets
• B. Large-range features can dominate distance
• C. Scaling removes every outlier
• D. It creates more observations

5. What is the safest place for StandardScaler?

• A. Fit on all rows before splitting
• B. Inside a pipeline fitted on training data
• C. After final prediction
• D. Only on the target

6. A very small k usually produces:

• A. Higher bias and lower variance
• B. A more flexible, noise-sensitive boundary
• C. A global constant prediction
• D. Faster fitting of a linear equation

7. A very large k can underfit because:

• A. It ignores too many neighbors
• B. It averages over overly broad regions
• C. It always uses Manhattan distance
• D. It removes scaling

8. weights='distance' means:

• A. Farther neighbors count more
• B. Only one neighbor is used
• C. Closer neighbors have greater influence
• D. Features are standardized automatically

9. Which is a key high-dimensional limitation?

• A. Distances can become less discriminative
• B. KNN becomes a linear model
• C. The target becomes continuous
• D. Training labels disappear

10. When should the final test set be used?

• A. To select k repeatedly
• B. To choose scaling after inspecting results
• C. Once after the recipe is frozen
• D. Before training data are created

Answer key and explanations

Table 15.15. Knowledge-check solutions

Score interpretation

• 9–10 correct: ready to build and evaluate a leakage-safe KNN classifier.
• 7–8 correct: solid understanding; revisit scaling or bias–variance behavior where needed.
• 5–6 correct: repeat the manual distance example and the k-curve lab.
• 0–4 correct: review the prediction sequence and parameter table before continuing.

Chapter summary

• KNN predicts from the labels of nearby training observations in a defined feature space.
• Distance, representation, and scale determine which observations are considered similar.
• Uniform weights give equal votes; distance weights give closer neighbors more influence.
• Minkowski p = 1 gives Manhattan distance and p = 2 gives Euclidean distance.
• Standardization should be fitted on training data inside a pipeline to prevent leakage.
• Small k creates flexible, high-variance behavior; large k creates smoother, higher-bias behavior.
• Validation curves reveal the relationship between k, training fit, and generalization.
• KNN is intuitive and nonlinear but can be slow, memory intensive, scale sensitive, and weak in high dimensions.
• The final model must be selected without using the protected test set.

Key vocabulary

Table 15.16. Essential terminology

Further reading

• scikit-learn: KNeighborsClassifier
• scikit-learn user guide: nearest neighbors
• scikit-learn: StandardScaler
• scikit-learn: Pipeline
• scikit-learn: validation_curve

What’s next?

The next chapter studies decision tree classification. Unlike KNN, a tree learns an explicit hierarchy of feature-based rules during training and usually predicts quickly without scaling. Comparing the two models reveals how algorithm assumptions, preprocessing needs, interpretability, and computational cost shape model selection.