Il k-means clustering è tra i più semplici e popolari algoritmi di unsupervised machine learning, utile per la segmentazione del dataset.
L’obiettivo è chiaro: raggruppare data points simili, scoprendo pattern nascosti, dividendo il dataset in un numero k di clusters.
Un cluster è quindi un insieme di osservazioni che condividono caratteristiche simili.
Abbiamo scritto una articolo su tutto quello che devi sapere sul clustering, in cui partendo dalla definizione approfondiamo tassonomie, casi d’uso e applicazioni concrete nel business.
Hai la libertà di perdertelo, spero solo che sia la scelta giusta per te e che non rappresenti un rimorso…
Sappi che è sempre lì, per te.
Advantages
Ieri abbiamo esaminato i Recommender System, comprendendo dapprima il vantaggio che siano in grado di conferire a un business.
Oggi riprendiamo il frame, per capire fin da subito perché il k-means clustering possa essere utile.
Un algoritmo di clusterizzazione come il DBSCAN, è in grado di segmentare un dataset in gruppi dalle caratteristiche comuni.
Siamo così in grado di segmentare i dati storici di un cliente, determinando gruppi di acquirenti tipo basandoci sui pattern di acquisto, o le preferenze per specifiche categorie di prodotti.
Il k-means clustering è un algoritmo di unsupervsied learning, con tutti i vantaggi e svantaggi che ne derivano.
Types
Esistono principalmente tre tipologie di clustering algorithms:
- Partitioning algorithms
- Hierarchical algorithms
- Density Based algorithms
Il k-means è un partiotioning algorithm, mentre il DBSCAN è un density based algorithm.
Questo significa che il k-means divide il dataset in numero k di clusters non sovrapposti e indipendenti, privi di strutture interne o labels, tali per cui le osservazioni di un cluster siano simili tra loro e dissimili da quelle presenti nei restanti insiemi.
Ottimo, ma come funziona?
La similarità tra i samples è usata per dare forma ai cluster, facendo in modo che osservazioni simili finiscano nello stesso insieme.
Convenzionalmente però, l’approccio scelto è opposto: si cerca di separare samples dissimili.
Il k-means tenta quindi di massimizzare la distanza inter-cluster tra i samples e minimizzare quella intra-cluster.
Come calcoliamo però la dissimilarità tra due osservazioni, nel concreto tra due acquirenti di un possibile e-commerce?
Matematica alla mano, usiamo delle formule per il calcolo della distanza come:
- Cosine similarity
- Euclidean Distance
- Average Distance
- Minkowski Distance
Per scegliere quale misura sia più corretta, è fondamentale prendere in esame parametri quali il domain knowledge del dataset, e la tipologia di attributi che lo compongono. (Gli attributi sono i data type, mentre le features sono l’accoppiata attributo-valore)
How k-means clustering works
Il funzionamento operativo dell’algoritmo si basa sul concetto di centroide, centro di ogni cluster, e richiede che venga specificato a priori il numero k di clusters.
Ora, due domande:
- Come inizializziamo i centrodi?
- Come scegliamo il corretto numero k?
Esistono due approcci all’inizializzazione dei centoridi. Il primo prevede la scelta casuale di un numero pari a k di samples, usati come partenza. Il secondo individua sempre un numero pari a k di punti, questa volta scelti però in modo completamente casuale, e non appartenenti al dataset.
A ogni iterazione, usando una delle metriche di cui sopra, è calcolata la distanza di ciascun sample dai centroidi.
In questo processo definiamo errore la distanza totale, intesa come sommatoria, di ciascun sample dal centroide.
Intuitivamente è fondamentale minimizzare l’errore.
Prima dell’iterazione successiva, ogni centroide è spostato nel punto medio delle distanze calcolate. Il ciclo ricomincia e continua fintantoché la posizione dei centroidi non si stabilizzi, cioè rimanga la medesima da un’iterazione alla successiva.
Trattandosi di una algoritmo euristico, la convergenza non è garantita.
Questo significa che nel minimizzare l’errore potremmo rimanere bloccati in un minimo locale, anziché raggiungere quello globale.
Le prestazioni dell’algoritmo sono influenzate dalla scelta iniziale dei centroidi.
È consuetudine testare diverse varianti dell’algoritmo, con condizioni di partenza ovviamente differenti. L’algoritmo è veloce, quindi non ci sono grosse problematiche.
Ricordati di ripassare cos’è il clustering in questo post di approfondimento!
Per il momento è tutto.
Per aspera, ad astra.
Un caldo abbraccio, Andrea
