Why Use Medoids?
Distance-based clustering is useful when the goal is to group observations by similarity, but the choice of representative within each group matters. K-means represents a cluster by its mean, which can be a point that does not occur in the data. Partitioning Around Medoids (PAM) instead represents each cluster by an observed case. This can make a cluster profile easier to interpret: the representative is an actual record with actual predictor values.
PAM is especially useful when a mean is not a suitable representative or when extreme observations could have disproportionate influence. It is not immune to outliers, and its results still depend on the chosen dissimilarity, variables, and number of clusters. These choices should be considered alongside the earlier material on scaling predictors and diagnosing outliers. The method and interpretation described here are aligned with the SOA Exam PA (Predictive Analytics) syllabus.
The PAM Objective and Assignment Rule
Let the data contain \(n\) observed cases. Write \(d(i,j)\) for the dissimilarity between cases \(i\) and \(j\). The following formulation assumes dissimilarities are nonnegative, symmetric, and zero from a case to itself. A distance is one common kind of dissimilarity, but the objective can use other appropriate dissimilarities too. Let \(M\) be a set of \(k\) distinct observed cases chosen as medoids. The PAM objective is:
For each case, the minimum selects its distance to its nearest medoid. The total \(J(M)\) is therefore the sum of within-cluster dissimilarities to the representatives. When there is a tie, a case is equally close to more than one medoid; software may use a particular tie-breaking rule to assign it, but the tied distances contribute the same amount to the objective.
For a single cluster, the best medoid is the observed case minimizing the sum of dissimilarities to all cases. For multiple clusters, both the medoid set and the resulting nearest-medoid assignments determine the objective. Finding the globally best set can require considering many candidate subsets, so the PAM algorithm uses a practical search procedure rather than relying on an unrestricted enumeration for larger data sets.
How PAM Searches for Medoids
PAM has two central stages. A BUILD stage constructs an initial set of medoids, typically adding candidates that reduce the objective. A SWAP stage considers exchanging a selected medoid with a non-medoid case. If a swap lowers the total objective, the new set is retained; the process continues until no considered swap improves the objective. The key decision is always about the change in total nearest-medoid dissimilarity, not whether a particular case seems intuitively central.
Set the number of medoids to use. PAM returns a partition for that choice; this step alone does not establish that \(k\) is best.
Select \(k\) observed cases as starting representatives using the method’s initialization procedure.
For each case, find its nearest medoid and sum those \(n\) dissimilarities.
Test replacing a medoid with a non-medoid. Keep an improving replacement and update assignments.
The result is a locally optimized medoid set under the search procedure, not a guarantee of the global minimum over every possible subset.
Worked Examples
Worked Example: Finding a One-Cluster Medoid
A hypothetical portfolio team has five cases summarized by a single numeric feature: \(0,1,2,3,20\). Use absolute difference, \(d(i,j)=|x_i-x_j|\), and select one medoid. Compute the total cost at every possible candidate and identify the minimum.
Method. With \(k=1\), each case is assigned to the only medoid. Thus, for candidate \(m\), the cost is \(\sum_i |x_i-m|\). The candidate must be one of the five observed values.
At candidate \(0\), the cost is \(0+1+2+3+20=26\). At candidate \(1\), it is \(1+0+1+2+19=23\). At candidate \(2\), it is \(2+1+0+1+18=22\). At candidate \(3\), it is \(3+2+1+0+17=23\). At candidate \(20\), it is \(20+19+18+17+0=74\).
The smallest cost is \(22\), so the medoid is the observed value \(2\). As a check, its distances to the five cases are \(2,1,0,1,18\), which sum to \(22\). The common mistake is to report the arithmetic mean, \(5.2\), as the medoid. It is not an observed case; it is not a permissible PAM medoid.
Worked Example: Comparing Two-Medoid Sets
A hypothetical service center has five cases with one numeric feature: \(0,2,3,10,11\). Use absolute difference and \(k=2\). Compare the possible pairs of medoids and find a minimum-cost pair.
Method. For each pair, calculate each case’s distance to its nearer medoid, then add the five values. For medoids \((0,3)\), for example, the nearest-medoid costs for \(0,2,3,10,11\) are \(0,1,0,7,8\), summing to \(16\)? This calculation needs care: the distance from \(2\) to \(3\) is \(1\), from \(10\) to \(3\) is \(7\), and from \(11\) to \(3\) is \(8\), giving \(0+1+0+7+8=16\).
Now compare all ten candidate pairs. For \((0,2)\), costs are \(0,0,1,8,9\), total \(18\). For \((0,3)\), they are \(0,1,0,7,8\), total \(16\). For \((0,10)\), they are \(0,2,3,0,1\), total \(6\). For \((0,11)\), they are \(0,2,3,1,0\), total \(6\). For \((2,3)\), they are \(2,0,0,7,8\), total \(17\).
For \((2,10)\), the costs are \(2,0,1,0,1\), total \(4\). For \((2,11)\), they are \(2,0,1,1,0\), also total \(4\). For \((3,10)\), they are \(3,1,0,0,1\), total \(5\). For \((3,11)\), they are \(3,1,0,1,0\), total \(5\). For \((10,11)\), they are \(10,8,7,0,0\), total \(25\).
The minimum is \(4\), attained by either \((2,10)\) or \((2,11)\). As a check, for \((2,10)\), the cases \(0,2,3,10,11\) contribute \(2,0,1,0,1\). A common trap is to add distances to both medoids; PAM adds only each case’s distance to its nearest medoid. Also, the pair \((0,3)\) has cost \(16\), not \(17\): its five nearest distances sum to \(16\).
Worked Example: Assessing the Effect of an Extreme Case
Consider the observed values \(0,1,2,3,20\), with absolute difference and one medoid. A new observation, \(100\), is added. Find the one-medoid cost at every possible candidate after the addition, then compare the selected medoid with the original result.
Method. Recompute the absolute-distance sum at every observed candidate. After adding \(100\), candidates \(4\) and \(5\) are not allowed: they are not observations.
For the original five values, costs at candidates \(0,1,2,3,20\) are \(26,23,22,23,74\), respectively, so \(2\) is the unique medoid. With \(100\) added, the costs at candidates \(0,1,2,3,20,100\) are as follows:
At \(0\): \(0+1+2+3+20+100=126\). At \(1\): \(1+0+1+2+19+99=122\). At \(2\): \(2+1+0+1+18+98=120\). At \(3\): \(3+2+1+0+17+97=120\). At \(20\): \(20+19+18+17+0+80=154\). At \(100\): \(100+99+98+97+80+0=474\).
The minimum is \(120\), tied between observed cases \(2\) and \(3\). The outlier raises the objective and changes a unique choice into a tie, but it does not pull the representative to \(100\). This illustrates reduced sensitivity, not immunity. A common mistake is to allow an unobserved value such as \(4\) to compete as a medoid, or to underestimate the sum at \(100\); the correct cost there is \(474\).
How PAM Differs From K-Means
For a numeric feature represented by vectors, k-means assigns cases to clusters and represents each cluster by its arithmetic mean. Its standard objective is the sum of squared Euclidean distances from cases to their cluster means. PAM instead chooses observed representatives and minimizes the sum of dissimilarities to the nearest medoid. The loss being minimized differs, so the resulting partitions need not agree.
| Feature | PAM | K-means |
|---|---|---|
| Cluster representative | An observed case (a medoid) | The arithmetic mean (a centroid) |
| Typical objective | Sum of nearest-medoid dissimilarities | Sum of squared Euclidean distances to centroids |
| Effect of extreme values | Often less sensitive with distance-based dissimilarities such as absolute distance | Squaring large distances can give extreme cases substantial influence |
| Interpretability | Representative is an actual observation | Representative may not correspond to any actual case |
For a short justification of the difference in sensitivity, consider one-dimensional data and absolute distance. Moving a candidate medoid changes each absolute-distance contribution in proportion to the distance moved; a far-away case can still matter, but its contribution grows linearly. Under squared error, a residual of magnitude \(r\) contributes \(r^2\), which grows quadratically. This explains why absolute-distance methods can be less affected by an extreme value than squared-error methods. It does not prove that every PAM fit is robust: the chosen distance, all observations, and the number of clusters still matter.
Worked Example: Contrasting the Representatives and Objectives
For the values \(0,1,2,3,20\), compare the one-cluster absolute-distance medoid result with the one-cluster k-means mean and squared-error objective.
Method. The medoid minimizes the sum of absolute distances over observed candidates; the k-means representative is the arithmetic mean, and its objective is the sum of squared residuals.
As calculated above, the absolute-distance costs at candidates \(0,1,2,3,20\) are \(26,23,22,23,74\). Thus the medoid is \(2\), with objective \(22\).
The mean is \((0+1+2+3+20)/5=26/5=5.2\). The squared-error objective is \((0-5.2)^2+(1-5.2)^2+(2-5.2)^2+(3-5.2)^2+(20-5.2)^2\) \(=27.04+17.64+10.24+4.84+219.04=278.80\).
The two objective values, \(22\) and \(278.80\), are not directly comparable because they use different loss functions and scales. The point is that the medoid is an observed value selected under absolute distance, while the k-means representative is \(5.2\), which is not observed and is selected under squared error. A common mistake is to compare the raw objective totals as though they measured the same quantity.
Practical Interpretation and Limitations
A medoid gives a concrete profile for a cluster: a reader can inspect the representative record’s predictor values rather than interpreting a synthetic average. This is useful when the goal is to describe typical cases or when a proposed representative needs to be explainable to a non-technical audience. It can also support a useful follow-up question: are cases near the medoid broadly similar, or does one representative hide meaningful variation within its cluster?
PAM does not remove the need for sound data preparation. The chosen features and scales affect distance-based results; a variable measured on a larger numerical scale can dominate if the distance calculation is not appropriate. The distance or dissimilarity must also reflect the meaning of similarity for the application. A medoid is only as representative as the inputs and dissimilarity allow.
- Robust does not mean unaffected. An extreme case can increase the objective, alter assignments, or change which cases minimize the total cost.
- The medoid must be observed. A mean or any other unobserved point is not a candidate, even if it looks central.
- A lower objective for larger \(k\) is expected. Adding medoids gives cases more representatives to choose from, so the minimum total dissimilarity cannot increase. That fact alone does not determine a useful cluster count.
- A local search result may not be globally optimal. The swap procedure improves the current solution when it finds a beneficial swap, but termination does not establish that every possible medoid set has been checked.
- Ties need interpretation. If multiple medoid sets have the same objective, other considerations such as interpretability or repeatability may help choose between them.
In R, PAM is commonly available through the cluster package’s pam function. It can be used with observations or, when supplied in the expected form, a dissimilarity object. Interpret its selected medoids together with the assigned clusters and the dissimilarity used; the output is not a substitute for checking whether the chosen variables and scale make the grouping meaningful.
Check Your Understanding
For each problem, use the stated dissimilarity and show how the stated result follows from the medoid objective.
- A one-cluster data set has values \(2,3,4,5,30\), and dissimilarity is absolute difference. Calculate the cost at every observed candidate and identify the medoid. (Answer: Costs at \(2,3,4,5,30\) are \(34,31,30,31,106\); medoid \(4\), cost \(30\).)
- For values \(1,4,5,12\), use absolute difference and \(k=2\). Compare all six candidate pairs by summing nearest-medoid costs. (Answer: \((4,12)\) is the unique minimizing pair, with cost \(4\).)
- A one-cluster data set is \(0,2,9\). Find its absolute-distance medoid and cost, then find the k-means mean. Explain why the mean is not a PAM medoid. (Answer: Medoid \(2\), cost \(9\); k-means mean \(11/3\), which is not observed.)
- For values \(0,1,2,10,11\), the current medoids are \(1\) and \(10\). Compute the current PAM objective, then evaluate replacing medoid \(1\) by \(2\). Does this swap improve the objective? (Answer: Current cost \(3\); swapped medoids \((2,10)\) have cost \(4\), so the swap does not improve it.)
- For \(0,1,2,3,20,100\), use one medoid and absolute difference. Find the minimum cost and all medoids attaining it. (Answer: Minimum cost \(120\), attained by medoids \(2\) and \(3\).)