Machine Learning
KMeans algorithm
KMeans initializes k centroids randomly and updates them iteratively.
Lloyd's algorithm
The standard solution for KMeans is Lloyd's algorithm. At each step inertia either drops or stays the same; that's why the algorithm always converges, but the solution it finds may be a local optimum.
def kmeans_adim(X, merkez):
d = ((X[:, None, :] - merkez[None, :, :]) ** 2).sum(axis=2)
etiket = d.argmin(axis=1) # assignment
yeni = np.array([X[etiket == k].mean(axis=0) for k in range(len(merkez))])
return etiket, yeni # update
n_iter_ shows how many rounds were needed to converge; max_iter is the upper limit.
Distance matrix with broadcasting
The expression X[:, None, :] - merkez[None, :, :] broadcasts the shapes (n, 1, d) and (1, k, d) to (n, k, d); summing along the last axis gives each example's squared distance to each centre. It is loop-free and fast:
print(X.shape, merkez.shape) # (500, 2) (5, 2)
d = ((X[:, None, :] - merkez[None, :, :]) ** 2).sum(axis=2)
print(d.shape) # (500, 5)
You'll meet the same pattern in KNN, the RBF kernel and the attention computation.
Exercise KMeans by hand
Taking the first 5 examples as the initial centres, run Lloyd's algorithm for 10 rounds (assignment + update). Print the final inertia (sum of squared distances to the nearest centre) as an integer with round.
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)
merkez = X[:5].copy()
for _ in range(10):
d = ((X[:, None, :] - merkez[None, :, :]) ** 2).sum(axis=2)
etiket = d.argmin(axis=1)
merkez = np.array([X[etiket == k].mean(axis=0) for k in range(5)])
d = ((X[:, None, :] - merkez[None, :, :]) ** 2).sum(axis=2)
print(round(d.min(axis=1).sum()))
Test yourself
-
How does inertia change from one round to the next in Lloyd's algorithm?
- It changes randomly
- It is always constant
- It decreases or stays the same
- It always increases
Show answer
It decreases or stays the same — Neither the assignment nor the update step can increase the sum of squared distances.
-
Assign each example to the nearest centre.
etiket = d.____(axis=1)
Show answer
etiket = d.argmin(axis=1)
-
Match the pieces.
- assignment
- d.argmin(axis=1)
- update
- Cluster mean
- n_iter_
- Rounds to converge
- local optimum
- Lloyd's limitation
Next lesson: Initialization
