k-means instrument
| Definition | A clustering that minimizes the sum of squared errors to the cluster centres. The mean minimizes each cluster's error and assigning each row to its nearest centre never raises the total, so it is the identity reader's clustering. Chapter 9. |
|---|---|
| Example | Points 1, 2, and 6 with two centres settle at 1.5 and 6, with sum of squared errors 0.5. |
| Book | Data Mining as Observation, draft 0.2, commit f3914f0; entry id k-means, kind instrument. |
| Status | no ledger row names this entry. Corrections: none recorded. |
| Defining equation | Book equation 9.1. |
| Assumptions and scope |
|
| Prior art | none recorded |
| Evidence | lean/DataMiningAsObservation/KMeans.lean |
| Reviewed | not yet reviewed; generated 2026-09-10 from records at the commits on the provenance page. |
Equation
Book equation 9.1.
\[\mathrm{SSE}=\sum_{k=1}^{K}\sum_{i\in\mathcal C_k}\|x_i-c_k\|^{2},\qquad\text{the }P_C=I\text{ distortion summed within clusters}.\]
Conditions
- A clustering that minimizes the sum of squared errors to the cluster centres. The error about any centre is the error about the mean plus the row count times the squared distance between the two, so the mean minimizes each cluster’s error, and assigning each row to its nearest centre never raises the total.
- It is the identity reader’s clustering. It weighs every direction equally, and a direction with large variance and no group structure pulls its centres exactly as variance-based reduction pulls its components.
Conditions are curated in entries.toml rather than read
from a record.
Ledger
none
First stated
Lloyd, least squares quantization in PCM, 1957, as chapter 9 section 9.1 of Data Mining as Observation reads it.
Measurements
none
Failures and corrections
none
Invariance envelope
none declared
Machine checked
lean/DataMiningAsObservation/KMeans.lean,
theorems sse_decomposition, mean_minimizes,
assign_nearest, at observation-data-mining f3914f0; what
the check covers is stated in the book’s appendix
C.
Used in
Data Mining as Observation chapters 0, 9, 10, 11.
Related
identity reader; validity index; silhouette; inverted file; DBSCAN.
See also
Book equations stated beside the entry’s terms, not defining it: 0.30, 4.2.
Ledger rows that cite the entry’s records without naming it: GO-3.
Sources-table rows that share a record with the entry without naming it: chapter 9 section 9.4, chapter 10 section 10.1.
Status
Generated 2026-09-10 by encyclopedia/generate.py; book
at observation-data-mining f3914f0; the commit of every record is listed
in the encyclopedia’s provenance.