K-Mediods: A Variation on K-Means
So, one variation of k-means [...] is called k-mediods. And the only difference here is that, instead of picking random points in space as the centers of clusters, it randomly picks points in your own data set, as the center of clusters. And it tends to come out to about the same sorts of results, but is a nice variation that people sometimes like to use, particularly for very numerical data.
If your data is innately highly clustered, this tends to give you a somehwat better result faster. [It's because of convergence.]
-- Hilary Mason
from "Hilary Mason: An Introduction to Machine Learning with Web Data"
Quoted on Mon Aug 20th, 2012