Най-близкият съсед е един от най-простите алгоритъми в машинното обучение, буквално, просто трябва да го видите веднъж през Geometry и това е, няма да го забравите.

В тази поредица от статии ще видим почти всичко за KNN, като неговата геометрична интуиция, математическа част, времева сложност, пространствена сложност, най-добър случай, най-лош случай и много други.

Преди да преминем директно към KNN, нека разберем някои от основните термини, които използваме в машинното обучение.

КАКВО Е КЛАСИФИКАЦИЯ???

На прост език, ако искаме да го разберем чрез пример, нека кажем, че имаме някои отзиви за храна в Amazon, някои са положителни, а други отрицателни, така че можем ли да намерим функция f(x), където x е новият преглед, който се преобразува във вектор, така че тази функция f(x) може да определи дали новият преглед е положителен или отрицателен.

Така че задачата за класификация е да се намери функцията y=f(x), ако y принадлежи само на два класа, както в горния пример, който се нарича двоична класификация.

Ако y принадлежи към повече от 2 класа, това се нарича многокласова класификация.

Така че Dn={xi,yi}, където i варира от 0 до n, xi принадлежи на реално число с размери d (тук размерите означават различни характеристики) и yi принадлежи на {0,1}, ако това е проблем с двоична класификация и yi принадлежи към {0,1,2,3….n} в многокласовата класификация.

КАКВО Е РЕГРЕСИЯ?

Сега, ако в горното изявление, ще се присъединя към още едно изявление, което е,

Ако yi принадлежи към Real Number и не е повече част от малък краен набор от класове, това е регресия.

пример-

xi‹тегло, възраст, пол, раса›

y‹височина›

Предвид набор от всички функции по-горе, ако искам да изчисля функция, която определя „височината“, това е проблем с регресията.

KNN(K НАЙ-БЛИЗКИ СЪСЕД)

Винаги подхождам към даден алгоритъм чрез пример или се опитвам да разбера неговата геометрична интуиция, след което преминавам към неговата математика и накрая Ограничения. Ще следваме същия модел и тук.

Първо ще се опитаме да разберем неговата геометрична интуиция, тук вземам 2D пример, защото е лесен за визуализиране и с помощта на проста линейна алгебра можем да разширим до 3D, 4D и повече измерения.

Така че нека вземем набор от данни D={xi,yi}, където i варира от 0 до n, xi принадлежи на реално число с размери 2 (тук размерите означават различни характеристики), а yi принадлежи на {0,1}

Цялата цел на машинното обучение в класификацията е, когато имате данни, алгоритъмът научава нещо от тях и при нова точка на заявка той казва дали е положителен или отрицателен.

Да кажем, че имаме данни, категоризирани в положителни и отрицателни, някакъв алгоритъм ще се учи от данните и след това ще ни каже дали дадена точка на заявка sq принадлежи към положителни или отрицателни.

Да кажем, че малкият ми кръг в горната снимка обозначава положителни, а малкият кръст представлява отрицателни.

Как работи KNN?

Стъпка 1- Намерете k най-близки точки до xq в набора от данни, да кажем k=3, така че ще намерим 3 най-близки точки от xq, да кажем x1,x2,x3 и от данните за обучение имаме съответните им класове, така че да кажем, че имаме да знаете от данните за обучение, че x1 принадлежи на y1, x2 принадлежи на y2, x3 принадлежи на y3.

Стъпка 2-Вземане на мнозинството от гласовете,

Да кажем, че и трите класа y1,y2,y3 принадлежат към положителни, така че xq принадлежи към положителни.

  1. +,+,+, мажоритарният вот ще бъде положителен, xq принадлежи към положителния клас
  2. +,+,-, мажоритарният вот ще бъде положителен, xq принадлежи към положителния клас
  3. +,-,-, мажоритарният вот ще бъде отрицателен, xq принадлежи към положителен клас

Един основен въпрос, който имаме, е КАК ДА ИЗБЕРЕМ СТОЙНОСТТА НА K??

Ще обсъдим това по-късно в тази статия.

Така че основно това е KNN, просто и лесно.

МАТЕМАТИКАТА ЗАД KNN

Математиката зад KNN е много ясна, ако мислите логично, можете лесно да я познаете, KNN работи на разстоянието между две точки, така че това е алгоритъм, базиран на разстояние.

Така че разстоянието може да бъде от различни видове. В тази статия ще проучим три мерки за разстояние.

  1. Евклидово разстояние - Така че това е основно най-късото разстояние между 2 точки, като на снимката по-долу, то е много право напред, да кажем, че имаме X1 е 2D или има две характеристики x11 и x12, по подобен начин X2 има две характеристики x21 и x22, ние вземаме разликата на точките във всяко измерение, повдигайки ги на квадрат, вземайки корен от сбора.

Евклидовото разстояние следва нормата L2, която е

||xi||=(x11²+x12²+x13²+x14²….)^1/2 където i варира от 0 до d означава d измерения

2. Разстояние до Манхатън –Да речем, че искате да отидете до най-близкия пазар, но условието е, че не можете да вземете най-краткото разстояние, просто трябва да поемете по вертикални и хоризонтални пътища, за да стигнете до там, това е разстоянието до Манхатън.

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

Разстоянието в Манхатън следва L1 норма, която е

||xi||=(x11+x12+x13….) i варира от 0 до d, означава d измерения

Дава абсолютната стойност.

3. Разстояние Минковски -Сега това е обобщената форма както на Манхатън, така и на Евклидовото разстояние.

Снимка

||xi||=(x11^p+x12^p+x13^p+x14^p….)^1/p където i варира от 0 до d означава d измерения .

Ако p=2, това е Евклидова норма или L2 норма.

Ако p=1, това е разстоянието Манхатън или L1 норма.

Разстоянието е между точките, а нормата е между векторите.

4. Косинусово сходство или косинусово разстояние-Сходството и разстоянието са противоположни, ако две точки имат значително голямо косинусово разстояние, тогава определено тяхното косинусово сходство ще бъде много ниско.

1-косинус сходство (x1,x2)= косинус-разстояние(x1,x2)

Това е връзката между косинусното подобие и косинусното разстояние.

Да речем

Косинусово сходство (x1,x2)=+1 тогава x1 и x2 са много сходни.

И ако

Косинусово сходство (x1,x2)=-1 тогава x1 и x2 са много различни.

Косинусното сходство между две точки, да кажем, x1 и x2 е cos theta ъгълът между x1 и x2.

Cos-подобие(x1,x2)= cos(theta) , където theta е ъгълът между x1 и x2

Както знаем, че от теорията на точковия продукт,

Cos(тета)=x1.x2/|x1|*|x2| , ако x1 и x2 са единични вектори, тогава,

Cos(theta)=x1.x2

ВРЪЗКА МЕЖДУ ЕВКЛИДОВО РАЗСТОЯНИЕ И КОСИНУСОВО ПОДОБИЕ

Евклидово разстояние (x1,x2)= 2(косинусово разстояние (x1,x2)

Искам да видите тази формула напълно и да се опитате да я извлечете, ако не можете да я извлечете, споменава в коментарите. Ще публикувам решението.

Всичко това бяха разстоянията, които можем да използваме, докато прилагаме KNN.

СЛУЧАИ НА ПОВРЕДА НА KNN

Има два основни случая, при които KNN не работи...

1. НЕ РАБОТИ ДОБРЕ С ВЪЗХОДЯЩИ

Нека помислим за ситуация, в която изграждаме модел с помощта на knn и имаме пет точки на заявка, за които трябва да определим дали принадлежат към клас „x“ или клас „0“, както е показано на снимката по-долу. Сега тук, за да избегна усложнения, приемам 2D разположение на точки от данни.

Прилагайки knn към всички точки на заявка (нека вземем k=3), можем лесно да забележим, че xq1 принадлежи към клас „0“, xq2 принадлежи към клас „x“, xq3 принадлежи към клас „0“, xq4 принадлежи към клас „x“. Но нека проверим за xq5, сега xq5 е на голямо разстояние от всеки клъстер от точки и това е проблем с KNN.

Можем да опитаме knn за тази точка, но резултатът ще бъде абсурден, нека опитаме.

За точката на заявката xq5, първата най-близка точка принадлежи към клас „0“, втората най-близка точка принадлежи към клас „x“, третата най-близка точка принадлежи към клас „x“, така че ако вземем тест за мнозинство, можем да кажем, че xq5 принадлежи към „ x”, но това ще бъде абсурдно.

Така че е по-добре да кажем, че не сме сигурни по този въпрос.

2. НЕ РАБОТИ КЪДЕТО НЯМА ГРУПИРАНЕ

Сега нека разберем случай, в който няма групиране на данни, основно те са произволно разпръснати в 2D пространство, това е като смесица от точки от клас „x“ данни и точки „0“. Прилагането на knn ще даде абсолютно абсурден резултат.

В следващата статия ще говоря за времевата и пространствената сложност на KNN, ще видим как да намерим правилното „k“, надстройка и недостатъчност в KNN.

Така че дотогава Благодаря за четенето.