3. L’ALGORITMO ORCLUS - REALIZZAZIONE
3.1 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.
Il test del programma è stato eseguito in ambiente Microsoft Windows 98, su un PC dotato di processore Athlon 1700+ e 512 MB di memoria DDR.
3.1.1 File disponibili – Sorgenti: o algoritmo.cpp o orclus.cpp o datafile.h o datafile.cpp o orclus_partition.h o orclus_partition.cpp o pcluster.h o pcluster.cpp o my_utils.h – Libreria Newmat 10 o sorgenti: newmat10\*.*
– Programma eseguibile: orclus32.exe – Utility di lancio: orclus.bat
3.1.2 Input
Il programma richiede sei parametri:
1. il nome del file di configurazione (testo) oppure
l’opzione -r, che specifica un’esecuzione con recupero dello stato; in questo caso la configurazione viene letta automaticamente dal file “stato.txt”
2. il nome del file contenente il dataset (binario o testo)
3. il nome del file destinato a contenere la tabella punti-cluster (testo) 4. il nome del file destinato a contenere i dati dei cluster (binario) 5. il nome del file destinato a contenere i centroidi dei cluster (testo)
6. il nome del file destinato a contenere i dati di riepilogo del partizionamento (testo)
Esempi di linee di comando valide:
– orclus32.exe config.txt dati.bin tabella.txt cluster.bin cluster.txt summary.txt
– orclus32.exe config.txt dati.txt tabella.txt cluster.bin cluster.txt summary.txt
– orclus32.exe -r dati.bin tabella.txt cluster.bin cluster.txt summary.txt
3.1.3 Output
I file prodotti sono:
1. 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. Se il punto è un outlier (cioè se la sua distanza dal centroide del cluster più vicino è maggiore della distanza fra i centroidi dei due cluster più lontani), il secondo campo contiene la stringa “outlier” invece di un numero d’ordine. 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.
2. Un file binario contenente i dati dei cluster
Il file è destinato ad essere utilizzato da futuri moduli aggiuntivi per l’esecuzione di eventuali analisi dei cluster prodotti (calcolo del diametro, analisi dei sottospazi associati, ecc.).
3. Un file testo contenente la tabella dei centroidi dei cluster
I centroidi sono calcolati come media aritmetica dei punti appartenenti ai cluster. La tabella, priva di intestazione, ha un numero di campi dipendente ovviamente dalla dimensionalità dello spazio-origine: il primo campo è l’identificativo del centroide (“S_” seguito dal numero d’ordine del cluster relativo); i campi successivi sono le coordinate, valori double precision a 10 cifre complessive. 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, disponibile per eventuali programmi classificatori che utilizzino i soli centroidi.
4. Un file testo contenente i dati di riepilogo del partizionamento, cioè la tabella cluster-cardinalità e il Cluster Sparsity Coefficient.
La tabella ha due campi: il primo è il numero d’ordine del cluster; il secondo è il numero di punti del dataset che sono stati assegnati al cluster. L’ultimo record della tabella contiene nel primo campo la stringa “outlier” e nel secondo il numero di punti classificati come outlier. 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. Il Cluster Sparsity Coefficient viene calcolato solo se richiesto dall’utente mediante il file di configurazione; in caso contrario, il valore restituito tra le informazioni di riepilogo è il carattere “-”.
5. Il file di testo “stato.txt”
Esso contiene una parte statica, costituita dai parametri di configurazione dell’esecuzione corrente. Contiene anche un’eventuale parte dinamica, costituita dallo stato dei cluster “congelato” al termine di uno step di elaborazione. La frequenza di salvataggio della parte dinamica va specificata nel file di configurazione, indicando il
3.1.4 Il file di configurazione
Per impostare i valori desiderati si può editare il prototipo del file di configurazione fornito insieme al programma. Si raccomanda di mantenere la struttura del contenuto del file, limitando le modifiche ai soli valori dei parametri.
Esempio di file di configurazione:
Dimensionalità dello spazio-origine: 30
Numero desiderato di cluster: 5
Dimensionalità dei sottospazi-proiezione: 6
Numero iniziale di semi: 75
Fattore di riduzione: 0.5
Tipo del file dataset: binario
Numero di punti del dataset: 10000
Tipo dei punti del dataset: double
Dimensione in byte delle coordinate dei punti del dataset: 8
Frequenza di salvataggio dello stato: 0
Metodo di calcolo degli autovalori: M
Progressive Random Sampling: prsOFF
Calcolo del Cluster Sparsity Coefficient: cscON
Basket Dataset flag: bdON
3.1.5 Significato dei parametri di configurazione e fine tuning
1. Dimensionalità dello spazio-origine ( D ) Intero positivo.
2. Numero desiderato di cluster ( K ) Intero positivo.
4. Numero iniziale di semi (K ) 0
Intero positivo K> . Per K crescente, aumenta la precisione del risultato ed 0
aumenta il tempo di esecuzione necessario. Valore consigliato: 15⋅K . 5. Fattore di riduzione (α )
Reale nell’intervallo
] [
0 . Ad ogni passo l’algoritmo usa questo valore per ridurre il ,1 numero corrente di cluster, usando una procedura di merging. Per α crescente, aumenta la precisione del risultato ed aumenta il tempo di esecuzione necessario. Valore consigliato: 0.5. La combinazione dei parametri α e K incide sul numero 0totale di passi dell’algoritmo:
(
)
(
( )
α)
α log log log 0 0 K K K K Np = = .Con i valori consigliati l’algoritmo termina in tre passi. 6. Tipo del file dataset
Testuale: “binario” o “testo”. 7. Numero di punti del dataset (N)
Intero lungo positivo. Teoricamente sono ammessi valori fino a 231 − . 1 8. Tipo dei punti del dataset:
Testuale: “double” o “integer”.
9. Dimensione in byte delle coordinate dei punti del dataset Intero positivo.
10. Frequenza di salvataggio dello stato
Intero. Indica quanti passi dell’algoritmo vengono eseguiti tra un salvataggio ed il successivo. Il valore 0 indica di non eseguire il salvataggio. La versione esegue il salvataggio dello stato ma non il recupero, quindi è necessario lasciare il valore 0. 11. Metodo di calcolo degli autovalori ( MCA )
programma è implementata anche una terza modalità, detta Mixed: si tratta di un compromesso tra precisione e rapidità, che usa il metodo di Householder fino al penultimo passo dell’algoritmo, mentre per il passo finale usa il metodo di Jacobi. 12. Progressive Random Sampling
Testuale: “prsON” o “prsOFF”. Indica al programma se applicare o meno una tecnica di progressive random sampling per l’assegnamento dei punti ai cluster. Se attivato, abbassa il tempo di esecuzione e diminuisce la qualità dei cluster prodotti. 13. Calcolo del Cluster Sparsity Coefficient
Testuale: “cscON” o “cscOFF”. Indica al programma se calcolare o meno il Cluster Sparsity Coefficient, dato da
∑
= ⋅ k i i i i U R C R k 1 ( , ) ) , ( 1 ε ε ,dove k è il numero di cluster, C è il cluster i -esimo, i U è l’intero dataset, R
( )
C,ε è l’energia proiettata del cluster C nel sottospazio ε . Questo calcolo, che non ha influenza alcuna sull’algoritmo vero e proprio, è computazionalmente pesante ed aumenta il tempo di esecuzione del programma.14. Basket Dataset flag1
Testuale: “bdON” o “bdOFF”. Indica al programma se applicare le varianti dell’algoritmo per dataset di tipo basket data (punti con molte coordinate nulle od uguali). Si raccomanda di settare il Basket Dataset flag solo se si ha la certezza che il dataset da partizionare sia di tipo basket data.
