Classification, Trees, Neighbours and Clusters

Classification and decision boundaries

A classifier sorts inputs into categories. Picture each example as a point, with one axis per feature, coloured by its class. A classifier carves this space into regions, one per class, and the edges between regions are decision boundaries.

Different algorithms draw different kinds of boundary:

k-nearest neighbours

k-nearest neighbours (kNN) is the simplest classifier there is, and a surprisingly good one.

1. Store all the training examples. That is the whole of training.
2. For a new point, measure its distance to every stored example.
3. Take the k closest, its nearest neighbours.
4. Predict the class most of them belong to.

The choice of k matters. With k = 1 the model copies its single nearest neighbour, so one mislabelled example creates a little island of wrong answers: overfitting. A very large k smooths everything towards the most common class: underfitting. An odd k avoids ties between two classes.

Logistic regression: probabilities from a line

Despite its name, logistic regression classifies. It computes a linear score exactly like regression, then squashes the score into a probability between 0 and 1 using the sigmoid function.

• A large positive z gives a probability near 1, a large negative z gives one near 0, and z = 0 gives exactly 0.5.
• The model predicts the class when the probability passes a threshold, usually 0.5. The boundary where z = 0 is a straight line.
• It is trained with log loss (cross-entropy), which punishes confident wrong answers severely. Level 5 explains why.

Look closely and you will see a weighted sum, a bias, and a squashing function. That is exactly an artificial neuron, which is Level 6.

Decision trees and forests

A decision tree asks a sequence of yes or no questions about the features, and each answer leads down a branch until a leaf gives the prediction.

How a tree chooses its questions

At each step the tree tries every feature and every threshold, and picks the question that splits the examples into the purest groups. Purity is measured with Gini impurity:

A group of all one class has Gini 0. A 50 : 50 mix of two classes has Gini 1 − (0.5² + 0.5²) = 0.5. The tree picks the split that lowers the average impurity the most, weighted by group size, then repeats inside each branch.

Forests

A single deep tree overfits. Two ensemble methods fix that:

• A random forest trains hundreds of trees, each on a random sample of the data and features, and lets them vote. The errors of individual trees cancel out.
• Gradient boosting builds trees one after another, each trained to correct the mistakes of those before. Libraries such as XGBoost and LightGBM are the standard tool for tabular data in industry.

Evaluating classifiers: the confusion matrix

For a yes or no classifier there are four possible outcomes:

From these four counts:

Raising the threshold makes the model more cautious: precision usually rises and recall falls. Which matters more depends on the cost of each mistake. Missing a cancer (a false negative) is far worse than an extra scan (a false positive), so a screening model favours recall. A spam filter that bins real emails is worse than one that lets a little spam through, so it favours precision.

Clustering with k-means

With no labels at all, k-means finds k groups of similar points.

1. Choose k, and place k centroids (cluster centres), for example at k random data points.
2. Assign every point to its nearest centroid.
3. Update: move each centroid to the mean of the points assigned to it.
4. Repeat steps 2 and 3 until nothing changes.

Each round can only reduce the total squared distance from points to their centroids, so the algorithm always settles down, usually within a handful of rounds.

Its limits

• You must choose k. The elbow method plots the total distance for k = 1, 2, 3 and so on, and looks for the point where adding clusters stops helping much.
• Different starting centroids can give different answers, so it is run several times and the best result kept.
• It assumes clusters are roughly round and similar in size, and it will happily split random noise into k clusters.

Hands-on: classify and cluster from scratch

k-nearest neighbours

import math

# (sweetness, crunchiness) of foods, labelled by type
data = [((9, 2), "fruit"), ((8, 3), "fruit"), ((7, 1), "fruit"), ((8, 1), "fruit"),
        ((2, 9), "vegetable"), ((3, 8), "vegetable"), ((1, 7), "vegetable"),
        ((2, 6), "vegetable"), ((6, 6), "nut"), ((5, 7), "nut"), ((5, 9), "nut")]

def knn(point, k):
    nearest = sorted(data, key=lambda item: math.dist(item[0], point))[:k]
    votes = {}
    for _, label in nearest:
        votes[label] = votes.get(label, 0) + 1
    return max(votes, key=votes.get), [label for _, label in nearest]

for food in [(7, 3), (3, 6), (6, 8)]:
    for k in (1, 3, 5):
        guess, neighbours = knn(food, k)
        print(f"{food} with k={k}: {guess:10} neighbours {neighbours}")

Choosing a split with Gini impurity

def gini(labels):
    n = len(labels)
    return 1 - sum((labels.count(c) / n) ** 2 for c in set(labels))

# Hours of sleep and whether the student felt alert
sleep = [4, 5, 5, 6, 7, 7, 8, 8, 9, 10]
alert = ["no", "no", "no", "no", "yes", "no", "yes", "yes", "yes", "yes"]

best = None
for threshold in sorted(set(sleep)):
    left = [a for s, a in zip(sleep, alert) if s < threshold]
    right = [a for s, a in zip(sleep, alert) if s >= threshold]
    if not left or not right:
        continue
    score = (len(left) * gini(left) + len(right) * gini(right)) / len(alert)
    print(f"split at sleep < {threshold:2}: weighted Gini {score:.3f}")
    if best is None or score < best[0]:
        best = (score, threshold)
print("Best question: is sleep <", best[1], "hours?")

k-means

import math

points = [(1, 1), (1.5, 2), (2, 1.2), (8, 8), (9, 8.5), (8.5, 9.5), (1, 8), (2, 9), (1.5, 9.5)]
centroids = [(1, 1), (2, 1.2), (8, 8)]          # deliberately poor starting places

for step in range(1, 10):
    clusters = [[] for _ in centroids]
    for p in points:
        nearest = min(range(len(centroids)), key=lambda i: math.dist(p, centroids[i]))
        clusters[nearest].append(p)
    new = [(sum(x for x, y in c) / len(c), sum(y for x, y in c) / len(c)) for c in clusters]
    print(f"round {step}:", [(round(x, 2), round(y, 2)) for x, y in new])
    if new == centroids:
        print("No change, so k-means has converged.")
        break
    centroids = new

Two starting centroids were placed inside the same group, yet within a few rounds one of them migrates to the empty group at the top left.

Activity: build a human decision tree

As a class, think of an animal. A volunteer may only ask yes or no questions about features, such as "does it have fur?". Record the questions on the board as a tree. Which first question splits the class's animals most evenly, and why is that the best first question?

Level check

• Explain what a decision boundary is and sketch the boundaries of three algorithms
• Describe the kNN algorithm and the effect of choosing k
• Explain how logistic regression turns a linear score into a probability
• Calculate Gini impurity and explain how a tree chooses a split
• Calculate precision and recall from a confusion matrix and say when each matters more
• Describe the k-means algorithm and two of its limitations

Key terms you must be able to define

Classifier

A model that predicts which category an input belongs to.

Decision boundary

The edge between the regions a classifier assigns to different classes.

k-nearest neighbours

Classifying a point by a vote of the k training examples closest to it.

Logistic regression

A classifier that passes a linear score through the sigmoid function to give a probability.

Sigmoid

The S-shaped function 1 ÷ (1 + e^-z) that squashes any number into the range 0 to 1.

Decision tree

A model that predicts by asking a sequence of yes or no questions about the features.

Gini impurity

A measure of how mixed the classes in a group are; 0 means all one class.

Random forest

Many decision trees trained on random samples of the data, voting together.

Precision

Of the examples predicted positive, the fraction that really are positive.

Recall

Of the examples that really are positive, the fraction the model found.

k-means

A clustering algorithm that repeatedly assigns points to the nearest of k centroids and moves each centroid to the mean of its points.

Centroid

The centre of a cluster: the mean of the points in it.

Flashcards

Go further: notes for future AI engineers

Support vector machines

Before deep learning, the most celebrated classifier was the support vector machine (SVM, 1990s). Of all the straight lines that separate two classes, it chooses the one with the widest margin, the gap to the nearest points on either side, which tends to generalise well. The kernel trick lets an SVM draw curved boundaries by implicitly mapping the data into a higher-dimensional space where a flat boundary works.

Why trees still win on tables

On images, sound and text, deep learning dominates because those inputs have structure (neighbouring pixels, word order) that networks exploit. Spreadsheet-style data has no such structure, features are often on wildly different scales, and datasets are often small. Gradient boosted trees handle all of that with little tuning. A good engineer tries a boosted tree baseline on any table before reaching for a neural network.

Misconceptions to avoid