TY - JOUR

T1 - AGORAS

T2 - International Conference on Computational Science, ICCS 2016

AU - Rangel, Esteban M.

AU - Hendrix, William

AU - Agrawal, Ankit

AU - Liao, Wei Keng

AU - Choudhary, Alok

N1 - Funding Information:
This work is supported in part by the following grants: NSF awards CCF-1409601, IIS-1343639, and CCF-1029166; DOE awards DESC0007456 and DE-SC0014330; AFOSR award FA9550-12-1-0458; NIST award 70NANB14H012.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - Cluster analysis

KW - K-medoids

KW - Partitional clustering

UR - http://www.scopus.com/inward/record.url?scp=84978485240&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84978485240&partnerID=8YFLogxK

U2 - 10.1016/j.procs.2016.05.446

DO - 10.1016/j.procs.2016.05.446

M3 - Conference article

AN - SCOPUS:84978485240

VL - 80

SP - 1159

EP - 1169

JO - Procedia Computer Science

JF - Procedia Computer Science

SN - 1877-0509

Y2 - 6 June 2016 through 8 June 2016

ER -