Clustering

Most algorithms so far learned from labelled examples. The model saw inputs and correct answers, then learned to predict those answers.

But many real datasets have no labels. Imagine collecting thousands of restaurant visits with price, distance, waiting time, calories, cuisine, and atmosphere, but no record of whether Jessie liked the restaurant.

Can we still discover useful structure? Clustering says yes.

A cluster is a group of examples that are more similar to one another than to the rest of the dataset. If restaurant visits form three visible groups, those groups might later be interpreted as fast food, casual dining, and fine dining.

The algorithm does not know those names. It only sees similarity. Humans interpret the meaning afterwards.

K-Means Algorithm

K-Means is the most common clustering algorithm. Choose a number of clusters $K$, place $K$ centroids, assign each point to its nearest centroid, move centroids to the mean of assigned points, and repeat.

Distance

K-Means usually uses Euclidean distance. For two points $x=(x_1,x_2)$ and $y=(y_1,y_2)$:

Objective Function

K-Means tries to minimize total within-cluster squared distance:

Here $x_i$ is a data point, $\mu_{c(i)}$ is the centroid of its assigned cluster, and $c(i)$ is the cluster assignment.

Why It Works

Each assignment step chooses the nearest centroid, so the objective cannot increase. Each update step moves the centroid to the mean, which is the point that minimizes squared distance to assigned points. This also cannot increase the objective.

Because the objective decreases or stays unchanged each iteration, K-Means eventually converges. It may converge to a local optimum, so different initializations can produce different clusters.

Choosing K

Choosing the number of clusters is one of the hard parts. The elbow method plots $K$ against within-cluster sum of squares and looks for the point where improvements begin to level off.

Silhouette score compares how close a point is to its own cluster versus nearby clusters. Higher values usually indicate cleaner separation.

Limitations

K-Means works best when clusters are roughly spherical, similarly sized, and well separated. It struggles with irregular shapes, different densities, outliers, and unscaled features.

Other Clustering Algorithms

Clustering Versus Classification

This NumPy implementation follows the two-step K-Means loop: assign to nearest centroid, then recompute centroids as means.

import numpy as np

def kmeans(X, k, max_iter=100, seed=0):
    rng = np.random.default_rng(seed)
    centroids = X[rng.choice(len(X), size=k, replace=False)]

    for _ in range(max_iter):
        distances = np.linalg.norm(
            X[:, None, :] - centroids[None, :, :],
            axis=2,
        )
        labels = np.argmin(distances, axis=1)

        new_centroids = np.array([
            X[labels == cluster].mean(axis=0)
            if np.any(labels == cluster)
            else centroids[cluster]
            for cluster in range(k)
        ])

        if np.allclose(new_centroids, centroids):
            break

        centroids = new_centroids

    objective = np.sum((X - centroids[labels]) ** 2)
    return labels, centroids, objective