# Лекція 9. Задачі кластеризації. Метод $k$-середніх ## Огляд Модулі 3 і 4 присвячені двом спорідненим, але принципово різним задачам. У [Лекціях 6](DA-L06.md)–[8](DA-L08.md) ми розв'язували **класифікацію**: маючи навчальну вибірку з **відомими** мітками класів, будували правило, що приписує клас новому об'єкту. Це **навчання з учителем** (англ. *supervised learning*) — «учитель» у вигляді правильних відповідей вказує алгоритму, до чого прагнути. Тепер уявіть, що міток **немає** зовсім. Є лише таблиця об'єктів з їхніми ознаками — покупці з історією покупок, документи, пікселі зображення, зорі на знімку — і треба самотужки виявити в них **природну структуру**: поділити на групи так, щоб усередині групи об'єкти були схожі, а між групами — різні. Це задача **кластеризації** — центральна задача **навчання без учителя** (англ. *unsupervised learning*), якій присвячено весь Модуль 4. У цьому розділі ми означуємо задачу кластеризації та відмежовуємо її від класифікації; показуємо, чому її **не можна** розв'язати простим перебором усіх розбиттів (тут з'явиться **число Стірлінга** з комбінаторики); оглядаємо п'ять класів методів; уводимо **функції відстані**, без яких «схожість» не має числового змісту; і докладно розбираємо найпопулярніший метод розбиття — **$k$-середніх** ($k$-means) — з його цільовою функцією (сумою квадратів помилок), алгоритмом, критерієм збіжності, сильними й слабкими сторонами. Наприкінці розглянемо **нечіткий** варіант — метод $c$-середніх, де об'єкт належить кільком кластерам частково. [Лекція 10](DA-L10.md) продовжить тему **ієрархічними** методами, що будують не одне розбиття, а цілу вкладену систему кластерів. > **Практичний бік.** Ітерації $k$-середніх «руками» на малому наборі точок ви > виконаєте в аудиторії, а сам алгоритм реалізуєте **програмою** в > [Лабораторній роботі 9](../Laboratory/Laboratory9/main.md). --- ## 9.1 Задача кластеризації > **Означення (кластеризація).** **Кластеризацією** (англ. *clustering*) називають > процес розбиття вибірки об'єктів на підмножини — **кластери** — так, щоб об'єкти > в межах одного кластера були **схожі** між собою, а об'єкти різних кластерів — > **несхожі**. Мітки груп заздалегідь **невідомі** й самі є результатом роботи > алгоритму. Формально задано множину об'єктів $X = \{x_1, x_2, \dots, x_n\}$, кожен з яких — вектор ознак $x_i \in \mathbb{R}^d$. Треба знайти **розбиття** $\{C_1, C_2, \dots, C_k\}$ множини $X$, тобто систему підмножин, що $$ C_1 \cup C_2 \cup \dots \cup C_k = X, \qquad C_a \cap C_b = \varnothing \ (a \ne b), \qquad C_c \ne \varnothing. $$ Кластери **не перетинаються** (кожен об'єкт — рівно в одному), **покривають** усю вибірку й **непорожні**. «Схожість» вимірюють через **відстань** (§9.4): чим менша відстань між об'єктами, тим вони схожіші. Ключова відмінність від класифікації — у **природі навчання**: | | Класифікація (Модуль 3) | Кластеризація (Модуль 4) | |---|---|---| | Мітки в навчанні | **відомі** (є «правильні відповіді») | **невідомі** | | Тип навчання | з учителем (*supervised*) | без учителя (*unsupervised*) | | Що шукаємо | правило «ознаки $\to$ відомий клас» | саму структуру груп | | Число груп | задане мітками | часто треба **обрати** самому | | Як оцінити якість | точність на тесті з мітками | внутрішні міри (компактність, §9.5) | > **Типова помилка (кластери $\ne$ класи).** Знайдені кластери — це groupings за > схожістю ознак, а **не** готові змістовні класи. Алгоритм може розділити людей > за зростом, тоді як вас цікавив дохід; або злити в один кластер дві змістовно > різні групи, схожі за обраними ознаками. Інтерпретацію кластерів завжди робить > **людина**, дивлячись на об'єкти всередині кожного. --- ## 9.2 Розв'язання перебором. Число Стірлінга Найпряміший задум — **перебрати всі можливі розбиття** вибірки на $k$ груп, для кожного порахувати міру якості (компактність кластерів) і обрати найкраще. Задум правильний, але **обчислювально нездійсненний**: розбиттів надзвичайно багато. Скільки саме — каже комбінаторика. > **Означення (число Стірлінга другого роду).** **Число Стірлінга другого роду** > $S(n, k)$ — це кількість способів розбити множину з $n$ **різних** об'єктів на > $k$ **непорожніх** підмножин, що не враховують порядку (групи не пронумеровані). Ці числа задовольняють рекурентне співвідношення (кожен новий об'єкт або утворює власну групу, або приєднується до однієї з $k$ наявних): $$ S(n, k) = k \cdot S(n-1, k) + S(n-1, k-1), \qquad S(n, 1) = S(n, n) = 1. $$ Обчислимо перші рядки трикутника $S(n, k)$: | $n \backslash k$ | 1 | 2 | 3 | 4 | 5 | $B_n = \sum_k S(n,k)$ | |:--:|:--:|:--:|:--:|:--:|:--:|:--:| | 1 | 1 | | | | | 1 | | 2 | 1 | 1 | | | | 2 | | 3 | 1 | 3 | 1 | | | 5 | | 4 | 1 | 7 | 6 | 1 | | 15 | | 5 | 1 | 15 | 25 | 10 | 1 | 52 | Останній стовпець — **число Белла** $B_n$: скільки всього є розбиттів $n$ об'єктів (на будь-яке число груп, $B_n = \sum_{k} S(n,k)$). Наприклад, для $n = 6$ їх уже $B_6 = 203$. Якщо ми **не знаємо** $k$ наперед, перебирати довелося б саме $B_n$ варіантів. **Приклад 9.1 (усі розбиття на 2 групи).** Для $n = 4$ об'єктів $\{a,b,c,d\}$ на $k = 2$ групи маємо $S(4, 2) = 7$ розбиттів: $$ \{a\}\{bcd\},\ \{b\}\{acd\},\ \{c\}\{abd\},\ \{d\}\{abc\},\ \{ab\}\{cd\},\ \{ac\}\{bd\},\ \{ad\}\{bc\}. $$ Для двох груп є зручна формула: кожен об'єкт, крім першого, потрапляє «з першим» або «окремо», що дає $2^{n-1}$ варіантів, з яких один (усі разом) лишає другу групу порожньою: $$ S(n, 2) = 2^{\,n-1} - 1. $$ Перевіримо: $S(4,2) = 2^3 - 1 = 7$; $S(10, 2) = 2^9 - 1 = 511$ — саме це число стоїть у таблиці на слайді лекції. **Приклад 9.2 (вибух комбінаторної складності).** Порахуємо $S(n, 2)$ для зростаючих $n$: | $n$ | $S(n, 2) = 2^{n-1}-1$ | |:--:|:--:| | 10 | $511$ | | 20 | $524\,287$ | | 50 | $\approx 5.63 \times 10^{14}$ | | 100 | $\approx 6.34 \times 10^{29}$ | І це лише для **двох** груп — найповільніший стовпець. Уже при $k = 10$ число розбиттів $50$ об'єктів сягає $\approx 2.62 \times 10^{43}$, а $100$ об'єктів — $\approx 2.75 \times 10^{93}$. Жоден комп'ютер не перебере стільки варіантів за час існування Всесвіту. ![Вибух числа розбиттів S(n,2)=2^(n-1)−1 на логарифмічній шкалі: за сотню об'єктів воно сягає 10^29](img/l09_stirling.png) > **Висновок.** Точний перебір розбиттів **неможливий** навіть для сотні об'єктів. > Тому всі практичні методи кластеризації — це **евристики**: вони не гарантують > глобально найкращого розбиття, але швидко знаходять **добре** розбиття. Метод > $k$-середніх (§9.5) — класичний приклад такої евристики. --- ## 9.3 Класи методів кластеризації Методи кластеризації прийнято ділити на п'ять великих класів за тим, **як** вони формують кластери. - **Методи розбиття** (англ. *partitioning*). Одразу ділять вибірку на задане число $k$ кластерів і покращують поділ ітераціями. Приклади: **$k$-середніх** (§9.5), $k$-медоїдів (центр — реальний об'єкт, а не середнє). Швидкі, масштабовані; треба задати $k$. - **Ієрархічні методи** (англ. *hierarchical*) — **об'єднувальні** (агломеративні: почати з окремих об'єктів і зливати) або **роздільні** (дивізивні: почати з усієї вибірки й ділити). Будують **дерево** вкладених кластерів (дендрограму), не вимагають наперед задавати $k$ (тема [Лекції 10](DA-L10.md)). - **Методи на основі щільності** (англ. *density-based*, напр. DBSCAN). Кластер — це область **високої щільності** точок, відокремлена розрідженими областями. Знаходять кластери **довільної форми** й автоматично позначають **викиди**. - **Решіткові методи** (англ. *grid-based*, напр. STING, CLIQUE). Розбивають простір ознак на скінченну **сітку** комірок і працюють з комірками, а не окремими точками, — дуже швидко на великих даних. - **Модельні методи** (англ. *model-based*). Припускають, що дані породжені **сумішшю розподілів** (напр., суміш гаусіан, GMM), і підбирають параметри моделі; належність об'єкта до кластера стає **ймовірнісною**. У цій лекції ми зосереджуємось на найпоширенішому методі розбиття — $k$-середніх, — а в кінці розглянемо його «м'який», модельний за духом варіант — нечіткий $c$-середніх (§9.9). --- ## 9.4 Поняття та функції відстані «Схожість» об'єктів у кластеризації задають через **відстань**: близькі об'єкти схожі, далекі — різні. Щоб відстань поводилася розумно, від функції $d(x, y)$ вимагають властивостей **метрики**. > **Означення (метрика).** Функція $d : X \times X \to \mathbb{R}$ є **метрикою** > (функцією відстані), якщо для всіх $x, y, z$: > 1. **невід'ємність та тотожність:** $d(x, y) \ge 0$, причому $d(x, y) = 0 \iff x = y$; > 2. **симетричність:** $d(x, y) = d(y, x)$; > 3. **нерівність трикутника:** $d(x, z) \le d(x, y) + d(y, z)$. Для векторів ознак $x = (x_1, \dots, x_d)$ і $y = (y_1, \dots, y_d)$ найуживаніші відстані — окремі випадки **відстані Мінковського** порядку $p$: > **Означення (відстань Мінковського).** > $$ d_p(x, y) = \left( \sum_{i=1}^{d} |x_i - y_i|^{p} \right)^{1/p}, \qquad p \ge 1. $$ Три важливі окремі випадки: | Назва | $p$ | Формула | |---|:--:|---| | **Манхеттенська** (міська, $L_1$) | $1$ | $\displaystyle\sum_{i} |x_i - y_i|$ | | **Евклідова** ($L_2$) | $2$ | $\displaystyle\sqrt{\sum_{i} (x_i - y_i)^2}$ | | **Чебишова** ($L_\infty$) | $\to\infty$ | $\displaystyle\max_{i} |x_i - y_i|$ | Евклідова відстань — звичайна «пряма» відстань між точками; манхеттенська рахує шлях уздовж осей (як кварталами міста); чебишова бере найбільше з покоординатних відхилень. Метод $k$-середніх за замовчуванням використовує **евклідову** відстань (точніше, її квадрат — див. §9.5). **Приклад 9.3 (обчислення відстаней).** Нехай $x = (2, 3)$, $y = (5, 7)$. Покоординатні відхилення: $|2-5| = 3$, $|3-7| = 4$. Тоді $$ d_1(x, y) = 3 + 4 = 7, \qquad d_2(x, y) = \sqrt{3^2 + 4^2} = \sqrt{25} = 5, \qquad d_\infty(x, y) = \max(3, 4) = 4. $$ Відстань Мінковського порядку $p = 3$: $d_3 = (3^3 + 4^3)^{1/3} = (27 + 64)^{1/3} = 91^{1/3} \approx 4.498$. Зі зростанням $p$ відстань зменшується від $L_1 = 7$ до $L_\infty = 4$. ![Евклідова, манхеттенська та чебишова відстані між точками x=(2,3) і y=(5,7): прямокутний трикутник з катетами 3 і 4](img/l09_distance.png) > **Типова помилка (несумірні ознаки).** Якщо ознаки мають різні масштаби (напр., > «вік» у роках $\sim 20\text{–}60$ і «дохід» у гривнях $\sim 10\,000\text{–}100\,000$), > евклідова відстань майже цілком визначається доходом — вік «тоне». Перед > кластеризацією ознаки зазвичай **нормалізують** (напр., до нульового середнього > й одиничної дисперсії), щоб кожна робила співмірний внесок у відстань. Це > робитимете й у домашньому завданні ([середній рівень](../Laboratory/Laboratory9/4task.md)). --- ## 9.5 Метод $k$-середніх. Сума квадратів помилок **Метод $k$-середніх** ($k$-means) — найвідоміший метод розбиття. Ідея: кожен кластер представлений своїм **центром** — **центроїдом** $\mu_c$, — а об'єкти відносять до найближчого центроїда. Якість такого розбиття вимірюють **сумою квадратів помилок**. > **Означення (центроїд).** **Центроїд** кластера $C_c$ — це середнє (центр ваги) > його об'єктів: > $$ \mu_c = \frac{1}{|C_c|} \sum_{x \in C_c} x. $$ > **Означення (сума квадратів помилок, SSE).** **Цільова функція** методу > $k$-середніх — **сума квадратів помилок** (англ. *sum of squared errors*): сума > квадратів відстаней від кожного об'єкта до центроїда його кластера: > $$ \mathrm{SSE} = \sum_{c=1}^{k} \sum_{x \in C_c} \lVert x - \mu_c \rVert^2. $$ Величина $\mathrm{SSE}$ вимірює **компактність** кластерів: що щільніше об'єкти згруповані навколо своїх центрів, то вона менша. Формальна задача $k$-середніх: > **Формальна задача.** Знайти розбиття $\{C_1, \dots, C_k\}$, що **мінімізує** > $\mathrm{SSE}$. Точний розв'язок — NP-складна задача (перебір розбиттів, §9.2), > тому $k$-середніх шукає **локальний** мінімум ітераційно. Чому центроїд — це саме **середнє**? Бо для фіксованого набору точок кластера середнє — це та точка $\mu$, що мінімізує $\sum_{x} \lVert x - \mu \rVert^2$ (сума квадратів відстаней). Це прямий наслідок того, що середнє мінімізує дисперсію (Лекція 2). Тому крок «перерахувати центр як середнє» гарантовано **зменшує** (не збільшує) SSE — саме на цьому тримається збіжність алгоритму. --- ## 9.6 Алгоритм $k$-середніх Алгоритм чергує два кроки: **віднесення** точок до найближчих центрів і **перерахунок** центрів як середніх утворених кластерів. ```text kMeans(точки X, число кластерів k): 1. ІНІЦІАЛІЗАЦІЯ: обрати k псевдовипадкових центроїдів mu_1, ..., mu_k повторювати: 2. ВІДНЕСЕННЯ: кожну точку x віднести до кластера з найближчим центроїдом c(x) = argmin_c d(x, mu_c) 3. ПЕРЕРАХУНОК: для кожного кластера обчислити новий центроїд mu_c = (середнє всіх точок кластера C_c) 4. якщо центроїди НЕ ЗМІСТИЛИСЯ -> СТОП (кластери побудовано) інакше -> повернутися до кроку 2 повернути кластери C_1, ..., C_k та центроїди ``` **Крок 2 (віднесення об'єкта).** Об'єкт $x$ потрапляє до того кластера, чий центроїд найближчий: $$ c(x) = \arg\min_{c \in \{1,\dots,k\}} \; d(x, \mu_c) = \arg\min_{c} \; \lVert x - \mu_c \rVert^2. $$ Оскільки корінь — монотонна функція, порівнювати можна **квадрати** відстаней — це уникає обчислення кореня й дає той самий результат. У прикладах ми все ж показуватимемо самі відстані для наочності. **Крок 4 (критерій збіжності).** Алгоритм зупиняється, коли **центроїди перестали зміщуватися**. Це рівносильно тому, що **не змінилося жодне віднесення** точок (стабільне розбиття) і що SSE **перестала спадати**. Можна довести, що кожна ітерація не збільшує SSE, а розбиттів скінченне число, — тож алгоритм **завжди збігається** за скінченну кількість кроків (на практиці — за кілька ітерацій). На практиці додають і «м'які» критерії: зупинятися, коли зсув центрів менший за поріг $\varepsilon$ або досягнуто максимуму ітерацій. --- ## 9.7 Приклад роботи алгоритму **Приклад 9.4.** Кластеризуємо $6$ точок на площині у $k = 2$ кластери: $$ A(1,2),\ B(2,2),\ C(2,4),\quad D(7,4),\ E(8,5),\ F(7,6). $$ Візьмемо **невдалу** ініціалізацію — обидва початкові центроїди зліва: $\mu_1 = A(1,2)$, $\mu_2 = B(2,2)$. Простежимо, як алгоритм її виправляє. **Ітерація 1.** Відстані від кожної точки до центрів (евклідові) та віднесення: | Точка | $d(\cdot, \mu_1{=}(1,2))$ | $d(\cdot, \mu_2{=}(2,2))$ | Кластер | |:--:|:--:|:--:|:--:| | $A(1,2)$ | $0.000$ | $1.000$ | $C_1$ | | $B(2,2)$ | $1.000$ | $0.000$ | $C_2$ | | $C(2,4)$ | $2.236$ | $2.000$ | $C_2$ | | $D(7,4)$ | $6.325$ | $5.385$ | $C_2$ | | $E(8,5)$ | $7.616$ | $6.708$ | $C_2$ | | $F(7,6)$ | $7.211$ | $6.403$ | $C_2$ | Розбиття: $C_1 = \{A\}$, $C_2 = \{B, C, D, E, F\}$. Перераховуємо центроїди як середні: $$ \mu_1 = A = (1, 2), \qquad \mu_2 = \left(\tfrac{2+2+7+8+7}{5}, \tfrac{2+4+4+5+6}{5}\right) = (5.2,\ 4.2). $$ Після перерахунку $\mathrm{SSE} = 43.6$ (було $119$ до першого перерахунку). **Ітерація 2.** З новими центрами $\mu_1 = (1,2)$, $\mu_2 = (5.2,\ 4.2)$: | Точка | $d(\cdot, \mu_1)$ | $d(\cdot, \mu_2)$ | Кластер | |:--:|:--:|:--:|:--:| | $A(1,2)$ | $0.000$ | $4.741$ | $C_1$ | | $B(2,2)$ | $1.000$ | $3.883$ | $C_1$ | | $C(2,4)$ | $2.236$ | $3.206$ | $C_1$ | | $D(7,4)$ | $6.325$ | $1.811$ | $C_2$ | | $E(8,5)$ | $7.616$ | $2.912$ | $C_2$ | | $F(7,6)$ | $7.211$ | $2.546$ | $C_2$ | Тепер точки $B$ і $C$ **перейшли** до $C_1$: розбиття стало $C_1 = \{A, B, C\}$, $C_2 = \{D, E, F\}$ — природний поділ «лівих» і «правих» точок. Нові центроїди: $$ \mu_1 = \left(\tfrac{1+2+2}{3}, \tfrac{2+2+4}{3}\right) = \left(\tfrac{5}{3}, \tfrac{8}{3}\right) \approx (1.667,\ 2.667), \quad \mu_2 = \left(\tfrac{7+8+7}{3}, \tfrac{4+5+6}{3}\right) = \left(\tfrac{22}{3}, 5\right) \approx (7.333,\ 5). $$ $\mathrm{SSE} = 6.0$. ![Три панелі ітерацій k-середніх: ініціалізація з обома центрами зліва, перше та друге віднесення точок із рухом центроїдів до правильного поділу](img/l09_iterations.png) **Ітерація 3.** З цими центрами віднесення **не змінюється** ($A, B, C \to C_1$; $D, E, F \to C_2$), тож центроїди лишаються тими самими — **критерій збіжності виконано, алгоритм завершено**. Простежимо, як монотонно спадала цільова функція: $$ \mathrm{SSE}: \quad 119 \ \to\ 43.6 \ \to\ 6.0 \ \to\ 6.0 \ (\text{стабілізувалася}). $$ ![Крива монотонного спадання SSE за ітераціями до збіжності: 119, потім 43.6, далі 6 і стабілізація на 6](img/l09_sse.png) **Відповідь:** кластери $\{A, B, C\}$ і $\{D, E, F\}$ з центрами $(\tfrac53, \tfrac83)$ та $(\tfrac{22}{3}, 5)$; фінальна $\mathrm{SSE} = 6$. Попри «невдалий» старт (обидва центри в одному згустку) алгоритм за дві ітерації знайшов правильне розбиття. ![Фінальні кластери прикладу: точки A, B, C та D, E, F розфарбовані за кластером із центроїдами-хрестиками й підписом SSE=6](img/l09_clusters.png) --- ## 9.8 Сильні та слабкі сторони **Сильні сторони.** $k$-середніх **простий**, **швидкий** (складність $O(n k d \cdot t)$ на $t$ ітерацій) і добре **масштабується** на великі дані; результат легко інтерпретувати через центроїди («типовий представник» кластера). **Слабкі сторони й способи їх пом'якшити.** - **Треба задати $k$.** Число кластерів — вхідний параметр, а «правильне» $k$ наперед невідоме. Його підбирають, порівнюючи розбиття за різних $k$: **метод ліктя** (*elbow*) шукає $k$, після якого SSE спадає вже повільно; **силует** (*silhouette*) оцінює, наскільки об'єкти «свої» у своїх кластерах (докладніше — [Лекція 10](DA-L10.md) та [високий рівень лабораторної](../Laboratory/Laboratory9/4task.md)). - **Чутливість до ініціалізації.** Різні початкові центроїди дають різні локальні мінімуми SSE. Рятунок — **кілька запусків** з різною випадковою ініціалізацією й вибір розбиття з **найменшою** SSE; розумніший старт дає прийом **$k$-means++** (центри розставляють якнайдалі один від одного). - **Чутливість до викидів.** Оскільки центр — це **середнє**, один далекий викид сильно зміщує центроїд. Стійкіший варіант — **$k$-медоїдів**, де центром є реальний об'єкт (медоїд), а не середнє. - **Сферичні кластери.** Мінімізуючи суму квадратів, $k$-середніх схильний утворювати **опуклі, приблизно кулясті** кластери близького розміру. Витягнуті, вкладені чи різнорозмірні кластери він розділяє погано — там доречніші щільнісні або ієрархічні методи. ![Метод ліктя: залежність SSE від числа кластерів k із помітним «ліктем» при k=2, після якого SSE спадає повільно](img/l09_elbow.png) > **Типова помилка (масштаб і викиди — перед кластеризацією).** Найчастіші причини > «дивних» кластерів — ненормалізовані ознаки (§9.4) та невилучені викиди. І те, й > те спотворює відстані та центроїди. Підготовка даних (нормалізація, обробка > викидів) для $k$-середніх важливіша за вибір самого алгоритму. --- ## 9.9 Нечіткий метод $c$-середніх У $k$-середніх віднесення **жорстке**: об'єкт належить рівно одному кластеру. Але межові об'єкти (посередині між двома згустками) природніше вважати такими, що належать **частково** обом. Цю ідею реалізує **нечіткий метод $c$-середніх** (англ. *fuzzy $c$-means*, FCM). > **Означення (матриця приналежності).** Замість жорсткого віднесення FCM > зберігає **ступені приналежності** $u_{ic} \in [0, 1]$ — наскільки об'єкт $x_i$ > належить кластеру $c$, — причому для кожного об'єкта > $$ \sum_{c=1}^{k} u_{ic} = 1. $$ Матриця $U = [u_{ic}]$ узагальнює жорстке розбиття (де $u_{ic}$ дорівнювало б лише $0$ чи $1$) на «м'яке». Цільова функція зважує кожен квадрат відстані ступенем приналежності, піднесеним до **параметра нечіткості** $m > 1$ (зазвичай $m = 2$): > **Означення (функція втрат FCM).** > $$ J_m = \sum_{i=1}^{n} \sum_{c=1}^{k} u_{ic}^{\,m} \, \lVert x_i - \mu_c \rVert^2. $$ Алгоритм чергує оновлення центрів і матриці приналежності: ```text cMeans(точки X, число кластерів k, нечіткість m): 1. ініціалізувати центроїди (або матрицю приналежності U) випадково повторювати: 2. ПРИНАЛЕЖНІСТЬ: перерахувати u_ic за формулою нижче 3. ЦЕНТРИ: перерахувати mu_c як ЗВАЖЕНЕ середнє (ваги u_ic^m) 4. РОЗРАХУНОК ВТРАТ J_m 5. якщо J_m майже не зменшилася -> СТОП, інакше -> до кроку 2 ``` - **Центр** — зважене середнє всіх точок (а не лише «своїх»): $$ \mu_c = \frac{\sum_{i=1}^{n} u_{ic}^{\,m}\, x_i}{\sum_{i=1}^{n} u_{ic}^{\,m}}. $$ - **Приналежність** — тим більша, чим ближчий об'єкт до центра $c$ порівняно з іншими центрами: $$ u_{ic} = \frac{1}{\displaystyle\sum_{j=1}^{k} \left( \frac{d(x_i, \mu_c)}{d(x_i, \mu_j)} \right)^{2/(m-1)}}. $$ **Приклад 9.5 (обчислення приналежності).** Нехай $m = 2$, центри $\mu_1 = (1,1)$, $\mu_2 = (5,5)$, а об'єкт $x = (3, 2)$. Відстані: $d_1 = \sqrt{(3-1)^2 + (2-1)^2} = \sqrt5 \approx 2.236$, $d_2 = \sqrt{(3-5)^2 + (2-5)^2} = \sqrt{13} \approx 3.606$. При $m = 2$ показник $2/(m-1) = 2$, тож формула зводиться до обернених квадратів відстаней: $$ u_{1} = \frac{1/d_1^2}{1/d_1^2 + 1/d_2^2} = \frac{1/5}{1/5 + 1/13} = \frac{0.2}{0.2769} \approx 0.722, \qquad u_{2} = 1 - u_{1} \approx 0.278. $$ Об'єкт на $72\%$ належить першому кластеру й на $28\%$ — другому (ближчий до $\mu_1$, тож і приналежність до нього більша). Щоб дістати жорстке розбиття, об'єкт відносять до кластера з **найбільшою** приналежністю. FCM корисний, коли кластери **перекриваються** й потрібна «впевненість» віднесення, а не лише мітка; він є містком до **модельних** методів (§9.3), де приналежність трактують як ймовірність. --- ## Застосування в аналітиці даних - **Сегментація клієнтів.** Поділ покупців на групи за поведінкою (сума й частота покупок, категорії товарів) для таргетованого маркетингу — класичне застосування $k$-середніх. - **Стиснення зображень (квантування кольорів).** Кластеризація пікселів у просторі кольорів RGB на $k$ груп і заміна кожного пікселя центроїдом його кластера зменшує палітру до $k$ кольорів. - **Виявлення аномалій.** Об'єкти, далекі від усіх центроїдів (з великим внеском у SSE), — кандидати у **викиди**; щільнісні методи роблять це ще природніше. - **Групування документів і тем.** Кластеризація текстів за векторами ознак (частоти слів) виявляє тематичні групи без наперед заданих рубрик. - **Попередній етап для інших методів.** Мітки кластерів часто стають новою ознакою або способом стиснути дані перед класифікацією чи візуалізацією. ## Підсумок - **Кластеризація** — поділ вибірки на групи схожих об'єктів **без заздалегідь відомих міток**; це навчання **без учителя**, на відміну від класифікації (з учителем) з Модуля 3. - **Точний перебір** розбиттів неможливий: їх число — **Стірлінга** $S(n,k)$ (для двох груп $S(n,2) = 2^{n-1}-1$) — росте надзвичайно швидко (уже $S(10,2) = 511$, а $S(100,2) \approx 6.3 \times 10^{29}$). Тому всі методи — **евристики**. - Методи діляться на **розбиття**, **ієрархічні**, **щільнісні**, **решіткові**, **модельні**. - **Схожість** вимірюють **відстанню**: евклідова ($L_2$), манхеттенська ($L_1$), Мінковського ($L_p$), чебишова ($L_\infty$). Ознаки різного масштабу **нормалізують**. - **$k$-середніх** мінімізує **суму квадратів помилок** $\mathrm{SSE} = \sum_c \sum_{x \in C_c} \lVert x - \mu_c \rVert^2$, чергуючи **віднесення** точок до найближчого центроїда й **перерахунок** центроїдів як середніх. Збігається, коли центроїди перестають зміщуватися; SSE монотонно спадає. У прикладі кластери $\{A,B,C\}$, $\{D,E,F\}$ дали $\mathrm{SSE} = 6$. - **Слабкі місця** $k$-середніх: треба задати $k$; чутливість до ініціалізації (рятують кілька запусків / $k$-means++) та викидів ($k$-медоїдів); схильність до **сферичних** кластерів. - **Нечіткий $c$-середніх** дає **м'яке** віднесення — матрицю приналежності $u_{ic}$ ($\sum_c u_{ic} = 1$) — і мінімізує $J_m = \sum_i \sum_c u_{ic}^{m} \lVert x_i - \mu_c \rVert^2$, оновлюючи центри зваженим середнім. ## Вправи ### Для розігріву 1. Чим кластеризація відрізняється від класифікації? Наведіть по одному прикладу задачі кожного типу з вашої предметної області. 2. Для точок $x = (0, 0)$ і $y = (3, 4)$ обчисліть манхеттенську, евклідову та чебишову відстані. Яка з них найбільша, яка найменша й чому? 3. Запишіть означення SSE. Що станеться зі значенням SSE, якщо збільшити $k$ аж до $k = n$ (кожна точка — окремий кластер)? ### Стандартні 4. Обчисліть $S(5, 2)$ і $S(5, 3)$ за рекурентною формулою, спираючись на рядок $n = 4$ трикутника. Перевірте $S(5,2)$ формулою $2^{n-1}-1$. 5. Дано точки $P_1(1,1)$, $P_2(1,2)$, $P_3(2,1)$, $P_4(6,5)$, $P_5(5,6)$, $P_6(6,6)$ і $k = 2$. Узявши початкові центроїди $\mu_1 = P_1$, $\mu_2 = P_4$, виконайте одну ітерацію $k$-середніх: віднесіть точки й перерахуйте центроїди. 6. Для об'єкта $x = (2, 2)$ і центрів $\mu_1 = (0, 0)$, $\mu_2 = (4, 5)$ обчисліть нечіткі приналежності $u_1, u_2$ при $m = 2$. До якого кластера віднести $x$ за жорстким рішенням? ### Підвищеної складності 7. Доведіть, що для фіксованого кластера точок $\{x_1, \dots, x_m\}$ сума квадратів відстаней $\sum_i \lVert x_i - \mu \rVert^2$ мінімальна саме при $\mu = \frac{1}{m}\sum_i x_i$ (центроїд — середнє). *(Підказка: розкрийте квадрат покоординатно й прирівняйте похідну за $\mu$ до нуля.)* 8. Поясніть, чому кожна ітерація $k$-середніх **не збільшує** SSE (розгляньте окремо крок віднесення й крок перерахунку) і чому звідси випливає збіжність за скінченну кількість кроків. Чи гарантує це **глобальний** мінімум? 9. Наведіть приклад розташування точок на площині, для якого $k$-середніх з $k = 2$ дає **різні** розбиття залежно від початкових центроїдів. Як на практиці борються з цією залежністю від ініціалізації? 10. Виведіть, що для двох кластерів ($k = 2$) число можливих непорожніх розбиттів $n$ об'єктів дорівнює $2^{n-1} - 1$, і поясніть комбінаторний сенс кожного доданка у виведенні.