k-medoids is like k-means, but each cluster centre must be an actual data point (a medoid). That makes it work with any distance (edit distance between strings, Manhattan distance on maps) and makes it robust to outliers.
Implement the alternating version on a precomputed (n, n) distance matrix D:
assign(D, medoids): each point's cluster is the index (into medoids) of its nearest medoid, with ties going to the earlier medoidk_medoids(D, init, max_iter=100): starting from the list of medoid indices init, alternate between assigning points and, within each cluster, choosing as the new medoid the member with the smallest total distance to the other members (ties: lowest index). Stop when the medoids stop changing. Return (medoids, labels).total_cost(D, medoids, labels): the sum of distances from each point to its medoid