The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

--- 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, 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, \ldots, \mathbf{x}_n \}$ v $d$-rozměrném prostoru do $k$ shluků ($k$ předem zadané). Optimalizuje se ztrátová funkce:\\
+$$
+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:** Náhodný výběr $k$ počátečních centroidů.\\
+  - **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í:** Opakování kroku 2–3, dokud se přiřazení bodů nemění nebo nedojde k maximálnímu počtu iterací.
+==== Příklad ====
+<tikzjax>
+\usepackage{amsmath}
+\usepackage{pgfplots}
+\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta}
+\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}
+</tikzjax>
+//Výsledek po konvergenci: 3 shluky s centroidy $\mu_1, \mu_2, \mu_3$.//
+==== 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/p}
+  $$\\
+- **Kosinová podobnost:** Pro textová/data s vysokou dimenzí.
+==== K-means++ ====
+Vylepšení inicializace centroidů:\\
+. První centroid náhodně vybrán z dat.\\
+. Každý další centroid vybrán s pravděpodobností úměrnou $\|\mathbf{x} - \mu_{\text{nejblížší}}\|^2$.\\
+**Výhody:** Snižuje riziko špatné konvergence, často dosáhne globálního optima s menším počtem iterací.
+==== Aplikace ====
+  * Segmentace zákazníků, analýza genomických dat, komprese obrazu (redukce barev), detekce anomálií.

Trace: • b4b38nvs • b4b01dma

Differences

Search

Navigation

Print/export

Tools

QR Code