k-närmaste grannar (kNN)

k-närmaste grannar har ingen träning alls: modellen är träningsdatan. För att klassificera en ny punkt:

1. Räkna avståndet till alla träningspunkter.
2. Ta de k närmaste.
3. Låt dem rösta (klassificering) eller ta medelvärdet (regression).

k litet (1–3): följer datan tätt, känsligt för brus och avvikare. k stort (50+): jämnare gräns, men detaljer suddas ut. Vid k = antalet punkter svarar modellen alltid majoritetsklassen.

Skalning är obligatoriskt. Har en feature enheten kronor (0–50 000) och en annan år (0–50) dominerar kronorna avståndet helt.

import numpy as np
from collections import Counter

def knn_predict(X_tr, y_tr, x, k=3):
    d = np.linalg.norm(X_tr - x, axis=1)        # avstånd till alla
    narmast = np.argsort(d)[:k]
    return Counter(y_tr[narmast]).most_common(1)[0][0]

X = np.array([[1, 1], [1.5, 2], [2, 1], [8, 8], [9, 9], [8.5, 9]])
y = np.array([0, 0, 0, 1, 1, 1])
print(knn_predict(X, y, np.array([2, 2]), k=3))   # 0
print(knn_predict(X, y, np.array([7, 8]), k=3))   # 1

Kostnaden: varje förutsägelse kräver avstånd till alla n träningspunkter — O(n·d). Med en miljon punkter i 768 dimensioner blir det för långsamt, och då används approximativa index (HNSW) i stället. Det är exakt vad en vektordatabas gör: kNN i stor skala.

Curse of dimensionality: i höga dimensioner blir alla punkter ungefär lika långt från varandra, och «närmast» slutar betyda något. Därför reducerar man ofta dimensionerna först.