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

Ці задачі розбирають в аудиторії «руками». Вони показують ті самі обчислення, які потім автоматизує домашня програма (4task.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. Евклідові відстані від кожної точки до центрів і віднесення до найближчого:

Розбиття: $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)$:

Тепер точка $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{стабілізувалася}).$$

Обчислення фінальної 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$.

Задача 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). Задача 2 — зручний тест: подайте ці шість точок на вхід і переконайтесь, що програма дає кластери $\{A,B,C\}$, $\{D,E,F\}$ та $\mathrm{SSE} = \tfrac{8}{3} \approx 2.667$.

Laboratory/Laboratory9/3classroom.md · 7.7 KB · updated 2026-08-05 09:27