Tecniche di clustering

Il clustering consiste in un insieme di metodi per raggruppare oggetti in classi omogenee. Un cluster è un insieme di oggetti che presentano tra loro delle similarità, ma che, per contro, presentano dissimilarità con oggetti in altri cluster. L’input di un algoritmo di clustering è costituito da un campione di elementi, mentre l’output è dato da un certo numero di cluster in cui gli elementi del campione sono suddivisi in base a una misura di similarità. Gli algoritmi di clustering forniscono come output anche la descrizione delle caratteristiche di ciascun cluster.

La cluster analysis è utilizzata per numerose applicazioni:

  1. Ricerche di mercato.
  2. Riconoscimento di pattern.
  3. Raggruppamento di clienti in base ai comportamenti d’acquisto (segmentazione del mercato).
  4. Posizionamento dei prodotti.
  5. Analisi dei social network, per il riconoscimento di community di utenti.
  6. Identificazione degli outliers. Gli outliers sono valori anomali che presentano grandi differenze con tutti gli altri elementi di un data set. La loro identificazione può essere interessante per due scopi: l’eliminazione di questi valori anomali, che potrebbero essere causati da errori, oppure l’isolamento di questi casi particolari che magari rivestono una certa importanza per il business.

Gli algoritmi di clustering si dividono in due categorie principali:

  1. Algoritmi di clustering gerarchico
  2. Algoritmi di clustering partizionale

I primi organizzano i dati in sequenze nidificate di gruppi che potremmo rappresentare in una struttura ad albero. Gli algoritmi di clustering partizionale, invece determinano il partizionamento dei dati in cluster in modo da ridurre il più possibile la dispersione all’interno del singolo cluster e, viceversa, di aumentare la dispersione tra i cluster. Non si tratta in questo caso di algoritmi gerarchici, poiché i cluster sono tutti allo stesso livello di partizionamento. Gli algoritmi di clustering partizionali sono più adatti a data set molto grandi, per i quali la costruzione di una struttura gerarchica dei cluster porterebbe a uno sforzo computazionale molto elevato. Per questo, nel prosieguo del post ci occuperemo in modo più approfondito di questa tecnica.

La misura di similarità tra un elemento e un altro può essere calcolata con metodi diversi.

Esistono numerose misure di similarità, tra le quali ricordiamo la distanza di Minkowski, il Simple Matching Coefficient, il coefficiente di Jaccard, la Pearson’s correlation.

Uno dei più semplici è la distanza euclidea tra due punti in uno spazio n-dimensionale. La sua formula è:

clustering

 

dove:
xi e xj sono due elementi del data set rappresentati da vettori. Per es.: xi = {xi1, xi2, …, xin} n è il numero di dimensioni

La formula è valida per le variabili continue, mentre per i valori booleani (vero/falso) o per le variabili categoriche (per es. il colore che potrebbe essere verde, bianco, rosso, ecc..) si utilizza un’altra formula:

clustering 2

 

Dove
p è il numero di attributi booleani o categorici
m è il numero di attributi con lo stesso valore tra xi e xjIl clustering gerarchico di tipo agglomerativo utilizza l’algoritmo seguente per l’identificazione dei cluster:

  1. Inizialmente ciascun elemento del data set forma un cluster separato
  2. Ad ogni iterazione sono accorpati i cluster più simili, via via ampliando la soglia di similarità
  3. L’iterazione termina quando tutti gli oggetti sono accorpati in un unico cluster, dove tutti gli elementi sono considerati simili.

La formazione dei cluster è rappresentata attraverso un dendogramma, o grafico a albero, come mostra la figura seguente:

clustering 3

Il punto di taglio dell’albero, definito dall’utente e rappresentato in figura con il valore di distanza dx, determina il numero di cluster. L’algoritmo è accurato ma è poco efficiente dal punto di vista del calcolo. Inoltre non prevede una riassegnazione degli elementi ai cluster durante l’iterazione.

Vediamo ora come funziona il clustering partizionale. Innanzitutto occorre stabilire quanti cluster si vogliono avere e indichiamo tale numero con K. Il procedimento è il seguente:

1) Partizioniamo l’insieme in K cluster, assegnando a ciascuno di essi degli elementi scelti a caso.
2) Calcoliamo i centroidi di ciascun cluster k con al formula seguente:

clustering 4
Dove:
Mk è il vettore delle medie, o centroide per il cluster k
nk è il numero di elementi del cluster k
xik è l’i-esimo elemento del cluster3) Calcoliamo la distanza degli elementi del cluster dal centroide, ottenendo un errore quadratico, attraverso la formula
clustering 5
dove:
ek2 è l’errore quadratico per il cluster k
xik è l’i-esimo elemento del cluster
nk è il numero di elementi del cluster k
Mk è il vettore delle medie, o centroide per il cluster kLa somma degli errori di tutti i cluster fornisce l’errore totale per la partizione, che rappresenta il valore da minimizzare.4) A questo punto si riassegnano gli elementi del campione in base al più vicino centroide.5) Si ripetono i passaggi 2,3 e 4 finché il valore minimo dell’errore totale non è raggiunto, oppure finché i membri dei cluster non si stabilizzano.L’algoritmo, detto K-means,è sensibile all’allocazione iniziale dei valori e, in base ad essa, potrebbe convergere a un minimo locale della funzione d’errore e non al minimo assoluto. Inoltre è molto sensibile al rumore nei dati e alla presenza di outliers. La variante K-mediods, che utilizza al posto della media degli elementi del cluster l’oggetto più centrale (medioide), risente meno della presenza di dati rumorosi e di outliers.Bibliografia:
A. Rezzani, Business Intelligence. Processi, metodi, utilizzo in azienda, APOGEO, 2012

Mehmed Kantardzic Data Mining: Concepts, Models, Methods, and Algorithms, John Wiley & Sons, 2003
Jiawei Han, Micheline Kamber, Data Mining:Concepts and Techniques Second Edition, Morgan Kaufmann Publishers, 2006

Alessandro Rezzani

Sono un consulente senior nell’ambito della Business Intelligence, specializzato in analisi di Big Data e tecniche di Analisi Predittiva. Nel 2016 ho fondato Dataskills, presto diventata azienda di riferimento nel territorio italiano per soluzioni di Data Science. Sono anche ricercatore e professore presso l’Università Bocconi di Milano.
Leggi la mia Biografia