Implement the Lloyd Algorithm for k-Means Clustering solved by 267

The Lloyd algorithm is one of the most popular clustering heuristics for the k-Means Clustering Problem. It first chooses k arbitrary points Centers from Data as centers and then iteratively performs the following two steps:

• Centers to Clusters: After centers have been selected, assign each data point to the cluster corresponding to its nearest center; ties are broken arbitrarily. 
• Clusters to Centers: After data points have been assigned to clusters, assign each cluster’s center of gravity to be the cluster’s new center. 
  

We say that the Lloyd algorithm has converged if the centers (and therefore their clusters) stop changing between iterations. 

Implement the Lloyd algorithm

Given: Integers k and m followed by a set of points Data in m-dimensional space.

Return: A set Centers consisting of k points (centers) resulting from applying the Lloyd algorithm to Data and Centers, where the first k points from Data are selected as the first k centers.

Sample Dataset

2 2
1.3 1.1
1.3 0.2
0.6 2.8
3.0 3.2
1.2 0.7
1.4 1.6
1.2 1.0
1.2 1.1
0.6 1.5
1.8 2.6
1.2 1.3
1.2 1.0
0.0 1.9

Sample Output

1.800 2.867
1.060 1.140

Extra Dataset

Click for an extra dataset