Darwill needs a deterministic clustering routine for grouping audience feature vectors before campaign analysis. Implement k-means without external machine learning libraries.
Given n points in d dimensions and k 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. If a point is equally close to multiple centroids, assign it to the centroid with the smallest index. If a centroid receives no points during an iteration, retain its previous coordinates. Stop when the largest squared centroid movement is at most tolerance², or when max_iterations is reached. Finally, assign every point using the returned centroids.
Return a dictionary with centroids, a list of final centroid vectors, and assignments, a list containing each point's centroid index.
Implement k_means(points, initial_centroids, max_iterations, tolerance). points and initial_centroids are nonempty lists of equal-dimensional numeric vectors. initial_centroids contains k vectors. Return {"centroids": list[list[float]], "assignments": list[int]}.
def k_means(points, initial_centroids, max_iterations, tolerance):