4. L’ALGORITMO ORCLUS - VALUTAZIONE
4.1 Generazione di dati artificiali
Per testare l’implementazione dell’algoritmo ORCLUS, si è provveduto a realizzare un semplice software per la generazione artificiale di dati, chiamato Datagen.
I dataset prodotti dal programma hanno caratteristiche tali da rendere inefficienti sia il clustering full-dimensional, sia il clustering su proiezioni parallele agli assi dello spazio- origine.
4.1.1 Principio di funzionamento di Datagen
Il primo stadio della generazione artificiale di dati è quello di creare i sottospazi l- dimensionali associati a ciascuno dei k cluster richiesti dall’utente. Tale operazione viene eseguita attraverso la generazione di matrici simmetriche. Per ogni matrice la ( )i, -esima j
entrata è un numero reale random appartenente all’intervallo [−1, 1]. Essendo la matrice simmetrica, i suoi autovalori sono tutti reali ed esiste un sistema di autovettori ortonormali, che sarà usato orientare il cluster corrispondente. Per ogni cluster si genera una diversa matrice, a partire dalla quale si scelgono l autovettori che definiscono il sottospazio associato.
Il numero di punti dei cluster viene determinato come segue:
– si generano costanti di proporzionalità che individuano quanti punti appartengono ad ogni cluster. Si ha
q R p
ri = + ⋅ , i=1,2,,k;
dove p e q sono costanti ed R è un numero random estratto da una distribuzione uniforme nell’intervallo [0, 1]. Le costanti r1,r2, saranno quindi campioni ,rk
– il numero di punti appartenenti al cluster i -esimo viene determinato come
∑=
= k⋅
i i
i i
r r N N
1
.
Il passo successivo è la generazione degli anchor point (un’approssimazione del punto centrale) di ciascun cluster, che vengono estratti da una distribuzione uniforme di punti nello spazio-origine.
Infine vengono stabilite le coordinate dei punti di ciascun cluster, rispetto al corrispondente sistema di assi trasformato. Questo perché nel sottospazio associato le correlazioni tra le dimensioni sono nulle, per cui le coordinate possono essere generate indipendentemente l’una dall’altra. I punti l-dimensionali così ottenuti vengono poi ri- trasformati nel sistema dello spazio-origine. Ciascuna delle rimanenti d−l coordinate viene estratta da una distribuzione uniforme.
La generazione delle coordinate dei punti nel sottospazio avviene in base alla procedura seguente:
– si determina la dispersione lungo ciascuno degli l autovettori, utilizzando la coppia di parametri µ e γ . La dispersione lungo l’autovettore i -esimo sarà proporzionale a s
)γ
(Qi , dove Q viene estratto da una distribuzione esponenziale con valor medio i µ ; il parametro γ determina la differenza di dispersione che si desidera creare tra le s
varie direzioni assiali;
– la i-esima coordinata del punto nel sottospazio del cluster viene estratta da una distribuzione normale con media uguale all’anchor point e varianza uguale a (Qi)γ. I cluster del dataset risultante dall’esecuzione di Datagen sono caratterizzati da un’elevata dispersione dei punti nello spazio-origine.
4.1.2 Scheda del software
Il programma è scritto in linguaggio C++. Si appoggia alla libreria matematica di libero utilizzo e distribuzione “Newmat 10” (http://www.robertnz.net).
È stato compilato utilizzando l’ambiente Microsoft Visual C++ 6.0.
Il file eseguibile gira in modalità W32 console (finestra DOS) e richiede parametri attraverso la linea di comando.
4.1.2.1 File disponibili – Sorgenti:
o datagen10.cpp o my_utils.h – Libreria Newmat 10
o sorgenti: newmat10\*.*
o oggetti: newmat10\obj\*.obj – Programma eseguibile: datagen10.exe – Utility di lancio: datagen10.bat
4.1.2.2 Input
Il programma richiede i seguenti parametri:
1. il text flag, che specifica la produzione di un file di output contenente il dataset in formato testo;
2. il nome del file destinato a contenere il dataset (binario);
3. il nome del file destinato a contenere la tabella punti-cluster (testo);
4. il nome del file destinato a contenere i dati di riepilogo del dataset (testo);
5. il numero di punti del dataset
6. la dimensionalità dello spazio-origine;
7. il numero desiderato di cluster;
8. la dimensionalità dei sottospazi associati;
9. la costante p ; 10. la costante q ; 11. la costante µ ; s 12. la costante γ .
Esempio di linea di comando valida:
datagen10.exe txtOFF dati.bin tabella.txt info.txt 50000 60 10 9 1 5 0.1 2
4.1.2.3 Output I file prodotti sono:
1. un file binario contenente i punti del dataset; le coordinate sono in formato floating point double precision;
2. un file testo contenente la tabella punti-cluster.
La tabella ha due campi: il primo è il numero d’ordine del punto nel dataset; il secondo è il numero d’ordine del cluster cui il punto è stato assegnato. I record della tabella occupano linee consecutive e i campi sono separati da una tabulazione. I dati prodotti risultano così un database in formato testo, pronto per essere importato (ad esempio in Microsoft Excel) per l’analisi;
3. un file testo contenente i dati di riepilogo del dataset generato (una copia dei parametri di input ricevuti).
4.1.3 Esempio di applicazione di Datagen
Allo scopo di illustrare graficamente la tipologia dei dataset generabili, si riporta un esempio ottenuto dall’esecuzione di Datagen. Si fa notare che la scelta dei parametri è stata fatta in modo da enfatizzare le caratteristiche del risultato.
Parametri di input:
– numero di punti: 50;
– dimensioni dello spazio-origine: 3;
– numero di cluster: 3;
– dimensioni dei sottospazi-proiezione: 2;
– costanti:
=1
p ; q=5; µs =0.1; γ =2.
La Tabella 3 mostra le coordinate dei punti nello spazio-origine. I punti sono ordinati per cluster di appartenenza, come si deduce dal codice a colori. Per comodità, nella tabella le coordinate sono state convertite da numeri reali a numeri interi.
Cluster 0 Cluster 1 Cluster 2
Punto X Y Z Punto X Y Z Punto X Y Z
P_0 5842 4684 2422 P_25 -3297 -9681 7797 P_37 -8975 -969 -139
P_1 4871 5226 1567 P_26 -1002 -9468 4669 P_38 -1586 -1581 2909
P_2 2184 6707 -656 P_27 -640 -9424 4165 P_39 1934 -1871 4361
P_3 6463 4357 2926 P_28 4775 -8920 -3255 P_40 7760 -2395 6816
P_4 3150 6178 147 P_29 932 -9272 1974 P_41 7779 -2360 6811
P_5 -3056 9601 -5041 P_30 -2797 -9659 7153 P_42 -5753 -1239 1184
P_6 4847 5246 1574 P_31 -124 -9370 3487 P_43 -4617 -1334 1652
P_7 -241 8072 -2703 P_32 737 -9291 2291 P_44 696 -1780 3856
P_8 -2794 9505 -4854 P_33 5019 -8907 -3666 P_45 -909 -1639 3187
P_9 3382 6049 336 P_34 3731 -9016 -1890 P_46 4082 -2034 5249
P_10 52 7889 -2434 P_35 3538 -9030 -1611 P_47 562 -1763 3801
P_11 -1207 8583 -3491 P_36 -1791 -9518 5764 P_48 -5160 -1279 1451
P_12 3342 6046 330 P_49 -5673 -1246 1220
P_13 137 7859 -2359
P_14 364 7708 -2179
P_15 2465 6536 -414
P_16 6722 4215 3139
P_17 -1790 8918 -4007
P_18 9816 2519 5727
P_19 7924 3557 4135
P_20 7626 3719 3879
P_21 5122 5059 1806
P_22 1947 6842 -858
P_23 5793 4700 2313
P_24 -1145 8536 -3437
Tabella 3
Le proiezioni su due dimensioni parallele agli assi sono mostrate in Figura 15, Figura 16, Figura 17. Si noti che la disposizione dei punti è tale da rendere necessarie tutte le dimensioni nello spazio full-dimensional e da non privilegiare alcuna proiezione tra quelle parallele agli assi.
In Figura 18 e Figura 19 si può apprezzare, grazie all’impiego delle due diverse scale, come cambia la situazione per il cluster formato dai punti color verde quando si considera il suo sottospazio associato.
-10000 -8000 -6000 -4000 -2000 0 2000 4000 6000 8000 10000
-100 00
-8000 -6000
-4000
-2000 0
20 00
40 00
60 00
80 00
10 00
0
X
Y
c luster 0 c luster 1 c luster 2
Figura 15
-10000 -8000 -6000 -4000 -2000 0 2000 4000 6000 8000 10000
-100 00
-8000 -6000
-4000
-2000 0
20 00
40 00
60 00
80 00
10 00
0 X
Z
clus ter 0 clus ter 1 clus ter 2
Figura 16
-10000 -8000 -6000 -4000 -2000 0 2000 4000 6000 8000 10000
-100 00
-8000 -6000
-4000
-2000 0
20 00
40 00
60 00
80 00
1000 0 Y
Z
c luster 0 c luster 1 c luster 2
Figura 17
-10000 -8000 -6000 -4000 -2000 0 2000 4000 6000 8000 10000
-10000 -8000 -6000 -4000 -2000
0
2000 4000 6000 8000 10000
X*
Y*
Figura 18
6700 6720 6740 6760 6780 6800 6820 6840 6860 6880 6900
1400 1420 1440 1460 1480 1500 1520 1540 1560 1580 1600
X*
Y*
Figura 19
4.2 Applicazione di ORCLUS a dati artificiali
Utilizzando il programma Datagen sono stati prodotti diversi dataset, le cui caratteristiche sono combinazioni dei seguenti valori:
– numero di punti: 10000, 50000, 100000;
– dimensionalità dello spazio-origine: 20, 25, 30;
– numero di cluster (k): 5, 10;
– dimensionalità dei sottospazi-proiezione: 6, 9.
Su questi dataset sono stati eseguiti test ripetuti di orclus32, al variare di tutti i singoli parametri di input. I risultati ottenuti hanno mostrato che il comportamento del software realizzato è corretto, sia perché le prestazioni temporali sono in linea con quelle previste teoricamente per l’algoritmo, sia perché la segmentazione risultante dei dataset è mediamente di alta qualità.
4.2.1 Prestazioni temporali
Il tempo di esecuzione è stato stimato inizialmente in funzione del numero di punti del dataset, fissando gli altri parametri di input ai valori seguenti:
– numero iniziale di cluster (k ): 0 15×k; – fattore di riduzione (α ): 0.5;
– calcolo di autovalori e autovettori: metodo di Jacobi;
– Progressive Random Sampling (PRS): off.
I valori per il numero di cluster e per la dimensionalità dei sottospazi desiderati sono stati scelti, di volta in volta, uguali ai valori di generazione del dataset utilizzato per il test.
Si ritiene opportuno sottolineare che i tempi misurati riguardano l’esecuzione completa del programma, non delle sole elaborazioni relative all’algoritmo, quindi includono i tempi per la produzione dei file di output.
Al variare del numero di punti dei dataset si è riscontrato un andamento quasi lineare del tempo di esecuzione (Figura 20).
Running Time (1.1)
00:00:00 00:01:26 00:02:53 00:04:19 00:05:46 00:07:12 00:08:38
0 50 100
Punti (x 1000)
Tempo (hh:mm:ss)
test_***_20_05_6_075_050_J_off test_***_20_05_9_075_050_J_off test_***_20_10_6_150_050_J_off test_***_20_10_9_150_050_J_off test_***_25_05_6_075_050_J_off test_***_25_05_9_075_050_J_off test_***_25_10_6_150_050_J_off test_***_25_10_9_150_050_J_off test_***_30_05_6_075_050_J_off test_***_30_05_9_075_050_J_off test_***_30_10_6_150_050_J_off test_***_30_10_9_150_050_J_off
Figura 20
Running Time (1.2)
y = 0,0002x2 + 2,3901x + 213,24
0 2000 4000 6000 8000 10000 12000 14000
Tempo (sec)
Per approfondire l’indagine è stata poi scelta la serie di test relativa ai dataset con dimensionalità pari a 30 e contenenti 10 cluster a 9 dimensioni, essendo quella caratterizzata dalla maggiore pendenza del grafico e quindi associata alle variazioni più evidenti. Sono stati generati dataset ulteriori, con 25000, 75000, 125000 e 150000 punti, sui quali sono stati eseguiti nuovi test. Mediante interpolazione dei risultati, si è ottenuta infine una stima del tempo di esecuzione necessario per elaborare dataset contenenti fino a quattro milioni di punti (Figura 21).
Successivamente è stata effettuata una valutazione dei tempi di esecuzione in funzione della dimensionalità dello spazio-origine. L’andamento iniziale riscontrato, riportato in Figura 22, appare non lineare. Analogamente a quanto fatto in precedenza, per approfondire l’indagine è stata poi scelta la serie di test relativa al dataset con 50000 punti, contenente 10 cluster a 9 dimensioni. Sono stati prodotti dataset aggiuntivi con 40, 50 e 60 dimensioni, sui quali sono stati eseguiti nuovi test. Mediante interpolazione dei risultati, è stata infine ottenuta una stima del tempo di esecuzione necessario per elaborare dataset aventi fino a 70 dimensioni (Figura 23).
Running Time (2)
00:00:00 00:01:26 00:02:53 00:04:19 00:05:46 00:07:12 00:08:38
18 25 32
Dimensioni origine
Tempo (hh:mm:ss)
test_010k_**_05_6_075_050_J_off test_010k_**_05_9_075_050_J_off test_010k_**_10_6_150_050_J_off test_010k_**_10_9_150_050_J_off test_050k_**_05_6_075_050_J_off test_050k_**_05_9_075_050_J_off test_050k_**_10_6_150_050_J_off test_050k_**_10_9_150_050_J_off test_100k_**_05_6_075_050_J_off test_100k_**_05_9_075_050_J_off test_100k_**_10_6_150_050_J_off test_100k_**_10_9_150_050_J_off
Figura 22
Running Time (3)
y = 0,83x2 - 24,197x + 298,29
0 500 1000 1500 2000 2500 3000 3500
Tempo (sec)
Tutti i test sono stati ripetuti utilizzando il metodo di Householder per il calcolo di autovalori e autovettori. La velocità di esecuzione è risultata incrementata rispetto ai valori relativi all’uso del metodo di Jacobi, ma gli incrementi sono decrescenti con l’aumentare del numero di punti del dataset (Figura 24).
10 25
50 00:00:00
00:01:26 00:02:53 00:04:19 00:05:46
Tempo (hh:mm:ss)
Punti (x 1000) Running Time (4.1)
test_***_30_10_9_150_050_H_off test_***_30_10_9_150_050_J_off
Figura 24
L’uso del Progressive Random Sampling, infine, si è dimostrato efficace nell’abbattere i tempi di esecuzione, producendo miglioramenti in linea con le previsioni teoriche relative al suo impiego.
4.2.2 Prestazioni qualitative
Come accennato in precedenza, i test effettuati hanno prodotto segmentazioni di qualità molto alta per tutti i dataset di prova.
Nei casi in cui il valore della dimensionalità dei sottospazi è stato posto uguale a quello di generazione del dataset, sono state confrontate direttamente la tabella punti-cluster associata al dataset e quella prodotta dall’elaborazione. I risultati dei confronti diretti hanno raggiunto anche il 100% di assegnamenti esatti, mantenendosi comunque al di sopra del 90%, salvo casi isolati.
Relativamente alle elaborazioni eseguite imponendo una dimensionalità dei sottospazi diversa da quella prodotta dal generatore di dati, le valutazioni di qualità sono state effettuate creando la Matrice di Confusione e calcolando la Dominant Ratio. Questa è risultata mediamente elevata, con variazioni comprese tra 0.77 e 0.98.
È stato valutato attentamente il Cluster Sparsity Coefficient, che nell’utilizzo dell’algoritmo su dati reali è l’unico parametro di riferimento per giudicare la qualità della segmentazione prodotta. I valori riportati nei casi di segmentazione identica a quella prodotta dal generatore sono stati dell’ordine di 10−10; i valori corrispondenti alle segmentazioni di qualità peggiore sono risultati dell’ordine di 10−1; complessivamente si può affermare che un buon clustering è indicato da un valore del CSC dell’ordine almeno di 10−2.
Riguardo all’opzione di Progressive Random Sampling e alla scelta del metodo di Householder, i risultati hanno mostrato che l’utilizzo di una o l’altra delle due soluzioni (che accelerano l’elaborazione) non comporta generalmente un degrado qualitativo sensibile, mentre il loro utilizzo contemporaneo produce risultati il cui CSC è al limite dei valori indicanti un risultato accettabile.
