# 3. Аудиторні задачі з розв'язаннями

Ці задачі розбирають **в аудиторії «руками»**. Вони показують ті самі обчислення,
які потім автоматизує домашня програма ([4task.md](4task.md)). Теорія й формули —
у [методичних вказівках](2method.md).

## Задача 1. Відстані та найближчий центроїд

**Дано** об'єкти $P(1,1)$ і $Q(4,5)$. **Знайти** манхеттенську, евклідову,
чебишову відстані та відстань Мінковського порядку $p = 3$. Далі: до якого з двох
центроїдів $\mu_1 = (1,2)$, $\mu_2 = (6,5)$ ближча точка $R(3,3)$?

**Розв'язання.** Покоординатні відхилення $P$ і $Q$: $|1-4| = 3$, $|1-5| = 4$.

$$ d_1 = 3 + 4 = 7, \qquad d_2 = \sqrt{3^2 + 4^2} = \sqrt{25} = 5, \qquad d_\infty = \max(3, 4) = 4, $$
$$ d_3 = (3^3 + 4^3)^{1/3} = (27 + 64)^{1/3} = 91^{1/3} \approx 4.498. $$

Для точки $R(3,3)$:

$$ d(R, \mu_1) = \sqrt{(3-1)^2 + (3-2)^2} = \sqrt{5} \approx 2.236, \qquad
d(R, \mu_2) = \sqrt{(3-6)^2 + (3-5)^2} = \sqrt{13} \approx 3.606. $$

Оскільки $2.236 < 3.606$, точку $R$ відносять до кластера з центром $\mu_1$.

**Відповідь:** $d_1 = 7$, $d_2 = 5$, $d_\infty = 4$, $d_3 \approx 4.498$;
$R \to$ кластер $\mu_1$.

## Задача 2. Повний прогін методу $k$-середніх

**Дано** $6$ точок на площині й $k = 2$:

$$ A(1,1),\ B(2,1),\ C(1,2),\quad D(5,4),\ E(6,5),\ F(5,5). $$

Початкові центроїди — перші дві точки: $\mu_1 = A(1,1)$, $\mu_2 = B(2,1)$.
**Виконати** дві повні ітерації, показати стабілізацію та обчислити фінальну SSE.

**Розв'язання.**

**Ітерація 1.** Евклідові відстані від кожної точки до центрів і віднесення до
найближчого:

| Точка | $d(\cdot, \mu_1{=}(1,1))$ | $d(\cdot, \mu_2{=}(2,1))$ | Кластер |
|:--:|:--:|:--:|:--:|
| $A(1,1)$ | $0.000$ | $1.000$ | $C_1$ |
| $B(2,1)$ | $1.000$ | $0.000$ | $C_2$ |
| $C(1,2)$ | $1.000$ | $1.414$ | $C_1$ |
| $D(5,4)$ | $5.000$ | $4.243$ | $C_2$ |
| $E(6,5)$ | $6.403$ | $5.657$ | $C_2$ |
| $F(5,5)$ | $5.657$ | $5.000$ | $C_2$ |

Розбиття: $C_1 = \{A, C\}$, $C_2 = \{B, D, E, F\}$. Перераховуємо центроїди як
покоординатні середні:

$$ \mu_1 = \left(\tfrac{1+1}{2}, \tfrac{1+2}{2}\right) = (1,\ 1.5), \qquad
\mu_2 = \left(\tfrac{2+5+6+5}{4}, \tfrac{1+4+5+5}{4}\right) = (4.5,\ 3.75). $$

Сума квадратів помилок після перерахунку: $\mathrm{SSE} = 20.25$.

**Ітерація 2.** З новими центрами $\mu_1 = (1,\ 1.5)$, $\mu_2 = (4.5,\ 3.75)$:

| Точка | $d(\cdot, \mu_1)$ | $d(\cdot, \mu_2)$ | Кластер |
|:--:|:--:|:--:|:--:|
| $A(1,1)$ | $0.500$ | $4.451$ | $C_1$ |
| $B(2,1)$ | $1.118$ | $3.717$ | $C_1$ |
| $C(1,2)$ | $0.500$ | $3.913$ | $C_1$ |
| $D(5,4)$ | $4.717$ | $0.559$ | $C_2$ |
| $E(6,5)$ | $6.103$ | $1.953$ | $C_2$ |
| $F(5,5)$ | $5.315$ | $1.346$ | $C_2$ |

Тепер точка $B$ **перейшла** до $C_1$: розбиття стало
$C_1 = \{A, B, C\}$, $C_2 = \{D, E, F\}$. Нові центроїди:

$$ \mu_1 = \left(\tfrac{1+2+1}{3}, \tfrac{1+1+2}{3}\right) = \left(\tfrac{4}{3}, \tfrac{4}{3}\right) \approx (1.333,\ 1.333), \quad
\mu_2 = \left(\tfrac{5+6+5}{3}, \tfrac{4+5+5}{3}\right) = \left(\tfrac{16}{3}, \tfrac{14}{3}\right) \approx (5.333,\ 4.667). $$

$\mathrm{SSE} = \tfrac{8}{3} \approx 2.667$.

**Ітерація 3 (перевірка стабілізації).** З цими центрами віднесення **не
змінюється** ($A, B, C \to C_1$; $D, E, F \to C_2$), тож центроїди лишаються тими
самими — **критерій збіжності виконано**. SSE монотонно спадала:

$$ \mathrm{SSE}: \quad 20.25 \ \to\ 2.667 \ \to\ 2.667 \ (\text{стабілізувалася}). $$

![Задача 2: дві ітерації k-середніх до збіжності — початкові центри, перше та друге віднесення з рухом центроїдів](img/lab9_iterations.png)

**Обчислення фінальної SSE «вручну».** Для контролю порахуємо
$\mathrm{SSE} = \sum_c \sum_{x \in C_c} \lVert x - \mu_c \rVert^2$ покроково.
Кластер $C_1 = \{A, B, C\}$ з центром $(\tfrac43, \tfrac43)$:

$$ \lVert A - \mu_1\rVert^2 = (\tfrac13)^2 + (\tfrac13)^2 = \tfrac{2}{9}, \quad
\lVert B - \mu_1\rVert^2 = (\tfrac23)^2 + (\tfrac13)^2 = \tfrac{5}{9}, \quad
\lVert C - \mu_1\rVert^2 = (\tfrac13)^2 + (\tfrac23)^2 = \tfrac{5}{9}, $$

разом $\tfrac{12}{9} = \tfrac{4}{3}$. Кластер $C_2 = \{D, E, F\}$ з центром
$(\tfrac{16}{3}, \tfrac{14}{3})$ дає симетрично $\tfrac{5}{9} + \tfrac{5}{9} + \tfrac{2}{9} = \tfrac{4}{3}$.
Отже

$$ \mathrm{SSE} = \tfrac{4}{3} + \tfrac{4}{3} = \tfrac{8}{3} \approx 2.667. $$

**Відповідь:** кластери $\{A, B, C\}$ та $\{D, E, F\}$ з центрами
$(\tfrac43, \tfrac43)$ і $(\tfrac{16}{3}, \tfrac{14}{3})$; фінальна
$\mathrm{SSE} = \tfrac{8}{3} \approx 2.667$.

![Задача 2: фінальні кластери {A,B,C} та {D,E,F} з центроїдами-хрестиками й підписом SSE=8/3≈2.667](img/lab9_clusters.png)

## Задача 3. Нечітка приналежність ($c$-середніх)

**Дано** центри кластерів $\mu_1 = (1,1)$, $\mu_2 = (6,5)$, об'єкт $x = (3,1)$ та
параметр нечіткості $m = 2$. **Знайти** ступені приналежності $u_1, u_2$ об'єкта
до кластерів і жорстке віднесення.

**Розв'язання.** Спершу відстані до центрів:

$$ d_1 = \sqrt{(3-1)^2 + (1-1)^2} = 2, \qquad d_2 = \sqrt{(3-6)^2 + (1-5)^2} = \sqrt{9+16} = 5. $$

При $m = 2$ показник $2/(m-1) = 2$, тож формула приналежності зводиться до
обернених квадратів відстаней:

$$ u_1 = \frac{1/d_1^2}{1/d_1^2 + 1/d_2^2} = \frac{1/4}{1/4 + 1/25} = \frac{0.25}{0.29} \approx 0.862, \qquad
u_2 = 1 - u_1 \approx 0.138. $$

Перевірка: $u_1 + u_2 = 1$. Об'єкт на $\approx 86\%$ належить першому кластеру й на
$\approx 14\%$ — другому. Жорстке віднесення — до кластера з **більшою**
приналежністю, тобто до $\mu_1$.

**Відповідь:** $u_1 \approx 0.862$, $u_2 \approx 0.138$; жорстко $x \to$
кластер $\mu_1$.

> **Зв'язок із домашнім завданням.** Кроки Задачі 2 — обрати центроїди, віднести
> точки за відстанню, перерахувати центри, повторювати до стабілізації й порахувати
> SSE — це рівно те, що виконуватиме ваша програма для довільного файлу CSV
> ([4task.md](4task.md)). Задача 2 — зручний **тест**: подайте ці шість точок на
> вхід і переконайтесь, що програма дає кластери $\{A,B,C\}$, $\{D,E,F\}$ та
> $\mathrm{SSE} = \tfrac{8}{3} \approx 2.667$.