Nearest Neighbor Classification

The k-nearest neighbors classification algorithm predicts a new data point by considering its closest neighbor(s) in the training set, and it is implemented in the KNeighborsClassifier class.

Programming

Interactive lab

Try it: k-Nearest Neighbours

How a k-nearest-neighbours classifier labels a new point: measure its distance to every known point, take the K closest, and let them vote.

How it works

Measure the straight-line (Euclidean) distance from the new point to every labelled point.
Rank the points from nearest to farthest.
Keep the K nearest.
Count how many of them belong to each class; the class with the most votes is the prediction (a tie goes to the class of the nearest tied neighbour).

Default run (15 steps): 10 labelled points and a new query point at (5, 3.5). K = 3. … Prediction: class A — A has the most votes.

Simplified: Small 2-D educational dataset (at most 30 points, three classes). Real KNN uses many features and usually scales them first.

Educational simulation

Loading the simulation…

Starting From a Working Program

This article starts with a program rather than a definition. A k-nearest neighbors classifier is built from a training set, asked to predict labels for new data, and then scored on a separate test set. The program below is a generated illustration of that workflow using scikit-learn and the iris dataset. Read it line by line before moving on, and notice the single number it prints at the end. The rest of the article explains where that number comes from.

python

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

iris_dataset = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
    iris_dataset.data, iris_dataset.target, random_state=0)

knn = KNeighborsClassifier(n_neighbors=1)
knn.fit(X_train, y_train)
print("Test set score: {:.2f}".format(knn.score(X_test, y_test)))

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

iris_dataset = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
    iris_dataset.data, iris_dataset.target, random_state=0)

knn = KNeighborsClassifier(n_neighbors=1)
knn.fit(X_train, y_train)
print("Test set score: {:.2f}".format(knn.score(X_test, y_test)))

Notes on the code

train_test_split divides the data into a training part and a test part
n_neighbors=1 tells the classifier to consider one neighbor
fit builds the model from training inputs and training labels
score measures accuracy on the test inputs and test labels

What do you think happens?

Before reading on: which two variables should the score method receive in the last line, and why?

Reveal answer

Answer:

It should receive X_test and y_test, the held-out test inputs and their true labels.

The test set holds examples kept apart from the training step, so the score reflects how the model handles data it did not learn from. Passing the training data instead would measure accuracy on data the model was built from.

The Face Recognition Question

The problem in this article is face recognition in its simplest form. Given a face that the system has not seen before, decide whether that face belongs to someone in a database of known people. Every number produced by the pipeline later in this article is an attempt to answer that one question.

The dataset is the Labeled Faces in the Wild collection, which holds face images of celebrities downloaded from the Internet, including politicians, singers, actors, and athletes from the early 2000s. The grayscale versions are scaled down for faster processing. The full collection contains 3,023 images, each 87 by 65 pixels, spread across 62 people. The collection is skewed: a large share of the images show two people, George W. Bush and Colin Powell.

A skewed dataset would let the most frequent people dominate any learned representation. To reduce that effect, the pipeline keeps at most 50 images for each person. Pixel values are then divided by 255 so they fall between 0 and 1, which the source describes as better numeric stability. Both steps change the data the classifier sees, so they are part of the pipeline and not a cosmetic detail.

Why Raw Pixels Make a Weak Comparison

Each image is a grid of grayscale pixel values. The simplest way to compare two faces is to compare the value of each pixel with the value at the same position in the other image. This is a direct, literal comparison, and it is easy to code. The trouble is that it does not match how a person would judge two faces. A face shifted one pixel to the right is, to a person, the same face, but under pixel-by-pixel comparison it becomes a substantially different representation.

Definition

Feature extraction is the search for a different representation of the data, one in which distances between items are more meaningful for the task, instead of accepting the representation you were given. Principal component analysis, or PCA, is one way to construct such a representation.

The rest of the article tests whether PCA actually helps for faces. The answer depends on measuring it, which is why the pipeline is built in stages that can each be checked.

Tracing the Shapes Through the Pipeline

The easiest way to debug this pipeline is to treat every stage as a transformation with a known input and output shape. Start with the raw training data. The training set contains 1,537 images, and each image is a row of pixel values. Since each image is 87 by 65 pixels, each row holds 5,655 values. The raw training data therefore has the shape 1,537 rows by 5,655 columns.

What is the shape of the data after each stage, and at which stage does the result differ from expectation?

Notice the stage where the shape changes most. PCA with 100 components turns each row of 5,655 pixel values into 100 numbers. The classifier then compares these 100-number rows instead of the original full-size rows. When a result looks wrong, the first question to ask is whether the shape at that stage matches what the stage is supposed to produce. A row count that does not match the number of training images, or a column count that is still 5,655 after PCA, is a signal to look at that stage first.

The pipeline is set up so that the PCA object is fitted on the training data only. It keeps the first 100 principal components and has whitening turned on. Both the training and test sets are then transformed using that fitted object, and the classifier is trained on the transformed training features and scored on the transformed test features.

What Whitening Changes

Whitening deserves its own explanation. Rotation alone changes the orientation of the data but leaves it stretched, so a cloud of points that is wide in one direction and narrow in another stays elliptical. Whitening also rescales each principal component so that all of them have the same scale. The source illustrates this by describing a centered panel becoming a circle rather than an ellipse.

How a One-Nearest-Neighbor Lookup Decides

The word neighbors in the name refers to the training points that are closest to the new point. The parameter n_neighbors=1 tells the classifier to consider one neighbor. With one neighbor, the prediction for a new face is the label of the single closest training face. The source does not describe other values of this parameter, so this article makes no claim about them. What the source does establish is the class structure: the KNeighborsClassifier class contains one piece of logic that builds the model and another that makes a prediction using the model.

After the new point is placed in feature space, which training point is selected as its nearest neighbor, and how does its label become the prediction?

Now apply this to the pipeline. The one-nearest-neighbor classifier using raw pixel values reached 26.6 percent accuracy. After the PCA with whitening transformation, the same kind of classifier reached 35.7 percent. The source treats this as a meaningful gain, though still well short of reliable recognition. It uses the result to confirm an intuition: the principal components provide a better representation for this task than the raw pixels do.

Watch for the number format when you read printed output. The printed lines show two-decimal scores such as 0.27 and 0.36. These are the same numbers as 26.6 and 35.7 percent, rounded and expressed as fractions. When two sources of numbers appear to disagree, check whether one is a percentage, a fraction, or a rounded value before concluding that a result is wrong.

Principal Components as Images

A principal component is a direction in the input space, chosen to capture as much variance in the data as possible. For image data, a direction in the input space has the same shape as an image. Each principal component can therefore be displayed as a picture. This is what makes PCA on faces unusually easy to inspect: you can look at what each component looks like instead of only reading numbers.

The source offers an informal reading of the first components. The first seems to encode mostly the contrast between the face and the background, and the second seems to encode lighting differences between the left and right halves of the face. The source is careful to call these guesses. It also points out that the components capture aspects tied to pixel alignment and lighting, which a human rater would not weigh first when judging similarity.

PCA also runs in reverse. After reducing a face to a set of coefficients, you can rotate back into the original pixel space using inverse_transform. Reconstructions made from only the first few components show a blurred impression of the face, and reconstructions made from more components recover finer detail. The source compares reconstructions using 10, 50, 100, 500, and 2,000 components. With only 10 components, the essence of the picture, such as orientation and lighting, is captured. Using as many components as there are pixels would discard nothing and reconstruct the image exactly, which is a useful reference point for judging how much information a chosen number of components has thrown away.

Before

# coarse summary: few components kept
few_components = 10
# orientation and lighting survive

A face rebuilt from 10 components shows the overall pose and lighting but little detail.

After

# fine detail: many components kept
many_components = 2000
# reconstruction approaches the original image

A face rebuilt from many components recovers finer detail, and using every pixel reproduces the image exactly.

The reconstruction view explains why the classifier's inputs matter. If only coarse information survives into the 100 components, the classifier is working from a summary of each face rather than its fine detail. Projecting the faces onto only the first two components produces a single mixed cloud with no visible separation between people. Even with 10 components, PCA captures only rough characteristics of faces, so two components carry far too little information to separate identities.

The fit and score Interface

The model is built by calling fit with training data and training outputs. The score method then computes accuracy on test set data and test set labels. The fit, predict, and score methods form the common interface to supervised models in scikit-learn, so once you know this pattern, the same core workflow applies to many machine learning tasks.

What data does fit receive and what state does it store, and how does score compute accuracy on the test set without retraining?

Method	What it receives	What it does, according to the source
fit	Training inputs and training outputs	Builds the model from input/output pairs in the training set
predict	New input data	Part of the common interface; uses the built model to make predictions
score	Test set data and test set labels	Computes accuracy on that test set using the existing model

The common scikit-learn interface for supervised models, as described in the source

Supervised learning is used whenever you want to predict an outcome from a given input and you have examples of input and output pairs. The model is built from these pairs, which make up the training set. The goal, however, is accurate predictions for new, never-before-seen data. The test set plays that role: it holds examples kept apart from the training step, so the score reflects how the model handles data it did not learn from. The source uses classifying iris flowers into species from physical measurements as its real application, and the source's own run of KNeighborsClassifier(n_neighbors=1) reported a test set score of 0.97, meaning the model was correct 97 percent of the time on the test set.

Where the Iris Workflow Diverges

Now trace the workflow and look for the stage where a result departs from what you expect. Suppose the final line is changed from scoring the test set to scoring the training set. Everything before that line stays the same: the data is split, and fit runs on the training data exactly as before. Only the evaluated data changes.

Before

print(knn.score(X_test, y_test))

Accuracy is measured on held-out test data that the model never learned from.

After

print(knn.score(X_train, y_train))

Accuracy is measured on data the model was built from, so the printed value is not comparable to the test score.

Debugging

The divergence occurs on the last line, in the score call, and not in the fit call. The original program passes X_test and y_test, so accuracy is measured on the test set. The changed version passes X_train and y_train, so accuracy is measured on the data the model was built from. The source does not give a value for that case, so the new printed number cannot be predicted from the source alone. What can be stated with confidence is that the evaluated data changed, which is why the printed value is not expected to match the test set score of 0.97 reported in the source's example.

Mistakes That Hide Pipeline Errors

Common mistake
Scoring on the training data and reporting that as the result
What it looks like
```
knn.score(X_train, y_train) printed as the model's accuracy
```
Why it fails
The model was built from these examples, so the score does not show how it handles data it did not learn from.
Do this instead
Score on the held-out test set with score(X_test, y_test).
Common mistake
Fitting PCA on the full dataset or on the test set
Why it fails
The source's pipeline fits the PCA object on the training data only, then transforms both sets with that fitted object.
Do this instead
Fit the transformer on training data, then transform the training and test sets with it.
Common mistake
Trusting a description over the printed shape
What it looks like
Believing the components are 50 by 37 pixels because the prose says so
Why it fails
The printed shape is (100, 5655), which matches 87 times 65 pixels.
Do this instead
Compare the printed shape at each stage against the expected shape, and investigate any mismatch.
Common mistake
Reading 0.36 as an error when the source reports 35.7 percent
Common mistake
Assuming two components are enough to separate identities

Practice Tracing a Workflow

MEDIUM

Using the iris program at the start of this article, predict what changes if n_neighbors is left at 1 but the fit call is removed. Then explain which method would fail first and why, using the roles of fit and score described in this article.

Hints

Ask what fit stores, and what score needs before it can compute accuracy.
Trace the call order: fit must come before score for the model to exist.

Your attempt (not saved)

EASY

A colleague reports that the 1-NN pipeline reached 0.36, but the article says 35.7 percent. Explain whether this is a contradiction, and name the stage you would check first if the printed shape of the transformed training data were 1,537 by 5,655.