Clustering

Clustering is the unsupervised task of grouping a set of objects so that objects in the same group (cluster) are more similar to each other than to objects in other groups. There are no labels — the algorithm discovers the groups itself.

The Goal, Formally

   Maximise INTRA-cluster similarity  (points within a cluster are close together)
   Minimise INTER-cluster similarity  (clusters are far apart from each other)

Types of Clustering Methods

Hard vs Soft Clustering

Distance and Similarity Measures

Clustering depends entirely on how "similar" is defined.

Euclidean (numeric, most common):
   d(p,q) = √[ Σ (pᵢ − qᵢ)² ]

Manhattan:
   d(p,q) = Σ |pᵢ − qᵢ|

Cosine similarity (text, high-dimensional sparse data):
                    p · q
   cos(θ) = ─────────────────────      ranges from −1 to 1; distance = 1 − cos(θ)
              ||p|| × ||q||

Jaccard similarity (binary/set data):
                 |A ∩ B|
   J(A,B) = ───────────────
                 |A ∪ B|

Hamming distance (categorical): number of attributes that differ

Always scale numeric features before clustering — exactly as with KNN, an unscaled income column will dominate every distance computation.

Evaluating Clusters

Without labels, evaluation is intrinsic — based on the geometry of the result.

Silhouette coefficient for a single point i:

              b(i) − a(i)
   s(i) = ─────────────────────
             max{ a(i), b(i) }

   a(i) = mean distance from i to all other points in ITS cluster (cohesion)
   b(i) = mean distance from i to all points in the NEAREST other cluster (separation)

   s(i) ≈  +1  ->  well clustered
   s(i) ≈   0  ->  on the boundary between two clusters
   s(i) ≈  −1  ->  probably assigned to the wrong cluster

Python — Comparing Clustering Algorithms

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs, make_moons
from sklearn.cluster import KMeans, AgglomerativeClustering, DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score, davies_bouldin_score

# Two datasets with very different shapes
X_blobs, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.9, random_state=42)
X_moons, _ = make_moons(n_samples=300, noise=0.06, random_state=42)

datasets = {"Globular blobs": StandardScaler().fit_transform(X_blobs),
            "Crescent moons": StandardScaler().fit_transform(X_moons)}

algorithms = {
    "K-Means (k=4/2)": lambda X, k: KMeans(n_clusters=k, n_init=10, random_state=42).fit_predict(X),
    "Hierarchical":    lambda X, k: AgglomerativeClustering(n_clusters=k).fit_predict(X),
    "DBSCAN":          lambda X, k: DBSCAN(eps=0.3, min_samples=5).fit_predict(X),
}

fig, axes = plt.subplots(2, 3, figsize=(16, 9))
for row, (dname, X) in enumerate(datasets.items()):
    k = 4 if row == 0 else 2
    for col, (aname, fn) in enumerate(algorithms.items()):
        labels = fn(X, k)
        axes[row, col].scatter(X[:, 0], X[:, 1], c=labels, cmap="viridis", s=25)
        n_found = len(set(labels)) - (1 if -1 in labels else 0)
        axes[row, col].set_title(f"{dname}\n{aname} — {n_found} clusters")
plt.tight_layout(); plt.show()
# KEY OBSERVATION: K-Means and hierarchical clustering cut the crescents in half
# (they assume convex, globular clusters). DBSCAN recovers the true shapes because
# it follows density, not distance-to-centre.

# Comparing quality metrics across algorithms
X = StandardScaler().fit_transform(X_blobs)
results = []
for name, model in [
    ("K-Means",      KMeans(n_clusters=4, n_init=10, random_state=42)),
    ("Hierarchical", AgglomerativeClustering(n_clusters=4)),
    ("DBSCAN",       DBSCAN(eps=0.5, min_samples=5)),
]:
    labels = model.fit_predict(X)
    if len(set(labels)) > 1:
        results.append({
            "Algorithm": name,
            "Clusters": len(set(labels)) - (1 if -1 in labels else 0),
            "Silhouette": round(silhouette_score(X, labels), 4),
            "Davies-Bouldin": round(davies_bouldin_score(X, labels), 4),
        })
print(pd.DataFrame(results).to_string(index=False))

DBSCAN in Brief

Density-Based Spatial Clustering of Applications with Noise groups points that are densely packed, and marks points in low-density regions as noise/outliers.

Advantages: finds arbitrarily shaped clusters, automatically determines the number of clusters, and explicitly identifies outliers. Disadvantages: struggles when clusters have very different densities, and ε is hard to choose in high dimensions.

Applications of Clustering

Clustering vs Classification — Exam Table

The next two lessons detail the two clustering algorithms the syllabus names: K-Means and hierarchical clustering.