K-Nearest Neighbors: Il Classificatore Lazy
K-Nearest Neighbors (KNN) è uno degli algoritmi più intuitivi del Machine Learning: per classificare un nuovo punto, guarda i K punti più vicini nel dataset di training e assegna la classe di maggioranza. Non costruisce un modello esplicito durante il training (per questo si chiama lazy learner): tutto il lavoro computazionale avviene al momento della predizione, quando l'algoritmo deve cercare i vicini nello spazio delle feature.
La semplicità del KNN è la sua forza e la sua debolezza: è facile da capire e implementare, ma diventa lento con dataset grandi perché deve calcolare la distanza da ogni punto di training per ogni nuova predizione. Le strutture dati come KD-Tree e Ball Tree mitigano questo problema ma non lo eliminano completamente.
Cosa Imparerai in Questo Articolo
- Come funziona KNN e le metriche di distanza
- Come scegliere il valore ottimale di K
- K-Means: il clustering più popolare
- DBSCAN: clustering basato sulla densità
- Come valutare il clustering senza etichette
- Silhouette Score e metodo del gomito (Elbow)
Metriche di Distanza
Il KNN si basa sul concetto di distanza tra punti nello spazio delle feature. La scelta della metrica influenza significativamente i risultati. La distanza euclidea è la più comune: la linea retta tra due punti nello spazio n-dimensionale. La distanza di Manhattan calcola la somma delle differenze assolute (come camminare in una griglia di strade). La distanza di Minkowski è una generalizzazione delle prime due, controllata dal parametro p.
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
import numpy as np
# Dataset
wine = load_wine()
X, y = wine.data, wine.target
X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.2, random_state=42
)
# Trovare il K ottimale
k_range = range(1, 31)
cv_scores = []
for k in k_range:
pipeline = Pipeline([
('scaler', StandardScaler()),
('knn', KNeighborsClassifier(n_neighbors=k))
])
scores = cross_val_score(pipeline, X_train, y_train, cv=5, scoring='accuracy')
cv_scores.append(scores.mean())
best_k = k_range[np.argmax(cv_scores)]
print(f"Miglior K: {best_k} con accuracy: {max(cv_scores):.3f}")
# Modello finale con il K ottimale
final_pipeline = Pipeline([
('scaler', StandardScaler()),
('knn', KNeighborsClassifier(n_neighbors=best_k, weights='distance'))
])
final_pipeline.fit(X_train, y_train)
test_accuracy = final_pipeline.score(X_test, y_test)
print(f"Test accuracy con K={best_k}: {test_accuracy:.3f}")K-Means Clustering
K-Means è l'algoritmo di clustering più utilizzato. Partiziona i dati in K cluster, dove ogni cluster è definito dal suo centroide (il punto medio). L'algoritmo alterna due fasi: assegnare ogni punto al centroide più vicino, e ricalcolare i centroidi come media dei punti assegnati. Si ripete fino alla convergenza.
K-Means funziona bene con cluster sferici di dimensioni simili, ma ha limiti importanti: richiede di specificare K in anticipo, è sensibile all'inizializzazione dei centroidi (risolto parzialmente da K-Means++) e non gestisce bene cluster di forma irregolare o dimensioni diverse.
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
import numpy as np
# Dati di esempio: segmentazione clienti
np.random.seed(42)
# 3 gruppi naturali di clienti
group1 = np.random.randn(100, 2) * 0.5 + [2, 2] # Budget
group2 = np.random.randn(100, 2) * 0.8 + [7, 7] # Premium
group3 = np.random.randn(100, 2) * 0.6 + [2, 8] # Frequenti
X = np.vstack([group1, group2, group3])
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
# Elbow method: trovare il K ottimale
inertias = []
silhouettes = []
K_range = range(2, 11)
for k in K_range:
kmeans = KMeans(n_clusters=k, random_state=42, n_init=10)
labels = kmeans.fit_predict(X_scaled)
inertias.append(kmeans.inertia_)
silhouettes.append(silhouette_score(X_scaled, labels))
# Risultati
for k, inertia, sil in zip(K_range, inertias, silhouettes):
marker = " <-- ottimale" if k == 3 else ""
print(f"K={k}: Inertia={inertia:.1f}, Silhouette={sil:.3f}{marker}")
# Modello finale
kmeans_final = KMeans(n_clusters=3, random_state=42, n_init=10)
clusters = kmeans_final.fit_predict(X_scaled)
print(f"\nDistribuzione cluster: {np.bincount(clusters)}")DBSCAN: Clustering Basato sulla Densità
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) è un algoritmo di clustering che non richiede di specificare il numero di cluster in anticipo. Identifica i cluster come regioni dense separate da regioni a bassa densità. Due parametri controllano il comportamento: eps (il raggio di vicinanza) e min_samples (il numero minimo di punti per formare un cluster).
DBSCAN classifica i punti in tre categorie: core points (con almeno min_samples vicini entro eps), border points (vicini a un core point ma con pochi vicini propri) e noise points (né core né border). A differenza di K-Means, DBSCAN gestisce cluster di forma arbitraria e identifica automaticamente gli outlier.
from sklearn.cluster import DBSCAN, AgglomerativeClustering
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
from sklearn.datasets import make_moons
import numpy as np
# Dataset con cluster non sferici (mezzalune)
X, y_true = make_moons(n_samples=300, noise=0.1, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
# DBSCAN
dbscan = DBSCAN(eps=0.3, min_samples=10)
labels_dbscan = dbscan.fit_predict(X_scaled)
n_clusters = len(set(labels_dbscan)) - (1 if -1 in labels_dbscan else 0)
n_noise = list(labels_dbscan).count(-1)
print(f"DBSCAN: {n_clusters} cluster, {n_noise} punti rumore")
if n_clusters > 1:
mask = labels_dbscan != -1
sil = silhouette_score(X_scaled[mask], labels_dbscan[mask])
print(f" Silhouette (escluso rumore): {sil:.3f}")
# Clustering Gerarchico (Agglomerativo)
agg = AgglomerativeClustering(n_clusters=2, linkage='ward')
labels_agg = agg.fit_predict(X_scaled)
sil_agg = silhouette_score(X_scaled, labels_agg)
print(f"\nHierarchical (Ward): Silhouette = {sil_agg:.3f}")
# K-Means per confronto (fatica con mezzalune)
from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=2, random_state=42, n_init=10)
labels_km = kmeans.fit_predict(X_scaled)
sil_km = silhouette_score(X_scaled, labels_km)
print(f"K-Means: Silhouette = {sil_km:.3f}")Metriche di Valutazione del Clustering
Valutare il clustering è più difficile rispetto alla classificazione supervisionata perché non ci sono etichette di riferimento. Il Silhouette Score misura quanto ogni punto è simile al proprio cluster rispetto ai cluster vicini: va da -1 (assegnazione sbagliata) a 1 (cluster densi e ben separati). Il Davies-Bouldin Index misura la similarità media tra cluster: più basso è meglio. Il Calinski-Harabasz Index misura il rapporto tra dispersione inter-cluster e intra-cluster: più alto è meglio.
KNN vs K-Means: Non confonderli! KNN è un algoritmo supervisionato per classificazione/regressione (usa le etichette). K-Means è un algoritmo non supervisionato di clustering (non usa etichette). L'unica cosa che condividono è la lettera K.
Quando Usare Ciascun Algoritmo
KNN: per problemi di classificazione con dataset piccoli-medi e quando la relazione tra feature e target è locale e non lineare. K-Means: per segmentazione con cluster sferici e bilanciati. DBSCAN: quando i cluster hanno forme irregolari, ci sono outlier significativi, o non si conosce il numero di cluster. Hierarchical: quando serve capire la gerarchia dei raggruppamenti e il dataset non è troppo grande.
Punti Chiave
- KNN classifica in base ai K vicini più prossimi: semplice ma lento su dataset grandi
- La scelta di K si fa con cross-validation: K troppo basso causa overfitting, troppo alto underfitting
- K-Means partiziona in K cluster con centroidi; richiede K noto e funziona con cluster sferici
- DBSCAN trova cluster di forma arbitraria basandosi sulla densità e identifica gli outlier
- Silhouette Score è la metrica più usata per valutare la qualità del clustering
- Lo scaling delle feature è essenziale per tutti gli algoritmi basati sulla distanza