Как да изградите KNN от нулата в Python

... добре, поне без KNeighborsClassifier на sklearn.

k-Най-близки съседи

k-Nearest Neighbors (KNN) е контролиран алгоритъм за машинно обучение, който може да се използва или за задачи за регресия, или за класификация. KNN е непараметрична, което означава, че алгоритъмът не прави предположения относно основните разпределения на данните. Това е в контраст с техника като линейната регресия, която е параметрична и изисква от нас да намерим функция, която описва връзката между зависимите и независимите променливи.

KNN има предимството да бъде доста интуитивен за разбиране. Когато се използва за класификация, дадена точка на заявка (или точка на изпитване) се класифицира въз основа на обозначените с k точки за обучение, които са най-близо до тази точка на заявка.

За опростен пример вижте фигурата по-долу. Левият панел показва двуизмерна диаграма от шестнадесет точки от данни — осем са означени като зелени, а осем са означени като лилави. Сега десният панел показва как бихме класифицирали нова точка (черния кръст), използвайки KNN, когато k=3. Намираме трите най-близки точки и преброяваме колко „гласа“ има всеки цвят в тези три точки. В този случай две от трите точки са лилави - така че черният кръст ще бъде означен като лилав.

Изчисляване на разстояние

Разстоянието между точките се определя чрез използване на една от няколко версии на уравнението на разстоянието на Минковски. Обобщената формула за разстоянието на Минковски може да бъде представена по следния начин:

където X и Yса точки от данни, n е броят на измеренията и p е параметърът на мощността на Минковски . Когатоp=1, разстоянието е известно като разстоянието на Манхатън (или таксиметровия автомобил), а когато p=2 разстоянието е известно като евклидово разстояние. В две измерения разстоянията на Манхатън и Евклид между две точки са лесни за визуализиране (вижте графиката по-долу), но при по-високи порядъци на p разстоянието на Минковски става по-абстрактно.

KNN в Python

За да внедря собствената си версия на класификатора KNN в Python, първо ще искам да импортирам няколко общи библиотеки, за да помогна.

Зареждане на данни

За да тествам класификатора KNN, ще използвам набора от данни за ириса от sklearn.datasets. Наборът от данни съдържа измервания (дължина на чашелистчето, ширина на чашелистчето, дължина на венчелистчето, ширина на венчелистчето) за 150 растения ирис, разделени по равно между три вида (0 = setosa, 1 = versicolor и 2 = virginica). По-долу зареждам данните и ги съхранявам в рамка с данни.

Също така ще разделя данните на характеристики (X) и целевата променлива (y), която е етикетът на вида за всяко растение.

Изграждане на KNN Framework

Създаването на функциониращ KNN класификатор може да бъде разделено на няколко стъпки. Въпреки че KNN включва малко повече нюанси от това, ето моя списък със задачи:

1. Дефинирайте функция за изчисляване на разстоянието между две точки
2. Използвайте функцията за разстояние, за да получите разстоянието между тестова точка и всички известни точки от данни
3. Сортирайте измерванията на разстоянието, за да намерите точките, които са най-близо до тестовата точка (т.е. намерете най-близките съседи)
4. Използвайте етикети на мнозинството класове на тези най-близки точки, за да предвидите етикета на тестовата точка
5. Повторете стъпки от 1 до 4, докато всички точки от тестови данни бъдат класифицирани

1. Дефинирайте функция за изчисляване на разстоянието между две точки

Първо, дефинирам функция, наречена minkowski_distance, която приема вход от две точки от данни (a & b) и параметър на мощността на Minkowski p,и връща разстоянието между двете точки. Имайте предвид, че тази функция изчислява разстоянието точно като формулата на Минковски, която споменах по-рано. Като направя p регулируем параметър, мога да реша дали искам да изчисля разстоянието Манхатън (p=1), евклидовото разстояние (p=2) или някакъв по-висок порядък от разстоянието на Минковски.

0.6999999999999993

2. Използвайте функцията за разстояние, за да получите разстоянието между тестова точка и всички известни точки от данни

За стъпка 2 просто повтарям изчислението на minkowski_distance за всички обозначени точки в X и ги съхранявам в рамка с данни.

3. Сортирайте измерванията на разстояния, за да намерите точките, които са най-близо до тестовата точка

В стъпка 3 използвам метода pandas .sort_values() за сортиране по разстояние и връщане само на първите 5 резултата.

4. Използвайте етикети на мнозинството класове на тези най-близки точки, за да предвидите етикета на тестовата точка

За тази стъпка използвам collections.Counter, за да следя етикетите, които съвпадат с най-близките съседни точки. След това използвам метода .most_common(), за да върна най-често срещания етикет. Забележка: ако има равенство между два или повече етикета за заглавието на „най-често срещания“ етикет, този, който първо е бил срещнат от обекта Counter(), ще бъде този, който ще бъде върнат.

1

5. Повторете стъпки от 1 до 4, докато всички точки от тестови данни бъдат класифицирани

В тази стъпка поставям кода, който вече съм написал, да работи и пиша функция за класифициране на данните с помощта на KNN. Първо извършвам train_test_split върху данните (75% тренировка, 25% тест) и след това мащабирам данните с помощта на StandardScaler(). Тъй като KNN е базиран на разстояние, важно е да се уверите, че характеристиките са правилно мащабирани, преди да ги подадете в алгоритъма.

Освен това, за да избегнете изтичане на данни, е добра практика да мащабирате функциите следизвършване на train_test_split. Първо мащабирайте само данните от набора за обучение(scaler.fit_transform(X_train)) и след това използвайте тази информация, за да мащабирате тестовия набор (scaler.tranform (X_тест)). По този начин мога да гарантирам, че за създаване на модела не се използва информация извън данните за обучение.

След това дефинирам функция, наречена knn_predict, която приема всички данни за обучение и тестове, k и p, и връща моите прогнози Класификаторът KNN прави тестовия набор (y_hat_test). Тази функция всъщност не включва нищо ново - тя просто прилага това, което вече съм работил по-горе. Функцията трябва да върне списък с прогнози за етикети, съдържащи само 0, 1 и 2.

[0, 1, 1, 0, 2, 1, 2, 0, 0, 2, 1, 0, 2, 1, 1, 0, 1, 1, 0, 0, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 1, 2, 1, 2, 2, 0, 1, 0]

И ето ги! Това са прогнозите, които този домашно приготвен класификатор KNN е направил върху тестовата серия. Нека да видим колко добре работи:

0.9736842105263158

Изглежда, че класификаторът е постигнал 97% точност на тестовия набор. Изобщо не е зле! Но как да разбера дали наистина работи правилно? Нека проверим резултата от KNeighborsClassifier на sklearn върху същите данни:

Sklearn KNN Accuracy: 0.9736842105263158

хубаво! Изпълнението на sklearn на класификатора KNN ни дава абсолютно същия резултат за точност.

Изследване на ефекта от варирането на k

Моят KNN класификатор се представи доста добре с избраната стойност от k = 5. KNN няма толкова много настройваеми параметри, както други алгоритми като Дървета на решенията или Случайни гори, но k случайно е един от тях. Нека да видим как се променя точността на класификацията, когато променям k:

В този случай използването на почти всяка kстойност, по-малка от 20, води до голяма (›95%) точност на класификацията на тестовия набор. Когато обаче k стане по-голямо от около 60, точността наистина започва да пада. Това има смисъл, тъй като наборът от данни има само 150 наблюдения — когато k е толкова високо, класификаторът вероятно обмисля етикетирани точки от данни за обучение, които са твърде далеч от точките за тестване.

Всеки съсед получава глас - или не?

При писането на моя собствен KNN класификатор избрах да пренебрегна една ясна възможност за настройка на хиперпараметър: тежестта, която всяка от kнай-близките точки има при класифицирането на точка. В KNeighborsClassifier на sklearn това е параметърът weights и може да бъде зададен на 'uniform', 'distance' или друга дефинирана от потребителя функция.

Когато е зададено на „uniform“, всеки от k най-близките съседи получава равен глас при етикетиране на нова точка. Когато е зададено на „разстояние“, съседите, които са най-близо до новата точка, имат по-голямо тегло от съседите, които са по-далеч. Със сигурност има случаи, при които претеглянето по „разстояние“ би дало по-добри резултати и единственият начин да разберете е чрез настройка на хиперпараметър.

Последни мисли

Сега, не се заблуждавайте – внедряването на sklearn е несъмнено по-ефективно и по-лесно за потребителя от това, което съм събрал тук. Въпреки това намерих за ценно упражнение да работя с KNN от „нулата“ и само затвърди разбирането ми за алгоритъма. Надявам се да направи същото и за вас!