K-Nærmeste Naboer

Den k-nærmeste naboer (KNN)-algoritme er en ikke-parametrisk, overvåget læringsalgoritme, der bruges til klassifikations- og regressionsopgaver inden for maskinlæring. Den bygger på nærhedsbegrebet og antager, at lignende datapunkter er placeret tæt ved hinanden. KNN er en “doven læringsalgoritme”, hvilket betyder, at den ikke kræver en træningsfase, men i stedet gemmer hele træningsdatasættet og bruger det til at bestemme klassen eller værdien af nye datapunkter. Algoritmen forudsiger resultatet for et testdatapunkt ved at identificere de ‘k’ træningsdatapunkter, der er tættest på testdataene, og udleder output baseret på disse naboer. Denne metode er meget intuitiv og efterligner menneskets opfattelsesstrategier, der bygger på at sammenligne nye data med kendte eksempler.

Sådan fungerer KNN

KNN fungerer ved at identificere de ‘k’ nærmeste datapunkter til et givet forespørgselspunkt og bruge disse naboer til at lave en forudsigelse.

• Ved klassifikationsopgaver tildeler algoritmen forespørgselspunktet til den klasse, der er mest almindelig blandt dens ‘k’ nærmeste naboer, hvilket kaldes flertalsafstemning. Flertalsafstemning i KNN kan forstås som “pluralitetsafstemning”, når der er flere klasser, hvor forespørgselspunktet tildeles til den klasse med flest stemmer blandt de nærmeste naboer, selvom det ikke udgør et absolut flertal.
• Ved regressionsopgaver forudsiger den værdien ved at gennemsnitliggøre værdierne for de ‘k’ nærmeste naboer.

Nærheds- og lighedsprincipperne, som er centrale for menneskelig opfattelse, er også centrale for, hvordan KNN fungerer, da datapunkter, der ligger tæt i feature-rummet, antages at være mere ens og derfor sandsynligvis har ensartede resultater.

Afstandsmål

For at bestemme de nærmeste naboer bruger KNN forskellige afstandsmål, som er afgørende for dens ydeevne:

• Euklidisk afstand: Den rette linje-afstand mellem to punkter i et multidimensionalt rum, almindeligt brugt for kontinuerlige variable. Det er det mest almindelige afstandsmål for KNN og er særligt nyttigt, når dataene er tætte og kontinuerlige.
• Manhattan afstand: Også kendt som taxameterafstand, beregner afstanden ved at summere de absolutte forskelle mellem koordinaterne for to punkter. Det er nyttigt i gitterlignende scenarier, hvor bevægelser er begrænset til ortogonale retninger.
• Minkowski afstand: En generaliseret form af både Euklidisk og Manhattan afstand, parameteriseret med ‘p’. Hvis p=1, bliver det Manhattan afstand, og hvis p=2, bliver det Euklidisk afstand. Dette afstandsmål giver fleksibilitet afhængigt af den valgte ‘p’-værdi.
• Hamming afstand: Bruges til kategoriske data og tæller antallet af forskellige bits mellem to binære vektorer. Dette er særligt nyttigt i binære klassifikationsproblemer, hvor attributter har binære værdier.

Valg af korrekt ‘k’-værdi

Parameteren ‘k’ i KNN angiver antallet af naboer, der skal tages i betragtning. Valget af det rette ‘k’ er afgørende:

• Et lille ‘k’ kan føre til overfitting, hvor modellen bliver for følsom over for støj i træningsdataene og opfanger tilfældige mønstre, der ikke generaliserer.
• Et stort ‘k’ kan resultere i underfitting, hvor modellen bliver for generaliseret og ignorerer vigtige mønstre, hvilket fører til dårlig prædiktiv ydeevne.
• Typisk vælges ‘k’ gennem krydsvalidering og bør være et ulige tal for at undgå stemmelighed i klassifikationsbeslutninger. Valget af ‘k’ kan have stor betydning for modellens nøjagtighed og bestemmes ofte empirisk.

Fordele og ulemper

Fordele

• Simpel og intuitiv: Nem at forstå og implementere, hvilket gør den til et godt valg for begyndere. KNN’s enkelhed ligger i dens ligefremme tilgang, hvor testinstanser sammenlignes med gemte eksempler.
• Ingen træningsfase: KNN kræver ingen eksplicit træningsfase, da den laver forudsigelser med det gemte datasæt. Det betyder, at modellen kan opdateres blot ved at tilføje nye datapunkter til datasættet.
• Alsidig: Kan bruges til både klassifikation og regression, og dens anvendelse er bred på tværs af forskellige domæner. Den er også nyttig til multi-label klassifikationsopgaver.

Ulemper

• Beregningstung: Da den kræver at gemme og sammenligne hvert nyt datapunkt med hele datasættet, kan den være langsom og ressourcekrævende, især ved store datasæt. Tidskompleksiteten for KNN er O(n), hvor n er antallet af træningsprøver.
• Følsom over for outliers: Tilstedeværelsen af outliers kan have stor indflydelse på forudsigelserne, da disse afvigende punkter kan forvride resultaterne, især når ‘k’ er lille.
• Dimensionsforbandelse: I højdimensionelle rum kan algoritmens ydeevne forringes, da afstandene mellem datapunkter bliver mindre meningsfulde. Når dimensionaliteten øges, vokser rummets volumen, hvilket gør dataene mere spredte. Denne spredning gør det svært for KNN at finde nærmeste naboer effektivt.

Anvendelsesområder

KNN anvendes i flere forskellige felter på grund af sin enkelhed og effektivitet:

• Anbefalingssystemer: Bruges til at anbefale produkter eller indhold til brugere baseret på præferencer hos lignende brugere. KNN kan hjælpe med at identificere lignende brugere eller elementer ved at evaluere feature-lighed.
• Mønsterkendelse: Anvendes til håndskriftsgenkendelse og andre mønsterkendelsesopgaver, hvor den kan klassificere billeder ud fra ligheden i pixelværdier.
• Dataimputation: Nyttig til at udfylde manglende værdier i datasæt ved at estimere dem på baggrund af lignende datapunkter, hvilket bevarer datasættets integritet.
• Finans og sundhedsvæsen: Anvendes til aktiemarkedsforudsigelser, risikovurdering og medicinsk diagnostik ved at analysere ligheder i historiske data. Inden for sundhedsvæsenet kan den forudsige patientdiagnoser ved at sammenligne symptomer med kendte tilfælde.

Implementering i Python

KNN kan implementeres ved hjælp af biblioteker som scikit-learn i Python. Her er et grundlæggende eksempel på brug af KNN til klassifikation:

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

# Indlæs datasæt
iris = load_iris()
X, y = iris.data, iris.target

# Opdel data i trænings- og testdatasæt
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Initialisér KNN-klassifikator med k=3
knn = KNeighborsClassifier(n_neighbors=3)

# Træn modellen
knn.fit(X_train, y_train)

# Lav forudsigelser
y_pred = knn.predict(X_test)

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

K-Nærmeste Naboer (KNN) i videnskabelig forskning

K-Nærmeste Naboer (KNN) er en grundlæggende algoritme, der bruges i forskellige felter såsom multimedieinformationssøgning, datamining og maskinlæring, især i forbindelse med store datasæt.

Bemærkelsesværdige forskningsartikler:

• “Approximate k-NN Graph Construction: a Generic Online Approach” af Wan-Lei Zhao m.fl.:
  Præsenterer en effektiv metode til både tilnærmet k-nærmeste nabo-søgning og grafkonstruktion. Artiklen demonstrerer en dynamisk og gennemførlig løsning til håndtering af forskellige dataskalaer og dimensioner, der understøtter onlineopdateringer, hvilket ikke er muligt i mange eksisterende metoder. Læs mere.

• “Parallel Nearest Neighbors in Low Dimensions with Batch Updates” af Magdalen Dobson og Guy Blelloch:
  Introducerer parallelle algoritmer, der kombinerer kd-træ og Morton-ordning i en zd-træsstruktur, optimeret til lavdimensionelle data. Forfatterne viser, at deres tilgang er hurtigere end eksisterende algoritmer og opnår betydelige hastighedsforbedringer med parallel behandling. Zd-træet understøtter unikt parallelle batch-dynamiske opdateringer, hvilket er en første i k-nærmeste nabo-datastrukturer. Læs mere.

• “Twin Neural Network Improved k-Nearest Neighbor Regression” af Sebastian J. Wetzel:
  Udforsker en ny tilgang til k-nærmeste nabo-regression ved brug af tvillinge-neurale netværk. Denne metode fokuserer på at forudsige forskelle mellem regressionsmål, hvilket fører til forbedret ydeevne i forhold til traditionelle neurale netværk og k-nærmeste nabo-regressionsteknikker på små til mellemstore datasæt. Læs mere.