Алгоритам к најближих суседа

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

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

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

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

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

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

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

Алгоритам

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

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

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

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

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

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

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

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

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

Стопа грешке

Постоји много резултата о стопи гешке код класификатора k најближих сусједа. Класификатор k најближих сусједа је јако (то је за сваку заједничку дистрибуцију на $(X,Y)$) конзистентан под условом да $k:=k_{n}$ дивергира и $k_{n}/n$ конвергира нули $n\to \infty$.

Нека $C_{n}^{knn}$ означава класификатор k најближег сусједа базиран на тренинг сету величине n. Под одређеним условима правилности, неумјереност ризика даје следећу асимптотичку експанзију

${\mathcal {R}}_{\mathcal {R}}(C_{n}^{knn})-{\mathcal {R}}_{\mathcal {R}}(C^{Bayes})=\left\{B_{1}{\frac {1}{k}}+B_{2}\left({\frac {k}{n}}\right)^{4/d}\right\}\{1+o(1)\},$

за неке константе $B_{1}$ и $B_{2}$.

Избор $k^{*}=\lfloor Bn^{\frac {4}{d+4}}\rfloor$ нуди компромис између два услова приказана изнад, за које грешка $k^{*}$ најближих сусједа конвергира у Бајесову грешку по оптималној (минимакс) стопи ${\mathcal {O}}(n^{-{\frac {4}{d+4}}})$.

Својства

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

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

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

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

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

Издвајање својстава

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

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

1. енгл. Haar препознавање лица
2. Анализа праћења главних промена
3. енгл. Principal Component Analysis или енгл. Linear discriminant analysis пројекција на функцију простора, након које следи класификацијом к-НН

Смањење димензија

За вишедимензионалне податке (нпр. са димензијом већом од 10), смањење димензија обично се примењује пре примене к-НН алгоритма како би се избегло проклетство димензионалности.

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

Издвајање својстава и смањење димензија могу се комбиновати у једном кораку коришћењем метода анализе главних компоненти (енгл. principal component analysis, или скраћено PCA), линеарне дискриминантне анализе (енгл. linear discriminant analysis, или скраћено LDA), или анализе канонске корелације (енгл. canonical correlation analysis, или скраћено CCA) технике као корака који претходи обради, након кога следи окупљање помоћу к-НН на функцију простора у простору смањене димензије. У машинском учењу овај процес се зове нискодимензионално уграђивање.

За веома велике вишедимензионалне скупове података (нпр. када се трага за сличношћу на видео приказима уживо, ДНК подацима или вишедимензионалним редовима времена) извршавање брзе апроксимације к-НН претраге коришћењем енгл. locality sensitive hashing, "случајних пројекција", "скица" или других вишедимензионалних техника претраге по сличности коришћењем енгл. VLDB кутије са алаткама може бити једина остварива опција.

Одређивање границе

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

Проширење к-НН за класификацију

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

Смањење података

Редукција података је један од најважнијих проблема у раду са огромним скуповима података. Обично су само неки од података потребни за тачну класификацију. Ти подаци се називају прототипови, а могуће их је пронаћи на следећи начин:

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

Одабир оних који не припадају класи

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

• случајна грешка
• недовољно тест примера дате класе (појављује се изолован пример уместо скупа)
• недостатак важних својстава (класе су одвојене у другим димензијама за које не знамо)
• сувише тест примера других класа (неуравнотежених класа) које стварају непријатељску позадину за дату малу класу.

Класни диспаранти са к-НН производе шум. Могуће их је открити и одвојити за даље анализе. За дата два природна броја, к > r > 0, тест пример се назива (к, р) - НН класни диспарант уколико његови к најближих суседи обухватају више од r тест примера других класа.

CNN за смањење података

Збијени најближи сусед (енгл. CNN, Хартов алгоритам) редставља алгоритам намењен за смањење скупа података за к-НН класификацију. Он селектује скуп прототипова U из тест података, таквих да енгл. 1NN са U може да класификује примере скоро прецизно као што то енгл. 1NN чини са читавим скупом података.

Израчунавање размереграница.

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

За дати тест скуп X, CNN ради итеративно:

1. Претражите све елементе у X, трагајући за елементом x таквим да најближи протип из U има другачију ознаку у односу на x.
2. Уклоните x из X и додаје га у U
3. Поновите претрагу све док не постоје прототипи које је могуће додати у U.

Користите U уместо X за класификацију. Примери који нису прототипови зову се "апсорбоване" тачке.

Ефикасан начин представља претраживање тест примера у циљу смањења размере граница. Размера граница тест примера x се дефинише као

a(x) = ||x'-y||/||x-y||

где је ||x-y|| растојање од најближег примерка y који има другачију боју у односу на x, а ||x'-y|| је растојање од y до његовог најближег примера x' са истом ознаком као x.

Размера граница је у интервалу [0,1] јер ||x'-y|| никад не прелази ||x-y||. Овакво уређење даје предност границама класа за укључивање у скуп прототипова U. Тачка са другачијом ознаком у односу на x назива се спољашњом у односу на x. Израчунавање размере граница приказано је на слици са десне стране. Тачке са подацима означене су бојом: почетна тачка је x и њена ознака је црвена. Спољашње тачкле су плаве и зелене. Најближа спољашњој тачки од x јесте тачка y. Најближа црвеној y тачки јесте тачка x'. Размера граница a(x) = ||x'-y|| / ||x-y||is the attribute of the initial point x.

Испод је у низу слика приказан CNN. Дате су три класе (црвена, зелена и плава).

Слика 1: на почетку се у свакој класи налази 60 тачака. На Слици 2 приказана је класификациона мапа 1NN: сваки пиксел се класификује 1NN коришћењем свих података. На Слици 3 приказана је касификациона мапа 5NN. Беле површине одговарају некласификованим подручијма, где је 5NN гласање загушено (нпр., ако постоје две зелене, две црвене и једна плава тачка међу пет најближих суседа). На Слици 4 приказан је редукован скуп података. Крстићи представљају класне диспаранте одабране правилом (3,2)NN (сва три најблилижа суседа ових инстанци припадају другим класама); квадрати су прототипи, а празни кругови су апсорбоване тачке. Леви доњи угао показује број класних диспараната, прототипова и апсорбованих тачака за све три класе. Број прототипова варира од 15 до 20% за различите класе у овом примеру. На Слици 5 приказана је класификациона мапа 1NN са прототиповима веома слична почетном скупу података.

Слике су урађене помоћу Mirkes applet-a.

• CNN model reduction for k-NN classifiers
• 
  Fig. 1. The dataset.
• 
  Fig. 2. The 1NN classification map.
• 
  Fig. 3. The 5NN classification map.
• 
  Fig. 4. The CNN reduced dataset.
• 
  Fig. 5. The 1NN classification map based on the CNN extracted prototypes.

к-НН регресија

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

1. Израчунати Еуклидско или Махаланобисово растојање од тест упита до означених примера.
2. Поређати означене примере према растућим растојањима.
3. Тражи се хеуристички оптималан број к најближих суседа који се заснива на RMCE. Ово се ради помоћу унакрсном провером.
4. Израчунати инверзно растојање тежинског просека к најближих вишепроменљивих суседа.

Провера резултата

Матрица забуне или "матрица пододурања" често се користи као средство провере тачности к-НН класификације. Такође се могу користити и нешто робуснији методи као што је тест односа вероватноће.

Види још

• Класификатор најближег тежишта
• Алгоритам две најближе тачке

Литература

• Devroye, L., Gyorfi, L. & Lugosi, G. (1996). A probabilistic theory of pattern recognition. Springer. ISBN 978-0-387-94618-4. CS1 одржавање: Вишеструка имена: списак аутора (веза)
• „When Is "Nearest Neighbor" Meaningful?”. CiteSeerX 10.1.1.31.1422 . 
• Belur V. Dasarathy, ур. (1991). Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. ISBN 978-0-8186-8930-7. 
• Shakhnarovish; Darrell; Indyk, ур. (2005). Nearest-Neighbor Methods in Learning and Vision. MIT Press. ISBN 978-0-262-19547-8. 
• Mäkelä H, Pekkarinen A (26. 7. 2004). „Estimation of forest stand volumes by Landsat TM imagery and stand-level field-inventory data”. Forest Ecology and Management. 196 (2–3): 245—255. doi:10.1016/j.foreco.2004.02.049. 
• Fast k nearest neighbor search using GPU. In Proceedings of the CVPR Workshop on Computer Vision on GPU, Anchorage, Alaska, USA, June 2008. V. Garcia and E. Debreuve and M. Barlaud.
• Scholarpedia article on k-NN
• google-all-pairs-similarity-search