Redigerer K-NN

'''''k''-nærmeste naboer''' (''k''-NN) er en parameterfri [[algoritme]] innen klassifisering og [[Regresjonsanalyse|regresjon]].<ref>{{cite journal |last=Altman |first=N. S. |title=An introduction to kernel and nearest-neighbor nonparametric regression |url=https://archive.org/details/sim_american-statistician_1992-08_46_3/page/175 |journal=The American Statistician |volume=46 |issue=3 |year=1992 |pages=175–185}}</ref> Det er en [[Lat læring|lat]] algoritme, som betyr at den ikke lager noen klassifiseringsmodell a priori, men i stedet utfører jobben i det den får et dokument som skal klassifiseres.

I tekst klassifisering vil man ved bruk av ''k''-NN få tilbake den antatte klassen på ett gitt dokument, basert på majoriteten til de nærmeste naboene. I regresjon derimot vil man få verdien til objekter, som da er gjennomsnittet til alle verdiene til de ''k-''nærmeste naboene.

I begge disse tilfellene kan det være bra å vekte de forskjellige naboene sin innflytelse på resultatet etter distansen til subjektet. På denne måten vil de nærmeste naboene bety mer enn de som er lengre vekke.

== Algoritme ==
''k-''NN blir sett på som en av de simpleste algoritmene for klassifisering som finnes. Algoritmen har bare 2 steg;
#Plasser alle objekter i ett plan med dimensjoner som representerer hver attributt.
#Finn de ''k-''nærmeste naboene av objektet, ved bruk av en likhets-score.
#Gi objektet en klasse fra flertallet av de k-nærmeste naboene.

''k'' er et heltall som må bli bestemt for hver implementasjon. Hvilket tall ''k'' skal være, vil variere basert på for eksempel størrelsen på læresettet. Det er lurt å teste forskjellige verdier for ''k'', for å se hvilken som fungerer best. Man kan sjekke dette ved hjelp av et testsett, altså et sett med objekter som man vet den korrekte klassifiseringen på, men som man ikke gir til algoritmen. Dermed kjører man algoritmen på settet og ser hvor mange den klassifiserer rett.

De nærmeste naboene er tatt ut fra et «læresett», som er et sett med objekter som er korrekt klassifisert. Metoden kalles derfor en veiledet algoritme.<ref>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.</ref> For å finne ut hvilken av disse som er nærmest dokumentet som klassifiseres, er det vanlig å bruke [[trigonometriske funksjoner]]. Dette er en måte å sammenligne forskjellen mellom to vectorer, i dette tilfellet alle attributtene til dokumentene. Det går også an å bruke evklidsk avstand mellom to dokumenter. Når man har disse rangeringene, kan man også bruke avstandsvekting for å påvirke resultatet.<ref>Eiben, F., Witten H, I., & Hall A, M. (2011). Data Mining: Practical Machine Learning Tools and Techniques (3rd ed.).</ref>

En fordel med ''k-''NN er at den bare baserer seg på objektet den skal klassifisere, i stedet for en stor global klassifiseringsmodell.
Dette kan gjøre det mer nøyaktig enn for eksempel ved et [[beslutningstre]], da man bare vurderer egenskaper som er relevante for objektet.

== Dimensjonsreduksjon ==
Dersom datasettet man skal kjøre ''k-''NN på har for mange attributter, vil det føre til algoritmen får det vanskelig å klassifisere rett. Irrelevante/uviktige attributter kalles støy. Man kan løse problemet med støy med dimensjonsreduksjon. Dette gjør man ved å bruke en metrikk som: ''information gain'', ''mutual information'' eller ''chi-square'' for å nevne noen. Dette er matematiske funksjoner som vise hvor mye attributter betyr for beskrivelsen av en klasse. Ved å bruke disse til å finne de viktigste attributtene kan man redusere mengden attributter helt ned til 1-10% av original mengden uten å miste mye informasjon.<ref>Sebastiani, F. (2002). Machine Learning in Automated Text Categorization. Retrieved May 13, 2014, from http://nmis.isti.cnr.it/sebastiani/Publications/ACMCS02.pdf</ref>

''k-''NN er utsatt for [[apofeni#overtilpasning|''overfitting'']]. Dette betyr at dersom en bruker for mange attributter til å beskrive dokumentene, kan det bli for detaljert. Dette kan påvirke effektiviteten til algoritmen på dokumenter utenfor treningssettet da det er for spesifikt koblet mot treningssettet og dermed får problemer med nye dokumenter utenfor det.

== Finne rett ''k'' ==
Det er vanlig å kjøre algoritmen noen ganger med forskjellig ''k'' for å finne den optimale verdien til ''k'', men det er også mulig å bruke heuristiske metoder for gjøre det. En av disse er [[hyperparameteroptimisering]].

Et stort antall ''k'' er bra for å redusere støyen i datasettet, men betyr også at å skille mellom klassene blir vanskeligere for algoritmen.

Dersom man har ett datasett med bare to klasser, er det bra å velge ett oddetall som ''k'', da det ikke kan bli like mange av hver klasse i resultatet.<ref>Hall P, Park BU, Samworth RJ (2008). "Choice of neighbor order in nearest-neighbor classification". Annals of Statistics 36 (5): 2135–2152. doi:10.1214/07-AOS537.</ref>

== ''k''-NN i regresjon ==
''k''-NN kan bli brukt for å finne kontinuerlige variabler. En slik metode er å bruke ett [[vektet gjennomsnitt]], som er vektet med invers dokument frekvens.
#Regn ut Euclidean eller Mahalanobis distansen fra subjektet til objekter fra treningssettet.
#Ranger objektene etter distansen.
#Finn det optimale nummeret for k ved bruk av heuristikk. Dette kan man bruke kross-validasjon for.
#Kalkuler ett vektet gjennomsnitt av invers distansen med de k nærmeste objektene.

== Referanser ==
<references/>
== Litteratur ==
* Baeza-Yates, R. Ribeiro-Neto, B. "Modern information retrieval, the concepts and technology behind search". p.&nbsp;299-300.

{{Autoritetsdata}}

[[Kategori:Sannsynlighetsteori]]
[[Kategori:Algoritmer]]
[[Kategori:Kunstig intelligens]]