logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-11172003-174953


Tipo di tesi
Tesi di laurea vecchio ordinamento
Autore
Piastra, Manuele
Indirizzo email
manupia@libero.it
URN
etd-11172003-174953
Titolo
CURE+: un'implementazione dell'algoritmo di clustering gerarchico agglomerativo CURE con riferimento all'analisi di grandi volumi di dati
Dipartimento
INGEGNERIA
Corso di studi
INGEGNERIA INFORMATICA
Relatori
relatore Lazzerini, Beatrice
Parole chiave
  • agglomerativo
  • algoritmo
  • BIRCH
  • cluster
  • cluster analysis
  • clustering
  • CURE
  • CURE+
  • data mining
  • gerarchico
  • Heap
  • KD-Tree
  • knowledge discovery
Data inizio appello
18/12/2003
Consultabilità
Completa
Riassunto
La quantità di dati a nostra disposizione, in qualsiasi settore dello scibile umano (scientifico, medico, demografico, finanziario, commerciale etc.) è diventata tale da
richiedere un'enorme quantità di tempo per essere analizzata con profitto. Poiché
l'attenzione umana è diventata una risorsa preziosa, è necessario disporre di metodi
automatici per analizzare, classificare e compendiare i dati. Tali tecniche devono essere in grado di evidenziare distribuzioni di interesse contenute nei dati ed eventuali anomalie e singolarità.

Quest'impellente esigenza ha fatto sì che oggi l'analisi dei dati impegni ricercatori di varie discipline: statistica, intelligenza artificiale, machine learning e data mining. Il
clustering, nell'ambito del data mining, è utilizzato per scoprire pattern di interesse nei
dati, soprattutto quando il loro volume ponga requisiti stringenti, se vogliamo mantenere
accettabili le prestazioni degli strumenti utilizzati.

Il lavoro di tesi da noi proposto consiste nell'implementazione dell'algoritmo di clustering gerarchico CURE. CURE+, il software a tale scopo realizzato, è un'applicazione per i sistemi operativi facenti parte della famiglia Microsoft Windows, sviluppata utilizzando il
linguaggio di programmazione C++ nell'ambito dell'Integrated Development Environment
Microsoft Visual Studio .Net.

Nei capitoli 1 e 2 illustriamo la nomenclatura e i concetti generali che stanno alla base del clustering.

Nel capitolo 3 descriviamo più in dettaglio cosa si intenda per clustering gerarchico e quali sono i vantaggi che tale strumento è in grado di offrire.

Nel capitolo 4 proponiamo invece una descrizione (tutt'altro che esaustiva) dell'algoritmo di clustering gerarchico agglomerativo BIRCH. Riteniamo che tale descrizione possa essere utile, in quanto BIRCH è stato il primo algoritmo di tipo gerarchico che si è prefisso l'obiettivo di rendere scalabile la complessa analisi dei dati nei confronti di grandi database. BIRCH costituirà il nostro trampolino di lancio per l'introduzione dell'algoritmo CURE, che ne raccoglie l'eredità pur cercando di limitarne gli inconvenienti.

Nel capitolo 5 passiamo dunque all'esposizione di una dettagliata descrizione dell'algoritmo CURE.

Nel capitolo 6 illustriamo in dettaglio l'interessante struttura dati kD-Tree e la sua versione randomizzata, denominata rkD-Tree.

Nel capitolo 7 passiamo, senza ulteriori indugi, all'esposizione approfondita di CURE+, illustrando gli strumenti, i metodi, le scelte e le innovazioni da noi effettuate durante lo sviluppo di tale applicazione.

Infine nel capitolo 8 forniamo una breve descrizione dei risultati forniti dall'analisi
effettuata da CURE+ su un file contenente dati di prova.
File