Cei mai apropiați k vecini și distanțe

Stocați totul. Faceți predicții uitându-vă la vecini. Cel mai simplu algoritm care chiar funcționează.

Tip: Construire Limbaj: Python Cerințe preliminare: Faza 1 (lecția 14, Norme și distanțe) Durată: ~90 de minute

Obiective de învățare

• Să implementați de la zero clasificarea și regresia KNN, cu K configurabil și vot ponderat după distanță
• Să comparați distanțele L1, L2, cosinus și Minkowski și să selectați măsura potrivită unui anumit tip de date
• Să explicați blestemul dimensionalității și să demonstrați de ce KNN se poate degrada în spații cu multe dimensiuni
• Să construiți un arbore k-d pentru căutarea eficientă a vecinilor apropiați și să analizați când depășește căutarea prin forță brută

Problema

Aveți un set de date. Sosește un punct nou și trebuie să-l clasificați sau să-i preziceți valoarea. În loc să estimați parametri din date, ca în regresia liniară sau SVM, găsiți cele K puncte de antrenare cele mai apropiate de punctul nou și le lăsați să voteze.

Acesta este algoritmul celor mai apropiați k vecini, KNN. În varianta prin forță brută nu există o etapă de optimizare a parametrilor și nicio funcție de pierdere de minimizat. Stocați întregul set de antrenare și calculați distanțele în momentul predicției.

Pare prea simplu ca să funcționeze. Totuși, KNN este surprinzător de competitiv pentru numeroase probleme, în special cu seturi de date mici sau medii. Înțelegerea lui scoate în evidență concepte fundamentale: alegerea distanței, legată de Faza 1, lecția 14, blestemul dimensionalității și diferența dintre învățarea amânată și cea anticipată.

KNN apare și în IA modernă, uneori sub alte denumiri. Bazele de date vectoriale caută vecini apropiați printre reprezentări vectoriale. Generarea augmentată prin regăsire, RAG, găsește fragmentele de document cele mai apropiate. Sistemele de recomandare caută utilizatori sau articole similare. Principiul este același; scara, aproximațiile și structurile de date diferă.

Notă tehnică: „Fără antrenare” înseamnă aici fără estimarea unui model parametric. Metoda fit trebuie totuși să valideze și să stocheze datele, să ajusteze transformările de preprocesare și, pentru căutarea arborescentă, să construiască un index.

Conceptul

Cum funcționează KNN

Pornind de la un set de puncte etichetate și de la un punct nou de interogare:

1. Calculați distanța dintre interogare și fiecare punct din set
2. Sortați punctele după distanță
3. Luați cele mai apropiate K puncte
4. Pentru clasificare, aplicați votul majoritar al celor K vecini
5. Pentru regresie, calculați media sau media ponderată a valorilor celor K vecini

Acesta este întregul algoritm de bază: fără ajustarea parametrilor, coborâre pe gradient sau epoci.

Alegerea lui K

K este hiperparametrul central, dar nu singurul: distanța, ponderarea, preprocesarea și regula de departajare contează de asemenea. K controlează compromisul deplasare–varianță:

K	Comportament
K = 1	Frontiera urmărește fiecare punct; eroare de antrenare zero dacă fiecare punct este propriul vecin și nu există duplicate cu etichete contradictorii; varianță mare, risc de supraînvățare
K mic, de exemplu 3–5	Sensibil la structura locală; poate surprinde frontiere complexe
K mare	Frontiere mai netede și uneori robuste la zgomot; poate conduce la subînvățare
K = N	În KNN neponderat, prezice clasa majoritară pentru orice punct sau media globală în regresie; deplasare mare

Regula K = sqrt(N) este doar un punct de pornire euristic pentru un set cu N puncte. Selectați K prin validare încrucișată în cadrul întregului pipeline. Un K impar reduce unele egalități în clasificarea binară neponderată, dar nu elimină toate departajările, de exemplu în cazul distanțelor identice sau al mai multor clase.

Măsuri de distanță

Funcția de distanță definește sensul noțiunii „aproape”. Măsuri diferite pot produce vecini și predicții diferite.

L2, distanța euclidiană, este alegerea implicită obișnuită. Ea măsoară distanța în linie dreaptă.

d(a, b) = sqrt(sum((a_i - b_i)^2))

Este sensibilă la scara caracteristicilor. Standardizați sau normalizați caracteristicile atunci când unitățile și scările lor nu trebuie să determine distanța; ajustați transformarea numai pe datele de antrenare.

L1, distanța Manhattan, însumează diferențele absolute. La nivelul contribuției fiecărei coordonate, este mai puțin sensibilă decât L2 la diferențe foarte mari, deoarece nu le ridică la pătrat.

d(a, b) = sum(|a_i - b_i|)

Distanța cosinus măsoară diferența de direcție dintre vectori și nu păstrează informația despre mărime. Este frecvent utilă pentru text și reprezentări vectoriale atunci când direcția este relevantă, iar norma nu este.

d(a, b) = 1 - (a . b) / (||a|| * ||b||)

Minkowski generalizează L1 și L2 prin parametrul p.

d(a, b) = (sum(|a_i - b_i|^p))^(1/p)

p=1: Manhattan
p=2: Euclidiană
p->inf: Cebîșev (diferența absolută maximă)

Notă tehnică: Pentru p >= 1, distanța Minkowski este o metrică; pentru 0 < p < 1, inegalitatea triunghiului nu mai este garantată. De asemenea, expresia 1 - cosine_similarity nu satisface în general inegalitatea triunghiului, deși este numită în mod uzual „distanță cosinus”. Vectorii nuli necesită o convenție explicită.

Alegerea depinde de date și trebuie validată:

Tip de date	Alegere inițială	Motiv
Caracteristici numerice cu scări comparabile	L2, euclidiană	Alegere naturală pentru geometrie spațială
Caracteristici numerice cu diferențe mari pe coordonate	L1, Manhattan	Nu amplifică pătratic diferențele mari
Reprezentări de text	Cosinus	Compară direcția independent de normă
Date rare cu multe dimensiuni	Cosinus sau L1	Pot fi mai potrivite decât L2, în funcție de semnificația valorilor
Tipuri mixte	Distanță personalizată	Combină măsuri și ponderi potrivite fiecărui tip de caracteristică

Nicio alegere din tabel nu este universal optimă; transformați caracteristicile și selectați distanța pe date de validare reprezentative.

KNN ponderat

KNN standard acordă aceeași pondere tuturor celor K vecini. Totuși, un vecin aflat la distanța 0,1 poate fi mai relevant decât unul aflat la distanța 5,0.

KNN ponderat după distanță atribuie fiecărui vecin o pondere invers proporțională cu distanța:

pondere_i = 1 / (distanță_i + epsilon)

Pentru clasificare: vot ponderat
Pentru regresie:      medie ponderată = sum(w_i * y_i) / sum(w_i)

Epsilon previne împărțirea la zero atunci când punctul de interogare coincide exact cu un punct de antrenare. O altă convenție uzuală este ca vecinii aflați la distanță zero să primească exclusiv votul.

Ponderarea poate reduce influența vecinilor îndepărtați și uneori sensibilitatea față de K, dar nu elimină necesitatea validării lui K și a funcției de ponderare.

Blestemul dimensionalității

KNN se poate degrada în spații cu multe dimensiuni. Manifestarea exactă depinde de distribuția datelor, metrică, numărul de eșantioane și dimensionalitatea intrinsecă.

Problema 1: concentrarea distanțelor. Pentru numeroase distribuții și norme, odată cu creșterea dimensionalității, contrastul relativ dintre vecinii apropiați și cei îndepărtați se reduce. Toate punctele pot părea aproape la fel de „departe” de interogare.

Exemplu ilustrativ pentru puncte uniforme aleatorii:

d=2:    max_dist / min_dist = poate varia mult
d=100:  max_dist / min_dist poate fi aproape de 1
d=1000: max_dist / min_dist poate fi și mai aproape de 1

Când distanțele sunt aproape egale, noțiunea „cel mai apropiat” are un contrast redus.

Notă tehnică: Valorile numerice 1,01 și 1,001 din sursă nu sunt universale și depind inclusiv de numărul de puncte și de definiția distanței. Experimentul trebuie să specifice distribuția, dimensiunea eșantionului, norma și statistica folosită.

Problema 2: volumul necesar crește. Pentru a include K vecini sau o fracțiune fixă din date, raza de căutare poate trebui să acopere o parte tot mai mare din intervalul fiecărei caracteristici. „Vecinătatea” devine mai puțin locală.

Problema 3: geometria hipercubului. Raportul dintre volumul sferei înscrise și cel al hipercubului unitate tinde la zero când dimensiunea crește. Afirmația informală că „domină colțurile” trebuie înțeleasă prin această geometrie și prin măsura aleasă, nu ca o regulă independentă de distribuție.

Consecința practică nu este un prag universal de 20–50 de caracteristici. Performanța depinde de dimensionalitatea intrinsecă, densitatea eșantionării, caracteristicile irelevante și metrică. Folosiți selecția caracteristicilor, PCA, TruncatedSVD pentru date rare sau o reprezentare învățată și validați întregul pipeline. UMAP poate fi evaluat în anumite fluxuri, dar t-SNE este conceput în primul rând pentru vizualizare și nu trebuie presupus drept preprocesor predictiv general.

Arbori k-d: căutarea rapidă a vecinilor apropiați

KNN prin forță brută calculează distanța de la interogare la fiecare punct de antrenare. Costul unei interogări este O(n * d). Pentru seturi mari poate fi prea lent.

Un arbore k-d partiționează recursiv spațiul de-a lungul axelor caracteristicilor. La fiecare nivel, împarte punctele după valoarea mediană a unei dimensiuni.

Pentru a găsi vecinul cel mai apropiat, parcurgeți arborele până la frunza care conține interogarea, apoi reveniți și verificați partițiile vecine numai dacă pot conține puncte mai apropiate.

În dimensiuni mici și pentru date favorabile, numărul mediu de comparații al unei interogări poate avea scara O(log n). Nu este o garanție: cazul nefavorabil ajunge la O(n), iar în dimensiuni mai mari revenirea elimină tot mai puține ramuri. Construcția arborelui are și ea un cost, care trebuie amortizat prin mai multe interogări.

Arbori Ball: o alternativă pentru dimensiuni moderate

Arborii Ball partiționează datele în hipersfere imbricate, în locul cutiilor aliniate cu axele. Fiecare nod definește o bilă, prin centru și rază, care conține toate punctele subarborelui.

Avantaje posibile față de arborii k-d:

• Pot funcționa mai bine în unele spații de dimensiune moderată sau cu structură intrinsecă favorabilă
• Pot gestiona structuri care nu sunt aliniate cu axele
• Volumele de delimitare pot permite eliminarea mai multor ramuri în anumite distribuții

Nu există un prag universal „până la 50 de dimensiuni”. Performanța depinde de n, d, metrica folosită, dimensiunea frunzelor, structura datelor și numărul de interogări. Atât arborii k-d, cât și Ball oferă căutare exactă în configurațiile descrise. La scară foarte mare, cu milioane de puncte și sute de dimensiuni, se folosesc adesea metode de căutare aproximativă precum HNSW, IVF și cuantizarea produsului, acceptând un compromis între rapel, latență și memorie. Aceste metode sunt introduse în Faza 1, lecția 14.

Învățare amânată și învățare anticipată

KNN este un algoritm de învățare amânată (lazy learning): varianta brută estimează foarte puțin în etapa fit, iar cea mai mare parte a calculului are loc la predicție. Majoritatea celorlalți algoritmi, precum regresia liniară, SVM și rețelele neuronale, sunt de învățare anticipată (eager learning): efectuează calcule pentru a construi un model compact, apoi predicțiile sunt de obicei rapide.

Aspect	Învățare amânată, KNN brut	Învățare anticipată, SVM sau rețea neuronală
Etapa de antrenare	Stocare și validare O(n*d); un index adaugă cost de construcție	Optimizare dependentă de algoritm, nu universal O(n * epoci)
Predicție	O(n*d) per interogare prin forță brută	Depinde de arhitectură și numărul de parametri activi
Memorie la predicție	Întregul set de antrenare și eventual indexul	Parametrii și starea necesară modelului
Adaptare la date noi	Adăugare simplă în varianta brută; indexurile pot necesita actualizare sau reconstrucție	De regulă necesită actualizare sau reantrenare
Frontieră de decizie	Implicită, determinată la interogare	Fixată de parametrii antrenați până la următoarea actualizare

Învățarea amânată poate fi potrivită atunci când:

• Setul se schimbă frecvent, iar varianta brută permite adăugarea sau eliminarea punctelor
• Aveți nevoie de foarte puține interogări și construcția unui model sau index nu s-ar amortiza
• Doriți o etapă de ajustare minimală
• Setul este suficient de mic pentru ca forța brută să fie rapidă

KNN pentru regresie

În locul votului majoritar, regresia KNN calculează media valorilor-țintă ale celor K vecini.

predicție = (1/K) * sum(y_i pentru i dintre cei K vecini apropiați)

Sau cu ponderare după distanță:
predicție = sum(w_i * y_i) / sum(w_i)
unde w_i = 1 / (distanță_i + epsilon)

Regresia KNN neponderată produce predicții constante pe regiuni. Ponderarea după distanță poate face variația mai graduală în interiorul unei mulțimi de vecini, însă schimbarea vecinilor poate introduce în continuare praguri sau neregularități. Predicția este o combinație a țintelor vecinilor și nu extrapolează în afara intervalului țintelor de antrenare: dacă toate sunt între 0 și 100, KNN nu va prezice 200.

knn-smoothness

Construiți

Pasul 1: funcții de distanță

Implementați distanțele L1, L2, cosinus și Minkowski. Acestea se leagă direct de Faza 1, lecția 14.

import math

def l2_distance(a, b):
    return math.sqrt(sum((ai - bi) ** 2 for ai, bi in zip(a, b)))

def l1_distance(a, b):
    return sum(abs(ai - bi) for ai, bi in zip(a, b))

def cosine_distance(a, b):
    dot_val = sum(ai * bi for ai, bi in zip(a, b))
    norm_a = math.sqrt(sum(ai ** 2 for ai in a))
    norm_b = math.sqrt(sum(bi ** 2 for bi in b))
    if norm_a == 0 or norm_b == 0:
        return 1.0
    return 1.0 - dot_val / (norm_a * norm_b)

def minkowski_distance(a, b, p=2):
    if p == float('inf'):
        return max(abs(ai - bi) for ai, bi in zip(a, b))
    return sum(abs(ai - bi) ** p for ai, bi in zip(a, b)) ** (1 / p)

Notă tehnică: Implementarea didactică folosește zip, care ignoră fără avertisment coordonatele suplimentare dacă vectorii au lungimi diferite. Validați dimensiunile și p >= 1. Pentru cosinus, întoarcerea valorii 1 în cazul unui vector nul este o convenție de implementare, nu o consecință a formulei, care este nedefinită.

Pasul 2: clasificator și regressor KNN

Construiți KNN cu K, funcție de distanță și ponderare opțională configurabile.

class KNN:
    def __init__(self, k=5, distance_fn=l2_distance, weighted=False,
                 task="classification"):
        self.k = k
        self.distance_fn = distance_fn
        self.weighted = weighted
        self.task = task
        self.X_train = None
        self.y_train = None

    def fit(self, X, y):
        self.X_train = X
        self.y_train = y

    def predict(self, X):
        return [self._predict_one(x) for x in X]

Notă tehnică: Fragmentul nu definește metoda _predict_one, deci clasa nu poate face singură predicții. Implementarea completă se află în code/knn.py, conform sursei. Aceasta trebuie să valideze cel puțin 1 <= K <= n, lungimile datelor, sarcina și regula de departajare.

Pasul 3: arbore k-d pentru căutare eficientă

Construiți de la zero un arbore k-d care împarte recursiv punctele după mediana fiecărei dimensiuni.

class KDTree:
    def __init__(self, X, indices=None, depth=0):
        # Recursively partition the data
        self.axis = depth % len(X[0])
        # Split on median of the current axis
        ...

    def query(self, point, k=1):
        # Traverse to leaf, then backtrack
        ...

Acesta este pseudocod Python executabil sintactic, dar ... nu construiește nodurile și nu implementează interogarea. Consultați code/knn.py pentru implementarea completă, metodele auxiliare și demonstrații.

Pasul 4: scalarea caracteristicilor

KNN necesită controlul scării, deoarece distanțele sunt sensibile la mărimea numerică a caracteristicilor. O caracteristică între 0 și 1.000 poate domina una între 0 și 1, chiar dacă nu este mai importantă.

def standardize(X):
    n = len(X)
    d = len(X[0])
    means = [sum(X[i][j] for i in range(n)) / n for j in range(d)]
    stds = [
        max(1e-10, (sum((X[i][j] - means[j]) ** 2 for i in range(n)) / n) ** 0.5)
        for j in range(d)
    ]
    return [[((X[i][j] - means[j]) / stds[j]) for j in range(d)] for i in range(n)], means, stds

Notă tehnică: Calculați mediile și abaterile numai pe setul de antrenare, apoi reutilizați aceiași parametri pentru validare, testare și producție. Apelarea separată a funcției pe test ar produce scurgere de date și coordonate incompatibile. Codul presupune, de asemenea, un set nevid și rânduri cu aceeași lungime.

Folosiți

Cu scikit-learn:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier(n_neighbors=5, metric="euclidean")),
])
clf.fit(X_train, y_train)
print(f"Accuracy: {clf.score(X_test, y_test):.4f}")

Cu valoarea implicită algorithm="auto", scikit-learn alege între arbore k-d, arbore Ball și forță brută printr-o euristică bazată pe date, metrică, dimensiune și K. Pentru date rare, metrici neacceptate de arbori sau dimensionalitate mare, poate alege forța brută. Controlați alegerea prin parametrul algorithm și măsurați performanța pe sarcina reală.

Pentru căutarea vecinilor la scară mare, cu milioane de vectori, puteți folosi FAISS, Annoy sau o bază de date vectorială:

import faiss

index = faiss.IndexFlatL2(dimension)
index.add(embeddings)
distances, indices = index.search(query_vectors, k=5)

Notă tehnică: faiss.IndexFlatL2 efectuează o căutare L2 exactă și exhaustivă, nu una aproximativă. Pentru compromisuri de tip ANN se aleg alte indexuri FAISS, de exemplu IVF, HNSW sau variante cu cuantizare, iar calitatea se măsoară prin rapel față de vecinii exacți.

Exerciții

1. Implementați clasificarea KNN pe un set 2D cu trei clase. Reprezentați frontiera de decizie pentru K=1, K=5, K=15 și K=N. Observați trecerea de la supraînvățare la subînvățare.

2. Generați 1.000 de puncte aleatorii în 2, 5, 10, 50, 100 și 500 de dimensiuni. Pentru fiecare dimensionalitate, calculați raportul dintre distanța maximă și cea minimă între perechi distincte. Excludeți diagonala cu distanță zero și raportați distribuția, norma și sămânța aleatoare. Reprezentați raportul în funcție de dimensionalitate pentru a vizualiza concentrarea distanțelor.

3. Comparați distanțele L1, L2 și cosinus pentru KNN într-o problemă de clasificare a textului, folosind vectori TF-IDF. Care oferă cea mai bună acuratețe pe validare? Explicați de ce cosinus poate funcționa bine pentru text, fără a presupune că va câștiga întotdeauna.

4. Implementați un arbore k-d și măsurați timpul de interogare față de forța brută pentru seturi de 1.000, 10.000 și 100.000 de puncte în 2D, 10D și 50D. Includeți separat timpul de construire și repetați suficiente interogări. La ce dimensionalitate și pentru câte interogări încetează arborele să fie mai rapid?

5. Construiți un regressor KNN ponderat pentru y = sin(x) + zgomot. Comparați-l cu KNN neponderat pentru K=3, 10 și 30. Evaluați netezimea și eroarea pe o grilă independentă; verificați empiric dacă ponderarea produce predicții mai netede, deoarece rezultatul nu este garantat pentru orice eșantion și funcție de ponderare.

Termeni-cheie

Termen	Ce înseamnă de fapt
Cei mai apropiați k vecini	Algoritm neparametric care prezice găsind cele mai apropiate K puncte de antrenare față de o interogare
Învățare amânată (lazy learning)	Fără estimarea anticipată a unui model compact; cea mai mare parte a calculului are loc la predicție, iar KNN este exemplul canonic
Învățare anticipată (eager learning)	Calcul în etapa de antrenare pentru construirea unui model; majoritatea algoritmilor ML urmează această abordare
Blestemul dimensionalității	Familie de fenomene prin care volumul, densitatea eșantionării și contrastul distanțelor se comportă nefavorabil când crește dimensiunea
Arbore k-d	Arbore binar care partiționează recursiv spațiul după axele caracteristicilor; poate oferi interogări apropiate de O(log n) în condiții favorabile de dimensiune mică
Arbore Ball	Arbore de hipersfere imbricate; poate depăși arborele k-d pentru anumite date și metrici, fără un prag dimensional universal
KNN ponderat	Variantă în care vecinii primesc ponderi în funcție de distanță, astfel încât cei apropiați pot influența mai mult predicția
Scalarea caracteristicilor	Transformarea caracteristicilor la scări comparabile, ajustată pe datele de antrenare; esențială când scara brută nu trebuie să determine distanța
Vot majoritar	Clasificare prin numărarea clasei celei mai frecvente între K vecini, cu o regulă explicită de departajare
Căutare prin forță brută	Calcularea distanței față de fiecare punct de antrenare; O(n*d) pentru o interogare, exactă și adesea competitivă pentru seturi mici
Vecin aproximativ cel mai apropiat	Metode precum HNSW, LSH și IVF, care găsesc rapid vecini aproximativi în schimbul unui posibil rapel sub 100%
Diagramă Voronoi	Partiționare a spațiului în regiuni ale punctelor mai apropiate de un anumit punct de antrenare decât de oricare altul; KNN cu K=1 induce frontiere Voronoi

Lecturi suplimentare

• Cover & Hart: Nearest Neighbor Pattern Classification (1967) — lucrarea fundamentală despre 1-NN; în regimul asimptotic și în ipotezele sale, riscul limită este mărginit prin riscul Bayes, inclusiv de două ori acesta ca limită mai simplă
• Friedman, Bentley, Finkel: An Algorithm for Finding Best Matches in Logarithmic Expected Time (1977) — lucrare timpurie despre căutarea eficientă prin arbori k-d
• Beyer et al.: When Is “Nearest Neighbor” Meaningful? (1999) — analiză formală a situațiilor în care contrastul distanțelor se pierde în dimensiuni mari
• scikit-learn Nearest Neighbors documentation — ghid practic pentru selecția algoritmului de căutare
• FAISS: A Library for Efficient Similarity Search — biblioteca Meta pentru căutarea exactă și aproximativă la scara miliardelor de vectori

---

Sursă: K-Nearest Neighbors and Distances — original

Navigare: înapoi: 02.05 — Mașini cu vectori suport · Faza 2 — Bazele învățării automate · Catalog complet · în continuare: 02.07 — Învățare nesupravegheată.