Sommario
1. Introduzione
2. Cosa fa l'algoritmo K-Means?
3. Implementazione in Python
4. Valutazione e interpretazione
5. Conclusioni e passi successivi
La maggior parte degli algoritmi di machine learning ampiamente utilizzati, come la regressione lineare, la regressione logistica, gli alberi decisionali e altri, sono utili per fare previsioni da dati etichettati, ovvero ogni input comprende valori di funzionalità con un valore di etichetta associato. Questo è ciò che viene chiamato Apprendimento supervisionato.
Tuttavia, spesso abbiamo a che fare con grandi quantità di dati a cui non è associata alcuna etichetta. Immagina un'azienda che deve comprendere i diversi gruppi di clienti in base al comportamento di acquisto, ai dati demografici, all'indirizzo e ad altre informazioni, in modo da poter offrire servizi, prodotti e promozioni migliori.
Questi tipi di problemi possono essere risolti con l'uso di Apprendimento non supervisionato tecniche. L'algoritmo K-Means è un algoritmo di apprendimento non supervisionato ampiamente utilizzato nel Machine Learning. Il suo approccio semplice ed elegante consente di separare un set di dati in un numero desiderato di K cluster distinti, consentendo così di apprendere modelli da dati non etichettati.
Come detto in precedenza, l'algoritmo K-Means cerca di partizionare i punti dati in un dato numero di cluster. I punti all'interno di ciascun cluster sono simili, mentre i punti nei diversi cluster presentano differenze considerevoli.
Detto questo, sorge spontanea una domanda: come definiamo la somiglianza o la differenza? Nel clustering K-Means, la distanza euclidea è la metrica più comune per misurare la somiglianza.
Nella figura seguente possiamo vedere chiaramente 3 gruppi diversi. Quindi, potremmo determinare i centri di ciascun gruppo e ogni punto sarebbe associato al centro più vicino.
In questo modo, matematicamente parlando, l'idea è di minimizzare il varianza all’interno del clusterla misura della somiglianza tra ciascun punto e il suo centro più vicino.
Eseguire l'attività nell'esempio precedente è stato semplice perché i dati erano bidimensionali e i gruppi erano chiaramente distinti. Tuttavia, poiché il numero delle dimensioni aumenta e vengono considerati diversi valori di K, abbiamo bisogno di un algoritmo per gestire la complessità.
Passaggio 1: scegli i centri iniziali (in modo casuale)
Dobbiamo seminare l'algoritmo con vettori centrali iniziali che possono essere scelti casualmente dai dati o generare vettori casuali con le stesse dimensioni dei dati originali. Guarda i diamanti bianchi nell'immagine qui sotto.
Passaggio 2: trova le distanze di ciascun punto dai centri
Ora calcoleremo la distanza di ciascun punto dati dai K centri. Quindi associamo ciascun punto al centro più vicino a quel punto.
Dato un set di dati con N voci e M caratteristiche, le distanze dai centri C può essere data dalla seguente equazione:
Dove:
K varia da 1 a K;
D è la distanza di un punto n da K centro;
X è il vettore punto;
C è il vettore centrale.
Quindi, per ciascun punto dati N avremo K distanze, quindi dobbiamo etichettare il vettore al centro con la distanza più piccola:
Dove D è un vettore con K distanze.
Passaggio 3: trova il K centroidi e ripetere
Per ciascuno dei K cluster, ricalcolare il baricentro. Il nuovo centroide è la media di tutti i punti dati assegnati a quel cluster. Quindi aggiornare le posizioni dei centroidi a quelle appena calcolate.
Controlla se i centroidi sono cambiati in modo significativo rispetto all'iterazione precedente. Questo può essere fatto confrontando le posizioni dei centroidi nell'iterazione corrente con quelle dell'ultima iterazione.
Se i centroidi sono cambiati in modo significativo, torna al passaggio 2. In caso contrario, l'algoritmo è convergente e il processo si interrompe. Vedi l'immagine qui sotto.
Ora che conosciamo i concetti fondamentali dell'algoritmo K-Means, è il momento di implementare una classe Python. I pacchetti utilizzati erano Numpy per i calcoli matematici, Matplotlib per la visualizzazione e il pacchetto Make_blobs di Sklearn per i dati simulati.
# import required packages
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
La lezione avrà le seguenti modalità:
Un metodo di costruzione per inizializzare i parametri di base dell'algoritmo: il valore K di cluster, il numero massimo di iterazioni max_iter, e la tolleranza tol valore per interrompere l'ottimizzazione quando non si riscontrano miglioramenti significativi.
Questi metodi mirano ad assistere il processo di ottimizzazione durante l'addestramento, come il calcolo della distanza euclidea, la scelta casuale dei centroidi iniziali, l'assegnazione del baricentro più vicino a ciascun punto, l'aggiornamento dei valori dei centroidi e la verifica se l'ottimizzazione converge.
Come accennato in precedenza, l'algoritmo K-Means è una tecnica di apprendimento non supervisionata, ovvero non richiede dati etichettati durante il processo di addestramento. In questo modo, è necessario un unico metodo per adattare i dati e prevedere a quale cluster appartiene ciascun punto dati.
Un metodo per valutare la qualità dell'ottimizzazione calcolando il errore quadratico totale dell'ottimizzazione. Ciò verrà esplorato nella sezione successiva.
Ecco il codice completo:
class Kmeans:# construct method for hyperparameter initialization
def __init__(self, k=3, max_iter=100, tol=1e-06):
self.k = k
self.max_iter = max_iter
self.tol = tol
# randomly picks the initial centroids from the input data
def pick_centers(self, X):
centers_idxs = np.random.choice(self.n_samples, self.k)
return X(centers_idxs)
# finds the closest centroid for each data point
def get_closest_centroid(self, x, centroids):
distances = (euclidean_distance(x, centroid) for centroid in centroids)
return np.argmin(distances)
# creates a list with lists containing the idxs of each cluster
def create_clusters(self, centroids, X):
clusters = (() for _ in range(self.k))
labels = np.empty(self.n_samples)
for i, x in enumerate(X):
centroid_idx = self.get_closest_centroid(x, centroids)
clusters(centroid_idx).append(i)
labels(i) = centroid_idx
return clusters, labels
# calculates the centroids for each cluster using the mean value
def compute_centroids(self, clusters, X):
centroids = np.empty((self.k, self.n_features))
for i, cluster in enumerate(clusters):
centroids(i) = np.mean(X(cluster), axis=0)
return centroids
# helper function to verify if the centroids changed significantly
def is_converged(self, old_centroids, new_centroids):
distances = (euclidean_distance(old_centroids(i), new_centroids(i)) for i in range(self.k))
return (sum(distances) < self.tol)
# method to train the data, find the optimized centroids and label each data point according to its cluster
def fit_predict(self, X):
self.n_samples, self.n_features = X.shape
self.centroids = self.pick_centers(X)
for i in range(self.max_iter):
self.clusters, self.labels = self.create_clusters(self.centroids, X)
new_centroids = self.compute_centroids(self.clusters, X)
if self.is_converged(self.centroids, new_centroids):
break
self.centroids = new_centroids
# method for evaluating the intracluster variance of the optimization
def clustering_errors(self, X):
cluster_values = (X(cluster) for cluster in self.clusters)
squared_distances = ()
# calculation of total squared Euclidean distance
for i, cluster_array in enumerate(cluster_values):
squared_distances.append(np.sum((cluster_array - self.centroids(i))**2))
total_error = np.sum(squared_distances)
return total_error
Ora utilizzeremo la classe K-Means per eseguire il clustering dei dati simulati. Per fare ciò, verrà utilizzato il file make_blobs pacchetto dalla libreria Sklearn. I dati sono costituiti da 500 punti bidimensionali con 4 centri fissi.
# create simulated data for examples
X, _ = make_blobs(n_samples=500, n_features=2, centers=4,
shuffle=False, random_state=0)
Dopo aver eseguito la formazione utilizzando quattro cluster, otteniamo il seguente risultato.
model = Kmeans(k=4)
model.fit_predict(X)
labels = model.labels
centroids =model.centroids
plot_clusters(X, labels, centroids)
In quel caso, l’algoritmo era in grado di calcolare con successo i cluster con 18 iterazioni. Dobbiamo però tenere presente che conosciamo già il numero ottimale di cluster dai dati simulati. Nelle applicazioni del mondo reale, spesso non conosciamo questo valore.
Come detto in precedenza, l'algoritmo K-Means mira a rendere il varianza all’interno del cluster il più piccolo possibile. La metrica utilizzata per calcolare tale varianza è la distanza euclidea quadrata totale dato da:
Dove:
p è il numero di punti dati in un cluster;
c_i è il vettore baricentro di un cluster;
K è il numero di cluster.
In parole, la formula sopra somma le distanze dei punti dati al baricentro più vicino. L'errore diminuisce all'aumentare del numero K.
Nel caso estremo di K = N, hai un cluster per ciascun punto dati e questo errore sarà zero.
Willmott, Paolo (2019).
Se tracciamo l'errore rispetto al numero di cluster e osserviamo dove il grafico “si piega”, saremo in grado di trovare il numero ottimale di cluster.
Come possiamo vedere, il grafico ha una “forma a gomito” e si piega a K = 4, il che significa che per valori maggiori di K la diminuzione dell'errore totale sarà meno significativa.
In questo articolo abbiamo trattato i concetti fondamentali alla base dell'algoritmo K-Means, i suoi usi e applicazioni. Inoltre, utilizzando questi concetti, siamo stati in grado di implementare da zero una classe Python che eseguiva il clustering dei dati simulati e spiegava come trovare il valore ottimale per K utilizzando uno scree plot.
Tuttavia, poiché si tratta di una tecnica non supervisionata, è necessario un ulteriore passaggio. L'algoritmo può assegnare con successo un'etichetta ai cluster, ma il significato di ciascuna etichetta è un compito che il data scientist o l'ingegnere del machine learning dovrà svolgere analizzando i dati di ciascun cluster.
Inoltre, lascerò alcuni punti per ulteriori approfondimenti:
- I nostri dati simulati utilizzavano punti bidimensionali. Prova a utilizzare l'algoritmo per altri set di dati e trova i valori ottimali per K.
- Esistono altri algoritmi di apprendimento non supervisionato ampiamente utilizzati come Clustering gerarchico.
- A seconda dell'ambito del problema, potrebbe essere necessario utilizzare altri parametri di errore come la distanza di Manhattan e la somiglianza del coseno. Prova a indagarli.
Codice completo disponibile Qui:
Fonte: towardsdatascience.com
