Modifica di Apprendimento non supervisionato (sezione)

== Algoritmo K-means ==

L’algoritmo K-means fu presentato per la prima volta da Stuart P. Lloyd nell’articolo ''Least Squares Quantization in PCM'' (1982). L’autore descrive un metodo iterativo per la quantizzazione vettoriale, oggi riconosciuto come la base computazionale del K-means, e ne espone il principio scrivendo:

“necessary conditions […] that the quanta and associated quantization intervals of an optimum finite quantization scheme must satisfy.”

"condizioni necessarie […] che devono essere soddisfatti dai quanti e dagli intervalli di quantizzazione a essi associati in uno schema di quantizzazione finito ottimale." 

L’ottimizzazione si basa sul criterio di minimizzare la potenza media del rumore di quantizzazione, concetto che corrisponde alla minimizzazione dell’errore quadratico medio, oggi al centro del metodo K-means.<ref>Lloyd, ''Least Squares Quantization in PCM'', p. 129.</ref>

Il termine “K-means” era stato introdotto precedentemente da James MacQueen nel 1967, nell’articolo ''Some Methods for Classification and Analysis of Multivariate Observations'', in cui l'autore proponeva una versione stocastica dell’algoritmo. Tale formulazione differisce da quella oggi comunemente utilizzata, che è più riconducibile al metodo deterministico descritto da Lloyd.

K-means è uno degli strumenti più noti e ampiamente utilizzati per l'analisi non supervisionata. Assume che il numero di cluster sia fissato a priori e che ciascun cluster possa essere descritto da un centroide, inteso come media dei punti che lo compongono. L'obiettivo è minimizzare la somma delle distanze quadratiche tra ogni punto del dataset e il centroide del cluster cui viene assegnato.<ref>Aggarwal e Reddy, ''Data Clustering'', pp. 73–74.</ref>

Dal punto di vista matematico, dato un insieme di dati D = {x₁, x₂, ..., xₙ}, con xᵢ ∈ ℝᵈ, e una partizione in cluster C = {C₁, C₂, ..., C_K}, l’obiettivo è minimizzare la seguente funzione di costo, detta Sum of Squared Errors (SSE):

SSE(C) = ∑ (da k=1 a K) ∑ (xᵢ ∈ C_k) || xᵢ − c_k ||²

dove: c_k è il centroide del cluster C_k, calcolato come:
c_k = (1 / |C_k|) ∑ (xᵢ ∈ C_k) xᵢ

Dal punto di vista implementativo, l’algoritmo K-means si basa su una procedura iterativa che alterna due operazioni fondamentali: l’assegnazione dei punti ai centroidi e l’aggiornamento dei centroidi stessi. Queste fasi vengono ripetute fino al raggiungimento della convergenza.

Il funzionamento dell’algoritmo può essere descritto sinteticamente con il seguente pseudocodice:

<pre>
Algoritmo K-means
==============================
1: Scegliere K punti iniziali come centroidi 
2: Ripetere
3: Assegnare ciascun punto al centroide più vicino 
4: Ricalcolare ogni centroide come media dei punti assegnati 
5: Fino a che non viene soddisfatto un criterio di convergenza 
</pre><ref>Aggarwal e Reddy, ''Data Clustering'', p. 89.</ref>

In pratica, il procedimento inizia con l’inizializzazione casuale di K centroidi. Successivamente, ciascun punto viene associato al centroide più vicino secondo la distanza euclidea, e i centroidi vengono aggiornati ricalcolando la media dei punti che sono stati loro assegnati. Questa fase di riassegnazione e aggiornamento continua fino alla convergenza, ovvero fino a quando le assegnazioni non cambiano più in modo significativo.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 90.</ref>

K-means presenta però alcune limitazioni:

* Richiede di specificare a priori il numero k di cluster.

* Presuppone che i cluster abbiano forma sferica e dimensione simile (non è quindi adatto a cluster non convessi o con densità variabile).

* È sensibile all’inizializzazione: scelte diverse dei centroidi iniziali possono portare a soluzioni differenti.

* È soggetto alla convergenza verso minimi locali della funzione obiettivo.

* È influenzato dagli outlier, che possono spostare i centroidi in modo significativo.

* Assume implicitamente che tutte le feature abbiano lo stesso peso e la stessa scala: richiede quindi normalizzazione preventiva dei dati.