Initialising k-means

Section of K-means clustering, part of Statistical learning

Type	Section
Taught in	K-means clustering
Part	Statistical learning

There is no single accepted start, and many procedures draw it at random. The initial centres may be drawn uniformly in a box that contains the data, or K of the observations may be used as the initial centres, or the observations may be split at random into K groups whose means are the start. Many other variants exist. A run is usually short, so repeat it and keep the clustering with the smallest \widetilde W. The kept value has not been shown to be the global minimum.

The objective is non-convex, and different regions of the initialisation space lead to different local minima. Descent from a fixed start is deterministic, so two starts in one region finish at the same partition, and a restart that remains in that region repeats the answer. A different local minimum requires a start in another region. Allocating every point independently at random to a cluster is a poor way to spread those starts. The K means then all lie near the centre of the sample and close to one another.

The fragment standardises the variables, tries 25 starts and retains the smallest reported within-cluster sum of squares. The default kmeans uses the Hartigan–Wong algorithm, which targets the same sum of squares and uses different updates. Specify algorithm = "Lloyd" when reproducing the alternating steps above. The iris laboratory uses the default and checks the reported objective directly.

set.seed(3006)
xs <- scale(x)                              # each column to mean 0, variance 1
fit <- kmeans(xs, centers = 3, nstart = 25) # 25 random starts, best kept
fit$tot.withinss                            # the unweighted criterion
table(fit$cluster)

Used in

Taught in K-means clustering
All 8 questions on K-means clustering

Used in

See also