التفاصيل البيبلوغرافية
| العنوان: |
Improved Guarantees for k-means++ and k-means++ Parallel |
| المؤلفون: |
Makarychev, Konstantin, Reddy, Aravind, Shan, Liren |
| المصدر: |
NeurIPS 2020 |
| سنة النشر: |
2020 |
| المجموعة: |
Computer Science |
| مصطلحات موضوعية: |
Computer Science - Machine Learning, Computer Science - Data Structures and Algorithms |
| الوصف: |
In this paper, we study k-means++ and k-means++ parallel, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved approximation and bi-criteria approximation guarantees for k-means++ and k-means++ parallel. Our results give a better theoretical justification for why these algorithms perform extremely well in practice. We also propose a new variant of k-means++ parallel algorithm (Exponential Race k-means++) that has the same approximation guarantees as k-means++. |
| نوع الوثيقة: |
Working Paper |
| URL الوصول: |
http://arxiv.org/abs/2010.14487 |
| رقم الانضمام: |
edsarx.2010.14487 |
| قاعدة البيانات: |
arXiv |