Esegui l'algoritmo di clustering

Nel machine learning, a volte si incontrano set di dati che possono contenere milioni di esempi. Gli algoritmi di machine learning devono essere in grado di scalare in modo efficiente fino a questi grandi set di dati. Tuttavia, molti algoritmi di clustering non scalano perché devono calcolare la somiglianza tra tutte le coppie di punti. Ciò significa che i suoi runtime aumentano al quadrato del numero di punti, contrassegnato come \(O(n^2)\). Ad esempio, gli algoritmi di clustering 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 è incentrato su k-means perché scala come \(O(nk)\), dove \(k\) è il numero di cluster. k-means raggruppa i punti in \(k\) cluster riducendo al minimo le distanze tra i punti e il centroid del loro cluster (come mostrato nella Figura 1 di seguito). Il centroid di un cluster è la media di tutti i punti nel cluster.

Come mostrato, k-means individua un cluster all'incirca circolare. Concettualmente, questo significa che k-mean tratta in modo efficace i dati come composti da una serie di distribuzioni approssimativamente circolari e cerca di trovare cluster corrispondenti a queste distribuzioni. In realtà, i dati contengono valori anomali e potrebbero non essere adatti a questo modello.

Prima di eseguire k-mean, devi scegliere il numero di cluster, \(k\). Inizia con un'ipotesi di \(k\). Più avanti vedremo come perfezionare questo numero.

Algoritmo di clustering k-means

Per raggruppare i dati in \(k\) cluster, k-means segue i passaggi seguenti:

Figura 1: k-significa l'inizializzazione.

Primo passaggio

L'algoritmo sceglie un centroid in modo casuale per ogni cluster. Nel nostro esempio, scegliamo un \(k\) di 3, pertanto l'algoritmo seleziona 3 centroidi in modo casuale.

Figura 2: cluster iniziali.

Secondo passaggio

L'algoritmo assegna ogni punto al centroide più vicino per ottenere \(k\) i cluster iniziali.

Figura 3: ricalcolo dei centroidi.

Terzo passaggio

Per ogni cluster, l'algoritmo ricalcola il centroide in base alla media di tutti i punti nel cluster. Le variazioni dei centroidi sono mostrate nella Figura 3 mediante frecce. Dato che i centroidi cambiano, l'algoritmo riassegna i punti al centroide più vicino. La Figura 4 mostra i nuovi cluster dopo la riassegnazione.

Figura 4: cluster dopo la riassegnazione.

Quarto passaggio

L'algoritmo ripete il calcolo dei centroidi e l'assegnazione dei punti fino a quando i punti non smettono di cambiare cluster. Quando si raggruppano grandi set di dati, l'algoritmo viene arrestato prima di raggiungere la convergenza, utilizzando altri criteri.

Non è necessario capire la matematica alla base dei media k. Tuttavia, se ti interessa, guarda di seguito la prova matematica.

Fai clic sull'icona più per la prova matematica

Dato \(n\) gli esempi assegnati ai \(k\) cluster, riduci al minimo la somma di distanze di esempi ai loro centroidi. Dove:

• \(A_{nk} = 1\) quando l' \(n\)° esempio è assegnato al \(k\)° cluster, altrimenti 0
• \(\theta_k\) è il centroide del cluster \(k\)

Vogliamo ridurre al minimo la seguente espressione: $$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$ soggetta a: $$A_{nk} \in \{0,1\} \forall n,k$$ e $$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ Per ridurre al minimo l'espressione rispetto ai centroidi del cluster \(\theta_k\), prendi la derivata in relazione a \(\theta_k\) e equiparala a 0. $$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$ $$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$ $$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$ $$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$ $$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$ Il numeratore è la somma di tutte le distanze centro-example nel cluster. Il denominatore è il numero di esempi nel cluster. Pertanto, il cluster centroid \(\theta_k\) è la media delle distanze example-centroid nel cluster. Quindi si è rivelato efficace.

Poiché le posizioni centroidi vengono scelte inizialmente in modo casuale, i valori k possono restituire risultati significativamente diversi nelle esecuzioni successive. Per risolvere questo problema, esegui k-means più volte e scegli il risultato con le metriche di qualità migliore. (Le metriche sulla qualità verranno descritte più avanti in questo corso). Hai bisogno di una versione avanzata di k-means per scegliere posizioni centrali iniziali migliori.

Esperimento: utilizzando questo simulatore di k-mean di Stanford, prova a eseguire k-means più volte e vedi se ottieni risultati diversi.

Termini chiave:

• centroid