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

Sept. 13, 2015, 10:41 p.m. by Rosalind Team

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:

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

Please login to solve this problem.