The K-Means Objective and Its Geometry

What the K-Means Objective Measures

A clustering is useful only relative to the feature space and criterion used to define it. K-means uses a particular geometric criterion: it seeks groups whose profiles lie close to their group means, with closeness measured by squared Euclidean distance. The objective is therefore a measure of within-cluster variation, not a probability model and not a direct measure of biological similarity.

Suppose \(x_1,\ldots,x_n\) are complete profile vectors in \(\mathbb{R}^p\), where each coordinate is a measured or transformed feature, and let \(K\) be a chosen integer with \(1\leq K\leq n\). All coordinates must be represented in a common Euclidean space. A clustering into \(K\) groups is a partition \(C_1,\ldots,C_K\) of the observations: each observation belongs to exactly one group, and each group is nonempty. The Euclidean squared distance between vectors \(x\) and \(y\) is \(\|x-y\|^2=\sum_{j=1}^{p}(x_j-y_j)^2\).

The objective gives every observation equal weight and squares every coordinate difference. Thus a few large deviations can contribute substantially, and features with large numerical scales can dominate unless the scale is scientifically appropriate or the data have been transformed. In genomic profiles, the coordinates might be normalized expression measurements or other profile features; the objective itself does not decide how those features should be prepared.

Why the Centroid Is the Mean

The centroid is not simply a convenient representative. For squared Euclidean distance, the arithmetic mean is the point that minimizes the total squared distance from the observations in a fixed cluster. This fact explains why the objective uses centroids and is central to its geometry.

To verify the result, write \(x_i-c=(x_i-\bar{x})+(\bar{x}-c)\), square the norm, and sum over the cluster. The cross-term vanishes because the deviations from the mean sum to zero:

The final term is nonnegative and equals zero at \(c=\bar{x}\), proving the claim. For a fixed partition, the best possible representative for each cluster is therefore its centroid. This is a statement about squared Euclidean loss; with a different loss, the best representative can differ.

Nearest Centers and Voronoi Geometry

For a fixed set of centers \(c_1,\ldots,c_K\), the squared-distance rule assigns a profile to a closest center. The region of space closest to a given center is its Voronoi region. These regions are separated by boundaries where distances to two or more centers are equal. For distinct centers in ordinary Euclidean space, each pairwise equal-distance locus is a hyperplane, and each Voronoi region is an intersection of the corresponding half-spaces, hence is convex. The shared boundary for a pair of regions may be empty; when nonempty, it is a portion of the corresponding hyperplane.

For two centers \(c_a\) and \(c_b\), equality of squared distances gives a useful boundary equation. Expanding both sides and cancelling \(x^\mathsf{T}x\) yields

This equation describes a hyperplane perpendicular to the line joining the centers. If the centers coincide, their distance comparisons tie everywhere; distinct centers give the usual separating boundary. Importantly, nearest-center assignment is a rule for fixed centers. If some center has no observations assigned to it, the induced assignment is not a partition into \(K\) nonempty clusters; its Voronoi region may nevertheless contain observed profiles tied with another center.

Comparing Candidate Partitions

A WCSS value is meaningful only in relation to a specified coordinate system, value of \(K\), and partition. For a fixed data set and \(K\), a lower value is better according to this objective. It does not establish that the groups are biologically real or that the chosen \(K\) is appropriate. In particular, adding groups cannot increase the best attainable WCSS: a group can be split into nonempty subsets, and re-centering those subsets cannot increase the sum of squared distances. This monotonicity means WCSS alone cannot choose \(K\).

Assumptions, Diagnostics, and Alternatives

The k-means objective is deterministic: it requires no sampling distribution or independence assumption to be calculated. Its interpretation nevertheless relies on substantive choices. Each observation must have comparable meaning in a common coordinate system, the selected distance must reflect relevant differences, and equal observation weights must be defensible. Squaring makes the criterion especially sensitive to extreme profiles. If one coordinate has a much larger scale or variance than others, it can dominate distances; centering and scaling may address scale differences, but should be chosen based on the scientific meaning of the measurements, not applied mechanically.

The geometry also constrains the kinds of groupings the objective favors. Nearest-centroid regions are convex, and the squared-distance criterion tends to favor compact groups around their means. It can represent awkwardly shaped or strongly overlapping groups poorly. In high dimensions, distance concentration can make pairwise distances less discriminating, so a nearest-center assignment may convey less separation than the low-dimensional picture suggests. A low WCSS is not a guarantee of stable assignments, meaningful separation, or useful biological interpretation.

Useful checks include confirming that the input coordinates and scaling are as intended, inspecting whether a small number of profiles or features dominate the squared deviations, and examining whether assignments depend on a narrow distance margin between competing centers. A profile exactly on a Voronoi boundary is tied; a profile nearly on one may be sensitive to small changes. Also inspect for empty groups when translating centers into assignments. These checks diagnose aspects of the criterion and its geometry; they do not replace a separate assessment of whether the resulting clusters answer the scientific question.

Alternative clustering criteria encode different preferences. A medoid-based criterion uses an observed profile as a representative rather than the coordinate-wise mean, and can be less affected by an extreme profile. Hierarchical methods define groups through a distance-and-linkage rule rather than by minimizing this centroid-based WCSS. Probabilistic mixture models describe profiles through distributions and quantify uncertainty differently. These approaches do not simply provide interchangeable calculations of the same quantity: they answer different modeling or geometric questions. The appropriate choice depends on the profile representation and scientific aim.