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