Machine Learning Foundations

Classic ML: k-NN, decision trees, k-means, and PCA

The workhorses before deep learning

~13 minLesson 9 of 57Written by Claude Opus 4.8

Four non-neural algorithms - one for boundaries, one for splits, one for clusters, one for compression - that build the geometric intuition every neural net is later just a fancier version of.

Long before neural networks, machine learning ran on a handful of algorithms so geometric you can draw each one on a napkin. k-nearest-neighbours classifies a point by asking its closest neighbours to vote. A decision tree is a flowchart of yes/no splits. k-means hunts for cluster centres with nobody labelling the data. And PCA finds the directions your data actually varies along and throws the rest away. Master these four and you own the intuition for decision boundaries, clustering, and dimensionality reduction - the same three ideas neural nets later learned to do automatically.

Four ideas before the neural net

Two of these are supervised - the data comes with answers (labels), and the model learns to reproduce them. k-NN and decision trees both draw decision boundaries: they carve the input space into coloured regions, one per class. The other two are unsupervised - no labels at all, just raw points, and the algorithm finds structure on its own. k-means finds groups; PCA finds the axes that matter. The playground below lets you build all three of the geometric ones by hand - place points, scrub a knob, and watch the algorithm redraw itself.

k-NN: a vote of the k nearest

There is no training. To classify a new point $x$ , measure the distance $d (x, x_{i}) = ∥ x - x_{i} ∥$ to every labelled point, keep the $k$ closest, and take the majority label among them: $\overset{y}{^} = mode {y_{i} : i \in N_{k} (x)}$ . That single parameter $k$ is a smoothness knob. At $k = 1$ each point rules its own little territory, so a single mislabelled stray carves out an island of the wrong colour - the boundary is jagged and it memorises the noise. Crank $k$ up and more neighbours vote, so strays get out-voted and the boundary smooths into a clean curve. Too high and it blurs real structure away. Start the playground on k-NN, then drag $k$ and watch the coloured regions breathe.

A decision boundary is just a colouring of space

Every classifier, from k-NN to a 100-billion-parameter transformer, ultimately paints the input space with one colour per class. The decision boundary is the seam where the colour flips. k-NN makes that seam explicit and visible: it is exactly the set of points that are a tie between two classes' nearest neighbours. When you scrub

k

below, you are not changing the data - only how wiggly the model is allowed to make that seam.

2-D ML playgroundpick an algorithm · click to add points

neighbours k = 1add:

k = 1. The seam hugs every point, so each lone stray owns its own island of colour - the model has memorised the noise. (8 in A, 8 in B - click to add more)

Class AClass Bshaded region = predicted class

k-means and PCA, hands-on

k-means (the k-means tab) is unsupervised: no labels, just a cloud, and you tell it only how many groups $K$ to find. It then repeats two dead-simple steps - Lloyd's algorithm:

Assign. Colour every point by whichever of the $K$ centroids is nearest.
Update. Move each centroid to the mean of the points that just chose it: $μ_{j} = \frac{1}{∣ C _{j} ∣} \sum_{x \in C_{j}} x$ .

Press Step to run one half-step at a time and literally watch the points recolour, then the centroids migrate toward the centres of mass. Each full round can only lower the total within-cluster spread, so it converges:

J = j = 1 \sum K x \in C_{j} \sum ∥ x - μ_{j} ∥^{2} shrinks every iteration.

The catch: the answer depends on where the centroids start. Hit Reseed a few times and you will sometimes see it settle into a worse split - the classic reason real code runs k-means several times and keeps the lowest $J$ .

PCA (the PCA tab) answers a different question: which direction does the data vary along most? It builds the covariance matrix $C = \frac{1}{n} \sum_{i} (x_{i} - \overset{ˉ}{x}) (x_{i} - \overset{ˉ}{x})^{⊤}$ and takes its eigenvectors. The top one, PC1, is the axis of greatest variance; PC2 is the next-greatest, at a right angle. Rotate the cloud and PC1 stays glued to its longest direction - variance is a property of the shape, not the angle you happen to view it from. Stretch the cloud and the bar fills: the fraction $λ_{1} / (λ_{1} + λ_{2})$ is how much of the data you could keep by projecting onto PC1 alone and discarding PC2. That is dimensionality reduction - throwing away the axis that barely moves.

PCA is compression by keeping only what varies

Projecting your data onto its top few eigenvectors is the oldest trick in the embeddings book. Instead of learning what matters (as a neural net does), PCA computes it: the directions of maximum variance are the ones that carry the most information, so keeping them and dropping the flat ones squeezes many dimensions down to a few with the least possible loss. When you meet word embeddings, remember this: "find the directions that matter, keep those, drop the rest" is the same idea a network arrives at on its own - PCA just does it with linear algebra you can see.

Decision trees: a flowchart of yes/no splits

The one algorithm the playground skips is the most human-readable of the four. A decision tree classifies by asking a sequence of threshold questions - "is feature 1 < 0.4?", then "is feature 2 < 0.7?" - each answer sending you left or right until you hit a leaf that names a class. Geometrically it chops the space into axis-aligned rectangles, one per leaf (where k-NN's boundary curves freely, a tree's is always a staircase of horizontal and vertical cuts). To pick each split, the tree tries every threshold and keeps the one that makes the two sides purest - most dominated by a single class. Purity is scored with the Gini impurity $G = 1 - \sum_{c} p_{c}^{2}$ , which is $0$ when a node holds one class only and largest when the classes are evenly mixed. Grow the tree deep enough and it memorises the training data (overfits), exactly like $k = 1$ ; the cure is to stop early or prune back - the tree's version of turning up $k$ .

from sklearn.neighbors import KNeighborsClassifier
from sklearn.tree      import DecisionTreeClassifier
from sklearn.cluster   import KMeans
from sklearn.decomposition import PCA

# --- supervised: learn a boundary from labelled X, y ---
knn  = KNeighborsClassifier(n_neighbors=5).fit(X, y)   # vote of 5 nearest
tree = DecisionTreeClassifier(max_depth=3).fit(X, y)   # 3 layers of splits
labels_knn = knn.predict(X_new)

# --- unsupervised: no y at all ---
km   = KMeans(n_clusters=3, n_init=10).fit(X)      # 10 restarts, keep best J
clusters = km.labels_                                # which group each point joined

pca  = PCA(n_components=2).fit(X)                # top 2 eigenvectors of cov(X)
X_small = pca.transform(X)                          # project onto PC1, PC2
print(pca.explained_variance_ratio_)               # e.g. [0.83, 0.11] -> PC1 keeps 83%

All four, the way you would actually call them

Check yourself

Increasing k in k-NN makes the decision boundary:

In PCA, the first principal component points along the direction of:

Recall k-means' two repeating steps, and what PCA's first two principal components represent.

Try to state it, then check.

k-means alternates: (1) assign each point to its nearest centroid, then (2) update each centroid to the mean of the points assigned to it - repeat until nothing moves. PCA's principal components are the eigenvectors of the data's covariance matrix: PC1 is the direction of greatest variance, PC2 the next-greatest at a right angle to it. Projecting onto the top few compresses the data while losing the least variance.

Lock it in

Four non-neural algorithms cover the core geometric ideas: k-NN and decision trees draw decision boundaries (supervised); k-means clusters and PCA compresses (unsupervised).
k-NN has no training - classify by the majority vote of the $k$ nearest points. $k$ is a smoothness knob: $k = 1$ memorises noise with a jagged seam, larger $k$ out-votes strays and smooths it.
k-means alternates assign (colour by nearest centroid) and update (move each centroid to its points' mean), shrinking the within-cluster spread $J$ every round - but the result depends on the seeding, so real code restarts and keeps the lowest $J$ .
PCA takes the eigenvectors of the covariance matrix: PC1 is the direction of greatest variance, and projecting onto the top few compresses the data with the least loss.
A decision tree chops space into axis-aligned rectangles, picking each split to minimise Gini impurity $G = 1 - \sum_{c} p_{c}^{2}$ ; grown too deep it overfits like $k = 1$ , cured by stopping early or pruning.

Primary source

Josh Starmer's StatQuest machine-learning playlist walks through k-NN, k-means, and PCA one clear picture at a time - it is the gentlest correct introduction anywhere. For PCA especially, spend ten minutes with Victor Powell & Lewis Lehe's interactive Explained Visually, where you drag a point cloud and watch the principal axes and variance track it live - the same interaction you just built above.

Ask your teacher

Sit with this connection: PCA is the missing bridge from eigenvectors (Lesson 86) to embeddings (Lesson 12). "Directions of maximum variance" is precisely how you would compress data down to a few meaningful axes before neural nets learned to discover those axes for themselves - the eigenvector you rotated in the demo is a hand-computed embedding dimension. Ask me why k-means can get stuck in a bad local minimum, how the "curse of dimensionality" quietly breaks k-NN in high dimensions, or how a decision tree's staircase boundary becomes a smooth one once you average hundreds of trees into a random forest.