MerQuR+Statistics Glossary

Statistics Glossary → K-Means Clustering

K-Means Clusteringanalysis

An exploratory clustering method that divides observations into a pre-set number (K) of groups so that each observation is as close as possible to the centre of its own cluster.

Concept

Clustering aims to divide observations whose groups are not known in advance into natural groups based on their similarity; there is no outcome variable to predict. K-means is the most widely used method for this: it answers the question 'how can these observations be split into K groups that are alike within and distinct between?', and is used for grouping regions, customers, species or profiles.

The algorithm starts by choosing K centres and repeats two steps: each observation is assigned to the nearest centre, then each centre is moved to the mean of the observations in its cluster. It stops when the assignments no longer change. This process reduces the within-cluster sum of squares, the sum of the squared distances of each observation from its own centre: WSS = Σ_k Σ_{i∈k} ‖x_i − centre_k‖². Because the result may be a local optimum that depends on the starting centres, the algorithm is run from many starts and the solution with the smallest WSS is kept. K-medoids (PAM) uses an actual observation in the cluster as the centre instead of the mean, and is less affected by outliers.

The method implicitly assumes that clusters are roughly spherical and of similar size; it cannot separate elongated, winding or very differently dense clusters well. Because distances rest on the measurements, the variables should usually be standardised. K-means always produces K clusters, even when the data have no real group structure; the choice of K should therefore be supported by criteria such as the silhouette and the gap statistic, and the meaning of the clusters checked against subject knowledge. ANOVA on the clusters is descriptive; since the clusters were formed from the same variables, its p values should not be read as a genuine test.

When to use it

  • When many observations measured on continuous variables are to be split into groups of similar profile whose number can be roughly guessed (customer segments, region types, student profiles).
  • If there is no idea about the number of clusters and the nested structure between groups is of interest, hierarchical clustering is preferred; if clusters are not spherical, or outliers are to be set aside as noise, DBSCAN/HDBSCAN.
  • If the variables are categorical, latent class analysis is more suitable; for probability-based membership and model comparison with continuous indicators, latent profile analysis.

An everyday example

A sports club wants to split 120 young athletes into three training groups based on their 30-metre sprint time, vertical jump height and strength test results. K-means first picks three random 'example athletes', assigns everyone to the example they most resemble, then takes each group's average profile as the new example, and repeats until the groups stop changing. In the end three groups emerge, for example 'fast but weak', 'strong but slow' and 'average across the board', and the coaches can give each group a different programme.

Parameters in MerQur

Number of clusters (K)

Concept: K is the number of clusters into which the data are split and is supplied by the user, not by the method. The within-cluster sum of squares always falls as K grows, so the aim is not the K with the smallest WSS but the K that gives meaningful, well-separated clusters.

Everyday example: If the club split its 120 athletes into 120 groups, everyone would sit exactly at the centre of their own group, but this would be of no use. For a club with three coaches, K = 3 is a practical starting point; if the data show four distinct profiles, that should be considered too.

What it does: The number of clusters into which the data are partitioned (2-20).

Effect on the result: All outputs (centres, SS, silhouette, CH, ANOVA).

On the validation data: (USArrests, z): With the default setting MerQur finds the global solution at K = 3 (SS 78.3233); at K = 10 with 26.2617 and at K = 20 with 11.6283 it may stay at a local optimum (the number of starts should be increased). iris (raw) at K = 2 and 3: cluster sizes 53/97 and 50/38/62; pseudo F 513.92 and 561.63.

→ Choosing the number of clusters

Initialization (k-means++ / Random)

Concept: How the algorithm picks its first centres. k-means++ picks the first centre at random and later ones by making points far from the existing centres more likely; the centres are thus spread over the data and the chance of getting stuck in a poor local solution falls.

Everyday example: If all three example athletes happen to be picked from among the fast sprinters, the first groups start out unbalanced. k-means++ tends to pick the second and third examples from profiles different from the first, so the start is more sensible.

What it does: Choice of the starting centres: k-means++ (Arthur & Vassilvitskii 2007) or K random observations.

Effect on the result: Can change only the local optimum reached.

On the validation data: USArrests K = 3: both give the same solution; iris raw K = 3: both 7885.144 (global).

→ Random starts and local optima

Missing Data (Drop (listwise) / Fill with mean / Fill with median / Fill with KNN)

Concept: Either removes observations with missing measurements from the analysis or fills the missing value with an estimate. Deleting rows shrinks the sample; filling with the mean or median reduces variability; filling from the nearest neighbours makes use of the observation's other measurements.

Everyday example: If the 6 athletes who missed the jump test through injury are deleted, the groups are built from 114 people. With KNN filling, these athletes' jump values are estimated from the average of the 5 athletes most similar to them in sprint and strength results.

What it does: Drops rows with missing values, or fills them with the column mean, the median or the mean of the 5 nearest neighbours (nan_euclidean) on the raw scale; the transformation is done after filling.

Effect on the result: n and therefore all results.

On the validation data: (airquality, 4 variables, K = 3, z): n = 111, 153, 153, 153; SS 186.0882, 300.1246, 293.9528, 281.6196.

→ Single imputation (mean, median, kNN filling)

K selection criterion (Manual (K above) / Highest mean silhouette (K=2..10) / Gap statistic (Tibshirani 2001))

Concept: Ways of choosing K from the data. The silhouette measures how well each observation fits its own cluster compared with the nearest other cluster (from −1 to 1); the gap statistic compares within-cluster spread with the spread expected in uniformly distributed random data that has no cluster structure.

Everyday example: The club checks how well the athletes fit their own groups for K = 2, 3, 4 and so on. If the average silhouette is highest at K = 3, three groups is the partition that best suits the data; the gap statistic answers 'are these groups clearly tighter than in a random set of athletes?'.

What it does: Chooses K from the data: the highest mean silhouette over K = 2..10, or the gap statistic (uniform null distribution, B = 50, the smallest k with Gap(k) >= Gap(k+1) - SE(k+1); Tibshirani et al. 2001).

Effect on the result: With manual selection K is taken from the form; with the other criteria K is selected from the data and all results are given for the selected K.

On the validation data: (USArrests): silhouette K = 2 (0.4085); gap K = 2 (Tibshirani et al. 2001 1-SE rule).

→ Choosing the number of clusters

Random seed

Concept: Fixes the choice of random starting centres, so re-running the analysis with the same seed gives the same result. If enough starts are used, the seed no longer affects the result.

Everyday example: When the coach re-runs the analysis a week later, they want the same athletes in the same groups; the same seed ensures this. If different seeds also always give the same groups, the solution is robust.

What it does: Seed of the k-means++ and random starts.

Effect on the result: Can only change the local optimum reached; with enough starts the result becomes independent of the seed.

On the validation data: USArrests K = 3, nstart 10: SS 78.4840 and 78.3564 for seeds 42 and 7 (two different local solutions); with the default nstart 25 the global solution (78.3233).

→ Random seed

Save cluster membership to the dataset

Concept: Adds each observation's assigned cluster and its distance from its own cluster centre to the dataset. Observations with a very large distance from the centre fit their cluster poorly or are outliers.

Everyday example: Each athlete's group is written into the club list. An athlete who lies very far from their group's centre, for example a talent who is both very fast and very strong, fits no group well and may be given a separate programme.

What it does: Adds the cluster number and the Euclidean distance of the observation to its own centre to the dataset.

Effect on the result: The results do not change; two columns are added to the dataset.

On the validation data: USArrests K = 3: the cluster number of each row and its distance to its own cluster centre are added to the data set.

Algorithm (K-means / K-medoids (PAM))

Concept: K-means uses the cluster mean as the cluster centre; K-medoids (PAM) uses an actual observation (the medoid) whose total distance to the other observations in the cluster is smallest. The mean shifts easily with a few extreme values, whereas the medoid is more robust.

Everyday example: If a group contains one exceptionally strong athlete, the group mean is pulled towards them. PAM instead picks the group's 'typical' athlete to represent it; because this is a real person, they can also be shown to the coaches as an example.

What it does: PAM (Kaufman & Rousseeuw 1990) uses an actual observation (medoid) instead of the centre; it is more robust to outliers.

Effect on the result: Centres, partition, SS and quality measures change; PAM is less affected by outliers.

On the validation data: USArrests K = 3 and 4, ruspini K = 4: the medoids, the objective (ruspini mean distance 11.4864), silhouette and CH are computed. In PAM the within-cluster SS is computed with respect to the medoid.

→ k-medoids (PAM)

Variable transformation (z-score / None / Range 0-1 / Maximum = 1 / SD = 1)

Concept: Because distances are computed from the measurements, if the variables are in different units the one with the largest numeric range dominates the distance. Transformations such as the z-score bring every variable onto a common scale so that all take part in the clustering with similar weight.

Everyday example: If sprint time ranges from 4 to 6 seconds and the strength test from 40 to 120 kilograms, in untransformed data the groups form almost entirely by strength. After z-scoring, a 1-second difference in speed can count as much as a 40-kilogram difference in strength.

What it does: Brings the variables to a common scale (z = (x - mean)/s, n-1).

Effect on the result: The distances and therefore the partition change; without transformation the large-scale variable (Assault) dominates.

On the validation data: (USArrests K = 3): none 47964.27 (Assault dominates); range 5.0109; maximum 3.1434 (global 3.1385); sd = z (a shift does not change the distance).

→ z-score (standardization)

Number of starts (nstart)

Concept: How many times the algorithm is restarted from different starting centres; among these, the solution with the smallest within-cluster sum of squares is reported. More starts lower the chance of getting stuck in a poor local solution.

Everyday example: The club starts the grouping 25 times with different example athletes and keeps the solution in which athletes are closest to their group centres. If this best solution turns up again and again in half of the 25 tries, the result is reliable.

What it does: Number of solutions repeated from different starting centres; the solution with the smallest within-cluster SS is reported.

Effect on the result: Few starts raise the risk of staying at a local optimum; many starts raise the chance of reaching the global solution.

On the validation data: (USArrests K = 3): 1 start 81.5933 (local optimum); 10: 78.3233; 100: 78.3233 (global). iris raw K = 3: 1 start 7885.567, 10: 7885.144 (global). The text states in how many starts the best SS was found.

→ Random starts and local optima

Maximum iterations

Concept: The maximum number of times the 'assign and update centres' steps are repeated within one start. If the limit is reached before convergence, the algorithm stops with an unfinished partition; after convergence the limit has no effect.

Everyday example: The groups usually settle within a few rounds: athletes are allocated to groups, group averages are updated, a few athletes switch groups, and finally nobody moves. If the round limit is set too low, some athletes may be left in the wrong group.

What it does: Maximum number of iterations within one start.

Effect on the result: If the limit is reached before convergence the solution changes; after convergence it has no effect.

On the validation data: 10, 300 and 2000 give the same result (the best start converges in 5 iterations; no effect).

→ Convergence and maximum iterations

K-selection criteria table and Chart

Concept: The within-cluster sum of squares (elbow plot), the silhouette and the Calinski-Harabasz index (the ratio of between-cluster to within-cluster spread) are given side by side for different values of K. In the elbow plot, the point where the decrease in WSS clearly slows down shows that further clusters bring little gain.

Everyday example: If the total WSS drops a lot from K = 2 to 3 but changes little from 3 to 4, the plot forms an elbow and three groups look reasonable. The PCA chart shows the athletes coloured by group on a two-dimensional plane, making it possible to see by eye how distinct the groups are.

What it does: SS (elbow), silhouette and Calinski-Harabasz for K = 2..10; the chart tab (observation silhouette also adds a per-cluster summary to the text; PCA changes only the chart).

Effect on the result: The solution for the selected K does not change; a K comparison table and plots are added.

On the validation data: At K = 2, 4, 5, 7 MerQur finds the global solution; at the other K values it may stay at a local solution. The per-cluster silhouette summaries are reported.

→ Choosing the number of clusters

Example on real data

Data: McNeil 1977, R datasets USArrests (50 states)

Variables: features Murder, Assault, UrbanPop, Rape (crime rates and urban population in 50 states)

  • Question: How are the 50 US states divided into three groups with similar profiles on four crime/urbanization indicators (Murder, Assault, UrbanPop, Rape)?
  • Setup: The variables were converted to z-scores (so that the large scale of Assault does not dominate); K = 3, 25 starts with k-means++. The best solution was found in 13 of the 25 starts.
  • Result: The clusters consist of 17, 13 and 20 states. Total within-cluster SS = 78.3233; the between-cluster SS explains 60.0% of the total variability.
  • Cluster quality: Mean silhouette 0.3094; a moderate structure with distinct but close clusters.
  • Descriptive: The 20-state cluster is high on all crime types (Murder mean 12.17, Assault 255.3), the 13-state cluster has low crime and low urbanization, and the 17-state cluster is urban with a medium crime level. Assault (F = 86.35) and Murder (F = 62.52) contribute most to the separation and UrbanPop (F = 11.31) least; these F values are descriptive only.
  • Limitation: k-means can get stuck at a local minimum: in USArrests at K = 3 a single start gives a worse solution with SS 81.59. Multiple starts should be used.
  • APA: k-means clustering on z-scores (K = 3, 25 starts) gave clusters of 17, 13 and 20 states; within-cluster SS = 78.32, R² = .60, mean silhouette = .31.

Related concepts

Choosing the number of clustersk-medoids (PAM)Random starts and local optimaSilhouette coefficientGap statisticSingle imputation (mean, median, kNN filling)z-score (standardization)Convergence and maximum iterations

The numbers in the examples are MerQur's output on independent, publicly available validation data; see the MerQur Technical Note for details.