# 2. Методичні вказівки

Цей розділ **самодостатній**: у ньому зібрано теорію ієрархічної (агломеративної)
кластеризації, потрібну для аудиторних задач ([3classroom.md](3classroom.md)) і
домашньої програми ([4task.md](4task.md)). Ширше ту саму теорію викладено в
[Лекції 10](../../Lectures/DA-L10.md).

## 2.1 Задача кластеризації та відстань

**Кластеризація** (категоризація) — поділ множини об'єктів на групи (**кластери**)
так, щоб об'єкти в одній групі були схожі, а в різних — несхожі. Міру несхожості
задають **відстанню**. Для одновимірних точок беруть модуль різниці
$d(x, y) = |x - y|$; для багатовимірних об'єктів $\mathbf{x} = (x_1, \dots, x_m)$ —
**евклідову** відстань

$$ d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{k=1}^{m} (x_k - y_k)^2}. $$

**Ієрархічна** кластеризація будує не одне розбиття, а **послідовність вкладених**
групувань — від «кожен об'єкт окремо» до «усі разом» — і подає її **дендрограмою**.

## 2.2 Агломеративний алгоритм («знизу догори»)

1. Кожен об'єкт — **окремий** кластер ($n$ кластерів).
2. Будуємо **матрицю відстаней** між усіма парами кластерів.
3. Знаходимо **найближчу** пару кластерів і **зливаємо** її.
4. Якщо лишився один кластер — кінець; інакше перераховуємо відстані до нового
   кластера й повертаємось до кроку 3.

Висота, на якій відбулося кожне злиття (відстань між злитими кластерами), формує
**дендрограму**.

## 2.3 Метрики зв'язку (linkage)

Відстань **між кластерами** (коли в них уже кілька точок) означують по-різному.
Нехай $C_i$, $C_j$ — кластери, $\mu_i$, $\mu_j$ — їхні центроїди.

| Метрика | Формула | Коротко |
|---|---|---|
| **Одиночний зв'язок** (single, найближчий сусід) | $\min\limits_{x\in C_i,\,y\in C_j} d(x,y)$ | найближчі точки; схильний до «ланцюжка» |
| **Повний зв'язок** (complete, найдальший сусід) | $\max\limits_{x\in C_i,\,y\in C_j} d(x,y)$ | найдальші точки; компактні кластери |
| **Середній** (average, груповий середній, UPGMA) | $\dfrac{1}{\lvert C_i\rvert\lvert C_j\rvert}\sum\limits_{x\in C_i}\sum\limits_{y\in C_j} d(x,y)$ | середнє з усіх попарних |
| **Центроїдний** (centroid) | $\lVert \mu_i - \mu_j \rVert$ | відстань між центроїдами |
| **Ward** | $\dfrac{\lvert C_i\rvert\lvert C_j\rvert}{\lvert C_i\rvert+\lvert C_j\rvert}\lVert \mu_i-\mu_j\rVert^2$ | мінімум приросту дисперсії |

**Вибір метрики впливає на результат.** Одиночний зв'язок «тягне» кластери через
випадкові містки (ефект ланцюжка) і добре вловлює витягнуті форми; повний зв'язок і
Ward дають компактніші, збалансованіші групи.

## 2.4 Дендрограма

**Дендрограма** — дерево злиттів. Висота з'єднання = відстань між кластерами під
час злиття. **Розріз** горизонтальною лінією на висоті $h$ дає конкретне розбиття:
що нижче ріжемо — то більше дрібних кластерів. Великий **стрибок** висоти між
сусідніми злиттями підказує природне місце розрізу.

## 2.5 Оцінка якості

Правильних міток немає, тож якість оцінюють **внутрішніми** мірами.

**Індекс Данна** — відношення мінімальної міжкластерної відстані до максимального
внутрішньокластерного діаметра:

$$ \mathrm{Dunn} = \frac{\min\ \text{міжкластерна відстань}}{\max\ \text{внутрішньокластерний діаметр}} \qquad (\text{більше} \Rightarrow \text{краще}). $$

**Силует** оцінює кожну точку: $a(i)$ — середня відстань до «своїх», $b(i)$ —
середня відстань до **найближчого чужого** кластера,

$$ s(i) = \frac{b(i) - a(i)}{\max\big(a(i), b(i)\big)} \in [-1, 1], $$

а силует розбиття — середнє $s(i)$. Значення біля $1$ — точка глибоко у своєму
кластері; біля $0$ — на межі; від'ємне — імовірно, віднесена не туди.

## 2.6 Порівняння з $k$-середніми

$k$-середніх ([Лекція 9](../../Lectures/DA-L09.md)) дає **одне** розбиття на
наперед задане $k$ і тяжіє до кулястих кластерів. Щоб **порівняти** ієрархічну
кластеризацію з $k$-середніми **чесно**, беруть **однакове** $k$ (розрізавши
дендрограму на $k$ кластерів) і зіставляють розбиття за **тією самою** мірою —
силуетом або індексом Данна. Вища міра означає якісніше розбиття.

## 2.7 Демонстраційний приклад (на інших даних, ніж у задачах)

Нехай маємо п'ять одновимірних об'єктів
$$ X = \{\, 1,\ 3,\ 4,\ 11,\ 15 \,\}. $$

Матриця відстаней $d(x,y)=|x-y|$:

| | **1** | **3** | **4** | **11** | **15** |
|---|:--:|:--:|:--:|:--:|:--:|
| **1** | 0 | 2 | 3 | 10 | 14 |
| **3** | 2 | 0 | 1 | 8 | 12 |
| **4** | 3 | 1 | 0 | 7 | 11 |
| **11** | 10 | 8 | 7 | 0 | 4 |
| **15** | 14 | 12 | 11 | 4 | 0 |

**(а) Одиночний зв'язок.**

- Найменша відстань $d(3,4)=1$ $\Rightarrow$ злиття $\{3,4\}$, висота **1**.
- Відстані від $\{3,4\}$: до $\{1\}=\min(2,3)=2$; до $\{11\}=\min(8,7)=7$; до
  $\{15\}=\min(12,11)=11$. Найменша в системі — $2$ $\Rightarrow$ $\{1\}+\{3,4\}=\{1,3,4\}$,
  висота **2**.
- Тепер $d(11,15)=4$ — найменша $\Rightarrow$ $\{11,15\}$, висота **4**.
- Останнє: $D_{\text{single}}(\{1,3,4\},\{11,15\})=\min(10,14,8,12,7,11)=7$ $\Rightarrow$
  корінь, висота **7**.

| Крок | Об'єднання | Висота |
|:--:|---|:--:|
| 1 | $\{3\}+\{4\}$ | 1 |
| 2 | $\{1\}+\{3,4\}$ | 2 |
| 3 | $\{11\}+\{15\}$ | 4 |
| 4 | $\{1,3,4\}+\{11,15\}$ | 7 |

```text
1  ────────┐
           ├─(2)──────┐
3  ──┐     │          │
     ├─(1)─┘          ├─(7)  ← корінь
4  ──┘                │
11 ──┐                │
     ├─(4)────────────┘
15 ──┘
```

Найбільший стрибок — між висотою $4$ і $7$: природний розріз дає **два кластери**
$\{1,3,4\}$ і $\{11,15\}$.

**(б) Повний зв'язок.** Перші кроки такі самі, але відстань $\{1\}$ до $\{3,4\}$
тепер $\max(2,3)=3$, а фінальне злиття — $\max(10,14,8,12,7,11)=14$. Порядок
злиттів і **розбиття на 2 кластери той самий** ($\{1,3,4\}\mid\{11,15\}$), лише
висоти інші: $1, 3, 4, 14$. На цих добре розділених даних метрика не змінила
результату (на відміну від аудиторних задач, де змінить).

**(в) Оцінка якості розбиття** $\{1,3,4\}\mid\{11,15\}$.

*Індекс Данна.* Найменша міжкластерна відстань — $d(4,11)=7$; найбільший діаметр —
у $\{11,15\}$ це $d(11,15)=4$ (діаметр $\{1,3,4\}$ дорівнює $3$). Отже
$\mathrm{Dunn}=7/4=1.75$ — понад $1$, тобто кластери розділені **краще**, ніж
щільні всередині: дуже добре розбиття.

*Силует.* Наприклад, для точки $1$: $a(1)=\tfrac{2+3}{2}=2.5$,
$b(1)=\tfrac{10+14}{2}=12$, тож $s(1)=\tfrac{12-2.5}{12}\approx 0.792$. Для
точки $11$: $a(11)=d(11,15)=4$, $b(11)=\tfrac{10+8+7}{3}=8.33$, тож
$s(11)=\tfrac{8.33-4}{8.33}\approx 0.52$. Усереднивши всі п'ять значень,
дістаємо силует розбиття $\bar{s}\approx 0.72$.

*Порівняння з $k$-середніми.* $k$-середніх із $k=2$ на цих точках дає **те саме**
розбиття $\{1,3,4\}\mid\{11,15\}$ (центроїди $\approx 2.67$ і $13$), тож і силует
той самий $\approx 0.72$. На добре розділених даних обидва методи узгоджуються;
різниця виявляється на складніших наборах — саме її ви й досліджуватимете у
домашньому завданні.

## 2.8 Робочий контрольний список

- Спершу **матриця відстаней**; на кожному кроці шукайте **найменший** елемент.
- Після злиття **замініть** рядки/стовпці двох кластерів **одним** — перерахованим
  за обраною метрикою (не користуйтеся старими відстанями).
- Фіксуйте **висоту** кожного злиття — це і є дендрограма.
- Для розбиття на $k$ кластерів **зупиніть** злиття, коли лишиться $k$ кластерів
  (рівнозначно розрізу дендрограми).
- Порівнюючи метрики чи методи, тримайте **однакове** $k$ і ту саму міру якості.