k-means

k-means partitions the data into $k$ clusters, each represented by its centroid ${\mathbf{\mu }}_j$, by minimising the within-cluster sum of squares:

Lloyd's algorithm alternates two steps until assignments stop changing:

• Assign: put each point in the cluster of its nearest centroid.
• Update: move each centroid to the mean of its assigned points.

Each step can only lower $J$, so it always converges — but possibly to a poor local minimum. Run it several times from different starts, and use k-means++ initialisation, which spreads the initial centroids out.

Choosing $k$: plot $J$ against $k$ and look for the elbow where improvement flattens, or pick the $k$ with the best average silhouette.