An Empirical Evaluation of $k$-Means Coresets
| Autor: | Schwiegelshohn, Chris, Sheikh-Omar, Omar Ali |
|---|---|
| Přispěvatelé: | Chechik, Shiri, Navarro, Gonzalo, Rotenberg, Eva, Herman, Grzegorz |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Machine Learning evaluation benchmark TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Computer Science - Data Structures and Algorithms k-means coresets Data Structures and Algorithms (cs.DS) Information systems → Clustering Theory of computation → Data compression Machine Learning (cs.LG) coresets |
| Zdroj: | Schwiegelshohn, C & Sheikh-Omar, O A 2022, An Empirical Evaluation of k-Means Coresets . in S Chechik, G Navarro, E Rotenberg & G Herman (eds), 30th Annual European Symposium on Algorithms, ESA 2022 . Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 244, pp. 84:1-84:17, 30th Annual European Symposium on Algorithms, ESA 2022, Berlin/Potsdam, Germany, 05/09/2022 . https://doi.org/10.4230/LIPIcs.ESA.2022.84 |
| DOI: | 10.4230/LIPIcs.ESA.2022.84 |
| Popis: | Coresets are among the most popular paradigms for summarizing data. In particular, there exist many high performance coresets for clustering problems such as k-means in both theory and practice. Curiously, there exists no work on comparing the quality of available k-means coresets. In this paper we perform such an evaluation. There currently is no algorithm known to measure the distortion of a candidate coreset. We provide some evidence as to why this might be computationally difficult. To complement this, we propose a benchmark for which we argue that computing coresets is challenging and which also allows us an easy (heuristic) evaluation of coresets. Using this benchmark and real-world data sets, we conduct an exhaustive evaluation of the most commonly used coreset algorithms from theory and practice. LIPIcs, Vol. 244, 30th Annual European Symposium on Algorithms (ESA 2022), pages 84:1-84:17 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|