Implement an ML Algorithm in Python

HardPython

Problem

Mastech Digital's delivery analytics pipeline needs a dependency-free implementation of K-means clustering for grouping multidimensional service metrics. Implement the clustering algorithm without using machine learning libraries.

Given n points in d-dimensional space, divide them into exactly k clusters. Use deterministic farthest-point initialization: choose the first input point as the first centroid, then repeatedly choose the point whose distance to its nearest selected centroid is greatest. Break all distance ties by choosing the lowest input index.

Repeat these steps until convergence or max_iter iterations:

Assign each point to its nearest centroid, breaking ties with the lowest centroid index.
Replace each centroid with the coordinate-wise mean of its assigned points.
If a cluster is empty, place its centroid at the point with the greatest distance to its assigned centroid, using the lowest index to break ties.

Return [labels, centroids], where labels[i] is the cluster index for points[i], and centroids is a list of k coordinate lists. Stop when every centroid moves by at most tol in Euclidean distance.

Constraints

1 <= len(points) <= 10^4
1 <= k <= len(points)
1 <= len(points[i]) <= 20
Coordinates are integers in [-10^6, 10^6]
1 <= max_iter <= 500
0 <= tol <= 10^6
There are at least k distinct points

Function Signature

def k_means(points, k, max_iter, tol):

Repeat these steps until convergence or max_iter iterations:

Assign each point to its nearest centroid, breaking ties with the lowest centroid index.
Replace each centroid with the coordinate-wise mean of its assigned points.
If a cluster is empty, place its centroid at the point with the greatest distance to its assigned centroid, using the lowest index to break ties.