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:22] – [Bayesianské rozhodování] mistrjirka
+++ statnice:bakalar:b4b33rpz [2025/06/07 11:45] (current) – [Příklad s TikZ] mistrjirka
@@ Line 267: / Line 267: @@
 Logistická regrese je základním nástrojem pro klasifikaci, který lze rozšířit pomocí **softmaxu** na více tříd. Funkce sigmoidy a softmaxu zajistí interpretaci výstupů jako pravděpodobnosti, což je klíčové pro mnoho aplikací v ML.
-==== Support Vector Machine ====
+===== Support Vector Machine =====
-**Klasifikátor typu Support Vector Machine (SVM) je metoda pro binární klasifikaci, která hledá optimální rozhodovací hranici maximalizující margin mezi třídami. Pro neseparabilní data zavádí slack proměnné nebo využívá kernel trik pro transformaci do vyšší dimenze.**
+**Klasifikátor hledající optimální hranici mezi třídami s maximální mezí. Používá se pro binární klasifikaci, regresi a detekci odlehlých hodnot. Efektivní i ve vysokodimenzionálních prostorech.**
-=== Formulace úlohy učení ===
+=== Příklad a účel ===
-Pro **lineárně separabilní data** řešíme optimalizační problém: $$\min \frac{1}{2} \|w\|^2 \quad \text{za podmínky} \quad y_i(w \cdot x_i + b) \geq 1$$ kde ''%%w%%'' je normálový vektor, ''%%b%%'' posun a ''%%y_i ∈ {-1,1}%%'' třídní štítky . Geometricky jde o maximalizaci marginu $m^* = \frac{2}{\|w\|}$ mezi rovnoběžnými hyperrovinami $w \cdot x + b = \pm 1$.
+  * **Příklad:** Rozhodnutí, zda e-mail je spam (třída +1) či nikoliv (třída -1) na základě slovních příznaků.\\
+  * **Účel:** Najít hyperrovinu $\mathbf{w}^T\mathbf{x} + b = 0$ s maximální vzdáleností od nejbližších bodů (support vectors), což zvyšuje generalizaci.
+=== Hard Margin vs. Soft Margin ===
+  - <WRAP>
+**Hard Margin:**
+    * Předpokládá lineární separabilitu dat.\\
+    * Primární úloha:\\
+$$
+\min_{\mathbf{w},b} \frac{1}{2} \|\mathbf{w}\|^2 \quad \text{za podmínek} \quad y_i(\mathbf{w}^T\mathbf{x}_i + b) \geq 1 \quad \forall i
+$$
+    * **Problém:** Citlivý na odlehlé hodnoty a šum.
 <tikzjax>
 \usepackage{amsmath}
 \usepackage{pgfplots}
 \usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta}
 \begin{document}
 \begin{tikzpicture}
   \begin{axis}[
-    axis equal image,
+ axis equal image,
-    axis lines=center,
+ axis lines=center,
-    xmin=-0.5, xmax=9,
+ xmin=-0.5, xmax=9,
-    ymin=-0.5, ymax=7,
+ ymin=-0.5, ymax=7,
-    xtick=\empty, ytick=\empty,
+ xtick=\empty, ytick=\empty,
-    no markers
+ no markers
   ]
-    % Bias and weight vectors
+ % Bias and weight vectors
-    \addplot[dashed,->]
+ \addplot[dashed,->]
-      coordinates {(0,0) (11/5,22/5)}
+   coordinates {(0,0) (11/5,22/5)}
-      node[midway,left=5pt]{$b$};
+   node[midway,left=5pt]{$b$};
-    \addplot[thick,->]
+ \addplot[thick,->]
-      coordinates {(0,0) (0.4472,0.8944)}
+   coordinates {(0,0) (0.4472,0.8944)}
-      node[below right]{$\hat{\mathbf{w}}$};
+   node[below right]{$\hat{\mathbf{w}}$};
-    % Margin width arrow
+ % Margin width arrow
-    \addplot[dashed,<->]
+ \addplot[dashed,<->]
-      coordinates {(6.6,1.2) (7.4,2.8)}
+   coordinates {(6.6,1.2) (7.4,2.8)}
-      node[right=10pt,above]{$\tfrac{2}{\|\mathbf{w}\|}$};
+   node[right=10pt,above]{$\tfrac{2}{\|\mathbf{w}\|}$};
-    % Hyperplanes D₋, D, D₊
+ % Hyperplanes D₋, D, D₊
-    \addplot[black,thin,domain=1:7]
+ \addplot[black,thin,domain=1:7]
-      {(9 - x)/2}
+   {(9 - x)/2}
-      node[pos=0.05,sloped,above]{\tiny $D_{-}$};
+   node[pos=0.05,sloped,above]{\tiny $D_{-}$};
-    \addplot[black,thick,domain=(7/5):(37/5)]
+ \addplot[black,thick,domain=(7/5):(37/5)]
-      {(11 - x)/2}
+   {(11 - x)/2}
-      node[pos=0.025,sloped,above]{\tiny $D$};
+   node[pos=0.025,sloped,above]{\tiny $D$};
-    \addplot[black,thin,domain=(9/5):(39/5)]
+ \addplot[black,thin,domain=(9/5):(39/5)]
-      {(13 - x)/2}
+   {(13 - x)/2}
-      node[pos=0.05,sloped,above]{\tiny $D_{+}$};
+   node[pos=0.05,sloped,above]{\tiny $D_{+}$};
-    % Data points (class a vs. class b) + support vectors (v)
+ % Data points (class a vs. class b) + support vectors (v)
-    \addplot[
+ \addplot[
-      scatter,only marks,
+   scatter,only marks,
-      point meta=explicit symbolic,
+   point meta=explicit symbolic,
-      scatter/classes={
+   scatter/classes={
-        a={mark=*},
+     a={mark=*},
-        b={mark=*,draw=black,fill=white},
+     b={mark=*,draw=black,fill=white},
-        v={mark=o,draw=darkgray,thick,scale=2.25}
+     v={mark=o,draw=darkgray,thick,scale=2.25}
-      }
+   }
-    ] table[meta=label] {
+ ] table[meta=label] {
-      x    y   label
+   x    y   label
     6   a
     4   a
 .5  5   a
 .5  5   a
     3.5 a
     5.5 a
     3   b
 .5  0.5 b
     2.5 b
     3   b
     1   b
     2   b
     3   v
     2   v
     4   v
-    };
+ };
   \end{axis}
 \end{tikzpicture}
+\end{document}
+</tikzjax>
+</WRAP>
+  - <WRAP>
+**Soft Margin:**
+    * Povoluje chyby klasifikace pomocí relaxačních proměnných $\xi_i$.\\
+    * Primární úloha:\\
+$$
+\min_{\mathbf{w},b,\xi} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i \quad \text{za podmínek} \quad y_i(\mathbf{w}^T\mathbf{x}_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0
+$$
+    * **Parametr $C$:** Řídí kompromis mezi šířkou okraje a chybami (nízké $C$ = větší margin, vyšší $C$ = méně chyb).
+<tikzjax>
+\usepackage{amsmath}
+\usepackage{pgfplots}
+\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta}
+\begin{document}
+\begin{tikzpicture}
+  \begin{axis}[
+ axis equal image,
+ axis lines=center,
+ xmin=-0.5, xmax=8,
+ ymin=-0.5, ymax=6,
+ xtick=\empty, ytick=\empty,
+ no markers
+  ]
+ % Hyperplanes: thin, decision (thick), thin
+ \addplot[black,thin,domain=1:7]   {(9 - x)/2};
+ \addplot[black,thick,domain=(7/5):(37/5)] {(11 - x)/2};
+ \addplot[black,thin,domain=(9/5):(39/5)] {(13 - x)/2};
+ % Slack vectors xi_i, xi_j
+ \addplot[dashed,->]
+   coordinates {(3.8,3.6) (4.45,4.9)}
+   node[above left]{$\xi_{i}$};
+ \addplot[dashed,->]
+   coordinates {(4.4,3.3) (3.55,1.6)}
+   node[above left]{$\xi_{j}$};
+ % Data points (class a vs. class b)
+ \addplot[
+   scatter,only marks,
+   point meta=explicit symbolic,
+   scatter/classes={
+     a={mark=*},
+     b={mark=*,draw=black,fill=white}
+   }
+ ] table[meta=label] {
+   x    y   label
+    6   a
+    4   a
+.5  5   a
+.5  5   a
+    3.5 a
+    5.5 a
+    3   b
+.5  0.5 b
+    2.5 b
+    3   b
+    1   b
+    2   b
+    3   b
+    2   b
+    4   a
+.5  5   b
+.5  1.5 a
+ };
+  \end{axis}
+\end{tikzpicture}
 \end{document}
 </tikzjax>
-=== Kernel SVM ===
+</WRAP>
+=== Kernel Trick ===
-Pro nelineární rozhodovací hranice používáme **kernel funkce** $K(x_i,x_j) = \phi(x_i) \cdot \phi(x_j)$, které implicitně mapují data do vyšší dimenze bez výpočetní náročnosti . Běžné jádra: - Lineární: $K(x_i,x_j) = x_i \cdot x_j$ - Polynomiální: $K(x_i,x_j) = (x_i \cdot x_j + c)^d$ - RBF: $K(x_i,x_j) = \exp(-\gamma\|x_i - x_j\|^2)$
-=== Vlastnosti ===
-**Výhody**: - Efektivní v vysokých dimenzích díky kernel triku - Robustnost díky maximalizaci marginu - Přesnost závislá pouze na support vektorech
+  * **Princip:** Mapuje data do vyšší dimenze pomocí jádrové funkce $K(\mathbf{x}_i, \mathbf{x}_j)$, aby se nelineárně separabilní data stala lineárně separabilními.\\
-**Nevýhody**: - Výpočetně náročné pro velké datasety - Citlivost na volbu kernelu a parametrů (C, γ) - Omezená interpretovatelnost výsledků
+  * **Příklad:** Gaussovo jádro (RBF) $K(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2)$.\\
-=== Použití ===
+  * **Výhoda:** Vyhýbá se explicitnímu výpočtu transformace (úspora výpočetního času).\\
-SVM se využívá pro: detekci spamu, klasifikaci textu, rozpoznávání obrazu a bioinformatiku, kde je klíčová schopnost pracovat s komplexními datovými strukturami pomocí kernelů.
+  * **Rovnice:** Rozhodovací funkce se stává $f(\mathbf{x}) = \sum_{i} \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b$.
+=== Vlastnosti, výhody a nevýhody ===
+^**Vlastnost**                  ^**Výhody**                                  ^**Nevýhody**                                      ^
+|**Přesnost**                   |Vysoká díky maximalizaci okraje.            |Citlivost na volbu hyperparametrů ($C$, $\gamma$).|
+|**Efektivita**                 |Rychlé předpovědi (pouze support vectors).  |Pomalé učení pro velké datasety.                  |
+|**Kernely**                    |Univerzálnost (lineární, polynomiální, RBF).|Nutnost křížové validace pro výběr jádra.         |
+|**Nelinearita**                |Zpracuje složité nelineární hranice.        |Interpretovatelnost modelu klesá.                 |
+|**Odolnost proti přetrénování**|Dobrá pro vysokodimenzionální data.         |Vyžaduje normalizaci vstupů.                      |
 ===== Adaboost =====
 **Adaboost, popis algoritmu, jeho interpretace jako minimalizace horního odhadu empirického rizika. Vlastnosti (výhody a nevýhody).**
+**Adaboost (Adaptive Boosting) je algoritmus ensemble learningu, který kombinuje slabé klasifikátory do silného klasifikátoru. Minimalizuje horní odhad empirického rizika a iterativně upravuje váhy chybně klasifikovaných vzorků.**
+==== Popis algoritmu ====
+  - **Inicializace vah**: Každému trénovacímu vzorku $(x_i, y_i)$ přiřadíme počáteční váhu $w_i^{(1)} = \frac{1}{m}$\\
+  - **Iterace** pro $t = 1$ až $T$:
+    - Natrénuj slabý klasifikátor $h_t(x)$ s minimální váženou chybou $\epsilon_t = \sum_{i=1}^m w_i^{(t)} \mathbf{1}_{[h_t(x_i) \neq y_i]}$\\
+    - Vypočti koeficient $\alpha_t = \frac{1}{2} \ln \left( \frac{1 - \epsilon_t}{\epsilon_t} \right)$\\
+    - Aktualizuj váhy: $w_i^{(t+1)} = \frac{w_i^{(t)} \exp(-\alpha_t y_i h_t(x_i))}{Z_t}$ kde $Z_t$ je normalizační faktor\\
+  - **Výsledný klasifikátor**: $H(x) = \text{sign} \left( \sum_{t=1}^T \alpha_t h_t(x) \right)$ [5]
+==== Minimalizace horního odhadu ====
+Empirické riziko je horní odhad chyby:\\
+$$ \mathcal{E}(H) \leq \prod_{t=1}^T Z_t \quad \text{kde} \quad Z_t = 2\sqrt{\epsilon_t(1-\epsilon_t)} $$\\
+Algoritmus v každé iteraci volí $h_t$ a $\alpha_t$ minimalizující $Z_t$, čímž exponenciálně snižuje chybu. [5]
+==== Vlastnosti ====
+**Výhody**:\\
+- Jednoduchá implementace\\
+- Odolnost proti přetrénování\\
+- Univerzálnost (kombinuje libovolné klasifikátory)
+**Nevýhody**:\\
+- Citlivý na šum a odlehlé hodnoty\\
+- Vyžaduje pečlivé nastavení parametrů\\
+- Problémy s nevyváženými třídami
+==== Příklad ====
+**Binární klasifikace s rozhodovacími stromy**:\\
+- **Data**: $\{(x_1=1, y_1=1), (x_2=2, y_2=-1), (x_3=3, y_3=1)\}$\\
+- **Iterace 1**: $h_1(x)$ chybuje u $x_2$ → $\epsilon_1=0.33$, $\alpha_1=0.55$\\
+- **Iterace 2**: $h_2(x)$ opravuje chybu u $x_2$ s vyšší vahou\\
+- **Výsledek**: $H(x) = 0.55h_1(x) + 0.8h_2(x)$
+<tikzjax>
+\usepackage{amsmath}
+\usepackage{pgfplots}
+\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta}
+\begin{document}
+\begin{tikzpicture}[scale=0.8]
+\draw[->] (0,0) -- (4,0) node[right] {$x$};
+\draw[->] (0,0) -- (0,3) node[above] {$y$};
+\draw[blue] (0.5,2.5) -- (1.5,0.5) node[midway,left] {$h_1$};
+\draw[red] (2.5,2.5) -- (3.5,0.5) node[midway,right] {$h_2$};
+\draw[thick] (0.5,2.7) .. controls (2,1.8) .. (3.5,0.3) node[right] {$H(x)$};
+\fill (1,2.5) circle (2pt) node[above] {+};
+\fill (2,0.5) circle (2pt) node[below] {-};
+\fill (3,2.5) circle (2pt) node[above] {+};
+\end{tikzpicture}
+\end{document}
+</tikzjax>
+==== Aplikace ====
+  * Rozpoznávání obličejů\\
+  * Detekce spamu\\
+  * Medicínská diagnostika\\
+//Princip zesilování slabých klasifikátorů z něj činí efektivní nástroj pro různé klasifikační úlohy.//
 ===== Neuronové sítě =====
 **Neuronové sítě s dopředným šířením. Struktura. Učení pomocí metody zpětného šíření. Vlastnosti (výhody a nevýhody).**
+**Neuronové sítě s dopředným šířením jsou vícevrstvé architektury inspirované biologickými neurony, které transformují vstupy na výstupy pomocí vážených spojení a nelineárních aktivačních funkcí. Učí se metodou zpětného šíření chyby.**
+==== Struktura ====
+  * Skládá se z vrstev: **vstupní** (přijímá data), **skryté** (provádí výpočty) a **výstupní** (poskytuje výsledek).
+  * Každý neuron počítá vážený součet vstupů plus bias: $z = \sum w_i x_i + b$, následovaný aktivační funkcí: $a = g(z)$.
+  * Typické nelineární funkce: sigmoida, tanh, ReLU.
+==== Učení metodou zpětného šíření ====
+  - **Dopředné šíření**: Výpočet výstupů vrstev postupně od vstupu.
+  - **Výpočet chyby**: Porovnání výstupu s cílem pomocí loss funkce (např. MSE).
+  - **Zpětné šíření**:
+    * Gradienty chyby se šíří od výstupu ke vstupu pomocí řetězového pravidla.
+    * Aktualizace vah: $w \leftarrow w - \alpha \frac{\partial L}{\partial w}$, kde $\alpha$ je learning rate.
+==== Vlastnosti ====
+  * **Výhody**: Schopnost aproximovat libovolné spojité funkce (univerzální aproximátor), automatická extrakce příznaků.
+  * **Nevýhody**: Pomalé trénování, riziko přetrénování, citlivost na inicializaci vah.
+==== Konvoluce (příklad) ====
+Operace aplikuje filtr (jádro) na vstupní matici pro extrakci lokálních vzorů. Příklad pro vstup $X$ a jádro $K$: $$
+X = \begin{pmatrix}
+& 2 & 3 \\
+& 5 & 6 \\
+& 8 & 9
+\end{pmatrix}, \quad
+K = \begin{pmatrix}
+& -1 \\
+& 0
+\end{pmatrix}
+$$ Výstup pro pozici (1,1): $$
+(1 \cdot 0) + (2 \cdot -1) + (4 \cdot 1) + (5 \cdot 0) = -2 + 4 = 2
+$$
+==== Pooling a MaxPooling (příklad ====
+Snižuje prostorové rozměry, zachovává dominantní rysy. **MaxPooling** vybírá maximální hodnotu v okně. Příklad pro okno 2×2: $$
+\text{Vstup: } \begin{pmatrix}
+& 8 & 2 \\
+& 1 & 4 \\
+& 7 & 9
+\end{pmatrix} \quad
+\text{Výstup: } \begin{pmatrix}
+\max(5,8,3,1) & \max(2,4) \\
+\max(6,7) & \max(9)
+\end{pmatrix} = \begin{pmatrix}
+& 4 \\
+& 9
+\end{pmatrix}
+$$
+==== Použití Softmax ====
+Převede výstupní vektor na pravděpodobnostní distribuci: $$
+\text{softmax}(z_i) = \frac{e^{z_i}}{\sum_{j=1}^K e^{z_j}}
+$$ Používá se ve **výstupní vrstvě** pro klasifikační úlohy (např. rozpoznání digitů v MNIST).
+==== Nevýhody lineární aktivační funkce ====
+Pokud by všechny vrstvy používaly **pouze lineární funkce** ($g(z) = z$): - Síť by se degradovala na jediný perceptron (lineární kombinátor). - Ztratila by schopnost modelovat nelineární vztahy, např. XOR problém. - Klesla by výrazně expresivita modelu.
 ===== Klasifikace metodou nejbližšího souseda =====
 **Klasifikace metodou nejbližšího souseda. Výhody a nevýhody. Řadu nevýhod triviální implementace lze odstranit, jak?**
+**Metoda k-NN (k-Nearest Neighbors) je algoritmus učení s učitelem, který klasifikuje neznámý vzorek na základě většinové třídy jeho //k// nejbližších sousedů v trénovacích datech. Nevýhody triviální implementace řeší např. k-D stromy.**
+==== Příklad ====
+Uvažujme 2D datovou sadu s třídami △ (modrá) a ● (červená):
+<tikzjax>
+\usepackage{amsmath}
+\usepackage{pgfplots}
+\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta}
+\begin{document}
+\begin{tikzpicture}[scale=0.6]
+\draw[gray!30] (0,0) grid (6,5);
+\draw[->] (0,0) -- (6.2,0);
+\draw[->] (0,0) -- (0,5.2);
+\foreach \point/\col in {(1,1)/blue, (1,3)/blue, (2,2)/blue, (4,4)/red, (5,3)/red, (5,5)/red}
+    \fill[\col] \point circle (4pt);
+\node[blue] at (1,1) {$\triangle$};
+\node[blue] at (1,3) {$\triangle$};
+\node[blue] at (2,2) {$\triangle$};
+\node[red] at (4,4) {$\bullet$};
+\node[red] at (5,3) {$\bullet$};
+\node[red] at (5,5) {$\bullet$};
+\fill[green] (3,3) circle (4pt); % Testovací bod
+\node at (3,3.3) {?};
+\end{tikzpicture}
+\end{document}
+</tikzjax>
+Pro testovací bod (3,3) a //k//=3:\\
+. Vzdálenosti k △: √5≈2.24, √1=1, √2≈1.41\\
+. Vzdálenosti k ●: √2≈1.41, √4=2, √5≈2.24\\
+Nejbližší sousedé: △ (1.0), ● (1.41), △ (1.41) → většina △ → klasifikace jako △.
+==== Využití ====
+  * Rozpoznávání obrazců (OCR, detekce objektů)
+  * Doporučovací systémy (“uživatelé s podobným profilem”)
+  * Lékařská diagnostika (klasifikace vzorků)
+==== Výhody ====
+  - **Jednoduchá implementace** bez potřeby tréninkového modelu\\
+  - **Adaptabilita** na nová data (stačí přidat vzorky)\\
+  - **Vhodná pro vysoký počet tříd** (i stovky tříd) [1]\\
+  - **Neparametrická** – nedělá předpoklady o distribuci dat
+==== Nevýhody ====
+  - **Výpočetní náročnost** – O(//n//) pro každou klasifikaci (prohledávání všech vzorků)\\
+  - **Citlivost na šum a irelevantní atributy**\\
+  - **Problém vysoké dimenzionality** (curse of dimensionality)\\
+  - **Nevhodná pro nevyvážená data** (dominance větších tříd)
+==== Řešení nevýhod ====
+  * <WRAP>
+**k-D stromy** (k-dimensional trees):\\
+Binární stromy pro hierarchické rozdělení prostoru. Příklad pro 2D:
+<code>
+Root: (x=3.5)
+├─ Vlevo: body s x<3.5 (rozděl na y=2.5)
+└─ Vpravo: body s x≥3.5 (rozděl na y=4)
+</code>
+Složitost klesne na O(log //n//) při nízkých dimenzích [1].\\
+</WRAP>
+  * **Vážení atributů** (např. ReliefF algoritmus)\\
+  * **Normalizace dat** (potlačení vlivu škálování)\\
+  * **Výběr optimálního //k//** (křížová validací)
+==== Omezení k-D stromů ====
+  * Efektivita klesá pro dimenze >20 (“curse of dimensionality”)\\
+  * Konstrukce stromu O(//n// log //n//), ale jednorázová investice [1]
 ===== 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: • a • b4b01num

Differences

Search

Navigation

Print/export

Tools

QR Code