K-means è uno degli algoritmi di clustering più popolari e ampiamente utilizzati nel campo del machine learning e dell’analisi dei dati. Si tratta di un algoritmo di apprendimento non supervisionato che mira a partizionare un insieme di dati in K cluster distinti. Il termine “K” in K-means indica il numero di cluster desiderato.
K-Means
L’algoritmo K-means fu proposto per la prima volta da Stuart Lloyd nel 1957 come metodo di quantizzazione vettoriale per la trasmissione di segnali a banda ridotta. Tuttavia, il nome “K-means” è stato coniato da James MacQueen nel 1967, e l’algoritmo è stato ulteriormente sviluppato e popolarizzato negli anni successivi. Dopo l’introduzione di MacQueen, l’algoritmo K-means è stato soggetto a numerosi sviluppi e miglioramenti. Diverse varianti sono state proposte per affrontare le sfide legate alla sensibilità all’inizializzazione dei centroidi, alla convergenza e alla scalabilità. Nel corso degli anni, l’algoritmo K-means è diventato ampiamente utilizzato in una varietà di campi, tra cui l’apprendimento automatico, l’analisi dei dati, la computer vision, la bioinformatica e altro ancora. La sua semplicità concettuale e la sua efficacia lo hanno reso uno degli algoritmi di clustering più popolari e utilizzati.
In generale, K-means è utile quando si desidera esplorare la struttura intrinseca di un insieme di dati non etichettato o quando si vuole raggruppare i dati in modo da poter prendere decisioni più informate o estrarre conoscenze utili dai dati stessi. Tuttavia, è importante notare che il K-means ha alcune limitazioni, come la sensibilità alla scelta del numero di cluster e alla distribuzione iniziale dei centroidi, che devono essere prese in considerazione durante l’analisi dei risultati.
Esso le varie fasi dell’algoritmo K-Means
Inizializzazione: inizialmente, vengono scelti casualmente K centroidi iniziali, uno per ogni cluster. Questi centroidi possono essere selezionati casualmente dai punti dati stessi o da una distribuzione casuale.
Assegnazione: per ogni punto dati ( x_i ), viene calcolata la sua distanza rispetto a ciascun centroide utilizzando una metrica di distanza, di solito la distanza euclidea. La formula per calcolare la distanza euclidea tra due punti ( x_i ) e ( c_j ) è:
dove ( D ) è il numero di dimensioni dei dati e ( x_{i,d} ) e ( c_{j,d} ) sono le coordinate del punto ( x_i ) e del centroide ( c_j ) nella dimensione ( d ). Una volta calcolate le distanze, il punto ( x_i ) viene assegnato al cluster il cui centroide è più vicino.
Ricalcolo dei centroidi: dopo che tutti i punti sono stati assegnati a un cluster, i centroidi vengono ricalcolati come la media dei punti assegnati a ciascun cluster. La formula per calcolare il nuovo centroide ( c_j ) per il cluster ( j ) è:
dove ( N_j ) è il numero di punti nel cluster ( j ) e ( x_i ) sono i punti assegnati al cluster ( j ).
Iterazione: i passaggi di assegnazione e ricalcolo dei centroidi vengono ripetuti iterativamente fino a quando i centroidi non cambiano significativamente di posizione o fino a quando non si raggiunge un numero massimo di iterazioni.
Convergenza: l’algoritmo converge quando i centroidi convergono verso posizioni fisse e i cluster diventano stabili.
Questo è il processo principale del K-means. La scelta del numero ottimale di cluster ( K ) è importante e può essere determinata utilizzando metodi come il metodo del gomito o la validazione incrociata.
K-Means con Scikit-Learn
L’algoritmo K-means è implementato nella libreria scikit-learn, che è una delle librerie più popolari per il machine learning in Python. Scikit-learn offre un’implementazione efficiente e flessibile dell’algoritmo K-means attraverso la classe KMeans.
Proviamo ora a realizzare un semplice esempio per vedere come implementare ed utilizzare l’algoritmo K-means con la libreria scikit-learn in Python.
Per prima cosa, pensiamo ai dati di partenza. A tal proposito, possiamo utilizzare make_blobs. Questa è una funzione fornita dalla libreria scikit-learn che consente di generare insiemi di dati sintetici utilizzati spesso per scopi di test e dimostrazione in algoritmi di machine learning. Questa funzione genera cluster di punti casuali in uno spazio bidimensionale o tridimensionale, con i centroidi dei cluster specificati e la deviazione standard dei cluster.
In pratica, make_blobs genera un numero specificato di campioni casuali distribuiti intorno a centroidi specificati, con una deviazione standard specificata che controlla la dispersione dei punti all’interno di ciascun cluster.
Questa funzione è utile per creare dataset di prova con diversi livelli di complessità e strutture di cluster, consentendo agli sviluppatori e ai ricercatori di testare e confrontare algoritmi di clustering, classificazione e altre tecniche di apprendimento automatico su dati sintetici prima di applicarli a dati reali.
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
# Generate random data using make_blobs function
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)
# Visualize the generated data
plt.scatter(X[:, 0], X[:, 1], s=50)
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.title('Generated Data')
plt.show()Eseguendo il codice otterremo la rappresentazione grafica dei punti generati da make_blobs.
Come si può vedere, la funzione make_blobs ci ha generato dei dati casuali già raggruppati in 4 gruppi differenziati. Adesso possiamo passare ad applicare su di essi l’algoritmo K-means per il clustering.
kmeans = KMeans(n_clusters=4)
kmeans.fit(X)Qui stiamo istanziando un oggetto KMeans dalla libreria scikit-learn con n_clusters=4, il che significa che vogliamo trovare 4 cluster nei nostri dati. Successivamente, chiamiamo il metodo fit(X) su questo oggetto per adattare il modello ai dati X generati precedentemente.
labels = kmeans.labels_
centroids = kmeans.cluster_centers_Dopo aver adattato il modello ai dati, otteniamo due importanti risultati:
labels: Questo è un array che contiene le etichette dei cluster assegnate a ciascun punto dati. Ogni etichetta indica a quale cluster appartiene il rispettivo punto.centroids: Questa è una matrice che contiene le coordinate dei centroidi dei cluster trovati dall’algoritmo. I centroidi sono i “punti medi” dei cluster, e rappresentano le posizioni centrali dei gruppi di dati.
Adesso riportiamo tutto il codice necessario:
# Apply K-means algorithm for clustering
kmeans = KMeans(n_clusters=4)
kmeans.fit(X)
# Get cluster labels and centroids
labels = kmeans.labels_
centroids = kmeans.cluster_centers_
# Visualize clusters and centroids found
plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap='viridis')
plt.scatter(centroids[:, 0], centroids[:, 1], marker='*', c='red', s=200, label='Centroids')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.title('Clustering with K-means')
plt.legend()
plt.show()Eseguendo si ottiene il risultato seguente:
Come possiamo vedere abbiamo ottenuto un grafico in cui sono evidenziati i 4 cluster identificati con 4 colori diversi. Inoltre vengono riportati i centroidi di ciascun cluster, con un marker a stella.
Valutazione dei risultati ottenuti
Il clustering è un compito non supervisionato, il che significa che non abbiamo etichette di classe note per valutare direttamente le prestazioni del modello. Tuttavia, esistono diverse metriche e tecniche che possono essere utilizzate per valutare la qualità dei cluster ottenuti.
Utilizziamo ora alcune di queste metriche di valutazione per valutare il clustering ottenuto con l’algoritmo K-means nell’esempio precedente.
- Silhouette Score: Questa metrica fornisce una misura della coesione e della separazione dei cluster. Un valore più alto indica che i cluster sono ben separati.
- Davies-Bouldin Score: Questa metrica misura la “dispersione” tra i cluster. Un valore più basso indica cluster più compatti e ben separati.
from sklearn.metrics import silhouette_score, davies_bouldin_score
silhouette_avg = silhouette_score(X, labels)
print("Silhouette Score:", silhouette_avg)
davies_bouldin = davies_bouldin_score(X, labels)
print("Davies-Bouldin Score:", davies_bouldin)È importante notare che queste metriche vengono calcolate utilizzando solo i dati e le etichette dei cluster, senza richiedere etichette di classe reali. Questo le rende molto utili per valutare il clustering non supervisionato. Eseguendo si ottengono risultati simili al seguente:
Silhouette Score: 0.6819938690643478
Davies-Bouldin Score: 0.43756400782378385Come dobbiamo valutarli?
Silhouette Score
Questo valore varia da -1 a 1. Un punteggio più vicino a 1 indica che i campioni sono ben assegnati ai propri cluster e che i cluster sono ben separati l’uno dall’altro. Un punteggio più vicino a -1 indica che molti campioni sono stati assegnati a cluster sbagliati. Un punteggio vicino a 0 indica che i cluster possono sovrapporsi. Nel nostro caso, un Silhouette Score di 0.68 suggerisce che i cluster sono ben separati e che i campioni sono ben assegnati ai propri cluster. È un buon risultato e indica una buona struttura del clustering.
Davies-Bouldin Score
Questo valore è un rapporto tra la “dispersione” media intra-cluster e la “dispersione” inter-cluster. Un valore più basso indica cluster più compatti e ben separati. Nel nostro caso, un Davies-Bouldin Score di 0.44 suggerisce che i cluster sono abbastanza compatti e ben separati. Anche questo è un buon risultato e conferma la coesione e la separazione dei cluster.
In generale, valutando insieme questi due punteggi, possiamo dire che il clustering ha prodotto risultati positivi e che i cluster sono ben definiti e separati tra loro. Tuttavia, è sempre consigliabile confrontare questi risultati con altri metodi di valutazione e con la conoscenza del dominio per una valutazione più completa.
Passiamo all’analisi visiva:
Iniziamo osservando la visualizzazione dei cluster. Dopo aver eseguito l’algoritmo K-means, abbiamo plottato i punti dati colorati in base ai cluster ai quali sono stati assegnati. Ogni colore rappresenta un cluster diverso. Inoltre, abbiamo contrassegnato i centroidi dei cluster con stelle rosse. Guardando la visualizzazione dei cluster, sembra che i dati siano stati raggruppati in modo coerente. I punti all’interno di ciascun cluster sembrano essere abbastanza vicini tra loro, mentre i centroidi sembrano essere al centro dei rispettivi cluster.
In sintesi, guardando sia la visualizzazione dei cluster che i punteggi delle metriche di valutazione, possiamo concludere che il clustering ottenuto con l’algoritmo K-means sembra essere significativo e di buona qualità. I cluster sono ben definiti e separati, e i centroidi sono posizionati in modo significativo rispetto ai dati.
Un caso più reale: il problema del numero dei cluster
Nell’esempio precedente abbiamo scelto arbitrariamente di utilizzare 4 cluster, perchè sapevamo che la funzione make_blobs ci avrebbe fornito 4 cluster. Nei casi reali, però il numero dei cluster presenti ci è ovviamente sconosciuta. Tuttavia, la scelta del numero ottimale di cluster è una decisione cruciale nel clustering e può influenzare significativamente i risultati. È importante considerare tecniche come il metodo del gomito o il metodo della silhouette per determinare il numero ottimale di cluster in base alla struttura dei dati.
Il Metodo del Gomito
Questa volta, ripartiamo dal presupposto di non conoscere il numero ottimale di cluster ottenibili dal nostro dataset di partenza. Come fare per conoscere quale è il numero dei cluster con cui applicare K-Means? Bene, esiste il metodo del gomito e vediamo come applicarlo al nostro esempio.
Per farlo, si calcolano le inerzie. Le inerzie (o “inertias” in inglese) sono una misura della coesione dei cluster in un algoritmo di clustering. Nel contesto dell’algoritmo K-means, l’inertia rappresenta la somma delle distanze quadrate dei punti dati rispetto ai centroidi dei rispettivi cluster. In altre parole, è una misura di quanto i punti all’interno di ciascun cluster siano vicini al centroide del cluster stesso.
Più specificamente, l’inertia è calcolata come la somma dei quadrati delle distanze tra ciascun punto dati e il centroide del cluster a cui appartiene. Un valore più basso di inertia indica che i punti all’interno dei cluster sono più vicini al centroide, quindi i cluster sono più compatti e coerenti.
Nel contesto del metodo del gomito per la scelta del numero ottimale di cluster, l’inertia è utile perché ci fornisce una misura della “qualità” complessiva del clustering per un determinato numero di cluster. Nel tracciare l’inertia rispetto al numero di cluster, possiamo cercare il punto in cui l’inertia smette di diminuire drasticamente, suggerendo il numero ottimale di cluster da utilizzare. Questo punto spesso forma un “gomito” nel grafico, da cui deriva il nome del metodo.
Scriviamo il codice che svolge il calcolo delle inerzie sul nostro dataset. Nel nostro caso, consideremo un numero di cluster possibili tra 1 e 10.
# List to store inertias
inertias = []
# Try a number of clusters from 1 to 10
for i in range(1, 11):
kmeans = KMeans(n_clusters=i)
kmeans.fit(X)
# Calculate inertia and store in the list
inertias.append(kmeans.inertia_)
# Plot inertia versus number of clusters
plt.plot(range(1, 11), inertias, marker='o')
plt.xlabel('Number of Clusters')
plt.ylabel('Inertia')
plt.title('Elbow Method for Choosing Number of Clusters')
plt.show()Eseguendo si ottiene il seguente risultato:
Abbiamo ottenuto il caratteristico “gomito” dove il numero 4 rappresenta proprio il punto corrispondente al gomito. Questo numero è il numero dei cluster ottimali identificabili nel nostro dataset.
Il calcolo dell’inertia per diverse configurazioni di cluster può essere computazionalmente oneroso, soprattutto quando si lavora con grandi quantità di dati o con un numero elevato di dimensioni. Poiché l’inertia coinvolge il calcolo delle distanze tra ogni punto dati e il centroide del cluster corrispondente, il numero di operazioni richieste può aumentare rapidamente con il numero di punti dati e il numero di cluster.
Tuttavia, per molte applicazioni, l’analisi del metodo del gomito è ancora fattibile. Spesso, è sufficiente eseguire questo calcolo su un sottoinsieme rappresentativo dei dati anziché sull’intero set di dati. Inoltre, la crescita esponenziale nel tempo di calcolo può essere mitigata utilizzando tecniche di ottimizzazione e parallelizzazione, specialmente quando si utilizzano librerie efficienti come scikit-learn in Python.
In generale, è importante bilanciare la complessità computazionale con l’accuratezza delle decisioni prese tramite il metodo del gomito. Potrebbe essere necessario eseguire un’analisi più dettagliata del numero ottimale di cluster solo quando è richiesta una maggiore precisione e quando si hanno le risorse computazionali necessarie per farlo.
Il Metodo della Silhouette
Il metodo della silhouette è un’altra tecnica utilizzata per valutare la coesione e la separazione dei cluster e può essere utilizzato per determinare il numero ottimale di cluster in un set di dati. Questo metodo fornisce una misura della qualità complessiva del clustering per un determinato numero di cluster, e il numero ottimale di cluster può essere identificato massimizzando il valore medio della silhouette su tutti i campioni.
Per ogni punto dati nel set, calcoliamo il punteggio silhouette. Il punteggio silhouette di un punto misura quanto è simile al proprio cluster rispetto agli altri cluster. Viene calcolato come:
Dove:
- ( s_i ) è il punteggio silhouette del punto ( i ).
- ( a_i ) è la distanza media del punto ( i ) agli altri punti nello stesso cluster.
- ( b_i ) è la distanza media del punto ( i ) ai punti nel cluster più vicino diverso da quello a cui appartiene il punto ( i ).
Dopo aver calcolato il punteggio silhouette per ogni punto, calcoliamo il punteggio silhouette medio su tutti i punti. Questo ci fornisce una misura complessiva della qualità del clustering per un determinato numero di cluster.
Ripetiamo il processo di clustering e calcolo della silhouette score per diversi valori di K (numero di cluster). Il numero ottimale di cluster è quello che massimizza il valore medio della silhouette score.
In pratica, possiamo tracciare il valore medio della silhouette score in funzione del numero di cluster e individuare il punto in cui il valore è massimo. Questo è spesso indicato come il numero ottimale di cluster da utilizzare.
Vediamo questo metodo applicato al nostro esempio:
from sklearn.metrics import silhouette_score
# List to store silhouette scores
silhouette_scores = []
# Try a number of clusters from 2 to 10
for i in range(2, 11):
kmeans = KMeans(n_clusters=i)
kmeans.fit(X)
# Calculate silhouette scores and store in the list
silhouette_avg = silhouette_score(X, kmeans.labels_)
silhouette_scores.append(silhouette_avg)
# Plot silhouette scores versus number of clusters
plt.plot(range(2, 11), silhouette_scores, marker='o')
plt.xlabel('Number of Clusters')
plt.ylabel('Average Silhouette Score')
plt.title('Silhouette Method for Choosing Number of Clusters')
plt.show()In questo codice, stiamo calcolando il punteggio silhouette per un numero di cluster da 2 a 10. Per ogni valore di i, addestriamo un modello K-means con il numero corrente di cluster e calcoliamo il punteggio silhouette medio per i punti dati utilizzando la funzione silhouette_score dalla libreria scikit-learn. I punteggi silhouette medi vengono quindi memorizzati nella lista silhouette_scores. Infine, tracciamo i punteggi silhouette medi rispetto al numero di cluster utilizzando plt.plot(), e identifichiamo il numero ottimale di cluster dove il punteggio silhouette medio è massimo.
Eseguendo si ottiene il seguente grafico:
Il numero ottimale di cluster è quello che massimizza il valore medio della silhouette score. Possiamo individuare il numero di cluster in corrispondenza del picco del grafico dei punteggi silhouette, che anche in questo caso corrisponde al valore 4.