Given a list of n points in d dimensions as points, an integer k, a maximum number of iterations max_iters, a tolerance tol, and an optional random seed seed, implement K-means clustering from scratch. Return the final centroids, the cluster assignment for each point, and the number of iterations performed. Use Euclidean distance, initialize centroids by sampling k distinct points, and stop when centroid movement is at most tol or when max_iters is reached. If a cluster becomes empty, reinitialize its centroid to the point farthest from its currently assigned centroid.
Example 1:
Input: points = [[1, 1], [1.5, 2], [3, 4], [5, 7], [3.5, 5], [4.5, 5], [3.5, 4.5]], k = 2, max_iters = 100, tol = 1e-4, seed = 0
Output: centroids close to [[1.25, 1.5], [3.9, 5.1]], labels like [0, 0, 1, 1, 1, 1, 1]
Explanation: The points separate into two compact groups, and K-means converges after a small number of iterations.
Example 2:
Input: points = [[0, 0], [0, 1], [10, 10], [10, 11]], k = 2, max_iters = 50, tol = 1e-6, seed = 1
Output: centroids close to [[0, 0.5], [10, 10.5]], labels like [0, 0, 1, 1]
Explanation: Each pair forms a natural cluster, so the centroids become the mean of each pair.
1 <= n <= 10^41 <= d <= 501 <= k <= n1 <= max_iters <= 3000 <= tol <= 1Given a list of n points in d dimensions as points, an integer k, a maximum number of iterations max_iters, a tolerance tol, and an optional random seed seed, implement K-means clustering from scratch. Return the final centroids, the cluster assignment for each point, and the number of iterations performed. Use Euclidean distance, initialize centroids by sampling k distinct points, and stop when centroid movement is at most tol or when max_iters is reached. If a cluster becomes empty, reinitialize its centroid to the point farthest from its currently assigned centroid.
Example 1:
Input: points = [[1, 1], [1.5, 2], [3, 4], [5, 7], [3.5, 5], [4.5, 5], [3.5, 4.5]], k = 2, max_iters = 100, tol = 1e-4, seed = 0
Output: centroids close to [[1.25, 1.5], [3.9, 5.1]], labels like [0, 0, 1, 1, 1, 1, 1]
Explanation: The points separate into two compact groups, and K-means converges after a small number of iterations.
Example 2:
Input: points = [[0, 0], [0, 1], [10, 10], [10, 11]], k = 2, max_iters = 50, tol = 1e-6, seed = 1
Output: centroids close to [[0, 0.5], [10, 10.5]], labels like [0, 0, 1, 1]
Explanation: Each pair forms a natural cluster, so the centroids become the mean of each pair.
1 <= n <= 10^41 <= d <= 501 <= k <= n1 <= max_iters <= 3000 <= tol <= 1
