K-nærmeste naboer

Den k-nærmeste naboer (KNN) algoritmen er en ikke-parametrisk, veiledet læringsalgoritme som brukes til klassifisering og regresjon i maskinlæring. Den er basert på konseptet om nærhet, og antar at lignende datapunkter befinner seg nær hverandre. KNN er en lat læringsalgoritme, som betyr at den ikke krever en treningsfase, men gjør prediksjoner ved å lagre hele treningsdatasettet og bruke det til å bestemme klassen eller verdien til nye datapunkter. Algoritmen predikerer utfallet for et testpunkt ved å identifisere de ‘k’ treningspunktene som er nærmest testpunktet, og trekker slutning basert på disse naboene. Denne metoden er svært intuitiv og etterligner menneskelige persepsjonsstrategier som baserer seg på å sammenligne nye data med kjente eksempler.

Hvordan KNN fungerer

KNN opererer ved å identifisere de ‘k’ nærmeste datapunktene til et gitt spørringspunkt og bruker disse naboene til å gjøre en prediksjon.

• Ved klassifiseringsoppgaver tildeler algoritmen spørringspunktet til den klassen som er mest vanlig blant dets ‘k’ nærmeste naboer, kjent som flertallsstemming. Flertallsstemming i KNN kan forstås som “pluralitetsstemming” når man har flere klasser, der spørringspunktet tildeles klassen med flest stemmer blant sine naboer, selv om det ikke utgjør et absolutt flertall.
• Ved regresjonsoppgaver predikerer den verdien ved å ta gjennomsnittet av verdiene til de ‘k’ nærmeste naboene.

Nærhets- og likhetsprinsippene, som er sentrale i menneskelig persepsjon, er også sentrale for hvordan KNN fungerer, siden datapunkter som er nært hverandre i egenskapsrommet antas å være mer like og derfor sannsynligvis har lignende utfall.

Avstandsmetrikker

For å bestemme de nærmeste naboene bruker KNN ulike avstandsmetrikker, som er avgjørende for ytelsen:

• Euklidsk avstand: Den rette linjen mellom to punkter i et flerdimensjonalt rom, ofte brukt for kontinuerlige variabler. Det er den vanligste avstandsmålingen for KNN og spesielt nyttig når dataene er tette og kontinuerlige.
• Manhattan-avstand: Også kjent som taxikab-avstand, beregner avstanden ved å summere de absolutte forskjellene mellom koordinatene til to punkter. Den er nyttig i rutemønster-scenarier hvor bevegelser er begrenset til ortogonale retninger.
• Minkowski-avstand: En generalisert form av både Euklidsk og Manhattan-avstand, parameterisert av ‘p’. Hvis p=1, blir det Manhattan-avstand, og hvis p=2, blir det Euklidsk avstand. Denne avstandsmålingen gir fleksibilitet avhengig av verdien på ‘p’ som velges.
• Hamming-avstand: Brukes for kategoriske data, og teller antall ulike biter mellom to binære vektorer. Dette er spesielt nyttig i binære klassifiseringsproblemer der attributtene har binære verdier.

Valg av riktig ‘k’-verdi

Parameteren ‘k’ i KNN representerer hvor mange naboer som skal vurderes. Riktig valg av ‘k’ er avgjørende:

• En liten ‘k’ kan føre til overtilpasning, der modellen blir for følsom for støy i treningsdataene og fanger opp tilfeldige mønstre som ikke generaliserer.
• En stor ‘k’ kan føre til undertilpasning, der modellen blir for generell og ignorerer viktige mønstre, noe som gir dårlig prediktiv ytelse.
• Vanligvis velges ‘k’ gjennom kryssvalidering og bør være et oddetall for å unngå uavgjort i klassifiseringsbeslutninger. Valget av ‘k’ kan ha stor innvirkning på modellens nøyaktighet og bestemmes ofte empirisk.

Fordeler og ulemper

Fordeler

• Enkel og intuitiv: Lett å forstå og implementere, noe som gjør den til et godt valg for nybegynnere. KNNs enkelhet ligger i dens direkte tilnærming med å sammenligne testeksempler mot lagrede eksempler.
• Ingen treningsfase: KNN krever ingen eksplisitt treningsfase, da den gir prediksjoner ved å bruke det lagrede datasettet. Dette betyr at modellen kan oppdateres enkelt ved å legge til nye datapunkter i datasettet.
• Allsidig: Kan brukes både til klassifisering og regresjon, og anvendelsen er bred på tvers av ulike domener. Den er også nyttig for fleretikett-klassifiseringsproblemer.

Ulemper

• Beregningstung: Fordi den må lagre og sammenligne hvert nytt datapunkt med hele datasettet, kan den være treg og ressurskrevende, spesielt med store datasett. Tidskompleksiteten til KNN er O(n), der n er antall treningsprøver.
• Følsom for uteliggere: Tilstedeværelsen av uteliggere kan påvirke prediksjonene betydelig, da disse avvikende punktene kan skjevfordele resultatene, spesielt når ‘k’ er liten.
• Forbannelsen ved dimensionalitet: I høydimensjonale rom kan algoritmens ytelse forringes fordi avstandene mellom datapunkter mister sin mening. Når dimensjonaliteten øker, øker volumet av rommet, og dataene blir spredte. Denne sparsiteten gjør det vanskelig for KNN å finne nærmeste naboer effektivt.

Bruksområder

KNN brukes i ulike fagfelt på grunn av sin enkelhet og effektivitet:

• Anbefalingssystemer: Brukes til å anbefale produkter eller innhold til brukere basert på preferansene til lignende brukere. KNN kan hjelpe med å identifisere lignende brukere eller objekter ved å evaluere egenskapslikhet.
• Mønster­gjenkjenning: Brukes til håndskriftgjenkjenning og annen mønstergjenkjenning, der den kan klassifisere bilder basert på likheten mellom pikselverdier.
• Dataimputering: Nyttig for å fylle manglende verdier i datasett ved å estimere dem basert på lignende datapunkter, og dermed opprettholde datasettets integritet.
• Finans og helse: Brukes i aksjemarkedsprognoser, risikovurdering og medisinsk diagnostikk ved å analysere likheter i historiske data. I helsesektoren kan den forutsi pasientdiagnoser ved å sammenligne symptomer mot kjente tilfeller.

Implementering i Python

KNN kan implementeres med biblioteker som scikit-learn i Python. Her er et grunnleggende eksempel på bruk av KNN til klassifisering:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score

# Last inn datasett
iris = load_iris()
X, y = iris.data, iris.target

# Del data i trenings- og testsett
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Initialiser KNN-klassifiserer med k=3
knn = KNeighborsClassifier(n_neighbors=3)

# Tren modellen
knn.fit(X_train, y_train)

# Gjør prediksjoner
y_pred = knn.predict(X_test)

# Evaluer nøyaktighet
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.2f}")

K-nærmeste naboer (KNN) i vitenskapelig forskning

K-nærmeste naboer (KNN) er en grunnleggende algoritme som brukes i flere fagområder som multimedia-informasjonssøk, datautvinning og maskinlæring, spesielt i forbindelse med store datasett.

Merkbare forskningsartikler:

• “Approximate k-NN Graph Construction: a Generic Online Approach” av Wan-Lei Zhao m.fl.:
  Presenterer en effektiv metode for både tilnærmet k-nærmeste nabo-søk og grafkonstruksjon. Artikkelen demonstrerer en dynamisk og gjennomførbar løsning for å håndtere ulike dataskalaer og dimensjoner, og støtter online-oppdateringer som ikke er mulig i mange eksisterende metoder. Les mer.

• “Parallel Nearest Neighbors in Low Dimensions with Batch Updates” av Magdalen Dobson og Guy Blelloch:
  Introduserer parallelle algoritmer som kombinerer kd-tre og Morton-orden til en zd-tre-struktur, optimalisert for lavdimensjonale data. Forfatterne viser at deres tilnærming er raskere enn eksisterende algoritmer og oppnår betydelig fartsøkning ved parallell prosessering. Zd-treet støtter unikt parallelle, batch-dynamiske oppdateringer, noe som er en nyvinning innen k-nærmeste nabo-datastrukturer. Les mer.

• “Twin Neural Network Improved k-Nearest Neighbor Regression” av Sebastian J. Wetzel:
  Utforsker en ny tilnærming til k-nærmeste nabo-regresjon ved bruk av tvilling-nevrale nettverk. Denne metoden fokuserer på å forutsi forskjeller mellom regresjonsmål, noe som gir bedre ytelse enn tradisjonelle nevrale nettverk og k-nærmeste nabo-regresjonsteknikker på små til mellomstore datasett. Les mer.