In questo articolo affronteremo un’altra importante famiglia di classificatori: quella dei k-Nearest Neighbors (o k-NN)

Nearest Neighbor

Partiamo come sempre dalla versione più semplice, cioè il Nearest Neighbor. Supponiamo che il nostro dataset di training sia composto da due classi di esempi: classe A e classe B (nella figura rappresentate da stelle rosse e triangoli verdi all’interno dello spazio delle feature). Se al modello applichiamo un nuovo ingresso da classificare (nella figura è rappresentato dal punto di domanda), questo verrà portato nello spazio delle feature e verrà confrontato con tutti gli altri esempi del dataset fino a trovare l’esempio più vicino. La classe del nuovo ingresso sarà la stessa dell’esempio trovato (in figura il punto di domanda è più vicino alla stella rossa, quindi verrà classificato come classe A).

k-Nearest Neighbors

Questo modello di classificazione è del tutto simile al precedente, ma invece di cercare l’esempio più vicino al dato in ingresso, ne cerca diversi. Il k del nome è infatti il numero di esempi da ricercare. La classe di appartenenza dell’ingresso sarà quella che è maggiormente rappresentata tra gli esempi trovati. In caso di pareggio, baserò la scelta su regole ulteriori. Per k = 1 ottengo il classificatore Nearest Neighbor che è quindi un caso particolare di k-NN.

Nell’esempio in figura vediamo come la scelta del valore k influisca sulla classificazione. Nel caso di k = 3 l’esempio in ingresso verrà classificato come classe B (triangoli verdi) perchè attorno all’ingresso i 3 esempi più vicini sono una stella rossa e due triangoli verdi. Nel caso di k = 7 la classe dell’ingresso sarà la A in quanto i 7 esempi più vicini risultano essere 4 stelle rosse e 3 triangoli verdi.

I modelli di classificazione appartenenti a questa famiglia sono definiti lazy, cioè pigri in quanto, come uno studente particolarmente pigro, non imparano le regole che consentono di arrivare ad una classificazione di un dato in ingresso, ma semplicemente memorizzano i dati di training e le relative classificazioni.

Calcolare la distanza

Ora è necessario mettersi d’accordo sul significato da dare a “più vicino“. Come al solito si devono utilizzare delle metriche, in particolare la distanza di Minkowski. Questa distanza, calcolata tra due punti A e B (ognuno di essi con n componenti), è definita come

I casi particolari di questa distanza sono la classica distanza Euclidea (che si ottiene con p=2) e la distanza Manhattan (che si ottiene con p=1).

Come si vede in figura, la distanza Euclidea è rappresentata dalla riga gialla che unisce direttamente A con B, mentre la distanza Manhattan (detta anche distanza del tassista) è la distanza che porta da A a B (o viceversa) utilizzando solo spostamenti lungo gli assi dello spazio in cui risiedono i due punti.

Il nome di distanza Manhattan è riferito a come sono costruite le strade dell’omonimo distretto di New York. Il riferimento al tassista ovviamente è da mettere in relazione a come un tassista può spostarsi all’interno di quella città, cioè attraverso un reticolo di strade ortogonali tra loro.

Algoritmo di classificazione k-NN

Per trovare la classe di appartenenza di un dato in ingresso, si esegue semplicemente un loop su ogni esempio di training. Per ogni esempio viene calcolata la distanza tra esempio e ingresso usando la metrica desiderata (ad esempio la distanza euclidea). Infine si prendono i k esempi con distanza minore e si contano le classificazioni di questi esempi. Vince la classificazione con maggior numero di esempi tra i k trovati. In caso di parità solitamente si prende la classe appartenente all’esempio più vicino in assoluto tra i k trovati. In caso di ulteriore parità (magari ci sono due o più esempi di classe diversa con stessa distanza minima) dovrei utilizzare regole ulteriori (ad esempio la classe con maggior numero di esempi tra tutti gli esempi di training o altro).

Da quanto appena detto appare evidente la semplicità di questo algoritmo (un semplice loop). Inoltre è altrettanto evidente che in caso si desideri arricchire il dataset di training con nuovi esempi, non è necessario eseguire una fase di training vera e propria, ma l’algoritmo sarà subito pronto a eseguire predizioni.

D’altro canto se il training set è grande, lo sforzo computazionale potrebbe aumentare troppo (una cosa è un loop eseguito su 1.000 esempi, una cosa diversa è un loop eseguito su 1.000.000 di esempi…). Inoltre, oltre al valore di k, influisce sul risultato anche la metrica utilizzata, che quindi va scelta in maniera opportuna.

Codice Python

NOTA: il codice di questo esempio lo trovi qui

Vogliamo provare la validità di un k-NN nella classificazione di digit, come fatto la volta scorsa per la regressione logistica. Per diminuire il carico di elaborazione, questa volta utilizziamo un dataset simile al MNIST, ma composto da immagini 8 x 8 pixel.

Quindi, carico il dataset ed eseguo l’encoding del vettore con le classi target.

# dati caricati da https://www.openml.org/d/28
X, Y = fetch_openml('optdigits', version=1, return_X_y=True)

# eseguo la codifica automatica delle label
labEnc = LabelEncoder()
Y_enc = labEnc.fit_transform(Y)

Dopo aver proceduto come al solito a suddividere il dataset in train set e test set e aver standardizzato i dati, voglio verificare come si modifica il risultato in base al valore di k, per cui eseguo un loop con k che va da 1 a 20 e calcolo accuracy e negative log-likelihood sia per il set di training che per il set di test (in modo da verificare anche se c’è overfitting).

# ciclo da 1 a 20 K
for K in range(1, 21):
    # eseguo la classificazione K-NN
    knn = KNeighborsClassifier(n_neighbors=K)
    knn.fit(X_train_std, Y_train)

    # eseguo predizione e calcolo confidenza su train
    Y_pred_train = knn.predict(X_train_std)
    Y_pred_train_proba = knn.predict_proba(X_train_std)

    # eseguo predizione e calcolo confidenza su test
    Y_pred = knn.predict(X_test_std)
    Y_pred_proba = knn.predict_proba(X_test_std)

    # valutiamo il modello con le metriche messe a disposizione da SciKitLearn
    print("K:", K)
    print("Accuracy: TRAIN =", "{0:.4f}".format(accuracy_score(Y_train, Y_pred_train)),
          "- TEST =", "{0:.4f}".format(accuracy_score(Y_test, Y_pred)))
    print("NLogLike: TRAIN =", "{0:.4f}".format(log_loss(Y_train, Y_pred_train_proba)),
          "- TEST =", "{0:.4f}".format(log_loss(Y_test, Y_pred_proba)))
    print()

K: 1 
Accuracy: TRAIN = 1.0000 - TEST = 0.9792 
NLogLike: TRAIN = 0.0000 - TEST = 0.7170 

K: 2 
Accuracy: TRAIN = 0.9860 - TEST = 0.9745 
NLogLike: TRAIN = 0.0167 - TEST = 0.4102 

K: 3 
Accuracy: TRAIN = 0.9878 - TEST = 0.9786 
NLogLike: TRAIN = 0.0276 - TEST = 0.3573 

...... 
...... 

K: 10 
Accuracy: TRAIN = 0.9769 - TEST = 0.9757 
NLogLike: TRAIN = 0.0662 - TEST = 0.1298 

K: 11 
Accuracy: TRAIN = 0.9769 - TEST = 0.9745 
NLogLike: TRAIN = 0.0712 - TEST = 0.1333 

...... 
...... 

K: 20 
Accuracy: TRAIN = 0.9705 - TEST = 0.9715 
NLogLike: TRAIN = 0.0988 - TEST = 0.1410

Per k = 1 si nota una condizione di overfitting. La situazione migliora fino a k = 10 per poi proseguire con qualche peggioramento e miglioramento.

Ora fissiamo k = 3 e vediamo quali esempi di test vengono classificati in modo sbagliato.

# rieseguo la classificazione con K=3
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_train_std, Y_train)

# eseguo predizione e calcolo confidenza su test
Y_pred = knn.predict(X_test_std)

# visualizzo le cifre sbagliate
for i in range(0, len(X_test)):
    if Y_pred[i] != Y_test[i]:
        print("La cifra", Y_test[i], "è stata classificata come cifra", Y_pred[i])
        plt.imshow(X_test[i].reshape([8, 8]), cmap="gray")
        plt.show()

La cifra 3 è stata classificata come cifra 5 
La cifra 7 è stata classificata come cifra 4 
La cifra 3 è stata classificata come cifra 2 
..... 
..... 
La cifra 9 è stata classificata come cifra 3 
La cifra 2 è stata classificata come cifra 1 
La cifra 7 è stata classificata come cifra 4

Come vedrete dalle immagini che verranno visualizzate dal programma (non le riporto per lasciarvi la suspense), in generale le errate classificazioni sono associate ad immagini difficilmente comprensibili anche all’occhio umano. Come unico esempio, riporto a lato l’immagine di un 1 che è stato erroneamente classificato come 7.

Voi avreste saputo fare di meglio?

See you soon!

Se volete sperimentare la classificazione k-NN su MNIST, sappiate che dovrete avere a disposizione un computer potente e tanta pazienza, perchè l’elaborazione porterà via alcune ore. Purtroppo Scikit-Learn non sfrutta alcune caratteristiche che possono concorrere ad accelerare i calcoli, come ad esempio l’uso di GPU di ultima generazione (sì, avete capito bene: le schede grafiche che usate per giocare). Più avanti vedremo che esistono invece altre librerie che possono sfruttare questi motori di calcolo estremamente potenti e che possono quindi aiutare nell’ottenere risultati in tempi significativamente ridotti anche su dataset molto grandi e con modelli di complessità enorme.

Per ora è tutto, ci vediamo alla prossima.

Bye!