Лекція 6. Класифікація. Метод $k$ найближчих сусідів (kNN) #

Огляд #

Цією лекцією починається Модуль 3 — методи класифікації. Досі ми даними описували (Модуль 1) та робили статистичні висновки про них (Модуль 2); у Лекції 5 регресія навчилася передбачати число за іншими числами. Тепер ми ставимо іншу задачу прогнозу: за ознаками об’єкта передбачити не число, а категорію — до якого з наперед відомих класів об’єкт належить. Лист прийшов — це спам чи ні? Пухлина доброякісна чи злоякісна? Транзакція шахрайська чи законна? Усе це — класифікація.

У розділі ми спершу вводимо саму задачу класифікації, її правила якості (повнота й чистота), місце класифікації в машинному навчанні та типи задач. Потім розбираємо, як оцінювати класифікатор: матрицю невідповідності (confusion matrix) і похідні від неї метрики — правильність, точність, чутливість, специфічність, $F_1$-міру та коефіцієнт кореляції Меттьюза. Друга половина лекції — перший конкретний метод: $k$ найближчих сусідів (англ. $k$-nearest neighbours, kNN), його алгоритм, функції відстані, роль нормалізації ознак, вплив параметра $k$ і зважений варіант. У Лекції 7 ми перейдемо до методів, що будують явну модель (дерева рішень), а поки що метод kNN покаже задачу класифікації в найпрозорішому вигляді — без навчання моделі взагалі.

Практичний бік. Класифікувати об’єкт методом kNN «руками» й обчислити метрики за матрицею невідповідності ви навчитесь в аудиторній частині, а програму kNN, що читає навчальну вибірку з CSV, напишете в Лабораторній роботі 6.

6.1 Класифікація як задача #

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

Уведемо робочі позначення. Об’єкт описують вектором ознак (предикторів, атрибутів) $x = (x_1, x_2, \dots, x_m)$; кожна ознака — числова або категоріальна. Клас (мітка, цільова ознака) $y$ набуває значень зі скінченної множини $\{c_1, \dots, c_K\}$. Класифікатор — це функція $\hat{y} = f(x)$, що за вектором ознак повертає передбачений клас.

Ключова відмінність від регресії (Лекція 5): там ціль $y$ — неперервне число, тут — категорія. Тому й міряють якість інакше: не середньоквадратичною похибкою, а часткою правильно віднесених об’єктів (§6.8–6.9).

Приклад 6.1. Банк класифікує заявників на кредит за ознаками $x = (\text{вік},\ \text{дохід},\ \text{стаж})$ у два класи $y \in \{\text{надати}, \text{відмовити}\}$. Це задача класифікації: ціль категоріальна.

6.2 Правила класифікації: повнота і чистота #

Будь-яке розбиття об’єктів на класи оцінюють двома взаємодоповняльними критеріями.

Означення (повнота, чистота). Повнота (англ. completeness) вимагає, щоб усі об’єкти, які насправді належать до одного класу, потрапляли в одну групу — клас охоплено повністю, без «загублених» об’єктів. Чистота (англ. purity) вимагає, щоб кожна група містила об’єкти лише одного класу — без домішок чужих об’єктів.

Ці дві вимоги перебувають у природному напруженні. Якщо оголосити всі об’єкти одним великим класом, повнота ідеальна (жоден об’єкт не загублено), але чистота жахлива (група змішана). Якщо ж кожен об’єкт зробити окремою групою, чистота ідеальна, зате повнота нульова (об’єкти одного класу розкидано). Гарний класифікатор балансує повноту й чистоту; кількісно це напруження виражають метрики чутливості та точності (§6.9), а в деревах рішень (Лекція 7) чистоту вузла міряють ентропією та індексом Джині.

6.3 Машинне навчання та його типи #

Класифікатор рідко програмують правилами вручну — його навчають на прикладах. Це підгалузь машинного навчання.

Означення (машинне навчання). Машинне навчання (англ. machine learning) — підгалузь штучного інтелекту, яка застосовує статистичні прийоми, щоб надати комп’ютерам здатність «навчатися» (поступово покращувати продуктивність у вирішенні задачі) на даних, замість того щоб бути запрограмованими явно на кожен випадок.

За тим, що саме відомо про дані під час навчання, розрізняють типи навчання:

• Навчання з учителем (англ. supervised learning) — у навчальних прикладах відома правильна відповідь (мітка класу). Модель учиться відтворювати відповідність «ознаки → клас». Класифікація (ця лекція) і регресія (Лекція 5) — саме такі задачі.
• Навчання без учителя (англ. unsupervised learning) — міток немає; модель сама шукає структуру в даних, групуючи схожі об’єкти. Це задача кластеризації (Модуль 4, Лекція 9).

Типова помилка (класифікація проти кластеризації). І там, і там об’єкти «розкладають по групах», але класифікація навчається на готових мітках і приписує об’єкт до наперед відомого класу, а кластеризація мітками не користується й формує групи сама. Плутати їх — усе одно що плутати «навчання з учителем» із «без учителя».

6.4 Типи задач класифікації #

Задачі класифікації класифікують і самі — за кількома незалежними ознаками.

Ці ознаки поєднуються: kNN — це багатовимірна класифікація, яку легко зробити і детерміністичною (мажоритарне голосування, §6.10), і ймовірнісною (частка сусідів кожного класу як оцінка ймовірності). Наступна Лекція 7 присвячена ординарним методам, а Лекція 8 — ймовірнісному (баєсовому) класифікатору.

6.5 Тренувальна й тестова множини #

Модель, навчену на певних даних, не можна чесно оцінювати на тих самих даних: вона могла їх просто «запам’ятати». Тому наявні розмічені дані ділять.

Означення (тренувальна й тестова множини). Тренувальну (навчальну) множину модель бачить під час навчання й на ній підбирає свої параметри. Тестову множину приховують до кінця й використовують один раз — щоб оцінити якість на нових, небачених об’єктах.

Мета — не мінімальна похибка на навчальних даних, а узагальнення (англ. generalization): добра робота на нових об’єктах. Модель, яка ідеально відтворює навчальні дані, але провалюється на тестових, перенавчена (англ. overfitting) — вона вловила випадковий шум замість закономірності. Типовий поділ — $70$–$80\,\%$ на навчання, решта на тест; для надійнішої оцінки застосовують перехресну перевірку (англ. cross-validation), коли роль тесту по черзі грають різні частини даних.

6.6 Характеристики методів класифікації #

Методи порівнюють не лише за точністю, а й за практичними властивостями.

• Швидкість — час навчання та час класифікації одного об’єкта. У kNN навчання миттєве (дані просто запам’ятовуються), зате класифікація повільна: щоб віднести об’єкт, треба обчислити відстань до всіх навчальних точок.
• Робасність (стійкість) — здатність давати правильний результат за наявності шуму й викидів у даних.
• Інтерпретованість — наскільки легко людині зрозуміти, чому модель ухвалила саме таке рішення. Дерева рішень прозорі, нейронні мережі — ні.
• Надійність — стабільність якості на різних наборах даних, відсутність різких провалів.

6.7 Огляд методів класифікації #

Класифікаторів багато; далі в курсі ми розберемо основні. Оглядовий перелік:

• Метод $k$ найближчих сусідів (kNN) — ця лекція;
• дерева рішень та випадковий ліс (ансамбль дерев) — Лекція 7;
• баєсівська (ймовірнісна) класифікація — Лекція 8;
• логістична регресія — лінійна межа, що видає ймовірність класу;
• метод опорних векторів (англ. SVM) — максимізує «зазор» між класами;
• лінійний дискримінантний аналіз (LDA);
• штучні нейронні мережі — гнучкі нелінійні моделі.

Ми починаємо з kNN, бо він не будує моделі взагалі: у ньому задача класифікації видно в чистому вигляді — «схожий об’єкт має схожий клас».

6.8 Матриця невідповідності #

Перш ніж вивчати конкретний метод, домовимося, як міряти його якість. Для бінарної класифікації один клас називають позитивним (той, що нас цікавить, — напр. «хворий», «спам»), інший — негативним. Порівнюючи передбачення з істиною, кожен об’єкт потрапляє в одну з чотирьох клітинок.

Означення (матриця невідповідності). Матриця невідповідності (також матриця помилок / плутанини, англ. confusion matrix) — таблиця $2\times 2$, що зіставляє справжній клас об’єктів із передбаченим:

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

Розшифровка чотирьох чисел:

• $TP$ (true positive) — позитивні об’єкти, правильно названі позитивними;
• $TN$ (true negative) — негативні, правильно названі негативними;
• $FP$ (false positive) — негативні, помилково названі позитивними (помилка I роду, «хибна тривога»);
• $FN$ (false negative) — позитивні, помилково названі негативними (помилка II роду, «пропуск»).

Діагональ $TP, TN$ — правильні рішення; поза діагоналлю $FP, FN$ — два різні за змістом типи помилок. Розрізняти їх критично: для медичного тесту пропуск хвороби ($FN$) значно небезпечніший за хибну тривогу ($FP$).

6.9 Метрики якості класифікації #

З чотирьох чисел матриці утворюють кілька метрик; усього об’єктів $N = TP + TN + FP + FN$.

Означення (метрики).

$$\text{правильність (accuracy):}\quad \text{ACC} = \frac{TP + TN}{TP + TN + FP + FN},$$

$$\text{точність (precision, PPV):}\quad P = \frac{TP}{TP + FP}, \qquad \text{чутливість/повнота (recall, TPR):}\quad R = \frac{TP}{TP + FN},$$

$$\text{специфічність (TNR):}\quad \text{TNR} = \frac{TN}{TN + FP}, \qquad \text{значущість негативного (NPV):}\quad \text{NPV} = \frac{TN}{TN + FN}.$$

Змістовно: точність відповідає на запитання «серед названих позитивними — скільки справді позитивні?», а чутливість — «серед справді позитивних — скільки ми вловили?». Вони в напруженні (як повнота й чистота §6.2), тож їх зводять в одну величину — гармонійне середнє:

Означення ($F_1$-міра).

$$F_1 = \frac{2 P R}{P + R}.$$

$F_1$ близька до $1$, лише коли обидві — і точність, і чутливість — високі; провал будь-якої тягне $F_1$ вниз.

Правильність (accuracy) сама по собі оманлива на незбалансованих класах.

Типова помилка (парадокс правильності). Нехай серед $1000$ пацієнтів лише $10$ хворих. Класифікатор, що завжди каже «здоровий», має $TP=0$, $FN=10$, $FP=0$, $TN=990$, тобто $\text{ACC} = 990/1000 = 0{.}99$ — «$99\,\%$ правильних»! Але його чутливість $R = 0/10 = 0$: він не виявив жодного хворого. Тому на рідкісний позитивний клас завжди дивіться на чутливість, точність і $F_1$, а не лише на ACC.

Єдина метрика, збалансована навіть за перекосу класів, — коефіцієнт кореляції Меттьюза.

Означення (коефіцієнт Меттьюза, MCC).

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

$\text{MCC} \in [-1, 1]$: $+1$ — ідеальне передбачення, $0$ — рівень випадкового вгадування, $-1$ — цілковита протилежність.

Приклад 6.2 (усі метрики за матрицею). Класифікатор дав матрицю $TP = 45$, $FN = 5$, $FP = 10$, $TN = 40$ ($N = 100$):

$$\text{ACC} = \frac{45 + 40}{100} = 0{.}85, \qquad P = \frac{45}{45 + 10} = \frac{45}{55} \approx 0{.}818, \qquad R = \frac{45}{45 + 5} = \frac{45}{50} = 0{.}90,$$

$$\text{TNR} = \frac{40}{40 + 10} = 0{.}80, \qquad F_1 = \frac{2 \cdot 0{.}818 \cdot 0{.}90}{0{.}818 + 0{.}90} \approx 0{.}857.$$

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

$$\text{MCC} = \frac{45\cdot 40 - 10\cdot 5}{\sqrt{55\cdot 50\cdot 50\cdot 45}} = \frac{1800 - 50}{\sqrt{6\,187\,500}} = \frac{1750}{2487{.}5} \approx 0{.}704.$$

Модель добре вловлює позитиви ($R = 0{.}90$), а помірна точність ($P \approx 0{.}82$) означає, що частина тривог хибні ($FP = 10$).

6.10 Метод $k$ найближчих сусідів: ідея #

Найпростіший принцип класифікації спирається на здоровий глузд: схожі об’єкти належать до схожих класів. Схожість вимірюють відстанню в просторі ознак (§6.12).

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

kNN — приклад лінивого навчання (англ. lazy learning): він не будує моделі. «Навчання» зводиться до запам’ятовування навчальної вибірки, а вся робота відбувається під час класифікації — тоді й обчислюють відстані до всіх точок. Через це kNN простий і напрочуд ефективний на малих даних, але повільний на великих (§6.6) і чутливий до масштабу ознак (§6.13).

Приклад 6.3 (kNN «руками»). Навчальна вибірка з $8$ точок двох класів — $\circ$ (клас 1) і $\bullet$ (клас 2) — у просторі двох нормованих ознак:

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

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

Відповіді різні! Точка $(5,4)$ — поодинокий $\circ$ серед $\bullet$ (шум або викид); при $k=1$ він визначає рішення сам, а при $k=3$ його «переголошують» два сусіди-$\bullet$. Це наочно показує, чому вибір $k$ важливий (§6.14).

6.11 Алгоритм kNN #

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

Часова складність класифікації одного об’єкта — $O(N\,m)$ на обчислення відстаней плюс $O(N \log N)$ (чи $O(N k)$) на відбір $k$ найменших, де $N$ — розмір вибірки, $m$ — число ознак. Для великих $N$ застосовують просторові структури (напр., $k$-d-дерева), що прискорюють пошук сусідів.

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

«Найближчий» означає «найближчий за деякою метрикою». Вибір відстані — частина налаштування kNN.

Для числових ознак ($x, y \in \mathbb{R}^m$):

Означення (метрики Мінковського).

$$\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}.$$

Евклідова — це $p = 2$, манхеттенська — $p = 1$; за $p \to \infty$ дістають відстань Чебишова $d_\infty = \max_i |x_i - y_i|$.

Для категоріальних ознак різниці не означено; тоді беруть відстань Геммінга.

Означення (відстань Геммінга). Для двох векторів категоріальних ознак відстань Геммінга дорівнює кількості позицій, у яких вони різняться.

Приклад 6.4 (порівняння метрик). Для $x = (1, 2)$, $y = (4, 6)$ різниці координат — $|{-3}| = 3$ і $|{-4}| = 4$:

$$d_2 = \sqrt{3^2 + 4^2} = \sqrt{25} = 5, \qquad d_1 = 3 + 4 = 7,$$

$$d_3 = (3^3 + 4^3)^{1/3} = 91^{1/3} \approx 4{.}498, \qquad d_\infty = \max(3, 4) = 4.$$

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

Приклад 6.5 (Геммінг). Об’єкти $(\text{Ч}, \text{Високий}, \text{Так})$ і $(\text{Ж}, \text{Високий}, \text{Ні})$ різняться у двох позиціях (стать і третя ознака), тож відстань Геммінга $= 2$.

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

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

Приклад 6.6 (масштаб спотворює сусідство). Клієнтів описують ознаками (вік, дохід): $A = (25,\ 40\,000)$, $B = (30,\ 45\,000)$, $C = (45,\ 41\,000)$. Хто ближчий до $A$? За «сирою» евклідовою відстанню

$$d(A, B) = \sqrt{5^2 + 5000^2} \approx 5000, \qquad d(A, C) = \sqrt{20^2 + 1000^2} \approx 1000,$$

тобто найближчий до $A$ — $C$: дохід (тисячі) повністю заглушив вік (десятки). Але за віком $A$ і $B$ майже однакові, а $C$ старший на $20$ років — інтуїтивно ближчим має бути $B$. Вину несе масштаб, і його усуває нормалізація.

Означення (нормалізація ознак). Мінімаксна нормалізація стискає ознаку в $[0, 1]$:

$$x' = \frac{x - x_{\min}}{x_{\max} - x_{\min}},$$

а $z$-стандартизація зводить її до нульового середнього й одиничного СКВ:

$$z = \frac{x - \bar{x}}{s}.$$

Візьмемо діапазони вік $[20, 60]$ (розмах $40$) і дохід $[20\,000, 80\,000]$ (розмах $60\,000$). Після мінімаксної нормалізації $A' = (0{.}125,\ 0{.}333)$, $B' = (0{.}250,\ 0{.}417)$, $C' = (0{.}625,\ 0{.}350)$, і тепер

$$d(A', B') \approx 0{.}150, \qquad d(A', C') \approx 0{.}500.$$

Найближчим став $B$ — відстань перестала визначатися лише доходом. Висновок: перед kNN числові ознаки майже завжди нормалізують; інакше метод фактично використовує одну «найбільшу» ознаку.

6.14 Вплив значення $k$ #

Параметр $k$ керує гладкістю меж між класами.

• Малий $k$ (напр. $k = 1$) робить рішення чутливим до кожної точки, зокрема до шуму й викидів: одна помилкова мітка поряд — і об’єкт класифіковано хибно (див. Приклад 6.3). Межі класів «рвані», є ризик перенавчання.
• Великий $k$ усереднює по багатьох сусідах і згладжує межі, придушуючи шум. Та якщо $k$ завелике, у голосуванні починають брати участь далекі, уже несхожі об’єкти; у крайньому разі $k = N$ завжди повертає найбільший клас усієї вибірки — надмірне згладжування (недонавчання).

Оптимальне $k$ шукають експериментально — за якістю на тестовій множині (§6.5). Практичне правило-орієнтир $k \approx \sqrt{N}$.

Типова помилка (парне $k$ у бінарній задачі). За парного $k$ можливий нічийний голос ($k/2$ проти $k/2$), який доведеться розв’язувати штучно. Для двокласової задачі беріть непарне $k$ ($1, 3, 5, \dots$) — тоді нічиєї між двома класами не буде.

6.15 Зважений kNN #

У звичайному голосуванні всі $k$ сусідів рівноправні, хоч один із них може бути впритул, а інший — на самому краю околу. Логічно дати ближчим сусідам більшу вагу.

Означення (зважений kNN). У зваженому kNN голос сусіда на відстані $d$ береться з вагою $w = \dfrac{1}{d}$ або $w = \dfrac{1}{d^{2}}$ (за $d = 0$ — нескінченна вага, тобто збіг із навчальною точкою). Клас об’єкта — той, для якого сума ваг сусідів найбільша.

Зважування, зокрема, розв’язує нічиї й пом’якшує вимогу до вибору $k$.

Приклад 6.7 (зважений голос знімає нічию). Нехай серед $k = 4$ сусідів два — класу A на відстанях $\{1,\ 4\}$ і два — класу B на відстанях $\{2,\ 3\}$. Звичайне голосування дає нічию $2 : 2$. Зважимо:

$$w_A = \frac{1}{1} + \frac{1}{4} = 1{.}25, \quad w_B = \frac{1}{2} + \frac{1}{3} \approx 0{.}833 \ \Rightarrow\ \text{клас A};$$

$$\text{з вагами } 1/d^2:\quad w_A = 1 + \frac{1}{16} = 1{.}0625, \quad w_B = \frac{1}{4} + \frac{1}{9} \approx 0{.}361 \ \Rightarrow\ \text{клас A}.$$

Обидві схеми ваг віддають об’єкт класу A — завдяки дуже близькому сусіду на відстані $1$, який в незваженому голосуванні важив стільки ж, скільки далекий.

Застосування в аналітиці даних #

• Рекомендаційні системи. «Користувачі, схожі на вас (найближчі сусіди), вподобали…» — це kNN у просторі вподобань.
• Медична діагностика. Класифікація за схожістю на раніше діагностованих пацієнтів; тут матриця невідповідності й чутливість особливо важливі (ціна пропуску $FN$ висока).
• Оцінювання будь-якого класифікатора. Матриця невідповідності та метрики (ACC, $P$, $R$, $F_1$, MCC) — універсальний інструмент порівняння моделей; ми застосовуватимемо їх до дерев (Лекція 7) і баєсового класифікатора (Лекція 8).
• Виявлення аномалій. Об’єкт, у якого навіть найближчі сусіди далеко, ймовірно, є викидом.

Підсумок #

• Класифікація — навчання з учителем: за ознаками $x$ передбачити категорію $y$ з наперед відомої множини класів. Якість грунтового розбиття описують повнотою (охопити клас цілком) і чистотою (без домішок).
• Типи задач: бінарна / мультиномінальна; одно- / багатовимірна; детерміністична / ймовірнісна. Дані ділять на тренувальну й тестову множини, щоб оцінити узагальнення й уникнути перенавчання.
• Матриця невідповідності ($TP, TN, FP, FN$) породжує метрики: правильність $\text{ACC}$, точність $P = TP/(TP+FP)$, чутливість $R = TP/(TP+FN)$, специфічність $\text{TNR}$, $F_1 = 2PR/(P+R)$ і MCC. На незбалансованих класах ACC оманлива — дивіться на $F_1$ та MCC.
• kNN відносить об’єкт до найпоширенішого класу серед $k$ найближчих сусідів; це ліниве навчання — моделі не будує, зате повільне на великих даних.
• Відстань: евклідова, манхеттенська, Мінковського (числові), Геммінга (категоріальні). Числові ознаки перед kNN обов’язково нормалізують, інакше домінує ознака з найбільшим масштабом.
• Малий $k$ — чутливість до шуму (перенавчання); великий $k$ — надмірне згладжування. Для бінарної задачі беріть непарне $k$. Зважений kNN (вага $1/d$ чи $1/d^2$) підсилює ближчих сусідів і знімає нічиї.

Вправи #

Для розігріву #

1. Чим задача класифікації відрізняється від задачі регресії (Лекція 5) і від задачі кластеризації (Лекція 9)? Наведіть по прикладу.
2. Поясніть на словах різницю між повнотою і чистотою класифікації та чому вони перебувають у напруженні.
3. Дано $TP = 80$, $TN = 90$, $FP = 10$, $FN = 20$. Обчисліть правильність, точність, чутливість і специфічність.
4. Чому для бінарної класифікації методом kNN радять брати непарне $k$?

Стандартні #

5. Для точок $x = (2, 3)$ і $y = (5, 7)$ обчисліть відстані: евклідову, манхеттенську, Мінковського порядку $3$ та Чебишова.
6. Навчальна вибірка: клас A — $(1,2), (2,2), (2,3)$; клас B — $(6,5), (7,5), (6,6)$. Класифікуйте точку $q = (4, 4)$ методом kNN за евклідовою відстанню для $k = 1$ і $k = 3$. Чи збігаються відповіді?
7. Ознаки об’єктів — (кількість кімнат $\in [1,6]$, площа $\in [30, 200]$ м²). Поясніть, чому без нормалізації kNN фактично ігноруватиме кількість кімнат, і нормалізуйте мінімаксно об’єкт $(3, 80)$.
8. За матрицею $TP = 45$, $FN = 5$, $FP = 10$, $TN = 40$ (Приклад 6.2) обчисліть $F_1$ і NPV; поясніть, що означає кожне число.

Підвищеної складності #

9. Побудуйте приклад незбалансованої вибірки, на якій правильність (accuracy) $\ge 0{.}95$, а $F_1$-міра $\le 0{.}1$. Який висновок про вибір метрики це ілюструє?
10. Доведіть, що для будь-якої матриці невідповідності $F_1$-міра не перевищує правильності, коли класи збалансовані; за яких умов $F_1 = \text{ACC}$?
11. У Прикладі 6.3 застосуйте зважений kNN з вагою $1/d^2$ при $k = 3$ до точки $q = (5, 5)$. Який клас переможе тепер і чому він може відрізнятися від незваженого голосування? (Підказка: найближчий сусід на відстані $1$ має вагу $1$.)
12. Поясніть, як зробити kNN ймовірнісним класифікатором (§6.4): що взяти за оцінку $P(y = c \mid x)$? Як на цю оцінку впливає збільшення $k$?

Lectures/DA-L06.md · 40.1 KB · updated 2026-08-05 09:40