K-Means clustering: a practical guide to initialisation
K-Means clustering turns unlabelled observations into k groups by repeatedly assigning each point to its nearest group centre. That centre, called a centroid, is the mean of the points currently assigned to it. The method suits numeric features such as spending, distance travelled or monthly usage, making it useful for customer segmentation, image compression and exploratory analysis. Understanding initialization explains why identical data can yield different groupings on separate runs.
The algorithm is easy to summarise, but its assumptions matter. It favours compact, roughly spherical groups measured with squared Euclidean distance, and it converges to a local solution rather than necessarily the best possible partition. Scaling, outliers, the number of groups and the starting centroids all influence the outcome. The following explanation connects these mechanics to practical choices about reproducibility, validation and Australian data contexts.
From observations to centroids
Imagine representing each shopper by annual spend, average basket size and the proportion of fresh-produce purchases. K-Means seeks k centroids that minimise the total squared distance between each shopper and their assigned centroid. Patterns close to one centre form a group, and that centre becomes the arithmetic mean of the group’s feature vectors. Unlike supervised classification, the resulting labels have no pre-existing meaning and can change between runs. The algorithm catalogue places the method alongside related techniques for exploring data.
The objective can be written as (\sum_{i=1}^{n}\sum_{j=1}^{k}\lVert x_i-c_j\rVert^2), where (x_i) is an observation and (c_j) is a centroid. Each iteration has an assignment step, which gives every point to its closest centroid, and an update step, which replaces each centroid with its assigned points’ mean. A point’s cluster identity depends on the current centres, so a small centroid movement can redirect points near a boundary.
Consider three centroids placed among two-dimensional points. Points near the horizontal divide might be sent left, while points just above it might be sent upward when the centroids shift. Updating the means then changes those distances. Repeating this assignment-and-update cycle produces stable groups once the assignments and centroids stop changing, subject to the maximum iteration limit.
Why the starting points matter
A poor initialisation can leave centroids crowded together, allowing one region to attract points that would otherwise form a separate cluster. K-Means then converges to a local optimum: a stable arrangement whose within-cluster sum of squares is lower than nearby alternatives, but not necessarily the lowest possible value. Different starts can therefore produce different group sizes and boundaries. Setting a fixed random seed makes a run reproducible; it does not remove the algorithm’s sensitivity to its initial centres.
K-means++ offers a more deliberate seeding strategy. The first centre is selected uniformly at random from the observations. Each later centre is chosen with probability proportional to the squared distance from a point to its nearest existing centre. In practical terms, points in poorly represented regions receive a larger chance of becoming the next centre, spreading the starting set across the data. This usually avoids the crowded-centre problem and reduces the likelihood of a poor local optimum.
The improved spread is not a guarantee of the global optimum. Several restarts remain sensible, especially with elongated or unevenly populated groups. A useful workflow is to standardise the features, run K-means++ with multiple initialisations, and compare the resulting objective values. Manually chosen centres can also encode useful domain knowledge, but they introduce bias and should be documented rather than presented as neutral defaults.
Running the algorithm carefully
Start with k centroids, assign every observation to its nearest centroid, recompute each centroid as the assigned points’ mean, and repeat until the assignments stabilise or a maximum iteration count is reached. This is Lloyd’s algorithm. The objective cannot increase under an exact update, so the process eventually settles on a stable partition for the chosen centres and tie-breaking rules. If a cluster receives no points, implementations commonly relocate its centre to the point farthest from its current centre or retain the previous position.
In Python’s scikit-learn, KMeans exposes these choices through parameters such as init, n_init, random_state, max_iter and tol. Use init="k-means++" for the distance-weighted seeding described above, and let n_init try multiple starts before selecting the lowest objective value. Standardise features with comparable units before clustering; otherwise, a variable measured in thousands can dominate one measured in tens. Nominal categories need suitable transformations rather than arbitrary integer codes, which would imply an ordering that does not exist.
The distance calculations cost (O(nkd)) per iteration, where (n) is the number of observations, (k) the number of clusters and (d) the number of features. Over (t) iterations, the main computational cost is (O(nkd t)), with memory use depending on the implementation. For contrast with another parallel workload, the site’s bitonic sorting guide explains how sorting can be divided across processors; K-Means has a different dependency because assignments rely on shared, changing centroids.
Checks for dependable clusters
Choosing (k) is a modelling decision, not a mathematical output. The elbow method looks for a bend in the objective-value curve, while the silhouette score rewards separation and compactness across candidate values of (k). Neither guarantees useful groups, so include domain requirements and test whether alternative values produce decisions that make sense. A cluster that merely separates high-value shoppers from everyone else may be less informative than several segments with distinct needs.
Before fitting the model:
- Standardise numeric features and confirm that every distance has a meaningful interpretation.
- Record the random seed, initialisation method and number of restarts for reproducibility.
- Inspect missing values, duplicates and extreme observations before assigning them to groups.
- Decide how (k) will be justified using validation evidence and domain constraints.
After fitting the model:
- Compare centroid profiles and sample members to identify what distinguishes each group.
- Check cluster sizes, boundaries and sensitivity to resampling or different seeds.
- Plot the groups in two dimensions or use another visualisation that reveals their shape.
- Compare the segmentation with a simple business or operational baseline.
Interpretation needs care. Centroids describe average feature combinations, not causes. A segment labelled “budget commuters” is simply a shorthand for members whose features resemble one another; it does not prove that price caused their travel behaviour. Validate patterns against later observations, document limitations and involve people familiar with the domain before acting on the groups.
Applying the method in Australian settings
A transport team in Sydney could hypothetically cluster aggregated Opal card journeys by departure time, route length and frequency of travel. Similar summaries from Melbourne’s Myki network could support broader comparisons across metropolitan travel patterns. K-Means might reveal recurring commuter profiles, such as frequent short trips or occasional long trips, without identifying individual passengers. Aggregated records would still need appropriate governance, and the result should not be treated as proof of commuter motivation.
For consumer analysis, Woolworths and Coles dominate Australia’s supermarket market, so hypothetical basket features might include spend, visit frequency, fresh-produce share and time since the previous purchase. Before analysing customer-level records, teams should check obligations under the Privacy Act 1988 and the Australian Privacy Principles. The Act includes a small-business exception for some organisations, but an exception to a privacy obligation is not a general guarantee of anonymity. Clustering personal information does not remove privacy responsibilities.
Australia’s voluntary 2019 AI Ethics Principles provide another reference point, emphasising transparency, fairness and accountable use. Cluster labels should therefore be checked for unintended impacts, especially when decisions affect access to services. The about hello ML page describes the community behind this educational resource, aligning naturally with an approach that values clear explanations, shared knowledge and scrutiny of assumptions.
A compact comparison makes the trade-offs clearer:
| Initialisation method | Strength | Limitation | Best fit |
|---|---|---|---|
| Uniform random | Simple and unbiased by hand-chosen locations | Can create crowded or unlucky centres | Baseline testing |
| K-means++ | Spreads centres using distance weighting | Still stochastic and not globally optimal | Most general-purpose use |
| Farthest-first | Strongly separates early centres | Sensitive to outliers and the first point | Small, well-behaved datasets |
| Domain-informed | Incorporates known meaningful starting points | Can bias results toward expectations | Strong subject expertise available |