k-NN, Decision Trees & Random Forests — AI Course

What you'll learn

Not every model needs gradients. This module covers three intuitive, widely-used classifiers that carve up feature space directly: k-nearest neighbours, decision trees, and the ensemble that made trees a powerhouse — the random forest.

By the end of this module you'll be able to:

Classify a point with k-NN by voting among neighbours
Read a decision tree as a flow of yes/no questions
Explain how a tree chooses its splits
Say why a forest of trees beats a single tree

k-nearest neighbours

The simplest classifier there is: to label a new point, find the k training points closest to it and let them vote. There's no training at all — the data is the model. Step through it:

k-NN: classify by nearest neighbours

k-nearest neighbours (k = 3)

grey ⬤ = a new point to classify

1/4k-NN classifies a new point by looking at the points nearest to it. Here is our new point (grey).

Find the k closest points, take a majority vote — then the decision map for every location.

Note

Small k gives a wiggly, detailed boundary that can overfit; large k gives a smoother one. k-NN is simple and strong on small datasets, but slow to predict on big ones — it must compare against every point.

Decision trees

A decision tree asks a sequence of yes/no questions about the features, following branches until it reaches a leaf that gives the answer. Each internal node splits the data on one feature threshold:

A decision tree is a flow of questions

petal length < 2.5 cm?

yes

🌸 Setosa

petal width < 1.8 cm?

yes

Versicolor

Virginica

Follow the answers down to a leaf. Trees are among the most interpretable models.

How a tree splits

At each node the tree tries every feature and threshold and keeps the split that best separates the classes — measured by an impurity score like Gini or entropy. A perfectly pure split (all one class on each side) scores best. It repeats, greedily, growing the tree.

Watch out

Left unchecked, a tree keeps splitting until every leaf is one point — memorising the training set. That's classic overfitting (Module 11). We limit depth, or better, combine many trees.

Random forests

One deep tree is unstable; a crowd of them is powerful. A random forest trains hundreds of trees, each on a random subset of the data and features, then averages their votes. The individual mistakes cancel out and the ensemble generalises far better — this is called bagging.

A close cousin, gradient boosting (XGBoost, LightGBM), builds trees one after another, each fixing the errors of the last. Together, these tree ensembles still win a huge share of real-world problems on tabular data.

trees.py

from sklearn.neighbors import KNeighborsClassifier
from sklearn.ensemble import RandomForestClassifier

# k-NN: no training — it just stores the data and votes at predict time
knn = KNeighborsClassifier(n_neighbors=3).fit(X_train, y_train)

# Random forest: hundreds of trees, each on a random slice, voting together
forest = RandomForestClassifier(n_estimators=200).fit(X_train, y_train)
print(forest.score(X_test, y_test))

Recap & quick check

Key takeaways

k-NN classifies a point by a majority vote of its k nearest neighbours — no training, but slow to predict.
A decision tree is a flow of yes/no feature questions ending in a class; it's highly interpretable.
Trees choose splits that best separate classes, measured by Gini or entropy impurity.
A single deep tree overfits; a random forest averages many trees (bagging) to generalise better.
Tree ensembles (random forests, gradient boosting) remain top performers on tabular data.

Quick check

1. How does k-NN classify a new point?

2. What does a decision tree's internal node do?

3. Why does a single unrestricted decision tree tend to overfit?

4. What is the core idea of a random forest?

So far every model had labels to learn from. Next we drop the labels entirely and let the data organise itself. Next up: Module 9 — Unsupervised Learning: k-Means & PCA.