Che cos'è l'analisi dei cluster?

L'analisi dei cluster è una tecnica di analisi dei dati che esplora i gruppi presenti naturalmente all'interno di un insieme di dati, noti come cluster. L'analisi dei cluster non ha bisogno di raggruppare i punti dati in gruppi predefiniti, il che significa che è un metodo di apprendimento non supervisionato. Nell'apprendimento non supervisionato, le informazioni utili vengono ricavate dai dati senza etichette o classi predefinite. Un buon algoritmo di clustering garantisce un'elevata somiglianza intra-cluster e una bassa somiglianza inter-cluster.

Un esempio di problema di clustering dei dati

Il raggruppamento dei punti vendita al dettaglio in base alle loro vendite è un semplice caso di utilizzo dell'analisi dei cluster. Supponiamo che un bar abbia otto punti vendita in città. La tabella seguente mostra le vendite di cappuccino e caffè freddo al giorno.

Il grafico seguente mostra gli stessi dati, dove le vendite di cappuccino e di caffè freddo per ciascun punto vendita sono tracciate rispettivamente sugli assi X e Y. In questo esempio, poiché i punti dati erano limitati, è stato facile tracciare su un grafico i due cluster di punti vendita di caffè presenti naturalmente e visualizzarli manualmente.

Tuttavia, quando si tratta di migliaia di punti dati, è necessario utilizzare algoritmi di analisi dei cluster per segmentare i punti di dati in cluster diversi.

Quali sono le applicazioni dell'analisi dei cluster?

L'analisi dei cluster viene spesso utilizzata in due modi principali:

• Come strumento autonomo per la risoluzione di problemi legati al raggruppamento dei dati.
• Come fase di pre-elaborazione per vari algoritmi di machine learning.

L'analisi dei cluster come strumento a sé stante

• Marketing: nel marketing, l'analisi dei cluster può essere utilizzata per suddividere i clienti in diversi gruppi in base ai loro modelli di acquisto o interessi. Questi sono noti come "customer personas" o profili dei clienti. Le organizzazioni utilizzano quindi strategie di marketing diverse per i diversi gruppi di clienti.
• Analisi del rischio in finanza: le organizzazioni finanziarie utilizzano vari algoritmi di analisi dei cluster per suddividere i clienti in varie categorie di rischio in base al saldo bancario e al debito. Durante l'approvazione di prestiti, assicurazioni o carte di credito, questi cluster vengono utilizzati per aiutare il processo decisionale.
• Immobiliare: gli specialisti delle infrastrutture utilizzano il clustering per raggruppare le case in base alle loro dimensioni, alla loro posizione e al loro valore di mercato. Queste informazioni vengono utilizzate per valutare il potenziale immobiliare delle diverse zone di una città.

L'analisi dei cluster come fase di pre-elaborazione per il machine learning

L'analisi dei cluster viene spesso utilizzata come fase di pre-elaborazione per vari algoritmi di machine learning.

Gli algoritmi di classificazione eseguono l'analisi dei cluster su un ampio set di dati per filtrare i dati che appartengono a gruppi ovvi. Le tecniche avanzate di classificazione dei dati possono quindi essere utilizzate sui punti dati ridotti e non ovvi. Poiché l'insieme di dati diventa più piccolo, il tempo di calcolo si riduce notevolmente. Lo stesso metodo può essere utilizzato in modo opposto, quando un algoritmo di analisi dei cluster viene utilizzato per filtrare il rumore o i dati dei valori anomali.

Prima di eseguire un algoritmo di apprendimento supervisionato, si potrebbe prima eseguire un'analisi dei cluster sui dati di input per individuare i cluster naturali nei dati.

Quali sono i principali algoritmi di analisi dei cluster?

Gli algoritmi di analisi dei cluster appartengono spesso alle seguenti categorie:

• Algoritmi basati sulla partizione
• Algoritmi gerarchici
• Algoritmi basati sulla densità
• Algoritmi basati sulla griglia
• Algoritmi basati su modelli
• Algoritmi basati su vincoli
• Algoritmi di analisi dei valori anomali

Ogni algoritmo è complesso al suo interno e può essere adatto per alcune analisi e non per altre.

Algoritmi basati sulla partizione per l'analisi dei cluster

In questo metodo, un algoritmo inizia con diversi cluster iniziali. Quindi ricolloca iterativamente i punti dati in diversi cluster fino a raggiungere una partizione ottimale. L'algoritmo di clustering K-means è uno degli algoritmi di clustering più popolari.

Un esempio di clustering K-means mostra come funziona.

Fase 1: decidere i cluster

Decidere il numero di cluster, "K" per l'algoritmo, ad esempio K=3. L'algoritmo suddividerà i dodici punti dati di cui sopra in 3 cluster. Il numero K può essere un valore qualsiasi. A seconda di questo, la correttezza del raggruppamento può variare. Esistono anche dei metodi algoritmici che possono essere utilizzati per determinare il valore ottimale per K.

Fase 2: scegliere i punti dati

Dato che K=3, si possono prendere tre punti dati qualsiasi come medie iniziali. In questo esempio, i punti C, D ed E sono scelti come medie iniziali. Si noti che l'algoritmo K-means può prendere qualsiasi punto come media iniziale.

Fase 3: calcolare le distanze

Calcolare la distanza di ogni punto dell'insieme di dati dalla media iniziale del cluster. Sono state scelte casualmente tre medie di cluster C, D ed E. Per ogni punto del campione, calcolare la distanza da queste tre medie. La distanza euclidea tra due punti (X1, Y1) e (X2, Y2) viene utilizzata come segue:

Dopo la fase 3, una tabella mostrerà la distanza di ciascun punto di dati dalle medie iniziali C, D ed E.

Un punto dati viene aggiunto a un cluster in base alla sua distanza minima. Ad esempio, il punto A ha una distanza minima da una media iniziale C. Ciò significa che A si trova nel cluster con media C. Dopo la prima fase, si ottengono i cluster.

Fase 4: reiterazione; calcolo delle nuove medie

Ora è facile vedere i cluster iniziali. Il passo successivo consiste nel calcolare le medie dei tre nuovi cluster. A tal fine, si prende ogni punto dati in un particolare cluster e si calcola la media.

Nuova media del cluster "C" = (5+2+6+1+4+3+6/7, 21+11+22+10+23+14+12/7) = (3,85, 16,14), chiamiamo questo punto X.

Nuova media del cluster "D" = (1+2+5/3, 6+8+4/3) = (2,66, 6), chiamiamo questo punto Y.

Nuova media del cluster "E" = (4+5/2, 10+11/2) = (4,5, 10,5). Chiamiamo questo punto Z.

Fase 5: reiterazione; calcolare la distanza di ciascun punto dati dalla nuova media

Ripetere il passaggio 3 per trovare la distanza di tutti i punti dati dalle medie dei cluster appena calcolate, X, Y e Z. In questa nuova iterazione, è facile notare che la distanza minima dei punti di dati C, D, I e L è cambiata. Ora appartengono a un nuovo cluster, come mostrato di seguito.

Quindi, l'iterazione K-means deve continuare perché alcuni dei punti dati hanno cambiato cluster.

Fase 6: reiterazione; calcolo delle nuove medie e dei nuovi cluster

Poiché i punti dati C, D, I, L hanno cambiato cluster, è necessario calcolare le nuove medie dei cluster come nel passaggio 4. A tal fine, si prende ogni punto dati in un determinato cluster e si calcola la media. A tal fine, si prendono tutti i punti dati di un particolare cluster e se ne calcola la media. Poi, come nel passo 5, si calcola la distanza di ogni punto dati dalla nuova media del cluster. In base alla distanza, i punti dati vengono assegnati al cluster con cui hanno una distanza minima.

Quando termina l'algoritmo K-means?

K-means è un algoritmo di partizione iterativo:

• Decidere il numero di cluster (K) con cui iniziare. Nell'esempio precedente, K=3.
• Assegnare a caso un numero K di punti dati come media iniziale del cluster.
• Ripetere i passaggi seguenti fino a quando nessun punto dati cambia il proprio cluster.
• Calcolare la distanza media tra il punto dati e la media del cluster.
• Assegnare un punto dati al cluster con la distanza più bassa.
• Verificare se un punto dati ha cambiato cluster.

In una nuova iterazione, se ogni punto dati rimane nel suo cluster precedente, l'algoritmo K-means termina. Ciò significa che è stata ottenuta una soluzione localmente ottimale.

Algoritmo di clustering basato sulla partizione K-Medoid

L'algoritmo K-medoids è un altro algoritmo di clustering basato su partizioni. Gli algoritmi K-medoids scelgono i medoidi come oggetto rappresentativo di un cluster. L'algoritmo K-medoids cerca di trovare quei punti di dati che hanno una dissimilarità minima da ogni altro punto di dati in un particolare cluster. Finché la dissimilarità non viene minimizzata, l'algoritmo K-medoids partiziona iterativamente l'insieme di dati. L'algoritmo K-means utilizza spesso la distanza di errore quadratico (distanza euclidea), mentre gli algoritmi K-medoids utilizzano spesso la distanza in valore assoluto, come la distanza di Manhattan, per misurare la dissimilarità tra due punti dati.

Un'implementazione standard dell'algoritmo K-medoids è l'algoritmo Partition Around Medoids (PAM). Ecco i passaggi fondamentali dell'algoritmo PAM.

1. Scegliere un valore per K, dove K è il numero di cluster in cui verranno suddivisi i punti dati.
2. Scegliere a caso un numero K di punti dati come medoidi.
3. Per ogni punto (Xi, Yi) dell'insieme di dati, misurare la dissimilarità tra il punto e i medoidi sopra selezionati. Una misura spesso utilizzata per la dissimilarità è la distanza di Manhattan:
   • | Xi - Ci| + | Yi - Cj|, dove (Ci, Cj) rappresenta un medoide.
4. Ogni punto dati (Xi, Yi) viene assegnato a un cluster in cui la dissimilarità è minima.
5. Per ciascuno dei cluster di cui sopra, calcolare il costo totale, ovvero la somma delle dissimilarità di ciascuno dei punti dati in quel cluster.
6. A questo punto, selezionare a caso un punto non medoide come nuovo medoide e ripetere i passaggi 3-5.
7. Interrompere quando non ci sono cambiamenti nei cluster.

Confronto tra gli algoritmi K-means e K-medoids

Anche se l'algoritmo K-means è semplice, non produce buoni risultati quando i dati presentano molto rumore e valori anomali. Il metodo K-medoids è più robusto in questi casi. Tuttavia, gli algoritmi K-medoids come PAM sono utili solo quando l'insieme dei dati è piccolo. Quando le dimensioni dell'insieme di dati aumentano, il tempo di calcolo dell'algoritmo K-medoids aumenta esponenzialmente.

Algoritmi divisivi

Come suggerisce il nome, gli algoritmi divisivi assegnano tutti i punti dati a un unico cluster all'inizio. L'algoritmo divide quindi il cluster in cluster meno simili, poi divide ricorsivamente questi cluster fino a raggiungere una soluzione ottimale. Gli algoritmi divisivi sono noti anche come metodo di clustering top-down.

Algoritmi agglomerativi

Questi algoritmi iniziano assegnando ogni punto dati a un cluster diverso. Poi, l'algoritmo unisce ricorsivamente i cluster più simili fino a raggiungere una soluzione ottimale. Gli algoritmi agglomerativi sono noti anche come metodo di clustering bottom-up.

Esempio di un algoritmo di clustering agglomerativo

Di seguito è riportata una matrice di distanza per cinque punti dati. La distanza tra i punti può essere calcolata in base alla distanza euclidea, alla distanza di Manhattan o a qualsiasi altra formula di distanza. La matrice di distanza è sempre una matrice simmetrica, poiché la distanza tra i punti X e Y è uguale a quella tra Y e X. Sulla base di questa matrice di distanza, un esempio di algoritmo di clustering agglomerativo (bottom-up).

Fase 1: nella matrice delle distanze, trovare i due punti la cui distanza è minore. Nell'esempio precedente, si tratta dei punti 3 e 5. La distanza tra loro è pari a 2. Inserirli in un unico cluster.

Fase 2: eliminare i punti 3 e 5, sostituirli con il cluster "35" e creare una nuova matrice di distanza. A tal fine, è necessario calcolare la distanza fra tutti i punti dati e il cluster "35". Esistono vari modi per determinare questa distanza.

In questo esempio, per misurare la distanza è stato utilizzato il seguente metodo:

Distanza del punto X dal cluster "35" = minimo (distanza (X, 3), distanza (X, 5)). La matrice di distanza aggiornata basata su questo metodo è:

Fase 3: ripetere la fase 2 finché tutti i punti dati non vengono raggruppati in un cluster. Nell'esempio attuale, sono necessarie sei iterazioni. Il diagramma seguente mostra la formazione dei cluster. Questo tipo di rappresentazione è noto come dendrogramma. In questa rappresentazione, l'asse Y rappresenta la distanza tra due punti dati. Ad esempio, la distanza tra i punti 3 e 5 è pari a 2.

Fase 4: una volta raggruppati tutti i punti dati, come mostrato sopra, si decide quanti cluster devono essere mantenuti. È una decisione difficile, perché ogni algoritmo di clustering gerarchico alla fine produce un singolo cluster. Esistono diversi metodi per decidere il numero ottimale di cluster dopo che un algoritmo di clustering gerarchico ha suddiviso i dati.

Algoritmi di clustering basati sulla densità

Questi algoritmi si basano sull'idea che i cluster siano sempre più densi dello spazio dati circostante. Gli algoritmi basati sulla densità partono da un singolo punto dati ed esplorano i punti dati nelle sue vicinanze. I punti nelle vicinanze del punto iniziale vengono inclusi in un singolo cluster. La definizione di quartiere varia a seconda dell'implementazione dell'algoritmo. Il clustering spaziale di applicazioni con rumore basato sulla densità (DBSCAN) è un algoritmo di clustering molto diffuso in questa categoria.

Algoritmi di clustering basati sulla griglia

Gli algoritmi di clustering basati sulla griglia sono simili a quelli basati sulla densità. Lo spazio dei dati viene suddiviso in diverse unità più piccole, dette griglie. Ogni punto dati viene assegnato a una particolare cella della griglia. L'algoritmo calcola quindi la densità di ogni griglia. Le griglie la cui densità è inferiore a una soglia vengono eliminate. Successivamente, l'algoritmo forma dei cluster da gruppi adiacenti di griglie dense. Statistical information grid (STING) e clustering in quest (CLIQUE) sono due noti algoritmi basati su griglie.

Oltre agli algoritmi sopra descritti, l'analisi dei cluster comprende un gruppo di algoritmi di clustering basati su modelli, di clustering basati su vincoli e di analisi dei valori anomali.

Vantaggi e svantaggi degli algoritmi di analisi dei cluster