K-Nearest Neighbors (K-NN) con scikit-learn per Problemi di Classificazione in Machine Learning

Pubblicato il di
Post Views: 983
K-Nearest Neighbor per classificazione header

L’algoritmo K-Nearest Neighbors (K-NN) è un metodo di apprendimento supervisionato utilizzato per la classificazione e la regressione. L’idea principale è di classificare un punto dati basandosi sulla maggioranza delle etichette delle sue k istanze più vicine nel set di addestramento. La “vicinanza” è spesso misurata utilizzando la distanza euclidea.

K-Nearest Neighbors

L’algoritmo K-Nearest Neighbors (KNN) ha una storia affascinante che affonda le radici negli anni ’50 con l’emergere della teoria del riconoscimento dei pattern. In quel periodo, gli scienziati iniziarono a esplorare metodi statistici e algoritmi di classificazione per distinguere e identificare schemi complessi nei dati.

Con il progredire degli anni ’60 e ’70, furono introdotti concetti fondamentali nel campo del riconoscimento dei pattern e dell’apprendimento automatico, come la distanza euclidea e la classificazione basata su istanze. Questi concetti sono stati precursori essenziali per lo sviluppo di KNN.

Negli anni ’80, con l’avvento di calcolatori più potenti e crescente interesse nell’applicare tecniche di apprendimento automatico, l’algoritmo KNN cominciò a prendere forma nel suo formato moderno. Durante gli anni ’90 e 2000, con l’esplosione di dati e miglioramenti nelle capacità computazionali, KNN divenne sempre più rilevante, trovando applicazioni in settori come bioinformatica, riconoscimento vocale e medicina.

Oggi, KNN rimane uno strumento fondamentale nell’arsenale dell’apprendimento automatico. Anche se può essere superato in prestazioni da algoritmi più complessi su dataset molto grandi, la sua semplicità concettuale e relativa facilità di implementazione lo rendono una scelta popolare, soprattutto per coloro che si avvicinano per la prima volta all’apprendimento automatico.

Questo algoritmo viene utilizzato per risolvere problemi:

  • classificazione
  • regressione

Per quanto riguardano i problemi di classificazione, K-NN trova i k vicini più prossimi di un punto di test, guarda le loro etichette e assegna al punto di test l’etichetta che appare più frequentemente tra i vicini.

Per quanto riguardano i problemi di regressione, invece di etichette di classe, si utilizzano valori medi o ponderati dei k vicini per predire il valore del punto di test.

È importante scegliere un valore adeguato per k e determinare la metrica di distanza appropriata in base al problema specifico. K-NN può essere sensibile alla scala dei dati e può richiedere una pre-elaborazione dei dati per ottenere risultati ottimali.

Nell’algoritmo K-Nearest Neighbors (K-NN), la distanza tra i punti può essere calcolata utilizzando diverse metriche, ma la più comune è la distanza euclidea. La formula della distanza euclidea tra due punti P(x_1, y_1) e Q(x_2, y_2) nello spazio bidimensionale è:

d(P, Q) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}

Generalizzando per uno spazio ( n )-dimensionale, la distanza euclidea tra due punti ( P ) e ( Q ) è data da:

d(P, Q) = \sqrt{\sum_{i=1}^{n} (q_i - p_i)^2}

Dove p_i e q_i sono le coordinate del punto P e Q rispettivamente lungo l’asse i .

Per quanto riguarda la scelta di k , è un iperparametro che può essere regolato per ottenere le migliori prestazioni nell’applicazione specifica. Un valore troppo basso potrebbe rendere l’algoritmo sensibile al rumore, mentre un valore troppo alto potrebbe rendere l’algoritmo troppo generico.

L’implementazione pratica di K-NN coinvolge anche il voto o la media dei vicini più prossimi per la classificazione o la regressione, rispettivamente.

K-Nearest Neighbors in Scikit-Learn

Scikit-learn, una delle librerie più popolari per l’apprendimento automatico in Python, include un’implementazione del KNN nel modulo neighbors. Il modulo neighbors di scikit-learn contiene diverse classi e funzionalità per la costruzione e l’utilizzo di modelli basati sulla vicinanza nei dati. Ecco una breve panoramica delle principali componenti di questo modulo:

  • KNeighborsClassifier: Questa classe implementa il classificatore K-Nearest Neighbors per problemi di classificazione. Consente di specificare il numero di vicini (n_neighbors) e altre opzioni per il calcolo della distanza e il peso dei vicini.
  • KNeighborsRegressor: Analogamente al classificatore, questa classe implementa il regressore K-Nearest Neighbors per problemi di regressione. Accetta gli stessi parametri del classificatore.
  • NearestNeighbors: Questa classe fornisce una base per il calcolo dei vicini più vicini. È utile quando si desidera accedere ai vicini senza dover necessariamente addestrare un modello, ad esempio per il clustering o altre operazioni basate sulla vicinanza.
  • RadiusNeighborsClassifier e RadiusNeighborsRegressor: Queste classi implementano versioni di KNN che utilizzano una distanza di raggio invece di un numero fisso di vicini. Ciò significa che vengono considerati tutti i punti all’interno di un determinato raggio rispetto a un punto di query.
  • UnsupervisedNeighborsMixin: Questa mixin class viene utilizzata come base per gli algoritmi di clustering basati sulla vicinanza.
  • kneighbors_graph: Una funzione per il calcolo della matrice di adiacenza basata sui vicini più vicini.

Queste sono solo alcune delle principali componenti del modulo neighbors di scikit-learn. La documentazione ufficiale di scikit-learn fornisce dettagli più approfonditi e esempi sull’utilizzo di queste classi e funzionalità.

Esempio di un problema di Classificazione con K-Nearest Neighbors

Il problema di classificazione affrontato in questo esempio utilizza il famoso dataset Iris. Questo dataset consiste in misurazioni di lunghezza e larghezza dei sepali e dei petali di tre specie di iris: Iris-setosa, Iris-versicolor e Iris-virginica. L’obiettivo è quello di predire correttamente la specie di iris basandosi su queste misurazioni.

Utilizzando l’algoritmo K-Nearest Neighbors (KNN) per risolvere questo problema ha diversi vantaggi:

  • Semplicità: KNN è un algoritmo di classificazione intuitivo e facile da comprendere. Non richiede l’addestramento di un modello complesso e non fa alcuna assunzione riguardo la distribuzione dei dati.
  • Adattabilità ai dati: KNN è particolarmente utile quando non ci sono informazioni a priori sulla distribuzione dei dati. Poiché basa le predizioni sulla vicinanza nei dati, può adattarsi a strutture complesse e non lineari nei dati.
  • Interpretabilità: Le predizioni di KNN possono essere interpretate in modo intuitivo. Poiché si basa sulla classificazione dei vicini più prossimi, è possibile visualizzare facilmente i punti vicini e comprendere perché una determinata istanza è stata classificata in un certo modo.
  • Buone prestazioni in piccoli dataset: KNN può funzionare bene su dataset di dimensioni moderate o piccole, come nel caso del dataset Iris. Non richiede un’elaborazione intensiva e può fornire buoni risultati anche con un set di dati relativamente piccolo.

Passiamo quindi ad implementare il codice dell’esempio.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score

# Loading the Iris dataset
iris = load_iris()
X = iris.data
y = iris.target

# Splitting the dataset into training and testing sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Creating a KNN classifier with 3 neighbors
knn = KNeighborsClassifier(n_neighbors=3)

# Training the classifier
knn.fit(X_train, y_train)

# Prediction phase on the test set
y_pred = knn.predict(X_test)

# Calculating the accuracy of the model
accuracy = accuracy_score(y_test, y_pred)
print("Accuracy:", accuracy)

Dopo aver caricato il dataset, dividiamo i dati in set di addestramento e di test utilizzando train_test_split(). Successivamente, creiamo un classificatore KNN con 3 vicini utilizzando KNeighborsClassifier(), lo addestriamo con i dati di addestramento usando il metodo fit(), e infine facciamo previsioni sui dati di test usando il metodo predict(). Infine, calcoliamo l’accuratezza del modello confrontando le previsioni con le etichette vere utilizzando accuracy_score().

Accuracy: 1.0

Per poter avere una rappresentazione grafica del nostro risultato possiamo utilizzare il codice seguente:

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap

# Create scatterplot to visualize data points
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=ListedColormap(['red', 'green', 'blue']), edgecolor='k', s=20)
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.title('KNN Classification Result')
plt.show()

Eseguendo otteniamo il seguente grafico:

KNN for classification - scatter plot

La rappresentazione che abbiamo ottenuto è bidimensionale, ma dato che il modello KNN è stato addestrato su un dataset con quattro features, la sua rappresentazione corretta dovrebbe essere quadridimensionale. Le quattro features nel dataset Iris includono lunghezza e larghezza del sepalo, e lunghezza e larghezza del petalo.

Tuttavia, poiché visualizzare un grafico quadridimensionale è molto complesso, in genere si utilizzano grafici bidimensionali o tridimensionali per rappresentare visivamente il risultato di un modello di classificazione. Nell’esempio precedente, abbiamo scelto di utilizzare solo le prime due features (lunghezza e larghezza del sepalo) per il meshgrid e la visualizzazione, mentre le altre due features sono state mantenute costanti a zero.

Questa è una semplificazione per permettere una visualizzazione più chiara e intuitiva. Tuttavia, è importante tenere presente che stiamo visualizzando solo una parte dello spazio delle features e che la visualizzazione non tiene conto delle altre due features del dataset Iris. Vediamo insieme tutte le possibili combinazioni dei rapporti tra le features.

KNN for classification - scatter plot all features

La Decision Boundary

La “Decision Boundary” (o confine decisionale) è una linea, un iperpiano o una superficie nello spazio delle features che separa le diverse classi nei problemi di classificazione. In altre parole, è il confine che il modello di classificazione utilizza per distinguere tra le diverse categorie di dati.

Nel contesto dell’apprendimento supervisionato, quando addestriamo un modello di classificazione, l’obiettivo è quello di trovare una Decision Boundary che minimizzi l’errore di classificazione sui dati di addestramento. Questa Decision Boundary può essere lineare, se il problema è lineamente separabile, o complessa se il problema richiede una separazione non lineare.

Per esempio, considerando un problema di classificazione binaria in cui i dati sono rappresentati da punti in uno spazio bidimensionale. La Decision Boundary sarebbe una linea che separa i punti di una classe da quelli dell’altra classe. Se hai più di due classi, la Decision Boundary può essere un iperpiano o una superficie che separa le diverse classi nello spazio delle features.

Python Data Analytics

Se vuoi approfondire l’argomento e scoprire di più sul mondo della Data Science con Python, ti consiglio di leggere il mio libro:

Python Data Analytics 3rd Ed

Fabio Nelli

Una buona Decision Boundary è quella che generalizza bene ai dati non visti, quindi un’importante considerazione nell’addestramento dei modelli di classificazione è trovare un equilibrio tra la complessità del modello e la capacità di generalizzazione. Un modello troppo semplice potrebbe non essere in grado di catturare la complessità dei dati, mentre un modello troppo complesso potrebbe soffrire di overfitting, cioè potrebbe adattarsi eccessivamente ai dati di addestramento, perdendo la capacità di generalizzare ai dati nuovi e non visti.

Ritornando al nostro esempio. Anche se il nostro problema è quadridimensionale (4 features), possiamo ancora visualizzare la Decision Boundary, ma dovremo fare delle semplificazioni. Una possibilità è quella di proiettare lo spazio delle features su uno spazio di dimensione inferiore, ad esempio utilizzando una tecnica di riduzione della dimensionalità come la PCA (Principal Component Analysis).

Per proiettare lo spazio delle features su uno spazio bidimensionale utilizzando la tecnica di riduzione della dimensionalità, possiamo impiegare la Principal Component Analysis (PCA) o la Linear Discriminant Analysis (LDA). In questo esempio, utilizzeremo la PCA per ridurre le dimensioni dello spazio delle features a 2.

Ecco come puoi modificare il codice precedente per includere la riduzione della dimensionalità utilizzando PCA e visualizzare le Decision Boundary in uno spazio bidimensionale:

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from sklearn.decomposition import PCA

# Applicazione della PCA per ridurre lo spazio delle features a 2 dimensioni
pca = PCA(n_components=2)
X_pca = pca.fit_transform(X)

# Creazione di un meshgrid per visualizzare le Decision Boundary
x_min, x_max = X_pca[:, 0].min() - 1, X_pca[:, 0].max() + 1
y_min, y_max = X_pca[:, 1].min() - 1, X_pca[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1),
                     np.arange(y_min, y_max, 0.1))

# Addestramento del classificatore KNN utilizzando le features ridotte
knn_pca = KNeighborsClassifier(n_neighbors=3)
knn_pca.fit(X_pca, y)

# Predizione delle classi per ogni punto nel meshgrid
Z = knn_pca.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)

# Creazione del grafico di dispersione per visualizzare le Decision Boundary
plt.contourf(xx, yy, Z, alpha=0.3)
plt.scatter(X_pca[:, 0], X_pca[:, 1], c=y, cmap=ListedColormap(['red', 'green', 'blue']), edgecolor='k', s=20)
plt.xlabel('Principal Component 1')
plt.ylabel('Principal Component 2')
plt.title('KNN Classification Result with PCA')
plt.show()

In questo codice, abbiamo applicato la PCA al dataset Iris per ridurre lo spazio delle features a due dimensioni. Abbiamo quindi addestrato il classificatore KNN utilizzando le features ridotte e visualizzato le Decision Boundary nello spazio PCA bidimensionale. Questo ci permette di visualizzare il risultato della classificazione in un formato bidimensionale, anche se il dataset originale ha quattro features.

KNN for classification - scatter plot all features

Proiezioni bidimensionali delle decision boundary del modello quadrimensionale senza la riduzione di dimensionalità porterebbero a conclusioni errate.

Se invece si vuole ragionare bidimensionalmente direttamente sulle feature, bisogna necessariamente sceglierne 2 delle quattro e costruire un nuovo modello di apprendimento KNN esclusivo su quelle due. Prendiamo per esempio le feature 1 e 2 del databases iris.

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score

# Loading the Iris dataset
iris = load_iris()
X = iris.data[:, :2]  # Utilizziamo solo le prime due features
y = iris.target

# Division of the dataset into training and test sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Creating a KNN classifier with 3 neighbors
knn = KNeighborsClassifier(n_neighbors=3)

# Classifier training
knn.fit(X_train, y_train)

# Prediction phase on the test set
y_pred = knn.predict(X_test)

# Calculation of model accuracy
accuracy = accuracy_score(y_test, y_pred)
print("Accuracy:", accuracy)

# Creating a meshgrid to display decision regions
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1),
                     np.arange(y_min, y_max, 0.1))

# Predicting classes for each point in the meshgrid
Z = knn.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)

# Create scatterplot to visualize data points and decision regions
plt.contourf(xx, yy, Z, cmap=ListedColormap(['red', 'green', 'blue']), alpha=0.3)
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=ListedColormap(['red', 'green', 'blue']), edgecolor='k', s=20)
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.title('KNN Classification Result')
plt.show()

Eseguendo si ottiene il seguente risultato:

Accuracy: 0.8
KNN for classification - bidimensional decision boundary

Graficamente potrebbe sembrare tutto molto coerente, con una buona corrispondenza tra i punti verdi dello scatterplot e le corrispondenti aree di appartenenza. Ma in realtà il valore di accuratezza è sceso da 1.0 (certezza) a 0.8. Questo perchè nell’apprendimento il modello ha perso moltissime informazioni contenute nelle altre due feature 3 e 4 che sebbene non facilmente rappresentabili (per noi) sono fondamentali per un buon livello di previsione da parte del modello.

Alcune Considerazioni sul modello K-Nearest Neighbor

Adesso che abbiamo un’idea su come funzioni K-Nearest Neighbor è importante fare alcune considerazioni utili per comprendere meglio tale modello.

  • Sensibilità alla dimensione e alla scala dei dati: K-NN è sensibile alla scala delle variabili, quindi è consigliabile normalizzare i dati prima di utilizzare l’algoritmo. Inoltre, in spazi ad alta dimensionalità, la distanza euclidea può diventare meno significativa, e questo può influenzare le prestazioni di K-NN.
  • Scelta del parametro k: La scelta del numero di vicini ((k)) è critica. Un valore (k) troppo piccolo può rendere il modello sensibile al rumore, mentre un valore (k) troppo grande può portare a un modello troppo generico. La scelta di (k) dovrebbe essere guidata dalla natura del problema e può richiedere l’uso di tecniche di ottimizzazione.
  • Computazionalmente costoso: Il principale svantaggio di K-NN è che può essere computazionalmente costoso, specialmente su dataset di grandi dimensioni. Calcolare la distanza tra tutti i punti può richiedere tempo, specialmente quando il numero di dimensioni è elevato.
  • Sensibile al rumore: K-NN può essere sensibile al rumore e agli outlier nei dati. La presenza di dati rumorosi o di outlier può influenzare negativamente le previsioni.
  • Memoria: K-NN richiede di memorizzare l’intero set di addestramento, il che può diventare problematico con grandi quantità di dati.
  • Non parametrico e adattativo: K-NN è un modello non parametrico, il che significa che non fa ipotesi rigide sulla forma della funzione di decisione. Questo lo rende adattativo a diverse forme di dati, ma può richiedere più dati per avere prestazioni ottimali.
  • Buono per dataset piccoli o con strutture complesse: K-NN può essere particolarmente utile quando si ha a che fare con dataset di dimensioni ridotte o con strutture complesse non facilmente modellabili con algoritmi parametrici.

In generale, K-NN è un algoritmo semplice e intuitivo, ma la sua efficacia dipende fortemente dalla natura del problema e dalla qualità dei dati. È spesso utilizzato come baseline o come parte di un ensemble di modelli più complessi.

Lascia un commento