2.4 Algoritmul K-Nearest Neighbors (K-NN)

Cel mai intuitiv algoritm de clasificare: „spune-mi cu cine te asemeni, ca să-ți spun cine ești". Un exemplu nou primește clasa majoritară a celor mai apropiați k vecini.

Teorie

Principiul celor mai apropiați vecini

K-NN nu „învață" nimic la antrenare — memorează pur și simplu datele. La predicție: calculează distanța de la exemplul nou la toate exemplele din train, ia cele mai apropiate k, și votează: clasa majoritară câștigă (la regresie: media valorilor vecinilor).

Alegerea parametrului k

Practic: se încearcă mai multe valori impare (evită egalitatea la vot) și se alege cea cu cel mai bun scor pe validare sau prin cross-validation.

Alegerea metricii de distanță

Utilizarea scikit-learn

from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import cross_val_score

sc = StandardScaler()
X_tr = sc.fit_transform(X_train)

for k in [1, 3, 5, 7, 11, 21]:
    model = KNeighborsClassifier(n_neighbors=k, metric="euclidean")
    scoruri = cross_val_score(model, X_tr, y_train, cv=5)
    print(f"k={k}: {scoruri.mean():.3f}")

# weights="distance": vecinii mai apropiați au vot mai greu
model = KNeighborsClassifier(n_neighbors=5, weights="distance")

Problemă rezolvată: Iris cu K-NN

import pandas as pd
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import cross_val_score

train = pd.read_csv("train.csv")
test = pd.read_csv("test.csv")
feats = ["sepal_length", "sepal_width", "petal_length", "petal_width"]

sc = StandardScaler()
X = sc.fit_transform(train[feats])
y = train["species"]

# alegem k prin cross-validation
best_k, best_s = None, 0
for k in range(1, 22, 2):
    s = cross_val_score(KNeighborsClassifier(n_neighbors=k), X, y, cv=5).mean()
    if s > best_s:
        best_k, best_s = k, s
print("Cel mai bun k:", best_k, "scor:", round(best_s, 3))

model = KNeighborsClassifier(n_neighbors=best_k).fit(X, y)
pred = model.predict(sc.transform(test[feats]))
pd.DataFrame({"SampleID": test["SampleID"], "species": pred}) \
  .to_csv("submission.csv", index=False)

Probleme propuse