# Лекція 6. Класифікація. Метод $k$ найближчих сусідів (kNN) ## Огляд Цією лекцією починається **Модуль 3 — методи класифікації**. Досі ми даними **описували** (Модуль 1) та робили статистичні **висновки** про них (Модуль 2); у [Лекції 5](DA-L05.md) регресія навчилася **передбачати число** за іншими числами. Тепер ми ставимо іншу задачу прогнозу: за ознаками об'єкта передбачити не число, а **категорію** — до якого з наперед відомих класів об'єкт належить. Лист прийшов — це спам чи ні? Пухлина доброякісна чи злоякісна? Транзакція шахрайська чи законна? Усе це — **класифікація**. У розділі ми спершу вводимо саму задачу класифікації, її **правила якості** (повнота й чистота), місце класифікації в **машинному навчанні** та типи задач. Потім розбираємо, як **оцінювати** класифікатор: **матрицю невідповідності** (confusion matrix) і похідні від неї метрики — правильність, точність, чутливість, специфічність, $F_1$-міру та коефіцієнт кореляції Меттьюза. Друга половина лекції — перший конкретний метод: **$k$ найближчих сусідів** (англ. *$k$-nearest neighbours, kNN*), його алгоритм, функції відстані, роль нормалізації ознак, вплив параметра $k$ і зважений варіант. У [Лекції 7](DA-L07.md) ми перейдемо до методів, що **будують явну модель** (дерева рішень), а поки що метод kNN покаже задачу класифікації в найпрозорішому вигляді — без навчання моделі взагалі. > **Практичний бік.** Класифікувати об'єкт методом kNN «руками» й обчислити > метрики за матрицею невідповідності ви навчитесь в аудиторній частині, а > **програму** kNN, що читає навчальну вибірку з CSV, напишете в > [Лабораторній роботі 6](../Laboratory/Laboratory6/main.md). --- ## 6.1 Класифікація як задача > **Означення (класифікація).** **Класифікація** — це процес упорядкування за > певним критерієм об'єктів, які мають ознаки, задля визначення **подібності або > відмінності** між ними. У задачах аналітики це означає побудову правила, яке > кожному об'єкту за значеннями його ознак приписує один із наперед заданих > **класів**. Уведемо робочі позначення. Об'єкт описують вектором **ознак** (предикторів, атрибутів) $x = (x_1, x_2, \dots, x_m)$; кожна ознака — числова або категоріальна. **Клас** (мітка, цільова ознака) $y$ набуває значень зі скінченної множини $\{c_1, \dots, c_K\}$. Класифікатор — це функція $\hat{y} = f(x)$, що за вектором ознак повертає передбачений клас. Ключова відмінність від регресії ([Лекція 5](DA-L05.md)): там ціль $y$ — **неперервне число**, тут — **категорія**. Тому й міряють якість інакше: не середньоквадратичною похибкою, а часткою правильно віднесених об'єктів (§6.8–6.9). **Приклад 6.1.** Банк класифікує заявників на кредит за ознаками $x = (\text{вік},\ \text{дохід},\ \text{стаж})$ у два класи $y \in \{\text{надати}, \text{відмовити}\}$. Це задача класифікації: ціль категоріальна. --- ## 6.2 Правила класифікації: повнота і чистота Будь-яке розбиття об'єктів на класи оцінюють двома взаємодоповняльними критеріями. > **Означення (повнота, чистота).** > **Повнота** (англ. *completeness*) вимагає, щоб **усі** об'єкти, які насправді > належать до одного класу, потрапляли в **одну** групу — клас охоплено повністю, > без «загублених» об'єктів. > **Чистота** (англ. *purity*) вимагає, щоб кожна група містила об'єкти **лише > одного** класу — без домішок чужих об'єктів. Ці дві вимоги перебувають у **природному напруженні**. Якщо оголосити всі об'єкти одним великим класом, повнота ідеальна (жоден об'єкт не загублено), але чистота жахлива (група змішана). Якщо ж кожен об'єкт зробити окремою групою, чистота ідеальна, зате повнота нульова (об'єкти одного класу розкидано). Гарний класифікатор **балансує** повноту й чистоту; кількісно це напруження виражають метрики чутливості та точності (§6.9), а в деревах рішень ([Лекція 7](DA-L07.md)) чистоту вузла міряють ентропією та індексом Джині. --- ## 6.3 Машинне навчання та його типи Класифікатор рідко програмують правилами вручну — його **навчають** на прикладах. Це підгалузь машинного навчання. > **Означення (машинне навчання).** **Машинне навчання** (англ. *machine learning*) > — підгалузь штучного інтелекту, яка застосовує статистичні прийоми, щоб надати > комп'ютерам здатність «навчатися» (поступово покращувати продуктивність у > вирішенні задачі) на **даних**, замість того щоб бути запрограмованими явно на > кожен випадок. За тим, **що** саме відомо про дані під час навчання, розрізняють типи навчання: - **Навчання з учителем** (англ. *supervised learning*) — у навчальних прикладах відома **правильна відповідь** (мітка класу). Модель учиться відтворювати відповідність «ознаки → клас». Класифікація (ця лекція) і регресія (Лекція 5) — саме такі задачі. - **Навчання без учителя** (англ. *unsupervised learning*) — міток **немає**; модель сама шукає структуру в даних, групуючи схожі об'єкти. Це задача **кластеризації** (Модуль 4, [Лекція 9](DA-L09.md)). > **Типова помилка (класифікація проти кластеризації).** І там, і там об'єкти > «розкладають по групах», але класифікація навчається на **готових мітках** і > приписує об'єкт до **наперед відомого** класу, а кластеризація мітками не > користується й формує групи **сама**. Плутати їх — усе одно що плутати «навчання > з учителем» із «без учителя». --- ## 6.4 Типи задач класифікації Задачі класифікації класифікують і самі — за кількома незалежними ознаками. | Ознака поділу | Тип | Пояснення | |---|---|---| | Кількість класів | **бінарна** | рівно два класи ($K=2$): спам / не спам | | | **мультиномінальна** (багатокласова) | три й більше класів: цифри $0$–$9$ | | Кількість ознак | **одновимірна** | рішення за **одним** предиктором (див. OneR, [Лекція 7](DA-L07.md)) | | | **багатовимірна** | рішення за вектором із кількох ознак (kNN — саме така) | | Характер відповіді | **ординарна (детерміністична)** | видає **одну** мітку класу | | | **ймовірнісна** | видає **ймовірності** належності до кожного класу | Ці ознаки поєднуються: kNN — це багатовимірна класифікація, яку легко зробити і детерміністичною (мажоритарне голосування, §6.10), і ймовірнісною (частка сусідів кожного класу як оцінка ймовірності). Наступна [Лекція 7](DA-L07.md) присвячена ординарним методам, а [Лекція 8](DA-L08.md) — ймовірнісному (баєсовому) класифікатору. --- ## 6.5 Тренувальна й тестова множини Модель, навчену на певних даних, не можна чесно оцінювати **на тих самих** даних: вона могла їх просто «запам'ятати». Тому наявні розмічені дані **ділять**. > **Означення (тренувальна й тестова множини).** **Тренувальну (навчальну) множину** > модель бачить під час навчання й на ній підбирає свої параметри. **Тестову > множину** приховують до кінця й використовують **один раз** — щоб оцінити якість > на **нових**, небачених об'єктах. Мета — не мінімальна похибка на навчальних даних, а **узагальнення** (англ. *generalization*): добра робота на нових об'єктах. Модель, яка ідеально відтворює навчальні дані, але провалюється на тестових, **перенавчена** (англ. *overfitting*) — вона вловила випадковий шум замість закономірності. Типовий поділ — $70$–$80\,\%$ на навчання, решта на тест; для надійнішої оцінки застосовують **перехресну перевірку** (англ. *cross-validation*), коли роль тесту по черзі грають різні частини даних. --- ## 6.6 Характеристики методів класифікації Методи порівнюють не лише за точністю, а й за практичними властивостями. - **Швидкість** — час навчання та час класифікації одного об'єкта. У kNN навчання миттєве (дані просто запам'ятовуються), зате **класифікація повільна**: щоб віднести об'єкт, треба обчислити відстань до **всіх** навчальних точок. - **Робасність** (стійкість) — здатність давати правильний результат за наявності **шуму** й **викидів** у даних. - **Інтерпретованість** — наскільки легко людині зрозуміти, **чому** модель ухвалила саме таке рішення. Дерева рішень прозорі, нейронні мережі — ні. - **Надійність** — стабільність якості на різних наборах даних, відсутність різких провалів. --- ## 6.7 Огляд методів класифікації Класифікаторів багато; далі в курсі ми розберемо основні. Оглядовий перелік: - **Метод $k$ найближчих сусідів** (kNN) — ця лекція; - **дерева рішень** та **випадковий ліс** (ансамбль дерев) — [Лекція 7](DA-L07.md); - **баєсівська (ймовірнісна) класифікація** — [Лекція 8](DA-L08.md); - **логістична регресія** — лінійна межа, що видає ймовірність класу; - **метод опорних векторів** (англ. *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$). ![Матриця невідповідності 2×2: діагональ TP і TN — правильні рішення (бірюзові клітинки), поза діагоналлю FP і FN — два різні типи помилок (помаранчеві клітинки)](img/l06_confusion.png) --- ## 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.2: правильність 0.850, точність 0.818, чутливість 0.900, специфічність 0.800, F1-міра 0.857](img/l06_metrics.png) --- ## 6.10 Метод $k$ найближчих сусідів: ідея Найпростіший принцип класифікації спирається на здоровий глузд: **схожі об'єкти належать до схожих класів**. Схожість вимірюють **відстанню** в просторі ознак (§6.12). > **Означення (kNN).** У методі **$k$ найближчих сусідів** об'єкт відносять до того > класу, який є **найпоширенішим** серед його $k$ найближчих (за обраною відстанню) > об'єктів навчальної вибірки. kNN — приклад **лінивого навчання** (англ. *lazy learning*): він **не будує моделі**. «Навчання» зводиться до запам'ятовування навчальної вибірки, а вся робота відбувається під час класифікації — тоді й обчислюють відстані до всіх точок. Через це kNN простий і напрочуд ефективний на малих даних, але **повільний** на великих (§6.6) і чутливий до масштабу ознак (§6.13). **Приклад 6.3 (kNN «руками»).** Навчальна вибірка з $8$ точок двох класів — $\circ$ (клас 1) і $\bullet$ (клас 2) — у просторі двох нормованих ознак: | Клас $\circ$ | (1,1) | (2,1) | (2,2) | (5,4) | |---|:--:|:--:|:--:|:--:| | Клас $\bullet$ | (6,6) | (6,7) | (7,7) | (8,6) | Класифікуємо нову точку $q = (5, 5)$. Обчислимо **евклідові** відстані $d(q, x_i)$ й упорядкуємо їх: | Сусід | Клас | $d(q, x_i)$ | |---|:--:|:--:| | (5,4) | $\circ$ | $\sqrt{1} = 1{.}000$ | | (6,6) | $\bullet$ | $\sqrt{2} \approx 1{.}414$ | | (6,7) | $\bullet$ | $\sqrt{5} \approx 2{.}236$ | | (7,7) | $\bullet$ | $\sqrt{8} \approx 2{.}828$ | | (8,6) | $\bullet$ | $\sqrt{10} \approx 3{.}162$ | | (2,2) | $\circ$ | $\sqrt{18} \approx 4{.}243$ | | (2,1) | $\circ$ | $\sqrt{25} = 5{.}000$ | | (1,1) | $\circ$ | $\sqrt{32} \approx 5{.}657$ | - **$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). ![Точки двох класів і запит q=(5,5); штрихове коло охоплює k=3 найближчих сусідів — один клас 1 і два клас 2, голосування 1:2 на користь класу 2](img/l06_knn_neighbors.png) --- ## 6.11 Алгоритм kNN ```text 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. $$ ![Порівняння відстаней між x=(1,2) та y=(4,6): евклідова — пряма гіпотенуза завдовжки 5, манхеттенська — Г-подібний шлях 3+4=7](img/l06_distance.png) Зі зростанням $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 на межу класів: за k=1 межа рвана й чутлива до шуму (виникають острівці), за k=15 межа згладжена](img/l06_effect_k.png) Оптимальне $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: ліворуч вага сусіда спадає з відстанню за 1/d і 1/d^2; праворуч зважене голосування знімає нічию 2:2 на користь класу A](img/l06_weighted.png) --- ## Застосування в аналітиці даних - **Рекомендаційні системи.** «Користувачі, схожі на вас (найближчі сусіди), вподобали…» — це kNN у просторі вподобань. - **Медична діагностика.** Класифікація за схожістю на раніше діагностованих пацієнтів; тут матриця невідповідності й **чутливість** особливо важливі (ціна пропуску $FN$ висока). - **Оцінювання будь-якого класифікатора.** Матриця невідповідності та метрики (ACC, $P$, $R$, $F_1$, MCC) — універсальний інструмент порівняння моделей; ми застосовуватимемо їх до дерев ([Лекція 7](DA-L07.md)) і баєсового класифікатора ([Лекція 8](DA-L08.md)). - **Виявлення аномалій.** Об'єкт, у якого навіть найближчі сусіди далеко, ймовірно, є **викидом**. ## Підсумок - **Класифікація** — навчання з учителем: за ознаками $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](DA-L05.md)) і від задачі кластеризації ([Лекція 9](DA-L09.md))? Наведіть по прикладу. 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$?