KNN

KNN – Algoritmo di Supervisione

In questo nuovo articolo trattiamo l’algoritmo di supervisione KNN (k-nearest neighbor classifier – classificatore a k vicini più prossimi) il quale è particolarmente interessante perché è un po’ diverso dagli algoritmi di Machine Learning che abbiamo trattato finora. 

KNN - un algoritmo pigro

Perché KNN viene definito un algoritmo di apprendimento pigro (lazy

Come abbiamo capito, questo algoritmo si differenzia dagli altri, non per la sua semplicità di utilizzo, bensì perché KNN non apprende una funzione di discriminazione da dati di addestramento, bensì memorizza il dataset completo di addestramento.  

Modelli parametrici e non parametrici

Esistono, all’interno del mondo Machine Learning, i modelli parametrici e non parametrici. Con il primo tipo possiamo stimare i parametri del dataset per ottenere una funzione in grado di classificare nuovi dati senza richiedere più il dataset di addestramento originale. Tra questi fanno parte il Perceptron, le SVM lineare e la regressione lineare

I modelli non parametrici invece non sono caratterizzati da un numero fisso di parametri perché i numero dei parametri cresce sulla base dei dati di addestramento. Il classificatore ad albero decisionale e foresta casuale sono due algoritmi di questo tipo.

KNN appartiene a una sottocategoria dei modelli non parametrici descritta come apprendimento basato su istanze. Gli algoritmi appartenenti a questa categoria sono caratterizzati dalla memorizzazione del dataset e l’apprendimento pigro è un caso speciale di apprendimento basato su istanze associato a costo zero durante il processo di apprendimento. 

How-to

L’algoritmo è molto semplice e ci viene in aiuto l’utilizzo di un elenco per mettere a fuoco i punti necessari per addestrare il modello:

  1.  Scegliere il numero k e una metrica della distanza;
  2. Trovare i k elementi più vicini del campione che vogliamo classificare;
  3. Assegnare l‘etichetta della classe sulla base di un voto a maggioranza;
KNN

Come possiamo vedere dall’immagine, il nuovo punto nei dati ? viene assegnato alla classe dei triangoli sulla base del voto di maggioranza fra i suoi cinque vicini più prossimi.  

Il vantaggio principale di questo tipo di classificazione basato sulla memorizzazione è il fatto che il classificatore si adatta immediatamente mentre raccogliamo nuovi dati di addestramento. A volte però, i vantaggi comportano degli svantaggi a dir poco fastidiosi. In questo tipo di algoritmo infatti, lo svantaggio principale è il fatto che la complessità computazionale per la classificazione di nuovi campioni cresce in modo lineare con il numero di campioni presenti nel dataset di addestramento a meno che il dataset abbia pochissime dimensioni e l’algoritmo sia stato implementato utilizzando strutture di dati efficienti

Implementazione scikit-learn del modello

Costruiamo il codice necessario ad addestrare l’algoritmo utilizzando una metrica di distanza euclidea:

				
					from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(n_neighbors=5, p=2, metric='minkowski')
knn.fit(X_train_std, y_train)

plot_decision_regions(X_combined_std, y_combined, 
                      classifier=knn, test_idx=range(105, 150))

plt.xlabel('petal length [standardized]')
plt.ylabel('petal width [standardized]')
plt.legend(loc='upper left')
plt.tight_layout()
plt.show()
				
			

Il confine decisionale si presenta relativamente morbido, specificando 5 vicini nel modello

In questo algoritmo è fondamentale la scelta di k per trovare un ottimo equilibrio tra i problemi di over e under fitting. Attenzione anche alla scelta della metrica della distanza che deve essere appropriata per la caratteristica del dataset. Spesso, come abbiamo utilizzato in precedenza, utilizziamo una semplice misurazione della distanza euclidea. La distanza ‘minkowsky‘ è una generalizzazione della distanza euclidea e Manhattan che può essere scritta in questo modo:

Se p viene impostato a 2 o la distanza mancante è uguale a p = 1, questa è una distanza euclidea.

L'overfitting in KNN

L’algoritmo è molto soggetto a overfitting a causa della maledizione della dimensionalità. Si tratta di un fenomeno in cui lo spazio delle caratteristiche diventa sempre più sparso a causa della crescita di dimensioni di un dataset di addestramento di dimensioni fisse. Allo stesso tempo consideriamo che i i vicini più prossimi siano troppo lontani per offrire una buona stima. Abbiamo trattato nei capitoli precedenti come utilizzare la regolarizzazione per far fronte al fenomeno dell’overfitting, ma in modelli come gli alberi decisionali e i KNN possiamo utilizzare alcune tecniche di selezione delle caratteristiche e di riduzione della dimensionalità per cercare di sfuggire alla maledizione della dimensionalità. 

Condividi il post

Condividi su facebook
Condividi su google
Condividi su twitter
Condividi su email
Condividi su whatsapp