K-medoids

K-medoids

1. Difference from K-means

Centroid must be a real data point (medoid), not a mean. Robust to outliers; works with any distance (strings, graphs), not just Euclidean.

2. PAM Algorithm (sketch)

pick k medoids; assign all points to nearest medoid
for each medoid m and non-medoid o: try swap m↔o, keep if total cost drops
repeat till no improving swap

Cost = sum of distances to medoid (use $L₁$ or domain distance for robustness).

3. K-means vs K-medoids

	K-means	K-medoids
Center	mean (may be unreal)	real point
Outlier	drags mean badly	mild effect
Distance	Euclidean mostly	any
Speed	$O(nkd)$ fast	$O(k(n-k)²)$ slow (use CLARA for big $n$)

4. When To Use

Small/medium $n$ with outliers or non-Euclidean distances (e.g. cluster customers by edit distance, facilities location).

5. Exam Points

• Medoid vs mean + robustness — 5 marks, very frequent.
• PAM swap idea — 3-5 marks, frequent.
• Complexity tradeoff — 2 marks.