Dictionary of Applied Machine Learning · clustering error
Updated on 2026-11-19
Numerical companion to the entry clustering error: it recomputes what the entry states and prints one line per check
Numerical companion to the glossary entry 'clusteringerror'. The 366 days of 2024 at Krems are data points with the feature vector (morning minimum temperature, maximum daytime temperature). A hard clustering represents each cluster by a centroid and assigns a day to the nearest centroid; its clustering error is the average, over the days, of a loss that measures how far a day is from the centroid it is assigned to.
Run it without installing anything:uv run https://dictionaryofml.org/terms/clusteringerror.py
uv downloads this script and the pinned NumPy and Matplotlib it needs, then runs it; the script fetches any input file it uses. To keep the output files, download clusteringerror.py into a folder and run uv run clusteringerror.py there. With NumPy and Matplotlib already installed, python3 clusteringerror.py, from any directory — it writes its output files into the current directory. Fixed seeds, so the printed numbers reproduce exactly. Download clusteringerror.py · Notebook · Open in Colab
Before running a downloaded copy, scan it: uvx bandit -q -t B102,B307,B602,B605 clusteringerror.py (B102,B307,B602,B605 are the exec, eval and shell checks of bandit) reports nothing: the script runs no shell command and evaluates no generated code.
One cell per block of the script: the code, and what that code printed when it last ran here
"""The clustering error of the days of one year at Krems an der Donau:
the average loss of a clustering, under three choices of the loss.
Purpose
-------
Numerical companion to the glossary entry 'clusteringerror'. The 366
days of 2024 at Krems are data points with the feature vector (morning
minimum temperature, maximum daytime temperature). A hard clustering
represents each cluster by a centroid and assigns a day to the nearest
centroid; its clustering error is the average, over the days, of a loss
that measures how far a day is from the centroid it is assigned to.
The demo checks the entry's claims: the clustering error is the average
of a per-data-point loss, so it is a training error; Lloyd's algorithm
never increases it and stops at a fixed point where every centroid is
the mean of its days; replacing the squared Euclidean distance by the
Euclidean distance or by the Manhattan distance changes the centroid
update (geometric median, coordinate-wise median) but not the
assignment step; adding a centroid never increases the clustering
error, so it falls with the number of clusters and reaches zero when
every day is its own cluster, which is why it cannot choose the number
of clusters.
Deterministic: Lloyd's algorithm starts from k-means++ seeds drawn with
a fixed seed and from the previous solution warm-started with one more
centroid. Self-contained: numpy + matplotlib only; the GeoSphere
download falls back to the committed CSV.
Blocks
------
[B-data] Download the daily minimum and maximum temperature of 2024
at Krems (GeoSphere station 3805) or read the committed
copy; 366 days, no missing value.
[B-loss] The clustering error for k = 2 centroids equals the
average of the per-day loss, the squared Euclidean
distance to the nearest centroid.
[B-lloyd] Lloyd's algorithm with k = 2: the clustering error never
increases, the assignments stop changing, and at the
fixed point each centroid is the mean of its days; the two
clusters are the cold and the warm days.
[B-norms] The same two clusters under the Euclidean distance
(centroid = geometric median, Weiszfeld's iteration) and
under the Manhattan distance (centroid = coordinate-wise
median): the assignment rule is unchanged, the centroids
and the error values are not.
[B-k] Clustering error for k = 1, ..., 8 under the squared
Euclidean loss: non-increasing in k (a warm start with one
more centroid cannot be worse), and zero at k = 366.
[B-plot] Every 18th day for the figure (21 of 366 days) with
its cluster for k = 2, the two centroids, and the error
curve.
Outputs
-------
clusteringerror_weather.csv : date, tmin, tmax (committed copy).
clusteringerror_points_plot.csv : the 21 drawn days with their cluster.
clusteringerror_centroids.csv : the two centroids under each loss.
clusteringerror_curve.csv : k, clustering error, k = 1, ..., 8.
clusteringerror.png : matplotlib preview (checking only).
"""
# /// script
# requires-python = ">=3.10"
# dependencies = ["matplotlib==3.10.7", "numpy==2.3.4"]
# ///
import json
import urllib.request
from pathlib import Path
import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
OUT_DIR = Path(__file__).parent
report = []
def check(name, ok):
report.append((name, bool(ok)))
print(f" [{'ok' if ok else 'FAIL'}] {name}")
Download the daily minimum and maximum temperature of 2024 at Krems (GeoSphere station 3805) or read the committed copy; 366 days, no missing value.
print("[B-data] daily minimum and maximum temperature at Krems, 2024")
URL = ("https://dataset.api.hub.geosphere.at/v1/station/historical/"
"klima-v2-1d?parameters=tlmin,tlmax&station_ids=3805"
"&start=2024-01-01&end=2024-12-31")
CSV = OUT_DIR / "clusteringerror_weather.csv"
try:
with urllib.request.urlopen(URL, timeout=120) as resp:
payload = json.load(resp)
params = payload["features"][0]["properties"]["parameters"]
records = [(stamp[:10], lo, hi)
for stamp, lo, hi in zip(payload["timestamps"],
params["tlmin"]["data"],
params["tlmax"]["data"])]
with open(CSV, "w") as fh:
fh.write("date,tmin,tmax\n")
for day, lo, hi in records:
fh.write(f"{day},{lo},{hi}\n")
print(f" downloaded {len(records)} days")
except OSError as err:
print(f" download failed ({err}); reading the committed CSV")
rows = CSV.read_text().strip().splitlines()[1:]
records = [(d, float(a), float(b))
for d, a, b in (r.split(",") for r in rows)]
check("[B-data] 366 days for 2024", len(records) == 366)
check("[B-data] no day is missing a temperature",
all(lo is not None and hi is not None for _, lo, hi in records))
X = np.array([[lo, hi] for _, lo, hi in records], dtype=float)
m = len(X)
# ---- the three losses and their centroid updates
def sq_euclid(x, w):
return np.sum((x - w) ** 2, axis=-1)
def euclid(x, w):
return np.sqrt(np.sum((x - w) ** 2, axis=-1))
def manhattan(x, w):
return np.sum(np.abs(x - w), axis=-1)
def geometric_median(pts, iters=200):
"""Weiszfeld's fixed-point iteration for the geometric median."""
w = pts.mean(axis=0)
for _ in range(iters):
d = np.sqrt(np.sum((pts - w) ** 2, axis=1))
if np.any(d < 1e-12):
return pts[np.argmin(d)]
wts = 1.0 / d
w = (wts[:, None] * pts).sum(axis=0) / wts.sum()
return w
LOSSES = {
"squared Euclidean": (sq_euclid, lambda pts: pts.mean(axis=0)),
"Euclidean": (euclid, geometric_median),
"Manhattan": (manhattan, lambda pts: np.median(pts, axis=0)),
}
def assign(X, W, dist):
"""Index of the nearest centroid for every data point."""
return np.argmin(np.stack([dist(X, w) for w in W], axis=1), axis=1)
def clustering_error(X, W, dist):
"""Average loss: the loss of a data point is its distance to the
nearest centroid."""
return float(np.mean(np.min(np.stack([dist(X, w) for w in W], axis=1),
axis=1)))
def lloyd(X, W0, dist, update, max_iter=500):
"""Lloyd's algorithm from the centroids W0; returns the centroids,
the assignments, and the clustering error after every iteration."""
W = np.array(W0, dtype=float)
errors = [clustering_error(X, W, dist)]
c = assign(X, W, dist)
for _ in range(max_iter):
W_new = np.array([update(X[c == j]) if np.any(c == j) else W[j]
for j in range(len(W))])
c_new = assign(X, W_new, dist)
W = W_new
errors.append(clustering_error(X, W, dist))
if np.array_equal(c_new, c):
c = c_new
break
c = c_new
return W, c, errors
def kmeanspp_seeds(X, k, rng):
W = [X[rng.integers(m)]]
for _ in range(1, k):
d2 = np.min(np.stack([sq_euclid(X, w) for w in W], axis=1), axis=1)
W.append(X[rng.choice(m, p=d2 / d2.sum())])
return np.array(W)
def best_clustering(X, k, dist, update, rng, warm=None, restarts=20):
"""Smallest clustering error over k-means++ restarts and, if given,
a warm start (the previous centroids plus one more)."""
best = None
starts = [kmeanspp_seeds(X, k, rng) for _ in range(restarts)]
if warm is not None:
starts.append(warm)
for W0 in starts:
W, c, errs = lloyd(X, W0, dist, update)
if best is None or errs[-1] < best[2][-1]:
best = (W, c, errs)
return best
[B-data] daily minimum and maximum temperature at Krems, 2024
downloaded 366 days
[ok] [B-data] 366 days for 2024
[ok] [B-data] no day is missing a temperature
The clustering error for k = 2 centroids equals the average of the per-day loss, the squared Euclidean distance to the nearest centroid.
print("[B-loss] the clustering error of two centroids is an average loss")
rng = np.random.default_rng(2024)
W_two, c_two, errs_two = best_clustering(X, 2, sq_euclid,
LOSSES["squared Euclidean"][1], rng)
per_day = np.array([sq_euclid(x, W_two[c]) for x, c in zip(X, c_two)])
err_two = clustering_error(X, W_two, sq_euclid)
check(f"[B-loss] average of the per-day losses {per_day.mean():.2f} equals "
f"the clustering error {err_two:.2f}",
abs(per_day.mean() - err_two) < 1e-9)
check("[B-loss] the per-day loss is the squared distance to the NEAREST "
"centroid", np.all(per_day <= sq_euclid(X, W_two[1 - c_two]) + 1e-12))
[B-loss] the clustering error of two centroids is an average loss [ok] [B-loss] average of the per-day losses 42.02 equals the clustering error 42.02 [ok] [B-loss] the per-day loss is the squared distance to the NEAREST centroid
Lloyd's algorithm with k = 2: the clustering error never increases, the assignments stop changing, and at the fixed point each centroid is the mean of its days; the two clusters are the cold and the warm days.
print("[B-lloyd] Lloyd's algorithm with k = 2")
order = np.argsort(X[:, 0])
W0 = np.array([X[order[: m // 2]].mean(axis=0), X[order[m // 2:]].mean(axis=0)])
W_l, c_l, errs_l = lloyd(X, W0, sq_euclid, LOSSES["squared Euclidean"][1])
check(f"[B-lloyd] the clustering error never increases over "
f"{len(errs_l) - 1} iterations ({errs_l[0]:.2f} -> {errs_l[-1]:.2f})",
all(b <= a + 1e-9 for a, b in zip(errs_l, errs_l[1:])))
check("[B-lloyd] at the fixed point each centroid is the mean of its days",
all(np.allclose(W_l[j], X[c_l == j].mean(axis=0)) for j in range(2)))
check("[B-lloyd] the fixed point is the best of the k-means++ restarts",
abs(errs_l[-1] - err_two) < 1e-6)
cold, warm = sorted(range(2), key=lambda j: W_two[j, 1])
n_cold, n_warm = int(np.sum(c_two == cold)), int(np.sum(c_two == warm))
check(f"[B-lloyd] cold days: centroid ({W_two[cold, 0]:.1f}, "
f"{W_two[cold, 1]:.1f}) with {n_cold} days; warm days: centroid "
f"({W_two[warm, 0]:.1f}, {W_two[warm, 1]:.1f}) with {n_warm} days",
W_two[cold, 1] < 12 < W_two[warm, 1] and n_cold + n_warm == m)
months = np.array([int(d[5:7]) for d, _, _ in records])
check("[B-lloyd] every July and August day is a warm day, every January "
"and February day a cold day",
np.all(c_two[np.isin(months, [7, 8])] == warm)
and np.all(c_two[np.isin(months, [1, 2])] == cold))
[B-lloyd] Lloyd's algorithm with k = 2 [ok] [B-lloyd] the clustering error never increases over 2 iterations (43.04 -> 42.02) [ok] [B-lloyd] at the fixed point each centroid is the mean of its days [ok] [B-lloyd] the fixed point is the best of the k-means++ restarts [ok] [B-lloyd] cold days: centroid (1.5, 10.5) with 192 days; warm days: centroid (13.4, 26.1) with 174 days [ok] [B-lloyd] every July and August day is a warm day, every January and February day a cold day
The same two clusters under the Euclidean distance (centroid = geometric median, Weiszfeld's iteration) and under the Manhattan distance (centroid = coordinate-wise median): the assignment rule is unchanged, the centroids and the error values are not.
print("[B-norms] k = 2 under the Euclidean and the Manhattan distance")
results = {"squared Euclidean": (W_two, c_two, err_two)}
for name in ("Euclidean", "Manhattan"):
dist, update = LOSSES[name]
rng = np.random.default_rng(2024)
W, c, errs = best_clustering(X, 2, dist, update, rng, warm=W_two)
results[name] = (W, c, errs[-1])
kind = ("geometric median" if name == "Euclidean"
else "coordinate-wise median")
check(f"[B-norms] {name}: at the fixed point each centroid is the "
f"{kind} of its days",
all(np.allclose(W[j], update(X[c == j]), atol=1e-3)
for j in range(2)))
agree = np.mean(c == c_two) if np.mean(c == c_two) > 0.5 \
else np.mean(c != c_two)
check(f"[B-norms] {name}: clustering error {errs[-1]:.2f}, centroids "
f"({W[0, 0]:.1f}, {W[0, 1]:.1f}) and ({W[1, 0]:.1f}, "
f"{W[1, 1]:.1f}); {100 * agree:.1f}% of the days keep their "
f"cluster", agree > 0.9)
W_e = results["Euclidean"][0]
check("[B-norms] the assignment rule is the same: nearest centroid under "
"the Euclidean distance and under its square agree for every day",
np.array_equal(assign(X, W_e, euclid), assign(X, W_e, sq_euclid)))
check("[B-norms] the Euclidean error is below the square root of the "
"squared Euclidean error (Jensen)",
results["Euclidean"][2] < np.sqrt(err_two))
[B-norms] k = 2 under the Euclidean and the Manhattan distance [ok] [B-norms] Euclidean: at the fixed point each centroid is the geometric median of its days [ok] [B-norms] Euclidean: clustering error 5.84, centroids (13.6, 26.1) and (1.9, 11.0); 99.5% of the days keep their cluster [ok] [B-norms] Manhattan: at the fixed point each centroid is the coordinate-wise median of its days [ok] [B-norms] Manhattan: clustering error 7.59, centroids (1.9, 10.9) and (13.7, 26.2); 99.7% of the days keep their cluster [ok] [B-norms] the assignment rule is the same: nearest centroid under the Euclidean distance and under its square agree for every day [ok] [B-norms] the Euclidean error is below the square root of the squared Euclidean error (Jensen)
Clustering error for k = 1, ..., 8 under the squared Euclidean loss: non-increasing in k (a warm start with one more centroid cannot be worse), and zero at k = 366.
print("[B-k] clustering error for k = 1, ..., 8 (squared Euclidean)")
curve = {}
prev = None
for k in range(1, 9):
rng = np.random.default_rng(100 + k)
warm_start = None
if prev is not None:
W_prev, c_prev, _ = prev
far = np.argmax(np.min(np.stack([sq_euclid(X, w) for w in W_prev],
axis=1), axis=1))
warm_start = np.vstack([W_prev, X[far]])
prev = best_clustering(X, k, sq_euclid, LOSSES["squared Euclidean"][1],
rng, warm=warm_start)
curve[k] = prev[2][-1]
check("[B-k] " + ", ".join(f"k={k}: {curve[k]:.2f}" for k in curve),
all(curve[k + 1] <= curve[k] + 1e-9 for k in range(1, 8)))
check(f"[B-k] k = 1: the clustering error {curve[1]:.2f} is the total "
f"variance of the two features",
abs(curve[1] - np.sum(X.var(axis=0))) < 1e-9)
check(f"[B-k] k = 2 halves it and more ({curve[2]:.2f}); the fall from "
f"k = 2 to 8 ({curve[2] - curve[8]:.2f}) is smaller than the fall "
f"from k = 1 to 2 ({curve[1] - curve[2]:.2f})",
curve[2] < curve[1] / 2 and curve[2] - curve[8] < curve[1] - curve[2])
check("[B-k] k = 366, every day its own centroid: clustering error 0",
clustering_error(X, X.copy(), sq_euclid) == 0.0)
[B-k] clustering error for k = 1, ..., 8 (squared Euclidean) [ok] [B-k] k=1: 138.86, k=2: 42.02, k=3: 25.50, k=4: 16.96, k=5: 14.01, k=6: 11.95, k=7: 10.43, k=8: 9.11 [ok] [B-k] k = 1: the clustering error 138.86 is the total variance of the two features [ok] [B-k] k = 2 halves it and more (42.02); the fall from k = 2 to 8 (32.91) is smaller than the fall from k = 1 to 2 (96.83) [ok] [B-k] k = 366, every day its own centroid: clustering error 0
Every 18th day for the figure (21 of 366 days) with its cluster for k = 2, the two centroids, and the error curve.
print("[B-plot] thinned scatter, centroids, error curve")
idx = np.arange(0, m, 18)
with open(OUT_DIR / "clusteringerror_points_plot.csv", "w") as fh:
fh.write("tmin,tmax,cluster,ctmin,ctmax\n")
for i in idx:
j = c_two[i]
fh.write(f"{X[i, 0]:.1f},{X[i, 1]:.1f},{int(j == warm)},"
f"{W_two[j, 0]:.4f},{W_two[j, 1]:.4f}\n")
check(f"[B-plot] every 18th day: {len(idx)} of the {m} days are drawn",
len(idx) == 21)
with open(OUT_DIR / "clusteringerror_centroids.csv", "w") as fh:
fh.write("lossid,loss,cluster,tmin,tmax,error\n")
for lid, (name, (W, c, e)) in enumerate(results.items()):
cold_j = int(np.argmin(W[:, 1]))
for j in (cold_j, 1 - cold_j):
fh.write(f"{lid},{name},{int(j != cold_j)},{W[j, 0]:.4f},"
f"{W[j, 1]:.4f},{e:.4f}\n")
with open(OUT_DIR / "clusteringerror_curve.csv", "w") as fh:
fh.write("k,error\n")
for k, e in curve.items():
fh.write(f"{k},{e:.4f}\n")
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.4, 3.9))
for j, mk, lab in ((cold, "o", "cold days"), (warm, "s", "warm days")):
sel = idx[c_two[idx] == j]
ax1.scatter(X[sel, 0], X[sel, 1], marker=mk, facecolors="none",
edgecolors="black", s=28, label=f"{lab} (every 18th day)")
for i in sel:
ax1.plot([X[i, 0], W_two[j, 0]], [X[i, 1], W_two[j, 1]],
color="0.6", lw=0.6, ls="--")
ax1.scatter(W_two[:, 0], W_two[:, 1], marker="x", color="black", s=60,
label="centroids (k = 2)")
ax1.set_xlabel("morning minimum temperature (°C)")
ax1.set_ylabel("maximum daytime temperature (°C)")
ax1.set_title("loss of a day: squared length of its dashed line")
ax1.legend(frameon=False, fontsize=8)
ks = sorted(curve)
ax2.plot(ks, [curve[k] for k in ks], "ko-")
ax2.set_xlabel("number of clusters k")
ax2.set_ylabel("clustering error (squared Euclidean)")
ax2.set_title("the clustering error only falls with k")
fig.tight_layout()
fig.savefig(OUT_DIR / "clusteringerror.png", dpi=110)
n_ok = sum(ok for _, ok in report)
print(f"\n{n_ok}/{len(report)} checks pass")
if n_ok != len(report):
raise SystemExit(1)
[B-plot] thinned scatter, centroids, error curve [ok] [B-plot] every 18th day: 21 of the 366 days are drawn 20/20 checks pass

B-plot writes when the script runs