У препознавању образаца, к-најближих суседа (или скраћено к-НН) представља непараметарски метод који се користи за класификацију и регресију. У оба случаја, улаз се састоји од к најближих тест примера у функцији простора. Излаз зависи од тога да ли се к-НН користио за класификацију или регресију:

У к-НН класификацији, излаз је члан класе. Објекат се класификује гласовима већине својих суседа, тако да објекат буде распоређен у класу најчешћу међу својим к најближим суседима (к је позитиван цео број, најчешће мали број). Ако је к = 1, онда се објекат једноставно додељује класи тог једног најближег суседа.

У к-НН регресији, излаз представља вредност објекта. Ова вредност представља просек вредности његових к најближих суседа.

к-НН је тип учења које се заснива на примерима, или тзв. лењо учење, где је апроксимација функције локална и сва израчунавања одлажу до класификације. The к-НН алгоритам је најједноставнији од свих алгоритама машинског учења.

Додела тежине доприносима суседа може бити од користи и за класификацију и за регресију, тако да ближи суседи доприносе просеку више у односу на оне удаљеније. На пример, честа шема доделе је таква да се сваком од суседа додели тежина од 1/d, где d представља растојање од суседа.This scheme is a generalization of linear interpolation.

Суседи се узимају из скупа објеката за које је класа (за к-НН класификацију) или вредност објекта (за к-НН регресију) позната. Ово се може посматрати као тест скуп за алгоритам иако експлицитни тест кораци нису неопходни.

Мана к-НН алгоритма је та што је осетљив на локалне структуре података. Алгоритам нема ништа заједничко и не треба га мешати са кластеризацијом кластеризацијом методом к-средњих вредности, што је друга популарна техника машинског учења.

Алгоритам мини|десно|Пример к-НН класификације. Тест пример (зелени круг) треба да буде класификован или као прва класа плавих квадрата или као друга класа црвених троуглова. Ако је к = 3 (пуна линија круга), онда је додељен другој класи јер се унутар унутрашњег круга налазе 2 троугла и само један квадрат. Ако је к = 5 (испрекидана линија круга), онда је додељен првој класи (3 квадрата у односу на 2 троугла унутар спољашњег круга).

Тест примери су вектори у мултидимензионалној функцији простора, где сваки има класну ознаку. Тест фаза алгоритма састоји се у складиштењу будућих вектрора и класних ознака тест примера.

У фази класификације, к је константа дефинисана од стране корисника, а неозначени вектор (упит или тест пример) се класификује доделом ознаке која је најучесталија међу к тест примерима најближим датом упиту.

Најчешће се користи Еуклидово растојање за непрекидне променљиве. За дискретне променљиве, нпр. за класификацију текста, користи се другачија техника, као што је на пример функција раздаљине засноване на преклапању (или Хамингово растојање). У контексту експресије гена микрочип података, к-НН се користи у вези са коефицијентима као што су Пеарсон и Спеарман. Често се тачност класификације к-НН алгоритма може значајно унапредити ако се растојање учи специјалним алгортмима као што су или Анализа компоненти суседа.

Мана класичне класификације "гласање већине" дешава се када је класна дистрибуција искривљена. Тако примери учесталијих класа теже доминацији при предвиђању нових примера, јер теже да, упркос њиховом великом броју, буду чести међу к најближим суседа. Један од начина да се превазиђе овај проблем јесте да се дода тежина класфикацији, узимајући у обзир растојање од тест тачке до сваког од к најближих суседа. Класа (или вредност, у проблемима са регресијом) сваке од к најближих тачака множи се тежином пропорционалном инверзу растојања од дате тачке до тест тачке. Други начин превазилажења овог проблема огледа се у апстракцији репрезентације података. На пример, у самоорганизујућој мапи ( или скраћено SOM), ваки чвор је представник (средиште) скупине сличних тачака, без обзира на њихову густину у оригиналним тест подацима. К-НН се онда може применити на СОМ.

Избор параметара

Најбољи избор к зависи од података; уопште узев, веће вредности к смањују ефекат шумова на класификацијуEveritt, B. S., Landau, S., Leese, M. and Stahl, D. (2011). Chichester, UK., али су зато границе међу класама мање јасне. Добар одабир к може се извести различтим хеуристикама . Посебан случај јесте када је предвиђено да класа буде класа најближих тест примера (нпр. када је к = 1), назива се алгоритам најближег суседа.

Тачност к-НН алгоритма може бити озбиљно смањена уколико су присутне грешке или нерелевантне одлике или уколико одлике нису у складу са њиховом важношћу. Уложено је много напора у одабир или скалирање могућности за побољшање класификације. Нарочито је распрострањен приступ употребе еволутивних алгоритама за оптимизацију скалирања одлика. Други распрострањен приступ јесте скалирање одлика према заједничким информацијама тест података са тест класама.

У проблемима са бинарном (две класе) класификацијом, корисно је изабрати к такво да буде непаран број како не би долазило до застоја. Један од распрострањених начина одабира емпријиски оптималног броја к у овој поставци јесте одабир помоћу тзв. метода подизања система (.

Стопа грешке

Постоји много резултата о стопи гешке код класификатора најближих сусједа. Класификатор најближих сусједа је јако (то је за сваку заједничку дистрибуцију на ) конзистентан под условом да дивергира и конвергира нули .

Нека означава класификатор најближег сусједа базиран на тренинг сету величине . Под одређеним условима правилности, неумјереност ризика даје следећу асимптотичку експанзију

за неке константе и .

Избор нуди компромис између два услова приказана изнад, за које грешка најближих сусједа конвергира у Бајесову грешку по оптималној (минимакс) стопи .

Својства к-НН представља посебан случај променљивог пропусног опсега, , уједначеног језгра.

Наивна верзија алгоритма је једноставна за примену. Рачунају се растојања од тест примера до свих сачуваних примера, али је ово рачунски захтевно за велике скупове. Коришћењем одговарајућег алгоритма претраге најближег суседа к-НН постаје рачунски обрадив чак и за велике скупове. До сада су предложени многи алгоритми претраге најближег суседа; уопште узев, сви ови предлози настоје да смање број изведених израчунавања растојања.

к-НН има добре резултате када је у питању доследност. Како се количина података приближава бесконачности, алгоритам гарантује стопу грешке не лошију од двоструке Бејове стопе грешке (минимална остварива стопа грешке у односу на дистрибуцију/расподелу података). к-НН гарантује приближавање Бејовој стопи грешке за неку вредност к (где се к повећава као функција броја тачака). Могућа су бројна побољшања к-НН коришћењем графова близине.

Учење растојања

Учинак класификације алгоритма к најближих суседа често се може значајно побољшати помоћу (надгледаног) учења растојања. Распрострањени алгоритми јесу анализа компоненти суседства и ларге маргин неарест неигхбор. Ови надгледани алгоритми учења растојања користе означене информације да науче функцију метрике или псеудо-метрику.

Издвајање својстава Када су улазни подаци за алгоритам сувише велики да би се обрадили и када се мисли да је то сувишно (нпр. иста мерења и у стопама и у метрима), тада се улазни подаци трансформишу у редуковану репрезентацију скупа својстава (вектор одлика). Трансформација улазних података у скуп својстава зове се издвајање својстава. Уколико су издвојена својства пажљиво одабрана, очекује се да ће скуп својстава извући релевантне информације о улазним подацима у циљу извршавања жељеног задатка користећи се редукованим приказом уместо података у пуној величини. Издвајање својстава одвија се над необрађеним подацима пре примене к-НН алгоритма на измењене податке у просторној функцији.

Пример уобичајеног извршавања инструкција у рачунару за препознавања лица коришћењем к-НН обухватајући и извлачење и смањење димензија претпроцесирања (обично имплементиран помоћу OpenCV): препознавање лица Анализа праћења главних промена или пројекција на функцију простора, након које следи класификацијом к-НН

Смањење димензија За вишедимензионалне податке (нпр. са димензијом већом од 10), смањење димензија обично се примењује пре примене к-НН алгоритма како би се избегло проклетство димензионалности. Beyer, Kevin, et al.. 'When is “nearest neighbor” meaningful?. Database Theory—ICDT’99, 217-235|year 1999

Проклетство димензионалности у контексту к-НН алгоритма заправо значи да Еуклидско растојање није од помоћи у великим димензијама јер су скоро сви вектори на једнаком растојању у односу на упит претраге (замислите више тачака које мање-више леже на кругу са упитом који представља тачку у центру; растојање од упита до свих тачака у простору претраге је скоро једнако).

Издвајање својстава и смањење димензија могу се комбиновати у једном кораку коришћењем метода анализе главних компоненти (, или скраћено PCA), линеарне дискриминантне анализе (, или скраћено LDA), или анализе канонске корелације (, или скраћено CCA) технике као корака који претходи обради, након кога следи окупљање помоћу к-НН на функцију простора у простору смањене димензије. У машинском учењу овај процес се зове нискодимензионално уграђивање.Shaw, Blake, and Tony Jebara. 'Structure preserving embedding. Proceedings of the 26th Annual International Conference on Machine Learning. ACM,2009

За веома велике вишедимензионалне скупове података (нпр. када се трага за сличношћу на видео приказима уживо, ДНК подацима или вишедимензионалним редовима времена) извршавање брзе апроксимације к-НН претраге коришћењем , "случајних пројекција",Bingham, Ella, and Heikki Mannila. Random projection in dimensionality reduction: applications to image and text data. Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM |year 2001 "скица" или других вишедимензионалних техника претраге по сличности коришћењем кутије са алаткама може бити једина остварива опција.

Одређивање границе Правила најближег суседа имплицитно рачунају границу одлучивања међу скуповима. Могуће је израчунати границу одлучивања експлицитно и ефикасно тако да сложеност израчунавања остане у границама сложености.

Проширење к-НН за класификацију За разлику од класичних к-НН метода у којима се користе само најближи суседи објекта за процену чланства у групи, проширење к-НН метода, скраћено , користи двосмерну комуникацију за класификацију: узима у обзир не само ко су најближи суседи тест примера, већ и ко сматра тест пример својим најближим суседом. Идеја метода је додела чланства у групи објекту максимизовањем унутар-класне повезаности, што представља статистичко мерење повезаности међу свим класама. Емпиријске студије су показале да може значајно да побољша тачност класификације у поређењену са к-НН методом.

Смањење података Редукција података је један од најважнијих проблема у раду са огромним скуповима података. Обично су само неки од података потребни за тачну класификацију. Ти подаци се називају прототипови, а могуће их је пронаћи на следећи начин: Изаберите оне које не припадају класи, тј. тест податке који су нетачно класификовани помоћу к-НН (за дато к) Раздвојите остале податаке на два скупа: (i) прототипове који се користе за одлуке класификације и (ii) апсорбоване тачке које се могу правилно сврстати помоћу к-НН коришћењем прототипова. Апсорбоване тачке затим могу бити уклоњене из тест скупа.

Одабир оних који не припадају класи Тест примери окружени примерима других класа зову се класни диспаранти. Узроци појаве ових класних диспараната обухватају следеће: случајна грешка недовољно тест примера дате класе (појављује се изолован пример уместо скупа) недостатак важних својстава (класе су одвојене у другим димензијама за које не знамо) сувише тест примера других класа (неуравнотежених класа) које стварају непријатељску позадину за дату малу класу.