Clustering

Clustering is an unsupervised learning task: you’re given data points x₁,…,xₙ (no labels), and you want to group them into “clusters” so that points in the same group are “similar,” and points in different groups are “dissimilar.”

The key idea is that clustering is not a single problem—it’s a family of problems defined by choices you make:

1) Representation: what is a data point? (a vector x ∈ ℝᵈ? a document? an image embedding?)

2) Similarity / distance: how do we measure “close”? (‖x−y‖₂, cosine distance, etc.)

3) Cluster model: what does a cluster “look like”? (a centroid-based ball, a connected component, a hierarchy)

4) Objective / procedure: what criterion do we optimize or what rule do we follow?

A practical definition you can use:

• •A cluster is a set of points grouped because, under a chosen distance/similarity, they are more similar to one another than to points outside the set.

Notice what’s missing: there is no universal “correct” clustering without extra assumptions. Two different distance metrics can yield different but equally defensible clusterings.

Why clustering is useful

Clustering shows up in many places because it provides structure without labels:

• •Exploration: discover subpopulations (customer segments, gene expression patterns)
• •Compression / summarization: represent many points by a few prototypes (centroids)
• •Preprocessing: create features like “cluster ID,” or initialize other models
• •Anomaly detection: points far from any cluster can be suspicious

The geometry intuition

If your data are vectors in ℝᵈ, distance-based clustering is fundamentally geometric.

• •With Euclidean distance, clustering often assumes that “togetherness” means points form compact blobs.
• •But real data may have elongated, varying-density, or nested structures.

This is why we study multiple clustering paradigms. In this lesson, we’ll focus on two core methods:

• •K-means (centroid-based, objective-driven)
• •Hierarchical clustering (tree-building, linkage-driven)

We’ll also treat clustering as a pipeline: choose distance + scale features, run algorithm, then validate and interpret.

Notation we’ll use

• •Data points: xᵢ ∈ ℝᵈ, i = 1,…,n
• •Number of clusters: k
• •Cluster index: j = 1,…,k
• •Centroid (prototype) of cluster j: μⱼ ∈ ℝᵈ
• •Assignment of point i: cᵢ ∈ {1,…,k}

The major theme: clustering is about optimizing or constructing a grouping consistent with your similarity notion—and knowing when that grouping is trustworthy.

K-means is the classic centroid-based clustering algorithm. It is popular because it is simple, fast, and often surprisingly effective.

Why K-means works (motivation first)

Suppose you believe each cluster can be summarized by a “typical” point—its centroid—and that points should belong to the cluster whose centroid is closest.

This belief translates into an objective: choose k centroids and assignments so that points are close to their assigned centroid.

The K-means objective

Given assignments cᵢ and centroids μⱼ, the within-cluster sum of squares (WCSS) is:

J(c, μ) = ∑ᵢ ‖xᵢ − μ_{cᵢ}‖₂²

K-means solves:

minimize over assignments cᵢ and centroids μⱼ:

min J(c, μ) = ∑ᵢ ‖xᵢ − μ_{cᵢ}‖₂²

This is sometimes described as “minimizing within-cluster variance.”

Why squared Euclidean distance?

• •Squaring strongly penalizes far-away points.
• •It yields a clean centroid update: the best centroid is the mean.
• •It leads to efficient alternating minimization.

But it also implies a geometric assumption: clusters are roughly spherical (balls) in Euclidean space.

The two-step alternating minimization

K-means uses an iterative procedure (often called Lloyd’s algorithm):

1) Assignment step (E-step-like):

Fix centroids μⱼ. Assign each point to the nearest centroid:

cᵢ ← argminⱼ ‖xᵢ − μⱼ‖₂²

2) Update step (M-step-like):

Fix assignments cᵢ. Update each centroid to the mean of points in that cluster:

μⱼ ← (1 / |Cⱼ|) ∑_{i: cᵢ = j} xᵢ

These steps repeat until assignments stop changing or the objective decreases only slightly.

Show-your-work: why the centroid is the mean

Focus on one cluster j with points {xᵢ : cᵢ = j}. We want μ that minimizes:

f(μ) = ∑_{i: cᵢ=j} ‖xᵢ − μ‖₂²

Expand using dot products:

‖xᵢ − μ‖₂² = (xᵢ − μ)·(xᵢ − μ)

= xᵢ·xᵢ − 2 xᵢ·μ + μ·μ

So

f(μ) = ∑ (xᵢ·xᵢ) − 2 ∑(xᵢ·μ) + ∑(μ·μ)

Let m = |Cⱼ|. Note ∑(μ·μ) = m(μ·μ).

Take the gradient with respect to μ:

∇ f(μ) = -2 ∑ xᵢ + 2 m μ

Set ∇ f(μ) = 0:

-2 ∑ xᵢ + 2 m μ = 0

⇒ m μ = ∑ xᵢ

⇒ μ = (1/m) ∑ xᵢ

So the centroid update is not a heuristic—it is the exact minimizer of the squared-distance objective given fixed assignments.

Convergence (what it guarantees and what it doesn’t)

Each iteration:

• •The assignment step does not increase J.
• •The update step does not increase J.

So J decreases monotonically and the algorithm converges in finitely many steps to a local minimum.

But:

• •The solution depends on initialization.
• •K-means can get stuck in poor local minima.

Initialization and k-means++

Random initialization (choose k random points as initial μⱼ) can be unstable.

k-means++ improves this by spreading initial centroids apart:

1) Pick one centroid uniformly from the data.

2) For each point x, compute D(x) = distance to nearest chosen centroid.

3) Choose next centroid with probability proportional to D(x)².

4) Repeat until k centroids are chosen.

This tends to reduce bad starts and usually improves results with minimal overhead.

Choosing k (model selection)

K-means requires k upfront, which is often the hardest practical choice.

Common heuristics:

• •Elbow method: plot WCSS(k) = ∑ᵢ ‖xᵢ − μ_{cᵢ}‖₂² vs k. Look for a point where improvements diminish (“elbow”).
• •Silhouette score: compares within-cluster tightness vs separation.

Silhouette score (intuition)

For a point i:

• •aᵢ = average distance to points in its own cluster
• •bᵢ = minimum (over other clusters) of average distance to that cluster

Silhouette:

sᵢ = (bᵢ − aᵢ) / max(aᵢ, bᵢ)

• •sᵢ ≈ 1: well-clustered
• •sᵢ ≈ 0: on the boundary
• •sᵢ < 0: possibly misassigned

Average sᵢ over i gives a score for k.

Scaling features (often the make-or-break detail)

K-means uses Euclidean distance, so feature scaling matters.

If one feature has a large numeric range, it dominates distances.

Typical fix: standardize each feature:

x' = (x − mean) / std

Without scaling, you may cluster by “units” rather than by actual structure.

When K-means is a good fit

• •Clusters are compact and roughly spherical in Euclidean geometry.
• •Similar cluster sizes and densities.
• •You want speed on large n.

When K-means struggles

• •Non-spherical clusters (rings, spirals).
• •Unequal densities (dense + sparse).
• •Outliers (can drag centroids).
• •Categorical features without a meaningful Euclidean embedding.

K-means is a sharp tool—but it’s sharp in a particular shape. Next we’ll study hierarchical clustering, which often provides more flexibility and interpretability via a dendrogram.

Hierarchical clustering builds a nested family of clusters rather than committing to a single partition with a fixed k.

Why hierarchical clustering (motivation)

Sometimes you don’t believe the data has one “correct” k. Instead, you might believe there are multiple meaningful scales:

• •At a coarse level: 2–3 big groups.
• •At a fine level: subtypes within each group.

Hierarchical clustering captures this by producing a dendrogram (a tree) that shows how clusters merge (or split) as you change the similarity threshold.

There are two main variants:

• •Agglomerative (bottom-up): start with each point as its own cluster, repeatedly merge.
• •Divisive (top-down): start with all points in one cluster, repeatedly split.

Agglomerative clustering is more common in practice, so we’ll focus on it.

The agglomerative algorithm (conceptual steps)

1) Start with n clusters: { {1}, {2}, …, {n} }

2) Compute distances between clusters using a linkage rule

3) Merge the two closest clusters

4) Update distances and repeat until one cluster remains

The output is a dendrogram. To get a final clustering, you cut the dendrogram at a chosen height (distance threshold) or choose a number of clusters.

Distances between clusters: linkage

Hierarchical clustering needs a distance between sets of points (clusters), not just between individual points.

Let A and B be two clusters.

Common linkage rules:

Ward’s linkage (connection to variance minimization)

Ward’s method chooses the merge that causes the smallest increase in total within-cluster sum of squares.

If you define the within-cluster SSE for a cluster C with centroid μ_C:

SSE(C) = ∑_{x∈C} ‖x − μ_C‖₂²

Ward chooses to merge A and B that minimize:

Δ(A,B) = SSE(A∪B) − SSE(A) − SSE(B)

This makes hierarchical clustering feel more “k-means-like,” but it still yields a full hierarchy.

Reading a dendrogram (what it actually tells you)

In a dendrogram:

• •Leaves are individual points.
• •A merge happens at a certain height h representing distance (or dissimilarity) at which the merge occurs.

A “natural” clustering often appears as:

• •many merges at low heights (tight subclusters)
• •then a noticeable jump to higher heights (merging distinct groups)

Cutting the tree at a height between those regimes yields a partition.

Complexity and scaling

Hierarchical clustering is typically more expensive than k-means:

• •Naive implementations can be O(n³).
• •Common optimized implementations are around O(n²) time and O(n²) memory due to the distance matrix.

So it’s often used for:

• •smaller datasets (n up to a few tens of thousands, depending on memory)
• •scenarios where interpretability of the dendrogram is valuable

Distance metrics still matter

Hierarchical clustering can use many distances:

• •Euclidean: ‖x−y‖₂
• •Manhattan: ‖x−y‖₁
• •Cosine distance: 1 − (x·y) / (‖x‖₂ ‖y‖₂)

Different distances can change the dendrogram dramatically. Scaling features is still crucial whenever numeric ranges differ.

Strengths and weaknesses vs K-means

Hierarchical clustering:

• •does not require choosing k upfront
• •can reveal multi-scale structure
• •can work with many distance measures

But:

• •is slower and heavier in memory
• •can be sensitive to noise/outliers (especially complete linkage)
• •once a merge is done, it can’t be undone (greedy)

K-means:

• •scales well
• •is simple

But:

• •requires k upfront
• •assumes centroid-like clusters

You’ll often try both: use hierarchical clustering to understand structure (choose k), then run k-means for a scalable final partition.

Clustering algorithms always produce some grouping—even on random noise. The real skill is building a workflow that makes clusters meaningful and defensible.

1) Clarify the goal

Different goals imply different choices:

• •Segmentation (e.g., customers): interpretability matters; stable clusters matter.
• •Compression (e.g., vector quantization): objective value matters.
• •Exploration (e.g., embeddings): you want clusters that align with semantic neighborhoods.

Ask: what would count as a “good” cluster in your domain?

2) Choose a representation

Raw features might not reflect similarity.

Examples:

• •Text: TF-IDF vectors or embedding vectors
• •Images: CNN embeddings
• •Graph nodes: node embeddings

Clustering works best when your representation makes “similarity” meaningful geometrically.

3) Scale / normalize

If using Euclidean distance, scale each feature to comparable units.

Typical options:

4) Pick an algorithm and distance

A useful mental map:

(There are other families like DBSCAN, GMMs, spectral clustering, but this node focuses on K-means + hierarchical.)

5) Choose k or a cut

For K-means

• •Try several k values.
• •Use elbow + silhouette.
• •Check stability across random seeds.

For hierarchical

• •Cut at a height where merges start jumping.
• •Or choose number of clusters by cutting to k leaves.

6) Validate: internal, stability, and external checks

Validation is not just a single number.

Internal metrics (no labels)

• •Silhouette: compares cohesion vs separation.
• •Davies–Bouldin: lower is better (cluster scatter vs separation).

Internal metrics can be misleading if your distance metric doesn’t match your semantic goal.

Stability checks

Run clustering under perturbations:

• •different random seeds (k-means)
• •bootstrap samples
• •small noise added to features

If cluster assignments drastically change, the structure may be weak.

External checks (domain-based)

Even without labels, you can often check:

• •Are clusters interpretable? (summary statistics)
• •Do clusters correlate with known attributes? (e.g., geography, device type)
• •Are clusters actionable? (different behaviors, different outcomes)

7) Interpret clusters

For each cluster j, compute:

• •size |Cⱼ|
• •centroid μⱼ
• •feature means / medians
• •representative points (closest to μⱼ)

Interpretation is often the main product of clustering.

8) Common failure modes (so you can detect them)

• •Scaling failure: one feature dominates distance.
• •Wrong k: k too small merges distinct groups; k too large fragments groups.
• •Outliers: centroids pulled; complete linkage distorted.
• •Non-spherical geometry: K-means splits one curved cluster into multiple.
• •High-dimensional distance concentration: distances become similar; clusters less distinct.

A practical mitigation in high dimensions is to reduce dimension first (e.g., PCA) for clustering—carefully, because projections can also distort structure.

Connection between K-means and hierarchical (a useful mental bridge)

• •K-means optimizes a fixed-k objective (SSE).
• •Ward hierarchical greedily merges clusters to control SSE increases.

So if you think “variance within clusters” is the right notion, both methods can align:

• •Use Ward dendrogram to pick k.
• •Then run K-means with that k for scalability.

The core professional habit: treat clustering as an iterative scientific process, not a one-click algorithm.