Implement K-means | Dataford Interview Questions

Implement K-means

Asked in the Online assessment stage. ML algorithm from scratch.

Given points, a list of d-dimensional numeric points, an integer k, and initial centroids, repeatedly assign each point to its nearest centroid and recompute each centroid as the coordinate-wise mean of its assigned points. Use squared Euclidean distance, break ties by choosing the lowest centroid index, and leave an empty cluster's centroid unchanged. Stop when centroids no longer change or max_iterations is reached.

I/O Contract

Implement def k_means(points, k, initial_centroids, max_iterations):. Return [centroids, labels], where centroids is a list of k points and labels[i] is the assigned centroid index for points[i].

Constraints

1 <= k <= len(points) <= 1000
All points and centroids have the same dimension, between 1 and 20
1 <= max_iterations <= 100
Coordinates are finite integers or floating-point values

Function Signature

def k_means(points, k, initial_centroids, max_iterations):

Your question is Implement K-means. 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