K-най-близките съседи (k-NN) е форма на контролирано обучение, което е непараметрично и базирано на екземпляри. Той работи, като класифицира обект въз основа на мнозинството гласове на неговите k най-близки съседи от набора за обучение, където k е положително цяло число. Когато става въпрос за регресионен проблем, той може да произведе средната стойност на k най-близките съседи или среднопретеглената стойност с разстояние, служещо за тегло.
Важно е да се разбере, че алгоритъмът k-NN е вид мързелив обучаем, което предполага, че той не разработва модел за правене на прогнози. Вместо това, той поддържа всички данни за обучение и ги използва, за да прави прогнози, когато се появят нови точки от данни.
Основната концепция зад k-NN е, че е вероятно сравними екземпляри да имат подобни етикети. В резултат на това алгоритъмът k-NN често се използва както при класификация, така и при проблеми с регресия.
Алгоритъмът k-NN може да бъде обобщен в следните стъпки:
- Решете стойността на k, която определя броя на най-близките съседи, които да вземете предвид.
- Идентифицирайте k най-близките съседи на новата точка от данни в пространството на характеристиките.
- Определете класа, който се появява най-често сред k най-близките съседи.
- Присвоете новата точка от данни на най-често срещания клас.
Съществуват няколко метода за изчисляване на разстоянието между две точки в пространството на характеристиките, като например:
- Евклидово разстояние: Това е най-често използваната мярка за разстояние и се изчислява като корен квадратен от сбора на квадратите на разликите между координатите на две точки. С други думи, това е разстоянието по права линия между две точки в евклидовото пространство.
d(x, y) = √(x2-x1)2 + (y2-y1)2
2.Разстояние Манхатън: Тази мярка за разстояние е известна още като разстояние „такси такси“, защото това е разстоянието, което едно такси би трябвало да измине, ако може да се движи само по решетката на даден град, за да стигне от една точка към друга. Изчислява се като сбор от абсолютните разлики между координатите на две точки.
d(x, y) = |x1-y1| + |x2-y2| + … + |xn — yn|
3. Косинусово сходство: Тази мярка за разстояние се използва за определяне на сходството между два ненулеви вектора на вътрешно продуктово пространство и измерва косинуса на ъгъла между тях. Изчислява се по следния начин
cos(x, y) = (x.y) / (||x||.||y||)
4. Разстояние на Минковски: Тази мярка за разстояние е обобщение на разстоянията на Евклид и Манхатън.
d(x, y)=((|x1-y1|^p)+(|x2-y2|^p)+…+(|xn-yn|^p))^(1/p)
Освен това, алгоритъмът k-NN може да се приложи за решаване на проблеми с двоична класификация, както и с многокласова класификация.
Предимства:
- Изчислението е лесно.
- Изпълнението е лесно.
- Изчислението е ефективно.
Недостатъци:
- Грешна класификация може да възникне поради шум.
- Той е неефективен, когато се работи с големи набори от данни за обучение.
Предизвикателството при избора на идеалната K стойност е:
- изборът на малка стойност може да доведе до прекалено чувствителен модел към шум, докато изборът на голяма стойност може да доведе до прекомерна гладкост на модела.
Има различни техники за определяне на най-добрата стойност за k, като например:
- Метод на кръстосано валидиране
- Адаптивен метод
Обикновено нечетно число между 3 и 10 се предпочита за k, за да се предотврати всяка възможност за равенство.
Пример:
Входен вектор: (x1, y1) = [6, 4]
- ( x1, y1 ) = [ 6, 4 ] и ( x2, y2 ) = [ 7, 3 ]
d(x, y) = √(x2-x1)2 + (y2-y1)2
= √(7–6)2 + (3–4)2
= √2 = 1.42
По подобен начин решете изчислете разстоянието на (x1,y1) от други точки.
Нека стойността на k = 5
така че входният вектор ( x1, y1 ) = [ 6, 4 ] принадлежи към клас B.
