AGORAS: A fast algorithm for estimating medoids in large datasets

Esteban M. Rangel, William Hendrix, Ankit Agrawal, Wei-Keng Liao, Alok Nidhi Choudhary

Research output: Contribution to journalConference article

5 Scopus citations

Abstract

The k-medoids methods for modeling clustered data have many desirable properties such as robustness to noise and the ability to use non-numerical values, however, they are typically not applied to large datasets due to their associated computational complexity. In this paper, we present AGORAS, a novel heuristic algorithm for the k-medoids problem where the algorithmic complexity is driven by, k, the number of clusters, rather than, n, the number of data points. Our algorithm attempts to isolate a sample from each individual cluster within a sequence of uniformly drawn samples taken from the complete data. As a result, computing the k-medoids solution using our method only involves solving k trivial sub-problems of centrality. This allows our algorithm to run in comparable time for arbitrarily large datasets with same underlying density distribution. We evaluate AGORAS experimentally against PAM and CLARANS - two of the best-known existing algorithms for the k-medoids problem - across a variety of published and synthetic datasets. We find that AGORAS outperforms PAM by up to four orders of magnitude for data sets with less than 10,000 points, and it outperforms CLARANS by two orders of magnitude on a dataset of just 64,000 points. Moreover, we find in some cases that AGORAS also outperforms in terms of cluster quality.

Original languageEnglish (US)
Pages (from-to)1159-1169
Number of pages11
JournalProcedia Computer Science
Volume80
DOIs
StatePublished - Jan 1 2016
EventInternational Conference on Computational Science, ICCS 2016 - San Diego, United States
Duration: Jun 6 2016Jun 8 2016

Keywords

  • Cluster analysis
  • K-medoids
  • Partitional clustering

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'AGORAS: A fast algorithm for estimating medoids in large datasets'. Together they form a unique fingerprint.

  • Cite this