1. Introduzione agli Algoritmi di clustering Rosario Turco
Abstract Il presente articolo un'introduzione ad un settore
teoricamente molto esteso, di notevole importanza e con possibili
margini di innovazione, ancor oggi. Nel seguito l'autore percorre
la storia degli algoritmi di clustering, ne esamina i vari punti di
forza e le debolezze, nell'ottica di individuare una soluzione
implementativa valida, da utilizzare in un progetto software e
tenendo sempre come punto di attenzione importanti caratteristiche
come le prestazioni, la scalabilit, l'affidabilit e l'esistenza di
un prodotto di mercato, certificato e supportato. Introduzione Il
Clustering una tecnica nata, sin dagli anni '50, in ambito
Statistica; consente attraverso un'analisi dei dati di segmentarli
e raggrupparli secondo dei patterns. Gli algoritmi di clustering
sono da sempre di notevole interesse per innumerevoli settori:
Biologia molecolare; Progettazione componenti elettronici; Text
mining; Bioinformatica; Biomedicina e Medicina; Marketing, per la
segmentazione della clientela; Social Network Analysis (SNA); Data
Mining Analysis; Web; Analisi delle frodi; Fisco; Filtraggio
immagini; 1
2. etc La Clustering Analysis, per, un'attivit leggermente
differente rispetto a settori come KDD (Knowledge Discovery in
Databases) e Data Mining; anche se spesso si incrociano e si
auto-sostengono. Il KDD un processo di estrazione di conoscenza
(catasto, storia, informatica, matematica, fisica, etc)
immediatamente estraibile da un datawarehouse e direttamente
fruibile. Il DataMining , invece, un processo automatico che lavora
su un datawarehouse e che porta alla scoperta dell'esistenza di
strutture all'interno dei dati. La somiglianza, almeno in termini
di definizione degli obiettivi, tra DataMining e Clustering
notevole. Nel seguito, per, vedremo cosa si intende per Clustering
e le sue sfumature e differenze rispetto al Data Mining. Problema
dell'Apprendimento L'apprendimento sostanzialmente "il cosa" un
algoritmo riesce a comprendere, circa un insieme di dati a
disposizione; in pratica l'algoritmo alla ricerca di una "regola
generale" o una "descrizione", che spieghi l'insieme dei dati,
avendone a disposizione un insieme di grandezza limitata. Gli
algoritmi di apprendimento sono classificati in generale in tre
famiglie: algoritmi supervisionati; algoritmi con apprendimento per
rinforzo; algoritmi non supervisionati; Algoritmi supervisionati Si
di fronte ad un algoritmo supervisionato quando i dati sono in
forma di coppie input-output e una descrizione dei dati solo la
ricerca della funzione o del mapping tra input e output.
L'algoritmo supervizionato perch abbiamo a che fare con valori
target o desiderati associati in input . Se i dati di input o
target sono una categoria o una classe, l'algoritmo affronta un
problema di classificazione. Se i dati di input o target sono
valori interi , l'algoritmo affronta un problema di regressione.
Esempi Data una bitmap di caratteri ricercare la corretta lettera
dell'alfabeto un problema di classificazione. Ricercare un indice
di borsa a fronte dei dati storici , invece, un problema di
regressione. 2
3. Algoritmi per rinforzo E' una filosofia di programmazione,
in grado di apprendere dall'ambiente attraverso le interazioni o
input ricevuti da esso. L'obiettivo degli algoritmi, in tal caso,
di massimizzare il premio ottenibile che dipende dal contesto del
problema. Esistono due categorie: 1. algoritmi ad apprendimento
continuo, che hanno delle semplici regole per stabilire se si
penalizzati o premiati e comunque di adattarsi a variazioni
dell'ambiente. Esempi sono i riconoscitori vocali, oppure gli OCR
2. algoritmi ad addestramento preventivo, un esempio classico sono
le reti neurali. Alcuni componenti elettronici vengono realizzati
in prima battuta con circuiti a rete neurale e solo dopo
l'apprendimento di diverso tempo si cristallizza il componente
realizzandolo definitivamente. Algoritmi non supervisionati Se i
dati forniti sono un insieme di oggetti senza nessun dato di input
o target, allora abbiamo a che fare con algoritmi non
supervisionati; in tal caso l'algoritmo deve individuare delle
regole, rispetto a delle variabili, per raggruppare i dati in
qualche modo: cluster altro Scopo dell'articolo indagare sugli
algoritmi non supervisionati. Algoritmi di clustering Nel 1999 Jain
classific gli algoritmi di clustering (algoritmi non
supervisionati) in due grandi famiglie: algoritmi gerarchici di
clustering, che fanno uso di rappresentazioni grafiche
(dendrogrammi) algoritmi partition clustering, che assegnano i dati
o partizionano i dati, secondo criteri (come metriche, densit,
similarit etc), inserendo essi in cluster differenti. Oggi gli
algoritmi di clustering si dovrebbero classificare come:
Gerarchico, Partizionale, Densit, Modello, Grid-Based; la tendenza,
comunque, spesso di avere un misto di tecniche tra essi, per
migliorare la scalabilit e l'efficvienza, tale da ridurli a sole
due-tre categorie principali. 3
4. Algoritmi gerarchichi di clustering Questi algoritmi
lavorano raggruppando oggetti in gerarchie di cluster. La gerarchia
in tal caso pu avvenire top-down (divisive hierarchical methods) o
bottom-up (agglomerative hierarchical methods). La loro complessit
di solito O(n^2). Alcuni miglioramenti furono introdotti con BIRCH
(Balanced Iterative Reducing and Clustering using Hierarchies) che
ha una complessit O(n), lavora con meno memoria, utilizza una
struttura dati CF-Tree per memorizzare e comprimere informazioni e
fa meno I/O. BIRCH lavora bene su data set con cluster sferici.
Altro algoritmo del genere CURE (Clustering Using Representative),
con O(n^2) e lavora con una filosofia diversa da BIRCH: usa un
numero fisso di punti di riferimento per determinare i cluster. Usa
un approccio gerarchico agglomerativo, in cui si mappa ogni cluster
con un insieme di oggetti rappresentativi. In ogni cluster vengono
identificati questi punti rappresentativi, che vengono condensati
verso il centro di un fattore prefissato (per ridurre leffetto del
rumore). La fusione di due cluster dipende dalla distanza tra i pi
vicini punti rappresentativi. Permette di gestire in modo corretto
clusters non sferici, scala bene allaumentare del numero di punti.
molto sensibile alla scelta dei parametri (numero di punti
rappresentativi, fattore di condensazione). Altri algoritmi noti
sono AGNES (AGlomerative NESting), DIANA (Divisive ANAlysis), Rock,
Chameleon che risulta pi efficace di CURE e di DBSCAN
(Density-Based Spatial Clustering of Applications with Noise).
Problematiche del clustering gerarchico Il clustering gerarchico
tipicamente poco scalabile (complessit almeno O(n^2)), e
tipicamente non consente di tornare indietro (se si fondono male
due cluster, non c modo poi di separarli a meno di non ripartire
daccapo con lalgoritmo). Hanno per interesse per tutti i problemi
che hanno dietro come inpalcatura una gerarchia tra nodi, item,
oggetti o soggetti. Cluster Analysis L'analisi dei cluster o
Cluster Analysis fu introdotta nel 1939 da Robert Tryon. La Cluster
Analysis un insieme di tecniche, matematiche ed informatiche, di
analisi dei dati con il preciso obiettivo di raggruppare i dati in
insiemi omogenei rispetto a determinate variabili. Tutte le
tecniche di analisi clustering si basano sul concetto di distanza
(come metrica) tra due punti, oggetti o dati. La bont delle analisi
di clustering dipende, quindi, dalla scelta della metrica o della
distanza o, come si dice, dalla minimizzazione 4
5. dell'Errore di Quantizzazione. Gli algoritmi di clustering
raggruppano i dati in base alla distanza reciproca e, quindi,
l'appartenza di un dato ad un insieme dipende da quanto esso dista
dall'insieme. Algoritmi di partition clustering Lo scopo di questi
algoritmi innanzitutto minimizzare la dissimilirit tra i dati di
uno stesso gruppo (o cluster o insieme )e massimizzare la
dissimilirit tra i dati di cluster differenti, secondo una metrica
prescelta che pu dipendere anche dal problema da affrontare. Nel
seguito accenneremo solo agli algoritmi di partition clustering.
Clustering density-based o Locality based Lo scopo di un algoritmo
Clustering density based di creare raggruppamenti di dati,
considerando l'intorno di ogni punto (o dato) nello spazio
d-dimensionale; analizzando, cio, la densit dei punti in un intorno
di raggio prefissato. Tutto questo possibile se si assume come
"propriet fondamentale" la densit locale dei punti, rinunciando
alla densit globale dei dati in senso statistico, proprio perch la
densit locale dei punti consente di individuare raggruppamenti in
zone diverse dello spazio d-dimensionale, altrimenti impossibile.
OPTICS, ad esempio, un algoritmo basato su questa idea. Definizioni
Sono importanti due parametri nel prosieguo: il raggio dell'intorno
considerato il numero minimo MinPts di punti all'interno dello
spazio o intorno considerato Oggetti Core e Oggetti Directly
Density Reachable Un oggetto p nell'intorno di un oggetto q se la
distanza tra p e q minore o uguale al raggio . Se l'oggetto q ha
nel suo intorno di raggio almeno MinPts punti, allora esso definito
"oggetto Core"; mentre l'oggetto p definito "Directly Density
Reachable" da q, ovvero nell'intorno di un oggetto core.
Illustrazione 1 Oggetti Density Reachable Un oggetto p Density
Reachable da un oggetto q, se esiste una 5
6. catena di oggetti p1=q,p2,...,pn=p per cui ogni oggetto pi+1
Directly Density Reachable dal precedente pi. Illustrazione 2
Oggetti Density Connected Un oggetto p Density Connected ad un
oggetto q se esiste un terzo oggetto o, da cui sia p che q sono
Density Reachable dall'oggetto o. Illustrazione 3 Cluster Un
cluster C un sottoinsieme dei dati, massimale e connesso. Per
massimale si intende che per ogni p e q, se p apparteiene a C e q
density reachable da p, allora q in C. Per connesso si intende che
per ogni p e q appartente a C, p density connected a q. Punti
Border e Outlier Un punto border sul bordo del cluster; mentre un
punto outlier non border n core. OPTICS usa qualche metrica
aggiuntiva, che andiamo a definire nel seguito. Core Distance e
Reachability Distance La Core Distance il min valore di raggio per
cui l'oggetto possibile considerarlo core, ovvero min = '. La
Reachability Distance tra due oggetti p e q il max valore tra
distanza euclidea e la Core Distance, ovvero max [de(p,q),'].
OPTICS (Ordering Points To Identify Clustering) Tipicamente la fase
di analisi per la determinazione dei cluster affrontata in almeno
due fasi. In pratica non si assegna un cluster ad ogni dato
elaborato, ma si elaborano prima gli oggetti per comprendere dove
si addensano e poi si decidono i cluster. 6
7. La tecnica nota come "DBSCAN" (Density-Based Spatial
Clustering of Applications with Noise). L'algoritmo va alla ricerca
di zone ad alta densit di punti rispetto a zone a bassa densit e
l'idea base del DBSCAN, come gi accennato precedentemente, di
individuare zone con punti che superano una soglia (il MinPts). La
tecnica DBSCAN ha complessit O(n^2), ma se si usa un indice
spaziale la complessit diventa O(nlogn). Vediamo nel seguito le due
fasi usate. Fase "Scan dei dati" Viene fatta l'analisi di un
oggetto, se non stato ancora elaborato, e si determinano i punti
nel suo intorno. Per questo si considera il raggio ed occorre
individuare almeno MinPts punti nell'intorno. Poi si calcola la
"Core Distance" ' e si inserisce l'oggetto nel database finale (DBF
da adesso in avanti) se esso un oggetto core. Se l'oggetto
precedente non un oggetto core, si passa ad un altro oggetto non
elaborato ancora. Se, invece, un oggetto core si determinano,
fissato e MinPts, tutti gli oggetti Directly Density Reachable
dall'oggetto. Tali oggetti, poi, sono inseriti in una lista (Lista
nel seguito), ordinata secondo la distanza euclidea dei punti
crescente al pi vicino oggetto core raggiungibile; viene, poi,
settata la Core Distance e la Reachability Distance. Si cicla ad
ogni passo sulla Lista, di cui prima, selezionando l'oggetto con la
minor Reachability Distance e si calcolano i punti vicini
(neighbors) e la Core Distance; infine l'oggetto viene alla fine
scritto nel DBF. Se l'oggetto core allora ulteriori punti possono
essere scritti nella lista e se ne aggiorna l'ordinamento e questo
finch non sono processati tutti i dati. Fase "elaborazione del DBF"
In questa fase si scandaglia sequenzialmente il DBF. Si fissa un
cluster corrente, se la Reachability Distance dell'oggetto
considerato maggiore della Clustering Distance ', in tal caso
l'oggetto non Density Reachable rispetto a ' e MinPts da nessuno
degli oggetti presenti nell'ordinamento prima dell'oggetto stesso.
Per cui si guarda la Core Distance e si crea un nuovo cluster B
solo se l'oggetto core rispetto a ' e MinPts, altrimenti
considerato rumore (noise). Se, invece, la Reachability Distance
dell'oggetto considerato minore della Clustering Distance ', si
assegna l'oggetto al cluster corrente, perch Density Reachable
rispetto a ' e MinPts dagli oggetti precedenti dell'ordinamento.
Visualizzazione con istogrammi Un metodo semplice di
visualizzazione nel caso Optics o degli algoritmi Clustering
density-based il Reachability plot. Si tratta di tracciare su
grafico un istogramma che mostra di ogni 7
8. oggetto il suo Reachability Distance nell'ordine in cui gli
oggetti sono processati. Appena si trova un oggetto core, invece,
si passa ad elaborare tutti gli ogetti Directly Density Reachable
rispetto all'oggetto core, proseguendo dai punti pi vicini a pi
lontani. In figura a sinistra l'addensamento degli oggetti e
l'individuazione dei cluster; mentre a sinistra il grafico degli
istogrammi. Tecniche automatiche per il clustering density based
Sono usate tecniche per creare i cluster automaticamente gestendo
una struttura gerarchica di cluster. In genere si lavora sugli
istogrammi degli oggetti, prodotti a partire da una metrica di
similarit o di distanza (ad esempio r il coefficiente di Pearson,
oppure la distanza euclidea normalizzata, etc). Avendo a
disposizione gli istogrammi occorre introdurre il parametro grado
di ripidezza. 8
9. Un punto detto "steep upward point" quando un punto ripido
in salita con un Reachability Distance almeno inferiore di %
rispetto al successivo. Un punto "steep downward point" l'analogo
punto ripido in discesa. Una "steep upward area" , invece, un'area
[s,e] tale che s ed e sono steep upward points; mentre ogni punto
tra s ed e ha una Reachability Distance almeno uguale a quella dei
suoi predecessori. Inoltre l'area non contiene pi di MinPts punti
che non sono "steep upward" points, altrimenti contribuirebbero a
cluster diversi. Analogamente si pu dire per una "steep downward
area". Un cluster soddisfa i seguenti requisiti: 1. inizia con una
"steep downward area" D; 2. Finisce con una "steep upward area" U;
3. L'inizio del cluster l'ultimo punto con alto valore di
Reachability Distance; 4. La fine del cluster l'ultimo punto con
basso valore di Reachability Distance; 5. La Reachability Distance
dei punti nel cluster deve essere % minore a quella del primo punto
di D e dell'ultimo punto di U Usando i criteri di sopra si possono
automatizzare le ricerche dei cluster. Clustering K-means (o
K-medie) Supponiamo di avere un insieme totale di n punti, in uno
spazio d- dimendionale. L'obiettivo che ci poniamo di individuare k
punti con kn, nello spazio d-dimensionale, minimizzando la distanza
quadratica media di ogni punto da un centroide. Detto in altri
termini occorre massimizzare, rispetto ad una serie di metriche, il
rapporto tra la varianza esterna (tra i gruppi) e quella interna
(nei gruppi). Il metodo sensibile ai punti outlier. Per tali tipi
di problemi non sono ancora noti algoritmi in tempi polinomiali.
Supponiamo inizialmente di far riferimento alla distanza euclidea
tra i punti x e y: d d E ( x, y ) = || ( x, y ) ||= i= 1 ( xi yi )
2 Ad esempio la distanza euclidea tra il punto (0,0), origine di un
sistema di assi cartesiani (d=2 o 2D), ed il punto (3,4) : 9
10. (3 0) 2 + (4 0) 2 = 5 La distanza euclidea viene, di
solito, valutata rispetto ad un "centroide" d-dimensionale tra k
punti d-dimensionali come segue: k k k x1i x2 i xd i (1) ( x1 , x2
,..., xk ) = i= 1 , i= 1 ,..., i = 1 k k k Ad esempio il centroide
in ambito 2D (d=2) dei punti (2,4),(5,2), (8,9), quindi con k=3, :
2+ 5+ 8 4+ 2+ 9 = , = ( 5,5 ) 3 3 Generalizzando, l'idea di base di
cercare k vettori j per j=1,...,k; poi per classificare un punto x
si dovr trovare il vettore j pi vicino a x e, in tal caso, potremo
affermare che x appartiene al cluster j. Supponiamo, difatti, che
il data set di dati disponibili x^n con n=1,...,N. Ora occorre
partizionare il dataset in k sottoinsiemi disgiunti Sj per
j=1,...,k a cui sar associabile un vettore j. L'errore di
quantizzazione E viene definito con: k 1 E= 2N j = 1 n S j ||x n j
||2 dove, in base alla (1) : 1 j = N n S j xn (2) Minimizzare
l'errore di quantizzazione significa minimizzare la distorsione o
la perdita di informazione che si ottiene sostituendo un punto (a
volte detto anche centro) col suo centroide. Per cui l'algoritmo
k-means va applicato, in generale, secondo i seguenti passi: 1. Si
assegnano inizialmente i punti x^n (punti o centri) in 10
11. modo randomico nei k insiemi (o cluster fissati) e si
scelgono k centri iniziali, uno per ogni cluster 2. Si calcolano i
centroidi con la (2) in basa ai cluster iniziali fissati ed i
centri iniziali 3. Si assegna ogni punto al pi vicino j e quindi lo
si assegna nel cluster j (questo minimizza la varianza interna e
massimizza la varianza esterna) 4. Se E non diminuisce ci si
arresta (significa anche che i punti non si spostano pi tra
cluster); se, invece, diminuisce si ritorna al passo 2 per
continuare Per poter minimizzare la distorsione occorre: 1. ogni
punto deve essere codificato col suo centroide 2. la derivata
parziale della distorsione rispetto alla posizione di ogni centro o
punto deve essere nulla. La configurazione iniziale dei punti e la
scelta di k L'algoritmo ha una relativa velocit di convergenza. Il
risultato iniziale non necessariamente quello ottimo. La cosa
dipende dalla configurazione iniziale, per cui di solito si provano
pi configurazioni iniziali randomiche o manuali dei punti e si
confrontano i risultati per scegliere alla fine la configurazione
iniziale giusta. Anche con la scelta di k si preferisce provare
diversi valori di k, in modo che minimizzi le distanze
intra-cluster e massimizzi le distanze inter-cluster. L'algoritmo
ha complessit O(tkn) dove t il numero di iterazioni che occorranno,
n il numero di punti e k il numero di cluster. Scelta della metrica
In generale uno dei problemi fondamentali, legato anche al
problema, la scelta della metrica di similitarit (Similitarity
Metric) o anche di distanza tra due serie di numeri
x={x1,x2,...,xn} e y={y1,y2,...,yn}. Possono essere scelte diverse
metriche, alcune delle quali sono: Distanza euclidea quadrata
distance(x,y)=i(xi-yi)2 Rappresenta la distanza o path pi breve tra
due punti.Di solito preferibile una distanza normalizzata ovvero
1/N di quella di sopra. Distanza City-block (Manhattan)
distance(x,y)=i|xi-yi| Il concetto dietro al City-block come se una
citt fosse divisa in quartieri o blocchi e per arrivare da un punto
11
12. all'altro della citt non possibile fare la distanza pi
breve, ma percorsi permessi tra quartieri; per cui il city- block
la somma dei path possibili messi a disposizione da ogni quartiere.
Di solito preferibile una distanza normalizzata ovvero 1/N di
quella di sopra. Distanza Chebychev distance(x,y)=Maximum|xi-yi|
Percentuale di disaccordo distance(x,y)=(Number of xiyi )/i
Coefficiente di correlazione di Pearson 'centered' 1 N xi x yi y r=
N i= 1 x y dove x o y 'segnato' sono la media, mentre x o y sono la
devizione standard. Il coefficiente r vale 1, 0, -1. Con 1 esiste
una correlazione tra i dati xi e yi, con 0 non esiste e con -1 una
correlazione opposta. Quando non si vuole parlare di distanza, ma
di similarit, r la metrica preferita insieme a quello uncentered.
Se si usa questo coefficiente non necessaria una normalizzazione,
perch gi implicita nella definizione. Il concetto della
correlazione di Pearson quanto r si avvicina ad approssimare il
passaggio per i punti; oppure pi semplicemente se i vettori x e y
sono pensati come curve di punti xi e yi, allora il coefficiente di
Pearson indica se le due curve hanno pendenze simili. Il
coefficiente di Pearson invariante rispetto ad una trasformazione
lineare di y; ad esempio se gli yi sono moltiplicati per una
costante o sommati per una costante il coefficiente di Pearson
ancora uguale al precedente (la pendenza rimasta la stessa).
Coefficiente di correlazione di Pearson 'uncentered' 1 N xi yi r=
(0) (0) N i= 1 x y rispetto al 'centered' assume la media nulla
anche se non lo realmente. Mentre sono definite come: N 1 (x) 2 (0)
x = i N i= 1 N 1 (y) 2 (0) y = i N i= 1 Se i dati x e y sono due
vettori, con analoga pendenza, e tra 12
13. i punti xi e yi esiste un offset costante, allora la
centered correlation 1 ma non 1 l'uncentered correlation. Questo
perch l'uncentered correlation rappresenta il coseno dell'angolo
tra due vettori x e y n-dimensionali, ognuno dei quali in uno
spazio a n dimensioni che passa per l'origine. Spearman rank
correlation rSpearman che rappresenta la correlazione dei rank dei
dati dei vettori. E' una versione derivata dal coefficiente di
Pearson, ed un coefficiente di solito pi robusto con gli outliers.
Si parte dai vettori e si sostituisce ad ogni loro valore quello
del loro rank o della loro posizione, poi si ricava il
coefficiente. In questo modo rimpiazzando il valore con quello del
rank si ottiene un valore prossimo a quello del coefficiente di
Pearson standard, anche se esistono valori estremi elevati
(outliers). Spesso lo Spearman rank correlation usato come test
statistico di indipendenza di x da y. Il di Kendall, anch'esso un
coefficiente derivato da quello di Pearson. Con Nc indichiamo il
numero di coppie (xi,yi) (xj,yj) concordi, cio tali che: xi > xj
e yi > yj oppure xi < xj e yi < yj (sinteticamente ogni
coppia con segni >> o