AGORAS: A Fast Algorithm for Estimating Medoids in Large Datasets
| Autor: | Ankit Agrawal, William Hendrix, Esteban Rangel, Alok Choudhary, Wei-keng Liao |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
021103 operations research
k-medoids Computational complexity theory Heuristic (computer science) Computer science 0211 other engineering and technologies 02 engineering and technology computer.software_genre Medoid Arbitrarily large Data point ComputingMethodologies_PATTERNRECOGNITION Robustness (computer science) 0202 electrical engineering electronic engineering information engineering Cluster (physics) General Earth and Planetary Sciences partitional clustering 020201 artificial intelligence & image processing Data mining Centrality Algorithm computer General Environmental Science cluster analysis |
| Zdroj: | ICCS |
| ISSN: | 1877-0509 |
| DOI: | 10.1016/j.procs.2016.05.446 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|