K-betyder++
k -means++ är en förbättrad version av k -means- klustringsalgoritmen . Kärnan i förbättringen är att hitta fler "bra" initiala värden för klustrets centroider. Det ursprungliga k-medlet specificerar inte hur detta steg i algoritmen utförs och är därför instabilt. Algoritmen föreslogs 2007 av David Arthur och Sergey Vassilvitsky. Det finns också andra liknande metoder som upptäckts av andra forskare oberoende.
Initiering
- Välj första tyngdpunkten slumpmässigt (bland alla punkter)
- För varje punkt, hitta värdet på kvadraten på avståndet till närmaste tyngdpunkt (av de redan valda) dx²
- Välj från dessa punkter nästa tyngdpunkt så att sannolikheten för att välja en punkt är proportionell mot det kvadratiska avståndet som beräknas för den
. Detta kan göras på följande sätt. I steg 2 måste du beräkna summan Sum(dx²) parallellt med beräkningen av dx². Efter att ha ackumulerat summan, hitta värdet Rnd=random(0.0,1.0)*Summa. Rnd kommer slumpmässigt att peka på ett tal från intervallet [0; Summa), och vi behöver bara bestämma vilken punkt detta motsvarar. För att göra detta måste du börja räkna summan S (dx²) igen tills summan överstiger Rnd. När detta händer stoppas summeringen och vi kan ta den aktuella punkten som tyngdpunkten.
När du väljer varje nästa tyngdpunkt är det inte nödvändigt att se till att det inte sammanfaller med en av punkterna som redan har valts som tyngdpunkter, eftersom sannolikheten för att välja en viss punkt är 0.
- Upprepa steg 2 och 3 tills alla nödvändiga tyngdpunkter har hittats.
Därefter exekveras den huvudsakliga k -medelalgoritmen .
Implementeringar
En Java-språkimplementering ingår i det populära Apache-biblioteket [1] .
Anteckningar
- ↑ Commons Math: Apache Commons Mathematics Library . Datum för åtkomst: 20 september 2013. Arkiverad från originalet den 6 oktober 2014. (obestämd)