# 3. Аудиторні задачі з розв'язаннями

Ці задачі розбирають **в аудиторії «руками»**. Вони показують ті самі обчислення,
які потім автоматизує домашня програма ([4task.md](4task.md)). Теорія й формули —
у [методичних вказівках](2method.md).

## Задача 1. Класифікація об'єкта методом kNN

**Дано** навчальну вибірку з $8$ об'єктів двох класів — **A** і **B** — у просторі
двох ознак $(x_1, x_2)$:

| Клас **A** | (1,3) | (2,2) | (3,4) | (2,4) |
|---|:--:|:--:|:--:|:--:|
| Клас **B** | (6,5) | (7,4) | (6,7) | (8,6) |

**Класифікувати** нову точку $q = (4, 4)$ методом kNN за евклідовою відстанню для
$k = 1$ та $k = 3$.

**Розв'язання.** Обчислимо квадрат відстані $d^2 = (x_1 - 4)^2 + (x_2 - 4)^2$ від
$q$ до кожної точки (корінь беремо лише наприкінці — порядок сусідів від нього не
залежить):

| Точка | Клас | $d^2$ | $d$ |
|---|:--:|:--:|:--:|
| (3,4) | A | $1 + 0 = 1$ | $1{.}000$ |
| (2,4) | A | $4 + 0 = 4$ | $2{.}000$ |
| (6,5) | B | $4 + 1 = 5$ | $2{.}236$ |
| (2,2) | A | $4 + 4 = 8$ | $2{.}828$ |
| (7,4) | B | $9 + 0 = 9$ | $3{.}000$ |
| (1,3) | A | $9 + 1 = 10$ | $3{.}162$ |
| (6,7) | B | $4 + 9 = 13$ | $3{.}606$ |
| (8,6) | B | $16 + 4 = 20$ | $4{.}472$ |

Упорядкувавши за зростанням $d$, голосуємо:

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

**Перевірка робасності ($k = 5$):** п'ять найближчих — $A, A, B, A, B$; голоси
$3 : 2$, знову **A**. Рішення стійке до вибору $k$.

**Відповідь:** для $k = 1$, $k = 3$ (і $k = 5$) точка $q = (4,4)$ належить класу
**A**.

![Класифікація точки q=(4,4) методом kNN: навчальні точки класів A і B, зелене коло k=1 та бірюзове коло k=3 навколо запиту; обидва k дають клас A](img/lab6_knn.png)

## Задача 2. Оцінка класифікатора за матрицею невідповідності

**Дано** результати класифікатора на тестовій вибірці з $N = 100$ об'єктів у вигляді
чисел матриці невідповідності: $TP = 30$, $FN = 10$, $FP = 15$, $TN = 45$.

**Знайти** правильність (accuracy), точність (precision), чутливість (recall),
специфічність, $F_1$-міру та коефіцієнт Меттьюза (MCC).

**Розв'язання.** Спершу випишемо матрицю (позитивний клас — той, що нас цікавить):

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

![Теплова карта матриці невідповідності задачі 2: TP=30 і TN=45 на діагоналі (правильні, бірюзові), FP=15 і FN=10 поза діагоналлю (помилки, помаранчеві)](img/lab6_confusion.png)

Правильність — частка правильних рішень (діагональ):

$$ \text{ACC} = \frac{TP + TN}{N} = \frac{30 + 45}{100} = 0{.}75. $$

Точність і чутливість:

$$ P = \frac{TP}{TP + FP} = \frac{30}{45} = \frac{2}{3} \approx 0{.}667, \qquad
R = \frac{TP}{TP + FN} = \frac{30}{40} = 0{.}75. $$

Специфічність:

$$ \text{TNR} = \frac{TN}{TN + FP} = \frac{45}{60} = 0{.}75. $$

$F_1$-міра (гармонійне середнє $P$ і $R$):

$$ F_1 = \frac{2 P R}{P + R} = \frac{2 \cdot \tfrac{2}{3} \cdot \tfrac{3}{4}}{\tfrac{2}{3} + \tfrac{3}{4}}
= \frac{1}{\tfrac{17}{12}} = \frac{12}{17} \approx 0{.}706. $$

Коефіцієнт Меттьюза:

$$ \text{MCC} = \frac{TP\cdot TN - FP\cdot FN}{\sqrt{(TP+FP)(TP+FN)(TN+FP)(TN+FN)}}
= \frac{30\cdot 45 - 15\cdot 10}{\sqrt{45\cdot 40\cdot 60\cdot 55}}. $$

Чисельник: $1350 - 150 = 1200$. Знаменник:
$\sqrt{45\cdot 40\cdot 60\cdot 55} = \sqrt{5\,940\,000} \approx 2437{.}2$. Отже,

$$ \text{MCC} = \frac{1200}{2437{.}2} \approx 0{.}492. $$

**Відповідь:** $\text{ACC} = 0{.}75$, $P \approx 0{.}667$, $R = 0{.}75$,
$\text{TNR} = 0{.}75$, $F_1 \approx 0{.}706$, $\text{MCC} \approx 0{.}492$. Метрики
помірні: класифікатор далекий і від ідеалу ($\text{MCC} = 1$), і від випадкового
вгадування ($\text{MCC} = 0$).

![Стовпчики метрик класифікатора задачі 2: ACC=0.750, P=0.667, R=0.750, TNR=0.750, F1=0.706, MCC=0.492](img/lab6_metrics.png)

## Задача 3. Функції відстані

**Дано** два об'єкти з числовими ознаками $x = (2, 2)$, $y = (7, 14)$ та два об'єкти
з категоріальними ознаками
$u = (\text{Сонячно}, \text{Спекотно}, \text{Висока}, \text{Слабкий})$,
$v = (\text{Дощ}, \text{Спекотно}, \text{Норма}, \text{Слабкий})$.

**Знайти** для числових об'єктів відстані — евклідову, манхеттенську, Мінковського
порядку $3$ та Чебишова; для категоріальних — відстань Геммінга.

**Розв'язання.** Покоординатні модулі різниць для $x, y$: $|2 - 7| = 5$ і
$|2 - 14| = 12$. Тоді

$$ d_2 = \sqrt{5^2 + 12^2} = \sqrt{169} = 13, \qquad d_1 = 5 + 12 = 17, $$

$$ d_3 = (5^3 + 12^3)^{1/3} = (125 + 1728)^{1/3} = 1853^{1/3} \approx 12{.}283, \qquad
d_\infty = \max(5, 12) = 12. $$

Зі зростанням порядку $p$ відстань спадає від $17$ (манхеттенська) до $12$
(Чебишова), бо все більшу вагу перебирає найбільша різниця ($12$).

Для категоріальних об'єктів порівнюємо позиції: $1$-ша різна (Сонячно / Дощ),
$2$-га однакова (Спекотно), $3$-тя різна (Висока / Норма), $4$-та однакова
(Слабкий). Різних позицій — **дві**, тож відстань Геммінга

$$ d_H(u, v) = 2. $$

**Відповідь:** $d_2 = 13$, $d_1 = 17$, $d_3 \approx 12{.}283$, $d_\infty = 12$;
$d_H = 2$.

> **Зв'язок із домашнім завданням.** Саме ці кроки — обчислити відстані від
> об'єкта до всіх навчальних точок, відібрати $k$ найближчих і проголосувати, а
> потім (на високому рівні) звести результати на тестовій вибірці в матрицю
> невідповідності й порахувати метрики — виконуватиме ваша програма
> ([4task.md](4task.md)). Задача 1 — зручний **тест**: подайте ці $8$ точок як
> навчальну вибірку, а $q = (4,4)$ — як об'єкт для класифікації, і переконайтесь, що
> програма повертає клас **A** для $k = 1$ і $k = 3$.