Tech(x) groups vectors generated by its embedding service to identify similar content. Implement KMeans clustering from scratch using Lloyd's algorithm, without machine-learning libraries.
Given n points in d-dimensional space, assign each point to its nearest centroid, recompute each centroid as the mean of its assigned points, and repeat until convergence or max_iters is reached. If a cluster receives no points, retain its previous centroid. Distance ties must be resolved by choosing the smallest cluster index.
Implement kmeans(points, k, initial_centroids, max_iters), where points and initial_centroids are nonempty lists of equal-dimensional numeric vectors. Return a dictionary with labels, a list of n cluster indices, and centroids, a list of k vectors. Stop early when every centroid coordinate changes by at most 1e-9.
def kmeans(points, k, initial_centroids, max_iters):