Inizializzazione

L'algoritmo inizia selezionando casualmente K centri iniziali dei cluster, noti anche come centroidi. Questi centroidi fungono da punti di partenza per ciascun cluster. Un approccio comune consiste nel scegliere casualmente K punti dati dal dataset come centroidi iniziali.

Fase di Assegnazione

In questa fase, ogni punto dati viene assegnato al centroide più vicino. La distanza viene solitamente misurata utilizzando la distanza euclidea, ma possono essere utilizzate anche altre metriche di distanza. Ogni punto dati viene inserito nel cluster rappresentato dal centroide più vicino.

Fase di Aggiornamento

Una volta che tutti i punti dati sono stati assegnati ai cluster, i centroidi vengono ricalcolati. Per ciascun cluster, il nuovo centroide viene calcolato come la media di tutti i punti dati appartenenti a quel cluster. In sostanza, il centroide viene spostato al centro del proprio cluster.

Iterazione

I passaggi 2 e 3 vengono ripetuti iterativamente. Ad ogni iterazione, i punti dati vengono riassegnati ai cluster in base ai centroidi aggiornati, e poi i centroidi vengono ricalcolati in base alle nuove assegnazioni dei cluster. Questo processo iterativo continua fino al raggiungimento di un criterio di arresto.

Convergenza

L'algoritmo si arresta quando si verifica una delle seguenti condizioni:

• I centroidi non cambiano in modo significativo: le posizioni dei centroidi si stabilizzano, ovvero nelle iterazioni successive vi è una variazione minima nelle loro posizioni;

• Le assegnazioni dei punti dati non cambiano: i punti dati rimangono negli stessi cluster, indicando che la struttura dei cluster è diventata stabile;

• È stato raggiunto il numero massimo di iterazioni: viene raggiunto un numero massimo predefinito di iterazioni. Questo impedisce che l'algoritmo venga eseguito indefinitamente.

Al termine della convergenza, l'algoritmo K-means ha suddiviso i dati in K cluster, ciascuno rappresentato dal proprio centroide. I cluster risultanti mirano ad essere coesi internamente e separati esternamente in base alla metrica di distanza scelta e al processo iterativo di raffinamento.