k-Means
A clustering algorithm that partitions data into k groups by iteratively minimizing distance to cluster centers.
Definition
k-means partitions data into k clusters, each represented by a centroid. It alternates two steps: assign each point to its nearest centroid, then recompute each centroid as the mean of its assigned points. Iterating reduces the total within-cluster squared distance until assignments stop changing.
The within-cluster sum of squares that k-means minimizes always decreases as k increases, which is why it cannot by itself tell you the right number of clusters. The elbow and silhouette heuristics look for the point of diminishing returns, but the choice remains partly a judgment.
Feature scaling is essential because k-means uses Euclidean distance, so a variable measured in large units would dominate the clustering purely by its scale. Standardizing features first is standard practice. The algorithm's speed makes it a natural first pass, but its spherical-cluster assumption means results should be checked against methods that allow elongated or nested groupings.
Algorithm
- Initialize k centroids (often with k-means++ for better starts).
- Assign points to the nearest centroid.
- Update centroids to the mean of their points.
- Repeat until convergence.
Strengths and limits
k-means is fast and simple, but it assumes roughly spherical, similarly sized clusters, is sensitive to initialization and outliers, and requires k in advance. It converges to a local optimum, so multiple restarts are common.
Why it matters
It is the most widely used clustering method and a standard baseline for segmentation and vector quantization.
Fusion connection
Kronos uses k-means to bin large simulation datasets into representative operating regimes, reducing thousands of Hyperion runs to a handful of typical cases for closer study.