Introduzione a K-Means

Lezione 9 di 19 del corso Introduzione all’apprendimento automatico di Coddy.

K-means è uno degli algoritmi di clustering più semplici e più utilizzati. Ha l’obiettivo di suddividere n osservazioni in k cluster, in cui ogni osservazione appartiene al cluster con la media (centroide) più vicina, che funge da prototipo del cluster. Supponiamo che tu abbia diversi tipi di frutta e voglia dividerli in cesti in base al tipo, ma che non conosca le etichette. K-means ti aiuta a fare proprio questo, ma usando punti dati invece della frutta!

Incheol, CC BY-SA 4.0, tramite Wikimedia Commons

Come funziona K-means?

L’algoritmo segue una procedura iterativa semplice ed efficiente per suddividere un insieme di dati in k cluster.

Inizializzare i centroidi: per prima cosa, scegli k punti dell’insieme di dati come centroidi iniziali. Questi punti possono essere selezionati casualmente o in base a una strategia specifica.
Assegnare i cluster: per ogni punto dell’insieme di dati, trova il centroide più vicino (usando misure di distanza come la distanza euclidea) e assegna il punto a quel cluster.
Aggiornare i centroidi: una volta assegnati tutti i punti ai cluster, ricalcola i centroidi facendo la media di tutti i punti di ciascun cluster.
Ripetere i passaggi 2 e 3: i passaggi precedenti vengono ripetuti finché i centroidi non smettono di cambiare in modo significativo. Ciò significa che l’algoritmo è convergente e i cluster sono stabili.

Mettiti alla prova

Questa lezione include un breve quiz. Inizia la lezione per rispondere e tenere traccia dei tuoi progressi.

Mettiti alla prova

Questa lezione include un breve quiz. Inizia la lezione per rispondere e tenere traccia dei tuoi progressi.

Mettiti alla prova

Questa lezione include un breve quiz. Inizia la lezione per rispondere e tenere traccia dei tuoi progressi.

Sfida

Facile

Determinare il numero ottimale di cluster, k, è un passaggio cruciale. Esistono vari metodi per farlo; il metodo del gomito è uno dei più diffusi.

Questa tecnica consiste nell'eseguire iterativamente K-means per k=1 fino a k=n. Per ogni valore di k, calcoliamo il valore della somma dei quadrati all'interno dei cluster (WCSS).

Ogni cluster ha un centroide; la WCSS è la somma dei quadrati di tutte le distanze dal centroide.

Crea una funzione chiamata wcss che riceva un elenco di punti dati (dello stesso cluster) e restituisca la WCSS del cluster. Segui questi passaggi:

Trova il centroide: un centroide è un punto che rappresenta la posizione media di tutti i punti di un cluster:

Ad esempio, ecco un elenco di due punti 3D: (1, 2 ,3), (4, 5, 6). Il centroide è:
```
(1 + 4) / 2 = 2.5,
(2 + 5) / 2 = 3.5,
(3 + 6) / 2 = 4.5,
>> (2.5, 3.5, 4.5)
```
Calcola la distanza euclidea tra ciascun punto e il centroide
Restituisci la somma di tutte le distanze divisa per il numero di punti

Provalo tu

def euclidian_distance(point_a, point_b):
    return (sum([(point_a[i] - point_b[i])**2 for i in range(len(point_a))]))**0.5

def wcss(points):
    # Scrivi il codice qui