Лекція 9. Задачі кластеризації. Метод $k$-середніх #

Огляд #

Модулі 3 і 4 присвячені двом спорідненим, але принципово різним задачам. У Лекціях 6–8 ми розв’язували класифікацію: маючи навчальну вибірку з відомими мітками класів, будували правило, що приписує клас новому об’єкту. Це навчання з учителем (англ. supervised learning) — «учитель» у вигляді правильних відповідей вказує алгоритму, до чого прагнути.

Тепер уявіть, що міток немає зовсім. Є лише таблиця об’єктів з їхніми ознаками — покупці з історією покупок, документи, пікселі зображення, зорі на знімку — і треба самотужки виявити в них природну структуру: поділити на групи так, щоб усередині групи об’єкти були схожі, а між групами — різні. Це задача кластеризації — центральна задача навчання без учителя (англ. unsupervised learning), якій присвячено весь Модуль 4.

У цьому розділі ми означуємо задачу кластеризації та відмежовуємо її від класифікації; показуємо, чому її не можна розв’язати простим перебором усіх розбиттів (тут з’явиться число Стірлінга з комбінаторики); оглядаємо п’ять класів методів; уводимо функції відстані, без яких «схожість» не має числового змісту; і докладно розбираємо найпопулярніший метод розбиття — $k$-середніх ($k$-means) — з його цільовою функцією (сумою квадратів помилок), алгоритмом, критерієм збіжності, сильними й слабкими сторонами. Наприкінці розглянемо нечіткий варіант — метод $c$-середніх, де об’єкт належить кільком кластерам частково. Лекція 10 продовжить тему ієрархічними методами, що будують не одне розбиття, а цілу вкладену систему кластерів.

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

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): чим менша відстань між об’єктами, тим вони схожіші.

Ключова відмінність від класифікації — у природі навчання:

Типова помилка (кластери $\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)$:

Останній стовпець — число Белла $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$:

І це лише для двох груп — найповільніший стовпець. Уже при $k = 10$ число розбиттів $50$ об’єктів сягає $\approx 2.62 \times 10^{43}$, а $100$ об’єктів — $\approx 2.75 \times 10^{93}$. Жоден комп’ютер не перебере стільки варіантів за час існування Всесвіту.

Висновок. Точний перебір розбиттів неможливий навіть для сотні об’єктів. Тому всі практичні методи кластеризації — це евристики: вони не гарантують глобально найкращого розбиття, але швидко знаходять добре розбиття. Метод $k$-середніх (§9.5) — класичний приклад такої евристики.

9.3 Класи методів кластеризації #

Методи кластеризації прийнято ділити на п’ять великих класів за тим, як вони формують кластери.

• Методи розбиття (англ. partitioning). Одразу ділять вибірку на задане число $k$ кластерів і покращують поділ ітераціями. Приклади: $k$-середніх (§9.5), $k$-медоїдів (центр — реальний об’єкт, а не середнє). Швидкі, масштабовані; треба задати $k$.
• Ієрархічні методи (англ. hierarchical) — об’єднувальні (агломеративні: почати з окремих об’єктів і зливати) або роздільні (дивізивні: почати з усієї вибірки й ділити). Будують дерево вкладених кластерів (дендрограму), не вимагають наперед задавати $k$ (тема Лекції 10).
• Методи на основі щільності (англ. 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.$$

Три важливі окремі випадки:

Евклідова відстань — звичайна «пряма» відстань між точками; манхеттенська рахує шлях уздовж осей (як кварталами міста); чебишова бере найбільше з покоординатних відхилень. Метод $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$.

Типова помилка (несумірні ознаки). Якщо ознаки мають різні масштаби (напр., «вік» у роках $\sim 20\text{–}60$ і «дохід» у гривнях $\sim 10\,000\text{–}100\,000$), евклідова відстань майже цілком визначається доходом — вік «тоне». Перед кластеризацією ознаки зазвичай нормалізують (напр., до нульового середнього й одиничної дисперсії), щоб кожна робила співмірний внесок у відстань. Це робитимете й у домашньому завданні (середній рівень).

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$-середніх #

Алгоритм чергує два кроки: віднесення точок до найближчих центрів і перерахунок центрів як середніх утворених кластерів.

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. Відстані від кожної точки до центрів (евклідові) та віднесення:

Розбиття: $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)$:

Тепер точки $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$.

Ітерація 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{стабілізувалася}).$$

Відповідь: кластери $\{A, B, C\}$ і $\{D, E, F\}$ з центрами $(\tfrac53, \tfrac83)$ та $(\tfrac{22}{3}, 5)$; фінальна $\mathrm{SSE} = 6$. Попри «невдалий» старт (обидва центри в одному згустку) алгоритм за дві ітерації знайшов правильне розбиття.

9.8 Сильні та слабкі сторони #

Сильні сторони. $k$-середніх простий, швидкий (складність $O(n k d \cdot t)$ на $t$ ітерацій) і добре масштабується на великі дані; результат легко інтерпретувати через центроїди («типовий представник» кластера).

Слабкі сторони й способи їх пом’якшити.

• Треба задати $k$. Число кластерів — вхідний параметр, а «правильне» $k$ наперед невідоме. Його підбирають, порівнюючи розбиття за різних $k$: метод ліктя (elbow) шукає $k$, після якого SSE спадає вже повільно; силует (silhouette) оцінює, наскільки об’єкти «свої» у своїх кластерах (докладніше — Лекція 10 та високий рівень лабораторної).
• Чутливість до ініціалізації. Різні початкові центроїди дають різні локальні мінімуми SSE. Рятунок — кілька запусків з різною випадковою ініціалізацією й вибір розбиття з найменшою SSE; розумніший старт дає прийом $k$-means++ (центри розставляють якнайдалі один від одного).
• Чутливість до викидів. Оскільки центр — це середнє, один далекий викид сильно зміщує центроїд. Стійкіший варіант — $k$-медоїдів, де центром є реальний об’єкт (медоїд), а не середнє.
• Сферичні кластери. Мінімізуючи суму квадратів, $k$-середніх схильний утворювати опуклі, приблизно кулясті кластери близького розміру. Витягнуті, вкладені чи різнорозмірні кластери він розділяє погано — там доречніші щільнісні або ієрархічні методи.

Типова помилка (масштаб і викиди — перед кластеризацією). Найчастіші причини «дивних» кластерів — ненормалізовані ознаки (§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.$$

Алгоритм чергує оновлення центрів і матриці приналежності:

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$, і поясніть комбінаторний сенс кожного доданка у виведенні.

Lectures/DA-L09.md · 39.7 KB · updated 2026-08-05 09:27