Shlukování

K-means najde tři shluky vždycky. I když v datech žádné nejsou. I když jsou čtyři. Zadáš k = 3 a algoritmus poslušně rozdělí prostor na tři části, spočítá těžiště a vrátí výsledek, který vypadá naprosto věrohodně.

Tohle je zásadní rozdíl oproti klasifikaci. Klasifikátor se dá otestovat - máš označená data a spočítáš přesnost. U shlukování žádná správná odpověď neexistuje, takže se nemáš čeho chytit a musíš výsledku rozumět, ne mu věřit.

Tahle stránka probírá tři rodiny shlukovacích metod a hlavně to, kde každá z nich selhává. Předpokládá to klasifikaci a rozpoznávání - rozdíl mezi klasifikací, rozpoznáváním a shlukováním - a metriky vzdálenosti, protože všechny tři metody stojí na tom, jak měříš podobnost.

Algoritmus k-means

Rozdělovací (partiční) metoda. Shluk je reprezentován těžištěm svých objektů.

1. Zadání počtu shluků k a množiny všech objektů.
2. Náhodný výběr k výchozích středů shluků.
3. Přiřazení každého objektu k nejbližšímu středu.
4. Přepočítání středů shluků.
5. Skok na krok 3, dokud se nic nemění.

flowchart TD
    A["zvol k náhodných středů"] --> B[přiřaď každý bod k nejbližšímu středu]
    B --> C[přepočítej středy jako průměr přiřazených bodů]
    C --> D{změnilo se přiřazení?}
    D -->|ano| B
    D -->|ne| E[hotovo]

Podívej se na ten cyklus. Je to lokální prohledávání, které o tom neví. Krok 3 a krok 4 každý zvlášť snižují vnitroshlukovou variabilitu, takže algoritmus jde vždycky z kopce a nikdy se nevrátí. Odtud plynou všechny jeho vlastnosti i všechny problémy.

Vlastnosti a čtyři místa, kde to nefunguje

Iterativní, směřuje k lokálnímu minimu vnitroshlukové variability. Ne ke globálnímu. Nikdy nedostaneš záruku, že lepší rozdělení neexistuje.

Silně závislý na počáteční volbě středů. Dva běhy s jiným náhodným startem dají jiný výsledek. Řeší se to inicializací k-means++, která středy nevybírá rovnoměrně náhodně, ale rozprostře je co nejdál od sebe. Ve scikit-learn je to výchozí nastavení a nemá smysl ho měnit.

Předpokládá sférické tvary shluků a podobnou velikost. Tohle je nejpodstatnější omezení. K-means dělí prostor podle vzdálenosti k těžišti, takže hranice mezi shluky je vždycky nadrovina. Protáhlý shluk ve tvaru banánu rozřeže napůl a půlky přiřadí sousedům. Dva soustředné kruhy nerozliší vůbec.

Citlivý na odlehlé hodnoty. Jeden bod daleko od všech ostatních posune těžiště celého shluku. Průměr je z definice citlivý na extrémy a k-means je na průměru postavený.

Jak zvolit k

Nemáš to jak zjistit, jen odhadnout. V praxi se používá:

Loketová metoda. Spusť k-means pro k = 1, 2, 3, ... a vykresli vnitroshlukovou variabilitu. Klesá vždycky, ale v místě „správného" k je zlom. Metoda je subjektivní a u nevýrazných dat žádný loket nevidíš.

Silueta. Pro každý bod se spočítá, o kolik je blíž ke svému shluku než k nejbližšímu cizímu. Průměr přes všechny body dává jedno číslo, které se dá maximalizovat.

Doménová znalost. Nejlepší způsob. Když víš, že máš segmentovat zákazníky do čtyř marketingových kategorií, k = 4 je odpověď a hledat loket je zbytečné.

Hierarchické metody

Postupné vytváření stromové struktury shluků. Dvě varianty, které jdou proti sobě:

Aglomerativní (bottom-up). Každý objekt je na začátku samostatný shluk a postupně se spojují ty nejpodobnější. Používá se prakticky vždycky.

Divizivní (top-down). Všechny objekty jsou v jednom shluku a postupně se dělí. V praxi vzácné, protože první dělení je vlastně vyřešení celé úlohy.

Výpočet odlišnosti dvou shluků má několik variant a není to detail - určuje tvar výsledných shluků:

Single link umí najít banán, který k-means rozseká. Zaplatíš za to chaining effectem - řetízek bodů mezi dvěma hustými oblastmi je slepí v jeden shluk.

Hlavní výhoda hierarchických metod: nemusíš zadat k předem. Výsledkem je dendrogram a počet shluků si vybereš až podle něj tím, kde ho přeřízneš. Hlavní nevýhoda: složitost je nejméně O(n²) v paměti i čase, takže se to hodí na tisíce bodů, ne na miliony.

DBSCAN

Algoritmus založený na hustotě dat. Řeší přesně ty tři věci, na kterých k-means selhává:

• nevyžaduje předem zadaný počet shluků,
• identifikuje shluky libovolného tvaru,
• automaticky detekuje šum.

Klíčové parametry jsou dva:

• ε - maximální poloměr okolí bodu,
• MinPts - minimální počet bodů v okolí ε.

Podle nich se každý bod zařadí do jednoho ze tří typů:

Shluk pak vznikne tak, že se spojí jádrové body, které se navzájem dosáhnou, a připojí se k nim jejich hraniční body. Tvar shluku je daný tvarem té husté oblasti, ne vzdáleností od nějakého středu - odtud plyne, proč DBSCAN najde banán, spirálu i dva soustředné kruhy.

Šum je plnohodnotný výstup, ne chyba. K-means musí přiřadit každý bod, i ten, který nikam nepatří. DBSCAN ho označí a nechá být. U detekce anomálií je to přesně to, co chceš - hledáš právě ty šumové body.

Kde DBSCAN přestává platit: má problém se shluky různé hustoty. Jedno ε platí pro všechny, takže když je jeden shluk hustý a druhý řídký, buď ten řídký prohlásíš za šum, nebo ten hustý slepíš se sousedy. Řeší to varianta OPTICS. Druhý problém je volba ε - pomáhá vykreslit vzdálenost ke k-tému nejbližšímu sousedu pro všechny body a hledat zlom.

Kterou metodu kdy

Doporučení: začni k-means, protože je rychlý, a podívej se na výsledek. Když ti shluky vypadají rozseknuté nebo když jeden pohltil všechno ostatní, zkus DBSCAN. Hierarchické metody používej hlavně na pochopení dat, ne na produkční nasazení.

Co je před shlukováním potřeba udělat

Normalizuj příznaky. Tohle je nejčastější chyba vůbec. Když má jeden příznak rozsah 0-1 a druhý 0-100 000, vzdálenost je určena výhradně tím druhým a první se neuplatní. Viz normalizace intervalových proměnných.

Zvol metriku podle dat. Euklidovská vzdálenost pro fyzikální veličiny, kosinová podobnost pro texty, kde nezáleží na délce dokumentu. Viz metriky vzdálenosti.

Sniž dimenzi, pokud je vysoká. Ve vysoké dimenzi jsou si všechny body zhruba stejně vzdálené a shlukování ztrácí smysl. Před shlukováním se proto často pouští PCA.

Co se na tom nejčastěji rozbije

Co si odnést

Shlukování nemá správnou odpověď. Nemáš označení, takže se výsledek nedá otestovat, jen posoudit.

K-means najde přesně tolik shluků, kolik zadáš. I když tam nejsou.

K-means předpokládá kulaté shluky podobné velikosti. Na banány a spirály nepoužívej.

Hierarchické metody nepotřebují k předem, ale škálují jen do tisíců bodů.

DBSCAN najde libovolný tvar a označí šum, ale nezvládne různou hustotu.

Normalizace není volitelná. Bez ní vzdálenost měří jen ten největší příznak.

Kam dál

• Metriky a vyhodnocení - jak se počítá vzdálenost a jak se výsledek posuzuje
• Kohonenovy mapy - shlukování neuronovou sítí, se zachováním topologie
• Klasifikace a rozpoznávání - druhá strana, kde označení máš
• Nástroje pro UI - KMeans a DBSCAN ve scikit-learn