Алгоритъм, който не се обучава
Всички модели дотук търсеха параметри. k-NN не търси нищо. Той просто пази данните и когато дойде нов пример, поглежда кои примери са най-близо до него.
k най-близки съседа (k-NN)
За нов пример намери k-те най-близки примера от обучаващия набор и му дай етикета, който преобладава сред тях.
Обучението се състои в запомняне на данните — затова методът се нарича мързелив. Цялата работа се върши в момента на предсказването.
Целият алгоритъм в четири реда
- Пресметни разстоянието от новия пример до всеки обучаващ пример.
- Подреди по разстояние.
- Вземи първите k.
- Върни най-често срещания етикет сред тях (при регресия — средното от стойностите им).
Затова го пишем сами
Това е единственият алгоритъм в курса, който можете да реализирате изцяло за един час — следващият урок е точно това. Полезно е да видите отвътре какво прави един класификатор.
Изборът на k
| Малко k (например 1) | Голямо k (например 50) | |
|---|---|---|
| Границата между класовете | накъсана, следва всяка точка | гладка |
| Шум и грешни етикети | влияят силно | се заглушават |
| Риск | пренастройване | недостатъчно обучение |
| Краен случай | запаметява данните | връща най-многобройния клас винаги |
- k се избира с проби върху валидационна част, не наизуст.
- При два класа се предпочита нечетно k, за да няма равен резултат.
- Добра отправна точка е k около корен квадратен от броя примери.
Къде се проваля
Мащабът на признаците
k-NN е изцяло базиран на разстояние, затова е най-чувствителният към мащаба алгоритъм. Ако единият признак е заплата (хиляди), а другият — брой деца (единици), заплатата решава всичко. Нормализирането тук не е препоръка, а условие.
Много признаци
При десетки признаци всички точки започват да са приблизително еднакво далече една от друга и понятието „най-близък“ губи смисъл. Това явление се нарича проклятие на размерността.
Скорост
Обучението е мигновено, но всяко предсказание изисква обхождане на целия набор. При 100 000 примера и хиляди заявки в секунда това е неприемливо. Има ускорения (специални дървовидни структури), но границите остават.
Кога все пак е добър избор
Малък набор, малко признаци, нужда от бърз резултат без обучение и от обяснимост: можете да покажете на потребителя точно кои примери са довели до отговора.