di Sergio Mauri
L’algoritmo di clustering K-means è un algoritmo di apprendimento non supervisionato utilizzato per raggruppare dati simili in un insieme di dati in un numero prestabilito di cluster. La sua formula si basa su un processo iterativo che cerca di minimizzare la somma delle distanze quadrate intra-cluster. Ecco la sua formulazione:
Supponiamo di avere n osservazioni x1,x2,…,xn da raggruppare in k cluster.
- Inizializzazione:
- Scegliere casualmente k centroidi iniziali μ1,μ2,…,μk dall’insieme di dati.
- Assegnazione dei cluster:
- Per ogni osservazione xi, calcolare la distanza tra xi e ciascun centroide μj.
- Assegnare xi al cluster il cui centroide è più vicino, ovvero assegnare xi al cluster j dove j=argminj∥xi−μj∥^2.
- Aggiornamento dei centroidi:
- per ciascun cluster j, calcolare il nuovo centroide μj come la media di tutti gli elementi assegnati al cluster j, ovvero: μj=1/∣Cj∣ ∑xi ∈ Cj^xi
- dove ∣Cj∣ rappresenta il numero di elementi nel cluster j.
- Ripetizione:
- Ripetere i passaggi 2 e 3 fino a quando i centroidi non cambiano significativamente o fino a quando viene raggiunto un numero prefissato di iterazioni.
- L’obiettivo dell’algoritmo K-means è di minimizzare la somma delle distanze quadrate intra-cluster, cioè minimizzare la funzione obiettivo: J=∑ (k superiore) j (inferiore =1 ∑xi ∈Cj ∥xi−μj∥^2
- dove Cj è il cluster j, μj è il centroide del cluster j, e ∥⋅∥^2 rappresenta la distanza euclidea quadra.
L’algoritmo di clustering K-means è iterativo e può convergere a un minimo locale della funzione obiettivo, ma non garantisce la soluzione ottimale globale. La scelta iniziale dei centroidi può influenzare notevolmente i risultati dell’algoritmo K-means, quindi spesso vengono eseguiti più tentativi con diverse inizializzazioni per ottenere una soluzione migliore.
