Machine Learning
Initialization
KMeans uses k-means++ as the default initialization method.
Why initialisation matters
Lloyd's algorithm depends on the initial centres. A bad start (for example two centres landing in the same real cluster) gets stuck in a local optimum: one cluster is split in two, two clusters are merged.
for rs in range(3):
km = KMeans(n_clusters=5, init="random", n_init=1, random_state=rs).fit(X)
print(rs, round(km.inertia_)) # a different result per seed
That's why the initialisation method and the number of repeats are KMeans's most important settings.
k-means++
scikit-learn's default initialisation is k-means++: the first centre is chosen at random, and each following centre is chosen from points far from the existing centres, with probability proportional to the squared distance. The centres start spread out:
km = KMeans(n_clusters=5, init="k-means++", n_init=1, random_state=0)
# init="random": uniformly at random among the examples
k-means++ gives both a better solution and usually fewer rounds.
Exercise Compare initialisations
For seeds 0-9, train a n_init=1 KMeans (5 clusters) with init="random" and with init="k-means++". Print the worst (largest) inertia for each method as integers with round on one line (random first).
Show example solution
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
X, _ = make_blobs(n_samples=500, centers=5, cluster_std=1.0, random_state=3)
kotu = []
for init in ["random", "k-means++"]:
kotu.append(round(max(KMeans(n_clusters=5, init=init, n_init=1, random_state=rs).fit(X).inertia_ for rs in range(10))))
print(*kotu)
Test yourself
-
What is the typical failure of random initialisation?
- Raising an error
- Two centres landing in the same cluster
- The algorithm not converging
- Centres being deleted
Show answer
Two centres landing in the same cluster — In that case one real cluster is split and two clusters elsewhere are merged.
-
Initialise the centres spread out.
km = KMeans(n_clusters=5, init=____)
Show answer
km = KMeans(n_clusters=5, init="k-means++")
-
Match the initialisations.
- init="random"
- Uniform random examples
- init="k-means++"
- Choice proportional to distance
- bad initialization
- Local optimum
- n_iter_
- Rounds needed
Next lesson: n_init
