Il clustering è l’attività di raggruppamento di istanze in gruppi o cluster sulla base di caratteristiche comuni. Può essere eseguita attraverso tecniche di machine learning, che si configurano come tecniche di apprendimento non supervisionato (unsupervised learning techniques) di cui il clustering è espressione più comune.
Quel metodo che sembra gridare un: “Senti non ho idea di quali siano i gruppi, arrangiati” ha una sua utilità.
Estratto del post | Fuzzy Clustering
In questo post, estenderemo la breve definizione di clustering in un discorso completo che ti conferisca una visione d’insieme sul clustering.
Lascia che mi presenti.
Continua a leggere…
Mi chiamo Andrea Provino, e scrivo blogpost su temi di Data Science, Machine Learning (anche Deep Learning e Neural network) e Privacy Enhancing Technologies, un termine molto fancy per indicare quelle tecnologie che coadiuvano nella protezione della privacy, permettendoci di trattare i Big Data nel rispetto degli interessati.
Mi piace condividere con te quello che imparo.
Sono un esploratore, appassionato e curioso, che vuole renderti la vita semplice attraverso la lettura di post verticali su temi e argomenti di norma disponibili solo in lingua inglese. Così troverai qui spiegazioni in italiano accanto a termini anglofoni, per avere sempre un riferimento al panorama internazionale.
Odio lo spam quanto te.
Per questo motivo troverai sul sito un focus sul contenuto e sulla qualità, ergo per cui pubblico un post ogni 72 ore: ogni articolo richiede ricerche, e un’attenzione nella stesura che valorizzi il contenuto e unisca tre elementi per me imprescindibili:
- Ispirazione
- Informazione
- Intrattenimento
Infine, è fondamentale per me allontanarmi dall’astrazione della teoria attraverso casi d’uso concreti ed effettivi, che abbraccino il mondo business, un luogo in cui le regole sono spesso diverse da quelle dei libri.
Potrei non averti convinto o non averti convinta: sentiti allora libero e libera di tornare a fare qualsiasi altra attività.
Se tuttavia ho acceso in te il desiderio d’investire qualche minuto di ciò che so essere il tuo prezioso tempo, seguimi in questa avventura alla scoperta di cosa sia davvero il clustering.
Struttura del post
Il post è pensato tanto per te che sei uno studente, e intendi preparare un esame universitario, quanto per te che sei un professionista e desideri applicare questo sistema di apprendimento non supervisionato per massimizzare il ROI di un progetto.
Chiaramente c’è ampio spazio anche a te, appassionato intenditore.
Ecco perché insieme a definizioni formali e spiegazioni intuitive, ho ben pensato di raccogliere per te le migliori fonti operative passando così dalla teoria alla pratica.
Definiremo il concetto di clustering, e ne studieremo una tassonomia utile a descriverne le varie tipologie esistenti.
Comprenderemo quali siano gli algoritmi oggi più usati, e ci sposteremo poi nel mondo reale.
Inizieremo quindi valutando gli scenari di applicazioni di questa tecnica e i possibili impatti sul bussines.
Vaglieremo poi le attuali soluzioni disponibili per l’ambiente cloud di Amazon (AWS), di Google (GCP), di Microsoft Azure e di IBM.
Adesso ammainiamo le vele, e leviamo l’ancora: siamo pronti a salpare!
Cos’è il clustering?
Quasi sicuramente hai una comprensione pregressa del significato della parola clustering.
Rispondiamo comunque alla domanda: cos’è il clustering?
Possiamo definire il clustering come un insieme di tecniche per l‘analisi multivariata, cioè quelle parte della statistica in cui l’oggetto dell’analisi è formato da almeno due componenti, aventi l’obiettivo di selezionare e raggruppare oggetti omogenei in un dataset.
Perché è affascinante il clustering? Perché come metodo di apprendimento non supervisionato (unsupervised machine learning) è in grado di individuare la regola nascosta per identificare gruppi di persone o cosa.
Considera di essere un piccolo imprenditore o imprenditrice che intende lanciare il proprio business.
Conoscere allora la propria audience, e cosa differenzia gli insiemi di buyer personas, si rivela una tattica essenziale in una strategia di digital marketing oggi imprescindibile in ogni azienda.
Più in generale, il clustering è una tecnica di descriptive analtyics che meglio aiuta a comprendere i propri dati per compiere data driven decisions.
Lascia allora che ti mostri sulla base di quali criteri possiamo distinguere i sistemi di clustering.
Tassonomia
Le tecniche oggi impiegate possono essere distinte in base a tre dimensioni:
- Annidamento (Nesting)
- Esclusività (Exclusiveness)
- Completezza (Completeness)
Nesting
La dimensione di nesting ci consente di distinguere i metodi di cluster che ammettono sottoinsiemi a quelli che invece non considerano questa eventualità.
Così troviamo:
- Hierarchical clustering in cui possiamo trovare insiemi piccoli raggruppati in altri di dimensione superiore. Più tecnicamente, viene costruita una gerarchia di partizioni con numero crescente o decrescente di gruppi, visibili attraverso rappresentazioni ad albero.
- Partitional Clustering in cui abbiamo insiemi distinti e ben definiti, generalmente scelti in numero a priori.
Devi tenere a mente che sebbene i sistemi gerarchici ci consentano di comprendere strutture nascoste nei dati, alcune versioni come l’HAC che vedremo tra poco peccano nel considerare ogni elemento rilevante.
Nel mondo reale, quasi mai ogni elemento è rilevante.
Esclusività
Pensare che una data osservazione debba appartenere a un e un solo insieme non è scontato. Esistono infatti approcci privi di questa limitazione.
Distinguiamo allora:
- Clustering Esclusivo o Exclusive Clustering ammette evidentemente un solo elemento per cluster.
- Clustering Non-Esclusvio o Partial Clustering che consente a un elemento di appartenere a più di un cluster. Questo è utile in molti contesti reali, in cui le differenze non devono essere così marcate. Uno studente che lavora, può quindi appartenere al cluster dei lavoratori e a quello dei dipendenti.
- Fuzzy clustering in cui ogni elemento appartiene a tutti i cluster.
Prima che la tua mente esploda nella contraddizione dell’ultima tipologia di clustering, lascia che spieghi l’apparente ipocrisia.
Quel metodo che sembra gridare un: “Senti non ho idea di quali siano i gruppi, arrangiati” ha una sua utilità.
A volte, invece di un valore categorico che descriva l’appartenenza di un elemento a un cluster avremmo bisogno di un valore continuo,
Il Fuzzy Clustering ci viene in aiuto, producendo qualcosa di simile a:
- 0.25 Cluster A
- 0.65 Cluster B
- 0.10 Cluster C
Questo sistema di raggruppamento è anche noto come Clustering Probabilistico o Probabilistic Clustering.
Completezza (Completeness)
L’ultima dimensione che vediamo è quella di completezza.
È possibile che qualche osservazione sia fuori da un cluster, o raggruppamento?
In base alla risposta distinguiamo:
- Complete Clustering in cui ogni elemento appartiene ad almeno un cluster
- Partial Clustering in cui alcuni elementi potrebbero non essere raggruppati.
Ok.
Secondo me le parole spese sui differenti sistemi di clustering sono state fine troppe.
Possiamo ora rispondere alla fatidica domanda…
Come funziona il clustering? Come fare il clustering?
Caro e cara mia, eccoci.
Come funziona il clustering?
Il clustering funziona grazie all’impiego di algoritmi atti a misurare la somiglianza tra gli elementi del dataset.
Ora puoi anche andare, tanto quello che segue non ti interessa vero?
No?
Allora sappi che questo spesso si traduce nel quantificare la distanza delle osservazioni in uno spazio multidimensionale.
La distanza diventa quindi espressione della loro similarità o, in negativo, della loro dissimalirità.
Devi qui sapere un’informazione chiave.
La qualità dell’esito del processo dipende molto dalla metrica selezionata, e cioè dall’algoritmo di misura della distanza.
Come fare clustering?
Per fare clustering occorre selezionare l’algoritmo migliore in funzione del proprio scopo e del dataset a disposizione.
Il prossimo paragrafo gioca quindi un ruolo fondamentale, perché capire davvero come funzioni il clustering significa comprendere a livello matematico il funzionamento degli algoritmi impiegati.
Quali sono gli algoritmi di clustering? (What are clustering algorithms?)
Gli algoritmi di clustering comunemente usati sono 5:
- K-Means Clustering
- Mean-Shift Clustering
- DBSCAN (Density-Based Spatial Clustering of Application with Noise)
- Expectation-Maximization (EM) Clustering using Gaussian Mixture Models (GMM)
- Agglomerative Hirearchical Clustering
Esaminiamoli allora uno ad uno: ci permettono di capire come funziona e come fare clustering!
K-Means Clustering
Probabilmente uno degli algoritmi di clustering più conosciuto, sicuramente il primo insegnato nei corsi di data science, online e in sede.
Fu introdotto nel 1967 da MacQueen ed è un algoritmo di clustering partizionale
È facile da capire e facilmente implementabile da zero, tanto che ti esorto a farlo.
Come funziona il K-Mean? In sintesi, il K-mean funziona in base a 4 step:
- Prendiamo un numero k di punti in modo casuale, considerandoli come punti medi dei cluster. Sono i centroidi.
- Associamo ciascuna osservazione D del dataset al più vicino centroide, andando a creare i primi K clusters.
- Ricalcoliamo la media degli insiemi, la posizione dei centroidi nello spazio multidimensionale.
- Ripetiamo gli step dal 2 al 3 finché la posizione dei centroidi continua a cambiare.
Per capire a fondo come funzioni il K-Mean ti esorto a leggere questo post sul k-means clustering.
Come si stabilisce il numero di cluster a priori?
Long story short… a caso.
I più professionali direbbero, dopo alcuni esperimenti il numero migliore di cluster per il set di dati in esame è…
La verità ultima è che molto dipende dal contesto in cui l’algoritmo di raggruppamento viene eseguito, cioè il suo scopo.
Qui allora introduciamo un concetto chiave, che poi distingue lo studente dal professionista.
Quello del domain knowledge, ossia la conoscenza del dominio, inteso come mercato di riferimento o attività aziendale, che unita a una comprensione profonda del set di dati, emersa nella fase di esplorazione iniziale, consente di definire il corretto numero di insiemi che è lecito aspettarsi.
L’ultima cosa che devi sapere, prima di passare all’algoritmo successivo, riguarda le sue limitazioni.
Sebbene il K-mean clustering converga velocemente, è necessario stabilire a priori il numero di insiemi.
Inoltre non è garantito il raggiungimento del minimo globale, cosa molto importante perché segnica che potremmo ottenere una soluzione sub ottimale.
La soluzione a queste insidie si chiama DBSCAN
DBSCAN
Il DBSCAN non è schizzinoso, ma pretenzioso.
Prima abbiamo detto che il k-mean definisce una serie di punti casuali per poi raggruppare sulla base della vicinanza tanti punti vicini.
DBSCAN invece di chiederci quanti clusters intendiamo ottenere ci pone due domande:
- cosa significa che un elemento sia vicino al centro di un cluster?
- cosa intendiamo per tanti elementi vicini al centro del cluster?
Ecco perché in questo algoritmo abbiamo due parametri che indichiamo come:
- Raggio o neighboring radius (Closeness)
- Elementi minimi o minimum neighbor (ovvero quanti dati elementi siano adiacenti al quel elemento)
Expectation–Maximization (EM) Clustering using Gaussian Mixture Models (GMM)
Un’altra limitazione del K-Mean è l’uso della sola media per il calcolo del centroide.
Alcune distribuzioni complesse richiedono tuttavia sistemi più sofisticati per il calcolo dei nuovi centri di cluster.
Il Gaussian Mixture Models (GMMs) hanno quindi una flessibilità superiore al K-Mean consentendoci di elaborare correttamente anche le distribuzioni più insidiose.
In questo metodo assumiamo che la distribuzione delle osservazioni sia Gaussiana, un’assunzione certamente meno restrittiva rispetto a considerarli circolari e impiegare la media.
In questo modo i parametri che descrivono la forma dei cluster sono due:
- media
- deviazione standard
La forma che i cluster possono assumere si estende ora a qualsiasi ellisse.
Per calcolare i parametri usiamo un algoritmo definito Expectation-Maximization (EM).
Mean-shift Clustering
Il Mean-shift è un algoritmo di raggruppamento basato sul concetto delle finestre a scorrimento di lettura (sliding-window-based algorithm).
L’obiettivo è qui quello di determinare le regioni con più densa concentrazione di punti.
Come il k-mean si basa sul concetto di centroidi, che vengono però calcolati con un approccio di Hill Climbing.
Ti ho spiegato nel dettaglio come funziona l’algoritmo di Mean-Shift nel relativo articolo che ti invito a leggere e che trovi linkato.
Agglomerative Hierarchical Clustering
Questo metodo di aggregazione può essere di tipo bottom-up (agglomerative) o top-down (divisive).
L’approccio bottom-up inizializza ciascuna osservazione come un insieme indipendente o cluster.
Combina poi i cluster vicini, iterando il processo finché alcune condizioni si verificano:
- raggiunto il numero prefissato di cluster
- superato il valore di distanza minima tra i cluster
- ottenuto un criterio statistico prefissato.
L’approccio top-down muove dal principio opposto: inizialmente tutte le osservazioni appartengono a un solo insieme o cluster, salvo poi essere divise in insiemi di dimensioni inferiori.
A determinare la fine del processo è qui una metrica che misura in genere l’omogeneità dei gruppi, anche se può spesso dipendere dal raggiungimento del numero prefissato di insiemi.
Tornando al primo, il metodo bottom-up combina o agglomera clusters.
Così un metodo che combina approccio bottom-up e Hierachical Clustering come sistema di annidamento ha un nome particolare: è l’agglomerative hierachical clustering.
L’HAC rappresenta la gerarchica dei clusters attraverso schemi ad albero denominati dendrogrammi. Le radici dell’albero sono i cluster unici con più samples, mentre le foglie quelli con un solo sample.
Come scegliere l’algoritmo di clustering?
Bella domanda.
Gli inglesi hanno un termine per definire la soluzione ideale a un problema specifico.
Chiamano questa soluzione silver bullet.
Purtroppo, non esiste alcun algoritmo che possa essere considerato un silver bullet, motivo per cui è importante considerare pregi e difetti di ognuno.
Queste considerazioni, se unite all’imprescindibile domain knowledge e a una buona conoscenza del proprio dataset, ci permettono di testare gli algoritmi migliori (i.e. Risparmiare tempo) e selezionare quello ottimale in base al nostro scopo.
Contrariamente ai sistemi supervisionati, in cui l’obiettivo da raggiungere è chiaro, non esiste una winning condition per i problemi di clustering.
Vorrei davvero non configurare questo paragrafo come uno scarico di responsabilità, ma se il clustering fosse semplice tutti lo farebbero!
Lascia comunque che condivida con te alcune veloci considerazioni.
In linea generale il K-Means tende a lavorare meglio su dataset grandi, ed è computazionalmente efficiente.
L’HAC richiede un numero elevato di calcoli e produce risultati ottimali su dataset contenuti; in più aiuta a visualizzare le gerarchie, utile se la natura del dataset è gerarchica.
In definitiva possiamo affermare che il clustering sia un mondo affascinante e strano, con un’ancora più strana collezione di tecniche, ma che se usato con saggezza sia in grado di estrarre sorprendenti insights sui nostri dati.
Come valutare l’efficacia del clustering (clustering evaluation)
Possiamo ricorrere agli indici di validità per valutare l’efficacia di una soluzione di clustering, sebbene ti ricordo ogni metrica debba in questo contesto essere interpretata in funzione del dataset e dello scopo del progetto.
Infatti, contrariamente ai metodi di classificazione standard per cui abbiamo metriche facilmente interpretabili che comparino il risultato predetto con quello effettivo (e.g. Accuracy, Precision, Recall, Confusion Matrix etc) non possiamo dire lo stesso per il clustering.
Qui non c’è alcuna classe effettiva con cui comparare risultati.
Come valutare i risultati del clustering?
Per valutare i risultati del clustering (clustering results evaluation) possiamo ricorrere agli indici di validità (validity indices), che possono essere di due tipi:
- Indici di validità interni, che considerano i valori all’interno dei singoli cluster (e.g. Sum of Squared Error, SSE):
- valutare come il clustering modelli i dati
- verificare che il numero di cluster sia corretto (i.e. applicando il domain knowledge)
- identificare la presenza di strutture non casuali
- Indici di validità esterni, che considerano informazioni esterne come la classe o label (e.g. Entropia):
- comparando le caratteristiche di due insiemi di cluster e valutare quale sia il migliore
- comparando le caratteristiche di due algoritmi per lo stesso fine
Approfondiremo gli indici di validità in un prossimo post.
Comunemente i risultati del clustering sono interpretati in forma grafica, e il ricorso agli indici di validità è una tattica aggiuntiva per avere una comprensione più profonda dei risultati ottenuti.
Benone! Un’altra domanda (l’ennesima).
Per cosa può essere usato il clustering?
Clustering use cases | Casi d’uso concreti
Abbiamo speso molte parole per descrivere i sistemi di clustering e abbiamo usato un elevato grado di astrazione.
La nostra pragmatica mente desidera però qualcosa di più tangibile.
Ecco gli esempi di applicazione del clustering!
Il clustering può essere usato ad esempio per o nei:
- Sistemi di raccomandazione per raggruppare tra loro utenti con criteri di ricerca e behaviorual pattern simili. A questo punto è facile condividere contenuti attinenti e dunque apprezzati. Ad esempio, Netflix consiglia serie televisive che potresti apprezzare, e Amazon prodotti che acquisteresti.
- Rilevamento anomalie, per identificare possibili frodi (fraud detection) o parti meccaniche difettose nell’ambito della predictive maintenance (manutenzione predittiva)
- Ricerca medica, raggruppando DNA pattern per analizzare evoluzioni e combattere malattie genetiche
- Segmentazione clienti, uno dei casi forse più comuni. Per massimizzare il ritorno di investimento nelle strategie di marketing, il ricorso alla customer segmentation attraverso algoritmi di clustering è una tattica dai risultati dirompenti.
A questi esempi generalisti, ne aggiungiamo altri di natura specifica.
Pensiamo ad esempio alla classificazione di documenti sull base del contenuto, degli argomenti e le categorie. I documenti sono qui inizialmente trasformati in vettori e il K-Means consente di effettuare il clustering dei vettori.
Sappi che questo caso d’uso è uno dei problemi reali più comuni in cui applicare tecniche di clustering.
Altri esempi includono:
- Identificazione delle Fake News
- Creazione filtri spam
- Identificazione traffico sito web (andando a bloccare traffico anomalo evitando rallentamenti e cattive esperienze per gli utenti)
Diciamo che la chiave corretta per identificare implementazioni presenti e future del clustering è quello di pensare a delle possibili classificazioni in cui però non abbiamo la classe discriminante.
Passiamo all’angolo biblioteca.
Quali sono i migliori libri sul clustering?
Un libro sul clustering che può essere considerato è questo.
Non l’ho letto, solo perché ancora in fase di stesura al momento, ma Manning è spesso garanzia su libri così tecnici.
Un altro testo sempre di Manning è questo. Alcune sezioni sono leggibili in chiaro, mentre per altre è necessario pagare.
For Professionals
In altri termini, dalla teoria alla pratica.
Un set di API che potresti trovare utile si chiama Carrot2 e consente la creazione di un motore di clustering per risultati di ricerca.
Potrai così organizzare la ricerca in modo automatico in argomenti senza alcuna conoscenza pregressa di tassonomie e criteri di classificazione.
Ha un supporto multilingua con 19 idiomi supportati, tra cui l’italiano.
Vediamo, seppur rapidamente cosa offra l’ambiente cloud.
AWS
In AWS l’ambiente di ML per eccellenza è Amazon SageMaker, il servizio di machine learning completamente gestito.
Tra gli algoritmi supportati troviamo il K-Means, e a questo link trovi una descrizione sul funzionamento by Amazon.
In realtà la versione qui usata è una variante ottimizzata, dalle prestazioni a loro detta migliori.
I dati devono essere in forma tabulare, con ogni riga che rappresenta l’elemento da raggruppare e chiaramente le colonne sono le features.
A questo notebook su GitHub trovi un esempio dell’impiego del Cloud AWS per la segmentazione della popolazione statunitense.
GCP
Il Cloud di Google punta tutto sulla sua ammiraglia in termini di Big Data: Google BigQuery.
Anche qui, affidandoci ai metodi completamente gestiti abbiamo poco margine: k-means.
Nella documentazione ufficiale è spiegato come procedere per l’implementazione, sebbene i testi di riferimento di Google siano sovente lacunosi e poco esplicativi.
Microsoft Azure
Microsoft ha sviluppatro un ecosistema cloud particolarmente attraente a Data Scientis e Machine Learning Engineers.
La documentazione è disponibile in italiano ma chiaramente tradotta in modo automatico con evidenti lacune logiche.
È comunque presente un modulo di riferimento a questo link.
IBM
IBM ci propone il solito algoritmo k-means con un’interessante applicazione per il clustering del customer churn, l’abbandono del cliente.
La documentazione è reperibile qui.
Per concludere, ho pensato di raccogliere per te le domande più frequenti sul clustering in comode schede per un agile ripasso.
Domande comuni clustering (FAQ)
Per il momento è tutto.
Per aspera, ad astra.
Un caldo abbraccio, Andrea
