Metoda k-means

Metoda k - means je nejoblíbenější metodou shlukování .  Vynalezl jej v 50. letech 20. století matematik Hugo Steinhaus [1] a téměř současně Stuart Lloyd [2] . Získal zvláštní popularitu po práci McQueena [3] .

Činnost algoritmu je taková, že se snaží minimalizovat celkovou čtvercovou odchylku bodů shluku od středů těchto shluků:

kde  je počet shluků,  jsou výsledné shluky, a  jsou těžiště všech vektorů ze shluku .

Analogicky s metodou hlavních komponent se středy shluků také nazývají hlavní body a samotná metoda se nazývá metoda hlavních bodů [4] a je zahrnuta v obecné teorii hlavních objektů , které poskytují nejlepší aproximaci dat. [5] .

Algoritmus

Algoritmus je verzí EM algoritmu , který se také používá k oddělení směsi Gaussiánů . Rozdělí množinu prvků vektorového prostoru do předem známého počtu shluků k .

Hlavní myšlenkou je, že při každé iteraci je těžiště přepočítáno pro každý shluk získaný v předchozím kroku, poté jsou vektory opět rozděleny do shluků podle toho, které z nových středů se ukázalo být bližší podle zvolené metriky.

Algoritmus se ukončí, když v nějaké iteraci nedojde ke změně vzdálenosti uvnitř clusteru. To se děje v konečném počtu iterací, protože počet možných rozdělení konečné množiny je konečný a v každém kroku se celková kvadratická odchylka V snižuje, takže smyčkování je nemožné.

Jak ukázali David Arthur a Sergey Vasilvitsky, na některých třídách množin je složitost algoritmu z hlediska času potřebného pro konvergenci [6] .

Ukázka algoritmu

Činnost algoritmu ve dvourozměrném případě. Počáteční body jsou vybrány náhodně.

Problémy s k-means

Rozšíření a variace

Široko známá a používaná je implementace neuronové sítě K-means - síť vektorové kvantizace signálů (jedna z verzí Kohonenovy neuronové sítě ).

Existuje rozšíření k-means++ , které je zaměřeno na optimální volbu počátečních hodnot středů clusteru.


Aplikace pro hluboké učení a strojové vidění

V algoritmech hlubokého učení se metoda k-means někdy nepoužívá pro svůj zamýšlený účel (klasifikace pomocí shlukování), ale pro vytvoření takzvaných filtrů (konvoluční jádra, slovníky). Například pro rozpoznávání obrazu je algoritmus k-means napájen malými náhodnými kousky obrazů cvičných vzorků, řekněme o velikosti 16x16, jako lineární vektor, jehož každý prvek kóduje jas svého bodu. Počet shluků k je nastaven velký, například 256. Trénovaná metoda k-průměrů za určitých podmínek vytváří shluková centra (centroidy), což jsou vhodné báze, na které lze rozložit jakýkoli vstupní obraz. Takto „vycvičené“ centroidy se dále používají jako filtry například pro konvoluční neuronové sítě jako konvoluční jádra nebo jiné podobné systémy strojového vidění [8] . Učení bez dozoru se tedy provádí pomocí metody k-means.

Odkazy

  1. ↑ Steinhaus H. (1956). Sur la division des corps materiels en parties. Býk. Akad. Polon. Sc., C1. III sv. IV: 801-804.
  2. ↑ Lloyd S. (1957). Kvantování metodou nejmenších čtverců v PCM. Bell Telephone Laboratories Paper.
  3. ↑ MacQueen J. (1967). Některé metody klasifikace a analýzy vícerozměrných pozorování. V Proc. 5. Berkeley Symp. na matematiku. Statistika a pravděpodobnost, strany 281-297.
  4. ↑ Flury B. (1990). hlavní body. Biometrika, 77, 33-41.
  5. ↑ Gorban AN, Zinovyev AY (2009). Hlavní grafy a variety , Ch. 2 v: Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods and Techniques, Emilio Soria Olivas et al. (eds), IGI Global, Hershey, PA, USA, str. 28-59.
  6. ↑ David Arthur a Sergei Vassilvitskii (2006). "Jak pomalá je metoda k-means?" (PDF) . Sborník příspěvků 2006 Symposium on Computational Geometry (SoCG) . Archivováno (PDF) z originálu 2009-01-24 . Získáno 20.04.2008 . Použitý zastaralý parametr |deadlink=( nápověda )
  7. ↑ Applet EM Mirkes, K-means a K-medoids Archivováno 29. května 2013 na Wayback Machine . University of Leicester, 2011.
  8. ↑ Adam Coates a Andrew Y. Ng. Reprezentace vzdělávacích funkcí s K-means Archivováno 21. června 2015 na Wayback Machine , Stanford University, 2012

Ukázka a vizualizace