# 3. Аудиторні задачі з розв'язаннями Ці задачі розбирають **в аудиторії «руками»**. Вони показують ту саму агломеративну кластеризацію, яку потім автоматизує домашня програма ([4task.md](4task.md)). Теорія й формули — у [методичних вказівках](2method.md). **Спільні дані задач 1–3.** П'ять одновимірних об'єктів (наприклад, значення однієї ознаки в п'яти клієнтів): $$ X = \{\, 0,\ 1,\ 7,\ 12,\ 15 \,\}. $$ Відстань — модуль різниці $d(x,y) = |x - y|$. Матриця попарних відстаней: | | **0** | **1** | **7** | **12** | **15** | |---|:--:|:--:|:--:|:--:|:--:| | **0** | 0 | 1 | 7 | 12 | 15 | | **1** | 1 | 0 | 6 | 11 | 14 | | **7** | 7 | 6 | 0 | 5 | 8 | | **12** | 12 | 11 | 5 | 0 | 3 | | **15** | 15 | 14 | 8 | 3 | 0 | --- ## Задача 1. Агломеративна кластеризація одиночним зв'язком **Дано** точки $X = \{0, 1, 7, 12, 15\}$. **Виконати** агломеративну кластеризацію **одиночним** зв'язком ($D = \min$): виписати послідовність злиттів із висотами, побудувати дендрограму й указати розбиття на два кластери. **Розв'язання.** На кожному кроці шукаємо найменшу відстань між кластерами й зливаємо цю пару; відстань одиночного зв'язку — **мінімум** попарних відстаней. - **Злиття 1.** Найменша відстань у матриці — $d(0,1)=1$. Зливаємо $\{0\}$ і $\{1\}$ у $\{0,1\}$ на **висоті 1**. - **Злиття 2.** Відстані від $\{0,1\}$: до $\{7\}=\min(7,6)=6$; до $\{12\}=11$; до $\{15\}=14$. Серед усіх відстаней найменша — $d(12,15)=3$. Зливаємо $\{12,15\}$ на **висоті 3**. - **Злиття 3.** Відстані від $\{7\}$: до $\{0,1\}=\min(7,6)=6$; до $\{12,15\}=\min(5,8)=5$. Найменша в системі — $5$, тож $\{7\}$ зливається з $\{12,15\}$ у $\{7,12,15\}$ на **висоті 5**. - **Злиття 4.** Лишилися $\{0,1\}$ і $\{7,12,15\}$; одиночний зв'язок — $\min(7,6,12,11,15,14)=6$ (пара $1$–$7$). Зливаємо на **висоті 6** — корінь. | Крок | Об'єднані кластери | Висота $h$ | |:--:|---|:--:| | 1 | $\{0\} + \{1\}$ | 1 | | 2 | $\{12\} + \{15\}$ | 3 | | 3 | $\{7\} + \{12,15\}$ | 5 | | 4 | $\{0,1\} + \{7,12,15\}$ | 6 | Дендрограма (висота зростає зліва направо): ```text 0 ──┐ ├─(1)──────────────┐ 1 ──┘ │ ├─(6) ← корінь 7 ────────┐ │ ├─(5)────────┘ 12 ──┐ │ ├─(3)─┘ 15 ──┘ ``` ![Дендрограма одиночного зв'язку для точок 0, 1, 7, 12, 15 з висотами злиттів 1, 3, 5, 6 та розрізом на два кластери](img/lab10_dendro_single.png) **Відповідь.** Порядок злиттів — з висотами $1, 3, 5, 6$. Розріз на **два кластери** (перед фінальним злиттям) дає $$ \boxed{\{0, 1\} \ \mid\ \{7, 12, 15\}}. $$ Точка $7$ приєдналася **праворуч**: її найближчий сусід — $12$ (відстань $5$) — ближчий, ніж найближча точка зліва ($1$, відстань $6$). --- ## Задача 2. Те саме повним зв'язком (контраст) **Дано** ті самі точки. **Виконати** кластеризацію **повним** зв'язком ($D = \max$) і порівняти з Задачею 1. **Розв'язання.** Тепер відстань між кластерами — **максимум** попарних відстаней. Перші два злиття збігаються з Задачею 1 (для окремих точок $\min=\max$). - **Злиття 1.** $d(0,1)=1$ $\Rightarrow$ $\{0,1\}$, висота **1**. - **Злиття 2.** $d(12,15)=3$ — найменша $\Rightarrow$ $\{12,15\}$, висота **3**. - **Злиття 3.** Відстані від $\{7\}$ (повний зв'язок): до $\{0,1\}=\max(7,6)=7$; до $\{12,15\}=\max(5,8)=8$. Найменша в системі — $7$ (а не $8$!), тож $\{7\}$ тепер зливається з $\{0,1\}$ у $\{0,1,7\}$ на **висоті 7**. - **Злиття 4.** Лишилися $\{0,1,7\}$ і $\{12,15\}$; повний зв'язок — $\max(12,11,5,15,14,8)=15$ (пара $0$–$15$). Зливаємо на **висоті 15**. | Крок | Об'єднані кластери | Висота $h$ | |:--:|---|:--:| | 1 | $\{0\} + \{1\}$ | 1 | | 2 | $\{12\} + \{15\}$ | 3 | | 3 | $\{7\} + \{0,1\}$ | 7 | | 4 | $\{12,15\} + \{0,1,7\}$ | 15 | ```text 0 ──┐ ├─(1)──┐ 1 ──┘ │ ├─(7)────────┐ 7 ─────────┘ │ ├─(15) ← корінь 12 ──┐ │ ├─(3)───────────────┘ 15 ──┘ ``` ![Дендрограма повного зв'язку для точок 0, 1, 7, 12, 15 з висотами злиттів 1, 3, 7, 15 та розрізом на два кластери](img/lab10_dendro_complete.png) **Відповідь.** Розріз на **два кластери** дає $$ \boxed{\{0, 1, 7\} \ \mid\ \{12, 15\}}, $$ що **відрізняється** від результату Задачі 1. Причина — місткова точка $7$: за **найближчим** сусідом (одиночний зв'язок) вона тяжіє до правої групи ($d=5$ до $12$), а за **найдальшим** (повний зв'язок) — до лівої ($d=7$ до $0$ проти $8$ до $15$). Вибір метрики зв'язку **змінює** кластеризацію — це головний висновок задачі. --- ## Задача 3 (опційно). Силует і індекс Данна простого розбиття **Дано** розбиття з Задачі 1: $\{0,1\}\mid\{7,12,15\}$. **Обчислити** середній силует та індекс Данна; порівняти з розбиттям Задачі 2. **Розв'язання.** Силует точки $s(i)=\dfrac{b(i)-a(i)}{\max(a(i),b(i))}$, де $a(i)$ — середня відстань до «своїх», $b(i)$ — до найближчого чужого кластера. | Точка | $a(i)$ (свій) | $b(i)$ (чужий) | $s(i)$ | |:--:|---|---|:--:| | 0 | $d(0,1)=1$ | $\tfrac{7+12+15}{3}=11.33$ | $\tfrac{11.33-1}{11.33}\approx 0.912$ | | 1 | $d(1,0)=1$ | $\tfrac{6+11+14}{3}=10.33$ | $\approx 0.903$ | | 7 | $\tfrac{5+8}{2}=6.5$ | $\tfrac{7+6}{2}=6.5$ | $0$ | | 12 | $\tfrac{5+3}{2}=4$ | $\tfrac{12+11}{2}=11.5$ | $\tfrac{11.5-4}{11.5}\approx 0.652$ | | 15 | $\tfrac{8+3}{2}=5.5$ | $\tfrac{15+14}{2}=14.5$ | $\approx 0.621$ | Середній силует: $\bar{s} = \tfrac{0.912+0.903+0+0.652+0.621}{5} \approx \mathbf{0.618}$. **Індекс Данна.** Найменша міжкластерна відстань — $d(1,7)=6$; найбільший внутрішньокластерний діаметр — у $\{7,12,15\}$ це $d(7,15)=8$. Тож $\mathrm{Dunn} = 6/8 = \mathbf{0.75}$. **Порівняння з Задачею 2.** Для розбиття $\{0,1,7\}\mid\{12,15\}$ аналогічний підрахунок дає $\bar{s}\approx 0.572$ і $\mathrm{Dunn}=5/7\approx 0.714$ (міжкластерна $d(7,12)=5$, діаметр $d(0,7)=7$). Обидві міри трохи вищі для розбиття Задачі 1, тобто **одиночне** розбиття тут якісніше. Місткова точка $7$ в обох випадках має $s(7)=0$ — вона чесно «сидить» на межі й перетягує якість униз. > **Зв'язок із домашнім завданням.** Саме ці кроки — побудувати матрицю відстаней, > злити найближчу пару, оновити відстані, повторити, а тоді оцінити розбиття > силуетом чи Данном — виконуватиме ваша програма для довільного файлу CSV > ([4task.md](4task.md)). Задачі 1–2 — зручний **тест**: подайте ці п'ять чисел на > вхід і переконайтесь, що одиночний зв'язок повертає $\{0,1\}\mid\{7,12,15\}$, а > повний — $\{0,1,7\}\mid\{12,15\}$.