Clustering

So far, every model we built predicted a known target. Clustering is different: there is no target, and the goal is to discover groups in the data — such as segments of customers who behave alike. In this lecture, we learn the K-Means algorithm and how to choose the number of clusters, then apply it to real customer data in Customer Segmentation Analysis.

Supervised vs. Unsupervised Learning

• Supervised Learning: we have a labeled target we want to predict, such as survival, churn, house price, etc.
  • Classification
  • Regression
• Unsupervised Learning: the data is not labeled
  • Clustering: group similar instances together into clusters
  • Association: find relationships between variables, such as "customers who bought this also bought that"
  • Dimensionality reduction: reduce the number of features while preserving as much information as possible

The intuition of a clustering algorithm is quite simple — it tries to achieve:

• Maximum similarity between records within a cluster
• Maximum dissimilarity between records of different clusters

The code for the figures on this page is in the Appendix.

K-Means Algorithm

K-Means clustering is a center-based clustering method that groups the data points into $k$ exclusive clusters.

• Each cluster is represented by a central point, called the Centroid (the blue triangles below)
• Each data instance belongs to exactly one cluster

A Voronoi Diagram for a K-Means clustering result — every point in a region is closer to that region's centroid than to any other centroid:

Centroid

The centroid of a cluster is the mean of its data points — that is where the "means" in K-Means comes from. For example, the centroid of the points (1, 2), (3, 4), and (4, 3) is ((1+3+4)/3, (2+4+3)/3) = (2.67, 3):

import matplotlib.pyplot as plt
plt.style.use('seaborn-v0_8')

fig, ax = plt.subplots()
ax.plot(1, 2, 'o', markersize=10)
ax.plot(3, 4, 'o', markersize=10)
ax.plot(4, 3, 'o', markersize=10)
ax.plot((1+3+4)/3, (2+4+3)/3, '^', markersize=15)  # the centroid

Distance Metrics

Different metrics can be used to measure the distance between data points, such as the Manhattan Distance and the Euclidean Distance:

K-Means uses the Euclidean distance. If $\mathbf{p} = (p_1, p_2, \ldots, p_n)$ and $\mathbf{q} = (q_1, q_2, \ldots, q_n)$ are two points in $n$-dimensional space, the Euclidean distance $d$ between them is:

See more at https://en.wikipedia.org/wiki/Euclidean_distance.

Key Steps of the K-Means Algorithm

Step 1: Initialize $k$ random centroids ($k$ is specified by the user, which is 3 in the following example)

Step 2: Assign each data point to the nearest centroid to form clusters

Step 3: Calculate the new centroid of each cluster

Step 4: Assign each data point to the nearest new centroid to form new clusters

Step 5: Repeat Steps 3 and 4 until the assignments no longer change

Smarter Initialization

Instead of picking the initial centroids at random as described above, K-Means++ selects initial centroids that are distant from one another, which speeds up convergence and leads to better clusters. K-Means++ is the default initialization in scikit-learn.

Evaluation Metrics

• How do we know what $k$ value to choose?
• How do we compare different clustering solutions?

Inertia

The most common evaluation metric is inertia: the sum of the squared distances between each instance and its closest centroid.

The smaller the inertia, the denser the clusters (the points in the same cluster are closer to each other), and the K-Means algorithm aims to minimize inertia.

More formally, K-Means divides a set of $n$ samples into $k$ disjoint clusters $C$, each described by the mean $\mu_j$ (centroid) of the cluster, and minimizes:

Inertia always goes down as $k$ goes up — with one cluster per data point, it would be 0. So we can't just pick the $k$ with the smallest inertia. Instead, we try a range of $k$ values, plot the corresponding inertia, and choose the value at the "elbow" of the plot, where adding more clusters stops helping much — $k = 5$ here:

Inertia has some weaknesses that make it a poor judge on its own:

• It has no minimum to aim for. Because it always decreases, choosing $k$ comes down to eyeballing the elbow, and when the curve bends gradually, two people can pick different values.
• It only measures cohesion, not separation. Inertia asks "how tight is each cluster?" but never "how far apart are the clusters?" Splitting one big blob into two halves that touch lowers inertia, even though it creates no real new group.
• Its value is hard to interpret. Inertia depends on the units and scale of the features and the number of points. An inertia of 4,382 says nothing by itself; you can only compare it with other runs on the same data.
• It is one number for the whole model. It doesn't tell you which clusters or which points are the problem.
• It only makes sense for centroid-based methods like K-Means.

The silhouette score addresses all five.

Silhouette Score (Optional)

The silhouette value measures how similar a data point is to its own cluster (cohesion) compared to other clusters (separation). Inertia only looks at the first of these.

[Silhouette analysis in scikit-learn]

For each data point $i$ in cluster $C_i$:

• $a(i)$ is the mean distance between $i$ and all other points in the same cluster:

  $$a(i) = \frac{1}{|C_i| - 1} \sum_{j \in C_i, j \neq i} d(i, j)$$

• $b(i)$ is the mean distance between $i$ and all points in the closest other cluster (hence the $\min$):

  $$b(i) = \min_{C_k \neq C_i} \frac{1}{|C_k|} \sum_{j \in C_k} d(i, j)$$

The silhouette value of point $i$ is:

It ranges from -1 to 1:

When $a(i) < b(i)$, the formula simplifies to

which turns a value into a plain sentence. For example, $s(i) = 0.6$ means $a(i)/b(i) = 0.4$: the point's average distance to its own cluster is only 40% of its average distance to the nearest other cluster.

The silhouette score is the average of $s(i)$ over all data points, so it reads the same way:

• near 1: the clusters are compact and clearly separated
• near 0: the clusters overlap, and many points are on borders. The data may not have a real cluster structure.
• below 0: the clustering is badly wrong. This is rare with K-Means.

Kaufman and Rousseeuw's book Finding Groups in Data (1990) gives a rough guide for the silhouette score:

From the following silhouette score plot, $k = 5$ is the best, matching the elbow of the inertia plot above. Its score of 0.554 means the mall customers data has a reasonable cluster structure:

Where the Name "Silhouette" Comes From

The method was introduced by Peter Rousseeuw in 1987, in a paper titled Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. As the title says, it started as a picture, not a number. The score came later, as a one-number summary of the picture.

To draw the picture:

1. compute $s(i)$ for every data point
2. group the points by cluster and sort each group by $s(i)$
3. draw each point as a horizontal bar of length $s(i)$, one cluster stacked above the other

Each cluster becomes a filled shape whose outline looks like a shadow or silhouette. The better a cluster's points fit, the further its shape reaches to the right. Here are the silhouette diagrams of the mall customers data:

How to read them:

• width: the length of each bar is $s(i)$, so the wider a cluster's shape reaches to the right (toward 1), the better its points fit
• red dashed line: the silhouette score, the mean $s(i)$ over all points, for that $k$
• height: the number of points in the cluster
• bars left of 0: points with a negative $s(i)$, which are closer to a neighbouring cluster than to their own

Because the bars are sorted, every cluster's shape is longest at the top and gets shorter toward the bottom. So don't judge a cluster by whether it narrows; they all do. Instead, compare the clusters in the same plot and ask where most of each shape sits relative to the red line. A problem cluster is one whose shape sits clearly left of the others, with most of its bars falling short of the red line.

In the mall customers diagrams, three clusters stand out this way:

Then look at the cluster's size to decide what to do:

• A big cluster that sits left of the others usually means two or more groups have been merged into one: try a larger $k$. Each point's $a(i)$ is averaged over the whole cluster, including the far-away other group, so $a(i)$ is large for many points and their $s(i)$ is low. Going from $k = 4$ to $k = 5$, the blue cluster (101 customers) splits into a cluster of 81 customers whose mean $s(i)$ rises from 0.43 to 0.60, and a new 23-customer cluster (purple) with a mean of 0.51. Both now sit level with the other clusters. But a big cluster can also be one group that is simply spread out with no gap inside. If $k + 1$ doesn't produce clusters that sit further right, keep the smaller $k$.
• A small cluster that sits left of the others usually means $k$ is too large: the algorithm has cut off a small group that is not really separate from its neighbour. Cluster 5 (brown) for $k = 6$ is an example.

Why Draw the Diagram If We Just Pick the Highest Score?

The score is an average, and an average can hide problems. The diagram shows what is behind it:

• A weak cluster can hide behind a good average. For $k = 6$, cluster 5 has a mean $s(i)$ of only 0.38, well below the overall 0.51, and only 2 of its 15 points reach the red line. The other clusters pull the average up. You can see the problem in the diagram: cluster 5 is the narrowest shape, with no bar longer than about 0.53, while the other clusters reach 0.65 to 0.72. A short bar means a small $s(i)$, and $s(i)$ is small when $b(i)$ is not much bigger than $a(i)$, that is, when the nearest other cluster is almost as close as the point's own cluster. So cluster 5's points sit closer to a neighbouring cluster than the points of the other clusters do. That suggests $k = 6$ has split off a group that may not be real. The diagram can't tell you which cluster is the close neighbour; for that, plot the clusters themselves.
• It shows what to change. A big cluster sitting left of the others means "split me": $k$ is too small. For $k = 3$, cluster 2 holds 123 of the 200 customers (62%), and only 38% of them are right of the red line. A small cluster sitting left of the others means "merge me": $k$ is too large, like cluster 5 for $k = 6$.
• It confirms the winner. For $k = 5$, no cluster sits clearly left of the others: every cluster has a mean $s(i)$ between 0.50 and 0.60. The best score comes from five reasonable clusters, not from a few excellent ones carrying a bad one.
• It flags individual points. The few bars left of 0 (two of them at $k = 5$) are customers on the border between two segments. Treat them with care, for example before targeting them with a segment-specific campaign.
• It helps when scores are close. The best $k$ and the runner-up are often a few hundredths apart, which can come down to random initialization. When that happens, prefer the $k$ where no cluster sits clearly left of the others, or the one that makes more business sense.

So the score picks a candidate, and the diagram checks whether that candidate deserves to win.

Rule of thumb for comparing two values of $k$: prefer the one where no cluster sits clearly left of the others. Between $k = 4$ and $k = 5$, that picks $k = 5$: at $k = 4$, the big blue cluster has 62% of its points left of the red line, while at $k = 5$, all clusters sit at about the same level.

Inertia vs. Silhouette Score

The silhouette score has costs of its own. It compares every pair of points, so it gets slow on large datasets (use the sample_size argument of silhouette_score to score a random sample). Like inertia, it favors round, compact clusters and can score correct clusterings of long or curved shapes poorly.

In practice, plot both against $k$: use the inertia elbow to narrow down the candidates and the silhouette score to choose among them. If the two disagree, look at the clusters and ask which grouping is more useful for the business question.

Appendix: Plotting Code

The code below draws the clustering, distance, K-Means step, cohesion/separation, and silhouette diagram figures on this page. Run the blocks in order; the last one reads mall_customers.csv from mall_customers.csv.zip.

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_samples

colors = ['tab:blue', 'tab:orange', 'tab:green', 'tab:red', 'tab:purple', 'tab:brown']

# Points grouped into three clusters
plt.style.use('seaborn-v0_8')
X, y = make_blobs(n_samples=60, centers=3, random_state=42)

fig, ax = plt.subplots(figsize=(6, 5))
for j in range(3):
    ax.scatter(X[y == j, 0], X[y == j, 1], s=40, color=colors[j],
               edgecolor='white', label=f'Cluster {j + 1}')
ax.set_xlabel('Feature 1')
ax.set_ylabel('Feature 2')
ax.set_title('Similar within a cluster, dissimilar between clusters')
ax.legend(loc='lower right', frameon=True)
plt.show()

# Manhattan distance vs. Euclidean distance
plt.style.use('seaborn-v0_8-white')
p = np.array([1, 2])
q = np.array([3, 1])
manhattan = np.abs(p - q).sum()             # |1-3| + |2-1| = 3
euclidean = np.sqrt(((p - q) ** 2).sum())   # sqrt(2^2 + 1^2) = sqrt(5)

fig, ax = plt.subplots(figsize=(6, 4.5))
# Manhattan: move along the grid, first horizontally then vertically
ax.plot([p[0], q[0], q[0]], [p[1], p[1], q[1]], '--', color='tab:orange', lw=2)
# Euclidean: the straight line
ax.plot([p[0], q[0]], [p[1], q[1]], '-', color='tab:blue', lw=2)
ax.plot(*p, 'o', color='black', markersize=10)
ax.plot(*q, 'o', color='black', markersize=10)
ax.annotate('X = (1, 2)', p, xytext=(-10, 12), textcoords='offset points',
            ha='right', fontsize=12)
ax.annotate('Y = (3, 1)', q, xytext=(12, -4), textcoords='offset points',
            ha='left', fontsize=12)
ax.text(2.25, 2.12, f'Manhattan distance\n|1 - 3| + |2 - 1| = {manhattan}',
        color='tab:orange', fontsize=11, ha='center', va='bottom')
ax.text(1.75, 1.2, f'Euclidean distance\n$\\sqrt{{2^2 + 1^2}} = \\sqrt{{5}}$ ≈ {euclidean:.2f}',
        color='tab:blue', fontsize=11, ha='center', va='top')
ax.set_xlim(0, 4.2)
ax.set_ylim(0, 3)
ax.set_xticks([0, 1, 2, 3, 4])
ax.set_yticks([0, 1, 2, 3])
ax.set_aspect('equal')
ax.grid(True, color='0.9')
ax.set_xlabel('x')
ax.set_ylabel('y')
plt.show()

# K-Means Steps 1-4: the first steps of a real K-Means run (k = 3)
plt.style.use('seaborn-v0_8')
X, _ = make_blobs(n_samples=60, centers=3, random_state=42)
k = 3


def assign(X, centroids):
    # index of the nearest centroid (Euclidean distance) for every point
    distances = np.sqrt(((X[:, None, :] - centroids[None, :, :]) ** 2).sum(axis=2))
    return distances.argmin(axis=1)


def update(X, labels):
    # the new centroid of each cluster is the mean of its points
    return np.array([X[labels == j].mean(axis=0) for j in range(k)])


# Step 1: k random centroids anywhere within the range of the data
rng = np.random.default_rng(0)
centroids_1 = rng.uniform(X.min(axis=0), X.max(axis=0), size=(k, 2))
# Step 2: assign each point to its nearest centroid
labels_2 = assign(X, centroids_1)
# Step 3: move each centroid to the mean of its cluster
centroids_3 = update(X, labels_2)
# Step 4: reassign each point to its nearest new centroid
labels_4 = assign(X, centroids_3)
changed = labels_4 != labels_2


def draw(ax, labels, centroids, title):
    if labels is None:
        ax.scatter(X[:, 0], X[:, 1], s=40, color='gray', edgecolor='white')
    else:
        ax.scatter(X[:, 0], X[:, 1], s=40, c=[colors[j] for j in labels], edgecolor='white')
    ax.scatter(centroids[:, 0], centroids[:, 1], s=350, marker='^',
               c=colors[:k], edgecolor='black', linewidth=1.5, zorder=3)
    ax.set_title(title)
    ax.set_xlim(-11, 9)
    ax.set_ylim(-11, 13)
    ax.set_xlabel('Feature 1')
    ax.set_ylabel('Feature 2')


fig, ax = plt.subplots(figsize=(6, 5))
draw(ax, None, centroids_1, 'Step 1: pick 3 random centroids')
plt.show()

fig, ax = plt.subplots(figsize=(6, 5))
draw(ax, labels_2, centroids_1, 'Step 2: assign each point to the nearest centroid')
plt.show()

fig, ax = plt.subplots(figsize=(6, 5))
# old centroids as faded triangles, with arrows to the new centroids
ax.scatter(centroids_1[:, 0], centroids_1[:, 1], s=350, marker='^',
           c=colors[:k], alpha=0.3, edgecolor='black', linestyle='--')
for old, new in zip(centroids_1, centroids_3):
    ax.annotate('', xy=new, xytext=old,
                arrowprops=dict(arrowstyle='->', color='black', lw=1.5, shrinkA=10, shrinkB=12))
draw(ax, labels_2, centroids_3, 'Step 3: move each centroid to the mean of its cluster')
plt.show()

fig, ax = plt.subplots(figsize=(6, 5))
draw(ax, labels_4, centroids_3, 'Step 4: reassign points to the nearest new centroid')
# circle the points that switched clusters
ax.scatter(X[changed, 0], X[changed, 1], s=110, facecolor='none',
           edgecolor='black', linewidth=1.2, label=f'{changed.sum()} points changed cluster')
ax.legend(loc='lower right', frameon=True)
plt.show()

# Cohesion a(i) and separation b(i) for one point
plt.style.use('seaborn-v0_8-white')
X, _ = make_blobs(n_samples=24, centers=3, cluster_std=1.2, random_state=7)
labels = KMeans(n_clusters=3, random_state=42).fit(X).labels_

# the point we look at: the one whose silhouette value is closest to 0.5
i = np.abs(silhouette_samples(X, labels) - 0.5).argmin()
own = labels[i]
dist = np.sqrt(((X - X[i]) ** 2).sum(axis=1))
a_i = dist[(labels == own) & (np.arange(len(X)) != i)].mean()
# mean distance to each other cluster; the nearest one gives b(i)
others = {c: dist[labels == c].mean() for c in range(3) if c != own}
nearest = min(others, key=others.get)
b_i = others[nearest]
s_i = (b_i - a_i) / max(a_i, b_i)
assert np.isclose(s_i, silhouette_samples(X, labels)[i])

fig, ax = plt.subplots(figsize=(8, 6))
for j in np.where(labels == own)[0]:
    if j != i:
        ax.plot(*zip(X[i], X[j]), color='tab:green', lw=1, alpha=0.7)
for j in np.where(labels == nearest)[0]:
    ax.plot(*zip(X[i], X[j]), color='tab:orange', lw=1, alpha=0.7)
ax.scatter(*X[labels == own].T, s=70, color='tab:green', edgecolor='white',
           label=f'own cluster: a(i) = {a_i:.2f}', zorder=3)
ax.scatter(*X[labels == nearest].T, s=70, color='tab:orange', edgecolor='white',
           label=f'nearest other cluster: b(i) = {b_i:.2f}', zorder=3)
third = [c for c in range(3) if c not in (own, nearest)][0]
ax.scatter(*X[labels == third].T, s=70, color='lightgray', edgecolor='white',
           label='another cluster (not used)', zorder=3)
ax.scatter(*X[i], s=250, color='tab:green', edgecolor='black', linewidth=2, zorder=4)
ax.annotate('i', X[i], xytext=(10, 8), textcoords='offset points', fontsize=14, weight='bold')
ax.set_title(f's(i) = (b(i) - a(i)) / max(a(i), b(i)) = '
             f'({b_i:.2f} - {a_i:.2f}) / {max(a_i, b_i):.2f} = {s_i:.2f}')
ax.legend(loc='best', frameon=True)
ax.margins(0.12)
ax.set_xticks([])
ax.set_yticks([])
plt.show()

# Silhouette diagrams for the mall customers data
# (reads mall_customers.csv from files/lectures-15-mall-customers-csv.zip)
plt.style.use('seaborn-v0_8')
df_mall = pd.read_csv('mall_customers.csv')
df_2d = df_mall[['income', 'score']]

fig, axes = plt.subplots(2, 2, figsize=(11, 10))
for ax, k in zip(axes.ravel(), [3, 4, 5, 6]):
    labels = KMeans(n_clusters=k, random_state=42).fit(df_2d).labels_
    values = silhouette_samples(df_2d, labels)
    score = values.mean()               # the silhouette score
    y_lower = 0
    ticks = []
    for j in range(k):
        v = np.sort(values[labels == j])
        ax.fill_betweenx(np.arange(y_lower, y_lower + len(v)), 0, v,
                         color=colors[j], alpha=0.8)
        ticks.append(y_lower + len(v) / 2)   # label each silhouette in the middle
        y_lower += len(v) + 5                # a small gap between clusters
    ax.axvline(score, color='red', linestyle='--')
    ax.set_title(f'k = {k} (silhouette score = {score:.3f})')
    ax.set_xlim(-0.1, 1)
    ax.set_xlabel('Silhouette value')
    ax.set_ylabel('Cluster')
    ax.set_yticks(ticks, labels=range(k))
plt.tight_layout()
plt.show()