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

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

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$ найближчих (за обраною відстанню) об’єктів навчальної вибірки.

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$ — істинно-позитивні, $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$ точок двох класів «$+$» і «$-$» у просторі двох ознак:

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

• $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, а не лише на правильність.

Laboratory/Laboratory6/2method.md · 8.5 KB · updated 2026-08-04 23:15