K nearest neighbors knn
Het KNN-algoritme
K-Nearest Neighbors (KNN) is een van de eenvoudigste machine learning-algoritmen. Het is een lazy learner: er wordt geen expliciet model getraind. In plaats daarvan worden alle trainingsdata opgeslagen. Bij het voorspellen van een nieuw datapunt wordt de afstand tot alle trainingspunten berekend, meestal met de Euclidische afstand. De k dichtstbijzijnde buren worden geselecteerd. Voor classificatie wordt de meerderheidsklasse onder deze buren gekozen; voor regressie wordt het gemiddelde van hun waarden genomen. De keuze van k is cruciaal. Een kleine k leidt tot een flexibele grens die gevoelig is voor ruis; een grote k leidt tot een vloeiender grens maar kan klassen vermengen. KNN is niet-parametrisch en kan complexe beslissingsgrenzen modelleren. Het is ook eenvoudig te implementeren en te begrijpen. Nadelen zijn de hoge rekenkosten bij voorspelling, vooral bij grote datasets, en de gevoeligheid voor de schaal van features. Normalisatie is daarom essentieel. Ook presteert KNN slecht bij hoogdimensionale data (vloek van dimensionaliteit), omdat afstanden dan minder betekenisvol worden. KNN wordt gebruikt in aanbevelingssystemen, patroonherkenning en medische diagnose.
Afstandsmaten en optimalisatie
De keuze van de afstandsmaat beïnvloedt de prestaties van KNN aanzienlijk. De Euclidische afstand is het meest gebruikelijk, maar Manhattan-afstand, Minkowski-afstand en cosine-afstand zijn alternatieven. Voor categorische data kan de Hamming-afstand worden gebruikt. Het aantal buren k wordt meestal bepaald via cross-validatie. Een oneven k vermijdt ties bij binaire classificatie. Om de rekenkosten te verlagen, kunnen datastructuren zoals KD-trees of Ball-trees worden gebruikt voor efficiënte nabuurazoek. Voor zeer grote datasets zijn benaderende methoden zoals Locality-Sensitive Hashing (LSH) nodig. KNN is ook gevoelig voor class imbalance: de meerderheidsklasse kan de stemmen domineren. Een oplossing is weighted voting, waarbij dichtere buren meer gewicht krijgen. Een ander probleem is dat KNN alle data in het geheugen moet houden, wat bij grote datasets problematisch is. Ondanks deze beperkingen blijft KNN populair vanwege de intuïtieve werking en de goede prestaties bij bepaalde problemen, zoals het herkennen van patronen in lage dimensies. Het wordt ook gebruikt als baseline voor complexere modellen.