Shlukovani.md

# 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](Klasifikace-a-rozpoznavani).** 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í](Klasifikace-a-rozpoznavani) - rozdíl mezi klasifikací, rozpoznáváním a shlukováním - a [metriky vzdálenosti](Metriky-a-vyhodnoceni#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í. ```mermaidflowchart 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í](Lokalni-prohledavani), 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ů: | Varianta | Vzdálenost shluků | Vyrábí ||---|---|---|| Minimální (single link) | nejbližší dvojice bodů | protáhlé, řetězící se shluky || Maximální (complete link) | nejvzdálenější dvojice | kompaktní, kulaté shluky || Střední / průměrná | průměr přes všechny dvojice | kompromis, nejpoužívanější | **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ů: | Typ bodu | Podmínka ||---|---|| **Core Point** (jádrový) | v okolí `ε` má alespoň `MinPts` bodů || **Border Point** (hraniční) | méně než `MinPts`, ale je v dosahu `ε` od jádrového bodu || **Noise Point** (šum) | ani jádrový, ani hraniční | 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 | Situace | Metoda ||---|---|| Znáš `k`, shluky jsou kompaktní, dat je hodně | **k-means** || Neznáš `k` a chceš vidět strukturu | **hierarchické** (dendrogram) || Shluky mají divný tvar nebo jsou v datech odlehlé body | **DBSCAN** || Hledáš anomálie | **DBSCAN** a čti šumové body || Máš miliony bodů | **k-means** nebo jeho minibatch varianta | **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](Metriky-a-vyhodnoceni#základní-typy-dat). **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](Metriky-a-vyhodnoceni#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 | Příznak | Kde je problém ||---|---|| Jeden shluk obsahuje skoro všechno | chybí normalizace, jeden příznak převálcoval vzdálenost || Každý běh dá jiný výsledek | k-means s náhodnou inicializací - zapni k-means++ a víc restartů || Protáhlý shluk je rozseknutý napůl | k-means předpokládá sférické tvary, jdi na DBSCAN || DBSCAN označí za šum skoro všechno | příliš malé `ε` nebo příliš velké `MinPts` || DBSCAN vrátí jeden obří shluk | příliš velké `ε` || Dendrogram je jeden dlouhý řetěz | single link a chaining effect - zkus complete nebo average || Loket na křivce není vidět | v datech nejsou zřetelné shluky, což je taky výsledek | ## 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í](Metriky-a-vyhodnoceni)** - jak se počítá vzdálenost a jak se výsledek posuzuje- **[Kohonenovy mapy](Kohonenovy-mapy)** - shlukování neuronovou sítí, se zachováním topologie- **[Klasifikace a rozpoznávání](Klasifikace-a-rozpoznavani)** - druhá strana, kde označení máš- **[Nástroje pro UI](Nastroje-pro-UI)** - `KMeans` a `DBSCAN` ve scikit-learn