Över ett halvt sekel gamla och visar inga tecken på åldrande, k-medel är fortfarande en av de mest populära databehandling algoritmer. Som bekant är en korrekt initiering av k-medel avgörande för att få en bra slutlig lösning. Den nyligen föreslagna k-means++ initieringsalgoritm uppnår detta, erhålla en inledande uppsättning av centra som är bevisligen nära den optimala lösningen. En stor nackdel med k-means++ är dess inneboende sekventiella natur, som begränsar dess tillämplighet till massiva data: man måste göra k passerar över data för att hitta en bra första uppsättning centra. I detta arbete visar vi hur man drastiskt kan minska antalet passerkort som behövs för att parallellt få en god initialisering. Detta är olikt rådande ansträngningar på parallellisering k-medel som mest har fokuserat på post-initialization faser av k-medel. Vi bevisar att vår föreslagna initieringsalgoritm k-means en nästan optimal lösning efter ett logaritmiskt antal pass, och sedan visa att i praktiken ett konstant antal pass räcker. Experimentell utvärdering av storskaliga data i realworld visar att k-means på ett bättre sätt än k-means++ i både sekventiella och parallella inställningar.
Bahman Bahmani m.fl. REF föreslog en initialiseringsalgoritm för att få en nästan optimal lösning efter ett logaritmiskt antal pass och visade sedan att det i praktiken räcker med ett konstant antal pass.
Scalable K-Means++
{'venue': 'Proceedings of the VLDB Endowment (PVLDB), Vol. 5, No. 7, pp. 622-633 (2012)', 'journal': None, 'mag_field_of_study': ['Computer Science']}