K-Nearest Neighbors Classification

This section introduces the simplest classifier of the course: k-nearest neighbors (KNN). To classify a new sample, KNN looks at the training samples closest to it and lets them vote. You will first run the method by hand on nine real iris flowers, then build, score and tune KNN models in scikit-learn with the two notebooks of week 5.

Objectives

By the end of the section you should be able to:

• Explain how KNN predicts a class: a distance, the K nearest training rows, and a majority vote.
• Compute Euclidean distances and a KNN prediction by hand for K = 1, 3 and 5.
• Scale features with StandardScaler and explain why a distance-based model needs it.
• Fit KNeighborsClassifier, then read a confusion matrix, the accuracy, the precision and the recall.
• Choose K with the elbow method.
• Build and use a KNN model on the iris dataset, and apply the same steps to your team project.

Where this sits in the course

Week 5 of the plan has three parts:

• Two notebooks. KNN_Classification works on a dataset of 1000 rows with 10 anonymous features and a 0 or 1 label. Nearest Neighbors works on the iris flowers.
• A real-world scenario. Build a simple supervised-learning model using the famous iris dataset, which contains 150 samples describing measurements for three species of iris.
• A project milestone. Machine Learning Model Implementation: this week your team implements a first model on its own data.

In weeks 3 and 4 you split data, fitted a regression model and a logistic regression model, and scored them. KNN reuses exactly the same fit, predict and score pattern, so the new part is the idea inside the model.

Part 1: The idea of KNN

What k-nearest neighbors is

K-nearest neighbors is a simple supervised-learning algorithm that predicts an outcome by identifying the data points closest in proximity to the input data. In one sentence: to classify a new sample, find the K training samples nearest to it and let them vote; the most common class among them is the prediction.

The vocabulary, on iris

The algorithm in four steps

1. Store the training rows and their labels. This is all fit needs to do.
2. Compute the distance from the query to every training row.
3. Sort the distances and keep the K smallest.
4. Count the labels of those K rows. The majority is the prediction.

Linear and logistic regression learn weights during fit. KNN learns no equation: it keeps the data itself and does its work at prediction time, when it measures distances.

Measuring closeness: Euclidean distance

For a training row x and a query q, both with n features:

d = square root of ( (x1 - q1)^2 + (x2 - q2)^2 + ... + (xn - qn)^2 )

Subtract feature by feature, square each difference, add them up, and take the square root. Because the square root never changes the order of two distances, you can rank the rows by the squared distance and take the root only at the end. That is what we do by hand.

When scikit-learn prints a fitted model, it shows metric='minkowski' with p=2. That combination is exactly the Euclidean distance above.

Worked example: one new flower, by hand

We take nine real flowers from the iris dataset and use only two features, petal length and petal width in cm. The new flower measures (4.7, 1.7). We predict its species with K = 1, K = 3 and K = 5.

Step 1: squared distances

For each flower, subtract the query from the flower, square both differences and add them. A negative difference squares to a positive number, for example (-0.2)^2 = 0.04.

F1, the setosa, is far away (squared distance 13.14), so it will never be one of the few nearest neighbours.

Step 2: sort and take the roots

F4 and F9 tie at a squared distance of 0.17; that does not matter here, because they are ranks 7 and 8 and we never look past rank 5.

Step 3: vote

• K = 1: only F2 votes. 1 versicolor, so the prediction is versicolor.
• K = 3: F2, F7 and F6 vote. 2 virginica, 1 versicolor, so the prediction is virginica. F2 is outvoted by the two virginica flowers.
• K = 5: F5 and F3 join. 3 versicolor, 2 virginica, so the prediction is versicolor.

The same flower received three different answers as K grew. K is a setting that changes the model's behaviour, and Part 3 shows how the notebook chooses it.

To see the example move, open the KNN playground on the nine flowers full screen. Drag the new flower, change K, and press Play or Step to reveal the neighbours one at a time.

K is a choice, and ties happen

• K is not learned from the data. You choose it, and then you check the choice on test data.
• A small K follows the single closest row, even when that row is unusual.
• A larger K listens to more rows, so one odd row matters less.
• With an even K a vote can tie, for example 1 to 1 with K = 2.

When a vote ties, scikit-learn gives the prediction to the class with the smaller number (for iris, versicolor 1 beats virginica 2). With two classes, an odd K can never tie.

Part 2: Notebook 1, the Classified Data

Open the notebook

Open KNN_Classification in Colab

The first cell reads the data from a file called Classified Data in the notebook's own folder. That file is not there when the notebook opens in Colab: in the repository it lives in the Datasets folder. Read it from the repository instead:

import pandas as pd
import numpy as np
import seaborn as sns
import matplotlib.pyplot as plt
 
url = ("https://raw.githubusercontent.com/"
       "tirthajyoti/Machine-Learning-with-Python/"
       "master/Datasets/Classified%20Data")
df = pd.read_csv(url, index_col=0)
df.head()

Load and inspect the data

df.info() reports 1000 rows and 11 columns: 10 feature columns with made-up names (WTT, PTI, EQW, and so on) and one label column, TARGET CLASS, with the values 0 and 1. The classes are balanced: 500 rows of each.

The notebook then draws one boxplot per feature, split by TARGET CLASS, to see which features take different values in the two classes:

l = list(df.columns)
for i in range(len(l) - 1):
    sns.boxplot(x='TARGET CLASS', y=l[i], data=df)
    plt.figure()

Why KNN needs scaled features

The distance adds the squared differences of all features. A feature measured on a bigger scale adds bigger numbers, so it decides on its own which rows count as near. StandardScaler rescales every feature to mean 0 and standard deviation 1, so each feature gets a fair say:

z = (x - mean) / standard deviation

The scaler is fitted on the features only, df.drop('TARGET CLASS', axis=1). The label is never scaled.

Worked example: scale one value

Row 0 of WTT is x = 0.913917. Over the 1000 rows, the mean of WTT is 0.949682 and its standard deviation is 0.289490.

z = (0.913917 - 0.949682) / 0.289490 = -0.12354 (rounded)

The value is a little below the mean, so z is slightly negative. df_feat.head() in the notebook shows -0.123542 in this cell, the same value computed without rounding the inputs.

df.describe() prints a slightly different standard deviation for WTT, 0.289635, because describe() divides by n minus 1 while StandardScaler divides by n. With the describe() value you would get -0.123480, which does not match the notebook.

Scale, split, fit and predict

from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
scaler.fit(df.drop('TARGET CLASS', axis=1))
scaled_features = scaler.transform(df.drop('TARGET CLASS', axis=1))
 
df_feat = pd.DataFrame(scaled_features, columns=df.columns[:-1])
 
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(
    scaled_features, df['TARGET CLASS'], test_size=0.50, random_state=101)
 
from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors=1)
knn.fit(X_train, y_train)
pred = knn.predict(X_test)

fit learns each column's mean and standard deviation, and transform applies the formula to every value. test_size=0.50 splits the rows into 500 for training and 500 for testing, and random_state=101 makes the split the same every time you run it.

Worked example: evaluate the K = 1 model

print(confusion_matrix(y_test, pred)) prints:

Rows are the true class and columns the prediction, so the diagonal holds the correct predictions and the other two cells the mistakes.

• Wrong predictions: 17 + 24 = 41. Right ones: 233 + 226 = 459.
• Accuracy: (233 + 226) / 500 = 0.918.
• Error rate: (17 + 24) / 500 = 0.082. The notebook prints the same number with np.mean(pred != y_test), the misclassification error rate.

classification_report(y_test, pred) adds two measures per class:

• Precision of a class: of the rows predicted as that class, the share that really are. For class 0: 233 / (233 + 24) = 0.907.
• Recall of a class: of the rows that really are that class, the share the model found. For class 0: 233 / (233 + 17) = 0.932.

The report rounds these to two decimals:

              precision    recall  f1-score   support
 
           0       0.91      0.93      0.92       250
           1       0.93      0.90      0.92       250
 
    accuracy                           0.92       500
   macro avg       0.92      0.92      0.92       500
weighted avg       0.92      0.92      0.92       500

Class 1 works the same way: precision 226 / (226 + 17) = 0.930 and recall 226 / (226 + 24) = 0.904. The notebook's saved output shows an older layout of the same report, with a final avg / total row; current versions of scikit-learn print the accuracy, macro avg and weighted avg rows shown here.

Part 3: Choosing K with the elbow method

The notebook trains one model for every K from 1 to 59 on the same split, and records each test error rate:

error_rate = []
 
for i in range(1, 60):
    knn = KNeighborsClassifier(n_neighbors=i)
    knn.fit(X_train, y_train)
    pred_i = knn.predict(X_test)
    error_rate.append(np.mean(pred_i != y_test))
 
plt.figure(figsize=(10, 6))
plt.plot(range(1, 60), error_rate, color='blue', linestyle='dashed', marker='o',
         markerfacecolor='red', markersize=8)
plt.title('Error Rate vs. K Value', fontsize=20)
plt.xlabel('K', fontsize=15)
plt.ylabel('Error (misclassification) Rate', fontsize=15)

The first twenty values of the loop:

How to read the curve:

• The error falls from 0.082 at K = 1 to 0.048 by K = 11. After that the curve is flat: every value from K = 12 to 59 lies between 0.046 and 0.056.
• The bend where the fast fall turns into the flat part is the elbow. Past it, a bigger K buys almost nothing and every prediction must compute more distances.
• The lowest error, 0.046, appears at K = 24, 38 and 40. A difference of 0.002 is a single test row out of 500, so do not crown a K on differences that small.
• K = 2 is worse than K = 1 (0.094 against 0.082). In 55 of the 500 test rows the two nearest neighbours disagree, the vote ties 1 to 1, and scikit-learn gives every such tie to class 0.

Open the elbow loop widget full screen to replay the loop one K at a time and see the confusion matrix behind every point.

Part 4: Notebook 2, the iris flowers

Load iris into a DataFrame

import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
 
from sklearn.datasets import load_iris
 
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['class'] = iris.target
df['class name'] = iris.target_names[iris['target']]
df.head()
 
sns.pairplot(df)

The dataset ships with scikit-learn, so nothing is downloaded. It holds 150 flowers, 50 of each species, and four features in cm. The pair plot draws every pair of features against each other. In the petal length and petal width panels setosa forms a group far from the other two species, while versicolor and virginica sit next to each other and overlap slightly, which is where KNN can make mistakes.

Split, train and score

from sklearn.model_selection import train_test_split
 
x_train, x_test, y_train, y_test = train_test_split(
    iris.data, iris.target, test_size=0.2, random_state=0)
 
from sklearn.neighbors import KNeighborsClassifier
 
model = KNeighborsClassifier()
model.fit(x_train, y_train)
model.score(x_test, y_test)

• test_size=0.2 keeps 30 of the 150 flowers for testing and trains on 120.
• No n_neighbors is given, so the default K = 5 is used.
• model.score returns the accuracy on the test set: 0.9667, which is 29 of 30 test flowers correct.

Predict a flower the model has never seen

predicted_class = model.predict([[5.6, 4.4, 1.2, 0.4]])
print(predicted_class)
print(iris.target_names[predicted_class[0]])

The output is [0] and then setosa. Note the two pairs of brackets: predict expects a table of rows, even for a single flower.

model.kneighbors([[5.6, 4.4, 1.2, 0.4]]) shows why. It returns the five nearest training flowers and their distances:

For the nearest one: (5.6 - 5.7)^2 + (4.4 - 4.4)^2 + (1.2 - 1.5)^2 + (0.4 - 0.4)^2 = 0.01 + 0 + 0.09 + 0 = 0.1, and the square root of 0.1 is 0.3162. All five neighbours are setosa, so the vote is 5 to 0.

Where the iris model goes wrong

confusion_matrix(y_test, model.predict(x_test)) for the same model:

The single mistake is a versicolor predicted as virginica: those are the two species that overlap in the petal plane.

With only 30 test flowers, one flower is 1/30 = 0.0333 of the score. On this split K = 1 scores 1.0 and K = 5 scores 0.9667; that is one flower, not a real difference between the two settings.

Open the KNN playground on all 150 flowers full screen and switch on the decision regions to see how the plane is divided for each K.

Common mistakes

• Forgetting to scale the features before a distance-based model.
• Passing one flat list to predict. It needs a list of rows: [[5.6, 4.4, 1.2, 0.4]].
• Reading Classified Data in Colab from a folder that does not contain it.
• Judging the model on the training rows instead of the test rows.
• Crowning a K because of a difference of one or two test rows.
• Using an even K with two classes and getting ties.

Project milestone: model implementation

This week's milestone is to implement a machine learning model on your team's project data. With KNN:

1. Take the features and the target you chose in week 4.
2. Scale the features, then split into a training set and a test set.
3. Fit KNeighborsClassifier and predict the test set.
4. Report the confusion matrix and classification_report.
5. Run the elbow loop, pick K, and write down why you picked it.

Keep the error rates and your chosen K. Next week the milestone continues with decision trees and random forests.

Key takeaways

1. KNN predicts by a majority vote of the K training rows closest to the query.
2. Closeness is the Euclidean distance, so the features must be on the same scale.
3. The same query can change class as K changes: K is a setting you choose.
4. Judge a model on test data with the confusion matrix, the accuracy, the precision and the recall.
5. Pick K with the elbow method, and do not chase differences of one or two test rows.

Practice

About 30 minutes. Try each task before you read its answer at the end of the page.

Practice 1: a second new flower (about 10 minutes)

Use the same nine flowers F1 to F9 from the worked example (petal length, petal width). The new flower is (5.1, 1.75).

1. Compute the squared distance from the new flower to every one of the nine flowers.
2. Rank the flowers from nearest to farthest.
3. Predict the species with K = 1, K = 3 and K = 5.

Hint: the differences now end in 5, for example 0.05^2 = 0.0025 and 0.15^2 = 0.0225.

Practice 2: read a confusion matrix (about 5 minutes)

Notebook 1 with n_neighbors=20 gives this confusion matrix on the 500 test rows:

Compute the accuracy, the error rate, and the precision and recall of class 1.

Practice 3: standardize by hand (about 5 minutes)

One feature takes the five values 4, 6, 8, 10, 12. Compute the mean, the standard deviation (divide by n, as StandardScaler does), and the five z values.

Practice 4: in Colab, on iris (about 10 minutes)

1. Run notebook 2 up to model.score(x_test, y_test).
2. Predict the flower [[6.0, 2.9, 4.5, 1.5]] and print its species name.
3. Call model.kneighbors on it. How did its five neighbours vote?
4. Loop K from 1 to 15 on the same split and print the score of each model. Reuse the elbow loop from notebook 1 with x_train, y_train, x_test, y_test and model.score.

Answers

Answer 1

Differences are flower minus query.

Ranking:

Votes:

• K = 1: 1 virginica, so virginica.
• K = 3: 2 versicolor, 1 virginica, so versicolor. F3 and F4 outvote F9.
• K = 5: 3 virginica, 2 versicolor, so virginica. F6 and F8 swing it back.

Again the answer changes with K.

Answer 2

• Accuracy: (238 + 238) / 500 = 0.952.
• Error rate: (12 + 12) / 500 = 0.048, the value the elbow loop records for K = 20.
• Precision of class 1: 238 / (238 + 12) = 0.952.
• Recall of class 1: 238 / (238 + 12) = 0.952.

Answer 3

• Mean: (4 + 6 + 8 + 10 + 12) / 5 = 8.
• Squared differences from the mean: 16, 4, 0, 4, 16, which add up to 40.
• Standard deviation: square root of (40 / 5) = square root of 8 = 2.8284.
• z values: -1.4142, -0.7071, 0, 0.7071, 1.4142.

Check: the z values add up to 0, and the value equal to the mean gets z = 0.

Answer 4

• model.predict([[6.0, 2.9, 4.5, 1.5]]) returns [1], and iris.target_names[1] is versicolor.
• The five neighbours returned by model.kneighbors:

The vote is 4 versicolor, 1 virginica, so versicolor wins.

• The scores for K = 1 to 15 on the same split:

Every score is either 1.0000 (all 30 test flowers correct) or 0.9667 (29 of 30). The test set is too small to tell these values of K apart.