Dopo l' introduzione del post precedente, oggi esamineremo la fase cruciale e maggiormente complessa di ogni algoritmo di Association Mining ovvero la fase di estrazione dei frequent pattern. Ricordo che i frequent pattern sono gli insiemi di prodotti che hanno supporto maggiore di quello minimo. Possiamo effettuare una prima classificazione degli algoritmi di frequent pattern mining individuando da una parte quelli che si basano su di un processo iterativo di generazione di itemset candidati, dall' altra quelli che calcolano i frequent pattern senza questo processo. 

ESTRAZIONE FREQUENT CON GENERAZIONE DEI CANDIDATI

Questa famiglia vede come capostite il noto e largamente diffuso algoritmo che va sotto il nome di Apriori. Da sottolineare come l'algoritmo Microsoft Association Rules incluso in Sql Server Analysis Services utilizzi una versione ottimizzata di Apriori (Agrawal, uno degli autori di Apriori, dal 2006 è un Microsoft Technical Fellow). Apriori si basa su di un principio, detto di antimonotonicità, che afferma un sottoinsieme di un frequent itemset è di sicuro frequente (presenta un supporto maggiore); questo principio apparentemente banale può essere espresso in una forma duale maggiormente interessante che afferma che se ho un itemset A ed un itemset sottoinsieme B di A, se B non è frequente allora A non può essere frequente. Piccolo esempio per capire meglio

{Latte,Birra} è un itemset frequente -->{Latte} e {Birra} sono frequenti

{Latte} non è frequente --> {Latte,Birra} non può essere frequente

Apriori utilizza un classico approccio Bottom-Up individuando iterativamente prima i frequent itemsets di cardinalità 1 (composti da un item), poi quelli di cardinalità 2 fino a quelli di cardinalità k (k-itemset); vengono in definitiva estesi i frequent aggiungendo un item alla volta fino a che non si arriva ad avere nessun itemset di cardinalità k che superi la soglia minima di supporto. Apriori si basa sulla generazione dei candidati; approfondiamo meglio che cosa siano i candidati e che relazione abbiano con i frequent itemset .

Supponiamo di avere 5 item {A,B,C,D,E} all' interno del nostro database transazionale composto da N transazioni; con 5 item il numero di possibili itemset che posso generare è pari a 2^5 = 32. Questi 32 itemset rappresentano i candidati, ovvero gli itemset che potranno o meno essere frequenti; lo spazio dei candidati rappresenta quindi lo spazio di ricerca all'interno del quale saranno presenti anche i frequent itemsets

La possibilità per i candidati di essere o meno frequente dipende dal loro supporto. In un primo tipo di approccio brute force viene calcolato il supporto di ogni candidato effettuando una scansione completa delle N transazioni del database. Supponendo di avere M candidati ed N transazioni la complessità risultante, il numero cioè di confronti da effettuare sarà pari circa ad O(MN). Calcolando che M=2^(NumDistinctItem) e che il numero di transazioni N è solitamente pari ad alcuni milioni, un approccio brute force (come al solito!!!) risulta inaccettabile. Vediamo quindi su quali fronti Apriori agisce. Innanzitutto Apriori sfrutta una euristica basata sul principio di antimonotonicità enunciato precedentemente, ovvero con riferimento allo schema precedente, se l'algoritmo di Apriori trova che l'itemset composto dall'elemento {A}  non è frequente allora elimina "a priori" i candidati che non potranno essere frequenti ovvero {A,B}, {A,B,C},{A,B,D},{A,B,E},{A,B,C,D},{A,B,C,E},{A,B,D,E},{A,B,C,D,E} poichè superinsieme di un itemset non frequente!! Apriori inoltre utilizza una struttura dati che va sotto il nome di HashTree che permette di conteggiare in modo efficace il supporto dei candidati. Vediamo adesso tramite un diagramma a blocchi come operi l'algoritmo Apriori

Commentiamo adesso il diagramma a blocchi sopra esposto; l'algoritmo inizia la propria esecuzione effettuando una scansione completa del database per determinare quali item (itemset con k=1) hanno un supporto maggiore della soglia minima; fatto questo si passa alla fase iterativa di esplorazione dello spazio dei candidati composta da due fasi:

1. Generazione a  partire dagli itemset frequenti L[k] di cardinalità k, dei candidati C[k+1] a cardinalità k+1. C[k+1] viene generato facendo il join di Lk con se stesso, considerando solamente gli itemset di lunghezza k+1 che contengono itemset distinti
2. Pruning dei candidati che presentano sottoinsiemi non frequenti (pruning apriori)

Queste fasi corrispondono ad una visita in ampiezza dello spazio dei candidati visto precedentemente in aggiunta a pruning dei sottoalberi qualora si verifichi la presenza di itemset non frequenti. Dopo aver generato i C[k+1] è necessario stabilire se questi candidati siano o meno frequenti (blocco rosso del diagramma); questa è la fase critica di tutto l'algoritmo in quanto ripeto, deve essere conteggiato il supporto dei candidati.Apriori oltre a ridurre il numero dei candidati per i quali deve essere conteggiato il supporto utilizza una struttura dati come detto in precedenza, che va sotto il nome di HashTree. L' HashTree è una struttura dati ibrida tra una hashtable ed una lista che permette di conteggiare in modo piuttosto efficiente il supporto dei candidati; non mi dilungo su questa struttura dati, vi darò qualche buona risorsa per approfondimenti. Una volta determinati quali siano i candidati frequenti questi vengono inseriti nel pool dei frequent finali, pool che contiene quindi frequent itemset con cardinalità diversa.

Dopo tutta questa parte algoritmica penso che sia opportuno mostrare con un semplice esempio come l'algoritmo operi su un semplice database giocattolo sul quale sia fissato come supporto minimo il 50%.

Analizzando Apriori possiamo mettere in evidenza alcuni bottleneck (questa è per te ginaluca!!!) che derivano principalmente dall'approccio di generazione dei candidati adottato. I candidati generati con un supporto relativamente basso possono essere decine se non centinaia di milioni, inoltre per effettuare il conteggio del supporto è necessario eseguire un numero di scansioni del database pari alla lunghezza del frequent pattern più lungo. Vediamo quindi adesso la seconda famiglia di algoritmi, quelli senza generazione dei candidati.

ESTRAZIONE FREQUENT SENZA GENERAZIONE DEI CANDIDATI

In questa famiglia di algoritmi, che non richiede la generazione dei candidati, rientra l'algoritmo maggiormente efficiente in fatto di Association Mining ovvero FPGrowth. In FPgrowth, il metodo di ricerca degli itemset frequenti si basa su una tecnica ricorsiva di tipo divide-et-impera, grazie alla quale il problema di trovare pattern frequenti lunghi (come accade in Apriori) si trasforma nel trovare dapprima quelli più corti (passo divide) per poi concatenarli tra loro (passo impera); questa logica permette di evitare completamente una fase di generazione dei candidati e quindi automaticamente anche il computo dei supporti (i passi più onerosi diApriori). Il funzionamento interno di FPgrowth ha ben poco in comune con quello iterativo di Apriori e si sviluppa lungo un albero ricorsivo nel quale ogni nodo è rappresentato da una particolare struttura dati detta FPtree. Questa struttura (albero di prefissi) memorizza in forma compatta e completa informazioni quantitative relative ai pattern frequenti. Ecco in sintesi come opera la ricorsione:

1. Al passo generico di ricorsione si genera l’FPtree tramite due precise informazioni: un sotto-database detto Conditional Pattern Base (o CPB)
   e un pattern prefisso alpha, entrambi ricavati al passo precedente. L’FPtree ottenuto è detto conditional FPtree. Il CPB è una proiezione del database originale nella quale si considerano solo gli item frequenti che co-occorrono insieme al pattern prefisso alpha. Il pattern prefisso è semplicemente una sequenza di item frequenti
2. Dall’FPtree così calcolato, se non vuoto, si ricavano n CPB ad esso associati e si estende il pattern prefisso alpha ricevuto con un opportuno item frequente Bi, specifico del CPBi i-esimo. Si ottengono quindi n coppie {CPBi, alpha U Bi}.
3. Si effettuano n chiamate ricorsive al punto 1,una per ogni singola coppia

Il passo di inizializzazione (radice della ricorsione) prevede la costruzione di un FPTree direttamente dal database originale e da un pattern frequente nullo

Detto questo vi lascio alcuni fonti da dove reperire ulteriori informazioni specialmente per FPGrowth che ho solamente introdotto; come elaborato per un esame del mio corso di studi insieme al mio collega Gianluca Ghettini abbiamo implementato e comparato in c# sia Apriori che FPGrowth; questo compito ha portato alla creazione di un progetto su codeplex che va sotto il nome di FPMiner dove è possibile sia scaricare i sorgenti degli algoritmi sopra esposti che la relazione finale dove vengono approfonditi gli algoritmi che vi ho illustrato effettuando una approfondita analisi delle performance.

Ad maiora...