K-Nearest Neighbors

Algoritmul k-cei mai apropiați vecini (KNN) este un algoritm de învățare supravegheată, neparametric, folosit pentru sarcini de clasificare și regresie în învățarea automată. Acesta se bazează pe conceptul de proximitate, presupunând că punctele de date similare se află aproape unele de altele. KNN este un algoritm de învățare leneșă, ceea ce înseamnă că nu necesită o fază de antrenare și face predicții stocând întregul set de date de antrenament și utilizându-l pentru a determina clasa sau valoarea noilor puncte de date. Algoritmul prezice rezultatul pentru un punct de testare identificând cei ‘k’ puncte de date de antrenament cei mai apropiați de acesta și deduce ieșirea pe baza acestor vecini. Această metodă este extrem de intuitivă și imită strategiile de percepție umană care se bazează pe compararea noilor date cu exemplele cunoscute.

Cum funcționează KNN

KNN operează identificând cei ‘k’ cei mai apropiați vecini ai unui punct de interogare și folosind acești vecini pentru a face o predicție.

• În sarcinile de clasificare, algoritmul atribuie punctului de interogare clasa cea mai comună dintre cei ‘k’ cei mai apropiați vecini, proces numit vot majoritar. Votul majoritar în KNN poate fi înțeles ca “vot prin pluralitate” când sunt mai multe clase, unde punctul de interogare este atribuit clasei cu cel mai mare număr dintre vecinii cei mai apropiați, chiar dacă nu constituie o majoritate absolută.
• În sarcinile de regresie, KNN prezice valoarea prin media valorilor celor ‘k’ vecini cei mai apropiați.

Principiile de proximitate și similaritate, esențiale pentru percepția umană, sunt centrale și pentru funcționarea KNN, deoarece se presupune că punctele de date apropiate în spațiul caracteristicilor sunt mai similare și, prin urmare, au rezultate similare.

Metrice de distanță

Pentru a determina cei mai apropiați vecini, KNN utilizează diverse metrici de distanță, care sunt critice pentru performanța sa:

• Distanța Euclidiană: Distanța în linie dreaptă dintre două puncte într-un spațiu multidimensional, utilizată frecvent pentru variabile continue. Este cea mai comună metrică de distanță în KNN, utilă în special când datele sunt dense și continue.
• Distanța Manhattan: Numită și distanța taximetristului, calculează distanța prin însumarea diferențelor absolute dintre coordonatele a două puncte. Este utilă în scenarii de trasee tip grilă, unde deplasările sunt constrânse pe direcții ortogonale.
• Distanța Minkowski: O formă generalizată a distanțelor Euclidiană și Manhattan, parametrizată de ‘p’. Dacă p=1, devine distanța Manhattan, iar dacă p=2, distanța Euclidiană. Această metrică oferă flexibilitate în funcție de valoarea lui ‘p’ aleasă.
• Distanța Hamming: Folosită pentru date categorice, numără câte biți diferă între doi vectori binari. Este utilă în special în probleme de clasificare binară unde atributele au valori binare.

Alegerea valorii potrivite pentru ‘k’

Parametrul ‘k’ în KNN reprezintă numărul de vecini luați în considerare. Alegerea corectă a lui ‘k’ este esențială:

• Un ‘k’ mic poate duce la supraînvățare, modelul fiind prea sensibil la zgomotul din datele de antrenament și captând tipare spurioase care nu se generalizează.
• Un ‘k’ mare poate duce la subînvățare, modelul devenind prea general și ignorând tipare importante, ceea ce duce la performanță predictivă slabă.
• De obicei, ‘k’ se alege prin validare încrucișată și ar trebui să fie un număr impar pentru a evita egalitățile în deciziile de clasificare. Alegerea valorii lui ‘k’ poate influența semnificativ acuratețea modelului și este, în general, determinată empiric.

Avantaje și dezavantaje

Avantaje

• Simplu și intuitiv: Ușor de înțeles și implementat, ceea ce îl face o alegere bună pentru începători. Simplitatea KNN constă în abordarea sa directă de a compara instanțele de test cu exemplele stocate.
• Fără fază de antrenare: KNN nu necesită o fază explicită de antrenare, făcând predicții pe baza setului de date stocat. Asta înseamnă că modelul poate fi actualizat pur și simplu prin adăugarea de noi puncte de date în setul de date.
• Versatil: Poate fi folosit atât pentru clasificare, cât și pentru regresie, fiind aplicabil într-o gamă largă de domenii. De asemenea, este util pentru probleme de clasificare multi-label.

Dezavantaje

• Intensiv din punct de vedere computațional: Deoarece necesită stocarea și compararea fiecărui nou punct de date cu întregul set de date, poate fi lent și solicitant din punct de vedere al resurselor, mai ales cu seturi de date mari. Complexitatea de timp a KNN este O(n), unde n este numărul de exemple de antrenament.
• Sensibil la valori aberante: Prezența valorilor aberante poate afecta semnificativ predicțiile, deoarece aceste puncte anormale pot distorsiona rezultatele, în special când ‘k’ este mic.
• Blestemul dimensionalității: În spații de dimensiuni mari, performanța algoritmului poate scădea deoarece distanțele dintre puncte devin mai puțin relevante. Pe măsură ce dimensionalitatea crește, volumul spațiului crește și datele devin rare. Această raritate face dificilă găsirea vecinilor cei mai apropiați în mod eficient pentru KNN.

Cazuri de utilizare

KNN este aplicat în diverse domenii datorită simplității și eficienței sale:

• Sisteme de recomandare: Folosit pentru recomandarea de produse sau conținut utilizatorilor pe baza preferințelor utilizatorilor similari. KNN poate ajuta la identificarea utilizatorilor sau elementelor similare evaluând similaritatea caracteristicilor.
• Recunoașterea tiparelor: Utilizat în recunoașterea scrisului de mână și alte sarcini de recunoaștere a tiparelor, unde poate clasifica imagini pe baza similarității valorilor pixelilor.
• Imputarea datelor: Util în completarea valorilor lipsă din seturile de date prin estimarea lor pe baza punctelor de date similare, menținând astfel integritatea setului de date.
• Finanțe și sănătate: Aplicat în predicții bursiere, evaluarea riscului și diagnostic medical prin analiza similarităților din datele istorice. În sănătate, poate prezice diagnosticul pacienților comparând simptomele cu cazuri cunoscute.

Implementare în Python

KNN poate fi implementat folosind biblioteci precum scikit-learn în Python. Iată un exemplu de bază de utilizare a KNN pentru clasificare:

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

# Încărcarea setului de date
iris = load_iris()
X, y = iris.data, iris.target

# Împărțirea datelor în seturi de antrenament și test
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Inițializarea clasificatorului KNN cu k=3
knn = KNeighborsClassifier(n_neighbors=3)

# Antrenarea modelului
knn.fit(X_train, y_train)

# Realizarea predicțiilor
y_pred = knn.predict(X_test)

# Evaluarea acurateței
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.2f}")

K-Nearest Neighbors (KNN) în cercetarea științifică

K-Nearest Neighbors (KNN) este un algoritm fundamental folosit în diverse domenii precum regăsirea informației multimedia, data mining și învățarea automată, în special în contextul seturilor de date mari.

Lucrări de cercetare notabile:

• “Approximate k-NN Graph Construction: a Generic Online Approach” de Wan-Lei Zhao et al.:
  Prezintă o metodă eficientă pentru căutarea aproximativă a celor k-cei mai apropiați vecini și pentru construcția de grafuri. Lucrarea demonstrează o soluție dinamică și fezabilă pentru gestionarea diverselor dimensiuni și scări de date, suportând actualizări online care nu sunt posibile în multe metode existente. Citește mai mult.

• “Parallel Nearest Neighbors in Low Dimensions with Batch Updates” de Magdalen Dobson și Guy Blelloch:
  Introduce algoritmi paraleli care combină kd-tree și ordonarea Morton într-o structură zd-tree, optimizată pentru date de dimensiuni mici. Autorii arată că abordarea lor este mai rapidă decât algoritmii existenți, obținând creșteri substanțiale de viteză prin procesare paralelă. Zd-tree suportă în mod unic actualizări batch-dinamice paralele, o premieră pentru structurile de date k-cei mai apropiați vecini. Citește mai mult.

• “Twin Neural Network Improved k-Nearest Neighbor Regression” de Sebastian J. Wetzel:
  Explorează o abordare nouă pentru regresia k-cei mai apropiați vecini folosind rețele neuronale gemene. Această metodă se concentrează pe prezicerea diferențelor dintre țintele de regresie, ducând la performanțe îmbunătățite față de rețelele neuronale tradiționale și tehnicile clasice de regresie k-cei mai apropiați vecini pe seturi de date mici și medii. Citește mai mult.