Proof k-Means Converges

k-Means is a clustering algorithm that clusters a set of points N into k clusters. The k is chosen by the model developer. Once the algorithm finishes running, each observation will be assigned to one cluster.

With any specification of k, the algorithm will eventually converge; that is, no more updates will be possible and each observation will be assigned to a cluster.

Using logic, sketch out a proof that a k-Means clustering algorithm will converge in a finite number of steps. Note that the proof is not necessarily for the most efficient or effective real-world implementation and that there may be better ways to implement the algorithm. For this question, you need only show that the algorithm will converge in a finite number of steps.

State any assumptions required, if any, for the algorithm to converge.