A Monica,
senza di lei non sarei arrivato qui.
(E se ci fossi arrivato avrei scritto solo la dedica successiva)


This thesis is affectionately dedicated
to the Amiga500 computer once installed at my home,
with whom I have spent many pleasant evenings.

Introduzione

Con l’evoluzione della tecnologia diventano sempre più importanti le tecniche che permettono di analizzare in modo automatico i dati.

Spesso infatti è semplice poter accedere a grandi moli di dati che descrivono un fenomeno ma essi si presentano in una forma eterogenea, ridondante e non strutturata, che rende impraticabile un’analisi "manuale".

Tutto ciò fa sì che solo una piccola parte di essi venga efficacemente sfruttata.

Uno dei motivi per cui si è sviluppato il Machine Learning anche al di fuori del mondo accademico è esigenza di sfruttare il patrimonio informativo contenuto nell’immensa mole di dati a cui possiamo avere accesso.

L’utilizzo delle tecniche di machine learning permette l’individuazione automatica delle associazioni "nascoste" presenti all’interno dei dati. L’obiettivo diventa quindi la scoperta ed individuazione di patterns, modelli e relazioni e di estrarne conoscenza, in termini di informazioni significative ed immediatamente utilizzabili.

Il data mining è una delle attività cruciali per la comprensione, la navigazione e lo sfruttamento dei dati nella nuova era digitale. (Ushama Fayyad)

Un albero di classificazione è un classificatore che può essere rappresentato con una struttura ad albero.

Comparsi per la prima volta in letteratura col lavoro di Quinlain del 1986 sono diventati in breve tempo uno dei metodi più utilizzati l’analisi e la ricerca di pattern nei dataset.

I vantaggi che presentano gli alberi di classificazione rispetto ad gli altri tipi di classificatori sono la robustezza al rumore e la capacità di trattare automaticamente attributi ridondanti o non rilevanti.

Oltre a questo il loro punto di forza è il presentarsi con una struttura facilmente leggibile e simile al modo in cui un umano si approccerebbe a un problema di classificazione. E’ infatti possibile rappresentarli con un albero o trasformarli in un sistema a regole.

Questo tipo di classificatori presentano però anche dei lati negativi, essendo basati su ricerche greedy producono un partizionamento ricorsivo del dataset che riduce di molto la taglia del dataset nei livelli più profondi dell’albero, provocando il fenomeno dell’overfitting.

Per evitare di ritrovarsi con un dataset troppo ristretto la soluzione più ovvia è partire da uno molto grande ma questo impone tipicamente dei tempi di calcolo proibitivi.

Col tempo si sono sviluppate diverse alternative alla costruzione di alberi sull’intero dataset alcune delle quali fanno uso degli algoritmi evolutivi.

Uno degli approcci più efficaci presenti in letteratura che usa questa strategia è GAIT. Gait evolve alberi generati con C4.5 riuscendo a migliorarne le prestazioni, produce però alberi particolarmente grandi che soffrono del fenomeno del Bloat (l’aumento incontrollato della dimenzione dell’albero senza avere in cambio un aumento delle prestazioni).

In questa tesi cercherò di migliorare i risultati di Gait producendo alberi più corti e privi di bloat che permetteranno quindi di ottenere le stesse performance di classificazione con tempi di classificazione minori.


Precedente Successivo


Copyright © 2014 Vincenzo La Spesa

Torna su