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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

У задачах бінарної (два класи) класифікації корисно вибрати 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-NN викиди

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

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

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

Див. також

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

Джерела

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