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

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

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$ — їхні центроїди.

Вибір метрики впливає на результат. Одиночний зв’язок «тягне» кластери через випадкові містки (ефект ланцюжка) і добре вловлює витягнуті форми; повний зв’язок і 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) дає одне розбиття на наперед задане $k$ і тяжіє до кулястих кластерів. Щоб порівняти ієрархічну кластеризацію з $k$-середніми чесно, беруть однакове $k$ (розрізавши дендрограму на $k$ кластерів) і зіставляють розбиття за тією самою мірою — силуетом або індексом Данна. Вища міра означає якісніше розбиття.

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

Нехай маємо п’ять одновимірних об’єктів

$$X = \{\, 1,\ 3,\ 4,\ 11,\ 15 \,\}.$$

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

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

• Найменша відстань $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  ────────┐
           ├─(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$ і ту саму міру якості.

Laboratory/Laboratory10/2method.md · 10.9 KB · updated 2026-08-04 23:32