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

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

Спільні дані задач 1–3. П’ять одновимірних об’єктів (наприклад, значення однієї ознаки в п’яти клієнтів):

$$X = \{\, 0,\ 1,\ 7,\ 12,\ 15 \,\}.$$

Відстань — модуль різниці $d(x,y) = |x - y|$. Матриця попарних відстаней:

Задача 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 — корінь.

Дендрограма (висота зростає зліва направо):

0  ──┐
     ├─(1)──────────────┐
1  ──┘                  │
                        ├─(6)   ← корінь
7  ────────┐            │
           ├─(5)────────┘
12 ──┐     │
     ├─(3)─┘
15 ──┘

Відповідь. Порядок злиттів — з висотами $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.

0  ──┐
     ├─(1)──┐
1  ──┘      │
            ├─(7)────────┐
7  ─────────┘            │
                         ├─(15)  ← корінь
12 ──┐                   │
     ├─(3)───────────────┘
15 ──┘

Відповідь. Розріз на два кластери дає

$$\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)$ — до найближчого чужого кластера.

Середній силует: $\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). Задачі 1–2 — зручний тест: подайте ці п’ять чисел на вхід і переконайтесь, що одиночний зв’язок повертає $\{0,1\}\mid\{7,12,15\}$, а повний — $\{0,1,7\}\mid\{12,15\}$.

Laboratory/Laboratory10/3classroom.md · 9.3 KB · updated 2026-08-05 09:44