4.2 - K-Nearest Neighbors (KNN) for emergency triage

In chapter 4 the Minermont team wants a system that suggests the urgency level of each patient arriving at the emergency department, from 1 (red, immediate) to 5 (blue, non-urgent). It is a multiclass classification problem: the model does not answer yes or no, it chooses one of five classes.

The first algorithm they study at AIA is K-Nearest Neighbors (KNN). It builds no explicit model: it memorizes the training cases and, to classify a new patient, it looks for the $K$ most similar ones and gives the new patient the most frequent level among them. In this notebook:

1. Import the libraries.
2. KNN by hand, on a small example.
3. Distance metrics: Euclidean, Manhattan and Chebyshev.
4. The triage data.
5. Feature scaling.
6. Choosing $K$ and the metric with cross-validation.
7. The curse of dimensionality.
8. Final evaluation on the test set.

Step 1: Import the libraries

---

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split, StratifiedKFold, cross_val_score
from sklearn.preprocessing import StandardScaler, MinMaxScaler, RobustScaler
from sklearn.pipeline import make_pipeline
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report, ConfusionMatrixDisplay

Step 2: KNN by hand

---

We start, as the book does, with two groups of points described by two features, and a new point to classify. The algorithm has four steps:

1. Choose $K$, the number of neighbors.
2. Compute the distance from the new point to every training point.
3. Take the $K$ points with the smallest distance.
4. Assign the most frequent class among them (majority vote).

X_toy = np.array([[3.0, 1.8], [2.05, 2.05], [1.7, 3.0], [1.0, 1.0], [1.5, 0.8], [0.8, 1.8], [1.8, 1.2], [1.2, 2.5],
                  [3.9, 3.9], [4.25, 3.0], [5.0, 5.0], [4.6, 5.4], [5.5, 4.4], [5.2, 3.8], [4.4, 4.8], [5.8, 5.2]])
y_toy = np.array(['A'] * 8 + ['B'] * 8)
new_point = np.array([3.0, 3.0])

def euclidean(a, b):
    return np.sqrt(np.sum((a - b) ** 2, axis=-1))

def knn_predict(X_train, y_train, x_new, k=3, distance=euclidean):
    distances = distance(X_train, x_new)                   # step 2
    nearest = np.argsort(distances)[:k]                    # step 3
    classes, votes = np.unique(y_train[nearest], return_counts=True)
    return classes[np.argmax(votes)], nearest              # step 4

prediction, nearest = knn_predict(X_toy, y_toy, new_point, k=3)
for i in nearest:
    print(f"Neighbor {X_toy[i]}  class {y_toy[i]}  distance {euclidean(X_toy[i], new_point):.3f}")
print(f"\nPrediction for {new_point}: class {prediction}")

plt.figure(figsize=(5.5, 5))
for label, color, marker in [('A', 'tab:blue', 'o'), ('B', 'tab:red', 's')]:
    plt.scatter(*X_toy[y_toy == label].T, color=color, marker=marker, s=60, label=f'class {label}')
plt.scatter(*X_toy[nearest].T, s=260, facecolors='none', edgecolors='k', label='3 nearest neighbors')
plt.scatter(*new_point, marker='*', s=350, color='gold', edgecolors='k', zorder=3, label='new point')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend(loc='upper left')
plt.grid(True)
plt.show()

Neighbor [3.  1.8]  class A  distance 1.200
Neighbor [4.25 3.  ]  class B  distance 1.250
Neighbor [3.9 3.9]  class B  distance 1.273

Prediction for [3. 3.]: class B

Two of the three nearest neighbors belong to class B, so the new point is classified as B, even though the single closest point is of class A. With $K = 1$ the answer would have been A: the value of $K$ matters.

Step 3: Distance metrics

---

What does "near" mean? The book presents three common metrics. If $x_q$ is the new point and $x_i$ a training point, both with $d$ features:

• Euclidean, the straight-line distance: $d(x_q, x_i) = \sqrt{\sum_{j=1}^{d} (x_{q,j} - x_{i,j})^2}$
• Manhattan, moving only along the axes, as on a grid of streets: $d(x_q, x_i) = \sum_{j=1}^{d} |x_{q,j} - x_{i,j}|$
• Chebyshev, only the largest difference in any single feature: $d(x_q, x_i) = \max_{j} |x_{q,j} - x_{i,j}|$

Martha visualizes them with the unit ball: all the points at distance 1 from the origin according to each metric.

def manhattan(a, b):
    return np.sum(np.abs(a - b), axis=-1)

def chebyshev(a, b):
    return np.max(np.abs(a - b), axis=-1)

t = np.linspace(0, 2 * np.pi, 400)
circle = np.c_[np.cos(t), np.sin(t)]
plt.figure(figsize=(5, 5))
for metric, color, name in [(euclidean, 'tab:blue', 'Euclidean'), (manhattan, 'tab:green', 'Manhattan'), (chebyshev, 'tab:red', 'Chebyshev')]:
    ball = circle / metric(circle, np.zeros(2))[:, None]      # rescale each direction to distance 1
    plt.plot(*ball.T, color=color, label=name)
plt.gca().set_aspect('equal')
plt.axhline(0, color='gray', linewidth=0.5)
plt.axvline(0, color='gray', linewidth=0.5)
plt.title('Unit balls: points at distance 1 from the origin')
plt.legend()
plt.show()

The circle, the diamond and the square contain different points, so each metric can choose different neighbors. Let's classify the same new point with each one:

fig, axes = plt.subplots(1, 3, figsize=(15, 4.8))
for metric, ax, name in zip([euclidean, manhattan, chebyshev], axes, ['Euclidean', 'Manhattan', 'Chebyshev']):
    prediction, nearest = knn_predict(X_toy, y_toy, new_point, k=3, distance=metric)
    print(f"{name:<10} neighbors {[tuple(p) for p in X_toy[nearest].tolist()]} -> class {prediction}")
    for label, color, marker in [('A', 'tab:blue', 'o'), ('B', 'tab:red', 's')]:
        ax.scatter(*X_toy[y_toy == label].T, color=color, marker=marker, s=60)
    ax.scatter(*X_toy[nearest].T, s=260, facecolors='none', edgecolors='k')
    ax.scatter(*new_point, marker='*', s=350, color='gold', edgecolors='k', zorder=3)
    radius = metric(X_toy[nearest[-1]], new_point)             # distance to the third neighbor
    ball = new_point + radius * circle / metric(circle, np.zeros(2))[:, None]
    ax.plot(*ball.T, 'k--', linewidth=1)
    ax.set_aspect('equal')
    ax.set_title(f'{name}: class {prediction}')
plt.show()

Euclidean  neighbors [(3.0, 1.8), (4.25, 3.0), (3.9, 3.9)] -> class B
Manhattan  neighbors [(3.0, 1.8), (4.25, 3.0), (1.7, 3.0)] -> class A
Chebyshev  neighbors [(3.9, 3.9), (2.05, 2.05), (3.0, 1.8)] -> class A

With the Euclidean distance the new point is B; with the Manhattan and Chebyshev distances it is A, and each metric has chosen a different set of neighbors. The Manhattan diamond reaches further along the axes and picks up the point (1.7, 3.0); the Chebyshev square reaches further along the diagonals and picks up (2.05, 2.05). As Martha says in the book, choosing the metric means choosing what "similar" means.

Step 4: The triage data

---

The emergency records of a real hospital are confidential, so we generate synthetic patients that behave like the ones in the book. The next cell contains the generator. You do not need to follow it line by line: what matters is that the urgency level comes from a hidden protocol (an early-warning score based on the vital signs, plus some clinical warning signs) and from the nurse's own judgement, which sometimes moves the level one step. The models never see that rule: they have to discover it from the examples.

Column	Meaning
age	Age in years (1–97; about one patient in eight is a child)
male	1 if the patient is a man, 0 if a woman
systolic_bp	Systolic blood pressure (mmHg)
heart_rate	Heart rate (beats per minute)
resp_rate	Respiratory rate (breaths per minute)
spo2	Oxygen saturation (%)
temperature	Temperature (°C)
consciousness	Level of consciousness: 0 alert, 1 responds to voice, 2 responds only to pain, 3 unresponsive
pain	Pain reported by the patient (0–10)
chest_pain, dyspnea, trauma, vomiting	Presenting symptoms: chest pain, difficulty breathing, injury, vomiting (1 = yes)
level	Target: urgency level, from 1 (red, immediate) to 5 (blue, non-urgent)

def generate_patients(n, seed):
    """Synthetic emergency patients at Minermont: one row per patient, with the urgency level assigned at triage."""
    rng = np.random.default_rng(seed)
    age = np.clip(np.round(np.where(rng.random(n) < 0.12, rng.uniform(1, 17, n), rng.normal(52, 20, n))), 1, 97)
    male = rng.binomial(1, 0.5, n)
    s = rng.gamma(0.9, 0.55, n)                        # hidden severity of the episode (never shown to the model)
    infection = rng.binomial(1, 0.12 + 0.1 * (s > 1), n)
    trauma = rng.binomial(1, 0.2, n)
    chest_pain = rng.binomial(1, np.clip(0.04 + 0.0025 * age, 0, 0.35), n)
    dyspnea = rng.binomial(1, np.clip(0.06 + 0.25 * s, 0, 0.9), n)
    vomiting = rng.binomial(1, 0.12, n)
    shock = (rng.random(n) < 0.35) & (s > 1.2)
    hr = 76 + 16 * s + 12 * infection + rng.normal(0, 10, n)
    brady = (rng.random(n) < 0.08) & (s > 1.3)         # a few severe patients have a very slow heart rate
    hr = np.where(brady, rng.normal(42, 6, n), hr)
    rr = 15 + 4.5 * s + 3 * dyspnea + rng.normal(0, 2.2, n)
    spo2 = np.clip(98.2 - 2.2 * s * (0.5 + dyspnea) + rng.normal(0, 1.1, n), 70, 100)
    sbp = np.clip(128 + 0.25 * (age - 50) + rng.normal(0, 16, n) - 28 * s * shock, 60, 230)
    temp = 36.8 + rng.normal(0, 0.35, n) + infection * rng.normal(1.6, 0.6, n)
    p_consc = np.clip(0.02 * s ** 2.2, 0, 0.9)
    consc = np.where(rng.random(n) < p_consc, rng.choice([1, 2, 3], n, p=[0.55, 0.3, 0.15]), 0)
    pain = np.clip(np.round(rng.normal(2.5 + 3.5 * trauma + 3 * chest_pain + 0.8 * s, 1.8, n)), 0, 10).astype(int)
    hr, rr, sbp = np.round(hr).astype(int), np.round(rr).astype(int), np.round(sbp).astype(int)
    temp, spo2 = np.round(temp, 1), np.round(spo2).astype(int)

    # The hidden protocol behind the labels, used only to generate the data:
    # an early-warning score in which a vital sign scores points when it is too low OR too high...
    score = (np.select([rr <= 8, rr <= 11, rr <= 20, rr <= 24], [3, 1, 0, 2], 3)
             + np.select([spo2 <= 91, spo2 <= 93, spo2 <= 95], [3, 2, 1], 0)
             + np.select([sbp <= 90, sbp <= 100, sbp <= 110, sbp <= 219], [3, 2, 1, 0], 3)
             + np.select([hr <= 40, hr <= 50, hr <= 90, hr <= 110, hr <= 130], [3, 1, 0, 1, 2], 3)
             + np.where(consc > 0, 3, 0)
             + np.select([temp <= 35, temp <= 36, temp <= 38, temp <= 39], [3, 1, 0, 1], 2))
    # ...plus clinical discriminators, from the least to the most urgent level
    level = np.full(n, 5)
    level = np.where((score >= 1) | (pain >= 4) | (trauma == 1), 4, level)
    level = np.where((score >= 4) | (pain >= 7) | (temp >= 39) | ((chest_pain == 1) & (age < 45)), 3, level)
    level = np.where((score >= 6) | ((chest_pain == 1) & (age >= 45)) | (spo2 <= 91), 2, level)
    level = np.where((score >= 9) | (consc >= 2) | (sbp <= 80), 1, level)
    # and the nurse's own judgement, which sometimes moves the level one step
    level = np.clip(level + rng.choice([-1, 0, 1], n, p=[0.05, 0.9, 0.05]), 1, 5)

    return pd.DataFrame({
        'age': age.astype(int), 'male': male, 'systolic_bp': sbp, 'heart_rate': hr, 'resp_rate': rr,
        'spo2': spo2, 'temperature': temp, 'consciousness': consc, 'pain': pain, 'chest_pain': chest_pain,
        'dyspnea': dyspnea, 'trauma': trauma, 'vomiting': vomiting, 'level': level,
    })

df = generate_patients(4000, seed=42)
feature_names = [c for c in df.columns if c != 'level']
level_names = ['1 Red', '2 Orange', '3 Yellow', '4 Green', '5 Blue']
X = df[feature_names]
y = df['level']

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25, random_state=42, stratify=y)
print(f"Training set: {len(y_train)} patients, test set: {len(y_test)} patients\n")
print("Patients per urgency level:")
print(pd.DataFrame({'patients': y.value_counts().sort_index(),
                    'share': y.value_counts(normalize=True).sort_index().round(3)},).set_axis(level_names).to_string())

Training set: 3000 patients, test set: 1000 patients

Patients per urgency level:
          patients  share
1 Red          158  0.040
2 Orange       530  0.132
3 Yellow       780  0.195
4 Green       1671  0.418
5 Blue         861  0.215

As in the book, there are many Level 4 and 5 patients and very few Level 1. We keep 25% of the patients apart as the test set (stratified, so each level keeps its proportion) and we will only use it at the end.

Step 5: Feature scaling

---

KNN compares distances, so the units matter. Look at the ranges of the features:

print(X_train.describe().loc[['min', 'max', 'std']].round(1).T.to_string())

                min    max   std
age             1.0   97.0  23.1
male            0.0    1.0   0.5
systolic_bp    60.0  195.0  19.1
heart_rate     32.0  142.0  14.0
resp_rate       8.0   35.0   3.7
spo2           85.0  100.0   1.7
temperature    35.6   40.5   0.7
consciousness   0.0    3.0   0.2
pain            0.0   10.0   2.5
chest_pain      0.0    1.0   0.4
dyspnea         0.0    1.0   0.4
trauma          0.0    1.0   0.4
vomiting        0.0    1.0   0.3

A difference of 20 mmHg in blood pressure is normal, while a difference of 2 °C in temperature is enormous, but without scaling KNN treats the first one as ten times larger. The book describes three ways of putting all the features on a comparable scale:

• Min–max scaling: $x' = \frac{x - \min(x)}{\max(x) - \min(x)}$, to the range [0, 1].
• Standardization (z-score): $z = \frac{x - \mu}{\sigma}$, mean 0 and standard deviation 1.
• Robust scaling: $x' = \frac{x - \text{median}}{\text{IQR}}$, less sensitive to extreme values.

We compare them with a stratified 5-fold cross-validation on the training set. Each scaler is inside a pipeline, so it learns its parameters only from the training folds.

cv = StratifiedKFold(n_splits=5, shuffle=True, random_state=42)
scalers = {'no scaling': None, 'min-max': MinMaxScaler(), 'standardization': StandardScaler(), 'robust': RobustScaler()}
for name, scaler in scalers.items():
    model = make_pipeline(scaler, KNeighborsClassifier(n_neighbors=5)) if scaler else KNeighborsClassifier(n_neighbors=5)
    print(f"{name:<16} mean validation accuracy = {cross_val_score(model, X_train, y_train, cv=cv).mean():.3f}")

no scaling       mean validation accuracy = 0.485

min-max          mean validation accuracy = 0.684
standardization  mean validation accuracy = 0.692

robust           mean validation accuracy = 0.663

Without scaling the accuracy drops to 0.485: the distance is dominated by age, blood pressure and heart rate, the features with the largest numbers, and the temperature, the symptoms or the level of consciousness hardly count. Any of the three scalers fixes most of the problem. Standardization gives the best result here, so we use it from now on.

Step 6: Choosing $K$ and the metric

---

A small $K$ is sensitive to noise (a single atypical neighbor decides); a large $K$ smooths too much and ignores local patterns. As the book says, $K$ is usually chosen with cross-validation:

ks = [1, 3, 5, 7, 9, 11, 15, 21, 31, 51, 101]
k_scores = [cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=k)),
                            X_train, y_train, cv=cv).mean() for k in ks]
best_k = ks[int(np.argmax(k_scores))]

plt.figure(figsize=(8, 4))
plt.semilogx(ks, k_scores, 'o-')
plt.axvline(best_k, color='gray', linestyle='--')
plt.xticks(ks, ks)
plt.xlabel('K (number of neighbors)')
plt.ylabel('Mean validation accuracy')
plt.title('Choosing K with 5-fold cross-validation')
plt.grid(True)
plt.show()
print("  ".join(f"K={k}: {score:.3f}" for k, score in zip(ks, k_scores)))
print(f"Best K: {best_k} (accuracy {max(k_scores):.3f})\n")

metric_scores = {}
for metric in ['euclidean', 'manhattan', 'chebyshev']:
    model = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=best_k, metric=metric))
    metric_scores[metric] = cross_val_score(model, X_train, y_train, cv=cv).mean()
    print(f"K = {best_k}, {metric:<10} mean validation accuracy = {metric_scores[metric]:.3f}")
best_metric = max(metric_scores, key=metric_scores.get)
print(f"Best metric: {best_metric}")

K=1: 0.645  K=3: 0.658  K=5: 0.692  K=7: 0.700  K=9: 0.708  K=11: 0.695  K=15: 0.697  K=21: 0.691  K=31: 0.681  K=51: 0.670  K=101: 0.648
Best K: 9 (accuracy 0.708)

K = 9, euclidean  mean validation accuracy = 0.708

K = 9, manhattan  mean validation accuracy = 0.719
K = 9, chebyshev  mean validation accuracy = 0.667
Best metric: manhattan

The curve has the shape the book describes. With $K = 1$ the model is sensitive to noise (0.645); the accuracy improves up to $K = 9$ and then falls again as the neighborhoods become too large. With $K = 9$, the Manhattan distance works slightly better than the Euclidean one, and Chebyshev, which only looks at the single largest difference, is the worst of the three.

Step 7: The curse of dimensionality

---

Liam warns in the book that with many features the notion of closeness stops being reliable. We can check it: we add columns of pure noise, which have nothing to do with the urgency, and repeat the cross-validation.

rng = np.random.default_rng(0)
for n_noise in [0, 5, 20, 50]:
    X_noisy = np.c_[X_train.to_numpy(dtype=float), rng.normal(size=(len(X_train), n_noise))]
    model = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=best_k, metric=best_metric))
    score = cross_val_score(model, X_noisy, y_train, cv=cv).mean()
    print(f"{len(feature_names)} real features + {n_noise:>2} noise columns: mean validation accuracy = {score:.3f}")

13 real features +  0 noise columns: mean validation accuracy = 0.719

13 real features +  5 noise columns: mean validation accuracy = 0.671
13 real features + 20 noise columns: mean validation accuracy = 0.604

13 real features + 50 noise columns: mean validation accuracy = 0.511

Every block of noise columns lowers the accuracy, from 0.719 with the 13 real features to 0.511 with 50 extra columns. After scaling, a noise column weighs as much in the distance as a real one, so the neighbors are increasingly chosen by chance. With real data this is a reason to select the features carefully before using KNN.

Step 8: Final evaluation

---

We train the chosen model (standardization, the best $K$ and the best metric) with the whole training set and evaluate it once on the test set. In a multiclass problem the confusion matrix is a $5 \times 5$ table: the rows are the real levels and the columns the predicted ones, so everything off the diagonal is an error.

knn = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=best_k, metric=best_metric))
knn.fit(X_train, y_train)
y_pred = knn.predict(X_test)

print(classification_report(y_test, y_pred, target_names=level_names, digits=3))
errors = y_pred != y_test
print(f"Errors: {errors.sum()}, of which {np.mean(np.abs(y_pred - y_test)[errors] == 1):.0%} are one level away from the real one")
ConfusionMatrixDisplay.from_predictions(y_test, y_pred, display_labels=level_names, cmap='Blues', xticks_rotation=30)
plt.xlabel('Predicted level')
plt.ylabel('Real level')
plt.title(f'KNN (K = {best_k}, {best_metric}) on the test set')
plt.show()

              precision    recall  f1-score   support

       1 Red      0.958     0.575     0.719        40
    2 Orange      0.773     0.750     0.762       132
    3 Yellow      0.688     0.508     0.584       195
     4 Green      0.728     0.840     0.780       418
      5 Blue      0.752     0.777     0.764       215

    accuracy                          0.739      1000
   macro avg      0.780     0.690     0.722      1000
weighted avg      0.741     0.739     0.734      1000

Errors: 261, of which 90% are one level away from the real one

On the test set KNN classifies 73.9% of the patients correctly. Look at the red level: when the model says Level 1 it is almost always right (precision 0.958), but it only finds 23 of the 40 Level 1 patients (recall 0.575). In triage that is the dangerous error, a critical patient classified as less urgent. Almost all the errors (90%) are one level away from the real one, which is also where the nurses' own judgement varies.

Finally, the knn_predict function we wrote at the beginning does exactly the same as scikit-learn. We apply it to the test patients, with the same scaling, the same $K$ and the same metric:

scaler = knn[0]
Xs_train, Xs_test = scaler.transform(X_train), scaler.transform(X_test)
distance = {'euclidean': euclidean, 'manhattan': manhattan, 'chebyshev': chebyshev}[best_metric]
ours = np.array([knn_predict(Xs_train, y_train.to_numpy(), x, k=best_k, distance=distance)[0] for x in Xs_test])
print(f"Same prediction as scikit-learn for {np.sum(ours == y_pred)} of {len(y_pred)} test patients")

Same prediction as scikit-learn for 1000 of 1000 test patients

Our twenty lines of NumPy give the same answer as scikit-learn for every test patient. scikit-learn only adds data structures that find the neighbors faster.

Conclusion

---

• KNN classifies a new case with the majority class of its $K$ nearest neighbors. It needs no training, but it has to store all the data and compute every distance for each prediction.
• What "near" means is a decision: the metric changes the neighbors, and without scaling the features with the largest units dominate the distance.
• $K$ and the metric are hyperparameters, chosen with cross-validation.
• With many irrelevant features the notion of closeness gets diluted: the curse of dimensionality.
• The model handles five classes naturally, but it gives no explanation of its decisions, and on the triage data it still makes many mistakes. As in the book, the next candidates are Naive Bayes, decision trees and random forests.