Лекція 10. Ієрархічні методи кластеризації #

Огляд #

У Лекції 9 ми розв’язали задачу кластеризації методом $k$-середніх: заздалегідь фіксували число кластерів $k$, розкидали центри й ітеративно «притягали» до них точки. Такий підхід простий і швидкий, але має дві слабкості: число кластерів треба знати наперед, а результат залежить від випадкового початкового розкидання центрів і від того, що кластери вважають приблизно кулястими.

Ієрархічні методи знімають першу з цих проблем. Замість одного розбиття на $k$ груп вони будують цілу послідовність вкладених розбиттів — від «кожна точка окремо» до «усі точки разом» — і подають її наочним деревом. Дивлячись на це дерево, аналітик сам обирає, на скільки кластерів різати дані, вже після обчислень. У цій лекції ми розберемо два напрями: агломеративний (знизу догори — злиття) і поділяючий (згори донизу — DIANA), докладно вивчимо метрики зв’язку між кластерами (single, complete, average, центроїдний, Ward) і навчимося оцінювати якість кластеризації індексом Данна та силуетним коефіцієнтом. Наступна Лекція 11 відкриє новий розділ — пошук асоціативних правил.

Практичний бік. Агломеративну кластеризацію одиночним і повним зв’язком ви виконуватимете «руками», а потім реалізуєте алгоритм програмою й порівняєте його з $k$-середніми у Лабораторній роботі 10.

Наскрізний приклад лекції — п’ять одновимірних точок (наприклад, значення однієї ознаки в п’яти клієнтів):

$$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):

Плата за гнучкість — обчислювальна вартість: доводиться працювати з матрицею попарних відстаней розміру $n \times n$, тож для дуже великих $n$ ієрархічні методи застосовують до вибірки або підвибірки даних.

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

Результат ієрархічної кластеризації подають дендрограмою.

Означення (дендрограма). Дендрограма — деревоподібна діаграма, що зображує послідовність злиттів (або поділів). Її листя — окремі об’єкти; кожна точка з’єднання (вузол) відповідає об’єднанню двох кластерів, а висота, на якій відбувається з’єднання, дорівнює відстані між цими кластерами в момент злиття.

Як читати дендрограму:

• Висота злиття — це «ціна» об’єднання: чим вище відбулося з’єднання, тим далі були кластери один від одного. Об’єкти, що зливаються низько, схожі; ті, що з’єднуються лише біля кореня, — різні.
• Різати дендрограму горизонтальною лінією на висоті $h$ — означає отримати конкретне розбиття: кожна вертикальна гілка, яку перетинає лінія, дає один кластер. Опустивши лінію нижче, дістанемо більше дрібніших кластерів; піднявши — менше й грубших. Так одна дендрограма містить усі розбиття одразу.
• Великий стрибок висоти між сусідніми злиттями — природна підказка, де різати: він означає, що наступне об’єднання з’єднує вже далекі групи, тож зупинитися варто саме перед ним.

Порядок листя вздовж осі не несе змісту (гілки можна повертати навколо вузла) — значення мають лише висоти з’єднань і структура вкладення.

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

Агломеративний підхід починає з найдрібнішого розбиття й зливає кластери, доки не лишиться один. Це найпоширеніший різновид ієрархічної кластеризації.

Алгоритм (агломеративна кластеризація).

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

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):

Крок за кроком (щоразу шукаємо найменший позатабличний елемент і зливаємо):

• Злиття 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 — це корінь.

Зведемо злиття в таблицю (це, по суті, і є дендрограма):

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

0  ──┐
     ├─(1)──────────────┐
1  ──┘                  │
                        ├─(5)   ← корінь
6  ────────┐            │
           ├─(4)────────┘
10 ──┐     │
     ├─(3)─┘
13 ──┘

Найбільший стрибок висоти — між злиттями на $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).$$

Відстань — середнє з усіх попарних відстаней між точками різних кластерів.

Центроїдний метод (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) обчислимо обидві метрики до кожної групи:

Ось де народжується різниця результатів. Одиночний зв’язок бачить, що в правій групі є точка ($10$), ближча до $6$, ніж будь-яка точка зліва, — і тягне $6$ праворуч. Повний зв’язок дивиться на найдальшу точку: праворуч це $13$ (відстань $7$), зліва — $0$ (відстань $6$), тож він відносить $6$ ліворуч. Середній і центроїдний методи бачать $6$ рівновіддаленою ($5.5$ до обох), тобто $6$ — справжня «місткова» точка. Повні злиття:

Розріз на два кластери дає різні розбиття:

$$\text{одиночний:}\ \{0,1\}\mid\{6,10,13\}, \qquad \text{повний:}\ \{0,1,6\}\mid\{10,13\}.$$

Типова помилка (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 віднесла місткову точку $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$ — імовірно, віднесена не туди.

Приклад 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|}$.)

Lectures/DA-L10.md · 38.2 KB · updated 2026-08-05 09:44