K-jelentése++
A k -means++ a k -means klaszterező algoritmus továbbfejlesztett változata . A fejlesztés lényege, hogy több „jó” kezdeti értéket találjunk a klaszter-centroidoknak. Az eredeti k-közép nem határozza meg az algoritmus ezen lépésének végrehajtását, ezért instabil. Az algoritmust 2007-ben David Arthur és Sergey Vassilvitsky javasolta. Vannak más hasonló módszerek is, amelyeket más tudósok egymástól függetlenül fedeztek fel.
Inicializálás
- Véletlenszerűen válassza ki az első súlypontot (az összes pont közül)
- Minden ponthoz keresse meg a legközelebbi súlypont távolságának négyzetét (a már kiválasztottak közül) dx²
- Válassza ki ezek közül a pontok közül a következő súlypontot úgy, hogy egy pont kiválasztásának valószínűsége arányos legyen a neki kiszámított távolság négyzetével
Ez a következőképpen tehető meg. A 2. lépésben ki kell számítania a Sum(dx²) összeget a dx² kiszámításával párhuzamosan. Az összeg felhalmozása után keresse meg az Rnd=random(0.0,1.0)*Sum értéket. Rnd véletlenszerűen mutat egy számra a [0; Összeg), és csak azt kell meghatároznunk, hogy ez melyik pontnak felel meg. Ehhez újra el kell kezdenie számolni az S (dx²) összeget, amíg az összeg meg nem haladja az Rnd értéket. Ha ez megtörténik, az összegzés leáll, és az aktuális pontot vehetjük súlypontnak.
Minden egyes következő súlypont kiválasztásakor nem szükséges megbizonyosodni arról, hogy nem esik egybe a már középpontként kiválasztott pontok egyikével, mivel egy bizonyos pont újraválasztásának valószínűsége 0.
- Ismételje meg a 2. és 3. lépést, amíg meg nem találja az összes szükséges súlypontot.
Ezután a fő k -means algoritmust hajtjuk végre.
Megvalósítások
A népszerű Apache könyvtár [1] tartalmaz egy Java nyelvi implementációt .
Jegyzetek
- ↑ Commons Math: The Apache Commons Mathematics Library . Hozzáférés időpontja: 2013. szeptember 20. Az eredetiből archiválva : 2014. október 6.. (határozatlan)