Kohonenovy mapy (SOM)

K-means ti řekne, do kterého shluku bod patří, a víc nic. Když se zeptáš, jestli je shluk 3 podobnější shluku 7 nebo shluku 12, nemá ti co odpovědět - čísla shluků jsou libovolné popisky bez vztahu.

Kohonenova mapa tuhle otázku zodpoví, protože shluky rozmístí do mřížky tak, aby sousedé v mřížce byli podobní i v datech. Výsledkem není seznam, ale mapa, na které se dá orientovat.

Tahle stránka popisuje architekturu a algoritmus učení SOM. Předpokládá to umělý neuron a shlukování, zejména k-means, protože se na kontrast s ním pořád odkazuje.

Definice

Self-Organizing Map (T. Kohonen, 1982) je síť s učením bez učitele, která zobrazuje vysokodimenzionální vstupní prostor na nízkodimenzionální - typicky dvourozměrnou - mřížku se zachováním topologie.

Ta poslední tři slova jsou celý rozdíl proti obyčejnému shlukování. Zachování topologie znamená, že body blízké ve vstupním prostoru skončí u blízkých neuronů v mřížce. Odtud plyne, proč se výsledek dá nakreslit a proč se z něj dá něco vyčíst pouhým pohledem.

Architektura

Vstupní vektor x = (x1, ..., xn) je připojen ke každému neuronu výstupní mřížky. Každý neuron i má svůj váhový vektor wi o stejné dimenzi jako vstup.

To je jiná úvaha, než na jakou jsi zvyklý z MLP. Váhový vektor tady není „síla spojení", ale bod ve vstupním prostoru - je to reprezentant, prototyp, těžiště. SOM je vlastně mřížka bodů, která se do dat rozprostře jako síťka.

Neurony v mřížce nejsou propojené. Jejich uspořádání do mřížky slouží jen k definici sousedství, nic přes ně neteče.

Algoritmus učení

Inicializace vah wi náhodnými malými hodnotami.
Pro každý trénovací vzor x:
- (a) spočítej euklidovskou vzdálenost ke každému neuronu:
```
Di = Σ (xk − wi,k)²        pro k = 1..n
```
- (b) najdi vítěze (BMU - Best Matching Unit) s nejmenší Di,
- (c) uprav váhy vítěze a jeho okolí R:
```
wi_nové = wi_staré + α (x − wi_staré)
```
  přičemž pro okolí platí míra učení β < α.
Poloměr okolí R i rychlosti α a β se v čase postupně zmenšují.

flowchart TD
    A["vezmi vzor x"] --> B["spočítej vzdálenost ke všem neuronům"]
    B --> C["najdi vítěze BMU"]
    C --> D["přitáhni vítěze k x rychlostí α"]
    D --> E["přitáhni sousedy v okolí R rychlostí β < α"]
    E --> F["zmenši R, α, β"]
    F --> A

Krok (c) je celý trik a je to nejdůležitější věc na téhle stránce. K-means posune jen vítězný střed. SOM posune i jeho sousedy v mřížce, byť slaběji. Tím se sousední neurony táhnou ke stejné oblasti dat - a přesně tak vznikne to zachování topologie.

Bez toho posunu okolí by ze SOM bylo k-means s divně organizovanými středy a nic víc.

Proč se R, α a β zmenšují. Na začátku je okolí velké a rychlost vysoká, takže se celá mřížka hrubě rozprostře a najde tvar dat. Ke konci je okolí malé a rychlost nízká, takže se jednotlivé neurony jen dolaďují. Je to stejná myšlenka jako simulované žíhání - nejdřív hrubě, pak jemně - a bez ní by se mřížka zamotala do sebe a nikdy nerozmotala.

Konvergence a aplikace

SOM typicky konverguje během 10 000 i více iterací. To je řádově víc, než potřebuje k-means, a je to daň za tu strukturu navíc.

Výstupem je dvourozměrná „mapa", v níž se podobné vstupní vzory shlukují k sobě. Použití:

rozpoznávání řeči a rukou psaného textu,
klastrování dokumentů (WebSOM),
analýza obrazových dat, kompresní mapování barev,
segmentace zákazníků, detekce anomálií.

Kompresní mapování barev je nejnázornější příklad. Vstupem jsou trojice RGB, mřížka je dvourozměrná. SOM se naučí paletu barev, ve které jsou podobné odstíny vedle sebe - takže výsledek se dá nejen použít jako paleta, ale i vytisknout a podívat se na něj.

Kde SOM přestává platit

Musíš zadat velikost mřížky předem. Je to tentýž problém jako k u k-means, jen ve dvou rozměrech. Mřížka 10×10 znamená sto prototypů, ať je v datech shluků kolik chce.

Mapa se dá špatně interpretovat. Že jsou dva neurony vedle sebe, ještě neznamená, že je mezi jejich daty malá vzdálenost - mřížka je konečná a někam se to natlačit musí. Řeší se to U-maticí, která k mapě dokreslí skutečné vzdálenosti mezi sousedy a udělá z ní čitelnou „krajinu" s hřebeny mezi shluky.

Nezachová vzdálenosti, jen sousednost. SOM je topologické, ne metrické zobrazení. Když potřebuješ zachovat i vzdálenosti, jdi na MDS nebo t-SNE.

Je pomalá a má hodně parametrů. Velikost mřížky, počáteční R, α, β, plány jejich zmenšování, počet iterací. U velkých dat je dnes obvykle lepší kombinace PCA nebo t-SNE pro vizualizaci a DBSCAN pro shluky.

Dneska se používá spíš vzácně. Pro vizualizaci vysokodimenzionálních dat vyhrálo t-SNE a UMAP, pro shlukování k-means a DBSCAN. SOM se drží tam, kde je potřeba současně shlukovat a mít z toho čitelnou mapu.

Co se na tom nejčastěji rozbije

Příznak	Kde je problém
Mřížka je zamotaná sama do sebe	příliš rychlé zmenšování `R` - začni s okolím přes půl mřížky
Všechny neurony skončily v jednom bodě	příliš velké `α` nebo příliš dlouho velké okolí
Část neuronů se nikdy nestala vítězem	mřížka je moc velká proti počtu dat, nebo špatná inicializace
Mapa vypadá náhodně	chybí normalizace vstupů
Nejde poznat, kde jsou hranice shluků	potřebuješ U-matici, samotná mapa hranice neukáže

Co si odnést

SOM je shlukování se zachováním topologie. Sousedé v mřížce jsou si podobní i v datech.

Váhový vektor neuronu je bod ve vstupním prostoru, ne síla spojení.

Posun okolí vítěze je celý trik. Bez něj je to k-means.

R, α a β se musí zmenšovat - nejdřív hrubě, pak jemně, jako u žíhání.

Velikost mřížky zadáváš předem a je to stejné rozhodnutí jako volba k.

Zachovává sousednost, ne vzdálenosti. Na vzdálenosti si dokresli U-matici.

Kam dál

Shlukování - k-means, hierarchické metody a DBSCAN pro srovnání
Topologie a učení sítí - kam SOM patří mezi ostatní sítě
Neuron a perceptron - Hebbovo pravidlo, ze kterého učení bez učitele vychází
Metriky a vyhodnocení - metriky vzdálenosti, na kterých SOM stojí