Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| statnice:bakalar:b4b33rpz [2025/06/07 11:44] – [Neuronové sítě] mistrjirka | statnice:bakalar:b4b33rpz [2025/06/07 11:45] (current) – [Příklad s TikZ] mistrjirka | ||
|---|---|---|---|
| Line 670: | Line 670: | ||
| ===== Shlukování metodou k-means ===== | ===== Shlukování metodou k-means ===== | ||
| - | **Shlukování metodou k-means, formulace úlohy a popis algoritmu. Vlastnosti algoritmu. Zobecnění - použití pro jiné ztrátové funkce než L2.** | ||
| + | **Shlukování metodou k-means, formulace úlohy a popis algoritmu. Vlastnosti algoritmu. Zobecnění – použití pro jiné ztrátové funkce než L2.** | ||
| + | |||
| + | ==== Formulace úlohy ==== | ||
| + | |||
| + | Cílem je rozdělit množinu $n$ datových bodů $\mathcal{D} = \{ \mathbf{x}_1, | ||
| + | $$ | ||
| + | J = \sum_{i=1}^k \sum_{\mathbf{x} \in C_i} \|\mathbf{x} - \boldsymbol{\mu}_i\|^2 | ||
| + | $$\\ | ||
| + | kde $C_i$ je $i$-tý shluk a $\boldsymbol{\mu}_i$ jeho centroid (průměr bodů ve shluku). | ||
| + | |||
| + | ==== Popis algoritmu ==== | ||
| + | |||
| + | - **Inicializace: | ||
| + | |||
| + | - **Přiřazení bodů:** Každý bod přiřazen k nejbližšímu centroidu (Eukleidovská vzdálenost): | ||
| + | $$ | ||
| + | C_i = \{ \mathbf{x} : \|\mathbf{x} - \boldsymbol{\mu}_i\|^2 \leq \|\mathbf{x} - \boldsymbol{\mu}_j\|^2 \, \forall j \} | ||
| + | $$\\ | ||
| + | |||
| + | - **Aktualizace centroidů: | ||
| + | $$ | ||
| + | \boldsymbol{\mu}_i = \frac{1}{|C_i|} \sum_{\mathbf{x} \in C_i} \mathbf{x} | ||
| + | $$\\ | ||
| + | |||
| + | - **Ukončení: | ||
| + | |||
| + | ==== Příklad ==== | ||
| + | |||
| + | < | ||
| + | \usepackage{amsmath} | ||
| + | \usepackage{pgfplots} | ||
| + | \usetikzlibrary{automata, | ||
| + | \begin{document} | ||
| + | |||
| + | \begin{tikzpicture} | ||
| + | % Data points | ||
| + | \filldraw[blue] (0.5,1.5) circle (2pt); | ||
| + | \filldraw[blue] (1,1) circle (2pt); | ||
| + | \filldraw[blue] (1.5,0.5) circle (2pt); | ||
| + | \filldraw[red] (3,2) circle (2pt); | ||
| + | \filldraw[red] (3.5,2.5) circle (2pt); | ||
| + | \filldraw[red] (4,3) circle (2pt); | ||
| + | \filldraw[green] (2,4) circle (2pt); | ||
| + | \filldraw[green] (2.5,4.5) circle (2pt); | ||
| + | \filldraw[green] (3,5) circle (2pt); | ||
| + | |||
| + | % Centroids (after convergence) | ||
| + | \filldraw[black] (1,1) circle (4pt) node[below] {$\mu_1$}; | ||
| + | \filldraw[black] (3.5,2.5) circle (4pt) node[below] {$\mu_2$}; | ||
| + | \filldraw[black] (2.5,4.5) circle (4pt) node[above] {$\mu_3$}; | ||
| + | \end{tikzpicture} | ||
| + | |||
| + | \end{document} | ||
| + | </ | ||
| + | //Výsledek po konvergenci: | ||
| + | |||
| + | ==== Vlastnosti algoritmu ==== | ||
| + | |||
| + | * **Rychlý a škálovatelný** pro velká data ($O(n \cdot k \cdot d)$ na iteraci).\\ | ||
| + | |||
| + | * **Citlivý na inicializaci** (špatná volba centroidů → suboptimální řešení).\\ | ||
| + | |||
| + | * **Předpokládá konvexní shluky** stejné velikosti (špatně zpracuje nestejnoměrná data).\\ | ||
| + | |||
| + | * **Lokální optimum:** Konverguje k nejbližšímu lokálnímu minimu $J$. | ||
| + | |||
| + | ==== Zobecnění pro jiné ztrátové funkce ==== | ||
| + | |||
| + | Místo Eukleidovské vzdálenosti ($\ell_2$) lze použít:\\ | ||
| + | - **Manhattanská vzdálenost ($\ell_1$): | ||
| + | $$ | ||
| + | J = \sum_{i=1}^k \sum_{\mathbf{x} \in C_i} \|\mathbf{x} - \boldsymbol{\mu}_i\|_1 | ||
| + | $$\\ | ||
| + | Centroid aktualizován jako **medián** shluku (odolnější vůči odlehlým hodnotám).\\ | ||
| + | - **Obecná Minkowského metrika ($\ell_p$): | ||
| + | $$ | ||
| + | \|\mathbf{x} - \boldsymbol{\mu}_i\|_p = \left( \sum_{j=1}^d |x_j - \mu_{ij}|^p \right)^{1/ | ||
| + | $$\\ | ||
| + | - **Kosinová podobnost: | ||
| + | |||
| + | ==== K-means++ ==== | ||
| + | |||
| + | Vylepšení inicializace centroidů: | ||
| + | 1. První centroid náhodně vybrán z dat.\\ | ||
| + | 2. Každý další centroid vybrán s pravděpodobností úměrnou $\|\mathbf{x} - \mu_{\text{nejblížší}}\|^2$.\\ | ||
| + | **Výhody: | ||
| + | |||
| + | ==== Aplikace ==== | ||
| + | |||
| + | * Segmentace zákazníků, | ||
