# 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í.

```mermaid
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í](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