Monotone constraint pushing in frequent pattern mining
Autore
Alessio Mazzanti - Università degli Studi di Pisa - [2002-03]
Documenti
Abstract
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.
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.
Questa tesi è correlata alle categorie
segnala questa pagina ::.