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

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

## 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}$:

| Назва | Формула |
|---|---|
| **Манхеттенська** ($L_1$) | $\sum_i |x_i - y_i|$ |
| **Евклідова** ($L_2$) | $\sqrt{\sum_i (x_i - y_i)^2}$ |
| **Чебишова** ($L_\infty$) | $\max_i |x_i - y_i|$ |

Метод $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$-середніх шукає
локальний мінімум ітераційно:

```text
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.** Евклідові відстані до центрів і віднесення:

| Точка | $d(\cdot, \mu_1{=}(2,8))$ | $d(\cdot, \mu_2{=}(3,8))$ | Кластер |
|:--:|:--:|:--:|:--:|
| $x_1(2,8)$ | $0.000$ | $1.000$ | $C_1$ |
| $x_2(3,8)$ | $1.000$ | $0.000$ | $C_2$ |
| $x_3(2,9)$ | $1.000$ | $1.414$ | $C_1$ |
| $x_4(8,2)$ | $8.485$ | $7.810$ | $C_2$ |
| $x_5(9,2)$ | $9.220$ | $8.485$ | $C_2$ |
| $x_6(9,3)$ | $8.602$ | $7.810$ | $C_2$ |

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

| Точка | $d(\cdot, \mu_1)$ | $d(\cdot, \mu_2)$ | Кластер |
|:--:|:--:|:--:|:--:|
| $x_1(2,8)$ | $0.500$ | $6.755$ | $C_1$ |
| $x_2(3,8)$ | $1.118$ | $6.010$ | $C_1$ |
| $x_3(2,9)$ | $0.500$ | $7.425$ | $C_1$ |
| $x_4(8,2)$ | $8.846$ | $1.904$ | $C_2$ |
| $x_5(9,2)$ | $9.552$ | $2.475$ | $C_2$ |
| $x_6(9,3)$ | $8.902$ | $1.904$ | $C_2$ |

Точка $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.