K-Means Clustering

Implement the missing code, denoted by ellipses. You may not modify the pre-existing code.

Your task is to implement parts of a k-Means Clustering algorithm from scratch, given an initial set of centroids.

Calculate the distance between each data point and the k centroids. Assign each data point to its nearest centroid. Average the data points in each cluster to update the centroids' locations and repeat for a set number of iterations. Return the predicted cluster for each data point.

Note: If a particular cluster is not assigned data points in one iteration, do not include that cluster in the next iteration. Any different cluster enumeration is also considered a valid answer.

Constraints

1 ≤ |data| ≤ 10000, 2 ≤ k ≤ 20, 1 ≤ iterations ≤ 500.

Example: data=[[1,2],[1,4],[1,0],[10,2],[10,4],[10,0]], k=2, centroids=[[1,2],[10,2]], iterations=10 → [0,0,0,1,1,1].