2. L’ALGORITMO ORCLUS - PRESENTAZIONE 2.1 Introduzione

2. L’ALGORITMO ORCLUS - PRESENTAZIONE

2.1 Introduzione

2.1.1 Problematiche legate alla multi-dimensionalità

L’elevata dimensionalità dei dati e le grandi dimensioni dei database creano grossi problemi nell’applicare algoritmi di clustering. Come illustrato nel Capitolo 1, gli algoritmi di partizionamento e quelli gerarchici sono qualitativamente efficienti ma nella pratica inapplicabili per grandi database, dal momento che le prestazioni variano con legge almeno quadratica con il numero di punti del database. Di conseguenza è spesso usato un campionamento random per ridurre la dimensione del dataset su cui applicare la tecnica. Il metodo BIRCH è uno dei più efficienti approcci per dati low-dimensional e richiede una sola passata sul database. L’utilizzo di CURE, attraverso l’applicazione di metodi robusti per misurare le distanze fra cluster, raggiunge qualità eccellente e può adattarsi bene a differenti forme di cluster. Recentemente è stata proposta un’interessante tecnica per il clustering high-dimensional, chiamata Optigrid, capace di trovare griglie di partizionamento ottime determinando il miglior iperpiano di partizionamento per ciascuna dimensione.

Malgrado l’evoluzione delle tecniche però, i dati high-dimensional continuano a rappresentare una sfida per i metodi di clustering. Molti algoritmi non lavorano efficientemente negli spazi ad alta dimensionalità a causa della inerente dispersione dei dati. Tradizionalmente questo problema è noto come dimensionality curse ed è la causa di un significativo sforzo dei ricercatori relativamente a versioni high-dimensional di problemi come il clustering e la similarità. Recenti risultati teorici hanno mostrato che, nello spazio high-dimensional, la distanza fra ogni coppia di punti è quasi la stessa per un’ampia varietà di distribuzioni di dati e funzioni-distanza. Una soluzione a questo problema è l’utilizzo della selezione delle caratteristiche per poter ridurre la dimensionalità della spazio, ma le correlazioni tra dimensioni sono spesso specifiche alla località dei dati. In altre parole, alcuni punti sono correlati in riferimento ad un certo insieme di caratteristiche ed altri rispetto a caratteristiche differenti, per cui non sempre può risultare fattibile decurtare troppe

Si può illustrare questo fenomeno con un esempio. In Figura 12 è rappresentato un insieme di punti a tre dimensioni, del quale sono riportate tre proiezioni e una vista prospettica. I due pattern esistenti nell’insieme sono evidenziati mediante l’attribuzione di colori diversi ai punti che ne fanno parte. Il pattern verde corrisponde ad un insieme di punti vicini tra loro sul piano X-Y; il pattern rosso corrisponde ad un insieme di punti vicini tra loro sul piano X-Z. Le tradizionali tecniche di selezione delle caratteristiche - che conservano poche dimensioni dal dataset originale - non funzionerebbero in questo caso, dato che ogni dimensione è rilevante per almeno uno dei due cluster. Nemmeno l’esecuzione di clustering nello spazio full-dimensional individuerebbe i due pattern, dal momento che ognuno di essi risulta fortemente disperso lungo una delle dimensioni.

Per semplici casi come quello appena esaminato, in cui cioè i pattern sono allineati lungo un particolare sistema di assi, sono stati elaborati e discussi metodi per scoprire cluster proiettati. Tuttavia nella pratica il problema potrebbe presentarsi ancora più complesso, come esemplificato in Figura 13. I due pattern dell’insieme, ancora una volta evidenziati con l’attribuzione di diversi colori ai punti, esistono in sottospazi arbitrariamente orientati rispetto alle dimensioni dello spazio di partenza. I punti del dataset sono cioè disposti lungo forme allungate ed arbitrariamente asimmetriche all’interno di spazi a dimensionalità inferiore, a causa di correlazioni parziali tra le caratteristiche. Di conseguenza la scelta di proiezioni parallele agli assi dello spazio di partenza non può efficacemente trovare i corrispondenti cluster.

2.1.2 L’approccio di ORCLUS

L’algoritmo ORCLUS (arbitrarily ORiented projected CLUSter generation - Aggarwal e Yu, 2002) si basa sui concetti di cluster proiettato generalizzato e di energia proiettata, utilizzando i quali cerca di scoprire cluster nascosti in sottospazi a dimensionalità minore di quella dello spazio dei dati. L’algoritmo richiede come input

– il numero k di cluster da trovare;

– la dimensionalità l dei sottospazi in cui ciascun cluster dovrà giacere; e restituisce come output

– una partizione {C₁,...,C_k,O} dei dati, tale che i punti in ciascun elemento della partizione eccetto l’ultimo formino un cluster;

– un insieme ε di vettori ortogonali per ciascun cluster _i C , tale che i punti di i C siano i ben raggruppati nel sottospazio definito da questi vettori.

I punti appartenenti all’ultimo elemento della partizione restituita sono gli outlier che, per definizione, non formano un gruppo compatto. I vettori per l’insieme O degli outlier possono essere l’insieme vuoto. Per ciascun cluster C la cardinalità del corrispondente _i

insieme ε è uguale al parametro _i l definito dall’utente.

2.1.2.1 Notazioni e definizioni rilevanti

– Si consideri un dataset di N record descritti da d caratteristiche, rappresentati da punti dello spazio d-dimensionale, detto spazio-origine:

(

y y

)

i N y_i = _i1,..., _id , 1≤ ≤ . – Si indichi con

{

e e_l

}

l≤d = ₁,..., , ε

un insieme di vettori ortonormali, definiti nello spazio-origine, che individuano un sottospazio.

– Si indichi con la notazione

( )

y1, y2

dist

la distanza Euclidea tra due punti.

– La proiezione di un punto y in un sottospazio ε è un punto l-dimensionale dato da

( ) (

y y e y el

)

P ,ε = ⋅ 1,, ⋅ ,

dove l’operatore “⋅ ” denota il prodotto scalare.

– La distanza proiettata fra due punti nel sottospazio ε è la distanza Euclidea tra le rispettive proiezioni in ε :

(

y₁,y₂,ε

)

dist

(

P

( ) ( )

y₁,ε ,P y₂,ε

)

Pdist = . – Si indichi con

{

x x x

}

t N C= ₁, ₂,_, _t , ≤

un insieme di punti che formano un cluster.

– Il centroide di un cluster sia dato dalla media aritmetica dei punti che gli appartengono:

( )

=

_∑

t_i= i t x C X ₁ .

– Si definisce energia proiettata del cluster Cnel sottospazio ε la distanza proiettata quadratica media fra i punti e il centroide del cluster:

( )

[

(

( )

)

]

2 1 , , 1 ,

∑

= = t i i X C x Pdist t C R ε ε .

La scelta del termine “energia” è dovuta al fatto che si tratta di una metrica invariante con la rotazione del sistema di assi e può essere espressa come somma delle energie nelle direzioni dei singoli assi. Si noti che l’energia proiettata di un cluster in un sottospazio è sempre inferiore a quella dello stesso cluster nello spazio-origine.

– Si definisce cluster proiettato generalizzato la coppia formata da un insieme ε di vettori e un insieme C di punti, tale che i punti di C hanno bassa energia proiettata nel sottospazio definito dai vettori di ε e risultano pertanto strettamente raggruppati in tale sottospazio.

2.1.2.2 Cluster Proiettati e Skew

ORCLUS mira a scoprire cluster con piccola energia proiettata in sottospazi arbitrariamente orientati di dimensione definita dall’utente. La dimensionalità dei sottospazi è la stessa, mentre a cluster diversi sono in generale associati sottospazi diversi. Considerando l’esempio di Figura 13, due sottospazi bi-dimensionali per i quali l’energia proiettata dei relativi cluster è probabilmente piccola sono i piani di proiezione individuabili dalle rappresentazioni prospettiche ruotate di Figura 14:

Figura 14

L’utilizzo di sottospazi di proiezione arbitrariamente orientati permette in definitiva di trovare cluster che risultano nascosti a causa di correlazioni parziali tra le dimensioni, per cui questa tecnica può anche essere considerata una ridefinizione significativa del problema del clustering per applicazioni di data mining multi-dimensionali. Spesso infatti i dati reali ad alta dimensionalità, pur essendo molto dispersi in tutti i possibili sottoinsiemi di attributi, contengono correlazioni interattributo che causano, negli spazi a minor dimensionalità, distribuzioni dei punti secondo forme arbitrarie dette skew. I cluster proiettati generalizzati sono fortemente connessi al problema di individuare skew nei dati, poiché gli insiemi

ortogonali di vettori che definiscono i sottospazi per i cluster proiettati forniscono informazioni sulla natura degli skew e conseguentemente sulle correlazioni tra i dati. Per esempio, il sottospazio in cui si verifica la massima dispersione della distribuzione dei punti è in generale il sottospazio complementare a quello in cui i punti sono più simili.

2.1.2.3 Cluster Proiettati e riduzione della dimensionalità

Il problema del clustering proiettato è molto più complesso di quello della riduzione di dimensionalità, perché deve anche tener conto della necessità di partizionare il dataset al meglio trovando le direzioni associate alla maggior similarità per ogni partizione.

La decomposizione ai valori singolari (SVD) è una tecnica utilizzata per ridurre la dimensionalità dei dati, poiché permette di selezionare le caratteristiche da escludere in modo da minimizzare la perdita di informazione. L’idea è di trasformare i dati in un nuovo sistema di coordinate in cui le correlazioni (del secondo ordine) tra i dati siano minimizzate. La trasformazione è compiuta attraverso i seguenti passi:

1. si costruisce la matrice di covarianza d×d per il dataset. In particolare, l’elemento di coordinate i, rappresenta la covarianza fra le dimensioni i e j . I valori sulla j

diagonale principale sono le varianze dei singoli attributi;

2. si trovano gli autovettori di questa matrice semidefinita positiva. Questi autovettori definiscono un sistema ortonormale per il quale sono rimosse le correlazioni del secondo ordine tra i dati. I corrispondenti autovalori denotano la diffusione lungo ciascuna delle dimensioni del nuovo sistema ortonormale. Gli autovettori per i quali il corrispondente autovalore è più grande possono essere scelti per formare il sottospazio in cui rappresentare i dati. Il risultato è una piccola perdita di informazione, poiché i dati non presentano varianza elevata lungo le altre dimensioni. Il problema della riduzione di dimensionalità riguarda la rimozione delle dimensioni nell’intero dataset in modo da minimizzare la perdita di informazione. Si scelgono pertanto gli autovettori associati alla massima diffusione, in modo da mantenere l’informazione necessaria a distinguere i punti l’uno dall’altro. L’obiettivo di ORCLUS è invece di trovare per ciascun cluster la miglior proiezione, quella cioè che consente di scoprire il più alto ammontare di similarità tra i punti del cluster. Si scelgono dunque le direzioni associate alla minima diffusione per ciascuno specifico cluster, in modo da conservare l’informazione di similarità tra i punti del cluster. Il sottospazio complementare al sottospazio di proiezione di

un cluster non è comunque inutile, poiché contiene la massima informazione che permette di distinguere i punti l’uno dall’altro all’interno dello specifico cluster.

2.1.2.4 Alcune proprietà della diagonalizzazione della matrice di covarianza

Sia M la matrice di covarianza per l’insieme di punti C. La matrice è semidefinita positiva e può essere espressa nella forma

T

P P M = ∆ ,

dove ∆ è una matrice diagonale a valori non negativi. Le colonne di P sono gli autovettori (ortonormali) di M . I valori λ ,...,1 λ_d sulla diagonale principale di ∆ sono gli autovalori di

M . Senza perdita di generalità si può assumere che valga

d λ λ

λ₁ ≤ ₂ ≤...≤ .

Gli autovettori ortonormali definiscono un nuovo sistema di assi e ∆ è la matrice di covarianza dell’insieme di punti quando si rappresentano in questo sistema. Dal momento che tutte le entrate non diagonali sono nulle, tutte le correlazioni del secondo ordine sono state rimosse. Questo significa anche che gli autovalori corrispondono alle varianze lungo ciascun asse del nuovo insieme. La traccia

∑

= d i 1λ i

è invariante sotto la trasformazione definita dall’autosistema P ed è uguale alla traccia della matrice di covarianza M . Quest’ultima è anche uguale all’energia del cluster C nello spazio-origine.

Evidentemente la selezione degli l ≤d autovettori associati agli autovalori più piccoli produce un sottospazio ε di autovettori nel quale la somma delle varianze lungo le l

dimensioni è molto bassa. L’operazione corrisponde quindi a proiettare l’energia del cluster

C nel sottospazio ε . In conclusione, la diagonalizzazione della matrice di covarianza fornisce informazioni sul sottospazio di proiezione di un cluster che ne minimizza la corrispondente energia.

2.2 Descrizione

dell’algoritmo

In ORCLUS si sfruttano contemporaneamente operazioni caratteristiche dei metodi gerarchici e dei metodi di partizionamento. Dal dataset D si sceglie inizialmente un piccolo numero k di punti rappresentativi, detti semi, che vengono partizionati in un set di cluster; 0 sui cluster si applica poi una variante del merging gerarchico, che usa informazione proveniente dall’intero dataset. Così facendo, le decisioni di merging risultano più robuste e non si verificano perdite di accuratezza significative.

Ad ogni stadio dell’algoritmo, sono associati a ciascun seme s : _i

– il cluster C (current cluster),_i

insieme di punti del dataset che sono più vicini al seme s in un certo sottospazio _i ε i associato a C . Si assume che il numero di current cluster sia indicato da i k ;c

– il sottospazio ε (current subspace), i

sottospazio in cui i punti di C sono ben raggruppati. La dimensionalità _i l di _c ε è _i almeno uguale alla dimensionalità l definita dall’utente. Inizialmente l è uguale alla _c

dimensionalità totale e il suo valore è ridotto gradualmente fino alla dimensionalità di input l. L’idea dietro questa graduale riduzione è che durante le iterazioni iniziali i cluster non corrispondono molto bene ai naturali cluster a minor dimensionalità, così si mantiene un più largo sottospazio per evitare perdita di informazione. Nelle successive iterazioni i cluster vengono raffinati e quindi possono essere estratti sottospazi di dimensionalità inferiore. L’importante è eseguire questo processo in modo graduale, così che l’algoritmo possa acquisire sufficiente informazione per eliminare via via i sottospazi più rumorosi.

Durante ogni iterazione dell’algoritmo si applica una sequenza di operazioni di merging per ridurre il numero di current cluster, secondo un fattore α <1. Contestualmente si riduce anche la dimensionalità dei current cluster secondo un fattore β <1. L’importanza del suddividere il processo di merging in diverse iterazioni è che ciascuna di esse corrisponde ad una certa dimensionalità del sottospazio in cui i cluster sono individuati. Le prime iterazioni avvengono in corrispondenza di una più alta dimensionalità e ciascuna iterazione successiva

valori di α e β devono essere relativi in qualche modo alla riduzione da k a 0 k cluster, che avviene nello stesso numero di iterazioni della riduzione da l0 = D ad l dimensioni. Quindi

α e β devono soddisfare la relazione

) 1 log( ) log( ) 1 ( log ) ( log _{0 0} β α l l k k = . L’algoritmo è il seguente: 1. Detti

o k: numero desiderato di cluster (input);

o l: dimensionalità desiderata dei sottospazi (input); o k : numero iniziale di semi (input), con 0 k0 >k; o d: dimensionalità dello spazio-origine;

o k : numero corrente di semi; _c

o l : dimensionalità corrente dei sottospazi; _c

o 1≤i≤k_c;

si scelgono k punti dal database; si pone ₀ kc = ; si pone k0 lc = ; si inizializzano d tutti i current subspace con lo spazio-origine; si inizializzano i valori di α e β (il primo generalmente a 0.5 e il secondo di conseguenza).

2. Finché si verifica k_c > : k

o si esegue la procedura Assign

(

s₁,s_kc,ε ₁, ε_kc

)

per trovare la partizione

indotta dai semi;

o per ognuno dei k current cluster della partizione, si esegue la procedura _c

(

Ci lc

)

s

FindVector , che determina il corrispondente current subspace associato;

o si pone knew =max

(

k,kc ⋅α

)

; si pone lnew =max

(

l,lc⋅β

)

;

o si esegue la procedura Merge

(

C1,Ckc,knew,lnew

)

per ridurre il numero di semi e la dimensionalità dei sottospazi;

o si pone kc=knew; si pone lc =lnew;

2.2.1 La procedura Assign

Il database viene partizionato in k current cluster assegnando ciascun punto al seme più _c

vicino. Nel processo di partizionamento, la distanza di un punto del database dal seme s è _i

misurata nel sottospazio ε . In altre parole, per ciascun punto p del database si calcola il _i valore Pdist

(

p,si,εi

)

e il punto è assegnato al current cluster C per il quale quel valore è il i minimo. L’ultima operazione della procedura è il rimpiazzamento di ciascun seme con il centroide del cluster appena creato. La procedura serve a raffinare sia il set di cluster che il set di semi ad essi associati.

2.2.2 La procedura FindVectors

Per ogni current cluster C calcola la corrispondente matrice di covarianza e sceglie gli _i l c autovettori ortonormali associati agli autovalori più piccoli, cioè le direzioni lungo le quali la dispersione è minima. Questo seleziona il sottospazio l -dimensionale in cui il current cluster c

i

C ha minima energia proiettata. Si tenga presente che il valore di l si riduce di iterazione in _c

iterazione.

2.2.3 La procedura Merge

Per poter ridurre il numero di cluster da k a c knew =(1−α)⋅kc, le coppie di current cluster più vicini devono essere fuse insieme progressivamente. Fare questo è relativamente semplice in un algoritmo full-dimensional, dato che la bontà della fusione può essere facilmente quantificata. Il caso di questo algoritmo presenta una maggiore complessità. Dal momento che ogni current cluster C esiste nel suo proprio sottospazio _i ε , il problema è _i decidere riguardo alla vicinanza di coppie di cluster. Dal momento che l’algoritmo mira a scoprire cluster con piccola energia proiettata, la valutazione cercata si può ottenere esaminando l’energia proiettata dell’unione di due cluster nel sottospazio a minima dispersione associato.

Il calcolo della qualità del merging di una coppia

[ ]

i, di current cluster è eseguito in due j

passi:

1. si usa la decomposizione ai valori singolari sui punti in C =Ci Cj e si trovano gli autovettori corrispondenti ai più piccoli l_new autovalori (dove l_new è la dimensionalità proiettata in quell’iterazione). Questi autovettori definiscono il sottospazio a minima dispersione per i punti nell’unione dei due current cluster, detto ε ′ ; _ij

2. si trova il centroide s′ di _ij C i Cj e si usa l’energia rij =R

( )

C,ε ′ij come indicatore della qualità della fusione eseguita. Si noti che, usando questo metodo, due cluster risultano molto probabilmente ben accoppiati se le direzioni di minima dispersione dei singoli cluster sono simili. In questo caso ε ′ , _ij ε ed i ε sono probabilmente tutti j sottospazi associati a un’energia proiettata piccola. L’idea generale è di misurare quanto bene i due current cluster si adattano ad un singolo pattern.

Il procedimento suddetto è ripetuto per ciascuna coppia di cluster e al termine si trova la coppia

[ ]

i′, per la quale j′ ri′j′ è minima. Se i cluster vengono fusi, allora il centroide si′ del ′j′ cluster combinato viene aggiunto al set di semi, mentre i semi s_i′ e s_j′ vengono rimossi. Il current cluster associato a questo nuovo seme è C_i′  e il current subspace è C′_j ε′ . ij

Questa procedura agglomerativa viene ripetuta molteplici volte, finché il numero di cluster è ridotto di un fattore α .

L’algoritmo termina quando il processo di merging iterativo ha ridotto il numero di cluster a k. A quel punto la dimensionalità l del sottospazio c ε associata con ciascun i cluster C è anche uguale ad _i l.

2.3 Evoluzione

dell’algoritmo

2.3.1 Scelta della dimensionalità di proiezione

Un parametro di input fondamentale per l’algoritmo è la dimensionalità di proiezione l. Per dare qualche direttiva all’utente nello scegliere questo parametro, si propone una misura legata al concetto di clustering proiettato generalizzato.

È stato dimostrato che, sotto certe condizioni per la distribuzione dei dati, al crescere della dimensionalità la distanza fra ogni coppia di punti diventa quasi la stessa. Questo significa che se un cluster di punti C viene confrontato con l’insieme di punti universale U

in uno spazio ad elevata dimensionalità D , si ha

(

)

(

,

)

1 , ≅ D U R D C R .

Tale situazione è problematica, perché la dispersione media (energia) del cluster è quasi la stessa della dispersione media dei punti dell’intero database nello spazio-origine. Il motivo dell’instabilità degli algoritmi di clustering a campionamento in spazi ad elevata dimensionalità è proprio questo: differenti esecuzioni portano a differenti set di cluster, il cui indice di qualità, indipendentemente dal metodo scelto per calcolarlo, è quasi sempre lo stesso.

Invece, nei sottospazi di D quel rapporto può essere molto più piccolo dell’unità. In generale è desiderabile un rapporto significativamente più piccolo di 1 perché indica un cluster fortemente compatto nel sottospazio di proiezione.

Si definisce allora la seguente misura qualitativa chiamata coefficiente di dispersione dei cluster (cluster sparsity coefficient):

∑

= ⋅ = k i i i i k k U R C R k C C S 1 1 1 ) , ( ) , ( 1 ) ... , ... ( ε ε ε ε .

Più basso è il valore di l, più piccolo è il valore della frazione, perché ε può essere scelto in _i modo migliore quando la dimensionalità è più bassa. In questo modo si riduce l’energia

(

Ci i

)

R ,_ε per quella particolare distribuzione di punti in C , mentre l’insieme complessivo _i

Al termine dell’elaborazione l’algoritmo può restituire il coefficiente di dispersione dei cluster: se il suo valore è prossimo all’unità, allora è chiaro che si deve scegliere un valore inferiore della dimensionalità di proiezione.

L’utente può definire una soglia minima per questa misura qualitativa e scegliere il massimo valore di l per il quale il coefficiente di dispersione ottenuto è minore della soglia.

Un modo alternativo di effettuare la scelta è quello di eseguire l’algoritmo per valori decrescenti della dimensionalità di proiezione, osservando la variazione del coefficiente di dispersione in funzione di quest’ultima: si sceglierà il valore l in corrispondenza del quale la ₀

variazione osservata è massima.

In effetti, la miglior soluzione per la scelta della dimensionalità di proiezione può richiedere un alto livello di interazione da parte dell’utente, in aggiunta allo studio del coefficiente di dispersione.

2.3.2 Trattamento degli Outlier

Per tenere conto del fatto che alcuni punti sono outlier, è necessaria qualche modifica all’algoritmo.

Si indichi con δ la distanza proiettata tra il seme _i s e il seme ad esso più vicino nel i sottospazio ε per ogni _i i∈{1,...,k_c}. Durante la fase di assegnamento, sia s il seme al quale _r

viene assegnato un punto P del database. Quel punto è un outlier se la sua distanza proiettata dal seme s nel sottospazio _r ε è maggiore di r δ . r

Si noti inoltre che anche alcuni dei semi scelti inizialmente potrebbero essere outlier. Bisogna rimuoverli durante l’esecuzione dell’algoritmo. Una semplice modifica che funziona abbastanza efficacemente è di scartare, in ciascuna iterazione, una certa percentuale dei semi per i quali il corrispondente cluster contiene pochi punti. Questo porta a scartare un numero maggiore di semi durante le iterazioni iniziali, perché in quelle finali tutti i semi rappresentano un cluster sufficientemente denso di punti.

Qualora si implementi l’opzione di outlier handling, il valore del fattore di riduzione α è definito dalla riduzione percentuale ad ogni iterazione dovuta sia alle fusioni che agli scarti.

2.3.3 Scalabilità

Uno degli aspetti della tecnica di merging usata è che occorre lavorare esplicitamente con il set di current cluster C ...1 Ck_c. Dal momento che il database può essere molto esteso, potrebbe essere estremamente ingombrante mantenere gli insiemi di punti C ...₁ C_kc

esplicitamente. Inoltre, il calcolo della matrice di covarianza è probabilmente molto pesante in termini di I/O, dato che ogni iterazione di calcoli per una matrice di covarianza richiede una passata sul database. Poiché la matrice di covarianza viene calcolata ( 2)

0

k

O volte dalla procedura Merge, questo si traduce in altrettante passate sul database. Il valore di k è ₀

probabilmente molte volte il numero k di cluster da determinare, quindi questo livello di I/O è inaccettabile.

Si introduce allora il concetto di extended cluster feature vector (ECF-vector), utilizzando il quale tutte le operazioni considerate possono sempre essere eseguite memorizzando solo informazioni di riepilogo dei cluster. Questo semplifica considerevolmente il calcolo delle matrici di covarianza.

L’ECF-vector è specifico per un dato cluster C e contiene _d2 _{+ d+}1 _{elementi. Gli} elementi sono di tre tipi:

1. d elementi sono relativi alle coppie di dimensioni 2

( )

i,j . Per ciascuna di esse, si sommano i prodotti della i -esima e della j -esima coordinata di ciascun punto del cluster.

In altre parole, se k i

x indica la i -esima componente del k-esimo punto del cluster

C, l’ECF-vector di C in corrispondenza della coppia di dimensioni

( )

i,j contiene l’elemento

∑

∈ ⋅ = _{k C} k j k i C ij x x ECF1

L’intero gruppo di questi elementi sarà indicato con _{ECF1 .}C

2. d elementi sono relativi alle singole dimensioni. L’i -esimo elemento contiene la somma delle i -esime componenti di ciascun punto del cluster, per il quale quindi si mantiene l’elemento

∑

= k

C _x

L’intero gruppo di questi elementi sarà indicato con _{ECF 2}C

3. Un unico elemento contiene il numero di punti del cluster C, che sarà indicato con C

ECF3

L’ECF-vector deriva direttamente dal noto CF-vector, al quale aggiunge il primo insieme di _{d elementi. Nel seguito si indicherà l’ECF-vector di un cluster con} 2

(

C C C

)

C _{ECF ECF ECF}

ECF = 1 , 2 , 3

Due importanti proprietà di cui gode l’ECF-vector sono le seguenti:

– La matrice di covarianza può essere ricavata direttamente dall’ECF-vector. Precisamente, la covarianza fra le dimensioni i e j per un insieme di punti C vale

2 ) 3 ( 2 2 3 1 C C j C i C C ij ECF ECF ECF ECF ECF ⋅ −

Poiché il CF-vector può essere usato per calcolare il centroide e il raggio di un cluster, essendo l’ECF-vector un’estensione del CF-vector la stessa misura può essere ottenuta dall’ECF-vector

– Proprietà additiva: l’ECF-vector dell’unione di due insiemi di punti equivale alla somma dei rispettivi ECF-vector

Gli ECF-vector sono usati per modificare ORCLUS nel seguente modo: durante l’intera esecuzione dell’algoritmo, i current cluster C ...1 Ck_C associati a ciascun seme non sono mantenuti esplicitamente. Invece sono mantenuti i rispettivi ECF-vector. L’ECF-vector di un cluster è sufficiente per calcolarne il raggio, il centroide e la matrice di covarianza. Quest’ultima può essere calcolata molto efficientemente, infatti la proprietà additiva assicura che, mentre si costruisce l’ECF-vector per l’unione di due cluster, non è necessario ricalcolare tutto da zero, ma è sufficiente sommare gli ECF-vector dei due cluster. Ad ogni iterazione gli ECF-vector devono essere ricalcolati solo durante la fase Assign, cosa estremamente vantaggiosa perché si tratta di un semplice processo additivo che non influisce sulla totale complessità temporale dell’algoritmo.

2.4 Requisiti

2.4.1 Requisiti temporali

Il tempo di esecuzione dell’algoritmo dipende dal numero iniziale di semi k scelto. La 0 struttura base dell’algoritmo contiene i due processi di agglomerazione e di assegnamento dei punti. L’aggiunta dell’opzione di trattamento degli outlier non può che ridurre il tempo di esecuzione, poiché le fusioni sono rimpiazzate da semplici scarti. Quindi l’analisi che segue per stimare gli ordini di grandezza dei tempi per le varie procedure è una stima per eccesso.

– Merge

Il tempo della fusione è asintoticamente controllato dal tempo richiesto nella prima iterazione per ridurre il valore del numero di current cluster da k ad 0 α⋅k0. In partenza sono calcolati gli autovettori per ciascuna delle k coppie di current cluster. 02 Questo richiede un tempo di esecuzione _O

( )

_d3 _{per ciascuna coppia. Inoltre, per} ciascuna delle successive

(

1−α

)

⋅k0 −k fusioni, devono essere ricalcolati gli

autovettori per O

( )

k0 coppie di cluster. Poiché il calcolo di ogni autovettore richiede un tempo _O

( )

_d3 _{, ne segue che il tempo complessivo per il calcolo degli autovettori} durante l’operazione di fusione è dato da O

(

k02⋅d3

)

. Inoltre, per ciascuna operazione di fusione, è richiesto un tempo di O

( )

k02 per poter scegliere il cluster con energia minima . Quindi il tempo di esecuzione complessivo per tutte le fusioni è

(

)

(

3

)

0 2 0 k d k O + . – Assign

Il tempo di esecuzione per assegnare gli N punti dello spazio d-dimensionale ai k 0 cluster nella prima iterazione è O

(

k0⋅N⋅d

)

. Nella seconda iterazione il tempo è di

(

)

(

k N d

)

O 0⋅α ⋅ ⋅ e così via. Quindi il tempo complessivo per il processo di

assegnamento è       − ⋅ ⋅ α 1 0 N d k O .

– Determinazione dei sottospazi

Il tempo per il calcolo degli autovettori (determinazione dei sottospazi) è già stato considerato. Rimane da considerare il tempo per la determinazione dei sottospazi durante ciascuna fase iterativa (procedura FindVectors dopo la Assign). Durante la prima iterazione dell’algoritmo i sottospazi vengono determinati k volte, durante la ₀

seconda k0⋅α volte e così via. Quindi per l’intero algoritmo ci sono al più α − 1

0

k

calcoli dei sottospazi. Questo tempo d’esecuzione è certamente piccolo rispetto a quello richiesto per determinare i sottospazi nella fase di fusione e può quindi essere trascurato asintoticamente.

Sommando i vari contributi, si ha che il tempo d’esecuzione totale richiesto è

(

2 3

)

0 0 3 0 k N d k d k

O + ⋅ ⋅ + ⋅ . Si noti la dipendenza dalla scelta del parametro iniziale k : un ₀

valore alto aumenterà il tempo d’esecuzione, ma migliorerà la qualità del clustering.

2.4.2 Requisiti spaziali

L’uso dell’ECF-vector abbatte considerevolmente i requisiti di spazio, dato che non vengono mantenuti i current cluster associati a ciascun seme. Durante ciascuna iterazione dell’algoritmo, devono essere mantenuti almeno k ECF-vector. Lo spazio necessario _C

richiesto è dato da _{k ⋅}(_d2_+d+1)

C . Questa quantità assume il valore massimo durante la prima iterazione, quando k_C = , quindi il requisito complessivo di spazio è k₀

(

2

)

0 d

k

O ⋅ , indipendente dalla grandezza del database.

2.5 Campionamento Progressivo (Progressive Random Sampling)

Dal punto di vista del tempo d’esecuzione, il contributo dipendente da N è dovuto alla procedura Assign e, sebbene si riduca di un fattore α ad ogni passo, può rappresentare un collo di bottiglia quando il database è molto esteso.

Lo scopo della procedura Assign è quello di assicurare che, in ciascuna iterazione, i semi siano il punto centrale del current cluster associato. Eseguendo un campionamento random progressivo si possono raggiungere gli stessi risultati in tempi inferiori: è sufficiente assegnare ai cluster solo un sottoinsieme campione dei punti per ciascuna iterazione. Il campione può essere diverso per iterazioni diverse e può cambiare anche in grandezza. Un modo efficace di realizzare il campionamento descritto è il seguente:

– si inizia con un campione casuale di dimensione N⋅k k₀;

– si incrementa il numero di punti del campione di un fattore α ad ogni iterazione. In questo modo, all’ultima iterazione saranno usati tutti i punti del database e il tempo necessario per la fase di assegnamento rimane costantemente O

(

N⋅k⋅d

)

. Il tempo di calcolo complessivo per l’esecuzione di tutte le iterazioni diviene quindi

            ⋅ ⋅ ⋅ k k d k N O _log 0 α .

Il tipo di campionamento introdotto può far risparmiare una considerevole quantità di tempo nelle iterazioni iniziali, purché k venga scelto sensibilmente più grande di 0 k. Inoltre la perdita di accuratezza causata è bassa, perché nelle ultime iterazioni i cluster risultano molto raffinati e per l’assegnamento sono usati campioni di dimensione più grande.