Implement K-Means Clustering | Dataford Interview Questions

Implement k-means clustering.

Asked in the PyTorch coding stage. This was the second problem in the PyTorch coding round. Use deterministic initialization: divide the input points into k consecutive balanced groups and initialize each centroid as that group's mean.

Input and Output

Implement k_means(points, k, max_iterations). points is a nonempty list of equal-length numeric lists. Return (centroids, labels), where centroids is a list of k coordinate lists and labels[i] is the index of the nearest centroid for points[i]. Use squared Euclidean distance, preserve the lowest-index centroid on ties, and leave an empty cluster's centroid unchanged.

Constraints

1 <= len(points) <= 10^4
1 <= k <= len(points)
1 <= len(points[i]) <= 20
1 <= max_iterations <= 100
All points have the same dimension
Point coordinates are finite numbers

Function Signature

def k_means(points, k, max_iterations):

Your question is Implement K-Means Clustering. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem