k-medoids (alternating)

The problem, from first principles

k-means represents each cluster by its mean, and a single outlier can drag a mean far away. k-medoids represents each cluster by one of its actual data points, the medoid that minimizes total distance to the other members. Because the center is always a real point, it is less affected by outliers, and it works with any distance function.

Implement k_medoids(X, k, max_iter=100, seed=0), which returns (labels, medoid_indices). Use Euclidean distance.

1. Pick k distinct medoid indices uniformly at random with np.random.default_rng(seed).
2. Assign every point to its nearest medoid. The medoid point is assigned to its own cluster.
3. For each cluster, make the member that minimizes the sum of distances to the other members its new medoid. An empty cluster keeps its old medoid.
4. Repeat steps 2 and 3 until the medoids stop changing or max_iter is reached.

Constraints

• 1 <= k <= n, otherwise raise ValueError.
• labels[medoid_indices[c]] == c for every cluster c.

Hints

Open one at a time. Each gives away a little more than the last.