K-Nearest Neighbors

Het k-nearest neighbors (KNN) algoritme is een niet-parametrisch, supervised leeralgoritme dat wordt gebruikt voor classificatie- en regressietaken in machine learning. Het is gebaseerd op het concept van nabijheid, waarbij aangenomen wordt dat vergelijkbare datapunten dicht bij elkaar liggen. KNN is een lui leeralgoritme, wat betekent dat het geen trainingsfase vereist en voorspellingen maakt door de gehele trainingsdataset op te slaan en te gebruiken om de klasse of waarde van nieuwe datapunten te bepalen. Het algoritme voorspelt de uitkomst voor een testdatapunt door de ‘k’ trainingsdatapunten te identificeren die het dichtst bij het testpunt liggen, en leidt de output af op basis van deze buren. Deze methode is zeer intuïtief en bootst menselijke perceptiestrategieën na die vertrouwen op het vergelijken van nieuwe data met bekende voorbeelden.

Hoe KNN Werkt

KNN werkt door de ‘k’ dichtstbijzijnde datapunten bij een gegeven querypunt te identificeren en deze buren te gebruiken om een voorspelling te doen.

• Bij classificatietaken wijst het algoritme het querypunt toe aan de klasse die het meest voorkomt onder de ‘k’ dichtstbijzijnde buren, wat bekend staat als meerderheidstemming. Meerderheidstemming in KNN kan worden opgevat als “pluraliteitsstemming” bij meerdere klassen, waarbij het querypunt wordt toegewezen aan de klasse met het hoogste aantal onder zijn dichtstbijzijnde buren, zelfs als dit geen absolute meerderheid is.
• Bij regressietaken voorspelt het de waarde door het gemiddelde te nemen van de waarden van de ‘k’ dichtstbijzijnde buren.

De principes van nabijheid en gelijkenis, die centraal staan in menselijke waarneming, zijn ook essentieel voor hoe KNN functioneert: datapunten die dicht bij elkaar liggen in de feature-ruimte worden verondersteld meer op elkaar te lijken en dus waarschijnlijk vergelijkbare uitkomsten te hebben.

Afstandsmetingen

Om de dichtstbijzijnde buren te bepalen, gebruikt KNN verschillende afstandsmetingen, die cruciaal zijn voor de prestaties:

• Euclidische Afstand: De rechte lijn afstand tussen twee punten in een multidimensionale ruimte, vaak gebruikt voor continue variabelen. Het is de meest voorkomende afstandsmaat voor KNN en is vooral nuttig wanneer de data dicht en continu is.
• Manhattan Afstand: Ook wel taxiafstand genoemd, berekent de afstand door de absolute verschillen tussen de coördinaten van twee punten op te tellen. Dit is nuttig in rasterachtige situaties waar verplaatsingen beperkt zijn tot orthogonale richtingen.
• Minkowski Afstand: Een algemene vorm van zowel de Euclidische als Manhattan afstand, geparametriseerd door ‘p’. Als p=1 is het de Manhattan afstand, bij p=2 de Euclidische afstand. Deze afstandsmaat biedt flexibiliteit afhankelijk van de gekozen waarde van ‘p’.
• Hamming Afstand: Gebruikt voor categorische data, telt het aantal verschillende bits tussen twee binaire vectoren. Dit is vooral nuttig bij binaire classificatieproblemen waarbij attributen binaire waarden hebben.

De Juiste ‘k’ Waarde Kiezen

De parameter ‘k’ in KNN staat voor het aantal buren dat wordt meegenomen. Het kiezen van de juiste ‘k’ is cruciaal:

• Een kleine ‘k’ kan leiden tot overfitting, waarbij het model te gevoelig is voor ruis in de trainingsdata en willekeurige patronen oppikt die niet generaliseren.
• Een grote ‘k’ kan resulteren in underfitting, waarbij het model te algemeen wordt en belangrijke patronen negeert, wat leidt tot slechte voorspellende prestaties.
• Gewoonlijk wordt ‘k’ gekozen via cross-validatie en moet het een oneven getal zijn om gelijke stemmen bij classificatie te voorkomen. De keuze van ‘k’ heeft een aanzienlijke invloed op de nauwkeurigheid van het model en wordt vaak empirisch vastgesteld.

Voordelen en Nadelen

Voordelen

• Eenvoudig en Intuïtief: Makkelijk te begrijpen en te implementeren, waardoor het een goede keuze is voor beginners. De eenvoud van KNN ligt in de rechttoe rechtaan aanpak van het vergelijken van testgevallen met opgeslagen voorbeelden.
• Geen Trainingsfase: KNN vereist geen expliciete trainingsfase, omdat het voorspellingen maakt met behulp van de opgeslagen dataset. Dit betekent dat het model eenvoudig kan worden bijgewerkt door nieuwe datapunten aan de dataset toe te voegen.
• Veelzijdig: Kan worden gebruikt voor zowel classificatie- als regressietaken en is breed inzetbaar in verschillende domeinen. Ook nuttig bij multilabel classificatieproblemen.

Nadelen

• Computationeel Intensief: Omdat elk nieuw datapunt wordt vergeleken met de gehele dataset, kan het traag en resource-intensief zijn, vooral bij grote datasets. De tijdscomplexiteit van KNN is O(n), waarbij n het aantal trainingsvoorbeelden is.
• Gevoelig voor Uitschieters: De aanwezigheid van uitschieters kan de voorspellingen aanzienlijk beïnvloeden, omdat deze afwijkende punten de resultaten kunnen vertekenen, vooral bij een kleine ‘k’.
• Curse of Dimensionality: In hoog-dimensionale ruimtes kunnen de prestaties van het algoritme achteruitgaan, omdat de afstanden tussen datapunten minder betekenisvol worden. Naarmate de dimensionaliteit toeneemt, groeit het volume van de ruimte, waardoor data schaars wordt. Deze schaarste maakt het moeilijk voor KNN om effectief dichtstbijzijnde buren te vinden.

Toepassingsgebieden

KNN wordt in verschillende vakgebieden toegepast vanwege zijn eenvoud en effectiviteit:

• Aanbevelingssystemen: Gebruikt om producten of content aan te bevelen aan gebruikers op basis van de voorkeuren van vergelijkbare gebruikers. KNN kan helpen bij het identificeren van vergelijkbare gebruikers of items door de gelijkenis van features te evalueren.
• Patroonherkenning: Ingezet bij handschriftherkenning en andere patroonherkenningstaken, waarbij het afbeeldingen kan classificeren op basis van gelijkenis van pixelwaarden.
• Data-Imputatie: Nuttig voor het opvullen van ontbrekende waarden in datasets door deze te schatten op basis van vergelijkbare datapunten en zo de integriteit van de dataset te behouden.
• Financiën en Gezondheidszorg: Toegepast bij aandelenmarktvoorspellingen, risicoanalyse en medische diagnose door overeenkomsten in historische data te analyseren. In de gezondheidszorg kan het diagnoses voorspellen door symptomen te vergelijken met bekende gevallen.

Implementatie in Python

KNN kan worden geïmplementeerd met behulp van bibliotheken zoals scikit-learn in Python. Hier is een eenvoudig voorbeeld van KNN voor classificatie:

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

# Dataset laden
iris = load_iris()
X, y = iris.data, iris.target

# Data splitsen in trainings- en testset
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Initialiseer KNN-classifier met k=3
knn = KNeighborsClassifier(n_neighbors=3)

# Model trainen
knn.fit(X_train, y_train)

# Voorspellingen maken
y_pred = knn.predict(X_test)

# Nauwkeurigheid evalueren
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.2f}")

K-Nearest Neighbors (KNN) in Wetenschappelijk Onderzoek

K-Nearest Neighbors (KNN) is een fundamenteel algoritme dat wordt gebruikt in verschillende vakgebieden, zoals multimedia-informatieopslag, data mining en machine learning, met name bij grote datasets.

Opmerkelijke Wetenschappelijke Artikelen:

• “Approximate k-NN Graph Construction: a Generic Online Approach” door Wan-Lei Zhao et al.:
  Presenteert een effectieve methode voor zowel benaderende k-nearest neighbor zoekopdrachten als grafenconstructie. Het artikel toont een dynamische en haalbare oplossing voor het omgaan met diverse dataschalen en dimensies, met ondersteuning voor online updates die bij veel bestaande methoden niet mogelijk zijn. Lees meer.

• “Parallel Nearest Neighbors in Low Dimensions with Batch Updates” door Magdalen Dobson en Guy Blelloch:
  Introduceert parallelle algoritmes die kd-tree en Morton ordering combineren tot een zd-tree structuur, geoptimaliseerd voor laag-dimensionale data. De auteurs tonen aan dat hun aanpak sneller is dan bestaande algoritmes en aanzienlijke snelheidswinst behaalt met parallelle verwerking. De zd-tree ondersteunt als eerste parallelle batch-dynamische updates in k-nearest neighbor datastructuren. Lees meer.

• “Twin Neural Network Improved k-Nearest Neighbor Regression” door Sebastian J. Wetzel:
  Onderzoekt een nieuwe aanpak voor k-nearest neighbor regressie met behulp van twin neural networks. Deze methode richt zich op het voorspellen van verschillen tussen regressiedoelen, wat leidt tot betere prestaties dan traditionele neurale netwerken en k-nearest neighbor regressietechnieken op kleine tot middelgrote datasets. Lees meer.