Метод k-найближчих сусідів

Частина з циклу
Машинне навчання та добування даних
Парадигми Кероване навчання Некероване навчання Інтерактивне навчання Пакетне навчання Метанавчання Напівкероване навчання Самокероване навчання Навчання з підкріпленням Навчання на основі правил Квантове машинне навчання
Задачі Класифікація Породжувальна модель Регресія Кластерування Знижування розмірності Оцінювання густини Виявляння аномалій Очищування даних АвтоМН Асоціативні правила Семантичний аналіз Структурове передбачування Конструювання ознак Навчання ознак Навчання ранжуванню Виведення граматик Навчання онтологій Мультимодальне навчання
Кероване навчання (класифікація • регресія) Ансамблі Випадковий ліс Бутстрепова агрегація Підсилювання Градієнтне підсилювання AdaBoost Дерева рішень MARS CART Доречно-векторна машина k-сусідів Лінійна регресія Логістична регресія Лінійний розділювальний аналіз Наївний баєсів класифікатор Перцептрон Підмайстрове навчання Опорно-векторна машина Штучні нейронні мережі
Кластерування BIRCH CURE Ієрархічне k-середніх Нечітке Очікування-максимізація DBSCAN OPTICS Спектральне Зсув середнього
Знижування розмірності Факторний аналіз Метод незалежних компонент Канонічна кореляція Дискримінантний аналіз Метод головних компонент Власний узагальнений розклад Розклад невід'ємних матриць t-розподілене вкладення стохастичної близькості Навчання розріджених словників
Структурове передбачування Графові моделі Баєсова мережа Прихована марковська модель Умовне випадкове поле
Виявляння аномалій RANSAC k-НС Коефіцієнт локального відхилення Відстань Кука Ізоляційний ліс
Штучна нейронна мережа Автокодувальник Когнітивні обчислення Глибоке навчання DeepDream Нейронна мережа прямого поширення Рекурентна нейронна мережа ДКЧП ВРВ МВС Резервуарне обчислення Обмежена машина Больцмана ГЗМ Дифузійна модель Самоорганізаційна карта Згорткова нейронна мережа U-Net Трансформер Зоровий Спайкова нейронна мережа Мемтранзистор Електрохімічна ПДД (ECRAM)
Навчання з підкріпленням Q-навчання SARSA Метод часових різниць Багатоагентне навчання з підкріпленням Гра проти себе
Навчання з людьми Активне навчання (машинне навчання) Краудсорсинг Людина-в-циклі
Діагностування моделей Крива спроможності навчатися
Математичні засади Ядрові машини Компроміс зсуву та дисперсії Ймовірнісно приблизно коректне навчання Мінімізація емпіричного ризику Оккамове навчання Регуляризація LASSO Тихонова Еластично-сіткова Статистичне навчання Теорія Вапника — Червоненкіса Теорія обчислювального навчання
Місця машинного навчання ECML PKDD NeurIPS ICML ICLR IJCAI ML JMLR
Пов'язані статті Глосарій штучного інтелекту Список наборів даних для досліджень з машинного навчання Перелік понять машинного навчання

Ме́тод k-найбли́жчих сусі́дів (англ. k-nearest neighbor method) — це непараметричний метод керованого навчання, вперше розроблений Евеліном Фіксом та Джозефом Ходжесом у 1951 році, а пізніше розвинутий Томасом Ковером. Метод використовується як для класифікації, так і для регресії. В обох випадках вхідні дані складаються з k найближчих навчальних прикладів у наборі даних. Результат залежить від того, для чого використовується k-НС для класифікації чи регресії:

• При класифікації k-НС результатом є належність класу. Об'єкт класифікується за допомогою множини голосів його сусідів, при цьому об'єкт належить до класу, найбільш поширеного серед його k найближчих сусідів (k — ціле додатне число, як правило, невелике). Якщо k = 1, то об'єкт просто приписується до класу цього єдиного найближчого сусіда.

• При k-НС регресії результатом є числове значення властивості об'єкта. Це значення є середнім із значень k найближчих сусідів.

k-НС — це тип класифікації, де функція локально лише апроксимується, а всі обчислення відкладаються до оцінки функції. Оскільки цей алгоритм покладається на функцію відстані для класифікації, то у випадку, коли ознаки представляють різні фізичні одиниці або мають дуже різні масштаби, то нормалізація навчальних даних може значно підвищити їх точність.

Як для класифікації, так і для регресії, корисним може бути призначення вагових значень внеску сусідів, щоб внесок у середнє у найближчих сусідів був більше, ніж у віддалених. Для прикладу, загальна схема зважування полягає в тому, щоб надати кожному сусіду вагу 1/d, де d — відстань до сусіда.

Сусіди беруться з множини об'єктів, для яких відомий клас (у випадку k-НС класифікації) або значення властивості об'єкта (у випадку k-НС регресії). Це можна розглядати як навчальний набір для алгоритму, хоча ніякого явного кроку навчання не потрібно виконувати.

Особливістю алгоритму k-НС є те, що він чутливий до локальної структури даних.

Статистичне тло

Припустимо, у нас є пари $(X_{1},Y_{1}),(X_{2},Y_{2}),\dots ,(X_{n},Y_{n})$, які приймають значення в множині $\mathbb {R} ^{d}\times \{1,2\}$, де Y — мітка класу точки X, отже $X|Y=r\sim P_{r}$ для $r=1,2$ (і розподілів ймовірностей $P_{r}$). Для заданої норми $\|\cdot \|$ на $\mathbb {R} ^{d}$ і точки $x\in \mathbb {R} ^{d}$, послідовність $(X_{(1)},Y_{(1)}),\dots ,(X_{(n)},Y_{(n)})$ буде таким переупорядкуванням навчальних даних, що $\|X_{(1)}-x\|\leq \dots \leq \|X_{(n)}-x\|$.

Алгоритм

Приклад k-НС класифікації. Тестовий зразок (зелене коло) повинен бути класифікований як синій квадрат або як червоний трикутник. Якщо k = 3, то класифікується як червоний трикутник, тому що всередині меншого кола 2 трикутника і тільки 1 квадрат. Якщо k = 5, то він буде класифікований як синій квадрат (3 квадрата проти 2-ох трикутників всередині більшого кола).

Навчальними прикладами є вектори багатовимірного ознакипростору ознак, кожен має мітку класу. Фаза навчання алгоритму складається лише із збереження векторів ознак і міток класів навчальних вибірок.

На етапі класифікації k є визначеною користувачем константою, а немаркований вектор (запит або тестова точка) класифікується шляхом призначення мітки, яка є найбільш поширеною серед k навчальних вибірок, найближчих до цієї точки запиту.

Часто використовуваною метрикою відстані для неперервних змінних є евклідова відстань. Для дискретних змінних, наприклад, для класифікації тексту, можна використовувати інший показник, наприклад метрику перекриття (або відстань Геммінга). У контексті мікромасивів даних експресії генів, наприклад, k-НС використовувався з коефіцієнтами кореляції, такими як Пірсон і Спірмен, у якості метрики. Часто точність класифікації k-НС можна значно підвищити, якщо навчатися функції відстані за допомогою спеціалізованих алгоритмів, таких як найближчий сусід з великим полем або аналіз компонентів сусідства.

Основна проблема при класифікації за допомогою «голосування більшості» трапляється, коли розподіл класів перекошений. Тобто, приклади більш частого класу, як правило, домінують у передбаченні нового прикладу, оскільки вони, як правило, поширені серед k найближчих сусідів через їх велику кількість. Одним із способів подолання цієї проблеми є зважування класифікації, беручи до уваги відстань від контрольної точки до кожного з її k найближчих сусідів. Клас (або значення в задачах регресії) кожної з k найближчих точок множиться на вагу, пропорційну оберненій відстані від цієї точки до контрольної точки. Іншим способом подолання перекосу є абстракція у представленні даних. Наприклад, у самоорганізаційній карті Кохонена (СКК) кожен вузол є представником (центром) кластера подібних точок, незалежно від їх щільності в вихідних навчальних даних. Потім k-НС можна застосувати до СКК.

Вибір параметрів

Найкращий вибір k залежить від даних; загалом, більші значення k зменшують вплив шуму на класифікацію, але роблять границі між класами менш чіткими. Гарне значення k можна вибрати різними евристичними методами (див. оптимізація гіперпараметрів). Окремий випадок, коли клас прогнозу є класом найближчої навчальної вибірки (тобто, коли k = 1), називається алгоритмом найближчого сусіда.

Точність алгоритму k-НС може бути значно погіршена через наявність шумних або невідповідних ознак, або якщо масштаби ознак не відповідають їх важливості. Багато дослідницьких зусиль було зосереджено на виборі або масштабуванні ознак для покращення класифікації. Особливо популярний  підхід — це використання еволюційних алгоритмів для оптимізації масштабування ознак. Іншим популярним підходом є масштабування функцій за допомогою взаємної інформації навчальних даних із навчальними класами. 

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

Класифікатор 1-найближчого сусіда

Найбільш інтуїтивно зрозумілим класифікатором типу найближчого сусіда є той класифікатор найближчого сусіда, який призначає точці x клас свого найближчого сусіда в просторі ознак, тобто $C_{n}^{1nn}(x)=Y_{(1)}$.

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

Зважений класифікатор найближчих сусідів

Класифікатор k найближчих сусідів можна розглядати як присвоєння k найближчим сусідам ваги $1/k$, а всі іншим 0 ваги. Це можна узагальнити на зважені класифікатори найближчих сусідів. Тобто, де i-му найближчому сусіду присвоюється вага $w_{ni}$, з $\sum _{i=1}^{n}w_{ni}=1$. Аналогічний результат щодо сильної узгодженості зважених класифікаторів найближчих сусідів також має місце.

Нехай $C_{n}^{wnn}$ позначає зважений найближчий класифікатор з вагами $\{w_{ni}\}_{i=1}^{n}$. За умови регулярності  щодо розподілів класів надмірний ризик має наступне асимптотичне розширення

${\mathcal {R}}_{\mathcal {R}}(C_{n}^{wnn})-{\mathcal {R}}_{\mathcal {R}}(C^{Bayes})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},$

для констант $B_{1}$ і $B_{2}$, де $s_{n}^{2}=\sum _{i=1}^{n}w_{ni}^{2}$ і $t_{n}=n^{-2/d}\sum _{i=1}^{n}w_{ni}\{i^{1+2/d}-(i-1)^{1+2/d}\}$.

Оптимальна схема зважування $\{w_{ni}^{*}\}_{i=1}^{n}$, що врівноважує два терми навелені вище, задається таким чином: $k^{*}=\lfloor Bn^{\frac {4}{d+4}}\rfloor$,

$w_{ni}^{*}={\frac {1}{k^{*}}}\left[1+{\frac {d}{2}}-{\frac {d}{2{k^{*}}^{2/d}}}\{i^{1+2/d}-(i-1)^{1+2/d}\}\right]$ для $i=1,2,\dots ,k^{*}$ і

$w_{ni}^{*}=0$, для $i=k^{*}+1,\dots ,n$.

При оптимальних вагах домінуючим членом в асимптотичному розкладанні надлишкового ризику є ${\mathcal {O}}(n^{-{\frac {4}{d+4}}})$. Подібні результати справедливі при використанні для агрегації класифікатора найближчого сусіда.

k-НС викиди

Відстань до k-го найближчого сусіда також можна розглядати як оцінку локальної щільності, і, таким чином, також є популярним показником викиду при виявленні аномалій. Чим більша відстань до k-НС, чим нижча локальна щільність, і тим більша ймовірність, що точка запиту є викидом. Ця модель викидів, хоча й досить проста, разом з іншим класичним методом аналізу даних, фактором локального відхилення, працює досить добре в порівнянні з більш сучасними та складнішими підходами, згідно з широкомасштабним експериментальним аналізом.

Прокляття розмірності

Цей класифікатор робить припущення, що подібні точки мають подібні мітки. На жаль, у високорозмірнісних просторах, точки, вибрані з розподілу ймовірностей, майже ніколи не опиняються близько одна до одної.

Див. також

• Граф найближчих сусідів

Джерела

• Глосарій термінів з хімії / укладачі: Й. Опейда, О. Швайка ; Ін-т фізико-органічної хімії та вуглехімії ім. Л. М. Литвиненка НАН України, Донецький національний університет. — Донецьк : Вебер, 2008. — 738 с. — ISBN 978-966-335-206-0.
• Лекція з методу k-найближчих сусідів