Cluster Analysis

In-depth Articles

Introduction

Cluster analysis is a fundamental task in unsupervised learning: the goal is to group observations into clusters such that within-cluster similarity is high and between-cluster similarity is low. Unlike supervised methods, there are no labels to guide the process — the algorithm must discover structure in the data on its own.

Applications include:



Distance Measures

The choice of distance metric fundamentally determines what "similar" means. Common measures include:

Euclidean Distance

The most common distance in continuous spaces:

\[ d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{i=1}^{p} (x_i - y_i)^2} \]

Manhattan Distance

Sum of absolute differences along each dimension:

\[ d(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^{p} |x_i - y_i| \]

Minkowski Distance

A generalization of both Euclidean (\(q=2\)) and Manhattan (\(q=1\)):

\[ d(\mathbf{x}, \mathbf{y}) = \left( \sum_{i=1}^{p} |x_i - y_i|^q \right)^{1/q} \]

Cosine Similarity

Measures the angle between two vectors, ignoring magnitude:

\[ \text{cos}(\mathbf{x}, \mathbf{y}) = \frac{\mathbf{x} \cdot \mathbf{y}}{\|\mathbf{x}\| \, \|\mathbf{y}\|} = \frac{\sum_{i=1}^p x_i y_i}{\sqrt{\sum_{i=1}^p x_i^2} \sqrt{\sum_{i=1}^p y_i^2}} \]

The cosine distance is then \(1 - \text{cos}(\mathbf{x}, \mathbf{y})\).

Correlation-Based Distance

\[ d(\mathbf{x}, \mathbf{y}) = 1 - \text{corr}(\mathbf{x}, \mathbf{y}) \]

Useful when the pattern of variation matters more than absolute values.

Standardization

The choice of distance depends on data type and scale. When features have different units or scales, standardization (e.g. z-score normalization) is critical — otherwise features with larger ranges will dominate the distance computation.



K-Means Clustering

Algorithm

K-Means partitions \(n\) observations into \(K\) clusters by iterating:

  1. Initialize \(K\) centroids (randomly or via K-means++)
  2. Assign each observation to the nearest centroid
  3. Recompute each centroid as the mean of its assigned points
  4. Repeat steps 2–3 until convergence (assignments no longer change)

Objective Function

K-Means minimizes the total within-cluster sum of squares:

\[ W(C) = \sum_{k=1}^{K} \sum_{\mathbf{x} \in C_k} \|\mathbf{x} - \boldsymbol{\mu}_k\|^2 \]

where \(\boldsymbol{\mu}_k = \frac{1}{|C_k|}\sum_{\mathbf{x} \in C_k} \mathbf{x}\) is the centroid of cluster \(C_k\).

Properties

  • The algorithm is guaranteed to converge, but only to a local minimum — the result depends on initialization
  • Use multiple random starts and select the solution with lowest \(W(C)\)
  • Assumes spherical, equally-sized clusters

Choosing K

  • Elbow method: plot \(W(C)\) vs \(K\) and look for the "elbow" where marginal decrease flattens
  • Silhouette score: choose \(K\) that maximizes the average silhouette width
  • Gap statistic: compare \(\log W(C)\) to the expected value under a null reference distribution (uniform)


Hierarchical Clustering

Agglomerative (Bottom-Up)

Start with \(n\) clusters (one per observation). At each step, merge the two closest clusters. Repeat until a single cluster remains.

Divisive (Top-Down)

Start with one cluster containing all observations. At each step, split a cluster into two. Less common in practice.

Linkage Methods

The definition of "distance between clusters" varies by linkage:

  • Single linkage: \(d(A,B) = \min_{a \in A, b \in B} d(a,b)\) — minimum distance (tends to produce elongated chains)
  • Complete linkage: \(d(A,B) = \max_{a \in A, b \in B} d(a,b)\) — maximum distance (produces compact clusters)
  • Average linkage: \(d(A,B) = \frac{1}{|A||B|}\sum_{a \in A}\sum_{b \in B} d(a,b)\)
  • Ward's method: merge the pair that minimizes the increase in total within-cluster variance: \[ \Delta W = \frac{|A| \cdot |B|}{|A|+|B|} \|\boldsymbol{\mu}_A - \boldsymbol{\mu}_B\|^2 \]

Dendrogram

A tree diagram representing the nested sequence of merges. The height at which two clusters merge reflects the dissimilarity between them. Cut the dendrogram at a desired height to obtain \(K\) clusters.



DBSCAN

Density-Based Spatial Clustering of Applications with Noise.

Key Concepts

  • Core point: a point with at least \(\text{minPts}\) neighbours within radius \(\varepsilon\)
  • Border point: within \(\varepsilon\) of a core point but does not have \(\text{minPts}\) neighbours itself
  • Noise point: neither core nor border — not assigned to any cluster

Algorithm

  1. Find all core points
  2. Form clusters by connecting core points that are within \(\varepsilon\) of each other (density-reachable)
  3. Assign each border point to the cluster of its nearest core point
  4. Label remaining points as noise

Advantages

  • Discovers clusters of arbitrary shape (not just spherical)
  • Detects outliers naturally as noise points
  • No need to specify \(K\) — the number of clusters is determined by the data

Parameters

  • \(\varepsilon\) (eps): neighbourhood radius — can be tuned using a k-distance plot
  • \(\text{minPts}\): minimum number of points to form a dense region — rule of thumb: \(\text{minPts} \geq p + 1\) where \(p\) is dimensionality


Evaluation Metrics

Internal: Silhouette Coefficient

For each observation \(i\):

\[ s(i) = \frac{b(i) - a(i)}{\max\{a(i),\, b(i)\}} \]

where:

  • \(a(i)\) = mean distance from \(i\) to all other points in the same cluster (intra-cluster distance)
  • \(b(i)\) = mean distance from \(i\) to all points in the nearest neighbouring cluster

Range: \([-1, 1]\). Values near 1 indicate well-clustered points; near 0 means on the boundary; negative values suggest misclassification.

External Metrics (when true labels are available)

  • Adjusted Rand Index (ARI): measures agreement between predicted and true clustering, adjusted for chance. Range \([-1, 1]\), with 1 = perfect agreement.
  • Normalized Mutual Information (NMI): measures the mutual information between predicted and true labels, normalized to \([0, 1]\).


Practical Guidelines