Introduzione agli

Algoritmi di clusteringRosario Turco

AbstractIl 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.

IntroduzioneIl 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

• etcLa 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'ApprendimentoL'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 supervisionatiSi è 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

Algoritmi per rinforzoE' 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 supervisionatiSe 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 clusteringNel 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

Algoritmi gerarchichi di clusteringQuesti 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 l’effetto 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 all’aumentare 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 gerarchicoIl 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 l’algoritmo). Hanno però interesse per tutti i problemi che hanno dietro come inpalcatura una gerarchia tra nodi, item, oggetti o soggetti.

Cluster AnalysisL'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

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 clusteringLo 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 basedLo 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.DefinizioniSono 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 ReachableUn oggetto p è nell'intorno di un oggetto q se la distanza tra p e q è minore o uguale al raggio Є.

Oggetti Density ReachableUn oggetto p è Density Reachable da un oggetto q, se esiste una

5

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

catena di oggetti p1=q,p2,...,pn=p per cui ogni oggetto pi+1 è Directly Density Reachable dal precedente pi.

Oggetti Density ConnectedUn 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.

ClusterUn 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 OutlierUn 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 DistanceLa 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

Illustrazione 2

Illustrazione 3

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 istogrammiUn 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

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 basedSono 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

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 UUsando 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 k≤n, 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:

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

2

1

( , ) || ( , ) || ( )d

E i ii

d x y x y x y=

= = −∑

La distanza euclidea viene, di solito, valutata rispetto ad un "centroide" d-dimensionale tra k punti d-dimensionali come segue:

Ad esempio il centroide in ambito 2D (d=2) dei punti (2,4),(5,2),(8,9), quindi con k=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:

dove, in base alla (1) è:

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

2 2(3 0) (4 0) 5− + − =

1 21 1 1

1 2( , ,..., ) , ,...,

k k k

i i d ii i i

k

x x xx x x

k k kµ = = =

=

∑ ∑ ∑

( )2 5 8 4 2 9, 5,53 3

µ + + + + = =

2

1

1 || ||2

j

kn

jj n S

E xN

µ= ∈

= −∑ ∑

1

j

nj

n Sx

Nµ

∈= ∑

(1)

(2)

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 centroide2. 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 kL'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 metricaIn 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

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 xi≠yi )/i

• Coefficiente di correlazione di Pearson 'centered'

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'

rispetto al 'centered' assume la media nulla anche se non lo è realmente. Mentre sono definite come:

Se i dati x e y sono due vettori, con analoga pendenza, e tra

12

1

1 Ni i

i x y

x x y yrN σ σ=

− −= ∑

(0) (0)1

1 Ni i

i x y

x yrN σ σ=

=

∑

( )

( )

2(0)

1

2(0)

1

1

1

N

x ii

N

y ii

xN

yN

σ

σ

=

=

=

=

∑

∑

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 <<)

mentre con Nd quelle discordi (sinteticamente ogni coppia con segni <> o >< ) che non rispettano la definizione precedente. In tal caso è:

Anche il coefficiente di Kendall può essere usato come test di indipendenza dei dati.

Missing valueSe uno dei due vettori da confrontare nella similitarità ha valori assenti, il valore presente nell'altro vettore corrispondente non verrà considerato; questo per poter confrontare a coppie i valori (xi,yi).

13

( 1) / 2Nc Nd

N Nτ −=

−

Esempio concettuale di clusteringSupponiamo k=2 cluster e prendiamo k=2 centri casuali (quelli in arancione nella figura 1), uno per cluster.Clusterizziamo i nostri dati rispetto a questi centri.

Codebook e Codevector, Insieme di Voronoi e Regione di VoronoiFormalizziamo ulteriormente quello già visto prima e indichiamo il dataset dei dati D con:

di cardinalità N, costituito da vettori S appartenenti a Rn, allora

14

Illustrazione 4

Ricalcoliamo ora i centroidi in base ai cluster individuati (vedi figura 2).

Rifacciamo il clustering dei nostri dati rispetto ai nuovi centroidi individuati (vedi figura 3).

Illustrazione 5

Illustrazione 6

Illustrazione 7

Si ripetono gli ultimi due passi fintanto che dei punti si muovono da un cluster ad un altro (vedi figura 4).

{ }1 2, ,..., ND S S S=

chiamiamo codebook l'insieme:

i cui elementi, detti codevector, sono:1. appartenenti a Rn,2. e l'insieme W ha una cardinalità k«N

L'insieme di Voronoi Vc del codevector μc è l'insieme di tutti i vettori in D per i quali μc è il codevector più vicino (o winner):

Per conseguenza la Regione di Voronoi Rc del codevector μc è l'insieme di tutti i vettori in Rn per i quali μc è winner:

La definizione di un codebook porta, inevitabilmente, alla quantizzazione vettoriale dello spazio di input e lo spazio di input diventa una collezione di poliedri (tassellazione di Voronoi).

15

{ }1 2, ,..., kW µ µ µ=

{ }| arg min || ||j jVc S D c S µ= ∈ = −

{ }| arg min || ||nj jRc S R c S µ= ∈ = −

Da quanto visto prima, una volta fissati i codevectors (k) possiamo ottenere codebook differenti; il codebook migliore è quello che minimizza l'errore di quantizzazione:

dove |D| è la cardinalità di D.

Algoritmo K-means (il ciclo di Lloyd)

L'algoritmo già visto prima, e qui riformulato, è dovuto a Lloyd nel 1957 e consiste in quattro passi iterativi:

1. Inizializziamo il codebook W={μ1,μ2,...,μk} con k vettori scelti dall'insieme dati D

2. Calcoliamo per ogni codevector μi ε W l'insieme di Voronoi del codevector

16

2

1

1 || ||2 | |

c

k

cc S V

E SD

µ= ∈

= −∑ ∑

Illustrazione 8: Tassellazione di Voronoi

3. Assegniamo ad ogni codevector μi la media (o centroide) dell'insieme di Voronoi

4. Torniamo al passo 2 se qualche codevector cambia; altrimenti abbiamo terminato.

Principali problematiche tecniche degli algoritmi precedentiI problemi che nascono con tecniche come quelle precedenti e di tante altre simili sono:

1. le performance che richiedono: • cluster hardware e linguaggi di programmazione che

consentano parallelismo e velocità di esecuzione• database in cluster ed affidabili• attenzione nella progettazione e nell'implementazione

privilegiando tecniche che migliorino le prestazioni 2. scarsa scalabilità del sistema di analisi non appena aumenta

largamente il numero di oggetti del data set di analisi ed il numero di dimensioni in gioco del dominio del problema (es: centinaia di migliaia di dimensioni).

In sostanza l'efficacia degenera col numero di dimensioni ed in base alla quantità di rumore (o errore). L'efficienza degenera al crescere del numero di punti da elaborare e del numero di dimensioni.Il punto 2 richiede un'attenta valutazione del proprio dominio del problema, con un'accurata scelta dei prodotti di base da utilizzare (tipicamente del prodotto a supporto della propria base dati), oltre ad una precisa progettazione di ogni dettaglio. Uno dei difetti delle precedenti tecniche, inerenti il punto 2, ma che il clustering grid-based evita, è che se la tecnica utilizzata porta al relazionamento col punto vicino o con il più vicino dei punti, allora questa tecnica tenderà a lavorare male in un dataset ad alte dimensioni. Difatti in un dataset con molte dimensioni, è improbabile che i punti sono più vicini gli uni agli altri rispetto alla distanza media tra i punti, perché c'è spazio scarsamente riempito. Come risultato, appena aumenta la dimensionalità, la differenza tra la distanza dal più vicino e dal più lontano di un punto va a zero (vedi [3]).

Clustering Grid-based e il miglioramento di OptiGridI metodi grid-based sono ragionevolmente veloci, capaci di scoprire cluster di qualsiasi forma.

17

1| |i

S ViS

Viµ

∈

= ∑

{ }| arg min || ||j jVi S D i S µ= ∈ = −

Gli algoritmi grid-based dividono lo spazio dell'input in ipercelle rettangolari, scartano le ipercelle a bassa densità e uniscono le ipercelle ad alta densità per formare i cluster. Molti algoritmi di tal genere sono STING, MAFIA, CLIQUE etc (vedi [3]). Tuttavia anche gli algoritmi grid-based diventano costosi, specie in termini di memoria, all'aumentare delle dimensioni in gioco.Esistono, però, diversi algoritmi che cercano di superare il problema dell'aumento della dimensionalità: ORCLUS, PROCLUS, OptiGrid, O-Cluster sono un esempio.OptiGrid è un algoritmo interessante sia per la sua semplicità che per la capacità di trovare cluster in spazi ad alte dimensioni, anche in presenza di rumore.

OptiGrid costruisce un "grid partitioning" dei dati, usando degli iperpiani di partizionamento e usando un "contratto progettuale" tra le differenti partizioni dei dati.

OptiGrid cerca degli iperpiani che soddisfano due requisiti:1. la separazione degli iperpiani deve effettuare un taglio

attraverso le regioni a bassa densità rispetto alla regioni circostanti;

2. la separazione degli iperpiani dovrebbe mettere in cluster i singole partizioni diverse.

Il primo requisito mira a prevenire il problema definito "oversplitting", cioè un piano di taglio non deve dividere mai un cluster. Facendo il taglio in regioni a bassa densità non si taglia uno stesso cluster in più parti, cioè non si dividono i dati di "ugual significato e peso", che dovrebbero stare in uno stesso cluster.

Il secondo requisito è il tentativo di far sì che il piano di taglio contribuisca a trovare cluster separati.

OptiGrid costruisce ricorsivamente una griglia multidimensionale con il partizionamento dei dati, utilizzando un taglio a iperpiani, ciascuno dei quali è ortogonale ad almeno una proiezione. Ad ogni step la generazione degli iperpiani candidati è controllata da due parametri di soglia:

1. il livello del rumore (noise level)

2. la massima densità di splitting

La tecnica implementativa proposta dagli autori considera che gli iperpiani di partitioning sono proiezioni parallele all'asse e dimostrano che l'errore diminuisce all'aumentare delle dimensioni (vedi [3]).

18

Difetti di OptiGridOptiGrid ha due difetti principali:

• è sensibile alla scelta dei parametri che portano alla scelta del piano di taglio;

• non descrive o prevede una tecnica di gestione dei dati dei dataset che non riescono, poi, a trovare spazio in memoria.

Algoritmo O-Cluster (Ortoghonal Partitioning Clustering)O-Cluster, è nato in ambito del database Oracle, già dal 2002 in Oracle 9i e presente come pacchetto PL/SQL. Sfrutta l'idea di base di OptiGrid e cerca di introdurre miglioramenti tale da eliminare i suoi due difetti principali.Due sono i punti di miglioramento introdotti in O-Cluster:

• l'uso di test statistici per validare o meno la scelta del piano di taglio, rendendo automatica tale operazione e garantendo una buona qualità del piano di taglio;

• l'uso di un buffer contenente un campione random dei dataset; il campionamento permette di avere ulteriori informazioni disponibili per le partizioni e la scelta del piano di taglio. Per alcuni tipi di partizioni, come vedremo, è possibile rimuovere dal buffer i dati dei dataset associati per liberare memoria e analizzare il resto dei dati.

O-Cluster lavora ricorsivamente: prima analizza i possibili punti di splitting (o di taglio) rispetto a tutte le dimensioni; poi individua il miglior splitting e divide i dati in due partizioni.

A questo punto O-Cluster cerca nuovi splitting da fare nelle due partizioni iniziali individuate. In pratica O-Cluster crea un albero gerarchico che tassella lo spazio di input in rettangoli.

O-Cluster ha complessità O(N*d) dove N è la quantità di dati nel buffer e d sono le dimensioni.L'algoritmo che usa O-Cluster si può riassumere come nel diagramma a blocchi successivo; i punti fondamentali dello schema a blocchi sono stati numerati e ad essi faremo riferimento nel seguito:

Step 1 Load Buffer: se l'intero daset non entra in memoria si mettono nel buffer solo dei campioni selezionati randomicamente (campionamento).Step 2 Computa gli istogrammi: l'obiettivo è di determinare un

19

insieme di proiezioni o dimensioni rispetto alle quali determinare degli istogrammi. Ogni partizione che presenta una foglia nella gerarchia di cluster e non è masrcata 'ambigua' o 'frozen' è da considerarsi come una partizione attiva. Allo step 4 e a quello 6 si vedrà cosa si intende per marcare le partizioni ambigue e frozen. E' essenziale calcolare gli istogrammi perchè, secondo vari studi (vedi [3]), si evidenzia che è possibile individuare un numero ottimale di contenitori in base alla distribuzione dei dati.Secondo alcuni studi l'approccio più semplice porta ad un numero di contenitori inversamente proporzionale alla deviazione standard dei dati di una certa dimensione e direttamente proporzionale a N1/3, con N il numero di punti interni ad una partizione. Un metodo alternativo è di considerare una strategia di contenitori globali e cambiare gli istogrammi appena il numero dei punti interni alla partizione decrementa. O-cluster è comunque robusto rispetto a qualsiasi strategia adottata.

Step 3 Cerca il 'best splitting': per ogni istogramma O-Cluster cerca il miglior piano di taglio se esiste; difatti un buon piano di taglio deve passare attraverso un punto di bassa densità dell'istogramma (un avvallamento) e l'avvallamento dovrebbe essere supportato, su entrambi i lati, da punti di alta densità (picchi). O-Cluster cerca proprio un avvallamento ed un picco, ad entrambi i lati, tale che la differenza tra picchi e gli avvallamenti sia significativo da un punto di vista statistico. Il test

20

significativo statistico che usa O-Cluster è il test χ2:

Nella formula il "valore osservato" è il conteggio degli istogrammi nell'avvallamento, mentre il "valore atteso" è il conteggio medio degli avvallamenti e dei picchi. Alcune implementazioni di O-Cluster risalenti al 2002 usavano già i seguenti valori: χ2=95% e χ2

0.005,1=3,843 dando buoni risultati.

Step 4 Marca 'ambigous' e 'frozen partitions':Se non esiste un buon splitting delle partizioni, O-Cluster cambia il test χ2, abbassando ad esempio χ2=90% e χ2

0.1,1=2,706. Se su molti dati si riscontra questo tipo di situazione, ovvero che abbassando i valori si rientra nel test, allora la partizione corrente è marcata 'ambigua'. Se non vengono trovati splitting, anche abbassando più volte i valori, e il test non è mai superato (partizioni ambigue) allora la partizione è marcata 'frozen' e i punti di essa vengono eliminati dal buffer.

Step 5 Splitting delle partizioni attive: Se è stato individuato uno splitting vengono create due partizioni e il procedimento riparte dallo step 2.

Step 6 Reload buffer: Il reload buffer viene attuato solo dopo che gli splitting sono terminati, come si vede dal diagramma a blocchi. Se tutte le partizioni rimaste sono marcate frozen oppure i dati sono finiti, allora l'algoritmo termina. Se esistono partizioni marcate come ambigue oppure esistono dataset non ancora esaminati, allora il buffer viene ricaricato. I nuovi dati vanno a rimpiazzare nel buffer quelli delle partizioni 'frozen' (congelate). In sostanza vengono caricati o dati di partizioni ambigue oppure dati mai esaminati. E' possibile durante l'elaborazione conteggiare le statistiche dei punti delle partizioni ambigue, congelate etc.Il caricamento continua fino a che non si verifica una delle seguenti condizioni:

1. il buffer è pieno2. i dati sono finiti

21

22 2

,12( exp )

expobserved ected

ected αχ χ−= ≥

3. un certo numero di dati sono stati letti, il buffer non è pieno e non vi sono molti dati

La terza condizione sembra strana ma serve per evitare un eccessivo Reloading; difatti il buffer è molto grande ed essere pieno con molti record marcati da cancellare, e ciò richiederebbe un tempo di attesa grande per poi riempirlo con i dati di una partizione ambigua. Per evitare questo, come compromesso, il processo di reloading si intende terminato quando si sono letti una quantità di dati almeno uguale alla lunghezza del buffer stesso.Una volta completato il reload del buffer si ritorna allo step 2.

Ulteriori caratteristiche di differenza tra O-Cluster e OptigridOpti-grid ha due parametri di soglia come visto precedentemente, che gli servono per individuare un buon piano di taglio:

1. il livello del rumore2. la massima densità di splitting

In OptiGrid i picchi degli istogrammi devono essere al di sopra del livello del rumore, mentre gli istogrammi dell'avvallemento devono avere densità più bassa della massima densità di splitting e normalmente la massima densità di splitting dovrebbe essere settata al di sopra della soglia del livello del rumore. La ricerca di tali valori ottimali è una fase critica da un punto di vista prestazionale per OptiGrid.

O-Cluster col test χ2 elimina la necessità dei poarametri di soglia rendendo più facile e meno critica la ricerca del taglio ottimale. Successivi studi su O-Cluster hanno portato anche alla introduzione del parametro sensitività ρ. Questo parametro ha quasi lo stesso significato del livello di rumore di OptiGrid. Lo scopo del parametro, difatti, è di eliminare arbitrari piccoli cluster, settando un conteggio minimo dei picchi degli istogrammi di O-Cluster.Sebbene OptiGrid tenta di far il miglior splitting possibile, può arrivare all'oversplitting. Per come è stato pensato inizialmente, OptiGrid tende a partizionare contemporaneamente con diversi piano di taglio. I cluster ottenuti con pochi punti vanno rimossi successivamente.OptiGrid lavora, inoltre, con istogrammi che sotto-arrotondano la densità di distribuzione, per cui sia questo fatto che il meccanismo delle soglie può portare a tagliare attraverso clusters. Questo fatto anche se non è un vero problema per OptiGrid, richiede diverse elaborazioni. Lo splitting, invece, di

22

O-cluster avviene con un clustering ad albero binario ed è validato statisticamente.

Benchmark di O-ClusterSu O-Cluster è stato eseguito (vedi [3]) un particolare benchmark, con un dataset bidimensionale DS3. I risultati sono da considerarsi molto validi per scalabilità, prestazioni, efficacia ed efficienza. Inoltre occorre tener conto che è basato su Oracle e, quindi, di un prodotto molto noto e supportato.

O-Cluster Data Mining Oracle 11gCome precedentemente visto O-Cluster crea un modello di clustering gerarchico e grid-based, con partizioni parallele agli assi (quindi ortogonali) rispetto allo spazio di input. Inoltre ripetutamente riesegue il lavoro fino a che la struttura gerarchica ottenuta riesce a tassellare tutto lo spazio di input. I cluster sono descritti da intervalli lungo gli assi degli attributi e corrispondenti ai centroidi e agli istogrammi.L'algoritmo k-means tassella lo spazio di input in n cluster (con n deciso dall'utente) anche quando il cluster non esiste, mentre ciò è evitato da O-Cluster. O-Cluster effettua piani di taglio nelle aree a bassa densità e si basa sul riconoscimento di picchi e valli negli istogrammi; per cui se un'area ha una densità uniforme, O-Cluster non la partiziona.

I cluster scoperti da O-Cluster sono usati (vedi [4]) per generare un modello bayesiano di probabilità che viene poi utilizzato durante l'assegnazione di punteggi (modello a pagamento) ai cluster.

Il modello di probabilità generato è un modello misto in cui sono rappresentati i componenti con un prodotto di distribuzioni normali indipendenti per gli attributi numerici e distribuzioni multinomiale per gli attributi categorici. Esso utilizza una forma particolare di binning equi-width che calcola il numero di cassonetti per attributo automaticamente.

Le colonne numeriche con tutti i valori null o un singolo valore vengono rimossi.

Va studiato l' "Oracle Data Mining Application Developer's Guide" per informazioni sulle colonne nidificati e dati mancanti.

O-Cluster non necessariamente utilizza tutti i dati di input quando costruisce un modello. Esso legge i dati in lotti (la

23

dimensione del lotto di default è 50000). O-Cluster legge un altro batch se ritiene, sulla base di test statistici, perchè potrebbero esistere gruppi che non ha ancora individuato. Poiché O-Cluster può smettere di costruire il modello prima di leggere tutti i dati, è altamente raccomandato che i dati siano randomizzati.

E' raccomandato che gli attributi binari siano dichiarati come categorici.

L'utilizzo di trasformazione equi-width binning Oracle Data Mining, con stima automatica del numero di cassonetti è altamente raccomandato.

La presenza di valori anomali possono influenzare notevolmente la algoritmi di clustering.

Utilizzare un ritaglio di trasformazione prima del binning o di una normalizzazione. Valori anomali con binning equi-larghezza possono impedire O-Cluster di rilevare cluster. Come risultato, l'intera popolazione sembra si inserisce in un singolo cluster.

Social Network Analysis e il clusteringNella SNA, il clustering è un punto teorico di base per poter descrivere le reti sottostanti che si analizzano. In questi casi la velocità di elaborazione ha una grande importanza.Esempi didattici sono alcuni tools disponibili anche per Windows come "Cluster" associato ad un Java Tree Viewer [5], che fornisce una visione didattica delle tecniche di clustering, ad esempio quelle gerarchiche, k-means, Self-Organizing Maps di Tamayo, Principal Component Analysis; mentre UCINET [6] è adatto allo studio delle Social Network Analysis.

Riferimenti[1]http://www.smaponline.net/tags/optics-clustering-java-implementation.html[2]http://download.oracle.com/docs/cd/E11882_01/datamine.112/e12216/clustering.htm[3] O-cluster: Scalable Clustering of Large High Dimensional Data Sets - Boriana L. Milenova (Oracle), Marcos M. Campos (Oracle)

[4] O-Cluster Data Mining – Oracle 11ghttp://www.comp.dit.ie/btierney/oracle11gdoc/datamine.111/b28129/algo_oc.htmhttp://www.oracle.com/technetwork/database/options/odm/index.html

24

Tools free per studio didattico su Windowsper didattica sul Clustering: [5]Cluster e Java Tree Viewer

per una didattica sul Social Network Analysis:[6]UCINET [7]PAJEK

-°-

Il presente documento è stato realizzato con OpenOffice.org

-°-

25