# K-Medoids

> Like k-means, but every center must be an actual data point, so any distance works and outliers pull less.

Source: https://www.mlfoundry.in/learn/k-medoids  
Section: ML Algorithms › Unsupervised · Clustering  
Level: core · 16 min read · updated 2026-10-07

**K-medoids:** partitions $n$ points into $k$ clusters, each represented by a **medoid**: the member of the cluster whose total distance to the other members is smallest. It minimizes the sum of (unsquared) dissimilarities from each point to its nearest medoid, and it needs nothing but a distance matrix, so it works with any distance you can compute.

- **Task:** Clustering (unsupervised partitioning)
- **Input → output:** a dissimilarity matrix $D\in\mathbb{R}^{n\times n}$ (or points + a metric) and $k$ → $k$ medoid indices and a cluster label per point
- **Learns:** a set $M$ of $k$ actual data points; each point belongs to its nearest medoid
- **Objective:** total deviation $\text{TD}=\sum_i \min_{m\in M} d(i,m)$
- **Training:** $O(n^2)$ memory for $D$; classic PAM SWAP costs $O(k(n-k)^2)$ per round, FasterPAM $O(n^2)$
- **Prediction:** $O(k)$ distance computations: assign to the nearest medoid
- **Hyperparameters:** k, the distance function, the algorithm (PAM / FasterPAM / alternating / CLARA), initialization
- **Assumes:** clusters are compact around a central member under your distance; no vector space or mean needed

## The problem

**k-means** represents each cluster by its **mean**. That single choice causes three problems. First, a mean only exists when you can average — there is no "average" of three DNA sequences, two customer journeys or a set of job titles. Second, k-means minimizes **squared** Euclidean distance, so a point 10 units away counts 100 times as much as a point 1 unit away; one outlier can drag a centre off the data, or capture a whole centre for itself. Third, the centre is a synthetic point that may correspond to nothing real, which makes it hard to explain to a person.

K-medoids fixes all three by restricting every centre to be **one of the data points** and by summing **plain** distances. It only ever looks up entries of the distance matrix, so Manhattan, cosine, edit distance, dynamic-time-warping or a hand-made dissimilarity all work. In the worked example below, k-means spends one of its two centres on a single outlier, while k-medoids keeps the two real groups.

## The idea

Pick $k$ data points to act as "representatives". Every other point joins the representative it is closest to, and pays its distance as a cost. Try to choose the representatives so the **total cost is as small as possible**. Because there are only $n$ candidates for each representative, the search is discrete: start with a sensible choice, then repeatedly ask *would swapping one representative for some other point make the total cost smaller?* and stop when no swap helps.

**Vocabulary**

- **Medoid:** the cluster member $m$ minimizing $\sum_{i\in C} d(i,m)$: the most central *actual* point. In 1-D with $|\cdot|$ it is a median of the cluster.
- **Dissimilarity matrix:** $D_{ij}=d(x_i,x_j)$ for all pairs. Only needs $d\ge0$ and $d(i,i)=0$; symmetry and the triangle inequality help but are not required by the objective.
- **Total deviation (TD):** the objective: sum over all points of the distance to their nearest medoid. Lower is better.
- **BUILD:** PAM's greedy initialization: add medoids one at a time, each time the point that lowers TD the most.
- **SWAP:** PAM's improvement phase: evaluate exchanging a medoid $m$ with a non-medoid $h$, apply the best exchange if it lowers TD, repeat.
- **Nearest / second-nearest:** $d_i$ and $e_i$: distance from point $i$ to its closest and second-closest medoid. Used to evaluate swaps quickly.
- **PAM:** Partitioning Around Medoids (Kaufman & Rousseeuw, 1987): BUILD + SWAP.

> **Shared theory lives next door:** Choosing k, the elbow plot and silhouette scores work the same way as for **k-means**; **hierarchical clustering** and **affinity propagation** are the other common clusterers that also run on an arbitrary distance matrix. This article sticks to what is specific to medoids.

## The math

Let $M\subseteq\{1,\dots,n\}$ with $|M|=k$ be the medoid set. Each point is assigned to its nearest medoid, and the objective is the total deviation:

$$
\text{TD}(M)=\sum_{i=1}^{n}\min_{m\in M} d(x_i,x_m)\qquad M^\star=\arg\min_{M\subseteq\{1..n\},\;|M|=k}\text{TD}(M)
$$

- $n$: number of points
- $k$: number of clusters (medoids)
- $M$: set of medoid indices — each is a real data point
- $d(x_i,x_m)$: dissimilarity between point $i$ and medoid $m$ (entry $D_{im}$)
- $\text{TD}(M)$: total deviation: sum of each point's distance to its nearest medoid

Compare k-means, which minimizes $\sum_i\min_j\lVert x_i-\mu_j\rVert^2$ over *arbitrary* vectors $\mu_j$. Two things change: the centre is constrained to the data, and the loss is $d$, not $d^2$. Finding $M^\star$ exactly is NP-hard (it is the discrete $k$-median problem), so we use local search. There are $\binom{n}{k}$ medoid sets; the heuristics below explore only a tiny fraction of them.

**Why medoids resist outliers.** With one cluster in 1-D and $d=|\cdot|$, the best centre minimizes $\sum_i |x_i-c|$, whose derivative is $\sum_i \operatorname{sign}(c-x_i)$ = (#points below $c$) − (#points above $c$). It is zero at the **median**, and moving one point far away does not change which point is in the middle. The squared loss has derivative $2\sum_i(c-x_i)$, zero at the **mean**, which moves by $\Delta/n$ whenever one point moves by $\Delta$. The robustness is a property of the *unsquared* loss; making the centre a data point is what lets that loss work with any $d$.

**BUILD (greedy start).** The first medoid is the single best centre, the point with the smallest row sum of $D$. Each later medoid is the candidate $c$ that removes the most cost given the medoids chosen so far, where $d_i$ is point $i$'s current nearest-medoid distance:

$$
m_1=\arg\min_{c}\sum_{i} d(i,c),\qquad m_{t+1}=\arg\max_{c\notin M}\;\sum_{i}\max\big(0,\;d_i-d(i,c)\big)
$$

- $d_i$: distance from point $i$ to its nearest medoid in the current $M$
- $\max(0,\,d_i-d(i,c))$: how much point $i$ saves if $c$ becomes a medoid (zero if $c$ is not closer than what $i$ already has)

The gain is exactly $\text{TD}(M)-\text{TD}(M\cup\{c\})$, because adding $c$ changes each point's cost from $d_i$ to $\min(d_i,d(i,c))$, and $d_i-\min(d_i,d(i,c))=\max(0,d_i-d(i,c))$.

**SWAP (local search).** For a medoid $m\in M$ and a non-medoid $h$, the change in cost from exchanging them is

$$
\Delta(m,h)=\text{TD}\big(M\setminus\{m\}\cup\{h\}\big)-\text{TD}(M)=\sum_{i} \Big(\min_{j\in M\setminus\{m\}\cup\{h\}} d(i,j)\;-\;d_i\Big)
$$

- $m$: the medoid being removed
- $h$: the non-medoid being promoted
- $\Delta(m,h)$: change in TD; negative means the swap helps

Each point's contribution falls into one of two cases, which is how PAM evaluates a swap in $O(n)$ instead of re-clustering. Let $e_i$ be the distance to the **second**-nearest medoid. If $m$ was point $i$'s medoid, then after the swap $i$ goes to $h$ or to its second-nearest medoid: contribution $\min(d(i,h),e_i)-d_i$. Otherwise $i$ keeps its medoid unless $h$ is closer: contribution $\min(d(i,h),d_i)-d_i\le0$. PAM applies the swap with the most negative $\Delta$ and stops when every $\Delta\ge0$. TD strictly decreases at every applied swap and there are finitely many medoid sets, so it always terminates, at a set that no *single* exchange can improve.

**How the choices act on the objective**

- **k:** TD is non-increasing in $k$ (adding a medoid can only lower each $\min$); at $k=n$ every point is its own medoid and TD $=0$. So choose $k$ with silhouette or a held-out criterion, never by TD alone.
- **Distance d:** defines the whole problem. With $d=\lVert\cdot\rVert^2$ the loss grows quadratically and outliers dominate, exactly like k-means; with $|\cdot|_1$ or $\lVert\cdot\rVert_2$ it grows linearly.
- **Feature scale:** for vector data $d$ is computed on raw features, so a feature measured in thousands swamps one measured in units. Standardize first, or use a scale-free dissimilarity.
- **Algorithm:** BUILD+SWAP (PAM) searches more thoroughly than the k-means-style alternating update, at higher cost per round (see Variants).

## Worked example: 11 points and one outlier

Two groups in the plane — A to F in the lower left, G to J in the upper right — plus one outlier **K** far to the right. We use $k=2$ and the **Manhattan** distance $d(p,q)=|p_1-q_1|+|p_2-q_2|$, so every distance is an integer you can check by hand (e.g. $d(F,J)=|4-8|+|4-6|=6$).

The data, with each point's total Manhattan distance to all others (BUILD step 1) and its gain if added next to F (BUILD step 2). Highlighted: F (smallest total, first medoid) and J (largest gain, second medoid).

| Point | x₁ | x₂ | Σ d(i, c) | d(i, F) | gain if added |
| --- | --- | --- | --- | --- | --- |
| A | 1 | 1 | 80 | 6 | 14 |
| B | 2 | 1 | 73 | 5 | 15 |
| C | 1 | 3 | 70 | 4 | 12 |
| D | 2 | 2 | 66 | 4 | 16 |
| E | 3 | 2 | 63 | 3 | 13 |
| **F** | 4 | 4 | **58** | 0 | — |
| G | 6 | 6 | 64 | 4 | 18 |
| H | 7 | 5 | 64 | 4 | 18 |
| I | 7 | 7 | 76 | 6 | 18 |
| **J** | 8 | 6 | 74 | 6 | **20** |
| K | 18 | 6 | 164 | 16 | 16 |

**PAM by hand**

1. **BUILD, medoid 1.** Sum each row of the distance matrix. F, the "bridge" point at (4, 4), has the smallest total, 58: alone, it is the best single centre. Note that F is between the groups — a good 1-medoid, a poor member of a 2-medoid solution.
2. **BUILD, medoid 2.** With F as the only medoid, point $i$ costs $d(i,F)$. Adding J saves $\max(0,4-2)+\max(0,4-2)+\max(0,6-2)+6+(16-10)=2+2+4+6+6=20$ (from G, H, I, J itself and K), the largest gain. Medoids $\{F,J\}$.
3. **Assign.** A–F go to F (distances 6, 5, 4, 4, 3, 0) and G–K go to J (2, 2, 2, 0, 10). $\text{TD}=22+16=38$.
4. **SWAP round 1.** Evaluate all $2\times9=18$ exchanges (table below). The best is **F → D** with $\Delta=-12$: A–F now cost 2, 1, 2, 0, 1, 4 = 10 instead of 22, and G–K are unaffected because they are all closer to J than to D. Apply it: $\text{TD}=38-12=26$.
5. **SWAP round 2.** With medoids $\{D,J\}$ all 18 exchanges have $\Delta\ge0$; the smallest is $+2$ (D → B, D → E, J → G, J → H, J → I). Stop. An exhaustive check of all $\binom{11}{2}=55$ pairs confirms TD = 26 is the global optimum here.
6. **Result.** Clusters $\{A,B,C,D,E,F\}$ with medoid D = (2, 2) and $\{G,H,I,J,K\}$ with medoid J = (8, 6). The second cluster's *mean* is (9.2, 6.0), pulled 1.2 units toward K; its medoid stays inside the group.
7. **Predict.** A new point (5, 3) is $|5-2|+|3-2|=4$ from D and $|5-8|+|3-6|=6$ from J, so it joins **D's cluster**.

SWAP round 1: ΔTD for replacing a medoid (row) by a candidate (column), starting from TD = 38. Negative entries lower the cost; the best is F → D (−12). Replacing J never helps.

| remove ↓ / add → | A | B | C | D | E | G | H | I | K |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| F | −8 | −10 | −8 | **−12** | −10 | +22 | +22 | +34 | +26 |
| J | +6 | +5 | +8 | +4 | +7 | +2 | +2 | +2 | +4 |

For comparison, k-means with $k=2$ on the same points (best of 10 starts) puts **K alone** in one cluster with centre (18, 6) and all ten other points in the other with centre (4.1, 3.7), inertia 109.0. Under squared distance, K's cost to any centre near the right group is about $10^2=100$, so giving K its own centre is "cheaper" than splitting the two real groups.

> Figure: PAM on the 11 points above (k = 2, Manhattan). BUILD picks F (total 58), then J (gain 20), TD = 38; SWAP round 1 scores all 18 exchanges in the heat-table and applies F → D (−12, TD 26); round 2 finds no negative Δ (smallest +2) and stops; the new point (5, 3) joins D (4 vs 6). Drag the outlier K along its row (y = 6): with Manhattan the medoids stay D and J and TD = 16 + d(K, J). Drag it up or down and the right-hand medoid hops to H or I; drag it to a far corner such as (18, 0) and PAM gives K its own medoid, so robustness has limits. Switch to squared distance and PAM ends with F and K as medoids (TD 110, while {D, J} would cost 122); with plain Euclidean BUILD chooses K over J by 14.14 to 14.02 and SWAP cannot escape (TD 30.78 versus the optimum 22.49). Toggle k-means to see its centres at (4.1, 3.7) and (18, 6).

> **The robustness comes from the loss, not from the medoid:** In the figure, switch the distance to squared Euclidean: k-medoids then makes the *same* mistake as k-means and gives K its own medoid. Restricting centres to data points buys you arbitrary distances and interpretable prototypes; it is the **unsquared** distance that makes the method robust. A centre-anywhere version with $|\cdot|_1$ (k-medians) is robust too.

## The algorithm, step by step

**PAM(D, k)**

1. **Distances.** Compute or receive the $n\times n$ dissimilarity matrix $D$. This is the only input the rest of the algorithm touches.
2. **BUILD.** $m_1\leftarrow\arg\min_c\sum_i D_{ic}$. While $|M|<k$: compute every point's nearest-medoid distance $d_i$ and add $\arg\max_{c\notin M}\sum_i\max(0,d_i-D_{ic})$.
3. **SWAP.** For each medoid $m\in M$ and each non-medoid $h$, compute $\Delta(m,h)$ using the nearest/second-nearest trick. Keep the most negative.
4. **Apply or stop.** If the best $\Delta<0$, replace $m$ by $h$, update $d_i,e_i$, and repeat SWAP. Otherwise stop: $M$ is a local optimum for single swaps.
5. **Label.** Each point gets the index of its nearest medoid. New points: compute $k$ distances and take the nearest.

**Cost**

- **Distance matrix:** $O(n^2)$ time and memory — the real bottleneck: $n=50{,}000$ needs $2.5\times10^9$ entries (10 GB in float32).
- **BUILD:** $O(kn^2)$
- **PAM SWAP round:** $k(n-k)$ candidate swaps × $O(n-k)$ each $=O(k(n-k)^2)$
- **FasterPAM round:** $O(n^2)$: evaluates all $k$ removals for a candidate $h$ in one pass and applies any improving swap immediately (Schubert & Rousseeuw, 2021)
- **Prediction:** $O(k)$ distances per new point

## Variants and practical tuning

The main k-medoids algorithms. All minimize the same TD; they differ in how hard they search and how much memory they need.

| Algorithm | Search | Cost per round | Use when |
| --- | --- | --- | --- |
| PAM (BUILD + SWAP) | best single swap per round | $O(k(n-k)^2)$ | small n (≲ few thousand), you want the classic, well-studied result |
| **FasterPAM** | first improving swap, all removals at once | $O(n^2)$ | default choice for n up to tens of thousands; same swaps evaluated far more cheaply, similar quality to PAM |
| Alternating (Voronoi iteration) | k-means-style: assign, then re-pick each cluster's medoid | about $O(n^2/k)$ | quick, but gets stuck more easily |
| CLARA | PAM on several random samples, keep the best medoids | PAM on sample size ≈ 40 + 2k | n too large for an n × n matrix |
| CLARANS | randomized swap search on the full data | random subset of swaps | large n, moderate k, quality between CLARA and PAM |

The **alternating** variant is what you get if you copy k-means literally: assign each point to its nearest medoid, then replace each medoid by the most central member of its own cluster, and repeat. Each medoid only looks inside its current cluster, so it cannot move a medoid to a different group. On our data, starting from $\{C,D\}$ it stalls at $\{D,G\}$ with TD 28, and from any start containing K it stays at $\{F,K\}$ with TD 42 (9 of the 55 possible starts end at a worse solution). PAM's SWAP escapes both: from $\{D,G\}$ it swaps G → J ($\Delta=-2$), and from $\{F,K\}$ it swaps K → J ($-4$), then F → D ($-12$), reaching TD 26.

**Tuning checklist**

- **Choosing k:** Silhouette works directly from the same distance matrix (no means needed); also plot TD vs k and look for the elbow, as with k-means.
- **Choosing d:** Pick the distance that matches what *similar* means in your domain: Manhattan for robust tabular data, cosine for text/embeddings, Gower for mixed numeric/categorical, edit or DTW for sequences.
- **Scaling:** Standardize numeric features before Manhattan/Euclidean, or one feature dominates the distance.
- **Initialization:** BUILD is deterministic and strong; with random init use several restarts (FasterPAM is cheap enough) and keep the lowest TD.
- **Large n:** CLARA / CLARANS, or cluster a sample and assign the rest to the nearest medoid.

## In code

```python
import numpy as np

def pairwise(X, metric="manhattan"):
    diff = X[:, None, :] - X[None, :, :]
    if metric == "manhattan":
        return np.abs(diff).sum(-1)
    if metric == "euclidean":
        return np.sqrt((diff ** 2).sum(-1))
    raise ValueError(metric)

def total_deviation(D, medoids):
    return D[:, medoids].min(axis=1).sum()

def build(D, k):
    medoids = [int(np.argmin(D.sum(axis=1)))]          # the 1-medoid
    while len(medoids) < k:
        near = D[:, medoids].min(axis=1)               # distance to current nearest medoid
        gain = np.maximum(near[:, None] - D, 0).sum(axis=0)
        gain[medoids] = -1
        medoids.append(int(np.argmax(gain)))
    return medoids

def pam(X, k, metric="manhattan", max_iter=100):
    D = pairwise(X, metric)
    medoids = build(D, k)
    td = total_deviation(D, medoids)
    print(f"BUILD -> medoids {medoids}, TD = {td:g}")
    for it in range(max_iter):
        best = (0.0, None, None)                       # (delta, slot, candidate)
        for slot in range(k):
            for h in range(len(X)):
                if h in medoids:
                    continue
                trial = medoids.copy(); trial[slot] = h
                delta = total_deviation(D, trial) - td
                if delta < best[0]:
                    best = (delta, slot, h)
        if best[1] is None:                            # no swap lowers TD: local optimum
            break
        delta, slot, h = best
        print(f"swap {medoids[slot]} -> {h}: delta = {delta:g}")
        medoids[slot] = h
        td += delta
    labels = D[:, medoids].argmin(axis=1)
    return medoids, labels, td

X = np.array([[1,1],[2,1],[1,3],[2,2],[3,2],[4,4],[6,6],[7,5],[7,7],[8,6],[18,6]])
medoids, labels, td = pam(X, k=2)
print("medoids", medoids, "=", X[medoids].tolist())
print("labels ", labels.tolist(), " TD =", td)
new = np.array([5, 3])
print("new point ->", np.abs(X[medoids] - new).sum(axis=1).tolist())
```

From scratch: PAM with BUILD and best-swap SWAP. Prints BUILD → medoids [5, 9], TD = 38; swap 5 -> 3: delta = -12; final medoids [3, 9] = (2, 2) and (8, 6), TD = 26; the new point is 4 and 6 away.

```python
import numpy as np
import kmedoids                      # pip install kmedoids
from sklearn.cluster import KMeans
from sklearn.metrics import pairwise_distances

X = np.array([[1,1],[2,1],[1,3],[2,2],[3,2],[4,4],[6,6],[7,5],[7,7],[8,6],[18,6]])

km = kmedoids.KMedoids(n_clusters=2, metric="manhattan", method="pam", init="build").fit(X)
print("PAM       medoids", km.medoid_indices_.tolist(), "labels", km.labels_.tolist(), "TD", km.inertia_)

D = pairwise_distances(X, metric="manhattan")      # any precomputed dissimilarity works
res = kmedoids.fasterpam(D, 2, init="random", random_state=0)
print("FasterPAM medoids", sorted(res.medoids.tolist()), "TD", res.loss)

print("predict (5,3) ->", km.predict(np.array([[5, 3]])).tolist())   # [3]: the medoid's row index (D)

means = KMeans(n_clusters=2, n_init=10, random_state=0).fit(X)
print("k-means   labels", means.labels_.tolist(), "centres", means.cluster_centers_.round(2).tolist())
```

With the kmedoids package (pip install kmedoids; scikit-learn style API), compared with k-means. Output: PAM medoids [3, 9], labels [0]*6 + [1]*5, TD 26.0; FasterPAM from a random start also reaches [3, 9] with TD 26.0; k-means labels put only K in cluster 1, centres (4.1, 3.7) and (18.0, 6.0).

> **Library quirks:** In the `kmedoids` package, `KMedoids.predict` returns the **row index of the nearest medoid** (here 3, i.e. point D), not a 0..k−1 label, and `inertia_` is the TD. The older `sklearn_extra.cluster.KMedoids` (scikit-learn-extra) has a similar API with `method="pam"` but is no longer maintained for recent scikit-learn versions.

**Strengths**

- Your data has no meaningful mean: strings, sequences, graphs, sets, mixed-type records with Gower distance.
- You have only a similarity or distance matrix, e.g. from a domain-specific comparison.
- Outliers are present and you use an unsquared distance.
- You need interpretable prototypes: each cluster is summarized by a real example you can show someone.

**Limitations**

- $n$ is large (≳ 50k) and you cannot afford the $O(n^2)$ distance matrix — use k-means, mini-batch k-means or CLARA.
- Clusters are non-convex or chained (rings, moons) — use DBSCAN, spectral or single-linkage clustering.
- Clusters have very different sizes or densities: a nearest-medoid rule splits big clusters, as k-means does.
- Your data is plain Euclidean vectors without outliers: k-means gives nearly the same answer much faster.

- **Bioinformatics:** Clustering gene-expression profiles or protein sequences under correlation or alignment distances; the medoid is a real representative gene or sequence.
- **Time-series grouping:** Load curves, sensor traces or user sessions clustered with dynamic time warping, where a mean curve would be blurred and meaningless.
- **Facility & sensor placement:** Choose k actual sites (warehouses, base stations) minimizing total travel distance — the k-median problem in its natural form.
- **Prototype selection:** Pick k representative customers, documents or images for review, labelling or a small training set.

> **Squared Euclidean throws the robustness away:** Passing $\lVert\cdot\rVert^2$ (the "sqeuclidean" metric) makes the objective as outlier-sensitive as k-means. On the worked example PAM then picks F and K as medoids (TD 110 versus 122 for D and J). Use Manhattan, Euclidean or a domain distance.

> **PAM is still a local search:** SWAP only tries one exchange at a time. With plain Euclidean distance on the example, BUILD picks K over J (gain 14.14 vs 14.02) and no single swap from {F, K} lowers TD, so PAM stops at 30.78 although {D, J} costs 22.49. Compare a few random restarts of FasterPAM, and compute silhouettes before trusting a result.

> **The n × n matrix:** Memory grows quadratically. 20,000 points in float64 is already 3.2 GB. Subsample (CLARA), use a sparse k-nearest-neighbour graph, or switch algorithm before you run out of RAM.

**Question:** One cluster contains the 1-D points 1, 2, 3, 4, 100. With d = |a − b|, what are its medoid and its mean?

- A. Medoid 3, mean 22
- B. Medoid 22, mean 3
- C. Medoid 4, mean 22
- D. Medoid 3, mean 3

**Answer:** A. Medoid 3, mean 22 — Total distances are 105, 102, 101, 102, 390 for the five candidates, so the medoid is 3 (the median). The mean is $110/5=22$, a value no point is near — dragged there by 100.

**Question:** PAM with n = 11 points and k = 2. How many (medoid, non-medoid) swaps does one SWAP round evaluate?

- A. 11
- B. 18
- C. 22
- D. 55

**Answer:** B. 18 — Each of the $k=2$ medoids can be exchanged with each of the $n-k=9$ non-medoids: $2\times9=18$. (55 is the number of all possible medoid pairs, $\binom{11}{2}$.)

**Question:** In the worked example, medoids are D = (2, 2) and J = (8, 6) with Manhattan distance. If the outlier K moves from (18, 6) to (20, 6), what is the new TD?

- A. 26
- B. 28
- C. 30
- D. TD cannot be predicted without rerunning PAM's BUILD

**Answer:** B. 28 — K is still nearest to J, now at distance $12$ instead of $10$; nothing else changes, so TD = 26 + 2 = 28 (and $\{D,J\}$ remains optimal, as you can check by dragging K in the figure).

**Question:** Which change would make k-medoids about as sensitive to outliers as k-means?

- A. Using FasterPAM instead of PAM
- B. Using squared Euclidean distance as d
- C. Using BUILD instead of random initialization
- D. Using cosine distance

**Answer:** B. Using squared Euclidean distance as d — Squaring makes far points dominate the sum, exactly as in the k-means objective. The algorithm and initialization change only how well TD is minimized, not what TD rewards.

**Key points**

- K-medoids picks $k$ actual data points as centres and minimizes the total (unsquared) distance $\text{TD}=\sum_i\min_{m}d(i,m)$.
- It needs only a dissimilarity matrix, so any distance works: Manhattan, cosine, Gower, edit distance, DTW.
- Robustness to outliers comes from the unsquared loss (median-like behaviour); with squared Euclidean it behaves like k-means.
- PAM = greedy BUILD + SWAP local search on $\Delta(m,h)$; FasterPAM gets the same quality in $O(n^2)$ per round.
- The price is $O(n^2)$ memory and time for the distance matrix; for big $n$ use CLARA, sampling or k-means.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
