07 K-Nearest Neighbors — Exercises¶

Test your understanding of distance computation, majority voting, weighted KNN, and the curse of dimensionality.

Prerequisites. Read theory.md and work through first_principles.ipynb before attempting these.

In [1]:

import random

import matplotlib.pyplot as plt
import numpy as np

%load_ext autoreload
%autoreload 2

SEED = 42
random.seed(SEED)
rng = np.random.default_rng(SEED)

plt.rcParams["figure.dpi"] = 90

import random import matplotlib.pyplot as plt import numpy as np %load_ext autoreload %autoreload 2 SEED = 42 random.seed(SEED) rng = np.random.default_rng(SEED) plt.rcParams["figure.dpi"] = 90

Exercise 1 — Hand Calculation: Distances and Majority Vote¶

Given 5 training points in 2D:

Point	$x_1$	$x_2$	Label
A	1	2	0
B	3	3	0
C	5	1	1
D	4	4	1
E	2	5	0

Query point: $x_q = (3, 2)$.

Tasks (compute by hand, then verify):

1. Compute the Euclidean distance from $x_q$ to each training point.
2. For $K = 3$, which 3 points are the nearest neighbors?
3. What is the majority-vote prediction for $K = 3$?
4. What is the majority-vote prediction for $K = 1$?

Expected distances:

Point	Distance
A	$\sqrt{(3-1)^2 + (2-2)^2} = 2.000$
B	$\sqrt{(3-3)^2 + (2-3)^2} = 1.000$
C	$\sqrt{(3-5)^2 + (2-1)^2} = \sqrt{5} \approx 2.236$
D	$\sqrt{(3-4)^2 + (2-4)^2} = \sqrt{5} \approx 2.236$
E	$\sqrt{(3-2)^2 + (2-5)^2} = \sqrt{10} \approx 3.162$

Expected results:

• K=3 neighbors: B (1.000), A (2.000), C or D (2.236) → labels {0, 0, 1} → predict 0
• K=1 neighbor: B (1.000) → label 0 → predict 0

In [2]:

# Verify hand calculations.
X_ex1 = np.array([[1, 2], [3, 3], [5, 1], [4, 4], [2, 5]], dtype=float)
y_ex1 = np.array([0, 0, 1, 1, 0])
x_q = np.array([3.0, 2.0])

distances = np.linalg.norm(X_ex1 - x_q, axis=1)
print("Distances:", distances.round(3))

# Check expected distances.
assert np.isclose(distances[0], 2.0, atol=1e-10), "Distance to A should be 2.0"
assert np.isclose(distances[1], 1.0, atol=1e-10), "Distance to B should be 1.0"
assert np.isclose(distances[2], np.sqrt(5), atol=1e-10), "Distance to C should be sqrt(5)"
assert np.isclose(distances[3], np.sqrt(5), atol=1e-10), "Distance to D should be sqrt(5)"
assert np.isclose(distances[4], np.sqrt(10), atol=1e-10), "Distance to E should be sqrt(10)"

# K=3: nearest are B(0), A(0), then C(1) or D(1) — both at sqrt(5).
# np.argpartition with K=3 selects indices of 3 smallest.
nearest_3 = np.argpartition(distances, 2)[:3]
labels_3 = y_ex1[nearest_3]
vals, counts = np.unique(labels_3, return_counts=True)
pred_k3 = vals[np.argmax(counts)]
print(f"K=3 neighbors: indices {nearest_3}, labels {labels_3}, prediction: {pred_k3}")
assert pred_k3 == 0, "K=3 should predict class 0"

# K=1: nearest is B (index 1, label 0).
pred_k1 = y_ex1[np.argmin(distances)]
print(f"K=1 prediction: {pred_k1}")
assert pred_k1 == 0, "K=1 should predict class 0"

print("All hand calculation checks passed.")

# Verify hand calculations. X_ex1 = np.array([[1, 2], [3, 3], [5, 1], [4, 4], [2, 5]], dtype=float) y_ex1 = np.array([0, 0, 1, 1, 0]) x_q = np.array([3.0, 2.0]) distances = np.linalg.norm(X_ex1 - x_q, axis=1) print("Distances:", distances.round(3)) # Check expected distances. assert np.isclose(distances[0], 2.0, atol=1e-10), "Distance to A should be 2.0" assert np.isclose(distances[1], 1.0, atol=1e-10), "Distance to B should be 1.0" assert np.isclose(distances[2], np.sqrt(5), atol=1e-10), "Distance to C should be sqrt(5)" assert np.isclose(distances[3], np.sqrt(5), atol=1e-10), "Distance to D should be sqrt(5)" assert np.isclose(distances[4], np.sqrt(10), atol=1e-10), "Distance to E should be sqrt(10)" # K=3: nearest are B(0), A(0), then C(1) or D(1) — both at sqrt(5). # np.argpartition with K=3 selects indices of 3 smallest. nearest_3 = np.argpartition(distances, 2)[:3] labels_3 = y_ex1[nearest_3] vals, counts = np.unique(labels_3, return_counts=True) pred_k3 = vals[np.argmax(counts)] print(f"K=3 neighbors: indices {nearest_3}, labels {labels_3}, prediction: {pred_k3}") assert pred_k3 == 0, "K=3 should predict class 0" # K=1: nearest is B (index 1, label 0). pred_k1 = y_ex1[np.argmin(distances)] print(f"K=1 prediction: {pred_k1}") assert pred_k1 == 0, "K=1 should predict class 0" print("All hand calculation checks passed.")

Distances: [2.    1.    2.236 2.236 3.162]
K=3 neighbors: indices [1 0 2], labels [0 0 1], prediction: 0
K=1 prediction: 0
All hand calculation checks passed.

Exercise 2 — Coding: Weighted KNN¶

Implement a weighted KNN classifier where each neighbor's vote is weighted by the inverse of its distance to the query point:

$$w_i = \frac{1}{d(x_q, x_i) + \epsilon}$$

The prediction is:

$$\hat{y} = \arg\max_c \sum_{i \in \mathcal{N}_K} w_i \cdot \mathbb{1}[y_i = c]$$

Tasks:

1. Implement WeightedKNN with fit(X, y) and predict(X) methods.
2. Use epsilon = 1e-10 to avoid division by zero.
3. Verify on the Exercise 1 dataset: for $K = 5$ (all points), the weighted vote should give more weight to closer points.

Deterministic check: Using the 5-point dataset from Exercise 1 with $K = 5$, the query $x_q = (3, 2)$ should predict class 0 (B is closest → class 0 gets highest total weight).

Second check: For $x_q = (4.5, 2.5)$, $K = 3$, the prediction should be class 1 (C and D are nearby class-1 points).

In [3]:

class WeightedKNN:
    """Weighted K-Nearest Neighbors with inverse-distance weighting."""

    def __init__(self, n_neighbors=5, epsilon=1e-10):
        self.n_neighbors = n_neighbors
        self.epsilon = epsilon
        self.X_train_ = None
        self.y_train_ = None

    def fit(self, X, y):
        # TODO: store training data
        pass

    def predict(self, X):
        # TODO: for each query point:
        #   1. Compute distances to all training points
        #   2. Find K nearest neighbors (use np.argpartition)
        #   3. Compute weights = 1 / (distance + epsilon)
        #   4. Sum weights per class, predict the class with highest total weight
        pass

class WeightedKNN: """Weighted K-Nearest Neighbors with inverse-distance weighting.""" def __init__(self, n_neighbors=5, epsilon=1e-10): self.n_neighbors = n_neighbors self.epsilon = epsilon self.X_train_ = None self.y_train_ = None def fit(self, X, y): # TODO: store training data pass def predict(self, X): # TODO: for each query point: # 1. Compute distances to all training points # 2. Find K nearest neighbors (use np.argpartition) # 3. Compute weights = 1 / (distance + epsilon) # 4. Sum weights per class, predict the class with highest total weight pass

Solution 2¶

In [4]:

class WeightedKNN:
    """Weighted K-Nearest Neighbors with inverse-distance weighting."""

    def __init__(self, n_neighbors=5, epsilon=1e-10):
        self.n_neighbors = n_neighbors
        self.epsilon = epsilon
        self.X_train_ = None
        self.y_train_ = None

    def fit(self, X, y):
        self.X_train_ = np.asarray(X, dtype=float)
        self.y_train_ = np.asarray(y)
        return self

    def predict(self, X):
        X = np.atleast_2d(np.asarray(X, dtype=float))
        classes = np.unique(self.y_train_)
        k = min(self.n_neighbors, len(self.X_train_))
        preds = np.empty(len(X), dtype=self.y_train_.dtype)
        for i, x_q in enumerate(X):
            distances = np.linalg.norm(self.X_train_ - x_q, axis=1)
            nearest = np.argpartition(distances, k - 1)[:k]
            weights = 1.0 / (distances[nearest] + self.epsilon)
            scores = np.array([
                weights[self.y_train_[nearest] == c].sum() for c in classes
            ])
            preds[i] = classes[np.argmax(scores)]
        return preds


# --- Deterministic checks ---
X_ex2 = np.array([[1, 2], [3, 3], [5, 1], [4, 4], [2, 5]], dtype=float)
y_ex2 = np.array([0, 0, 1, 1, 0])

# Check 1: query (3, 2) with K=5 → predict 0
wknn = WeightedKNN(n_neighbors=5).fit(X_ex2, y_ex2)
pred1 = wknn.predict(np.array([[3.0, 2.0]]))
assert pred1[0] == 0, f"Expected class 0, got {pred1[0]}"

# Check 2: query (4.5, 2.5) with K=3 → predict 1
wknn3 = WeightedKNN(n_neighbors=3).fit(X_ex2, y_ex2)
pred2 = wknn3.predict(np.array([[4.5, 2.5]]))
assert pred2[0] == 1, f"Expected class 1, got {pred2[0]}"

print("All weighted KNN checks passed.")

class WeightedKNN: """Weighted K-Nearest Neighbors with inverse-distance weighting.""" def __init__(self, n_neighbors=5, epsilon=1e-10): self.n_neighbors = n_neighbors self.epsilon = epsilon self.X_train_ = None self.y_train_ = None def fit(self, X, y): self.X_train_ = np.asarray(X, dtype=float) self.y_train_ = np.asarray(y) return self def predict(self, X): X = np.atleast_2d(np.asarray(X, dtype=float)) classes = np.unique(self.y_train_) k = min(self.n_neighbors, len(self.X_train_)) preds = np.empty(len(X), dtype=self.y_train_.dtype) for i, x_q in enumerate(X): distances = np.linalg.norm(self.X_train_ - x_q, axis=1) nearest = np.argpartition(distances, k - 1)[:k] weights = 1.0 / (distances[nearest] + self.epsilon) scores = np.array([ weights[self.y_train_[nearest] == c].sum() for c in classes ]) preds[i] = classes[np.argmax(scores)] return preds # --- Deterministic checks --- X_ex2 = np.array([[1, 2], [3, 3], [5, 1], [4, 4], [2, 5]], dtype=float) y_ex2 = np.array([0, 0, 1, 1, 0]) # Check 1: query (3, 2) with K=5 → predict 0 wknn = WeightedKNN(n_neighbors=5).fit(X_ex2, y_ex2) pred1 = wknn.predict(np.array([[3.0, 2.0]])) assert pred1[0] == 0, f"Expected class 0, got {pred1[0]}" # Check 2: query (4.5, 2.5) with K=3 → predict 1 wknn3 = WeightedKNN(n_neighbors=3).fit(X_ex2, y_ex2) pred2 = wknn3.predict(np.array([[4.5, 2.5]])) assert pred2[0] == 1, f"Expected class 1, got {pred2[0]}" print("All weighted KNN checks passed.")

All weighted KNN checks passed.

Exercise 3 — Conceptual: Why Does KNN Fail in High Dimensions?¶

Questions:

1. The volume of a $p$-dimensional unit ball is $V_p = \pi^{p/2} / \Gamma(p/2 + 1)$. Compute $V_p$ for $p = 1, 2, 3, 5, 10, 20$. What happens as $p$ grows?

2. Consider 1000 points drawn uniformly in $[0, 1]^p$. To capture the nearest 10 points (1% of data) in a hypercube, you need a cube with side length $s = 0.01^{1/p}$. Compute $s$ for $p = 1, 2, 5, 10, 20, 100$. What does this tell you about how "local" the neighborhood is in high dimensions?

3. Explain in 2-3 sentences why adding irrelevant features hurts KNN more than it hurts a regularised linear model (e.g., Lasso).

Expected for Q2:

$p$	$s = 0.01^{1/p}$
1	0.010
2	0.100
5	0.398
10	0.631
20	0.794
100	0.955

Insight: In 100D, capturing just 1% of points requires spanning 95.5% of each feature's range — the neighborhood is no longer "local."

In [5]:

from scipy.special import gamma

# Q1: Volume of unit ball in p dimensions.
dims = [1, 2, 3, 5, 10, 20]
print("Volume of unit ball V_p:")
for p in dims:
    V = np.pi ** (p / 2) / gamma(p / 2 + 1)
    print(f"  p={p:2d}: V = {V:.6f}")

# V_2 should be pi, V_3 should be 4*pi/3
assert np.isclose(np.pi ** 1 / gamma(2), np.pi, atol=1e-10)
assert np.isclose(np.pi ** 1.5 / gamma(2.5), 4 * np.pi / 3, atol=1e-10)

print("\nQ2: Side length s to capture 1% of data:")
dims_q2 = [1, 2, 5, 10, 20, 100]
for p in dims_q2:
    s = 0.01 ** (1 / p)
    print(f"  p={p:3d}: s = {s:.3f}")

# Check specific values.
assert np.isclose(0.01 ** (1 / 1), 0.01, atol=1e-10)
assert np.isclose(0.01 ** (1 / 2), 0.1, atol=1e-10)
assert np.isclose(0.01 ** (1 / 100), 0.955, atol=0.001)
print("\nAll dimensional checks passed.")

from scipy.special import gamma # Q1: Volume of unit ball in p dimensions. dims = [1, 2, 3, 5, 10, 20] print("Volume of unit ball V_p:") for p in dims: V = np.pi ** (p / 2) / gamma(p / 2 + 1) print(f" p={p:2d}: V = {V:.6f}") # V_2 should be pi, V_3 should be 4*pi/3 assert np.isclose(np.pi ** 1 / gamma(2), np.pi, atol=1e-10) assert np.isclose(np.pi ** 1.5 / gamma(2.5), 4 * np.pi / 3, atol=1e-10) print("\nQ2: Side length s to capture 1% of data:") dims_q2 = [1, 2, 5, 10, 20, 100] for p in dims_q2: s = 0.01 ** (1 / p) print(f" p={p:3d}: s = {s:.3f}") # Check specific values. assert np.isclose(0.01 ** (1 / 1), 0.01, atol=1e-10) assert np.isclose(0.01 ** (1 / 2), 0.1, atol=1e-10) assert np.isclose(0.01 ** (1 / 100), 0.955, atol=0.001) print("\nAll dimensional checks passed.")

Volume of unit ball V_p:
  p= 1: V = 2.000000
  p= 2: V = 3.141593
  p= 3: V = 4.188790
  p= 5: V = 5.263789
  p=10: V = 2.550164
  p=20: V = 0.025807

Q2: Side length s to capture 1% of data:
  p=  1: s = 0.010
  p=  2: s = 0.100
  p=  5: s = 0.398
  p= 10: s = 0.631
  p= 20: s = 0.794
  p=100: s = 0.955

All dimensional checks passed.

Exercise 4 — Coding: Manhattan Distance KNN¶

Modify the from-scratch KNN to use Manhattan distance (L1) instead of Euclidean (L2):

$$d_1(x, z) = \sum_{j=1}^p |x_j - z_j|$$

Tasks:

1. Implement KNN_L1 with Manhattan distance.
2. Compare its predictions with sklearn.neighbors.KNeighborsClassifier(metric='manhattan').
3. They should match exactly.

Deterministic check: On the Exercise 1 data with K=3 and query $(3, 2)$:

• Manhattan distances: A=2, B=1, C=3, D=3, E=4
• K=3 neighbors: B(1), A(2), C or D (3) → predict 0

In [6]:

class KNN_L1:
    """KNN classifier with Manhattan (L1) distance."""

    def __init__(self, n_neighbors=5):
        self.n_neighbors = n_neighbors
        self.X_train_ = None
        self.y_train_ = None

    def fit(self, X, y):
        # TODO: store training data
        pass

    def predict(self, X):
        # TODO: same as Euclidean KNN but use L1 distance:
        # distances = np.sum(np.abs(self.X_train_ - x_q), axis=1)
        pass


# Deterministic check on Exercise 1 data.
# knn_l1 = KNN_L1(n_neighbors=3).fit(X_ex2, y_ex2)
# pred_l1 = knn_l1.predict(np.array([[3.0, 2.0]]))
# assert pred_l1[0] == 0, f"Expected class 0, got {pred_l1[0]}"

# Sklearn comparison.
# from sklearn.neighbors import KNeighborsClassifier as SkKNN
# from ml_first_principles.data_utils import generate_classification_data, train_test_split
# X_l1, y_l1 = generate_classification_data(n_samples=200, n_features=2, random_state=SEED)
# X_tr, X_te, y_tr, y_te = train_test_split(X_l1, y_l1, test_size=0.2, random_state=SEED)
# ours = KNN_L1(n_neighbors=5).fit(X_tr, y_tr)
# skl = SkKNN(n_neighbors=5, metric='manhattan').fit(X_tr, y_tr)
# assert np.all(ours.predict(X_te) == skl.predict(X_te))
# print('Manhattan KNN matches sklearn.')

class KNN_L1: """KNN classifier with Manhattan (L1) distance.""" def __init__(self, n_neighbors=5): self.n_neighbors = n_neighbors self.X_train_ = None self.y_train_ = None def fit(self, X, y): # TODO: store training data pass def predict(self, X): # TODO: same as Euclidean KNN but use L1 distance: # distances = np.sum(np.abs(self.X_train_ - x_q), axis=1) pass # Deterministic check on Exercise 1 data. # knn_l1 = KNN_L1(n_neighbors=3).fit(X_ex2, y_ex2) # pred_l1 = knn_l1.predict(np.array([[3.0, 2.0]])) # assert pred_l1[0] == 0, f"Expected class 0, got {pred_l1[0]}" # Sklearn comparison. # from sklearn.neighbors import KNeighborsClassifier as SkKNN # from ml_first_principles.data_utils import generate_classification_data, train_test_split # X_l1, y_l1 = generate_classification_data(n_samples=200, n_features=2, random_state=SEED) # X_tr, X_te, y_tr, y_te = train_test_split(X_l1, y_l1, test_size=0.2, random_state=SEED) # ours = KNN_L1(n_neighbors=5).fit(X_tr, y_tr) # skl = SkKNN(n_neighbors=5, metric='manhattan').fit(X_tr, y_tr) # assert np.all(ours.predict(X_te) == skl.predict(X_te)) # print('Manhattan KNN matches sklearn.')

Exercise 5 — Conceptual: KNN vs Parametric Models¶

Questions:

1. KNN stores the entire training set. A logistic regression model stores only a $p$-dimensional vector $\theta$. For a dataset with $n = 10^6$ samples and $p = 100$ features (float64), how much memory does each model require at prediction time? Which is more practical for deployment?

2. KNN prediction is $O(np)$ per query. Logistic regression prediction is $O(p)$. If you need to classify 1000 queries per second with $n = 10^6$ and $p = 100$, is brute-force KNN feasible? What about with a KD-tree?

3. Why does KNN naturally handle multi-class problems without any modification, while logistic regression needs to be extended to softmax? What architectural feature of KNN makes this possible?