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

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

2.1 Задача кластеризації #

Кластеризація — розбиття вибірки об’єктів $X = \{x_1, \dots, x_n\}$ на групи (кластери) так, щоб об’єкти одного кластера були схожі, а різних — несхожі. Мітки груп невідомі наперед (навчання без учителя) — на відміну від класифікації, де класи задані. Розбиття $\{C_1, \dots, C_k\}$ покриває всю вибірку, кластери не перетинаються й непорожні.

2.2 Функції відстані #

«Схожість» задають відстанню: близькі об’єкти схожі. Для векторів $x = (x_1, \dots, x_d)$ і $y = (y_1, \dots, y_d)$ уживають окремі випадки відстані Мінковського $d_p(x,y) = \big(\sum_i |x_i - y_i|^p\big)^{1/p}$:

Метод $k$-середніх використовує евклідову відстань. Оскільки корінь — монотонна функція, для віднесення точки до найближчого центроїда можна порівнювати квадрати відстаней (без обчислення кореня).

2.3 Метод $k$-середніх та SSE #

Кожен кластер представлений центроїдом $\mu_c$ — середнім своїх об’єктів:

$$\mu_c = \frac{1}{|C_c|} \sum_{x \in C_c} x.$$

Якість розбиття вимірюють сумою квадратів помилок (англ. sum of squared errors):

$$\mathrm{SSE} = \sum_{c=1}^{k} \sum_{x \in C_c} \lVert x - \mu_c \rVert^2.$$

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

kMeans(точки X, число кластерів k):
  1. обрати k псевдовипадкових центроїдів
  повторювати:
     2. ВІДНЕСЕННЯ: кожну точку -> до кластера з найближчим центроїдом
     3. ПЕРЕРАХУНОК: центроїд кожного кластера = середнє його точок
     4. якщо центроїди не змістилися -> СТОП, інакше -> крок 2

2.4 Критерій збіжності #

Алгоритм зупиняється, коли центроїди перестають зміщуватися — рівносильно, коли не змінюється жодне віднесення точок і SSE перестає спадати. Кожна ітерація не збільшує SSE (крок віднесення зменшує її вибором найближчого центра, крок перерахунку — тим, що середнє мінімізує суму квадратів), а розбиттів скінченне число, тож алгоритм завжди збігається за скінченну кількість кроків. Результат залежить від початкових центроїдів (можливий локальний мінімум).

2.5 Нормалізація ознак #

Якщо ознаки мають різні масштаби, евклідова відстань визначається переважно ознакою з більшим діапазоном. Тому перед кластеризацією ознаки нормалізують. Дві поширені схеми:

• $z$-нормування (стандартизація): $x' = \dfrac{x - \bar{x}}{s}$ — нульове середнє й одинична дисперсія кожної ознаки;
• min–max масштабування: $x' = \dfrac{x - x_{\min}}{x_{\max} - x_{\min}}$ — усі значення в $[0, 1]$.

2.6 Вибір числа кластерів $k$ #

$k$ — вхідний параметр; «правильне» $k$ підбирають, порівнюючи розбиття:

• Метод ліктя (англ. elbow). Для кількох $k$ будують графік SSE$(k)$: зі зростанням $k$ SSE спадає, але з певного $k$ — вже повільно. Точку «зламу» (лікоть), після якої виграш малий, беруть за розумне $k$.
• Силуетний коефіцієнт (англ. silhouette). Для об’єкта $i$ нехай $a(i)$ — середня відстань до об’єктів свого кластера, а $b(i)$ — найменша середня відстань до об’єктів іншого кластера. Тоді

  $$s(i) = \frac{b(i) - a(i)}{\max\{a(i),\, b(i)\}} \in [-1, 1].$$

  Середнє $s(i)$ по всіх об’єктах — силует розбиття; що ближче до $1$, то краще розділені кластери. Обирають $k$ з найбільшим силуетом.

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

Кластеризуємо $6$ точок на площині у $k = 2$ кластери:

$$x_1(2,8),\ x_2(3,8),\ x_3(2,9),\quad x_4(8,2),\ x_5(9,2),\ x_6(9,3).$$

Точки утворюють два згустки (вгорі-ліворуч і внизу-праворуч). Візьмемо невдалі початкові центроїди — обидва у верхньому згустку: $\mu_1 = x_1(2,8)$, $\mu_2 = x_2(3,8)$.

Ітерація 1. Евклідові відстані до центрів і віднесення:

Розбиття: $C_1 = \{x_1, x_3\}$, $C_2 = \{x_2, x_4, x_5, x_6\}$. Нові центроїди:

$$\mu_1 = \left(\tfrac{2+2}{2}, \tfrac{8+9}{2}\right) = (2,\ 8.5), \qquad \mu_2 = \left(\tfrac{3+8+9+9}{4}, \tfrac{8+2+2+3}{4}\right) = (7.25,\ 3.75).$$

$\mathrm{SSE} = 50.0$.

Ітерація 2. З новими центрами $\mu_1 = (2,\ 8.5)$, $\mu_2 = (7.25,\ 3.75)$:

Точка $x_2$ перейшла до $C_1$: розбиття стало $C_1 = \{x_1, x_2, x_3\}$, $C_2 = \{x_4, x_5, x_6\}$ — правильний поділ згустків. Нові центроїди:

$$\mu_1 = \left(\tfrac{2+3+2}{3}, \tfrac{8+8+9}{3}\right) = \left(\tfrac{7}{3}, \tfrac{25}{3}\right) \approx (2.333,\ 8.333), \quad \mu_2 = \left(\tfrac{26}{3}, \tfrac{7}{3}\right) \approx (8.667,\ 2.333).$$

$\mathrm{SSE} = \tfrac{8}{3} \approx 2.667$.

Ітерація 3. Віднесення не змінюється, центроїди не зміщуються — збіжність. SSE монотонно спадала: $50.0 \to 2.667 \to 2.667$. Фінальне розбиття $\{x_1, x_2, x_3\}$, $\{x_4, x_5, x_6\}$, $\mathrm{SSE} = \tfrac{8}{3}$.

2.8 Робочий контрольний список #

• Спершу зафіксуйте $k$ і початкові центроїди (перші $k$ точок, випадкові точки або $k$-means++).
• На кроці віднесення для кожної точки рахуйте відстань до всіх центрів і беріть найближчий (порівнюйте квадрати відстаней — швидше).
• На кроці перерахунку новий центр — це покоординатне середнє точок кластера; порожній кластер лишіть зі старим центром (або переініціалізуйте).
• Зупиняйтесь, коли центроїди не змістилися (або зсув менший за поріг $\varepsilon$ / досягнуто максимуму ітерацій).
• SSE має не зростати між ітераціями — якщо зросла, шукайте помилку в обчисленнях.
• Для порівняння розбиттів різних запусків беріть те, у якого найменша SSE.

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