1. PANORAMICA SUL CLUSTERING 1.1 Descrizione generale

1. PANORAMICA SUL CLUSTERING

1.1 Descrizione

generale

Il clustering è un metodo attraverso il quale grandi insiemi di dati vengono partizionati in gruppi più piccoli, detti cluster (lett. “grappolo”). Eseguire il clustering di un dataset assegnato, contenente oggetti descritti da un insieme di attributi, significa individuare gruppi di oggetti tali che:

– elementi appartenenti ad un cluster siano più simili l’uno all’altro (alta similarità intra-classe);

– elementi appartenenti a cluster diversi siano meno simili l’uno all’altro (bassa similarità inter-classe).

La discriminazione degli oggetti avviene valutandone gli attributi in base ad una prestabilita misura di similarità.

Figura 1

Il clustering è una classificazione non supervisionata, per la quale non ci sono classi predefinite. Esso viene generalmente utilizzato come mezzo per verificare ipotesi intuitive relativamente a distribuzioni di dati, o come passo di pre-processing in altri algoritmi di data mining. In generale si utilizza la cluster detection quando si sospetta che nei dati da analizzare esistano raggruppamenti naturali rappresentativi di classi (per esempio clienti o prodotti con

2

I settori applicativi nei quali si fa uso di metodi di clustering sono numerosi e molto diversi fra loro. Per esempio, nell’ambito del marketing si ricercano insiemi di clienti simili nelle basi di dati, per favorire lo sviluppo di programmi mirati; in urbanistica è di interesse l’identificazione di gruppi di edifici in base a tipo, valore e locazione geografica; nello studio dei fenomeni tellurici si mira all’individuazione delle fratture continentali a partire dagli epicentri rilevati dei terremoti.

La variabilità dei campi di applicazione e le differenti caratteristiche dei problemi specifici da affrontare comportano, per la scelta di un metodo di clustering appropriato, l’utilizzo di uno o più criteri discriminativi. Tra i requisiti generalmente richiesti in problemi di data mining figurano

– scalabilità,

– possibilità di trattare differenti tipi di attributi, – individuazione di cluster con forma arbitraria,

– necessità di minima conoscenza del dominio per determinare i parametri di input, – robustezza rispetto al rumore e agli outlier,

– insensibilità all’ordine dei record in input, – capacità di operare su dati ad alta dimensionalità, – incorporazione di vincoli specificati dall’utente, – interpretabilità ed usabilità dei risultati.

1.2 Definizioni e concetti rilevanti

Trattandosi di un insieme di metodi e tecniche molto ampio ed in continua espansione, il clustering non è associato ad una esaustiva nomenclatura cui fare sempre riferimento. È comunque possibile individuare una serie di elementi fondamentali, che costituiscono una base formale valida indipendentemente dalla particolare metodologia.

1.2.1 Strutture per la rappresentazione degli oggetti

Generalmente per descrivere e memorizzare in forma compatta gli oggetti da classificare si ricorre all’utilizzo di matrici, riconducibili a due categorie principali. La prima, detta

object-by-variable, realizza mediante la Matrice dei Dati una tabella relazionale che rappresenta n oggetti

con p variabili (attributi o misure). La seconda, detta object-by-object, mette in relazione coppie di oggetti mediante la Matrice di Dissimilarità:

          = np n p x x x x M      1 1 11

1 (Matrice dei Dati)

( )

( ) ( )

( ) ( ) ( )

               = 0 3 , 2 , 1 , 0 2 , 3 1 , 3 0 1 , 2 0 2      n d n d n d d d d M (Matrice di Dissimilarità)

( )

i j i j d , ≥0 ∀ , (Dissimilarità)

4 1.2.2 Tipi di variabili

1.2.2.1 Variabili Continue

Questo tipo di variabili rende necessaria una standardizzazione dei dati per evitare la dipendenza del valore dalla scelta dell’unità di misura. Per il calcolo della misura standardizzata, detta z-score, è conveniente fare uso della deviazione assoluta media:

(

k k k k nk k

)

k x m x m x m

n

s = 1 − + 2 − ++ −

1

(deviazione assoluta media)

k k ik ik s m x z = − (z-score)

(

k k nk

)

k x x x n m = 1 + 2 ++ 1

L’uso della deviazione assoluta media offre, in presenza di outlier, maggior robustezza rispetto all’uso della deviazione standard. Infatti nel calcolo della deviazione assoluta media gli scostamenti non vengono elevati al quadrato, quindi gli z-score degli outlier non decrescono e questi ultimi rimangono ancora ben individuabili.

Per misurare la similarità tra due oggetti i cui attributi sono variabili continue, viene utilizzata normalmente una funzione-distanza. Si riportano qui di seguito alcune delle distanze maggiormente utilizzate:

– Distanza Euclidea

È probabilmente il tipo di distanza più comunemente scelto. Si tratta della distanza geometrica in uno spazio multi-dimensionale:

( )

_∑

(

)

= − = p k kj ki x x j i d 1 2 , . Proprietà: ○ d

( )

i,j ≥0 ○ d

( )

i,i ₌0 ○ d

( ) ( )

i,j =d j,i ○ d

( ) ( ) ( )

i,j ≤d i,k +d k,j

– Distanza di Manhattan

Si tratta della somma delle differenze fra le dimensioni. In molti casi questa distanza produce risultati simili alla distanza Euclidea. Si noti comunque che con questa distanza l’effetto di singole grandi differenze (outlier) è attenuato, dal momento che esse non sono quadratiche:

( )

i j xi xj xi xj xip xjp

d , = 1− 1 + 2 − 2 ++ − .

Le proprietà valide per la distanza Euclidea rimangono valide anche per questa misura.

– Distanza di Minkowski

Questa distanza permette di incrementare o decrementare il peso assegnato a dimensioni lungo le quali gli oggetti risultano molto diversi:

( )

(

q

)

q jp ip q j i q j i x x x x x x j i d , = ₁ − ₁ + ₂ − ₂ ++ − 1 . – Distanza pesata

Se è nota in qualche modo l’importanza relativa che dovrebbe essere assegnata ad ogni variabile, si possono attribuire pesi alle variabili, ottenendo

( )

(

)

2

(

)

2 1 1 1 ,j w x_i x_j w_p x_ip x_jp i d = − ++ − . 1.2.2.2 Variabili Binarie

Hanno solo due stati possibili: “0” oppure “1”. Una variabile binaria si dice simmetrica se i suoi stati sono equivalenti, cioè se non ci sono preferenze su quale risultato debba essere codificato con lo stato “1”; la similarità basata su variabili binarie simmetriche è detta

similarità invariante. Se invece gli stati della variabile non sono equivalenti, come nel caso di

6

In presenza di dati binari, per valutare la similarità si può ricorrere ad una tabella di dipendenza, come mostrato in Tabella 1

ogg. j ogg. i 1 0 ∑ 1 a b a+b 0 c d c+d ∑ a+c b+d p Tabella 1 dove ( )

_∑

( )

_∑

( )

_∑

( )

∑

= = = = = = = = p k k p k k p k k p k k _{b c d} a 1 00 1 01 1 10 1 11 , , , _{γ γ γ} γ ( )

(

)

( )

   = = altrimenti r q x x se _{ik jk} k qr ₀ , , 1 γ

Il grado di similarità viene poi calcolato mediante un coefficiente di corrispondenza:

( )

i j _{a b}b _cc _d d + + + + =

, (Coeff. di Corrisp. Semplice)

( )

i j _ab_bc _c d + + + = , (Coeff. di Jaccard)

Il coefficiente di corrispondenza semplice è invariante per variabili binarie simmetriche, il coefficiente di Jaccard è non invariante per variabili binarie asimmetriche.

Esempio

Sia assegnato il dataset mostrato in Tabella 2, i cui oggetti sono record provenienti da una cartella clinica. L’attributo “Sesso” è simmetrico, gli altri attributi sono asimmetrici; si è scelto di associare i valori “Y” e “P” allo stato “1”, il valore “N” allo stato “0”:

Nome Sesso Febbre Tosse Test-1 Test-2 Test-3 Test-4 Marco M Y N P N N N

Rita F Y N P N P N

Francesco M Y P N N N N

Il calcolo dei Coefficienti di Jaccard risulta:

(

)

0.33 1 0 2 1 0 , = + + + = Rita Marco d

(

)

0.67 1 1 1 1 1 , = + + + = Francesco Marco d

(

)

0.75 2 1 1 2 1 , = + + + = Rita Francesco d 1.2.2.3 Variabili Nominali

Si tratta di variabili binarie generalizzate, in quanto possono assumere più di due stati, per esempio {“rosso”, “giallo”, “blu”, “verde”}. Per valutare la similarità si può calcolare la

corrispondenza semplice

( )

i j p _pm

d , = − ,

dove m è il numero di corrispondenze e p è il numero di variabili.

Alternativamente è possibile creare una nuova variabile binaria per ciascuno degli M stati nominali, mappando quindi il problema in uno spazio binario con maggior dimensionalità.

1.2.2.4 Variabili Ordinali

Per questa tipologia di variabili è importante l’ordinamento dei valori possibili, per esempio {“Oro”, “Argento”, “Bronzo”}. Per la valutazione di similarità le variabili ordinali sono spesso trattate come continue, applicando una procedura del tipo seguente:

1. gli stati ordinati definiscono il ranking _{1 }, ,M_k;

2. si sostituiscono le x (nominali) con i rispettivi rank _ik r_ik∈

{

_{1 }, ,M_k

}

(numerici); 3. si mappa il range di ogni variabile in

[ ]

0 sostituendo ,1 r con _ik

1 1 − − = k ik ik M r z ;

8

1.2.2.5 Variabili Miste

Può capitare che un database contenga molti dei tipi di variabili fin qui esaminati, o addirittura tutti. In tal caso è possibile utilizzare una formula pesata per combinare i loro effetti:

( )

( ) ( ) ( )

∑

∑

= = = _p k k ij p k k ij k ij d j i d 1 1 , δ δ , dove     ∧ = = = altrimenti 1 asimm. binaria è 0 se 0 manca se 0 k x x x jk ik ik ij δ     = = altrimenti 1 se nominali, e binarie variabili per 0 ordinali e continue variabili per normalizz. assoluta dist. jk ik ij x x d

1.3 Principali metodi di clustering

Dal punto di vista dell’approccio al problema, le tecniche di clustering possono essere suddivise in alcune grandi categorie:

– Algoritmi di Partizionamento: eseguono la costruzione di un numero variabile di cluster, per poi valutarli e selezionare quelli definitivi;

– Algoritmi Gerarchici: creano una decomposizione gerarchica del dataset;

– Metodi Density-based: basandosi su connettività e funzioni-densità, fanno “crescere” i cluster finché la densità di punti nel vicinato non supera un prefissato limite; sono in grado di trovare cluster di forma arbitraria;

– Metodi Grid-based: sono basati su una struttura a livelli multipli di granularità, che forma una griglia sulla quale vengono eseguite tutte le operazioni; le prestazioni dipendono solo dal numero di celle della griglia;

– Metodi Model-based: ipotizzano un modello per ciascun cluster cercando il miglior adattamento di quel modello con ciascun altro.

Nei paragrafi seguenti saranno presi in considerazione alcuni esempi di metodi appartenenti alle prime due categorie.

1.3.1 Algoritmi di Partizionamento

Prevedono la costruzione di k cluster a partire da un database D di n oggetti. Il parametro k è un input del problema e il risultato è un partizionamento che ottimizza il criterio di ripartizione scelto.

Due noti metodi euristici sono il “K-Means” e il “K-Medoids”. Essi sono rilevanti da esaminare perché spesso costituiscono la base per varianti più o meno sofisticate.

1.3.1.1 Il metodo K-Means

Sia n il numero di oggetti e k il numero desiderato di cluster. L’algoritmo prevede quattro step:

10

3. si assegna ogni oggetto al cluster con il seme ad esso più vicino;

4. si riprende dallo step 2, arrestandosi quando non è più possibile effettuare nuovi assegnamenti.

Dal punto di vista dell’efficienza, la complessità è O

( )

tkn , dove t è il numero di iterazioni. Normalmente si ha k,t<<n.

L’algoritmo spesso termina in un ottimo locale. L’ottimo globale può essere trovato usando tecniche di compattamento deterministico ed algoritmi genetici.

La limitazione principale del metodo K-Means consiste nel fatto che per la sua applicazione è necessario definire la media per gli oggetti da classificare. Questo comporta sensibilità al rumore e anche agli outlier, in quanto un piccolo numero di essi può influenzare notevolmente il valor medio.

Da notare infine che il metodo non è affidabile per trovare cluster di forma non convessa.

Esempio

(a) (b)

(d) (c)

Esiste una proposta di framework per rendere scalabile il K-Means (Figura 3). L’idea è di compiere iterazioni su campioni del database, combinando ad ogni passo l’informazione ottenuta dai campioni precedenti con quella fornita dal campione attuale.

Data RAM Buffer Model under consideration Data Compression Discarded Set (DS) Compressed Set (CS) Retained Set (RS) Termination criteria Updated Models Secondary Clustering Init ial Poi n ts Cluster Data +

Model Sufficient Stats

Fi

nal Solut

ion

s

Figura 3

La metodologia proposta prevede tre passi:

1. estrarre il prossimo campione disponibile dal database; 2. aggiornare il modello attuale;

3. sulla base del modello aggiornato, classificare i campioni come o RS - da conservare nel buffer;

o DS - da scartare, previo aggiornamento delle sufficient statistics;

12

La compressione dei dati viene a sua volta eseguita in due fasi: – Compressione primaria

Mira a scartare quei campioni che non cambierebbero l’assegnamento ai cluster in successive iterazioni; questo obiettivo può essere raggiunto efficientemente in due modi alternativi:

o si definisce un raggio-soglia attorno al centroide del cluster, procedendo poi a scartare tutti gli oggetti entro il raggio;

o si definiscono intervalli di confidenza (CI) per ogni centroide; per ciascun oggetto si muove il centroide del cluster corrispondente il più lontano possibile (entro il proprio CI) e quello degli altri cluster il più vicino possibile; questa perturbazione crea la situazione peggiore per l’oggetto considerato; se dopo la perturbazione l’oggetto non risulta essere più vicino ad altri cluster, può essere scartato;

– Compressione secondaria

Mira a comprimere campioni che, insieme, cambiano sempre l’assegnamento ai cluster; una volta identificati tali oggetti, si forma con essi un sub-cluster del quale si memorizzano le sufficient statistics. Gli oggetti in questione vengono poi eliminati. Agli aggiornamenti futuri dei centroidi dei cluster contribuiranno le sufficient statistics del sub-cluster.

1.3.1.2 Il metodo K-Medoids

Sua caratteristica principale è la rappresentazione del cluster per mezzo di uno degli oggetti che gli appartengono, piuttosto che per mezzo di una media di essi. Ognuno degli oggetti rappresentativi dei cluster è detto medoid.

Tra gli algoritmi che sfruttano questo approccio sono rilevanti “PAM”, “CLARA” e “CLARANS”, tre varianti che si ritiene interessante esaminare.

– PAM (Partitioning Around Medoids, 1987)

Comincia da un set iniziale di medoid e cerca di minimizzare la somma delle distanze tra gli oggetti del cluster:

1. si selezionano arbitrariamente k medoid;

2. per ciascuna coppia di oggetti

( )

x,y , rispettivamente medoid e non-medoid, si calcola il costo totale di scambio

∑

= j jxy xy C TC ,

dove a secondo membro compare la sommatoria dei costi di scambio rispetto agli oggetti del cluster (Figura 4);

3. si individua la coppia di oggetti cui corrisponde il costo minimo, sia

( )

h, ; i

4. se TChi <0, si rimpiazza l’oggetto i con l’oggetto h;

5. si assegna ciascun oggetto non-medoid al medoid più similare;

6. si ripetono i passi da 2 a 5 finché non si verificano più ulteriori cambiamenti. L’algoritmo lavora efficacemente su piccoli dataset, ma non scala.

t i j h C_jih = d(j,h) - d(j,i) t j h i C_jih = 0 Figura 4

14

– CLARA (Clustering LARge Applications - Kaufmann e Rousseeuw, 1990)

Estrae un campione del dataset ed applica PAM sul campione per trovare i medoid. Se il campione è rappresentativo, i medoid trovati dovrebbero approssimare quelli dell’intero dataset.

Per migliorare l’approssimazione, generalmente si estraggono più campioni e si restituisce come output il miglior clustering, la cui accuratezza è misurata dalla dissimilarità media di tutti gli oggetti.

CLARA tratta efficientemente dataset più grandi rispetto a PAM, anche se l’efficienza dipende dalla dimensione del campione. Inoltre è da sottolineare l’importanza dell’estrazione di un campione rappresentativo: un clustering accurato basato sul campione non necessariamente rappresenterà un buon clustering dell’intero dataset se il campione è “influenzato”.

– CLARANS (“Randomized” CLARA - Ng e Han, 1994)

In questo algoritmo il processo di clustering può essere presentato come un grafo di ricerca, dove ogni nodo è una potenziale soluzione, cioè un set di k medoid. Il problema di ottenere un buon clustering corrisponde a quello di cercare il minimo sul grafo.

Operativamente:

o due nodi sono considerati vicini se i loro set differiscono per un solo medoid; o a ciascun nodo può essere assegnato un costo, definito come la dissimilarità

totale fra ogni oggetto ed il medoid del rispettivo cluster;

o ad ogni passo si cercano tutti i vicini del nodo corrente; il vicino che corrisponde al più profondo calo del costo viene scelto come prossima soluzione.

Dal punto di vista dell’efficienza si ha che per grandi valori di n e k l’esame dei

(

n k

)

k − vicini del nodo è costoso, per cui si adotta una variante in cui ad ogni passo si estraggono campioni dei vicini da esaminare. Rispetto a CLARA, che estrae un campione dei nodi solo all’inizio, CLARANS ha il vantaggio di non restringere la ricerca ad un’area limitata.

L’algoritmo affronta il problema degli ottimi locali eseguendo iterazioni multiple: se viene trovato un ottimo, si riparte comunque da un altro nodo selezionato

casualmente, in cerca di un nuovo ottimo. Il numero di ottimi locali da cercare è un parametro di input.

CLARANS è più efficiente e scalabile sia del PAM che del CLARA, inoltre restituisce cluster di qualità migliore.

1.3.2 Algoritmi Gerarchici

I metodi di questa classe raggruppano i dati in un albero di cluster e lavorano basandosi sulla Matrice di Dissimilarità. Non richiedono il numero di cluster desiderato come input, ma necessitano di una condizione di terminazione, per esempio una distanza-soglia. Ci sono due tipi di clustering gerarchico (Figura 5):

– ad agglomerazione (strategia bottom-up); – a divisione (strategia top-down).

a b c d e cde ab de abcde Ad agglomerazione

Passo 0 Passo 1 Passo 2 Passo 3 Passo 4

A divisione Passo 0 Passo 1 Passo 2 Passo 3 Passo 4

16

Per scegliere ad ogni passo la coppia di cluster da unire o dividere, si valuta il grado di vicinanza tra cluster in base ad una regola di collegamento:

– Link Singolo (vicino più prossimo)

La distanza tra due cluster è determinata dalla distanza minima tra tutte le coppie di oggetti appartenenti ai due cluster considerati; l’applicazione di questa regola porta ad ottenere cluster tendenti a rappresentare catene di oggetti;

– Link Completo (vicino più remoto)

La distanza tra due cluster è determinata dalla distanza massima tra tutte le coppie di oggetti appartenenti ai due cluster considerati; questo metodo generalmente conduce a buoni risultati nei casi in cui gli oggetti formano blocchi distinti, risulta invece inappropriato quando i cluster tendono ad essere del tipo concatenato o ad assumere forme allungate;

– Media di Coppia

La distanza tra due cluster è calcolata come distanza media tra tutte le coppie di oggetti appartenenti ai due cluster considerati; questo metodo è anch’esso molto efficiente quando gli oggetti formano naturalmente blocchi distinti e si comporta comunque bene con cluster del tipo concatenato;

– Centroide di Coppia

La distanza tra due cluster è determinata dalla distanza tra i rispettivi centroidi.

Due noti algoritmi gerarchici rilevanti da illustrare sono quelli noti rispettivamente come “AGNES” e “DIANA”.

1.3.2.1 AGNES (Agglomerative Nesting - Kaufmann e Rousseeuw, 1990)

Si basa sulla regola Link Singolo, combinando ripetutamente i nodi che hanno la minore dissimilarità (Figura 6). Utilizza la Distanza Euclidea.

Figura 6

Il dendogramma in Figura 7 mostra come i cluster siano combinati gerarchicamente. Il risultato, da un punto di vista grafico, si ottiene tagliando il dendogramma al livello desiderato: ciascun componente connesso forma un cluster.

Obj-1 Obj-2 Obj-3 Obj-4 Obj-5 Obj-6 Obj-7 Obj-8 Obj-9 Obj-10 Obj-11 Obj-12 Obj-13 Obj-14

18

1.3.2.2 DIANA (DIvisive ANAlysis- Kaufmann e Rousseeuw, 1990)

Lavora in ordine inverso rispetto ad AGNES. In DIANA tutti gli oggetti vengono usati per formare un cluster iniziale, che poi viene diviso in accordo alla regola Link Completo utilizzando generalmente la distanza Euclidea. Al limite, ogni oggetto può formare un cluster composto solo da se stesso (Figura 8).

Figura 8

I metodi gerarchici, in particolare quelli agglomerativi, risultano limitati da due punti di debolezza principali:

– non scalano bene, in quanto la complessità è almeno _O

( )

_n2 _{, con n numero}

complessivo di oggetti;

– non è possibile tornare indietro una volta eseguita un’iterazione.

Per tentare di abbattere queste limitazioni, sono stati recentemente proposti algoritmi che integrano metodi gerarchici con clustering basato sulla distanza. Si tratta di “BIRCH”, “CURE” e “CHAMELEON”.

1.3.3 BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies - Zhang, Ramakrishnan e Livny, SIGMOD 1996)

Introduce due nuovi concetti, detti Clustering Feature e Clustering Feature Tree, per comprimere la rappresentazione dei cluster utilizzando strutture dati di riepilogo.

1.3.3.1 Clustering Feature

Si tratta di una tripla che contiene informazione relativa a sub-cluster. In essa sono registrate in forma compatta misurazioni fondamentali per il calcolo dei cluster (Figura 9).

(

N LS SS

)

CF = , , (Clustering Feature)

∑

= = N i i X LS 1 (Linear Sum)

∑

= = N i i X SS 1 2 _{(Square Sum)} N: numero di oggetti CF = ( 5, (16,30), (54,190) ) P1 = (3,4) P2 = (2,6) P3 = (4,5) P4 = (4,7) P5 = (3,8) Figura 9 1.3.3.2 CF-Tree

Si tratta di un albero che contiene le Clustering Feature per clustering gerarchico. Nei nodi non-foglia sono memorizzate le somme delle CF dei loro nodi figli.

1.3.3.3 L’algoritmo

Costruisce in maniera incrementale un CF-Tree per l’esecuzione di clustering multifase. – Fase 1

Compie una passata sul database per costruire un CF-Tree iniziale in memoria. Per ogni punto, il CF-Tree viene navigato per trovare il cluster più vicino (nodo-foglia).

20 – Fase 2

Utilizza un algoritmo arbitrario per eseguire un clustering dei nodi-foglia del CF-Tree realizzato.

BIRCH scala linearmente con il numero di oggetti. Il clustering risultante dalla prima passata sul dataset è migliorabile con passate supplementari.

BIRCH è particolarmente indicato per trovare cluster sferici. La sua limitazione principale è la sensibilità all’ordine dei record nel dataset.

1.3.4 CURE (Clustering Using REpresentatives - Guha, Rastogi e Shim, 1998) Molti algoritmi considerano solo un punto come rappresentativo di un cluster. Questo comporta un indebolimento delle prestazioni in presenza di outlier, oppure la limitazione a trovare solo cluster con forma convessa. CURE propone l’uso di un numero s di punti rappresentativi per valutare la distanza tra cluster.

L’algoritmo, illustrato in Figura 10, è il seguente: – si sceglie casualmente un numero s di campioni;

– si suddividono i campioni in un numero p di partizioni;

– si esegue il clustering parziale delle partizioni, ottenendo pqs cluster;

– si combinano gerarchicamente i cluster aventi le coppie di punti rappresentativi più vicini;

– si modifica la posizione dei punti rappresentativi di ogni cluster, riconducendoli verso il centro (effetto gravità).

Gli outlier vengono eliminati sia grazie al campionamento random, sia in seguito all’eliminazione dei cluster che crescono troppo lentamente durante la fase gerarchica.

22

1.3.5 CHAMELEON (G. Karypis, E.H. Han e V. Kumar, 1999)

Esegue clustering gerarchico utilizzando modellazione dinamica. È stato sviluppato con l’obiettivo di scavalcare le limitazioni di molti algoritmi, tra le quali:

– adozione di un modello statico per i dati;

– crollo delle prestazioni in caso di applicazione a dati raggruppati in cluster di forme differenti.

CHAMELEON usa una rappresentazione a grafo sparso, basata sull’approccio del vicinato-k (k-nearest neighbor): esiste un arco tra due nodi se uno di essi risulta appartenente al vicinato-k dell’altro. Un arco rappresenta la similarità tra due oggetti.

L’esempio di Figura 11 mostra (a) i dati originali, (b) il grafo del vicinato-1, (c) il grafo del vicinato-2, (d) il grafo del vicinato-3.

Figura 11

Dati due cluster C e _i C , si ha: j

– Interconnettività Assoluta EC

(

C_i,C_j

)

: somma dei pesi degli archi che collegano i due cluster;

– Interconnettività Interna EC

( )

C_i : somma dei pesi degli archi che attraversano il taglio minimo che divide il cluster in due parti approssimativamente uguali;

– Interconnettività Relativa RI

(

Ci,Cj

)

:

(

)

_{( )}

(

)

_{( )}

2 , , j i j i j i C EC C EC C C EC C C RI + = ;

– Vicinanza Assoluta SEC

(

C_i,C_j

)

: peso medio degli archi che connettono vertici del cluster C a quelli del cluster _i C ; j

– Vicinanza Interna SEC

( )

C_i : peso medio degli archi che attraversano il taglio minimo che divide il cluster in due parti approssimativamente uguali;

– Vicinanza Relativa RC

(

Ci,Cj

)

:

(

)

(

)

( )

( )

j j i j i j i i j i j i C SEC C C C C SEC C C C C C SEC C C RC + + + = , , .

Due cluster C e _i C sono fusi insieme solo se sono elevate l’Interconnettività Relativa e j

la Vicinanza Relativa fra di essi. CHAMELEON prevede due fasi:

1. uso di un algoritmo per la costruzione del grafo: esegue il clustering degli oggetti producendo un gran numero di sub-cluster relativamente piccoli;

2. uso di un algoritmo di clustering gerarchico agglomerativo: trova i cluster naturali combinando ripetutamente i sub-cluster precedentemente ottenuti.

È stato dimostrato che CHAMELEON è più potente di CURE nell’individuare cluster di alta qualità con forme arbitrarie. Comunque, il costo in termini di tempo per dati ad elevata dimensionalità può raggiungere _O

( )

_n2 _{nel caso peggiore.}