Най-близък съсед метод: пример за работа

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

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

Хипотеза на метода

Методът на най-близкия съсед може да се счита за най-често използваният алгоритъм за класификация. Обект, който претърпява класификация, принадлежи към този клас y_i, към който принадлежи най-близкият обект на учебната проба x_i.

Специфичност на методологията на най-близките съседи

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

Техниката на претегляните съседи

Методът на най-близките съседи се използва, когато броят на класовете не е по-малък от три, а странното не може да се използва. Но в тези случаи възниква двусмисленост. Тогава i-та съсед получава теглото w_i, което намалява с нарастващия ранг на съсед i. Предметът се отнася за клас, който ще има максимално общо тегло сред близките съседи.

Компактна хипотеза

В основата на всички горепосочени методи е хипотезата за компактност. Тя включва връзка между мярката за сходство на обектите и принадлежността им към една класа. В тази ситуация границата между различните изгледи има проста форма и класовете създават компактни подвижни зони в пространството на обектите. Под такива домейни в математическия анализ е обичайно да означават затворени ограничени комплекти. Тази хипотеза не е свързана с ежедневното възприемане на тази дума.

Основната формула

Нека анализираме по-подробно метода на най-близкия съсед. Ако предложен живот тип проба "обект-отговор» X ^ т = {(x_1, y_1), точки, (x_m, y_m) } - ако е зададено разстояние функция р (х, х ") за множество обекти, които е представена под формата на адекватен модел на сходство на обектите, тъй като стойността на тази функция се увеличава, приликата между обектите х, х `намалява.

За всеки обект ф, ние конструираме пробните обекти на обучение x_i, тъй като разстоянията до u се увеличават:

Rho (ф, x_ {1- ф}) екв р (ф, x_ {2- ф}) екв cdots екв р (ф, x_ {т- ф}),

където x_ {i-u} характеризира пробния обект за обучение, който е i-ти съсед на оригиналния обект u. Използваме тази нотация за отговора на i-th съсед: y_ {i-u}. В резултат на това получаваме, че произволен обект u провокира промяна в номерирането на собствената му извадка.

Определяне на броя на съседите k

Методът на най-близкия съсед при k = 1 може да даде грешна класификация не само на емисионни обекти, но и на други класове, които се намират в близост.

Ако вземем k = m, алгоритъмът ще бъде възможно най-стабилен и ще се дегенерира в константна стойност. Ето защо заради надеждността е важно да не се допускат крайни показатели k.

На практика критерият за плъзгащ контрол се използва като оптимален показател k.

Премахване на емисиите

Обектите на обучението са предимно неравномерни, но сред тях има такива, които имат характерни черти на класа и се наричат ​​стандарти. С близостта на субекта до идеалната извадка вероятността за принадлежност към дадена класа е висока.

Колко ефективен е методът на най-близките съседи? Един пример може да се разгледа на базата на периферни и неинформиращи категории обекти. Предполага се, че околната среда е гъсто заобиколена от други представители на този клас. Ако ги премахнете от извадката, качеството на класификацията няма да бъде засегнато.

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

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

На първо място интерполация от най-близката съсед позволява да се подобри качеството на класификацията, да се намали количеството съхранени данни, да се намали времето за класификация, което се изразходва за избора на най-близките стандарти.

Използването на изключително големи проби

Методът на най-близкия съсед се основава на действителното съхранение на учебни предмети. За да създадете супер големи образци, използвайте технически проблеми. Задачата не е просто да се запази значителен обем информация, но и в минимална времева рамка, за да можем да намерим произволен предмет u сред най-близките k съседи.

За да се справим със задачата, се използват два метода:

• подредете пробата, като изхвърлите не-информационни обекти;
• прилагат специални ефективни структури и индекси за данни за незабавно търсене на най-близките съседи.

Правила за подбор на методология

Класификацията беше разгледана по-горе. Методът на най-близкия съсед се използва за решаване на практически проблеми, при които разстоянието функция rho (x, x `) е известно предварително. Когато описваме обекти, цифровите вектори използват евклидовия показател. Такъв избор няма специална обосновка, но предполага измерването на всички знаци "на един мащаб". Ако този фактор не се вземе предвид, тогава метриката ще бъде доминирана от знака с най-големи числови стойности.

При наличието на значителен брой характеристики, изчисляване на разстоянието като сума от отклонения за специфични характеристики, се появява сериозен проблем с измерените величини.

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

заключение

Математическите изчисления често включват използването на различни техники, които имат свои собствени отличителни характеристики, предимства и недостатъци. Замисленият метод на най-близките съседи позволява да се решат доста сериозни проблеми, свързани с характеризирането на математическите обекти. Експерименталните концепции, базирани на анализираната техника, сега се използват активно в инструментите за изкуствена интелигентност.

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

За да бъде анализираният метод възможно най-надежден, ефективен, да даде желания резултат, е необходимо да се вземе минималният показател k, а също и да не се допускат емисиите от анализираните обекти. Ето защо се прилага методологията за избор на стандарти, а също и оптимизирането на показателите.