Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

K-Medoids

English · فارسی

K-Medoids

Computer Science Dept, Ferdowsi University of Mashhad

Where this page sits

Section 14.3.10 of Hastie et al. (2009) (pp. 515-518) repairs the two restrictions that K-means acquires from its objective: it needs attribute values to average, and its squared Euclidean distance gives the largest distances the largest influence, which makes it fragile against outliers.

The repair is small. Of the two steps of K-means, only one uses the squared distance: replacing each cluster by its mean. If that step is replaced by “replace each cluster by one of its own observations”, any dissimilarity at all becomes usable - including the proximity matrices of the previous page, where no averaging is possible.

What you should be able to do at the end

  • write Algorithm 14.2 and point at the one line that differs from K-means;

  • say why K-medoids accepts an arbitrary dissimilarity matrix and K-means does not;

  • count the cost: O(Nk2)O(N_k^2) instead of O(Nk)O(N_k) per cluster, and say when that is worth paying;

  • read the country-dissimilarity example, including its reordered matrix and its MDS display.

1. The one step that assumes squared distance

K-means minimises the within-cluster scatter, and it does so by alternating two steps: assign every point to the nearest centre, then move every centre to the mean of its points. The second step is optimal only for squared Euclidean distance, because (14.32) of the book says

xˉS=arg⁡min⁡m∑i∈S∥xi−m∥2,\bar{x}_S = \arg\min_{m} \sum_{i \in S} \lVert x_i - m \rVert^2 ,

which is the mean and nothing else. Change the distance and the mean is no longer the best representative; replace the distance by a table of dissimilarities and the mean is not even defined.

The general statement of the method keeps the criterion and drops the shortcut. Centre mkm_k of cluster CkC_k is chosen to minimise the total dissimilarity to the cluster’s own members:

mk=arg⁡min⁡m∈Ck∑i∈CkD(xi,m).m_k = \arg\min_{m \in C_k} \sum_{i \in C_k} D(x_i, m).

For a general DD that minimisation is a search over the cluster’s own observations, and the minimiser is an observation - a medoid. It is not a new point, it is the most central existing point, which is why the medoid can be shown to a domain expert and why it exists for categorical data.

2. Algorithm 14.2

As printed in Hastie et al. (2009), p. 516:

  1. For a given cluster assignment CC, find the observation in each cluster that minimises the total distance to the other points of that cluster:

    ik=arg⁡min⁡{i:C(i)=k}∑C(i′)=kD(xi,xi′),(14.35)i_k = \arg\min_{\{i: C(i)=k\}} \sum_{C(i')=k} D(x_i, x_{i'}), \qquad \text{(14.35)}

    and set mk=xikm_k = x_{i_k} for k=1,…,Kk = 1,\dots,K.

  2. Given the centres, assign every observation to the nearest one:

    C(i)=arg⁡min⁡1≤k≤KD(xi,mk).(14.36)C(i) = \arg\min_{1 \le k \le K} D(x_i, m_k). \qquad \text{(14.36)}
  3. Iterate until the assignments stop changing.

The price is visible in the two line counts. Step 2 costs K⋅NK \cdot N, as in K-means. Step 1 costs Nk2N_k^2 per cluster instead of NkN_k, because every member is compared with every other member; over a full run that is the difference between linear and quadratic work in each cluster. The book says it plainly: K-medoids is far more computationally intensive than K-means.

Even so, Algorithm 14.2 is a heuristic for the combinatorial problem min⁡C,{ik}∑k∑C(i)=kD(xi,xik)\min_{C,\{i_k\}} \sum_k \sum_{C(i)=k} D(x_i, x_{i_k}) (14.38). Kaufman and Rousseeuw’s PAM improves on it by trying to exchange a current medoid with a non-medoid and keeping the exchange that reduces the criterion most, repeated until no exchange helps; Massart et al. give a branch-and-bound method that finds the global optimum for very small data sets.

Below is Algorithm 14.2 as written, with many random starts because - as on the families page - the criterion has local minima.

criterion (sum of distances to the medoid): 30.08
medoids: ['CUB', 'USA', 'ZAI']
  cluster 0: ['CHI', 'CUB', 'USS', 'YUG']
  cluster 1: ['BEL', 'EGY', 'FRA', 'ISR', 'USA']
  cluster 2: ['BRA', 'IND', 'ZAI']

Three groups come out, and they are the ones a reader of the 1990 survey would expect: a western group around the United States, France, Israel and Belgium, a second around Cuba and the USSR together with China and Yugoslavia, and a third of Brazil, India and Zaire. Egypt joins the western group, but the MDS display below shows why the book singles it out: it sits about halfway between two groups, so its assignment is a matter of a few tenths of a dissimilarity unit.

The left panel of Figure 14.10 in the book is the dissimilarity matrix with its rows and columns reordered by cluster, so that the blocks appear on the diagonal.

<Figure size 550x500 with 2 Axes>

The three dark blocks on the diagonal are the three clusters: within a block the entries are small, between blocks they are large. This picture is the clustering, and it is worth more than a list of labels, because the off-diagonal entries show how close the groups are to each other - Brazil’s block is far from both others, the western and the ex-Soviet blocks are not so far apart.

3. The same clustering in two dimensions

Distances cannot be drawn, but a two-dimensional multidimensional scaling of them can: find points whose pairwise Euclidean distances are as close as possible to the given dissimilarities. The right panel of Figure 14.10 is this plot; it is a diagnostic and not a proof, since the two coordinates are fitted and can be rotated or reflected arbitrarily.

<Figure size 600x500 with 1 Axes>

4. Why not just use K-means on attribute data?

With attribute data both methods apply, so the choice is about the loss. Squared Euclidean distance multiplies a large difference by itself, so a handful of distant points can pull a mean far from the bulk of its cluster; a sum of distances, which is what the medoid minimises, treats one large deviation linearly. The experiment below is the smallest version of the effect: one compact cloud of 40 points, and three points far away. The mean of the forty-three points is pulled towards the stragglers; the medoid is one of the observations and cannot move.

true centre of the cloud     : (0.00, 0.00)
mean of all 43 points        : [0.42 0.24]
medoid of all 43 points      : [-0.02273144 -0.18260265]
distance from the true centre: mean 0.48, medoid 0.18

The distance in the last line is the whole argument. A centroid is a computed position: it can land between two groups, or outside the data altogether, when the cluster contains a point that does not belong to it. A medoid is always one of the observations, so its worst case is “a real member of the cluster that is not very central”, never “a place where nothing was measured”. On clean attribute data the two methods usually agree, so the reason to prefer K-medoids is not accuracy - it is that its answer is robust to the kind of point that is common in real data (a mis-recorded measurement, a heavy tail, a survey respondent who answered carelessly).

The cost is real, so the practical rule is:

  • attribute data, squared loss acceptable, many points - K-means;

  • only dissimilarities available (the country survey, a confusion matrix, a string-edit table) - K-medoids, which is the only option;

  • attribute data with outliers, or KK small and NN moderate - K-medoids if the quadratic step is affordable, otherwise K-means on medians or a trimmed variant.

Summary

  • K-medoids is K-means with the mean replaced by a member of the cluster, which removes both the squared-distance assumption and the need for coordinates.

  • Algorithm 14.2 alternates (14.35) and (14.36); only step 1 is new, and it costs O(Nk2)O(N_k^2) per cluster.

  • The criterion (14.38) still has local minima, so multiple starts are still necessary; PAM exchanges medoids, and branch-and-bound can solve tiny instances exactly.

  • On the country data the three medoids give three interpretable groups, and the reordered matrix and the MDS plot are the two ways the book displays them.

  • The reason to use it is robustness and generality, not accuracy on clean attribute data.

Exercises

  1. Replace the medoid update by a mean update in k_medoids and run it on the country matrix. What fails, and why is that the whole point of the section?

  2. Implement the Kaufman-Rousseeuw exchange: from a solution of Algorithm 14.2, try exchanging each medoid with each non-medoid and keep the best exchange. How much does the criterion improve on the country data?

  3. Cluster the countries with K=2K = 2 and K=4K = 4. Which group splits first, and does Egypt move?

  4. Compare the K=3K = 3 medoids with the clustering you get from the squared dissimilarities D2D^2. Which clusters change?

  5. Time both methods on the iris data for N=150N = 150 and for a sample of N=1500N = 1500. How does the ratio of run times grow with NN?

  6. K-medoids with the median instead of the medoid of each coordinate is another robust variant. Is it the same algorithm? Give a counterexample if not.

Sources

  • Algorithm 14.2, (14.35)-(14.38), the complexity remark and the country example: §14.3.10 of Hastie et al. (2009), pp. 515-518.

  • The survey data (Table 14.3) and PAM: Kaufman and Rousseeuw (1990), cited there; the same matrix is used on the proximity matrices page.

  • Multidimensional scaling is §14.8 of the same book; sklearn.manifold.MDS implements the metric version used above.

References
  1. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. 10.1007/978-0-387-84858-7