Википедија

Algoritam k najbližih suseda

U prepoznavanju obrazaca, k-najbližih suseda (ili skraćeno k-NN) predstavlja neparametarski metod koji se koristi za klasifikaciju i regresiju.[1] U oba slučaja, ulaz se sastoji od k najbližih test primera u funkciji prostora. Izlaz zavisi od toga da li se k-NN koristio za klasifikaciju ili regresiju:

  • U k-NN klasifikaciji, izlaz je član klase. Objekat se klasifikuje glasovima većine svojih suseda, tako da objekat bude raspoređen u klasu najčešću među svojim k najbližim susedima (k je pozitivan ceo broj, najčešće mali broj). Ako je k = 1, onda se objekat jednostavno dodeljuje klasi tog jednog najbližeg suseda.
  • U k-NN regresiji, izlaz predstavlja vrednost objekta. Ova vrednost predstavlja prosek vrednosti njegovih k najbližih suseda.

k-NN je tip učenja koje se zasniva na primerima, ili tzv. lenjo učenje, gde je aproksimacija funkcije lokalna i sva izračunavanja odlažu do klasifikacije. The k-NN algoritam je najjednostavniji od svih algoritama mašinskog učenja.

Dodela težine doprinosima suseda može biti od koristi i za klasifikaciju i za regresiju, tako da bliži susedi doprinose proseku više u odnosu na one udaljenije. Na primer, česta šema dodele je takva da se svakom od suseda dodeli težina od 1/d, gde d predstavlja rastojanje od suseda.[2]

Susedi se uzimaju iz skupa objekata za koje je klasa (za k-NN klasifikaciju) ili vrednost objekta (za k-NN regresiju) poznata. Ovo se može posmatrati kao test skup za algoritam iako eksplicitni test koraci nisu neophodni.

Mana k-NN algoritma je ta što je osetljiv na lokalne strukture podataka. Algoritam nema ništa zajedničko i ne treba ga mešati sa klasterizacijom klasterizacijom metodom k-srednjih vrednosti, što je druga popularna tehnika mašinskog učenja.

Algoritam uredi

 
Primer k-NN klasifikacije. Test primer (zeleni krug) treba da bude klasifikovan ili kao prva klasa plavih kvadrata ili kao druga klasa crvenih trouglova. Ako je k = 3 (puna linija kruga), onda je dodeljen drugoj klasi jer se unutar unutrašnjeg kruga nalaze 2 trougla i samo jedan kvadrat. Ako je k = 5 (isprekidana linija kruga), onda je dodeljen prvoj klasi (3 kvadrata u odnosu na 2 trougla unutar spoljašnjeg kruga).

Test primeri su vektori u multidimenzionalnoj funkciji prostora, gde svaki ima klasnu oznaku. Test faza algoritma sastoji se u skladištenju budućih vektrora i klasnih oznaka test primera.

U fazi klasifikacije, k je konstanta definisana od strane korisnika, a neoznačeni vektor (upit ili test primer) se klasifikuje dodelom oznake koja je najučestalija među k test primerima najbližim datom upitu.

Najčešće se koristi Euklidovo rastojanje za neprekidne promenljive. Za diskretne promenljive, npr. za klasifikaciju teksta, koristi se drugačija tehnika, kao što je na primer funkcija razdaljine zasnovane na preklapanju (ili Hamingovo rastojanje). U kontekstu ekspresije gena mikročip podataka, k-NN se koristi u vezi sa koeficijentima kao što su Pearson i Spearman.[3] Često se tačnost klasifikacije k-NN algoritma može značajno unaprediti ako se rastojanje uči specijalnim algortmima kao što su engl. Large Margin Nearest Neighbor ili Analiza komponenti suseda.

Mana klasične klasifikacije "glasanje većine" dešava se kada je klasna distribucija iskrivljena. Tako primeri učestalijih klasa teže dominaciji pri predviđanju novih primera, jer teže da, uprkos njihovom velikom broju, budu česti među k najbližim suseda.[4] Jedan od načina da se prevaziđe ovaj problem jeste da se doda težina klasfikaciji, uzimajući u obzir rastojanje od test tačke do svakog od k najbližih suseda. Klasa (ili vrednost, u problemima sa regresijom) svake od k najbližih tačaka množi se težinom proporcionalnom inverzu rastojanja od date tačke do test tačke. Drugi način prevazilaženja ovog problema ogleda se u apstrakciji reprezentacije podataka. Na primer, u samoorganizujućoj mapi (engl. self-organizing map ili skraćeno SOM), vaki čvor je predstavnik (središte) skupine sličnih tačaka, bez obzira na njihovu gustinu u originalnim test podacima. K-NN se onda može primeniti na SOM.

Izbor parametara uredi

Najbolji izbor k zavisi od podataka; uopšte uzev, veće vrednosti k smanjuju efekat šumova na klasifikaciju[5], ali su zato granice među klasama manje jasne. Dobar odabir k može se izvesti različtim heuristikama . Poseban slučaj jeste kada je predviđeno da klasa bude klasa najbližih test primera (npr. kada je k = 1), naziva se algoritam najbližeg suseda.

Tačnost k-NN algoritma može biti ozbiljno smanjena ukoliko su prisutne greške ili nerelevantne odlike ili ukoliko odlike nisu u skladu sa njihovom važnošću. Uloženo je mnogo napora u odabir ili skaliranje mogućnosti za poboljšanje klasifikacije. Naročito je rasprostranjen pristup upotrebe evolutivnih algoritama za optimizaciju skaliranja odlika.[6] Drugi rasprostranjen pristup jeste skaliranje odlika prema zajedničkim informacijama test podataka sa test klasama.

U problemima sa binarnom (dve klase) klasifikacijom, korisno je izabrati k takvo da bude neparan broj kako ne bi dolazilo do zastoja. Jedan od rasprostranjenih načina odabira emprijiski optimalnog broja k u ovoj postavci jeste odabir pomoću tzv. metoda podizanja sistema (engl. bootstrap.[7]

Stopa greške uredi

Postoji mnogo rezultata o stopi geške kod klasifikatora k najbližih susjeda.[8] Klasifikator k najbližih susjeda je jako (to je za svaku zajedničku distribuciju na  ) konzistentan pod uslovom da   divergira i   konvergira nuli  .

Neka   označava klasifikator k najbližeg susjeda baziran na trening setu veličine n. Pod određenim uslovima pravilnosti, neumjerenost rizika daje sledeću asimptotičku ekspanziju[9]

 

za neke konstante   i  .

Izbor   nudi kompromis između dva uslova prikazana iznad, za koje greška   najbližih susjeda konvergira u Bajesovu grešku po optimalnoj (minimaks) stopi  .

Svojstva uredi

k-NN predstavlja poseban slučaj promenljivog propusnog opsega, engl. kernel density "balloon" estimator, ujednačenog jezgra.[10] [11]

Naivna verzija algoritma je jednostavna za primenu. Računaju se rastojanja od test primera do svih sačuvanih primera, ali je ovo računski zahtevno za velike skupove. Korišćenjem odgovarajućeg algoritma pretrage najbližeg suseda k-NN postaje računski obradiv čak i za velike skupove. Do sada su predloženi mnogi algoritmi pretrage najbližeg suseda; uopšte uzev, svi ovi predlozi nastoje da smanje broj izvedenih izračunavanja rastojanja.

k-NN ima dobre rezultate kada je u pitanju doslednost. Kako se količina podataka približava beskonačnosti, algoritam garantuje stopu greške ne lošiju od dvostruke Bejove stope greške (minimalna ostvariva stopa greške u odnosu na distribuciju/raspodelu podataka).[12] k-NN garantuje približavanje Bejovoj stopi greške za neku vrednost k (gde se k povećava kao funkcija broja tačaka). Moguća su brojna poboljšanja k-NN korišćenjem grafova blizine.[13]

Učenje rastojanja uredi

Učinak klasifikacije algoritma k najbližih suseda često se može značajno poboljšati pomoću (nadgledanog) učenja rastojanja. Rasprostranjeni algoritmi jesu analiza komponenti susedstva i large margin nearest neighbor. Ovi nadgledani algoritmi učenja rastojanja koriste označene informacije da nauče funkciju metrike ili pseudo-metriku.

Izdvajanje svojstava uredi

Kada su ulazni podaci za algoritam suviše veliki da bi se obradili i kada se misli da je to suvišno (npr. ista merenja i u stopama i u metrima), tada se ulazni podaci transformišu u redukovanu reprezentaciju skupa svojstava (vektor odlika). Transformacija ulaznih podataka u skup svojstava zove se izdvajanje svojstava. Ukoliko su izdvojena svojstva pažljivo odabrana, očekuje se da će skup svojstava izvući relevantne informacije o ulaznim podacima u cilju izvršavanja željenog zadatka koristeći se redukovanim prikazom umesto podataka u punoj veličini. Izdvajanje svojstava odvija se nad neobrađenim podacima pre primene k-NN algoritma na izmenjene podatke u prostornoj funkciji.

Primer uobičajenog izvršavanja instrukcija u računaru za prepoznavanja lica korišćenjem k-NN obuhvatajući i izvlačenje i smanjenje dimenzija pretprocesiranja (obično implementiran pomoću OpenCV):

  1. engl. Haar prepoznavanje lica
  2. Analiza praćenja glavnih promena
  3. engl. Principal Component Analysis ili engl. Linear discriminant analysis projekcija na funkciju prostora, nakon koje sledi klasifikacijom k-NN

Smanjenje dimenzija uredi

Za višedimenzionalne podatke (npr. sa dimenzijom većom od 10), smanjenje dimenzija obično se primenjuje pre primene k-NN algoritma kako bi se izbeglo prokletstvo dimenzionalnosti. [14]

Prokletstvo dimenzionalnosti u kontekstu k-NN algoritma zapravo znači da Euklidsko rastojanje nije od pomoći u velikim dimenzijama jer su skoro svi vektori na jednakom rastojanju u odnosu na upit pretrage (zamislite više tačaka koje manje-više leže na krugu sa upitom koji predstavlja tačku u centru; rastojanje od upita do svih tačaka u prostoru pretrage je skoro jednako).

Izdvajanje svojstava i smanjenje dimenzija mogu se kombinovati u jednom koraku korišćenjem metoda analize glavnih komponenti (engl. principal component analysis, ili skraćeno PCA), linearne diskriminantne analize (engl. linear discriminant analysis, ili skraćeno LDA), ili analize kanonske korelacije (engl. canonical correlation analysis, ili skraćeno CCA) tehnike kao koraka koji prethodi obradi, nakon koga sledi okupljanje pomoću k-NN na funkciju prostora u prostoru smanjene dimenzije. U mašinskom učenju ovaj proces se zove niskodimenzionalno ugrađivanje.[15]

Za veoma velike višedimenzionalne skupove podataka (npr. kada se traga za sličnošću na video prikazima uživo, DNK podacima ili višedimenzionalnim redovima vremena) izvršavanje brze aproksimacije k-NN pretrage korišćenjem engl. locality sensitive hashing, "slučajnih projekcija",[16] "skica"[17] ili drugih višedimenzionalnih tehnika pretrage po sličnosti korišćenjem engl. VLDB kutije sa alatkama može biti jedina ostvariva opcija.

Određivanje granice uredi

Pravila najbližeg suseda implicitno računaju granicu odlučivanja među skupovima. Moguće je izračunati granicu odlučivanja eksplicitno i efikasno tako da složenost izračunavanja ostane u granicama složenosti.[18]

Proširenje k-NN za klasifikaciju uredi

Za razliku od klasičnih k-NN metoda u kojima se koriste samo najbliži susedi objekta za procenu članstva u grupi, proširenje k-NN metoda, skraćeno engl. ENN[19], koristi dvosmernu komunikaciju za klasifikaciju: uzima u obzir ne samo ko su najbliži susedi test primera, već i ko smatra test primer svojim najbližim susedom. Ideja engl. ENN metoda je dodela članstva u grupi objektu maksimizovanjem unutar-klasne povezanosti, što predstavlja statističko merenje povezanosti među svim klasama. Empirijske studije su pokazale da engl. ENN može značajno da poboljša tačnost klasifikacije u poređenjenu sa k-NN metodom.

Smanjenje podataka uredi

Redukcija podataka je jedan od najvažnijih problema u radu sa ogromnim skupovima podataka. Obično su samo neki od podataka potrebni za tačnu klasifikaciju. Ti podaci se nazivaju prototipovi, a moguće ih je pronaći na sledeći način:

  1. Izaberite one koje ne pripadaju klasi, tj. test podatke koji su netačno klasifikovani pomoću k-NN (za dato k)
  2. Razdvojite ostale podatake na dva skupa: (i) prototipove koji se koriste za odluke klasifikacije i (ii) apsorbovane tačke koje se mogu pravilno svrstati pomoću k-NN korišćenjem prototipova. Apsorbovane tačke zatim mogu biti uklonjene iz test skupa.

Odabir onih koji ne pripadaju klasi uredi

Test primeri okruženi primerima drugih klasa zovu se klasni disparanti. Uzroci pojave ovih klasnih disparanata obuhvataju sledeće:

  • slučajna greška
  • nedovoljno test primera date klase (pojavljuje se izolovan primer umesto skupa)
  • nedostatak važnih svojstava (klase su odvojene u drugim dimenzijama za koje ne znamo)
  • suviše test primera drugih klasa (neuravnoteženih klasa) koje stvaraju neprijateljsku pozadinu za datu malu klasu.

Klasni disparanti sa k-NN proizvode šum. Moguće ih je otkriti i odvojiti za dalje analize. Za data dva prirodna broja, k > r > 0, test primer se naziva (k, r) - NN klasni disparant ukoliko njegovi k najbližih susedi obuhvataju više od r test primera drugih klasa.

CNN za smanjenje podataka uredi

Zbijeni najbliži sused (engl. CNN, Hartov algoritam) redstavlja algoritam namenjen za smanjenje skupa podataka za k-NN klasifikaciju[20]. On selektuje skup prototipova U iz test podataka, takvih da engl. 1NN sa U može da klasifikuje primere skoro precizno kao što to engl. 1NN čini sa čitavim skupom podataka.

 
Izračunavanje razmeregranica.
 
Tri tipa tačaka: prototipovi, klasni disparanti i apsorbovane tačke.

Za dati test skup X, CNN radi iterativno:

  1. Pretražite sve elemente u X, tragajući za elementom x takvim da najbliži protip iz U ima drugačiju oznaku u odnosu na x.
  2. Uklonite x iz X i dodaje ga u U
  3. Ponovite pretragu sve dok ne postoje prototipi koje je moguće dodati u U.

Koristite U umesto X za klasifikaciju. Primeri koji nisu prototipovi zovu se "apsorbovane" tačke.

Efikasan način predstavlja pretraživanje test primera u cilju smanjenja razmere granica. Razmera granica test primera x se definiše kao

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

gde je ||x-y|| rastojanje od najbližeg primerka y koji ima drugačiju boju u odnosu na x, a ||x'-y|| je rastojanje od y do njegovog najbližeg primera x' sa istom oznakom kao x.

Razmera granica je u intervalu [0,1] jer ||x'-y|| nikad ne prelazi ||x-y||. Ovakvo uređenje daje prednost granicama klasa za uključivanje u skup prototipova U. Tačka sa drugačijom oznakom u odnosu na x naziva se spoljašnjom u odnosu na x. Izračunavanje razmere granica prikazano je na slici sa desne strane. Tačke sa podacima označene su bojom: početna tačka je x i njena oznaka je crvena. Spoljašnje tačkle su plave i zelene. Najbliža spoljašnjoj tački od x jeste tačka y. Najbliža crvenoj y tački jeste tačka x'. Razmera granica a(x) = ||x'-y|| / ||x-y||is the attribute of the initial point x.

Ispod je u nizu slika prikazan CNN. Date su tri klase (crvena, zelena i plava).

Slika 1: na početku se u svakoj klasi nalazi 60 tačaka. Na Slici 2 prikazana je klasifikaciona mapa 1NN: svaki piksel se klasifikuje 1NN korišćenjem svih podataka. Na Slici 3 prikazana je kasifikaciona mapa 5NN. Bele površine odgovaraju neklasifikovanim područijma, gde je 5NN glasanje zagušeno (npr., ako postoje dve zelene, dve crvene i jedna plava tačka među pet najbližih suseda). Na Slici 4 prikazan je redukovan skup podataka. Krstići predstavljaju klasne disparante odabrane pravilom (3,2)NN (sva tri najbliliža suseda ovih instanci pripadaju drugim klasama); kvadrati su prototipi, a prazni krugovi su apsorbovane tačke. Levi donji ugao pokazuje broj klasnih disparanata, prototipova i apsorbovanih tačaka za sve tri klase. Broj prototipova varira od 15 do 20% za različite klase u ovom primeru. Na Slici 5 prikazana je klasifikaciona mapa 1NN sa prototipovima veoma slična početnom skupu podataka.

Slike su urađene pomoću 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.

k-NN regresija uredi

U k-NN regresiji, k-NN algoritam se koristi za procenu neprekidnih promenljivih. Jedan takav algoritam koristi težinski prosek k najbližih suseda kojima je dodeljna funkcija težine inverzna njihovih distanci. Ovaj algoritam radi na sledeći način:

  1. Izračunati Euklidsko ili Mahalanobisovo rastojanje od test upita do označenih primera.
  2. Poređati označene primere prema rastućim rastojanjima.
  3. Traži se heuristički optimalan broj k najbližih suseda koji se zasniva na RMCE. Ovo se radi pomoću unakrsnom proverom.
  4. Izračunati inverzno rastojanje težinskog proseka k najbližih višepromenljivih suseda.

Provera rezultata uredi

Matrica zabune ili "matrica pododuranja" često se koristi kao sredstvo provere tačnosti k-NN klasifikacije. Takođe se mogu koristiti i nešto robusniji metodi kao što je test odnosa verovatnoće.

Vidi još uredi

Reference uredi

  1. ^ Altman, N. S. (1992). „An introduction to kernel and nearest-neighbor nonparametric regression”. The American Statistician. 46 (3): 175—185. S2CID 17002880. doi:10.1080/00031305.1992.10475879. hdl:1813/31637. 
  2. ^ This scheme is a generalization of linear interpolation.
  3. ^ Jaskowiak, P. A.; Campello, R. J. G. B. „Comparing Correlation Coefficients as Dissimilarity Measures for Cancer Classification in Gene Expression Data”. citeseerx.ist.psu.edu. Brazilian Symposium on Bioinformatics (BSB 2011). str. 1—8. CiteSeerX 10.1.1.208.993  . Pristupljeno 16. 10. 2014. 
  4. ^ D. Coomans; D.L. Massart (1982). „Alternative k-nearest neighbour rules in supervised pattern recognition : Part 1. k-Nearest neighbour classification by using alternative voting rules”. Analytica Chimica Acta. 136: 15—27. doi:10.1016/S0003-2670(01)95359-0. 
  5. ^ Everitt, B. S., Landau, S., Leese, M. and Stahl, D. (2011) Miscellaneous Clustering Methods, in Cluster Analysis, 5th Edition, John Wiley & Sons, Ltd, Chichester, UK.
  6. ^ Nigsch F, Bender A, van Buuren B, Tissen J, Nigsch E, Mitchell JB (2006). „Melting point prediction employing k-nearest neighbor algorithms and genetic parameter optimization”. Journal of Chemical Information and Modeling. 46 (6): 2412—2422. PMID 17125183. doi:10.1021/ci060149f. 
  7. ^ Hall P, Park BU, Samworth RJ (2008). „Choice of neighbor order in nearest-neighbor classification”. Annals of Statistics. 36 (5): 2135—2152. S2CID 14059866. doi:10.1214/07-AOS537. 
  8. ^ Devroye, L., Gyorfi, L. & Lugosi, G. (1996). A probabilistic theory of pattern recognition. Springer. ISBN 978-0-387-94618-4. 
  9. ^ J., Samworth R. (2012). „Optimal weighted nearest neighbour classifiers”. Annals of Statistics. 40 (5): 2733—2763. S2CID 88511688. doi:10.1214/12-AOS1049. 
  10. ^ D. G. Terrell; D. W. Scott (1992). „Variable kernel density estimation”. Annals of Statistics. 20 (3): 1236—1265. doi:10.1214/aos/1176348768. 
  11. ^ Mills, Peter (2012-08-09). „Efficient statistical classification of satellite measurements”. International Journal of Remote Sensing. 
  12. ^ Cover, T. M.; Hart, PE (1967). „Nearest neighbor pattern classification”. IEEE Transactions on Information Theory. 13 (1): 21—27. S2CID 5246200. doi:10.1109/TIT.1967.1053964. 
  13. ^ Toussaint, GT (2005). „Geometric proximity graphs for improving nearest neighbor methods in instance-based learning and data mining”. International Journal of Computational Geometry and Applications. 15 (2): 101—150. doi:10.1142/S0218195905001622. 
  14. ^ Beyer, Kevin, et al.. 'When is “nearest neighbor” meaningful?. Database Theory—ICDT’99, 217-235|year 1999
  15. ^ Shaw, Blake, and Tony Jebara. 'Structure preserving embedding. Proceedings of the 26th Annual International Conference on Machine Learning. ACM,2009
  16. ^ 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
  17. ^ Shasha, D. (2004). High Performance Discovery in Time Series. Berlin: Springer. ISBN 978-0-387-00857-8. 
  18. ^ Bremner D, Demaine E, Erickson J, Iacono J, Langerman S, Morin P, Toussaint G (2005). „Output-sensitive algorithms for computing nearest-neighbor decision boundaries”. Discrete and Computational Geometry. 33 (4): 593—604. doi:10.1007/s00454-004-1152-0. 
  19. ^ Tang B, He H (2015). „ENN: Extended Nearest Neighbor Method for Pattern Recognition [Research Frontier]”. IEEE Computational Intelligence Magazine. 10 (3): 52—60. S2CID 1569297. doi:10.1109/MCI.2015.2437512. 
  20. ^ Hart, P. (1968). „The condensed nearest neighbor rule (Corresp.)”. IEEE Transactions on Information Theory. 14 (3): 515—516. doi:10.1109/TIT.1968.1054155. 

Literatura uredi

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Алгоритам_к_најближих_суседа&oldid=27755432”