I detta dokument studeras k-means++-algoritm för klustring samt den klass av D-provtagningsalgoritmer som k-means++ tillhör. Det visas att för varje konstant faktor β > 1 ger valet av βk klustercenter genom D-provtagning en konstant-faktor approximation till den optimala klustereringen med k-centra, i förväntan och utan villkor på datauppsättningen. Detta resultat utvidgar den tidigare kända O(log k)-garantin för ärendet β = 1 till systemet med bikriterier med konstant faktor. Det förbättras också på en befintlig konstant faktor bi-criteria resultat som håller bara med konstant sannolikhet.
Wei REF förbättrade K-means++-algoritmen genom att välja klustercentra med hjälp av provtagningsmetoden i K-means++-algoritmen och sedan producera k-centra med förväntan om att ha en ungefär konstant faktor för det bästa klusterresultatet.
A Constant-Factor Bi-Criteria Approximation Guarantee for $k$-means++
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}