<p>A medoid can be defined as the object of a cluster whose average dissimilarity to all the objects in the cluster is minimal.</p>
<p>The K-medoids algorithm is related to k-means and the medoidshift algorithm. Both the k-means and k-medoids algorithms are partition and both attempt to minimize the distance between points in the cluster to it's center. In contrast to k-means, it chooses data points as centers and uses the Manhattan Norm to define the distance between data points instead of the Euclidean.</p>
<p>This method is known to be more robust to noise and outliers compared to k-means since it minimizes the sum of pairwise dissimilarities instead of the sum of squared Euclidean distances.</p>
<h2>Algorithms</h2>
<p>There are several algorithms that have been created as an optimization to an exhaustive search. In this section, we'll discuss PAM and Voronoi iteration method.</p>
<h3>Partitioning Around Medoids (PAM)</h3>
<ol>
<li>Select $k$ of the $n$ data points as medoids</li>
<li>Associate each data point to the closes medoid</li>
<li>While the cost of the configuration decreases:
<ol>
<li>For each medoid $m$, for each non-medoid data point $o$:
<ol>
<li>Swap $m$ and $o$, recompute the cost (sum of distances of points to their medoid)</li>
<li>If the total cost of the configuration increased in the previous step, undo the swap</li>
</ol></li>
</ol></li>
</ol>
<h3>Voronoi Iteration Method</h3>
<ol>
<li>Select $k$ of the $n$ data points as medoids</li>
<li>While the cost of the configuration decreases
<ol>
<li>In each cluster, make the point that minimizes the sum of distances within the cluster the medoid</li>
<li>Reassign each point to the cluster defined by the closest medoid determined in the previous step.</li>
</ol></li>
</ol>
<h3>Clustering Large Applications (CLARA</h3>
<p>This is a variant of the PAM algorithm that relies on the sampling approach to handle large datasets. The cost of a particular cluster configuration is the mean cost of all the dissimilarities.</p>
<h2>R Implementations</h2>
<p>Both PAM and CLARA are defined in the <code>cluster</code> package in R.</p>
