K-betyder++
k -means++ er en forbedret version af k -betyder klyngealgoritmen . Essensen af forbedringen er at finde flere "gode" begyndelsesværdier for klyngecentroiderne. Det originale k-middel angiver ikke, hvordan dette trin i algoritmen udføres og er derfor ustabilt. Algoritmen blev foreslået i 2007 af David Arthur og Sergey Vassilvitsky. Der er også andre lignende metoder opdaget af andre videnskabsmænd uafhængigt.
Initialisering
- Vælg første tyngdepunkt tilfældigt (blandt alle punkter)
- For hvert punkt, find værdien af kvadratet af afstanden til nærmeste tyngdepunkt (af de allerede valgte) dx²
- Vælg fra disse punkter det næste tyngdepunkt, så sandsynligheden for at vælge et punkt er proportional med den kvadrerede afstand beregnet for det.Dette
kan gøres som følger. I trin 2 skal du beregne summen Sum(dx²) parallelt med beregningen af dx². Efter at have akkumuleret summen, find værdien Rnd=random(0.0,1.0)*Sum. Rnd vil tilfældigt pege på et tal fra intervallet [0; Sum), og vi skal kun bestemme hvilket punkt dette svarer til. For at gøre dette skal du begynde at tælle summen S (dx²) igen, indtil summen overstiger Rnd. Når dette sker, stopper summeringen, og vi kan tage det aktuelle punkt som tyngdepunkt.
Når du vælger hvert næste tyngdepunkt, er det ikke nødvendigt at sikre sig, at det ikke falder sammen med et af de punkter, der allerede er valgt som tyngdepunkter, da sandsynligheden for at genvælge et bestemt punkt er 0.
- Gentag trin 2 og 3, indtil alle nødvendige tyngdepunkter er fundet.
Dernæst udføres den primære k -betydningsalgoritme .
Implementeringer
En Java-sprogsimplementering er inkluderet i det populære Apache-bibliotek [1] .
Noter
- ↑ Commons Math: Apache Commons Mathematics Library . Dato for adgang: 20. september 2013. Arkiveret fra originalen 6. oktober 2014. (ubestemt)