K-means++
k -means++ je vylepšená verze shlukovacího algoritmu k -means . Podstatou vylepšení je najít více „dobrých“ počátečních hodnot těžišť clusteru. Původní k-means nespecifikuje, jak se tento krok algoritmu provádí, a proto je nestabilní. Algoritmus byl navržen v roce 2007 Davidem Arthurem a Sergejem Vassilvitským. Existují také další podobné metody objevené jinými vědci nezávisle.
Inicializace
- Vyberte první těžiště náhodně (mezi všemi body)
- Pro každý bod najděte hodnotu druhé mocniny vzdálenosti k nejbližšímu těžišti (z těch již vybraných) dx²
- Vyberte z těchto bodů další těžiště tak, aby pravděpodobnost výběru bodu byla úměrná druhé mocnině vzdálenosti pro něj vypočítané.To
lze provést následovně. V kroku 2 musíte spočítat součet Sum(dx²) souběžně s výpočtem dx². Po sečtení součtu najděte hodnotu Rnd=random(0.0,1.0)*Sum. Rnd bude náhodně ukazovat na číslo z intervalu [0; Součet) a my musíme pouze určit, kterému bodu to odpovídá. Chcete-li to provést, musíte znovu začít počítat součet S (dx²), dokud součet nepřekročí Rnd. Jakmile k tomu dojde, sčítání se zastaví a můžeme vzít aktuální bod jako těžiště.
Při výběru každého dalšího těžiště není nutné dbát na to, aby se nekrylo s některým z bodů již zvolených jako těžiště, protože pravděpodobnost opětovného výběru určitého bodu je 0.
- Opakujte kroky 2 a 3, dokud nenajdete všechna požadovaná těžiště.
Dále je proveden hlavní algoritmus k -means .
Implementace
Implementace jazyka Java je součástí populární knihovny Apache [1] .
Poznámky
- ↑ Commons Math: The Apache Commons Mathematics Library . Datum přístupu: 20. září 2013. Archivováno z originálu 6. října 2014. (neurčitý)