# Лекція 10. Ієрархічні методи кластеризації ## Огляд У [Лекції 9](DA-L09.md) ми розв'язали задачу **кластеризації** методом $k$-середніх: заздалегідь фіксували число кластерів $k$, розкидали центри й ітеративно «притягали» до них точки. Такий підхід простий і швидкий, але має дві слабкості: **число кластерів треба знати наперед**, а результат залежить від випадкового початкового розкидання центрів і від того, що кластери вважають приблизно **кулястими**. Ієрархічні методи знімають першу з цих проблем. Замість одного розбиття на $k$ груп вони будують **цілу послідовність вкладених розбиттів** — від «кожна точка окремо» до «усі точки разом» — і подають її наочним деревом. Дивлячись на це дерево, аналітик сам обирає, на скільки кластерів різати дані, вже **після** обчислень. У цій лекції ми розберемо два напрями: **агломеративний** (знизу догори — злиття) і **поділяючий** (згори донизу — DIANA), докладно вивчимо **метрики зв'язку** між кластерами (single, complete, average, центроїдний, Ward) і навчимося **оцінювати якість** кластеризації індексом Данна та силуетним коефіцієнтом. Наступна [Лекція 11](DA-L11.md) відкриє новий розділ — пошук асоціативних правил. > **Практичний бік.** Агломеративну кластеризацію одиночним і повним зв'язком ви > виконуватимете «руками», а потім реалізуєте алгоритм **програмою** й > порівняєте його з $k$-середніми у > [Лабораторній роботі 10](../Laboratory/Laboratory10/main.md). Наскрізний приклад лекції — п'ять одновимірних точок (наприклад, значення однієї ознаки в п'яти клієнтів): $$ X = \{\, 0,\ 1,\ 6,\ 10,\ 13 \,\}. $$ Одновимірність тут навмисна: відстань між точками — це просто модуль різниці $d(x, y) = |x - y|$, тож усю увагу можна зосередити на **логіці злиттів**, а не на арифметиці. Усі формули розділу дослівно переносяться на багатовимірні дані, де замість $|x-y|$ беруть евклідову відстань. --- ## 10.1 Мета ієрархічних методів > **Означення (ієрархічна кластеризація).** **Ієрархічна кластеризація** — > побудова **послідовності вкладених групувань** множини об'єктів: від найдрібнішого > розбиття (кожен об'єкт — окремий кластер) до найгрубшого (усі об'єкти в одному > кластері). Цю послідовність зображують **бінарним деревом**, у якому **листя** — > окремі точки, а **корінь** — кластер, що об'єднує всі точки. Ключове слово — **вкладене**. Розбиття називають вкладеним, якщо кожен кластер грубшого рівня є об'єднанням кількох кластерів дрібнішого рівня; кластери **ніколи не перетинаються частково** — вони або вкладені один в один, або неперетинні. > **Означення (вкладене розбиття).** Дві системи кластерів $\mathcal{P}$ і > $\mathcal{Q}$ утворюють **вкладену** пару, якщо кожен кластер із $\mathcal{Q}$ — > це об'єднання цілих кластерів із $\mathcal{P}$ (тобто $\mathcal{Q}$ грубша за > $\mathcal{P}$). Ієрархія — це ланцюг таких розбиттів > $\mathcal{P}_n \prec \mathcal{P}_{n-1} \prec \dots \prec \mathcal{P}_1$, де > $\mathcal{P}_n$ — $n$ окремих точок, а $\mathcal{P}_1$ — один спільний кластер. Порівняймо з $k$-середніми ([Лекція 9](DA-L09.md)): | Властивість | $k$-середніх | Ієрархічні методи | |---|---|---| | Число кластерів $k$ | задають **наперед** | обирають **після** побудови дерева | | Результат | одне розбиття на $k$ груп | **уся** родина вкладених розбиттів | | Форма кластерів | тяжіє до кулястих | залежить від метрики зв'язку | | Відтворюваність | залежить від старту | **детермінований** (за фіксованих правил) | | Складність | $O(nki)$ | зазвичай $O(n^2 \log n)$ або $O(n^3)$ | Плата за гнучкість — **обчислювальна вартість**: доводиться працювати з матрицею попарних відстаней розміру $n \times n$, тож для дуже великих $n$ ієрархічні методи застосовують до вибірки або підвибірки даних. --- ## 10.2 Дендрограма Результат ієрархічної кластеризації подають **дендрограмою**. > **Означення (дендрограма).** **Дендрограма** — деревоподібна діаграма, що > зображує послідовність злиттів (або поділів). Її листя — окремі об'єкти; кожна > **точка з'єднання** (вузол) відповідає об'єднанню двох кластерів, а **висота**, > на якій відбувається з'єднання, дорівнює **відстані між цими кластерами** в > момент злиття. Як **читати** дендрограму: - **Висота злиття** — це «ціна» об'єднання: чим вище відбулося з'єднання, тим **далі** були кластери один від одного. Об'єкти, що зливаються **низько**, схожі; ті, що з'єднуються лише **біля кореня**, — різні. - **Різати** дендрограму горизонтальною лінією на висоті $h$ — означає отримати конкретне розбиття: кожна вертикальна гілка, яку перетинає лінія, дає один кластер. Опустивши лінію нижче, дістанемо **більше** дрібніших кластерів; піднявши — **менше** й грубших. Так одна дендрограма містить **усі** розбиття одразу. - **Великий стрибок висоти** між сусідніми злиттями — природна підказка, де різати: він означає, що наступне об'єднання з'єднує вже далекі групи, тож зупинитися варто саме перед ним. Порядок листя вздовж осі не несе змісту (гілки можна повертати навколо вузла) — значення мають лише **висоти** з'єднань і **структура** вкладення. --- ## 10.3 Агломеративний алгоритм (знизу догори) **Агломеративний** підхід починає з найдрібнішого розбиття й **зливає** кластери, доки не лишиться один. Це найпоширеніший різновид ієрархічної кластеризації. > **Алгоритм (агломеративна кластеризація).** > 1. Кожен елемент виносимо в **окремий** кластер (маємо $n$ кластерів). > 2. Будуємо **матрицю відстаней** між усіма парами кластерів. > 3. Знаходимо **найближчу** пару кластерів і **зливаємо** її в один. > 4. Якщо лишився **один** кластер — кінець; інакше повертаємось до кроку 2 > (перерахувавши відстані до нового кластера). ```text Agglomerative(точки X, метрика зв'язку L): clusters <- [{x} для кожного x у X] # крок 1: n листків D <- матриця попарних відстаней між кластерами # крок 2 поки |clusters| > 1: (A, B) <- пара кластерів з найменшим D[A,B] # крок 3 h <- D[A,B] # висота злиття -> дендрограма C <- A ∪ B; прибрати A, B; додати C оновити D: відстані від C до решти за метрикою L # крок 4 повернути дерево злиттів (дендрограму) ``` Уся змістовна відмінність між варіантами алгоритму захована в кроці 4 — **як саме** перераховувати відстань від новоутвореного кластера до решти. Цей вибір задає **метрику зв'язку** (§10.4). Почнемо з найпростішої — **одиночного зв'язку** (найближчого сусіда): відстань між кластерами дорівнює відстані між їхніми **найближчими** точками. ### Приклад 10.1 (агломеративна кластеризація одиночним зв'язком) Візьмемо наскрізні дані $X = \{0, 1, 6, 10, 13\}$. Матриця попарних відстаней $d(x,y) = |x-y|$ (крок 2): | | **0** | **1** | **6** | **10** | **13** | |---|:--:|:--:|:--:|:--:|:--:| | **0** | 0 | 1 | 6 | 10 | 13 | | **1** | 1 | 0 | 5 | 9 | 12 | | **6** | 6 | 5 | 0 | 4 | 7 | | **10** | 10 | 9 | 4 | 0 | 3 | | **13** | 13 | 12 | 7 | 3 | 0 | ![Теплова карта матриці попарних відстаней між точками 0, 1, 6, 10, 13](img/l10_distance_matrix.png) **Крок за кроком** (щоразу шукаємо найменший позатабличний елемент і зливаємо): - **Злиття 1.** Найменша відстань — $d(0,1) = 1$. Зливаємо $\{0\}$ і $\{1\}$ у $\{0,1\}$ на **висоті 1**. - **Злиття 2.** Тепер найменша — $d(10,13) = 3$. Зливаємо у $\{10,13\}$ на **висоті 3**. - **Злиття 3.** Відстані від $\{6\}$: до $\{0,1\}$ — $\min(6,5) = 5$; до $\{10,13\}$ — $\min(4,7) = 4$. Найменша в системі — саме $4$, тож $\{6\}$ зливається з $\{10,13\}$ у $\{6,10,13\}$ на **висоті 4**. - **Злиття 4.** Лишилися $\{0,1\}$ і $\{6,10,13\}$; відстань одиночного зв'язку — $\min(6,5,10,9,13,12) = 5$ (пара $1$–$6$). Зливаємо на **висоті 5** — це корінь. Зведемо злиття в таблицю (це, по суті, і є дендрограма): | Крок | Об'єднані кластери | Висота $h$ | |:--:|---|:--:| | 1 | $\{0\} + \{1\}$ | 1 | | 2 | $\{10\} + \{13\}$ | 3 | | 3 | $\{6\} + \{10,13\}$ | 4 | | 4 | $\{0,1\} + \{6,10,13\}$ | 5 | ![Кроки агломеративного злиття одиночним зв'язком: п'ять окремих точок, три кластери після перших злиттів і фінальний розріз на два кластери {0,1} та {6,10,13}](img/l10_agglomerative.png) Схематична дендрограма (висота зростає зліва направо): ```text 0 ──┐ ├─(1)──────────────┐ 1 ──┘ │ ├─(5) ← корінь 6 ────────┐ │ ├─(4)────────┘ 10 ──┐ │ ├─(3)─┘ 13 ──┘ ``` ![Дендрограма одиночного зв'язку для точок 0, 1, 6, 10, 13 з висотами злиттів 1, 3, 4, 5 та зеленою лінією розрізу на два кластери](img/l10_dendrogram.png) Найбільший стрибок висоти — між злиттями на $4$ і фінальним на $5$ — невеликий, але структурно найприродніший розріз дає **два кластери**: $\{0,1\}$ і $\{6,10,13\}$. Зверніть увагу: «місткова» точка $6$ потрапила до **правої** групи, хоча за координатою вона майже посередині. Чому — стане зрозуміло у §10.4. > **Типова помилка (забути оновити відстані).** Після злиття $A$ і $B$ рядки й > стовпці $A$, $B$ у матриці **замінюють одним** рядком/стовпцем нового кластера > $C = A \cup B$, перерахованим за обраною метрикою. Часта помилка — продовжувати > користуватися старими відстанями до вже неіснуючих кластерів; тоді дерево > виходить неправильним. --- ## 10.4 Метрики зв'язку (linkage) **Метрика зв'язку** (linkage) визначає, що таке «відстань між кластерами», коли в кожному з них уже може бути кілька точок. Нехай $C_i$, $C_j$ — кластери, $|C_i|$, $|C_j|$ — їхні розміри, $\mu_i$, $\mu_j$ — **центроїди** (середні точки). > **Одиночний зв'язок (single linkage, метод найближчого сусіда).** > $$ D_{\text{single}}(C_i, C_j) = \min_{x \in C_i,\ y \in C_j} d(x, y). $$ > Відстань між кластерами — відстань між двома **найближчими** їхніми точками. > **Повний зв'язок (complete linkage, метод найдальшого сусіда).** > $$ D_{\text{complete}}(C_i, C_j) = \max_{x \in C_i,\ y \in C_j} d(x, y). $$ > Відстань — між двома **найдальшими** точками (діаметр об'єднаної пари). > **Середній зв'язок (average linkage, метод групового середнього, UPGMA).** > $$ D_{\text{average}}(C_i, C_j) = \frac{1}{|C_i|\,|C_j|} \sum_{x \in C_i} \sum_{y \in C_j} d(x, y). $$ > Відстань — **середнє** з усіх попарних відстаней між точками різних кластерів. ![Метрики зв'язку між двома кластерами: одиночний як мінімальна відстань, повний як максимальна, середній як середнє всіх попарних відстаней](img/l10_linkage.png) > **Центроїдний метод (centroid linkage, UPGMC).** > $$ D_{\text{centroid}}(C_i, C_j) = d(\mu_i, \mu_j) = \lVert \mu_i - \mu_j \rVert. $$ > Відстань між **центроїдами** кластерів. Найпростіший геометричний варіант; тяжіє > до кластерів **кулястої** форми. > **Метод Варда (Ward, мінімум приросту дисперсії).** На кожному кроці зливають ту > пару, що дає **найменший приріст** внутрішньокластерної суми квадратів > $\mathrm{ESS} = \sum_{C} \sum_{x \in C} \lVert x - \mu_C \rVert^2$. Для пари > $(C_i, C_j)$ приріст обчислюють за формулою > $$ \Delta\mathrm{ESS}(C_i, C_j) = \frac{|C_i|\,|C_j|}{|C_i| + |C_j|}\, \lVert \mu_i - \mu_j \rVert^2. $$ > Ward будує **компактні кластери близького розміру** й найкраще працює для > приблизно кулястих груп. > **Зауваження (єдина формула оновлення).** Усі перелічені метрики — окремі > випадки **рекурентної формули Ленса — Вільямса**, що виражає відстань від > новоутвореного кластера $C_i \cup C_j$ до кластера $C_k$ через попередні відстані > $D(C_i, C_k)$, $D(C_j, C_k)$, $D(C_i, C_j)$ з коефіцієнтами, що залежать від > методу. Тому крок 4 алгоритму можна реалізувати **однаково** для всіх метрик, > лише підставляючи потрібні коефіцієнти, — не перебираючи щоразу всі пари точок. ### Приклад 10.2 (одиночний проти повного зв'язку) Застосуємо до тих самих даних $X = \{0, 1, 6, 10, 13\}$ **повний зв'язок** і порівняймо з одиночним із Прикладу 10.1. Перші два злиття однакові (для окремих точок $\min$ і $\max$ збігаються): $\{0,1\}$ на висоті $1$, $\{10,13\}$ на висоті $3$. Далі — відмінність. Для точки $\{6\}$ (крок 3) обчислимо обидві метрики до кожної групи: | Метрика | до $\{0,1\}$ | до $\{10,13\}$ | Куди приєднається $6$ | |---|:--:|:--:|:--:| | Одиночний ($\min$) | $\min(6,5)=5$ | $\min(4,7)=\mathbf{4}$ | праворуч, до $\{10,13\}$ | | Повний ($\max$) | $\max(6,5)=\mathbf{6}$ | $\max(4,7)=7$ | ліворуч, до $\{0,1\}$ | | Середній | $\tfrac{6+5}{2}=5.5$ | $\tfrac{4+7}{2}=5.5$ | однаково (нічия) | | Центроїдний | $|6-0.5|=5.5$ | $|6-11.5|=5.5$ | однаково (нічия) | Ось де народжується різниця результатів. **Одиночний** зв'язок бачить, що в правій групі є точка ($10$), ближча до $6$, ніж будь-яка точка зліва, — і тягне $6$ **праворуч**. **Повний** зв'язок дивиться на найдальшу точку: праворуч це $13$ (відстань $7$), зліва — $0$ (відстань $6$), тож він відносить $6$ **ліворуч**. Середній і центроїдний методи бачать $6$ **рівновіддаленою** ($5.5$ до обох), тобто $6$ — справжня «місткова» точка. Повні злиття: | Крок | Одиночний зв'язок | $h$ | Повний зв'язок | $h$ | |:--:|---|:--:|---|:--:| | 3 | $\{6\} + \{10,13\}$ | 4 | $\{6\} + \{0,1\}$ | 6 | | 4 | $\{0,1\} + \{6,10,13\}$ | 5 | $\{10,13\} + \{0,1,6\}$ | 13 | Розріз на **два кластери** дає **різні** розбиття: $$ \text{одиночний:}\ \{0,1\}\mid\{6,10,13\}, \qquad \text{повний:}\ \{0,1,6\}\mid\{10,13\}. $$ ![Порівняння дендрограм одиночного та повного зв'язку для точок 0, 1, 6, 10, 13: місткова точка 6 приєднується до різних груп](img/l10_single_vs_complete.png) > **Типова помилка (single-linkage «ланцюжок»).** Одиночний зв'язок схильний до > **ефекту ланцюжка** (chaining): він радо приєднує точку до кластера через > одного-єдиного близького сусіда, тож може «протягнути» ланцюжок точок і злити > дві насправді окремі групи через випадковий місток. **Повний** зв'язок і **Ward**, > навпаки, дають компактніші, збалансованіші кластери, але чутливіші до викидів. > Універсально «правильної» метрики немає — вибір залежить від даних і мети. --- ## 10.5 Поділяючий алгоритм DIANA (згори донизу) **Поділяючий** (divisive) підхід рухається у зворотному напрямі: усі точки спершу в одному кластері, який послідовно **розщеплюють**. Класичний алгоритм — **DIANA** (*DIvisive ANAlysis*). > **Алгоритм (DIANA).** > 1. Усі точки — в **одному** кластері. > 2. Обираємо кластер із **найбільшим діаметром** (максимальною попарною відстанню) > серед тих, що містять принаймні $2$ елементи. > 3. Знаходимо в ньому **найвіддаленішу** точку — з найбільшою **середньою** > відстанню до решти — і виносимо її в нову «відколоту» групу (splinter). > 4. Перерозподіляємо решту: точку переносимо у відколоту групу, якщо вона > **ближча** (у середньому) до неї, ніж до залишку старого кластера, тобто якщо > $$ D(i) = \overline{d}(i,\ \text{старий}) - \overline{d}(i,\ \text{відколотий}) > 0. $$ > Повторюємо, доки є точки з $D(i) > 0$ (щоразу переносячи ту, де $D(i)$ > найбільше). > 5. Якщо лишилися кластери з $\ge 2$ точок — повертаємось до кроку 2; інакше — > кінець. ### Приклад 10.3 (DIANA на наскрізних даних) Розщепимо $X = \{0, 1, 6, 10, 13\}$. Діаметр — $d(0,13) = 13$, тож ділимо весь кластер. **Середні** відстані кожної точки до решти: $$ \overline{d}(0)=7.5,\quad \overline{d}(1)=6.75,\quad \overline{d}(6)=5.5,\quad \overline{d}(10)=6.5,\quad \overline{d}(13)=8.75. $$ Максимум у точки $13$ ($8.75$) — вона стає зерном відколотої групи: $A = \{13\}$, залишок $B = \{0,1,6,10\}$. **Перерозподіл, раунд 1** ($D(i) = \overline{d}(i, B\setminus\{i\}) - \overline{d}(i, A)$): - $D(0) = \tfrac{1+6+10}{3} - 13 = 5.67 - 13 = -7.33$ — лишається; - $D(1) = \tfrac{1+5+9}{3} - 12 = 5 - 12 = -7$ — лишається; - $D(6) = \tfrac{6+5+4}{3} - 7 = 5 - 7 = -2$ — лишається; - $D(10) = \tfrac{10+9+4}{3} - 3 = 7.67 - 3 = +4.67$ — **переносимо** $10$ у $A$. Тепер $A = \{10, 13\}$, $B = \{0, 1, 6\}$. **Раунд 2:** - $D(0) = \tfrac{1+6}{2} - \tfrac{10+13}{2} = 3.5 - 11.5 = -8$; - $D(1) = \tfrac{1+5}{2} - \tfrac{9+12}{2} = 3 - 10.5 = -7.5$; - $D(6) = \tfrac{6+5}{2} - \tfrac{4+7}{2} = 5.5 - 5.5 = 0$. Жодного $D(i) > 0$ — зупиняємось. Перший поділ: $$ \{0, 1, 6\} \ \mid\ \{10, 13\}. $$ ![Поділ DIANA згори донизу: відколювання найвіддаленішої точки 13 як зерна групи та перший поділ на кластери {0,1,6} і {10,13}](img/l10_diana.png) Цікаво, що DIANA віднесла місткову точку $6$ **ліворуч** — так само, як **повний** зв'язок (§10.4), а не як одиночний. Це не випадковість: DIANA спирається на **середні** відстані до цілих груп, тому поводиться ближче до «компактних» метрик. Гранична точка $6$ ($D(6)=0$) за домовленістю лишається у старій групі (переносять лише при строгому $D(i) > 0$). > **Зауваження (вартість поділу).** Наївний перебір усіх способів розділити кластер > на дві частини коштує експоненційно ($2^{m-1}$ варіантів для $m$ точок). Саме тому > DIANA не перебирає всі поділи, а вирощує відколоту групу **жадібно** (кроки 3–4). > Через це поділяючі методи рідше застосовують, ніж агломеративні, хоча згори вони > «бачать» глобальну структуру даних раніше. --- ## 10.6 Оцінка якості кластеризації Кластеризація — задача **без учителя**: правильних міток немає, тож якість оцінюють **внутрішніми** мірами, що винагороджують **щільні** (компактні) і **добре розділені** кластери. Розглянемо дві класичні. ### Індекс Данна > **Означення (індекс Данна).** Для розбиття на кластери > $$ \mathrm{Dunn} = \frac{\min\ \text{міжкластерна відстань}}{\max\ \text{внутрішньокластерний діаметр}}, $$ > де чисельник — найменша відстань між точками **різних** кластерів, а знаменник — > найбільший діаметр (максимальна попарна відстань усередині кластера). **Що > більший** індекс, то краще: кластери далі один від одного й водночас щільніші. **Приклад 10.4.** Оцінимо два розбиття наскрізних даних (§10.4) за Данном. *Одиночний зв'язок,* $\{0,1\}\mid\{6,10,13\}$: найменша міжкластерна відстань — $d(1,6)=5$; найбільший діаметр — усередині $\{6,10,13\}$ це $d(6,13)=7$. Тож $\mathrm{Dunn} = 5/7 \approx 0.714$. *Повний зв'язок,* $\{0,1,6\}\mid\{10,13\}$: найменша міжкластерна — $d(6,10)=4$; найбільший діаметр — $d(0,6)=6$. Тож $\mathrm{Dunn} = 4/6 \approx 0.667$. За індексом Данна **одиночне** розбиття тут дещо краще ($0.714 > 0.667$). ### Силуетний коефіцієнт Силует оцінює **кожну точку** окремо, а тоді усереднює. > **Означення (силует точки).** Для точки $i$ нехай $a(i)$ — **середня** відстань > до інших точок **свого** кластера, а $b(i)$ — найменша (серед чужих кластерів) > середня відстань до точок **найближчого сусіднього** кластера. Силует точки — > $$ s(i) = \frac{b(i) - a(i)}{\max\big(a(i),\, b(i)\big)} \in [-1, 1]. $$ > **Силует розбиття** — середнє $s(i)$ по всіх точках. Тлумачення: $s(i) \approx 1$ — точка глибоко у «своєму» кластері; $s(i) \approx 0$ — на межі двох кластерів; $s(i) < 0$ — імовірно, віднесена **не туди**. ![Силует точки: середня внутрішньокластерна відстань a до свого кластера проти найближчої міжкластерної відстані b до сусіднього кластера](img/l10_silhouette.png) **Приклад 10.5.** Обчислимо силует для одиночного розбиття $\{0,1\}\mid\{6,10,13\}$. Для точки $0$: $a(0) = d(0,1) = 1$; $b(0) = \tfrac{6+10+13}{3} = 9.67$; отже $s(0) = \tfrac{9.67 - 1}{9.67} \approx 0.897$. Для точки $10$: $a(10) = \tfrac{d(10,6)+d(10,13)}{2} = \tfrac{4+3}{2} = 3.5$; $b(10) = \tfrac{10+9}{2} = 9.5$; отже $s(10) = \tfrac{9.5 - 3.5}{9.5} \approx 0.632$. Для місткової точки $6$: $a(6) = \tfrac{4+7}{2} = 5.5$, $b(6) = \tfrac{6+5}{2} = 5.5$, тож $s(6) = 0$ — вона рівно на межі. Усереднивши всі п'ять значень, дістаємо силует розбиття $\bar{s} \approx 0.60$. Для повного розбиття $\{0,1,6\}\mid\{10,13\}$ аналогічний підрахунок дає $\bar{s} \approx 0.55$. Обидві міри — і Данн, і силует — тут віддають перевагу **одиночному** розбиттю; але точка $6$ в обох випадках лишається «граничною» ($s(6)=0$), що чесно відображає її проміжне положення. > **Типова помилка (порівнювати різні $k$).** Силует і Данн залежать від **числа** > кластерів. Не можна робити висновок «метод A кращий за метод B», порівнюючи їхні > коефіцієнти на **різному** $k$: спершу зафіксуйте $k$, а вже тоді порівнюйте. > Часто силует навпаки **використовують** для вибору $k$ — беруть те, що дає > найбільше середнє $\bar{s}$. --- ## Застосування в аналітиці даних - **Сегментація ринку.** Групування клієнтів за поведінкою чи вподобаннями; дендрограма показує, як дрібні сегменти зливаються у великі, і дає змогу обрати зручний рівень деталізації сегментації. - **Оцінка роботи персоналу та аналіз уподобань споживачів.** Виявлення груп співробітників чи покупців зі схожими профілями без наперед заданого числа груп. - **Розпізнавання образів і аналіз просторових даних.** Одиночний зв'язок вловлює **витягнуті**, нерегулярні форми (наприклад, географічні скупчення), тоді як Ward і повний зв'язок краще виділяють компактні згустки. - **Класифікація документів.** Ієрархія тем: близькі документи зливаються рано, тематичні розділи — біля кореня; зручно для навігації каталогом. - **Біоінформатика.** Дендрограми — стандарт для кластеризації генів і побудови філогенетичних дерев (метод UPGMA прийшов саме звідти). - **Вибір числа кластерів.** Навіть коли остаточно застосовують $k$-середніх, дендрограму й силует часто використовують **попередньо**, щоб оцінити розумне $k$. ## Підсумок - **Ієрархічна кластеризація** будує послідовність **вкладених** розбиттів у вигляді **бінарного дерева**: листя — точки, корінь — усі дані. Число кластерів обирають **після** обчислень, розрізавши **дендрограму**. - **Дендрограма**: висота з'єднання = відстань між кластерами під час злиття; розріз на висоті $h$ дає конкретне розбиття; великий стрибок висоти підказує, де різати. - **Агломеративний алгоритм** (знизу догори): кожна точка — кластер; будуємо матрицю відстаней; зливаємо найближчу пару; повторюємо, доки не лишиться один кластер. - **Метрики зв'язку** визначають «відстань між кластерами»: **одиночний** ($\min$), **повний** ($\max$), **середній** (UPGMA), **центроїдний** (між центроїдами), **Ward** (мінімум приросту дисперсії $\Delta\mathrm{ESS}$). Одиночний схильний до **ланцюжка**, повний і Ward дають **компактні** кластери. - На даних $\{0,1,6,10,13\}$ одиночний зв'язок дав $\{0,1\}\mid\{6,10,13\}$, а повний — $\{0,1,6\}\mid\{10,13\}$: місткова точка $6$ приєдналася по-різному. - **DIANA** (згори донизу): відколюємо найвіддаленішу точку з кластера найбільшого діаметра й нарощуємо відколоту групу, доки $D(i) > 0$. На наших даних DIANA дала $\{0,1,6\}\mid\{10,13\}$ — як повний зв'язок. - **Якість**: **індекс Данна** $=\dfrac{\min\ \text{міжкластерна}}{\max\ \text{діаметр}}$ (більше — краще); **силует** $s=\dfrac{b-a}{\max(a,b)}\in[-1,1]$ (ближче до $1$ — краще). Для наших даних одиночне розбиття мало Данн $0.714$ і силует $\approx 0.60$. ## Вправи ### Для розігріву 1. Поясніть, чим **вкладене** розбиття відрізняється від довільного набору кластерів. Наведіть приклад двох розбиттів, які **не** утворюють вкладеної пари. 2. Що означає **висота** з'єднання в дендрограмі? Як за дендрограмою отримати розбиття на $3$ кластери? 3. Для двох кластерів $\{1, 2\}$ і $\{8, 10\}$ обчисліть відстань одиночного, повного та середнього зв'язку (одновимірні точки, $d=|x-y|$). ### Стандартні 4. Для точок $\{0, 2, 5, 6, 10\}$ виконайте агломеративну кластеризацію **одиночним** зв'язком: побудуйте матрицю відстаней, випишіть послідовність злиттів із висотами та накресліть схематичну дендрограму. 5. Ті самі точки $\{0, 2, 5, 6, 10\}$ згрупуйте **повним** зв'язком. Порівняйте розбиття на $2$ кластери з результатом вправи 4; поясніть відмінність через поведінку $\min$ проти $\max$. 6. Для розбиття $\{0,2\}\mid\{5,6,10\}$ обчисліть **індекс Данна** та **середній силует**. Чи узгоджуються обидві міри в оцінці якості? ### Підвищеної складності 7. Виконайте **DIANA** для точок $\{1, 2, 9, 10, 11\}$: знайдіть діаметр, зерно відколотої групи (за середніми відстанями), перерозподіліть точки й запишіть перший поділ. Порівняйте з результатом повного зв'язку. 8. Доведіть, що для **одиночного** зв'язку висоти злиттів утворюють **неспадну** послідовність (дендрограма без «інверсій»). Наведіть приклад, коли **центроїдний** метод дає інверсію (злиття на меншій висоті, ніж попереднє). 9. Покажіть, що для двох кластерів формула Варда $\Delta\mathrm{ESS} = \frac{|C_i||C_j|}{|C_i|+|C_j|}\lVert\mu_i-\mu_j\rVert^2$ дорівнює приросту загальної суми квадратів $\mathrm{ESS}$ при злитті $C_i$ і $C_j$. *(Підказка: розкрийте $\mathrm{ESS}$ об'єднаного кластера через центроїд об'єднання $\mu = \frac{|C_i|\mu_i + |C_j|\mu_j}{|C_i|+|C_j|}$.)*