K-Medoids Clustering Algorithm Performance

Abstract

Klusteranalyse er muligens det viktigste problemet i maskinlæring uten tilsyn. Løsing av klusteringproblemet er NP-hardt, og krever derfor heuristiske algoritmer selv for små problemstørrelser. Siden introduksjonen av $k$-medoider algoritmer har det vært betydelig fremgang innen teoretisk kompleksitet. Imidlertid er det knappe ressurser tilgjengelig for sammenligning av nylige utviklinger, og dette verket har forsøkt å svare på dette problemet ved å grundig sammenligne diverse $k$-medoider algoritmer. Gjennom ytelsesmåling på populære datasett viser vi at nylige utviklinger representerer betydelig fremgang, og til og med åpner for bruk av $k$-medoider på medium-store datasett.

Clustering is perhaps the most important problem in unsupervised machine learning. Solving the clustering problem is NP-hard, and so approximate algorithms are necessary even for small problem sizes. Since the introduction of $k$-medoids algorithms, significant progress has been made on theoretical complexity. However, the resources comparing recent developments have been limited, and this work has sought to alleviate this issue by thoroughly comparing various $k$-medoids algorithms. By benchmarking on popular datasets, we show that recent developments indeed represent significant progress, and even enable usage of $k$-medoids on medium-large datasets.