K-Means Clustering (MLE)

Implement the classic k-means clustering algorithm from scratch in NumPy. You will be given a 2-D NumPy array X of shape (n_samples, n_features) and an integer k. Your task is to partition the n_samples points into k clusters by alternating between two steps:

1. Assignment step: assign every point to the nearest centroid (Euclidean distance).
2. Update step: recompute each centroid as the mean of all points currently assigned to it.

Repeat these steps until convergence or until a supplied max_iters is reached. Convergence is defined as no change in any centroid coordinate between iterations. To improve initialization you must implement k-means++ seeding: choose the first centroid uniformly at random from the data points; each subsequent centroid is chosen from the remaining points with probability proportional to the squared distance to the nearest already-chosen centroid.

Your function kmeans(X, k, max_iters=300) should return a tuple (centroids, labels) where centroids is a (k, n_features) array with the final cluster centers and labels is a length-n_samples array containing the index (0…k-1) of the cluster to which each point is assigned.

Handle edge cases: if X is empty return empty arrays; if k ≥ n_samples simply return each point as its own centroid and labels 0…n_samples-1; if a cluster becomes empty keep its centroid unchanged from the previous iteration.