k-means Clustering

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