k-means from scratch, and why it sometimes lies

k-means is usually the first clustering algorithm anyone learns: hand it data and a number k, and it splits the data into k groups. It's two simple steps repeated until they settle, and you can write