K-înseamnă ++

k -means++  este o versiune îmbunătățită a algoritmului de grupare k -means . Esența îmbunătățirii este găsirea unor valori inițiale mai „bune” ale centroizilor clusterului. Mijloacele k originale nu specifică modul în care se realizează acest pas al algoritmului și, prin urmare, este instabilă. Algoritmul a fost propus în 2007 de David Arthur și Sergey Vassilvitsky. Există și alte metode similare descoperite de alți oameni de știință în mod independent.

Inițializare

1. Alegeți primul centroid la întâmplare (dintre toate punctele)
2. Pentru fiecare punct, găsiți valoarea pătratului distanței până la cel mai apropiat centroid (dintre cei deja selectați) dx²
3. Alegeți din aceste puncte următorul centroid, astfel încât probabilitatea de a alege un punct să fie proporțională cu distanța la pătrat calculată pentru acesta.Acest
   lucru se poate face după cum urmează. La pasul 2, trebuie să calculați suma Sum(dx²) în paralel cu calculul lui dx². După acumularea sumei, găsiți valoarea Rnd=random(0.0,1.0)*Sum. Rnd va indica aleatoriu un număr din intervalul [0; Sumă), și nu trebuie decât să stabilim cărui punct îi corespunde. Pentru a face acest lucru, trebuie să începeți să numărați din nou suma S (dx²) până când suma depășește Rnd. Odată ce se întâmplă acest lucru, însumarea se oprește și putem lua punctul curent drept centroid.
   Atunci când alegeți următorul centroid, nu este necesar să vă asigurați că acesta nu coincide cu unul dintre punctele deja alese ca centroid, deoarece probabilitatea de a reselege un anumit punct este 0.
4. Repetați pașii 2 și 3 până când sunt găsiți toți centroizii necesari.

În continuare, se execută algoritmul principal k -means .

Implementări

O implementare a limbajului Java este inclusă în populara bibliotecă Apache [1] .

Note

1. ↑ Commons Math: Biblioteca de matematică Apache Commons . Data accesului: 20 septembrie 2013. Arhivat din original pe 6 octombrie 2014. (nedefinit)