What a Distance Function Decides About Cluster Shape

Clustering algorithms rarely define similarity themselves. They take a distance function and a data matrix, and the resulting groups are determined as much by the distance as by the procedure. Running a centroid method twice on the same matrix with two different metrics produces two different partitions of the same points, and neither is more correct than the other: the metric is the definition of what counts as close. Because the definition is usually implicit in a default, it is worth understanding what each common choice assumes and where it stops being usable.

Squared Euclidean distance and the shape it imposes

Squared Euclidean distance treats every coordinate as an independent axis with unit variance and equal weight. Under that distance the nearest-centroid regions are Voronoi cells, so clusters are convex, roughly spherical, and equally sized in the sense that the objective penalizes a large radius quadratically. Those properties are baked into the objective examined in Lloyd’s Algorithm and the Local Minima of k-Means long before any iteration runs.

The axes are not commensurate. Squared distance sums sum_j (x_j - y_j)^2, so a feature measured in millimetres contributes a factor of one million more than the same feature expressed in metres. If two features describe the same quantity at different scales, the larger-scale one dominates and the smaller one is nearly invisible. Standardizing each feature to zero mean and unit variance removes the unit dependence, and standardizing is exactly the choice of a diagonal metric D = diag(1/sigma_j^2), because sum_j (x_j - y_j)^2 / sigma_j^2 is the distance in the scaled coordinates.

Constant shifts and orthonormal transforms of the whole feature space leave the partition unchanged: rotating or translating all points trades no ordering among distances. Arbitrary linear maps do not have that property. A non-orthogonal map changes relative distances and can change the partition, which is the precise statement of why feature weighting alters clustering rather than merely preprocessing it.

Mahalanobis distance and the case for decorrelation

Correlated features carry redundant information, and squared Euclidean distance counts the redundancy twice. Mahalanobis distance divides by the covariance: d(x, y)^2 = (x - y)^T S^{-1} (x - y). If S is the identity the distance reduces to Euclidean; if S is diagonal the distance is a per-feature weighting. Choosing S as the sample covariance is equivalent to whitening the data, that is, applying S^{-1/2} to the matrix, then running the same algorithm in the whitened space.

The catch is estimation. A general d by d covariance matrix has d(d+1)/2 free parameters, so it needs a sample count well above d to be stable, and inverting a nearly singular S amplifies noise along the poorly observed directions. That inverts the usual intuition that more features are better: with d = 200 there are 20,100 covariance entries to estimate. Practical alternatives are a shrunk covariance (a convex blend of S with a diagonal target), a diagonal metric, or per-cluster covariances in a model-based method, as in Gaussian Mixture Models and the EM Lower Bound.

Cosine similarity lives on the unit sphere

Cosine similarity divides the inner product by both norms, discarding magnitude entirely. On unit-norm vectors the relationship to Euclidean distance is exact: ||x - y||^2 = 2 (1 - x . y) = 2 (1 - cos). Assignment by nearest centroid under squared Euclidean distance is therefore identical to assignment by maximum cosine similarity, provided both the data and the centroids lie on the unit sphere.

The centroids do not naturally lie there. The mean of unit vectors has norm at most 1, with equality only when the vectors coincide, so a Euclidean update places the centroid strictly inside the sphere. Spherical k-means normalizes the centroid after each update, which makes the update step a maximization of the summed cosine similarity rather than a least-squares mean. That change means the monotone-descent property of the plain algorithm holds for the spherical objective, not for the squared-distance objective.

Discarding magnitude is the point of cosine distance and also its hazard. Two count vectors that differ only by a factor of two have cosine distance zero, while Euclidean distance separates them by a wide margin. Normalizing term-frequency vectors before comparison therefore declares document length irrelevant, which is appropriate for topical similarity and wrong if the length itself is meaningful. Cosine distance is also not a metric on unnormalized vectors: for x = (1,0), y = (0,1), z = (1,1) the distances are 1, 0.293, and 0.293, so the triangle inequality fails by a wide margin. Restricting to unit vectors repairs this, because the distance is then a monotone function of Euclidean distance.

Sets, counts, and mixed-type data

For binary data the natural comparison is the Jaccard coefficient, the size of the intersection over the size of the union, with distance 1 - J. It counts joint presence and ignores joint absence, which is what distinguishes it from Hamming distance on the same vectors. Hamming distance is the basis of the k-modes algorithm, which replaces the mean with the per-feature mode and the squared distance with the count of mismatching features; k-prototypes blends that with a squared Euclidean term on the numeric features through a weight on the categorical part. Both are optimizations of a different objective from the k-means one, and neither inherits the least-squares derivation.

Mixed numeric and categorical tables are often handled with Gower’s coefficient, which averages per-feature similarities: range-normalized differences for numeric features and exact match indicators for categorical ones. The result is a legitimate similarity, and it can be plugged into methods that only consume a pairwise matrix, such as average-linkage agglomerative clustering described in Agglomerative Clustering and the Lance-Williams Recurrence. It cannot be plugged into a centroid method, because the average of a set of Gower similarities is not the distance from any representable point; the centroid update has no meaning for a metric that is not induced by an inner product.

Distance concentration in high dimensions

Under independent attributes with bounded moments, the distance to the nearest neighbour and the distance to the farthest neighbour converge to the same value as the dimension grows. More precisely, the spread (max_i d_i - min_i d_i) / min_i d_i over a sample tends to zero in probability under conditions on the distribution, so a nearest neighbour becomes only marginally nearer than the rest of the sample. Every radius-based method inherits the consequence: a threshold chosen for a neighbourhood no longer separates neighbours from non-neighbours, and a bandwidth tuned at low dimension over-smooths at high dimension.

The effect is not uniform across metrics. Manhattan distance behaves differently from Euclidean distance on high-dimensional sparse data because it sums absolute deviations instead of squares, so a few large coordinate differences stand out less sharply against a background of many small ones; distances with an exponent below 1 behave differently again, at the cost of losing the triangle inequality that index structures and guarantees rely on. Common mitigations are to remove uninformative coordinates, to reduce dimension first with a linear projection, or to drop the global radius in favour of adaptive neighbourhoods, the direction taken by density-based methods.

Whichever metric is chosen, two checks are cheap and informative. Distances should be computed to the same effective scale for all features, whether by standardization, by an explicit weighting, or by a whitening transform. And the metric has to match the geometry the algorithm assumes: an objective written in terms of means requires a space where means exist, and a rejection threshold written in terms of a fixed radius requires distances that do not collapse as dimensionality grows.