Въведение
K Nearest Neighbors е алгоритъм за контролирано обучение, базиран на предположението, че точките в околността (т.е. най-близките точки) принадлежат към един и същи клас.
Следователно, предвид положително цяло число k и тестово наблюдение, KNN идентифицира k най-близките точки и след това може да направи изводи въз основа на тези най-близки цели.
Забележете, че може да се използва както за проблеми с класификация, така и за регресия. По-специално, за класификационен проблем, той оценява условната вероятност за клас j като част от точките в околността, чиято целева стойност е равна на j em>:
където N0 представлява околността на даденото наблюдение. Той класифицира наблюдението с класа с най-висока условна вероятност. По къси панталони се счита за класа на мнозинството в квартала!
От друга страна, при регресионен проблем изходът ще бъде само средната стойност на k най-близките цели.
Как да изберем правилната стойност на k
Изборът на kвинаги е критичен, всъщност трябва да обърнем внимание на два различни сценария:
- малък k :тъй като сте много близо до наблюдението, ще имате ниско отклонение, но може да бъдете засегнати от силна дисперсия поради наличието на някои извънредни стойности
- голямо k :ако разширите квартала си, вие ще бъдете по-стабилни към отклоненията (ниска дисперсия), но в крайна сметка ще получите по-голямо отклонение, защото вероятно ще вземете предвид точки, които не са толкова близки.
„Компромисът отклонение-вариация“ винаги е зад ъгъла!
Добре, страхотно, но как да го изберем? За съжаление няма абсолютен отговор, но трябва да опитаме различни стойности.
Обичайна практика е да се начертае метриката на референтната грешка за различни стойности на k. По този начин можете да видите със собствените си очи как се държи вашият модел и какво може да бъде добър компромис.
Показатели за разстояние
За да определим количествено колко едно наблюдение xе близо до y,трябва да дефинираме подходяща метрика за разстояние. Най-често срещаните са:
- манхатън:разстоянието между две точки е сумата от абсолютните разлики на техните координати.
- евклидов: той е може би най-използваният и се дефинира като корен квадратен от сумата от квадратите на разликите на координатите
- chebyshev: това е максималната абсолютна разлика между всички координати. Нарича се още върховно разстояние
Внедряване
За да обобщим, наивният алгоритъм е доста ясен:
- За всички тестови наблюдения изчислете разстоянията между тях и всички тренировъчни
- Обмислете само kнай-близките точки и поддържайте техните цели
- Ако това е проблем с класификацията, вземете класа на мнозинството, в противен случай вземете средната стойност на най-близките цели.
Пълното изпълнение може да бъде намерено тук. Първо, бих искал да докладвам скелета на класа с всички методи, които трябва да приложим.
Методът __init__ ще се използва за дефиниране на броя на съседите, избраната метрика и спомагателен флаг за разбиране дали имаме работа с проблем с регресия или класификация. Сега постепенно ще обогатим кода до края!
За краткост тук съм докладвал само евклидовото разстояние, но в хранилището на github ще намерите всички реализации.
Освен това, тъй като можем да избираме от различни показатели, важно е да проверим дали обмисляме „валиден“ такъв:
След това трябва да можем да изчислим разстоянието, затова нека добавим два други метода: compute_distance()иeuclidean_distance(). Първият ще се използва за извикване на правилния метод за разстояние въз основа на избрания, докато вторият (и също тези, които не съм докладвал) ще отговарят за връщането на действителното разстояние.
Тук започва забавлението! Дефинирахме всички методи на контура, но сега трябва да дефинираме чистия метод fit_predict(). Спомнете си, че в този случай прилагаме подход с груба сила, но има много по-ефективни решения.
Така че за всяка тестова точка трябва да изчислим (и запазим) всички разстояния с тренировъчните точки. След това ги сортираме и вземаме само kнай-близките (т.е. тези, за които имаме най-ниското разстояние).
След това запаметяваме само техния клас и накрая можем да направим нашата прогноза като средна стойност или клас на мнозинството, съответно за проблем с регресия или класификация.
И накрая, за пълнота, сравних производителността на този алгоритъм с внедряването на ScikitLearn върху Iris Dataset и производителността е еднаква!
Изводи
Този алгоритъм е доста прост, но е изключително мощен, когато имаме умерен брой функции и проби. Беше доста забавно и предизвикателно и се надявам, че сте разбрали всички скрити пасажи!
За всякакви коментари, съмнения или обратна връзка, не се колебайте да се свържете с мен в LinkedIn, ще се радвам да отговоря! :Д
