Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Monotone constraint pushing in frequent pattern mining

L’estrazione di patterns frequenti da databases di grandi dimensioni gioca un ruolo essenziale in molti compiti di data mining e risulta utile per una vasta gamma di applicazioni.
Molti degli algoritmi sviluppati nella direzione del frequent pattern mining hanno dimostrato grande efficacia nel far fronte alla soluzione di questa categoria di problemi. Tuttavia, a seconda dei dati in input, molte applicazioni pratiche possono risultare intrattabili, a fronte della intrinseca complessità del problema.
Grazie al recente sviluppo di alcune tecniche di constraint pushing, è possibile spingere nel profondo del calcolo alcune categorie di vincoli, catturando così la semantica di una specifica applicazione. L’ausilio di queste tecniche consente di ridurre sensibilmente l’esplorazione dello spazio di ricerca e dunque il costo computazionale della maggior parte degli algoritmi per frequent pattern mining.
I vincoli incorporabili nella estrazione di patterns frequenti possono essere suddivisi in categorie differenti a seconda delle proprietà che essi rispettano.
Ad ogni specifica categoria, risulta naturalmente associata una strategia di pushing, sfruttabile con ogni vincolo o congiunzione di vincoli appartenenti a tale categoria.
La possibilità di sfruttare valide tecniche di pushing rivolte a vincoli appartenenti ad una specifica classe non estingue tuttavia la possibilità di fallire, nel tentativo di focalizzare l’estrazione di patterns frequenti in porzioni interessanti dello spazio di ricerca. Il predicato complessivo che detiene la semantica di un’applicazione è infatti il risultato della congiunzione di vincoli che in generale appartengono a classi differenti. Il tentativo spontaneo di applicare contemporaneamente, su uno stesso dominio, tutte le tecniche di pushing del caso, può condurre addirittura ad esplorare una porzione di spazio di ricerca superiore a quella che normalmente verrebbe esplorata da un usuale algoritmo per frequent pattern mining. Questo ragionamento è in particolare rivolto a compiti di mining che risultano semanticamente associati a congiunzioni di vincoli antimonotoni (come il tipico vincolo di frequenza) e vincoli monotoni.
L’obiettivo di questa tesi è affrontare il problema appena delineato, introducendo un nuovo algoritmo di pre-processing e due nuovi algoritmi level-wise. I procedimenti di calcolo che vengono presentati affrontano il problema dello sfruttamento contemporaneo di antimonotonia e monotonia per diverse condizioni dei parametri in input e basando l’approccio sullo sfruttamento di euristiche nuove e diverse da algoritmo ad algoritmo.
Risultati sperimentali mostrano che le nuove metodologie adottate consentono di superare su tutti i fronti le performance degli algoritmi preesistenti.

Mostra/Nascondi contenuto.
1Overview The problem studied is how to push monotone constraints in frequent pattern mining task. The results are three different algorithms that altogether attack effectively the problem for every kind of the input data : - ExAnte (accepted for publication at PKDD’03 and SEBD’03) - ExAMiner (submitted for publication at ICDM’03) - ACP (accepted for publication at PKDD’03)

Tesi di Laurea

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Alessio Mazzanti Contatta »

Composta da 198 pagine.

 

Questa tesi ha raggiunto 490 click dal 20/03/2004.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.