Riprendiamo gli articoli sull’uso pratico di metodi e strumenti di intelligenza artificiale e machine learning, dando uno sguardo agli algoritmi di clustering più utilizzati.

Cos’è il clustering

Il clustering è una tecnica che consente di raggruppare oggetti in modo non supervisionato, cioè senza poter sfruttare esempi da utilizzare come base di apprendimento. Ogni raggruppamento, o cluster, rappresenta una classe di appartenenza, dal significato analogo a quello utilizzato per la classificazione già vista nei precedenti articoli.

Non avendo a disposizione esempi da cui imparare, il clustering sfrutta delle similarità tra i dati che deve analizzare, similarità che possono essere di varia natura ma che in sostanza definiscono una distanza tra i punti del dataset (solitamente una distanza euclidea).

K-means

Il K-means è uno degli algoritmi di clustering più diffuso e più performante. Nonostante ciò è un algoritmo semplicissimo da implementare ed utilizzare.

K-means si basa sui cosiddetti centroidi. Il centroide è un punto appartenente allo spazio delle features che media le distanze tra tutti i dati appartenenti al cluster ad esso associato. Rappresenta quindi una sorta di baricentro del cluster ed in generale, proprio per le sue caratteristiche, non è uno dei punti del dataset.

L’algoritmo di clustering di K-means è molto semplice:

1. Non conoscendo le classi presenti nel dataset di ingresso, la prima cosa da fare è decidere il numero di classi (o meglio cluster, in questo caso) in cui si vuole suddividere il dataset stesso. Questo numero è detto K, da cui il nome del metodo K-means (il termine means sottintende l’uso dei centroidi, cioè di punti medi).
2. Si scelgono in modo casuale K centroidi appartenenti allo spazio delle features. L’unica condizione è che non siano coincidenti, anzi solitamente ci si assicura che siano abbastanza distanti tra loro. In caso contrario l’algoritmo potrebbe avere problemi a convergere.
3. Si calcola la distanza di ogni punto del dataset rispetto ad ogni centroide.
4. Ogni punto del dataset viene associato al cluster collegato al centroide più vicino.
5. Si ricalcola la posizione di ogni centroide facendo la media delle posizioni di tutti i punti del cluster associato (solo di questi punti!)
6. Si itera dal punto 3 fino a quando non ci sarà più alcun ingresso che cambia di cluster.

In figura è possibile vedere graficamente questa iterazione.

Il metodo del gomito (elbow method)

Come si può vedere, i dati di ingresso dell’animazione precedente sono tali da costituire 3 raggruppamenti già individuabili ad occhio. In generale la situazione non è così semplice e quindi potrebbe non essere così immediato individuare il numero di cluster da utilizzare.

E’ però possibile utilizzare un metodo maggiormente oggettivo per decidere questo numero: il cosiddetto elbow method o metodo del gomito.

In pratica si itera il K-means per diversi valori di K ed ogni volta si calcola la somma delle distanze al quadrato tra ogni centroide ed i punti del proprio cluster.

Graficando i valori di K (asse orizzontale) e i valori della somma delle distanze al quadrato (asse verticale), si ottiene un grafico simile a quello in figura. Questo grafico deve essere letto da destra verso sinistra. Si deve trovare il punto in cui la curva tende a salire in modo più consistente.

Nella figura in esempio si nota che dal valore K=9 a K=3 la curva sale in modo quasi lineare. Dal valore K=3 a K=1 la curva sale in modo più evidente. Ciò significa che il valore K=3 è il nostro gomito (pensando alla curva come ad un braccio con la mano in K=9, il gomito in K=3 e la spalla in K=1), da cui il nome del metodo.

Il numero ottimale di cluster è quello in cui è posizionato il gomito.

Codice Python

NOTA: il codice di questo esempio lo trovi qui

Anche in questo caso la libreria SciKitLearn gestisce i modelli K-means tramite una classe ad hoc. Prima di tutto creiamo un dataset random utilizzando una funzione sempre di SciKitLearn con la quale possiamo decidere il numero di esempi, il numero di macrogruppi, la deviazione standard eccetera. Essendo un apprendimento non supervisionato, preleviamo solo i dati di input X e non i target Y (che come si nota nel codice viene sostituito dal simbolo underscore che in Python serve proprio per scartare un risultato.

# creo un dataset casuale con 4 macroaree e un random_state fisso 
# per rendere ripetibili le prove
# NOTA: scarto i valori target (y) perchè il clustering è uno strumento "unsupervised" 
# Quindi, nella pratica, non ho esempi da utilizzare per l'addestramento
X, _ = make_blobs(n_samples=500, centers=4, cluster_std=0.8, random_state=1234)

Graficando il dataset prodotto, è possibile notare ad occhio i 4 macro raggruppamenti.

Chiaramente si tratta di un esempio, in generale i dati non sono così ben suddivisi.

Addestro il modello indicando di volere 4 cluster. Poi eseguo la predizione dei dati in input in modo da assegnare ad ogni punto un cluster. Inoltre ottengo anche le posizioni dei centroidi tramite la proprietà cluster_centers_ del modello.

# istanzio la classe di gestione di K-Means e un numero di cluster pari a 4
km = KMeans(n_clusters=4)
km.fit(X)

# assegno una classe ad ogni esempio del dataset
y = km.predict(X)

# ottengo i "centroidi" dei cluster
centroids = km.cluster_centers_

Infine grafico il tutto utilizzando i colori per individuare i cluster e segnando in rosso i centroidi.

Come si può notare ogni centroide è posizionato nel centro geometrico del rispettivo cluster, come ci si aspettava. Inoltre noterete che l’esecuzione dell’addestramento è estremamente veloce.

Ora, come già detto, nella realtà è molto improbabile riuscire ad individuare ad occhio il numero di cluster, anche perchè solitamente si lavora in uno spazio delle features multidimensionale. Verifichiamo quindi che la scelta del numero di cluster sia corretto, utilizzando il metodo del gomito.

Iteriamo il procedimento di addestramento del modello per diversi valori di K e memorizziamo, per ognuno di esso, il valore della somma delle distanze al quadrato. Niente paura, non dovremo calcolarlo noi, perchè come al solito ci penserà SciKitLearn che lo mette a disposizione tramite la proprietà intertia_ del nostro modello.

# verifico il numero di cluster ideali utilizzando l'elbow-method
# preparo un dizionario dove memorizzerò i valori della somma delle distanze al quadrato 
# di ogni valore di K testato
sdq = {}
for k in range(1, 10):
    # istanzio la classe di gestione di K-Means e un numero di cluster pari al k attuale
    # NOTA: utilizzo l'inizializzazione "k-means++" che inizializza i centroidi 
    # in modo casuale ma garantendo che non si trovino troppo vicini l'uno con l'altro, 
    # per minimizzare i problemi che questo porterebbe, soprattutto con valori di K elevati
    km = KMeans(init="k-means++", n_clusters=k)
    km.fit(X)

    # per il k attuale, memorizzo il valore di ssd
    sdq[k] = km.inertia_

Graficando i valori così ottenuti, ottengo un grafico simile a quello visto in precedenza, dove si nota che da K=9 a K=4 la curva ha un comportamento quasi lineare e poi inizia a salire sempre più ripidamente.

Questo indica che, in questo caso, il valore K=4 è quello migliore.

See you soon!

Potete allenarvi creando un dataset con caratteristiche diverse o utilizzando uno dei dataset già visti per la classificazione o altri dataset che avete a disposizione e infine verificare il comportamento del modello.

Noi ci vediamo al prossimo articolo!

Bye!