k-medoids

<h2 id="algorithms">Algorithms</h2>

In general, the k-medoids problem is NP-hard to solve exactly.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> As such, many heuristic solutions exist. 

<h3>Partitioning Around Medoids (PAM)</h3>
PAM<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> uses a greedy search which may not find the optimum solution, but it is faster than exhaustive search. It works as follows:

<ol><li>(BUILD) Initialize: <a href="/facts/Greedy_algorithm/alfsekco">greedily</a> select k of the n data points as the medoids to minimize the cost</li>
<li>Associate each data point to the closest medoid.</li>
<li>(SWAP) While the cost of the configuration decreases:
<ol><li>For each medoid m, and for each non-medoid data point o:
<ol><li>Consider the swap of m and o, and compute the cost change</li>
<li>If the cost change is the current best, remember this m and o combination</li></ol></li>
<li>Perform the best swap of 
 
 
 
 
 m
 
 best
 
 
 
 
 {\displaystyle m_{\text{best}}}
 
 and 
 
 
 
 
 o
 
 best
 
 
 
 
 {\displaystyle o_{\text{best}}}
 
, if it decreases the cost function. Otherwise, the algorithm terminates.</li></ol></li></ol>
The runtime complexity of the original PAM algorithm per iteration of (3) is 
 
 
 
 O
 (
 k
 (
 n
 −
 k
 
 )
 
 2
 
 
 )
 
 
 {\displaystyle O(k(n-k)^{2})}
 
, by only computing the change in cost. A naive implementation recomputing the entire cost function every time will be in 
 
 
 
 O
 (
 
 n
 
 2
 
 
 
 k
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2}k^{2})}
 
. This runtime can be further reduced to 
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2})}
 
, by splitting the cost change into three parts such that computations can be shared or avoided (FastPAM). The runtime can further be reduced by eagerly performing swaps (FasterPAM),<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> at which point a random initialization becomes a viable alternative to BUILD.

<h3>Alternating Optimization</h3>
Algorithms other than PAM have also been suggested in the literature, including the following <a href="/facts/Lloyd%27s_algorithm/LuersNRa">Voronoi iteration</a> method known as the "Alternating" heuristic in literature, as it alternates between two optimization steps:<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<ol><li>Select initial medoids randomly</li>
<li>Iterate while the cost 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>
k-means-style Voronoi iteration tends to produce worse results, and exhibit "erratic behavior".<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>: 957  Because it does not allow re-assigning points to other clusters while updating means it only explores a smaller search space. It can be shown that even in simple cases this heuristic finds inferior solutions the swap based methods can solve.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>

<h3>Hierarchical Clustering</h3>
Multiple variants of <a href="/facts/Hierarchical_clustering/KxXs6GPK">hierarchical clustering</a> with a "medoid linkage" have been proposed. The Minimum Sum linkage criterion<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> directly uses the objective of medoids, but the Minimum Sum Increase linkage was shown to produce better results (similar to how Ward linkage uses the increase in squared error). Earlier approaches simply used the distance of the cluster medoids of the previous medoids as linkage measure,<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a><a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> but which tends to result in worse solutions, as the distance of two medoids does not ensure there exists a good medoid for the combination. These approaches have a run time complexity of 
 
 
 
 O
 (
 
 n
 
 3
 
 
 )
 
 
 {\displaystyle O(n^{3})}
 
, and when the dendrogram is cut at a particular number of clusters k, the results will typically be worse than the results found by PAM.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> Hence these methods are primarily of interest when a hierarchical tree structure is desired.

<h3>Other Algorithms</h3>
Other approximate algorithms such as CLARA and CLARANS trade quality for runtime. CLARA applies PAM on multiple subsamples, keeping the best result. CLARANS works on the entire data set, but only explores a subset of the possible swaps of medoids and non-medoids using sampling. BanditPAM uses the concept of multi-armed bandits to choose candidate swaps instead of uniform sampling as in CLARANS.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>

<h2 id="software">Software</h2>
<ul><li><a href="/facts/ELKI/C2LWqW13">ELKI</a> includes several k-medoid variants, including a Voronoi-iteration k-medoids, the original PAM algorithm, Reynolds' improvements, and the O(n²) FastPAM and FasterPAM algorithms, CLARA, CLARANS, FastCLARA and FastCLARANS.</li>
<li><a href="/facts/Julia_language/AoB0PJ9C">Julia</a> contains a k-medoid implementation of the k-means style algorithm (fast, but much worse result quality) in the <a href="https://github.com/JuliaStats/Clustering.jl">JuliaStats/Clustering.jl</a> package.</li>
<li><a href="/facts/KNIME/232lez5G">KNIME</a> includes a k-medoid implementation supporting a variety of efficient matrix distance measures, as well as a number of native (and integrated third-party) k-means implementations</li>
<li><a href="/facts/Python_(programming_language)/YbuGqofa">Python</a> contains FasterPAM and other variants in the "<a href="https://pypi.org/project/kmedoids/">kmedoids</a>" package, additional implementations can be found in many other packages</li>
<li><a href="/facts/R_(programming_language)/LSrkr8K8">R</a> contains PAM in the "<a href="https://cran.r-project.org/web/packages/cluster/index.html">cluster</a>" package, including the FasterPAM improvements via the options variant = "faster" and medoids = "random". There also exists a "fastkmedoids" package.</li>
<li><a href="/facts/RapidMiner/F7jGMflS">RapidMiner</a> has an operator named KMedoids, but it does not implement any of above KMedoids algorithms. Instead, it is a k-means variant, that substitutes the mean with the closest data point (which is not the medoid), which combines the drawbacks of k-means (limited to coordinate data) with the additional cost of finding the nearest point to the mean.</li>
<li><a href="/facts/Rust_(programming_language)/8JNMV19F">Rust</a> has a "<a href="https://crates.io/crates/kmedoids">kmedoids</a>" crate that also includes the FasterPAM variant.</li>
<li><a href="/facts/MATLAB/qPjLISCk">MATLAB</a> implements PAM, CLARA, and two other algorithms to solve the k-medoid clustering problem.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Kaufman, Leonard; Rousseeuw, Peter J. (1990-03-08), "Partitioning Around Medoids (Program PAM)", Wiley Series in Probability and Statistics, Hoboken, NJ, USA: John Wiley & Sons, Inc., pp. 68–125, doi:10.1002/9780470316801.ch2, ISBN 978-0-470-31680-1, retrieved 2021-06-13 <a href="978-0-470-31680-1" target="_blank">978-0-470-31680-1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Hsu, Wen-Lian; Nemhauser, George L. (1979). "Easy and hard bottleneck location problems". Discrete Applied Mathematics. 1 (3): 209–215. doi:10.1016/0166-218X(79)90044-1 – via Elsevier Science Direct. <a href="https://www.sciencedirect.com/science/article/pii/0166218X79900441?via%3Dihub" target="_blank">https://www.sciencedirect.com/science/article/pii/0166218X79900441?via%3Dihub</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Kaufman, Leonard; Rousseeuw, Peter J. (1990-03-08), "Partitioning Around Medoids (Program PAM)", Wiley Series in Probability and Statistics, Hoboken, NJ, USA: John Wiley & Sons, Inc., pp. 68–125, doi:10.1002/9780470316801.ch2, ISBN 978-0-470-31680-1, retrieved 2021-06-13 <a href="978-0-470-31680-1" target="_blank">978-0-470-31680-1</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Schubert, Erich; Rousseeuw, Peter J. (2021). "Fast and eager k -medoids clustering: O(k) runtime improvement of the PAM, CLARA, and CLARANS algorithms". Information Systems. 101: 101804. arXiv:2008.05171. doi:10.1016/j.is.2021.101804. S2CID 221103804. <a href="/wiki/Peter_Rousseeuw" target="_blank">/wiki/Peter_Rousseeuw</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Maranzana, F. E. (1963). "On the location of supply points to minimize transportation costs". IBM Systems Journal. 2 (2): 129–135. doi:10.1147/sj.22.0129. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning, Springer (2001), 468–469. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Park, Hae-Sang; Jun, Chi-Hyuck (2009). "A simple and fast algorithm for K-medoids clustering". Expert Systems with Applications. 36 (2): 3336–3341. doi:10.1016/j.eswa.2008.01.039. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Teitz, Michael B.; Bart, Polly (1968-10-01). "Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph". Operations Research. 16 (5): 955–961. doi:10.1287/opre.16.5.955. ISSN 0030-364X. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Schubert, Erich; Rousseeuw, Peter J. (2021). "Fast and eager k -medoids clustering: O(k) runtime improvement of the PAM, CLARA, and CLARANS algorithms". Information Systems. 101: 101804. arXiv:2008.05171. doi:10.1016/j.is.2021.101804. S2CID 221103804. <a href="/wiki/Peter_Rousseeuw" target="_blank">/wiki/Peter_Rousseeuw</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Schubert, Erich (2021). HACAM: Hierarchical Agglomerative Clustering Around Medoids – and its Limitations (PDF). LWDA’21: Lernen, Wissen, Daten, Analysen September 01–03, 2021, Munich, Germany. pp. 191–204 – via CEUR-WS. <a href="http://star.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-2993/paper-19.pdf" target="_blank">http://star.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-2993/paper-19.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Miyamoto, Sadaaki; Kaizu, Yousuke; Endo, Yasunori (2016). Hierarchical and Non-Hierarchical Medoid Clustering Using Asymmetric Similarity Measures. 2016 Joint 8th International Conference on Soft Computing and Intelligent Systems (SCIS) and 17th International Symposium on Advanced Intelligent Systems (ISIS). pp. 400–403. doi:10.1109/SCIS-ISIS.2016.0091. <a href="https://ieeexplore.ieee.org/document/7801678" target="_blank">https://ieeexplore.ieee.org/document/7801678</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Herr, Dominik; Han, Qi; Lohmann, Steffen; Ertl, Thomas (2016). Visual Clutter Reduction through Hierarchy-based Projection of High-dimensional Labeled Data (PDF). Graphics Interface. Graphics Interface. doi:10.20380/gi2016.14. Retrieved 2022-11-04. <a href="https://graphicsinterface.org/wp-content/uploads/gi2016-14.pdf" target="_blank">https://graphicsinterface.org/wp-content/uploads/gi2016-14.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Schubert, Erich (2021). HACAM: Hierarchical Agglomerative Clustering Around Medoids – and its Limitations (PDF). LWDA’21: Lernen, Wissen, Daten, Analysen September 01–03, 2021, Munich, Germany. pp. 191–204 – via CEUR-WS. <a href="http://star.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-2993/paper-19.pdf" target="_blank">http://star.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-2993/paper-19.pdf</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Tiwari, Mo; Zhang, Martin J.; Mayclin, James; Thrun, Sebastian; Piech, Chris; Shomorony, Ilan (2020). "BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits". Advances in Neural Information Processing Systems. 33. <a href="https://proceedings.neurips.cc/paper/2020/hash/73b817090081cef1bca77232f4532c5d-Abstract.html" target="_blank">https://proceedings.neurips.cc/paper/2020/hash/73b817090081cef1bca77232f4532c5d-Abstract.html</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
</ol>

k-medoids open-in-new

k-medoids