Clustering: k-Means, Hierarchical & Density-Based

Clustering assigns observations to groups without target labels. There is no algorithm-independent definition of the “correct” clusters. Compact spherical groups, connected curved regions, nested taxonomies, and mixture components are different mathematical objects. Choosing an algorithm means choosing which object counts as a cluster.

k-means minimizes squared distance to centroids #

For $K$ clusters $C_1,\ldots,C_K$ with centroids $\mu_k$ , k-means minimizes inertia

J=\sum_{k=1}^{K}\sum_{x_i\in C_k}\lVert x_i-\mu_k\rVert^2.

Lloyd's algorithm alternates:

Assign each point to its closest centroid.
Replace each centroid with the mean of its assigned points.

Each step cannot increase $J$ , so the procedure converges, but generally to a local minimum. Different initializations can produce different partitions. k-means++ spreads initial centers to improve the starting geometry; multiple restarts still matter.

For one-dimensional points $0,2,8,10$ and $K=2$ , centers initialized near 0 and 10 yield clusters $\{0,2\}$ and $\{8,10\}$ with centroids 1 and 9. Inertia is $1+1+1+1=4$ . A single cluster has centroid 5 and inertia 136. This does not prove two real populations: the objective is guaranteed to improve as $K$ increases and reaches zero at one cluster per distinct point.

Because the mean minimizes squared Euclidean distance, k-means favors compact, roughly isotropic, similarly sized groups. It fails on interlocking moons, elongated structures, strong outliers, or categorical data unless representation makes Euclidean centroids meaningful.

k-prototypes combines numeric means with categorical modes #

For mixed numerical and categorical records, k-prototypes replaces each k-means centroid with a prototype containing a numeric mean and a categorical mode. A common objective is

J=\sum_{k=1}^{K}\sum_{x_i\in C_k} \left[ \sum_{j\in\mathcal N}(x_{ij}-\mu_{kj})^2 +\gamma\sum_{j\in\mathcal C}\mathbf 1(x_{ij}\ne m_{kj}) \right],

where $\mathcal N$ and $\mathcal C$ index numerical and categorical features, $\mu_{kj}$ is a cluster mean, $m_{kj}$ is a modal category, and $\gamma$ trades one categorical mismatch against squared numerical distance. Assignment to the nearest prototype followed by mean/mode updates cannot increase this objective, but—as with k-means—it reaches only a local optimum and depends on initialization.

The units of the two terms do not match automatically. Rescaling a numerical variable or changing $\gamma$ can reorganize the partition. A categorical field with many noisy levels can accumulate mismatch cost, while a high-variance numerical feature can dominate squared distance. Choose preprocessing and $\gamma$ from a stated domain interpretation or nested validation/stability study, not from a historical rule of thumb alone.

k-prototypes does not make nominal categories geometrically meaningful beyond equality versus mismatch. It treats every unequal category pair alike, cannot directly express ordered categories, and uses a single modal value even when a cluster contains meaningful subgroups. Missing values need an explicit distance/update rule rather than silent imputation. Compare against Gower-distance clustering, models for mixed data, and the option of avoiding a hard partition altogether.

Hierarchical clustering builds a nested tree #

Agglomerative clustering starts with each observation alone and repeatedly merges the closest pair of clusters. The linkage defines cluster-to-cluster distance:

single: closest pair of points; can recover chains but bridges through noise;
complete: farthest pair; favors compact groups and is sensitive to outliers;
average: average cross-cluster distance; compromises between them;
Ward: merge causing the smallest increase in within-cluster squared error; tied to Euclidean variance.

A dendrogram records merge order and heights. Cutting it at a height produces a flat partition. The height is a linkage dissimilarity, not a posterior probability or automatically a statistically significant separation. Rescaling a feature or changing linkage can reorder the whole tree.

Hierarchical methods are useful when nesting itself matters or when $K$ should be inspected at several levels. They can be computationally expensive because pairwise relationships grow quadratically without structural constraints.

Density connectivity discovers shape and noise #

DBSCAN defines a point as a core point when at least min_samples observations lie in its $\varepsilon$ -neighbourhood. Core points connected through overlapping neighbourhoods form clusters; reachable non-core points join borders; other points are labeled noise.

This finds non-convex shapes and does not require $K$ . But $\varepsilon$ sets the density scale. One value struggles when clusters have substantially different densities, and distances degrade in high dimension. HDBSCAN/OPTICS explore a range of density scales, but their stability criteria still depend on representation and neighbourhood geometry.

Representation determines the answer #

Clustering on age in years and income in dollars without scaling mostly clusters income. One-hot dimensions can overweight categorical fields with many levels. Duplicated correlated features count the same notion repeatedly. Learned embeddings import the objective and population of their upstream model.

Fit transforms on the intended reference population, record versions, and inspect nearest neighbours in original terms. If a cluster cannot be described by observable differences beyond the same features used to create it, the label may not support any decision.

Evaluation without ground truth #

Internal indices such as silhouette compare within-cluster cohesion with separation. They favor geometries aligned with their distance assumptions; a high silhouette can reject a valid curved cluster. Inertia always improves with $K$ . Visual separation after a nonlinear embedding is circular if the embedding was tuned to display separation.

Stronger evidence includes:

stability under resampling, perturbation, and reasonable preprocessing choices;
reproducibility on a later or external sample;
enrichment for outcomes not used to construct clusters;
a downstream action that performs better than using continuous features directly;
expert interpretation grounded in the generating process.

If known labels exist only for evaluation, external measures such as adjusted Rand index can compare partitions while accounting for chance. They still judge agreement with those labels, not universal truth.

Common misconceptions #

Cluster numbers are arbitrary identifiers; cluster 2 is not greater than cluster 1.
The elbow in an inertia curve is a heuristic, often without a clear bend.
Noise points in DBSCAN are not necessarily bad data; they are points outside the chosen density structure.
A Gaussian mixture component is a distributional component and may overlap; it is not the same object as a k-means Voronoi cell.
Assigning every future point to a cluster can be unsafe for transductive methods or remote points.

Clustering earns meaning from stability and use. The algorithm supplies a partition; the domain supplies the claim.