k-Means Clustering

Every algorithm before this topic assumed a training set of labelled pairs $(x^{(i)},y^{(i)})$. This lesson opens unsupervised learning with the most direct possible question: given only unlabelled points $\{x^{(1)},\dots,x^{(m)}\}$, how do you group them into cohesive clusters? k-means answers this with a strikingly simple iterative algorithm — alternately assigning points to their nearest cluster centre and moving each centre to the mean of its assigned points — which this note shows is secretly a coordinate descent procedure on a well-defined objective, explaining both why it always converges and why it can get stuck.