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 language | English (US) |
---|---|
Pages (from-to) | 1159-1169 |
Number of pages | 11 |
Journal | Procedia Computer Science |
Volume | 80 |
DOIs | |
State | Published - 2016 |
Event | International Conference on Computational Science, ICCS 2016 - San Diego, United States Duration: Jun 6 2016 → Jun 8 2016 |
Funding
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.
Keywords
- Cluster analysis
- K-medoids
- Partitional clustering
ASJC Scopus subject areas
- General Computer Science