Robust $k$-medoids

Whenever higher robustness [Hub81] is sought or when means are not meaningful (e.g., certain binary features), the $k$-medoids algorithm, while computationally expensive, might be the method of choice. It uses medoids (representative sample objects) instead of means. However, the extension of a median to multivariate data is usually realized using a randomized approach. A random object is selected and the cost function is evaluated assuming that the selected object is one of the $k$-medoids. If the cost decreases, a swap is performed and the search is iterated until no changes occur for all medoids.