next up previous contents
Next: Agglomerative Nearest-neighbor Clustering Up: Clustering Algorithms Previous: The -means Framework   Contents

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.

Alexander Strehl 2002-05-03