Clustering

Overview#

Clustering is unsupervised learning's core task: grouping similar data points together without any labeled target to guide the process. This notebook covers K-Means (the most widely used clustering algorithm), hierarchical clustering, DBSCAN (density-based clustering), methods for choosing the number of clusters, and evaluation metrics for clustering quality — a genuinely different problem from supervised evaluation, since there's no ground truth to compare against.

1. Clustering vs Everything Else in This Course#

Every algorithm covered so far in this course has been supervised — learning from labeled examples (X, y). Clustering is unsupervised — there is no y at all. The algorithm's job is to discover structure in X alone, grouping similar points together based purely on their feature values.

Python
CopyAsk AI
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt

X, true_labels = make_blobs(n_samples=300, centers=4, cluster_std=0.8, random_state=42)
# Note: true_labels exists here only because this is SIMULATED data for
# teaching purposes — in a real unsupervised problem, no labels exist at all

2. K-Means Clustering#

K-Means partitions data into k clusters, where each point belongs to the cluster with the nearest centroid (the cluster's mean position).

Python
CopyAsk AI
from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=4, random_state=42, n_init=10)
kmeans.fit(X)

labels = kmeans.labels_             # which cluster each point was assigned to
centroids = kmeans.cluster_centers_   # the final centroid positions

print(f"Cluster centers:\n{centroids}")

How K-Means actually works (the algorithm)#

text
Ask AICopy
1. Initialize k centroids randomly (or via k-means++, a smarter method)
2. Repeat until convergence:
   a. ASSIGNMENT step: assign each point to its nearest centroid
   b. UPDATE step: move each centroid to the mean position of its
      currently assigned points
3. Stop when assignments no longer change (or after a max iteration limit)

Python
CopyAsk AI
# n_init=10 (default in recent scikit-learn) runs the whole algorithm 10
# times with different random starting centroids, keeping the best result
# — this matters because K-Means can converge to different, suboptimal
# solutions depending on its random starting point
kmeans = KMeans(n_clusters=4, n_init=10, random_state=42)

K-Means is NOT guaranteed to find the globally optimal clustering — it's a greedy algorithm that converges to a local optimum, which can depend heavily on the initial centroid positions. Running it multiple times with different initializations (n_init) and keeping the best result (lowest total within-cluster distance) mitigates this.

K-Means++ initialization#

Python
CopyAsk AI
kmeans = KMeans(n_clusters=4, init="k-means++", n_init=10, random_state=42)
# init="k-means++" (the default) intelligently spreads out initial
# centroids rather than placing them uniformly at random, generally
# leading to faster convergence and better final results

Predicting cluster assignment for new points#

Python
CopyAsk AI
new_points = [[0, 0], [5, 5]]
predicted_clusters = kmeans.predict(new_points)
print(predicted_clusters)   # assigns each new point to its nearest existing centroid

3. Choosing k: The Elbow Method#

K-Means requires you to specify k in advance — but the right number of clusters usually isn't known ahead of time. The elbow method plots "inertia" (total within-cluster squared distance) against different values of k, looking for a bend where adding more clusters stops helping much.

Python
CopyAsk AI
import numpy as np

inertias = []
k_range = range(1, 11)

for k in k_range:
    kmeans = KMeans(n_clusters=k, n_init=10, random_state=42)
    kmeans.fit(X)
    inertias.append(kmeans.inertia_)

plt.plot(k_range, inertias, marker="o")
plt.xlabel("Number of clusters (k)")
plt.ylabel("Inertia")
plt.title("Elbow Method")
plt.show()

text
Ask AICopy
Inertia always DECREASES as k increases (more clusters can always fit the
data more tightly — at k = n_samples, inertia reaches zero). The "elbow"
— the point where the rate of decrease sharply slows down — is a
reasonable estimate of a good k. Beyond the elbow, adding more clusters
yields diminishing returns relative to the added complexity.

The Silhouette score: a more principled alternative#

Python
CopyAsk AI
from sklearn.metrics import silhouette_score

silhouette_scores = []
for k in range(2, 11):   # silhouette score requires at least 2 clusters
    kmeans = KMeans(n_clusters=k, n_init=10, random_state=42)
    labels = kmeans.fit_predict(X)
    score = silhouette_score(X, labels)
    silhouette_scores.append(score)
    print(f"k={k}: silhouette score = {score:.3f}")

best_k = list(range(2, 11))[np.argmax(silhouette_scores)]
print(f"Best k by silhouette score: {best_k}")

text
Ask AICopy
Silhouette score ranges from -1 to +1:
  +1  → point is well-matched to its own cluster, far from other clusters
   0  → point is on or near the boundary between two clusters
  -1  → point is likely assigned to the WRONG cluster

The silhouette score gives a concrete, bounded, more interpretable signal
than inertia (which has no natural scale) for choosing k, and doesn't
require visually eyeballing an "elbow" that isn't always clearly defined.

4. Limitations of K-Means#

Python
CopyAsk AI
from sklearn.datasets import make_moons

X_moons, _ = make_moons(n_samples=200, noise=0.08, random_state=42)

kmeans_moons = KMeans(n_clusters=2, n_init=10, random_state=42)
labels_moons = kmeans_moons.fit_predict(X_moons)
# K-Means will produce a poor result here — it assumes roughly SPHERICAL,
# similarly-SIZED clusters, and this crescent-moon-shaped data violates
# that assumption badly

text
Ask AICopy
K-Means assumes:
- Clusters are roughly spherical/convex (not crescent-shaped, elongated,
  or otherwise irregular)
- Clusters are of roughly similar size and density
- The number of clusters (k) is known in advance
- Distance is measured in a way where "mean" is a meaningful summary
  (doesn't work well for categorical data without special handling)

When any of these assumptions is badly violated, K-Means produces
misleading results — DBSCAN (below) handles irregularly-shaped clusters
much better.

5. Hierarchical Clustering#

Hierarchical clustering builds a tree of nested clusters, either by repeatedly merging the closest pairs of clusters (agglomerative, the more common approach) or by repeatedly splitting clusters apart (divisive).

Python
CopyAsk AI
from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt

agg = AgglomerativeClustering(n_clusters=4, linkage="ward")
labels = agg.fit_predict(X)

Visualizing the full hierarchy with a dendrogram#

Python
CopyAsk AI
linked = linkage(X, method="ward")

plt.figure(figsize=(12, 6))
dendrogram(linked)
plt.xlabel("Sample index")
plt.ylabel("Distance")
plt.title("Hierarchical Clustering Dendrogram")
plt.show()

A key advantage over K-Means: a dendrogram shows the entire merge history, letting you choose the number of clusters after seeing the full structure (by drawing a horizontal cut line at any height), rather than needing to commit to k upfront.

Linkage methods (how "distance between clusters" is defined)#

Python
CopyAsk AI
AgglomerativeClustering(n_clusters=4, linkage="ward")     # minimizes variance within merged clusters
AgglomerativeClustering(n_clusters=4, linkage="complete")   # max distance between any two points across clusters
AgglomerativeClustering(n_clusters=4, linkage="average")     # average distance between all cross-cluster pairs
AgglomerativeClustering(n_clusters=4, linkage="single")        # min distance between any two points (can create "chains")

ward linkage is the most commonly used default — it tends to produce well-balanced, compact clusters similar in spirit to K-Means, while single linkage can create long, straggly "chained" clusters that merge based on just one close pair of points, regardless of overall cluster shape.

6. DBSCAN: Density-Based Clustering#

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) groups together points that are densely packed, marking points in low-density regions as noise/outliers rather than forcing them into a cluster — a capability K-Means and hierarchical clustering fundamentally lack.

Python
CopyAsk AI
from sklearn.cluster import DBSCAN

dbscan = DBSCAN(eps=0.3, min_samples=5)
labels = dbscan.fit_predict(X_moons)

print(f"Number of clusters found: {len(set(labels)) - (1 if -1 in labels else 0)}")
print(f"Number of noise points: {list(labels).count(-1)}")   # labeled -1 = noise

How DBSCAN works#

text
Ask AICopy
For each point, DBSCAN checks how many other points fall within a
distance of `eps`:

- If a point has at least `min_samples` neighbors within `eps`, it's a
  CORE point — the seed of a cluster.
- If a point is within `eps` of a core point but doesn't have enough
  neighbors itself, it's a BORDER point — part of the cluster, but not
  a seed.
- If a point is neither, it's NOISE — doesn't belong to any cluster.

Clusters grow by connecting core points that are within eps of each
other, along with their border points.

DBSCAN naturally handles clusters of arbitrary shape (like the crescent-moon data that broke K-Means) and doesn't require specifying the number of clusters in advance — it discovers that automatically based on density. Its main tuning burden shifts to choosing eps and min_samples appropriately.

Python
CopyAsk AI
dbscan_moons = DBSCAN(eps=0.2, min_samples=5)
labels_moons = dbscan_moons.fit_predict(X_moons)
# DBSCAN correctly identifies the two crescent shapes as separate
# clusters, where K-Means failed

Choosing eps: the k-distance plot#

Python
CopyAsk AI
from sklearn.neighbors import NearestNeighbors

neighbors = NearestNeighbors(n_neighbors=5)
neighbors.fit(X)
distances, _ = neighbors.kneighbors(X)
distances = np.sort(distances[:, -1])   # distance to the 5th nearest neighbor, sorted

plt.plot(distances)
plt.xlabel("Points sorted by distance")
plt.ylabel("5th nearest neighbor distance")
plt.title("k-distance plot for choosing eps")
plt.show()
# Look for an "elbow" in this plot — a good eps value is often around
# where the curve sharply bends upward

7. K-Means vs Hierarchical vs DBSCAN#

8. Evaluating Clustering Quality#

Since there's no ground truth in real unsupervised problems, clustering evaluation looks different from supervised metrics.

Python
CopyAsk AI
from sklearn.metrics import silhouette_score, calinski_harabasz_score, davies_bouldin_score

labels = kmeans.fit_predict(X)

print(f"Silhouette score: {silhouette_score(X, labels):.3f}")           # higher is better, range [-1, 1]
print(f"Calinski-Harabasz score: {calinski_harabasz_score(X, labels):.1f}")   # higher is better, no fixed range
print(f"Davies-Bouldin score: {davies_bouldin_score(X, labels):.3f}")          # LOWER is better, unlike the other two

When ground truth labels ARE available (for validation/comparison only)#

Python
CopyAsk AI
from sklearn.metrics import adjusted_rand_score, normalized_mutual_info_score

# Only usable when you happen to have true labels available for
# validation purposes — comparing the clustering result against them
ari = adjusted_rand_score(true_labels, labels)
nmi = normalized_mutual_info_score(true_labels, labels)
print(f"Adjusted Rand Index: {ari:.3f}")   # 1.0 = perfect match, ~0 = random

These label-based metrics are useful when evaluating a clustering algorithm's general performance on benchmark datasets (where labels happen to be known), but don't apply to genuinely unsupervised real-world problems where no labels exist at all — in that case, silhouette score and similar internal metrics are what you actually have available.

Notes#

• Clustering is fundamentally different from every supervised method covered elsewhere in this course — there's no target variable, and therefore no single "correct" answer to validate against.
• K-Means assumes roughly spherical, similarly-sized clusters and a known k — violating these assumptions (as with crescent-shaped or highly varying-density data) produces poor results.
• The elbow method is a useful but somewhat subjective heuristic; silhouette score gives a more concrete, bounded metric for comparing different values of k.
• DBSCAN's ability to explicitly mark points as noise, rather than forcing every point into some cluster, is a major practical advantage when real data contains genuine outliers.
• Clustering results, unlike supervised model predictions, always require domain judgment to interpret — a clustering algorithm will always produce some grouping, even on data with no real underlying structure, so the results need sanity-checking against actual understanding of the data.

Best Practices Checklist#

• Scale features before clustering, since K-Means and DBSCAN both rely on distance calculations
• Use the elbow method or silhouette score to guide the choice of k for K-Means, rather than picking arbitrarily
• Run K-Means with multiple initializations (n_init) to avoid poor local optima
• Consider DBSCAN or hierarchical clustering when clusters are suspected to be non-spherical or contain genuine outliers
• Use a dendrogram to explore cluster structure at multiple granularities before committing to a specific cluster count
• Use a k-distance plot to guide the choice of eps for DBSCAN
• Evaluate clustering quality with silhouette score (or similar) rather than assuming any given clustering is "correct"
• Sanity-check clustering results against actual domain knowledge — an algorithm will produce groupings even from structureless data