Che cos'è il clustering K-means?

Come accennato in precedenza, molti algoritmi di clustering non sono scalabili ai set di dati utilizzati nel machine learning, che spesso contengono milioni di esempi. Ad esempio, gli algoritmi di clustering gerarchico aggregativo o divisibile esaminano tutte le coppie di punti e hanno complessità di $O(n^2 log(n))$ e $O(n^2)$, rispettivamente.

Questo corso si concentra su K-means perché è scalabile come $O(nk)$, dove $k$ è il numero di cluster scelti dall'utente. Questo algoritmo raggruppa i punti in$k$ cluster riducendo al minimo le distanze tra ciascun punto e il centroide del cluster (vedi Figura 1).

Di conseguenza, k-means tratta efficacemente i dati come composti da un numero di distribuzioni approssimativamente circolari e cerca di trovare cluster corrispondenti a queste distribuzioni. Tuttavia, i dati reali contengono valori anomali e cluster basati sulla densità e potrebbero non corrispondere alle ipotesi alla base di k-means.

Algoritmo di clustering K-means

L'algoritmo segue questi passaggi:

1. Fornisci una stima iniziale per $k$, che può essere rivista in un secondo momento. Per questo esempio, scegliamo $k = 3$.

2. Scegli $k$ centroidi in modo casuale.

   

   Figura 1: k-means all'inizializzazione.

3. Assegna ogni punto al centroide più vicino per ottenere i $k$ cluster iniziali.

   

   Figura 2: cluster iniziali.

4. Per ogni cluster, calcola un nuovo centroide prendendo la posizione media di tutti i punti del cluster. Le frecce nella Figura 4 mostrano la variazione delle posizioni del baricentro.

   

   Figura 3: centroidi ricalcolati.

5. Riassegna ogni punto al nuovo centroide più vicino.

   

   Figura 4: cluster dopo la riassegnazione.

6. Ripeti i passaggi 4 e 5, ricalcolando i centroidi e l'appartenenza ai cluster, finché i punti non cambiano più cluster. Nel caso di set di dati di grandi dimensioni, puoi interrompere l'algoritmo prima della convergenza in base ad altri criteri.

Poiché le posizioni dei centroidi vengono scelte inizialmente in modo casuale, k-means può fornire risultati significativamente diversi nelle esecuzioni successive. Per risolvere questo problema, esegui k-means più volte e scegli il risultato con le migliori metriche di qualità. Descriveremo le metriche sulla qualità più avanti in questo corso. Per scegliere posizioni iniziali dei centroidi migliori, è necessaria una versione avanzata di k-means.

Anche se non è necessaria una conoscenza approfondita della matematica, per chi è curioso, k-means è un caso speciale dell'algoritmo di massimazione dell'aspettativa. Consulta le note del corso sull'argomento della UPenn.