Come accennato in precedenza, molti algoritmi di clustering non scalano per i set di dati. utilizzate nel machine learning, che spesso hanno milioni di esempi. Ad esempio: gli algoritmi di clustering gerarchico agglomerativo o divisivo prendono in considerazione tutte le coppie di punti e presentano complessità di \(O(n^2 log(n))\) e \(O(n^2)\), rispettivamente.
Questo corso si concentra su K-means perché scala come \(O(nk)\), dove \(k\) è il numero di cluster scelti dall'utente. Questo algoritmo raggruppa i punti \(k\) di cluster riducendo al minimo le distanze tra ciascun punto e baricentro del cluster (vedi Figura 1).
Di conseguenza, K-means tratta in modo efficace i dati come composti da una serie di distribuzioni circolari e cerca di trovare cluster corrispondenti distribuibili. Ma i dati del mondo reale contengono outlier e cluster basati sulla densità e potrebbe non corrispondere alle ipotesi alla base di K-means.
Algoritmo di clustering K-means
L'algoritmo segue questi passaggi:
Fornisci un'ipotesi iniziale per \(k\), che potrà essere modificata in seguito. Per questo ad esempio \(k = 3\).
Scegli \(k\) i centrii in modo casuale.
Figura 1: k-means all'inizializzazione. Assegna ogni punto al centroide più vicino per ottenere \(k\) i cluster iniziali.
Figura 2: cluster iniziali. Per ogni cluster, calcola un nuovo baricentro prendendo la posizione media in tutti i punti del cluster. Le frecce nella Figura 4 mostrano la modifica della delle posizioni del baricentro.
Figura 3: centroidi ricalcolati. Riassegna ogni punto al nuovo centroide più vicino.
Figura 4: cluster dopo la riassegnazione. Ripeti i passaggi 4 e 5, ricalcolando i centroidi e l'appartenenza al cluster, finché non cambiano più i cluster. Nel caso di set di dati di grandi dimensioni, è possibile interrompere l'algoritmo prima della convergenza in base ad altri criteri.
Poiché le posizioni del baricentro sono inizialmente scelte in modo casuale, k-means può restituiscono risultati significativamente diversi nelle esecuzioni successive. Per risolvere il problema, problema, esegui K-means più volte e scegli il risultato con la qualità migliore metriche di valutazione. Descriveremo le metriche relative alla qualità più avanti in questo corso. È necessaria una versione avanzata di K-means per scegliere posizioni iniziali migliori del baricentro.
Sebbene non sia necessaria una profonda comprensione della matematica, per coloro che curioso, K-means è un caso speciale del algoritmo di massimizzazione delle aspettative. Consulta appunti sulle lezioni sull'argomento di UPenn.