Cos'è il clustering?

Esistono diversi modi per utilizzare il clustering nel machine learning, dalle esplorazioni iniziali di un set di dati al monitoraggio dei processi in corso.

Puoi utilizzarlo nell’analisi esplorativa dei dati con un nuovo set di dati per conoscere le tendenze, i modelli e gli outlier sottostanti. In alternativa, puoi disporre di un set di dati più grande che deve essere suddiviso in più set di dati, oppure ridotto utilizzando la riduzione della dimensionalità.

In questi casi, il clustering può essere un passaggio della pre-elaborazione.

Esempi di cluster possono includere generi musicali, gruppi di utenti differenti, segmenti chiave di una segmentazione di mercato, tipi di traffico di rete su un cluster di server, gruppi di amici su un social network o molti altri tipi di categorie.

Il processo di clustering può utilizzare solo una funzione dei dati oppure tutte le funzioni presenti nei dati.

È utile pensare al clustering come al tentativo di trovare raggruppamenti naturali nei dati per vedere quali categorie potrebbero esistere e cosa definisce tali categorie. I cluster possono aiutarti a trovare le relazioni sottostanti tra i punti dati per vedere quali funzioni o caratteristiche sono condivise tra le categorie.

A seconda dell’algoritmo di clustering utilizzato, potrebbe essere possibile rimuovere gli outlier dai dati oppure etichettarli come outlier. Il clustering può inoltre essere utile per il rilevamento delle anomalie individuando i punti dati che non sono contenuti all’interno di un cluster o che sono associati solo in modo debole ad uno e pertanto possono rappresentare un’anomalia nel processo di generazione dei dati.

È inoltre possibile utilizzare il clustering per ridurre la complessità dei set di dati di grandi dimensioni riducendo il numero di dimensioni dei dati. Se noti che le categorie sono definite solo da due o tre funzioni, puoi rimuovere le funzioni estranee oppure utilizzare tecniche di riduzione della dimensionalità come la PCA.

Il clustering è inoltre molto utile nella creazione di visualizzazioni dei set di dati per vedere le proprietà emergenti dei dati, nonché la densità e le relazioni tra i cluster.

Talvolta gli algoritmi di clustering vengono distinti in algoritmi di hard clustering, in cui ogni punto dati appartiene a un solo cluster e ha un valore binario che indica se è o non è incluso in uno, oppure soft, in cui a ogni punto dati viene assegnata una probabilità di appartenere a ciascun cluster individuato.

Non esiste un processo di clustering migliore, sei tu che dovrai scegliere l’approccio più adatto alle tue esigenze e ai dati con cui stai lavorando.

Esistono diversi algoritmi di clustering, così come esistono diversi modi per definire un cluster. I diversi approcci funzionano bene per diversi tipi di modelli a seconda della dimensione dei dati di input, della dimensionalità dei dati, della rigidità delle categorie e del numero di cluster all’interno del set di dati.

Vale la pena notare che un algoritmo può funzionare molto bene per un set di dati e molto male per un altro. In questa sezione vengono illustrati cinque degli approcci al clustering utilizzati più frequentemente.

Esistono altre tecniche come il clustering spettrale o il clustering Mean-Shift che non vengono però illustrati in questo articolo.

Il clustering basato su centroidi è un tipo di metodo di clustering che partiziona o suddivide un set di dati in gruppi simili in base alla distanza tra i loro centroidi. Il centroide di ogni cluster, o centro, è la media o la mediana di tutti i punti del cluster a seconda dei dati.

Una delle tecniche di clustering basate sui centroidi utilizzate più frequentemente è l’algoritmo di clustering k-means. K-means presuppone che il centro di ciascun cluster definisca il cluster stesso utilizzando una misura della distanza, solitamente la distanza euclidea, dal centroide.

Per inizializzare il clustering, fornisci un numero di cluster previsto che rappresenta la “K” in k-means e l’algoritmo tenta di trovare cluster ragionevoli nei dati che corrispondano a quel numero. I cluster k ottimali in un determinato set di dati vengono identificati minimizzando in modo iterativo la distanza totale tra ciascun punto e il centroide del cluster assegnato.

K-means è un approccio di tipo hard clustering, il che significa che ogni punto dati è assegnato a un cluster separato e non è associata nessuna probabilità di appartenere al cluster.

K-means funziona bene quando i cluster sono di dimensioni approssimativamente equivalenti e non ci sono outlier significativi o cambiamenti di densità tra i dati. K-means spesso non risulta efficiente quando i dati sono ad alta dimensionalità o quando i cluster hanno dimensioni o densità significativamente diverse.

K-means è inoltre particolarmente sensibile ai valori anomali in quanto tenta di stabilire centroidi in base ai valori medi di tutti i valori nel cluster ed è quindi suscettibile di overfitting per includere tali outlier.

Un altro approccio basato su centroidi ai K-means è il K-medoids. I medoidi sono oggetti rappresentativi di un set di dati o di un cluster all’interno di un set di dati la cui somma delle distanze rispetto ad altri oggetti nel cluster è minima. Invece di avere un centroide arbitrario come centro del grafo, l’algoritmo crea cluster utilizzando singoli punti dati come medoidi o centro del cluster.

Poiché l’algoritmo K-medoids utilizza punti di dati estanti anziché centroidi arbitrari, è meno sensibile agli outlier.

Il clustering gerarchico, talvolta chiamato clustering basato sulla connettività, raggruppa i punti dati in base alla prossimità e alla connettività dei loro attributi. Questo metodo determina i cluster in base alla vicinanza dei punti dati in tutte le dimensioni. L’idea è che gli oggetti che sono più vicini sono più strettamente correlati di quelli che sono lontani tra loro.

A differenza di k-means, non è necessario specificare in anticipo il numero di cluster. L’algoritmo di clustering crea invece una rete grafica dei cluster a ogni livello gerarchico. Questa rete è gerarchica, il che significa che ogni nodo ha un solo nodo padre ma può avere più nodi figlio.

I cluster gerarchici possono essere rappresentati graficamente con un dendrogramma per aiutare a riassumere e organizzare visivamente i cluster scoperti e la gerarchia che possono contenere.

Esistono due approcci per eseguire l’analisi gerarchica dei cluster:

• Agglomerativo: nel clustering agglomerativo, un approccio bottom-up parte dai singoli punti dati e unisce successivamente i cluster calcolando la matrice di prossimità di tutti i cluster al livello attuale della gerarchia, al fine di creare una struttura ad albero. Una volta creato un livello di cluster in cui tutti i cluster hanno una somiglianza inter-cluster nulla o bassa, l’algoritmo passa al set dei cluster appena creati e ripete il processo fino a quando non trova un nodo radice in cima al grafico gerarchico.
  
  Esistono diverse scelte possibili in termini di come questi cluster debbano essere uniti tra loro, con compromessi in termini di qualità ed efficienza del clustering.
  
  Nel clustering single-linkage, la distanza più breve tra qualsiasi coppia di punti dati in due cluster viene utilizzata come misura di somiglianza.
  
  Nel linkage a coppie, si utilizza la media di tutte le coppie di punti dati, mentre nel linkage a campione, si utilizza un campionamento dei punti dati nei due cluster per calcolare la distanza media.
  
  Nel centroid-linkage, si utilizza la distanza tra i centroidi.
  
  Un problema dei metodi agglomerativi è che possono presentare un concatenamento, in cui i cluster più grandi sono naturalmente predisposti ad avere distanze più vicine rispetto ad altri punti e quindi continuano a diventare sempre più grandi e ad attirare più punti dati nel loro cluster. Un altro svantaggio è che i metodi agglomerativi possono essere molto più lenti dei metodi di divisione per costruire la gerarchia.
  
  
• Divisivo: nei metodi di clustering gerarchico di tipo divisivo, un approccio top-down suddivide successivamente i punti dati in una struttura ad albero.
  
  Il primo passo consiste nel suddividere il set di dati in cluster, utilizzando un metodo di clustering piatto come K-Means. I cluster con la somma degli errori quadratici (SSE) più elevata vengono poi ulteriormente suddivisi utilizzando un metodo di clustering piatto.
  
  L’algoritmo si interrompe quando raggiunge singoli nodi o un SSE minimo. Il partizionamento divisivo consente una maggiore flessibilità sia in termini di struttura gerarchica dell’albero, sia di livello di equilibrio nei diversi cluster.
  
  Non è necessario avere un albero perfettamente equilibrato in termini di profondità dei diversi nodi o un albero in cui il grado di ogni ramo è esattamente due. Questo consente la costruzione di una struttura ad albero che permette diversi compromessi nell’equilibrio delle profondità dei nodi e dei pesi dei nodi (numero di punti dati nel nodo).
  
  Il clustering gerarchico divisivo può essere più rapido rispetto al clustering gerarchico agglomerativo, specialmente quando i dati non richiedono la costruzione dell’albero fino ai singoli punti dati.

Il clustering basato sulla distribuzione, a volte chiamato clustering probabilistico, raggruppa i punti dati in base alla loro distribuzione di probabilità. Questo approccio presuppone che vi sia un processo che genera distribuzioni normali per ogni dimensione dei dati, che creano i centri dei cluster.

Si differenzia dal clustering basato sui centroidi perché non utilizza una metrica di distanza come la distanza euclidea o Manhattan. Gli approcci basati sulla distribuzione cercano invece una distribuzione ben definita che viene visualizzata in ogni dimensione. Le medie dei cluster sono le medie della distribuzione gaussiana in ogni dimensione.

Il clustering basato sulla distribuzione è un approccio al clustering basato sul modello, perché richiede l’adattamento di una distribuzione più volte su ogni dimensione per trovare i cluster, il che significa che può essere computazionalmente costoso quando si lavora con grandi insiemi di dati.

Un approccio comunemente utilizzato per il clustering basato sulla distribuzione consiste nel creare un modello di miscela gaussiana (GMM) attraverso la massimizzazione delle aspettative. Il nome GMM deriva dall’ipotesi che ogni cluster sia definito da una distribuzione gaussiana, spesso chiamata distribuzione normale.

Considera un set di dati con due cluster distinti, A e B, definiti entrambi da due distribuzioni normali diverse: uno lungo l’asse x e uno lungo l’asse y. L’aspettativa-massimizzazione inizia con un’ipotesi casuale su quali siano queste due distribuzioni lungo ciascun asse e poi procede a migliorare iterativamente alternando due passaggi:

• Aspettativa: assegna ciascun punto dati a ognuno dei cluster e calcola la probabilità che provenga dal cluster A e dal cluster B.
  
  
• Massimizzazione: aggiorna i parametri che definiscono ogni cluster, una posizione media ponderata e una matrice di varianza-covarianza, in base alla probabilità che ogni punto dati si trovi nel cluster. Si ripete quindi il passaggio di aspettativa fino a quando l’equazione non converge sulle distribuzioni osservate per ogni cluster.

A ogni punto dati viene data una probabilità di essere associato a un cluster. Questo significa che il clustering tramite aspettativa-massimizzazione è un approccio soft clustering e che un determinato punto può essere associato probabilisticamente a più di un cluster. Ha senso in alcuni scenari, un brano può essere un po’ folk e un po’ rock o un utente può preferire i programmi televisivi in spagnolo ma a volte anche guardare i programmi in inglese.

Il clustering basato sulla densità funziona rilevando le aree in cui i punti sono concentrati e dove sono separati da aree vuote o sparse. A differenza degli approcci basati sui centroidi, come K-means, o degli approcci basati sulla distribuzione, come aspettativa-massimizzazione, il clustering basato sulla densità può rilevare cluster di forma arbitraria. Questo può essere estremamente utile quando i cluster non sono definiti intorno a una posizione o distribuzione specifica.

A differenza di altri algoritmi di clustering, come K-means e il clustering gerarchico, un algoritmo basato sulla densità può rilevare cluster di qualsiasi forma, dimensione o densità nei dati. Il clustering basato sulla densità può inoltre distinguere tra punti di dati che fanno parte di un cluster e quelli che devono essere etichettati come rumore. È particolarmente utile quando si lavora con set di dati con rumore oppure outlier o quando non si dispone di conoscenze preliminari sul numero di cluster nei dati.

DBSCAN è un esempio di algoritmo di clustering che adotta un approccio basato sulla densità al clustering. Utilizza un approccio di clustering spaziale basato sulla densità per creare cluster con una densità trasmessa dall’utente che si concentra attorno a un centroide spaziale. L’area immediatamente intorno al centroide viene definita quartiere e DBSCAN tenta di definire quartieri di cluster con la densità specificata.

Per ogni cluster, DBSCAN definirà tre tipi di punti dati:

• Punti centrali: un punto dati è un punto centrale se il neighborhood intorno a quel punto dati contiene almeno tanti punti quanti sono i punti minimi specificati dall’utente.
  
  
• Punti di confine: un punto dati è un punto di confine se il neighborhood intorno a quel punto dati contiene meno del numero minimo di punti dati, mentre il neighborhood intorno a quel punto contiene un punto centrale.
  
  
• Outlier: un punto dati è un outlier se non è né un punto centrale né un punto di confine. In sostanza, questa è la classe “other”.

HDBSCAN è una variante di DBSCAN che non richiede l’impostazione di alcun parametro; questo può renderlo ancora più flessibile dell’originale. È meno sensibile al rumore e agli outlier nei dati.

Inoltre, DBSCAN a volte può avere problemi nell’individuazione di cluster con densità non uniforme. Questa è stata una delle motivazioni principali per HDBSCAN, che quindi gestisce cluster di densità variabile in modo molto più efficace.

Gli algoritmi di clustering basati su griglia non vengono utilizzati con la stessa frequenza dei quattro approcci descritti in precedenza, ma possono essere utili nel clustering ad alta dimensionalità in cui altri algoritmi di clustering potrebbero non essere altrettanto performanti.

In questo approccio, l’algoritmo suddivide un set di dati ad alta dimensione in celle. A ogni cella viene assegnato un identificatore univoco denominato ID cella e tutti i punti dati che rientrano in una cella sono considerati parte dello stesso cluster.

Il clustering basato su griglia è un algoritmo efficiente per l’analisi di set di dati multidimensionali di grandi dimensioni in quanto riduce il tempo necessario per la ricerca dei quartieri più prossimi, il che è un passaggio comune in numerosi metodi di clustering.

Un popolare algoritmo di clustering basato su griglia prende il nome di STING, che sta per Statistical Information Grid. In STING, l’area spaziale viene suddivisa in celle rettangolari e diversi livelli di celle a diversi livelli di risoluzione. Le celle di alto livello vengono suddivise in diverse celle di basso livello.

STING può essere molto efficiente nel calcolo di cluster in scenari di big data in cui i set di dati sono estremamente grandi perché semplicemente partiziona il set di dati in modo iterativo in griglie più fini e valuta il numero di punti all’interno di tale griglia. Uno svantaggio di STING è che i confini dei cluster devono essere definiti orizzontalmente o verticalmente, l’algoritmo non è in grado di rilevare confini di cluster non rettangolari.

Un altro algoritmo basato su griglia particolarmente potente con dati ad alta dimensione è l’algoritmo Clustering In Quest o CLIQUE. L’algoritmo CLIQUE combina un approccio al clustering basato su griglia e uno basato sulla densità.

In questo algoritmo, lo spazio dati viene suddiviso in una griglia e la densità relativa dei punti all’interno delle celle della griglia viene confrontata e i sottospazi che hanno densità simili vengono uniti. Questo approccio trova unità dense in tutti i sottospazi di interesse e quindi misura se cluster simili devono essere collegati tra loro. Ciò significa che l’algoritmo CLIQUE è in grado di rilevare cluster di forme arbitrarie in dati ad alta dimensione.

Esistono diverse metriche di valutazione per l’analisi del cluster e la selezione della metrica appropriata dipende dal tipo di algoritmo di clustering e dal set di dati corrispondente.

Le metriche di valutazione possono essere generalmente suddivise in due categorie principali: estrinsiche e intrinseche.

Le misure intrinseche sono metriche di valutazione per l’analisi di cluster che utilizzano solo le informazioni all’interno del set di dati. Queste possono essere utili quando si lavora con dati non etichettati.

La qualità dell’analisi si basa interamente sulle relazioni tra i punti dati. Possono essere utilizzati quando non abbiamo conoscenze o etichette precedenti dei dati.

Le misure intrinseche comuni includono:

• Punteggio di silhouette: questa metrica misura la somiglianza e la differenza di ogni punto dati rispetto al proprio cluster e a tutti gli altri cluster. I valori delle metriche variano da -1 a +1. Un valore elevato indica che l’oggetto è ben abbinato al proprio cluster e poco abbinato ai cluster vicini.
  
  
• Indice di Davies-Bouldin: questa metrica calcola il rapporto tra la distanza all’interno del cluster e la distanza tra i cluster. Più basso è il punteggio dell’indice, migliori saranno le prestazioni del clustering.
  
  
• Indice di Calinski-Harabasz: noto anche come criterio del rapporto di varianza, misura il rapporto tra la varianza tra i cluster e la varianza all’interno dei cluster. Più alto è il rapporto Calinski-Harabasz, più un cluster è ben definito.

Queste metriche di valutazione possono aiutarci a confrontare le prestazioni di diversi algoritmi e modelli di clustering, a ottimizzare i parametri di clustering e a convalidare l’accuratezza e la qualità dei risultati del clustering.

Le misure estrinseche utilizzano la verità di base o le informazioni esterne per valutare la validità delle prestazioni dell’algoritmo di clustering. Questo richiede una qualche forma di etichettatura di dati che confermi la classe o il cluster a cui appartiene ogni punto dati.

In questo caso, puoi confrontare l’accuratezza dell’analisi di clustering con le metriche spesso utilizzate per l’accuratezza della classificazione.

Le misure estrinseche comuni includono:

• Punteggio F (chiamato anche misura F): questa metrica determina l’accuratezza dell’algoritmo di clustering esaminando la precisione e il richiamo quando si confronta un clustering proposto con una verità di base. Nel caso di un punteggio F, più alto è, e meglio è.
  
  
• Purezza: questa metrica misura la frazione di punti dati assegnati correttamente alla stessa classe o cluster a cui appartengono. Nel caso di una misura di purezza, più alto è, meglio è.
  
  
• Indice di Rand: si tratta di una misura della somiglianza tra le etichette vere e quelle previste dell’algoritmo di clustering, compresa tra 0 e 1. Un valore più alto indica una migliore prestazione di clustering.
  
  
• Variazione delle informazioni (nota anche come distanza informativa condivisa): misura la quantità di informazioni persa e acquisita tra due cluster. Questo valore può essere tra un clustering di verità di base e un clustering generato da un algoritmo, o tra due diversi clustering. Un numero più basso è migliore, in quanto mostra una distanza minore tra due risultati di clustering.

Esistono numerose aree applicative in cui il clustering è uno strumento prezioso per il data mining o l'analisi esplorativa dei dati. Qui possiamo elencare solo un piccolo campione di tali aree di applicazione per dare un'idea dell'importanza di questo tipo di analisi.

Il clustering può aiutare a scoprire le anomalie misurando quali punti dati non sono inclusi nella struttura di clustering definita dall’analisi dei cluster. I punti dati che appartengono a cluster piccoli o molto sparsi o che sono lontani dal cluster assegnato possono essere considerati anomalie.

I metodi basati sulla densità, come il metodo aspettativa-massimizzazione, vengono utilizzati per individuare i punti dati nelle regioni dense come normali e quelli nelle regioni a bassa densità come anomalie.

Quando si cerca di capire quali potrebbero essere i personaggi dei clienti o i sottoinsiemi di mercati, il clustering può essere un potente strumento per aiutare a segmentare i clienti. Potresti essere in grado di combinare i dati demografici con i dati sul comportamento dei clienti per scoprire quali tipi di caratteristiche e modelli di acquisto sono più spesso correlati.

Le immagini possono avere i pixel raggruppati in vari modi che possono aiutare a ritagliare l’immagine in sezioni diverse per suddividere il primo piano dallo sfondo, rilevare oggetti utilizzando somiglianze di colore e luminosità o suddividerle in aree di interesse per un’ulteriore elaborazione.

Con le immagini, i metodi di clustering elaborano i pixel nell’immagine e definiscono le aree all’interno dell’immagine che rappresentano il cluster.

L’analisi di clustering può essere utile per l’elaborazione dei documenti in diversi modi.

I documenti possono essere raggruppati per somiglianza per mostrare quali sono i più simili tra loro. Questo può basarsi sulla lunghezza del documento, sulla distribuzione della frequenza delle parole o su altri vari modi per quantificare le sue caratteristiche chiave.

Un altro caso d’uso comune consiste nell’analizzare cluster di sezioni di un documento in base alla frequenza delle parole chiave, alla lunghezza della frase o alle distribuzioni di termini. Questo può aiutare a fare un riepilogo dei documenti o a suddividere documenti più grandi in set di dati più piccoli per consentire ulteriori analisi.