Skip to main content

Module 4 — k-nearest neighbors and support vector machines

After the linear models, two geometric approaches to classification. k-NN bets everything on proximity: alike resembles alike. The SVM seeks the boundary that separates classes with the greatest safety margin. Two opposite philosophies — no learning at all versus careful optimization — and complementary lessons.

k-NN: predicting by looking at the neighbors​

The k-nearest-neighbors algorithm holds in one sentence: to classify a new point, find the kk closest training points and take a majority vote. No training phase in the usual sense — the model is the dataset. Distance (Euclidean most often — the norms from the mathematics course) does all the work.

from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler

X_train_s = StandardScaler().fit_transform(X_train)  # imperative: same scale
model = KNeighborsClassifier(n_neighbors=5).fit(X_train_s, y_train)

Standardization is non-negotiable here: a feature with a large scale would crush the others in the distance computation.

Choosing k: the bias-variance trade-off again​

  • Small k (1 or 3): highly flexible boundary, sensitive to noise → overfitting (excess variance).
  • Large k: smoothed boundary, the vote drowns local structure → underfitting (excess bias).

You tune kk by cross-validation. Two structural limits to know: prediction is slow on large datasets (you must compare against every point), and performance collapses in high dimension — the curse of dimensionality, where distances lose their meaning, seen in the mathematics course.

SVM: the widest-margin boundary​

Among all the lines that separate two classes, which is best? The SVM answers: the one that passes as far as possible from the points of both classes — the maximum-margin boundary. Intuition: the wider the safety corridor, the better the boundary tolerates the small variations of new data, hence better generalization.

The points that touch the margin's edge are called support vectors: they alone determine the boundary. Remove any other point and nothing changes — a remarkable economy.

from sklearn.svm import SVC
model = SVC(kernel="rbf", C=1.0).fit(X_train_s, y_train)

The parameter C sets margin strictness: a large C tolerates no points inside the margin (overfitting risk), a small C accepts violations for a wider, more robust margin. Same slider as λ\lambda in module 2, in reverse.

The kernel trick: separating the non-separable​

When no line can separate the classes, the SVM plays its trump card: the kernel trick. The idea — project the data into a higher-dimensional space where they become linearly separable, without ever explicitly computing that projection. The RBF (Gaussian) kernel is the versatile default, capable of drawing arbitrarily flexible boundaries in the original space.

When to use which?

k-NN: small dataset, few dimensions, need for an explainable model ("your case resembles these 5 known cases"). SVM: medium dataset, complex boundary, standardized features. On very large datasets, both give way to the trees and boosting of the coming modules — which is precisely why the course now heads toward trees.

Summary​

  • k-NN classifies by majority vote of the kk nearest neighbors: no training, but standardization required and slow prediction.
  • The choice of kk replays bias-variance: small kk overfits, large kk smooths too much.
  • The SVM seeks the maximum-margin boundary, determined solely by the support vectors; C sets the strictness.
  • The kernel trick (RBF) lets you separate non-linear classes without explicit projection.

Next module: decision trees — readable models that split the space with if/then rules.