Machine Learning: Come funziona un algoritmo di clustering e il K-means

regressione lineare

Gli algoritmi di clustering sono procedure matematiche progettate per organizzare un insieme di dati.

Questi insiemi di dati sono gruppi omogenei o “cluster”, e il criterio applicato è quello delle caratteristiche simili dei dati stessi.

K-means è un algoritmo di clustering che esegue il training di un modello, mediante il raggruppa di oggetti tra loro simili

Estimated reading time: 8 minuti

Clustering

Gli algoritmi di clustering sono come i detective dei dati: il loro compito principale è identificare pattern e relazioni nascoste nei tuoi dati. Immagina di avere un cesto pieno di frutta mista e l’obiettivo è separare le mele dalle banane, gli agrumi dai kiwi. Gli algoritmi di clustering fanno proprio questo, ma su un grande set di dati, in modo più sofisticato e accurato di quanto potremmo fare manualmente.

Ecco alcuni punti chiave:

  1. Tipi di Algoritmi di Clustering:
    • Gerarchici: Costruiscono una gerarchia di cluster, suddividendo i dati in sottogruppi più piccoli.
    • Partitivi: Suddividono i dati in cluster separati senza gerarchia.
  2. Non Supervisionati: Gli algoritmi di clustering ricadono nella categoria degli algoritmi non supervisionati. Non hanno bisogno di dati da cui apprendere; raggiungono i risultati per cui sono progettati indipendentemente.
  3. Applicazioni:
    • Marketing Intelligence: Identificano segmenti di clientela.
    • Analisi delle Reti Sociali: Rilevano gruppi di utenti con interessi simili.
    • Data Science: Aiutano a scoprire tendenze nascoste nei dati.

Clustering e la cluster analisys

La Cluster Analysis è uno degli strumenti più potenti e utilizzati per i statistici e Data Scientist.

Per esempio se prendiamo un insieme di individui, possiamo conoscere il colore dei loro occhi e possiamo suddividere l’insieme in un numero di cluster pari al numero di colori degli occhi.

Quindi avremo un cluster contenente tutti gli individui con gli occhi azzurri, un altro contenente gli individui con gli occhi verdi e così via.

Possiamo estendere questo ragionamento, pensando a un numero maggiore di attributi. Immaginiamo che ogni individuo dell’insieme indossi una maglietta rossa o blu. Possiamo creare una nuova suddivisione in cluster per raggruppare tutti gli individui con gli occhi azzurri e la maglietta rossa, gli occhi azzurri e la maglietta blu, gli occhi verdi e la maglietta rossa e così via.

Quindi, in sostanza, preso un insieme di oggetti aventi un certo numero di attributi, questi possono essere utilizzati per separare gli oggetti in un numero qualunque di cluster.

Clustering e classificazione: differenze

Quindi il cluster assomiglia molto alla classe, la differenza sta nel modo con cui si procede.

Quando si effettua una classificazione si hanno una serie di classi note a priori e lo scopo è quello di capire a quale gruppo appartiene un oggetto osservando il valore dei suoi attributi.

Per fare questo, durante la fase di addestramento di un artefatto (modello) di classificazione, si parte da un insieme di oggetti dei quali si conosce già la categoria di appartenenza.

Attraverso l’analisi degli attributi degli oggetti appartenenti a una determinata classe si cerca di trovare un pattern comune. La classificazione è, quindi, un procedimento di apprendimento supervisionato dove la conoscenza di una determinata categoria esiste a prescindere dagli oggetti in essa raggruppabili.

Nella clusterizzazione, invece, si vuole estrapolare un certo numero di gruppi in cui è possibile separare gli oggetti di un insieme analizzando i valori dei loro attributi.

In questo caso non esistono classi predeterminate né esempi che le rappresentino.

L’algoritmo deve riuscire a identificare gli oggetti che “si somigliano” e raggrupparli tra loro. Di conseguenza la clusterizzazione è un algoritmo di tipo non supervisionato.

Clustering: tecniche

Ci sono più tecniche che permettono di clusterizzare un insieme di oggetti. Una prima importante suddivisione dipende dalla tecnica di generazione dei cluster stessi, che divide gli algoritmi in due categorie:

Algoritmi di clusterizzazione agglomerativi (bottom-up): Iniziano inserendo ogni oggetto dell’insieme in un proprio cluster per poi raggrupparli iterativamente fino al raggiungimento di una condizione specifica (es. numero di cluster desiderato).

Clustering agglomerativo
Clustering agglomerativo

Algoritmi di clusterizzazione divisivi (top-down): Iniziano inserendo tutti gli oggetti dell’insieme in un unico cluster per poi separarlo iterativamente in cluster più piccoli fino al raggiungimento di una condizione specifica.

Clustering divisivo
Clustering divisivo

Gli algoritmi di clustering si basano tutti su una metrica, puramente geometrica, che permette di identificare quanto simili sono due oggetti fra di loro. Infatti gli oggetti in esame vengono visti come insiemi di valori reali che ne rappresentano le caratteristiche (colore degli occhi, altezza, peso, ecc.).

Questi valori, a loro volta, possono essere raggruppati in modo da formare dei vettori che rappresentino punti in uno spazio euclideo.

Se consideriamo l’altezza come prima coordinata ed il peso come seconda, questi tre individui possono essere rappresentati dai seguenti vettori e quindi visualizzabili in uno spazio euclideo (in questo caso di sole due dimensioni).

Han: (180, 75)

Leia: (160, 50)

Chewbacca: (210, 130)

Visualizzazione sul piano cartesiano di Leia, Han e Chewbacca in funzione dell’altezza e del peso.

Leia, Han e Chewbacca su grafico
Leia, Han e Chewbacca su grafico

Maggiore è il numero degli attributi, maggiori saranno le dimensioni dello spazio in questione. Una volta che gli oggetti dell’insieme sono associati a punti nello spazio è possibile verificarne la “somiglianza” attraverso il concetto di distanza: più due punti sono vicini più saranno simili.

Le metriche principalmente utilizzate sono :

●Distanza euclidea.

●Distanza Manhattan.

●Distanza di Hamming.

K-means

L’algoritmo K-means è un metodo di clustering non supervisionato che suddivide un insieme di dati in (K) gruppi (o cluster) in base alle loro caratteristiche. Ecco come funziona:

  1. Scelta del Numero di Cluster ((K)): Prima di tutto, dobbiamo decidere quanti cluster vogliamo ottenere. Questo valore (K) rappresenta il numero di gruppi in cui suddividere i dati.
  2. Inizializzazione dei Centroidi: L’algoritmo seleziona casualmente (K) punti come centroidi iniziali. Ogni centroide rappresenta il “centro” di un cluster.
  3. Assegnazione dei Punti ai Cluster: Per ogni punto dati, calcoliamo la distanza dai centroidi e assegniamo il punto al cluster il cui centroide è più vicino. Questo crea (K) gruppi iniziali.
  4. Aggiornamento dei Centroidi: Calcoliamo il nuovo centroide per ciascun cluster, utilizzando la media dei punti assegnati a quel cluster.
  5. Iterazione: Ripetiamo i passaggi 3 e 4 fino a quando i centroidi non cambiano significativamente o fino a quando l’algoritmo converge.
  6. Obiettivo: L’obiettivo finale è minimizzare la varianza all’interno di ciascun cluster (cioè rendere i punti all’interno di un cluster simili tra loro) e massimizzare la varianza tra i cluster (cioè rendere i cluster diversi tra loro).

L’algoritmo K-means è ampiamente utilizzato in analisi dei dati, raggruppamento di utenti, segmentazione di clienti e altro ancora. Ricorda che la scelta di (K) e l’inizializzazione dei centroidi possono influenzare i risultati, quindi è importante eseguire diverse iterazioni e valutare i cluster ottenuti.

punti prima della clusterizzazione
Punti prima della clusterizzazione

A seguito della clusterizzazione tramite K-means i punti vengono suddivisi in cinque cluster, evidenziati in figura con colori diversi.

punti dopo algoritmo k-means
punti dopo algoritmo k-means

Ercole Palmeri

Autore