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

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

## 2.1 Задача класифікації

**Класифікація** — це навчання з учителем: за вектором **ознак** об'єкта
$x = (x_1, \dots, x_m)$ передбачити його **клас** $y$ з наперед відомої скінченної
множини $\{c_1, \dots, c_K\}$. Класифікатор навчають на **тренувальній множині**
розмічених прикладів $D = \{(x_i, y_i)\}_{i=1}^{N}$, а оцінюють на окремій
**тестовій множині** — щоб перевірити **узагальнення**, а не запам'ятовування.

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

Метод kNN міряє схожість об'єктів **відстанню** в просторі ознак. Для **числових**
ознак:

$$ \text{евклідова:}\quad d_2(x, y) = \sqrt{\sum_{i=1}^{m} (x_i - y_i)^2}, \qquad
\text{манхеттенська:}\quad d_1(x, y) = \sum_{i=1}^{m} |x_i - y_i|, $$

$$ \text{Мінковського порядку } p:\quad d_p(x, y) = \Big( \sum_{i=1}^{m} |x_i - y_i|^{p} \Big)^{1/p}
\quad(p=2 \to \text{евклідова},\ p=1 \to \text{манхеттенська}). $$

Для **категоріальних** ознак беруть **відстань Геммінга** — кількість позицій, у
яких вектори різняться.

> **Порада.** Щоб лише **порівняти** сусідів, корінь можна не брати: порядок за $d$
> і за $d^2 = \sum (x_i - y_i)^2$ однаковий. Це економить обчислення.

## 2.3 Алгоритм kNN

> **Означення (kNN).** Об'єкт відносять до **найпоширенішого** класу серед його $k$
> найближчих (за обраною відстанню) об'єктів навчальної вибірки.

```text
kNN(вибірка D = {(x_i, y_i)}, точка q, число k, відстань d):
  1. для кожного (x_i, y_i): r_i = d(q, x_i)
  2. упорядкувати об'єкти за зростанням r_i
  3. узяти перші k — найближчих сусідів
  4. підрахувати голоси кожного класу серед них
  5. повернути клас із найбільшою кількістю голосів
```

kNN — **ліниве** навчання: моделі не будує, вся робота — під час класифікації.

## 2.4 Вибір $k$

- **Мале $k$** (напр. $1$): чутливе до шуму й викидів, «рвані» межі, ризик
  **перенавчання**.
- **Велике $k$**: згладжує межі й придушує шум, але залучає далекі, несхожі об'єкти;
  за $k = N$ завжди повертає найбільший клас — **надмірне згладжування**.
- Для **двокласової** задачі беріть **непарне** $k$, щоб не було нічиєї; орієнтир
  $k \approx \sqrt{N}$.

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

Відстань додає квадрати різниць покоординатно, тож ознака з великим масштабом
**задавить** решту. Перед kNN числові ознаки нормалізують:

$$ \text{мінімакс:}\quad x' = \frac{x - x_{\min}}{x_{\max} - x_{\min}} \in [0, 1],
\qquad z\text{-стандартизація:}\quad z = \frac{x - \bar{x}}{s}. $$

## 2.6 Зважений kNN

Ближчі сусіди мають важити більше. У **зваженому** kNN голос сусіда на відстані $d$
береться з вагою $w = 1/d$ або $w = 1/d^2$; клас об'єкта — той, для якого **сума
ваг** сусідів найбільша. Це знімає нічиї й пом'якшує вибір $k$.

## 2.7 Оцінювання: матриця невідповідності та метрики

Для бінарної задачі (позитивний / негативний клас) кожен об'єкт потрапляє в одну з
чотирьох клітинок **матриці невідповідності** (confusion matrix):

| | Справжній: позитив | Справжній: негатив |
|---|:--:|:--:|
| **Передбачено: позитив** | $TP$ | $FP$ |
| **Передбачено: негатив** | $FN$ | $TN$ |

де $TP$ — істинно-позитивні, $TN$ — істинно-негативні, $FP$ — хибно-позитивні
(помилка I роду), $FN$ — хибно-негативні (помилка II роду). Метрики ($N = TP+TN+FP+FN$):

$$ \text{ACC} = \frac{TP+TN}{N}, \quad P = \frac{TP}{TP+FP}, \quad R = \frac{TP}{TP+FN},
\quad \text{TNR} = \frac{TN}{TN+FP}, \quad F_1 = \frac{2PR}{P+R}, $$

$$ \text{MCC} = \frac{TP\cdot TN - FP\cdot FN}{\sqrt{(TP+FP)(TP+FN)(TN+FP)(TN+FN)}}. $$

На **незбалансованих** класах правильність (ACC) оманлива — спирайтесь на $F_1$ і MCC.

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

**(а) kNN «руками».** Навчальна вибірка з $8$ точок двох класів «$+$» і «$-$» у
просторі двох ознак:

| Клас «$+$» | (4,5) | (6,6) | (3,3) | (1,4) |
|---|:--:|:--:|:--:|:--:|
| Клас «$-$» | (7,6) | (8,4) | (8,7) | (8,9) |

Класифікуємо точку $q = (5, 5)$ за евклідовою відстанню. Обчислимо $d^2$ і $d$ та
впорядкуємо:

| Сусід | Клас | $d^2$ | $d$ |
|---|:--:|:--:|:--:|
| (4,5) | $+$ | $1$ | $1{.}000$ |
| (6,6) | $+$ | $2$ | $1{.}414$ |
| (7,6) | $-$ | $5$ | $2{.}236$ |
| (3,3) | $+$ | $8$ | $2{.}828$ |
| (8,4) | $-$ | $10$ | $3{.}162$ |
| (8,7) | $-$ | $13$ | $3{.}606$ |
| (1,4) | $+$ | $17$ | $4{.}123$ |
| (8,9) | $-$ | $25$ | $5{.}000$ |

- **$k = 1$:** найближчий — $(4,5)$ класу «$+$». Отже, $\hat{y} = +$.
- **$k = 3$:** три найближчі — $(4,5)\,{+}$, $(6,6)\,{+}$, $(7,6)\,{-}$; голоси
  $2 : 1$ на користь «$+$». Отже, $\hat{y} = +$.

Обидва $k$ дають «$+$» — рішення **робасне** (не залежить від дрібного вибору $k$).

**(б) Метрики за матрицею невідповідності.** Нехай класифікатор на тестовій вибірці
з $N = 200$ об'єктів дав $TP = 50$, $FN = 20$, $FP = 10$, $TN = 120$:

$$ \text{ACC} = \frac{50 + 120}{200} = 0{.}85, \qquad
P = \frac{50}{50 + 10} = \frac{50}{60} \approx 0{.}833, \qquad
R = \frac{50}{50 + 20} = \frac{50}{70} \approx 0{.}714, $$

$$ \text{TNR} = \frac{120}{120 + 10} \approx 0{.}923, \qquad
F_1 = \frac{2 \cdot 0{.}833 \cdot 0{.}714}{0{.}833 + 0{.}714} \approx 0{.}769, $$

$$ \text{MCC} = \frac{50\cdot 120 - 10\cdot 20}{\sqrt{60\cdot 70\cdot 130\cdot 140}}
= \frac{6000 - 200}{\sqrt{76\,440\,000}} = \frac{5800}{8743{.}0} \approx 0{.}663. $$

Висока специфічність ($0{.}923$) і нижча чутливість ($0{.}714$) означають, що модель
радше **пропускає** позитиви ($FN = 20$), ніж здіймає хибні тривоги ($FP = 10$).

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

- Перед відстанями числові ознаки **нормалізуйте** (якщо масштаби різні).
- Для порівняння сусідів рахуйте $d^2$ — корінь брати не обов'язково.
- Беріть **непарне** $k$ у двокласовій задачі; за нічиєї — зважте голоси $1/d$.
- Якість оцінюйте на **тестовій** множині; на незбалансованих класах дивіться на
  $F_1$ і MCC, а не лише на правильність.