WetBlog

Download gratuto: Data Structure and Algorithms eBook

Luca Del Tongo — Wed, 27 Aug 2008 17:45:03 GMT

E' con grande piacere che dopo alcuni mesi di gestazione insieme al mio amico Granville, abbiamo pubblicato il libro

Data Structures and Algorithms: Annotated Reference with Example.

Allo stato attuale il libro è ancora un work in progress ma personalmente sono soddisftatto di come sia evoluto nel corso del tempo (sono un pò di parte... ). Il libro è rivolto a tutti coloro che conoscono un linguaggio di programmazione ad oggetti, senza particolari requisiti; l'utilizzo dello pseudo codice pone infatti l'attenzione sulla parte algoritmica piuttosto che su quella di implementazione. La scelta di renderlo totalmente free è data dalla convinzione che fosse la cosa più giusta:) Sono ben accetti quindi consigli suggerimenti etc. etc.

A livello personale, scrivere un libro in inglese non è stato cosi semplice ma sicuramente sono esperienze che servono ad ampliare i proprio orizzonti, collaborare poi con Granville per me è un piacere ed uno stimolo ad un continuo miglioramento.... quindi spread the word!!!!

[EDIT] Ricordo che io, e sopratutto Granville, abbiamo provveduto ad implementare in C# tutti gli algoritmi e le strutture dati presenti nel libro; potete trovare l'implementazione su codeplex al seguente indirizzo

http://codeplex.com/dsa

Technorati Tag: .NET,Data Structure

Padre e figlio ... le dimensioni e le prestazioni contano

Luca Del Tongo — Mon, 30 Jun 2008 12:53:59 GMT

Per il compleanno di mia sorella ed in vista della sua imminente partenza per Dublino, ho deciso di regalarle un Asus Eee PC 900; ho acquistato la versione con installato linux per avere 20 Gb di memorizzazione SSD (2 schede 4+16). Sono molto soddisfatto dell'acquisto fatto anche se ho dovuto sperimentare alcune specifiche non documentate su cui i produttori come al solito giocano un pò. Dato che mia sorella utilizza regolarmente Windows XP ho deciso in un primo momento di installare suddetto OS.... ho così ottenuto un computer con delle buone performance.... qualche cosa però dentro di me mi ha spinto verso una soluzione un pò più estrema.... il risultato lo vedete qui sotto (cliccare sull'immagine per immagine originale)

Analizzando le specifiche tecniche dell' Eee PC 900 possiamo osservare come questo sia dotato di un Gb di RAM e di un Celeron 900... quindi non proprio in linea con i requisti minimi richiesti da Windows Vista..... ma nell'era della customizzazione perchè non scegliere di farsi un bel Vista su misura eseguendone una vera e propria ricompilazione? Eccoci giunti al punto, utilizzando il mitico Vlite. Questo software permette di selezionare le feature di interesse rimuovendo caratteristiche di Windows non necessarie... fatto questo dato che l'eepc non dispone di un lettore CD ho dovuto selezionare una installazione tramite penna USB.... a questo punto eseguo l'installazione di Vista selezionando come disco SSD quello da 16 Gb..... installo tutti i driver e i software necessari (Office 2007, Messenger, Skype etc...) però nota che il sistema è lento .... troppo lento ..... a questo punto mi sono detto... ecco Luca sei il solito testone... ma online ho scoperto che nn solo l'unico... confortato da questo post ho eseguito un breve performance test su entrambi i dispositivi SSD e ho scoperto... che le performance di accesso e trasferimento dati tra i due hanno prestazioni molto diverse... la scheda SSD da 4 Gb offre prestazioni nettamente superiori... quindi l'installazione del' OS deve essere effettuata su quel disco... essendo da 4 Gb è necessario usare VLite per rimuovere le parti nn necessarie... fatto ciò ho eseguito una nuova installazione, ho ottimizzato la configurazioni dei services, ho ridotto al minimo gli aspetti grafici, ho spostato lo swap file sul disco da 16 Gb e finalmente sono arrivato ad avere un sistema con delle buone performance, come potete osservare nel video che ho registrato :)

[University Stuff] Simple NAry Tree

Luca Del Tongo — Thu, 26 Jun 2008 17:01:37 GMT

In questi giorni, per un esame di algoritmi distribuiti ho avuto la necessità di lavorare con un particolare albero nario. Genericamente un albero nario è un albero in cui ogni nodo presenta al massino n figli. Un albero binario è un caso particolare di albero nario dove n=2; in figura viene mostrato un albero 3ario.

Vediamo come realizzare un semplice albero nario che permetta di specificare il fattore di ramificazione e che permetta di inserire nodi all'interno dell' albero in modo tale che l'albero venga riempito livello per livello (prima ci creare un nuovo livello si porta a saturazione il livello corrente). Prima di passare alla definizione dell' albero voglio ricordare come un albero nario possa contenere un numero massimo di nodi per una certa altezza h pari a:

MaxNumNodi = N^(h+1)-1/N-1

In riferimento alla figura sopra esposta possiamo osservare che con N=3 ed h=2 otteniamo un numero massimo di nodi pari a 13. Passiamo adesso alla definizione del nostro albero. Per prima cosa definiamo due classi: una container che rappresenta l'albero ed esponde le funzionalità ed una che rappresenta i nodi all'interno di un albero.

   1: public class NAryTree<T> where T:IComparable<T>

   2:     {

   3:         public NAryNode<T> root { get; set; }

   4:         public int branchFactor { get; set; }

5:

   6:         public NAryTree(T rootValue, int BranchFactor)

   7:         {

   8:             branchFactor = BranchFactor;

   9:             root = new NAryNode<T>(rootValue, branchFactor);

  10:         }

  11:         .

  12:         .

  13:         .

  14:     }

Come possiamo vedere la classe generica NAryTree tiene traccia della radice dell'albero e del fattore di ramificazione (numero di figli o arità). La constraint sul tipo generico in realtà nn viene utilizzata in quanto non si ha ordinamento parziale tra gli elementi ma serve come base per un eventuale albero nario di ricerca. Passiamo adesso alla classe NAryNode:

   1: public class NAryNode<T> where T:IComparable<T>

   2:     {

   3:         public T value { get; set; }

   4:         public int childnum { get; set; }

   5:         public NAryNode<T>[] childs { get; set; }

6:

   7:         public NAryNode(T Value, int branchFactor)

   8:         {

   9:             value = Value;

  10:             childnum = branchFactor;

  11:             childs = new NAryNode<T>[branchFactor];

  12:         }

  13:     }

Anche la definizione di questa classe risulta abbastanza semplice.... abbiamo una property che memorizza il valore del nodo, un array di nodi figlio ed ancora una proprietà che mi informa sul numero di nodi figlio (proprietà ridondante avendo memorizzato questa info per la classe NaryTree ). Vediamo adesso come inserire per livelli i nodi all'interno dell' albero...

   1: public void Insert(T value)

   2:        {

   3:            NAryNode<T> firstFreeNode = FindFirstFreeNode(root);

   4:            firstFreeNode.childs[CountImmediateChildren(firstFreeNode)] = new NAryNode<T>(value, branchFactor);

   5:        }

6:

   7: private int CountImmediateChildren(NAryNode<T> node)

   8:        {

   9:            int count = 0;

  10:            for (int i = 0; i < node.childnum; i++)

  11:            {

  12:                if (node.childs[i] != default(NAryNode<T>))

  13:                    count++;

  14:            }

  15:            return count;

  16:        }

17:

  18:        private NAryNode<T> FindFirstFreeNode(NAryNode<T> root)

  19:        {

  20:            //BREADTH FIRST WAY!!!!

  21:            Queue<NAryNode<T>> row = new Queue<NAryNode<T>>();

  22:            row.Enqueue(root);

  23:            while (row.Count > 0)

  24:            {

  25:                NAryNode<T> currentNode = row.Dequeue();

  26:                if (CountImmediateChildren(currentNode) < root.childs.Length)

  27:                {

  28:                    return currentNode;

  29:                }

  30:                for (int index = 0; index < CountImmediateChildren(currentNode); index++)

  31:                {

  32:                    row.Enqueue(currentNode.childs[index]);

  33:                }

  34:            }

  35:            return default(NAryNode<T>);

  36:        }

Per eseguire l'inserimento ho usato una tecnica molto brute force che nn fa altro che reperire il primo nodo che ha ancora spazio libero tra i propri figli ed eseguire su di esso l' inserimento.... una tecnica più efficiente consiste nel tenere all'interno della classe NaryTree un riferimento all' ultimo nodo inserito in modo tale che ad ogni inserimento non venga fatta una scansione dell' intero albero per trovare il nodo su cui fare l'inserimento. Unica cosa degna di nota è l'ottimizzazione in termini di allocazione dello stack di sistema eseguita all'interno della funzione FindFirstFreeNode grazie all'uso di una coda dove per ogni livello vengono accodati i vari nodi. A questo punto allego la solution dove potete trovare l'intero codice comprensivo di test ed una piccola demo winform che utilizza la libreria GLEE. Se ritenete opportuno avere un'implementazione seria di albero nario lasciate un feedback che magari verrà presa in considerazione come feature da aggiungere all'interno di DSA

Opportunità lavoro Avanade Italia

Luca Del Tongo — Tue, 24 Jun 2008 13:42:31 GMT

Avanade Italia, attraverso un programma che va sotto il nome di Avanade Academy, offre posti di lavoro per favorire l'ingresso nel mondo del lavoro di neolaureati in Ingegneria, Informatica, Matematica e Fisica. I neoassunti cominceranno la propria carriera nell’ambito della consulenza tecnologica, partecipando ai progetti presso le aziende clienti, occupandosi dello sviluppo di soluzioni applicative in ambiente Microsoft a supporto del business

Chi è interessato può avere ulteriori informazioni e proporre la propria candidatura direttamente dal sito Student to Business. Le opportunità ci sono, è compito quindi di noi studenti dimostrare o meno il proprio valore.....

Ad maiora...

Joining DSA project

Luca Del Tongo — Mon, 02 Jun 2008 14:58:29 GMT

Sono appena entrato a far parte del progetto DSA (Data Structure and Algorithms) giunto in questi giorni alla versione 0.5. Far parte di questo progetto per me è uno stimolo davvero interessante e per questo ringrazio il mio amico Granville Barnett, fondatore del progetto. Compito della libreria DSA è quello di cercare di colmare le lacune presenti all' interno della BCL in quanto ad algoritmi e strutture dati. In questi giorni stiamo lavorando con Granville per decidere quali strutture ed algoritmi implementare sino al rilascio della versione 1.0. Devo subito dire che la metodologia TDD adottata da Granville aiuterà a raffinare il mio coding style e spero di accumulare ulteriore esperienza da questo connubio. Se avete idee o suggerimenti vi rimando al forum del progetto.

Technorati Tag: .NET,Algorithm

DevCon 2008 Review and beyond

Luca Del Tongo — Mon, 02 Jun 2008 14:26:46 GMT

Anche questo anno ho avuto la fortuna di partecipare a DevCon e devo dire che come per lo scorso anno il bilancio è decisamente positivo. Innanzitutto sembra strano ma anche in questo caso, avere già l'esperienza di una devcon alle spalle ha sicuramente giovato sia nella scelta delle sessioni da seguire (2 track parallelle) che nell' aver acquisito una certà familiarità con alcuni dei concetti esposti. Senza entrare troppo nel dettaglio cercherò di evidenziare alcune riflessioni personali nate dalle sessioni che ho seguito.

WCF

Per quanto riguarda WCF, c'è davvero poco da dire in quanto i benefici che questa piattaforma ha portato nello sviluppo di applicazioni distribuite è sin troppo evidente. Delle tre sessioni che ho seguito, quella in cui Paolo ha illustrato i concetti maggiormente nuovi ed interessanti per me è sicuramente "WCF Web Centric". Durante i primi minuti della sessione Paolo ha fatto un bel ripasso su come funziona il protocollo HTTP, evidenziando le caratteristiche e le differenze in termini di payload fra i vari metodi che presenta (HTTP POST,HTTP GET, HTTP PUT...); questo succulento ripassino ha portato all' introduzione dell'architettura REST e di come sia possibile definire dei tipi di Web Service secondo questo stile architetturale. Personalmente il messagio che ho colto è quello che REST anche se meno formale nella definizione dello scambio dei dati, basandosi sulle intestazioni delle GET e delle POST, permette di utilizzare in modo leggero i meccanismi di request e response alla base del Web, sfruttando un semplice meccanismo legato alle URI. La sessione è proseguita contestualizzando questi concetti all'interno di uno scenario di interazione fra un servizio web ed una pagina ASP.NET basato sulla nuova Syndication API.

WF

Seguendo le sessioni di Rob, ho capito come Workflow Foundation sia uno strumento tanto bello e potente quanto complicato; avere una strumento a disposizione che permette di gestire flussi di informazioni tramite sia diagrammi sequenziali che diagrammi a stati finiti, apre scenari davvero interessanti. Come giustamente Rob ha evidenziato WF essendo uno strumento "general purpose", rappresenta davvero una strumento pervasivo capace di trovare applicazione in scenari eterogenei accumunati dal basilare concetto di flusso; può quindi essere applicato ad esempio per definire il flusso di navigazione all'interno di un sito Web ma al tempo stesso anche per definire ad esempio gli stati di un casello autostradale. Detto questo, WF lavora principalmente in asincrono e già secondo me qui nascono le prima gioie e dolori. Asincrono è sinonimo di efficienza e ottimizzazione ma lato developer secondo viene visto come perdita del controllo, delle precedenti conoscenze; WF si appoggia su un meccanismo di persistenza che offre fault tolerance da una parte ma al tempo stesso può rappresentare se nn correttamente configurato il famigerata bottleneck applicativo. Quello che Rob "penso" abbia messo in evidenza, specie nella sezione di ottimizzazione è come sia necessario riuscire a trovare quel giusto trade off tra affidabilità e performance magari ricorrendo ad un meccanismo di scheduling manuale in cui la gestione dei thread sia quindi a carico dello sviluppatore. Sono stati inoltre mostrate alcune configurazioni che permettono di aumentare leggermente le performance anche se alla fine i fattori che maggiormente entrano in gioco sono l'accesso in I/O su disco in fase di persistenza e caricamento dello xoml.

WEB DEVELOPMENT

La parte di sviluppo Web, sia comprendente tecnologie attuali che future, è stata coperta dalle sessioni di Luka e Rob. Lo sviluppo web come al solito è pieno di insidie e spesso gli scenari in cui il requisito principale è la scalabilità, richiedono conoscenze approfondite sia del funzionamento del web che delle varie tecnologie presenti. Condivido il pensiero secondo cui ultimamente stiamo un pò "tirando il collo" al web che in effetti solo apparentemente mostra una veste 2.0. E' in questa ottica che vedo bene l' inserimento di Silverlight 2.0; sicuramente la strada da fare per recuperare il gap nei confronti di Flash è notevole ma Silverlight può beneficiare di una base solida come il framework .NET che Flash non possiede. A livello di mera multimedialità magari ad oggi verterei sull' utilizzo di Flash, per realizzare una applicazione web senza particolari requisiti di retrocompatibilità o scadenza sicuramente opterei per Silverlight. All' interno della sessione di chiusura della conferenza sono state prese in rassegna anche le ultimissime tecnologie quale ASP.NET Dynamic Data, Astoria ed ASP.NET MVC. Quello che ho seguito con più attenzione è naturalmente MVC poichè incarnando i principi di Separation of Concern favorisce lo sviluppo e il testing del codice prodotto. Chiudo con un monito: mai usare le session!!!!!

LINQ

Quando il gioco si fa duro Linq comincia ad interrogare... avere a disposizione uno strumento per eseguire query indipendentemente dalla sorgente dati non ha prezzo. Da studente le mie attenzioni erano rivolte maggiormente a LINQ To Objects poichè rivoluziona il modo con cui si scrive codice e si implementano i vari algoritmi. Concetti cardine, che stanno alla base di LINQ, quali ad esempio Expression Tree, hanno radici molto lontane che ricalcano i passi compiuti dagli odierni compilatori. Per quanto concerne la diatriba tra LINQ To Sql vs Linq To Entities io sto dalla parte di NHibernate... senza offese ma allo stato attuale delle cose se devo utilizzare perchè necessario un ORM, Linq To Sql non lo ritengo un "ORM for Dummies", non è proprio un ORM; Linq To Entities avrebbe le caratteristiche per essere un ORM ma l' implementazione che è stata fatta rovina l'approccio POCO e di Persistence Ignorancy che altri ORM offrono. Mi hanno inoltre fatto osservare come nei casi reali il degrado di performance che NHibernate introduce a causa dell'utilizzo di reflection sia elevato penso però che il vero collo di bottiglia sulle performance di accesso ai dati sia come al solito il disco i cui tempi di accesso sono di qualche ordine di grandezza superiore rispetto alla memoria principale.

PARALLEL PROGRAMMING

Questa bonus session capeggiata da Marco, è stata quella che sicuramente dal punto di vista della programmazione in senso lato maggiormente mi ha impressionato. Da una parte la possibilità di sfruttare attraverso una libreria come PLINQ le potenzialità delle macchine multicore affascina non poco, dall' altra però si aprono scenari in cui il MultiThread è all' ordine del giorno e penso che le competenze e l'acume richiesto ad un programmatore sia davvero troppo elevato per non incorrere in errori non predicibili a compile time che magari si verificano sporadicamente a runtime. Molto interessante inoltre il confronto tra le scelte architetturali effettuate all'interno di Microsoft Robotics e PLINQ stesso.

Concludo con un doveroso ringraziamento alla DevLeap Gang of Four ed un saluto a Cristian, Guido, Jessica, Sergio ed Alberto. Alla goccia DevCon!!!!

Technorati Tag: DevCon,.NET,NHibernate

Nth Root

Luca Del Tongo — Sun, 18 May 2008 10:47:42 GMT

In questo post mostro poche linee di codice che permettono di calcolare la radice ennesima (nth-root) di un numero in C#. Prima di buttar giù queste righe di codice mi sono chiesto se nel framework ci fosse qualche cosa che facesse al caso mio... risposta negativa :( Con l' ausilio di un pò di matematica però si può ovviare a ciò, sfruttando la definizione di logaritmo e le proprietà che lo legano alla funzione esponenziale. Possiamo infatti scrivere:

La dimostrazione di questa formula è piuttosto semplice in quanto la prima uguaglianza è una proprietà che deriva dalla nozione di base di radice, mentre la seconda relazione può essere dimostrata applicando il logaritmo ad ambo i membri.

   1: class Program

   2:     {

   3:         static void Main(string[] args)

   4:         {

   5:             int a, n, x;

   6:             a = n = x = 0;

   7:             a = 243;

   8:             n = 5;

   9:             //radice quinta di 243 = 3^5;

  10:             x =(int)Math.Round(Math.Exp(Math.Log(a, Math.Exp(1))/n));

  11:         }

  12:     }

Nunc est bibendum...

Technorati Tag: .NET,C#

Data Mining Algorithms : Microsoft Association Rules Revealed

Luca Del Tongo — Wed, 16 Apr 2008 17:01:37 GMT

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:

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
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:

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
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}.
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...

Technorati Tag: Data Mining,AI

Data Mining Algorithms : Microsoft Association Rules Introduction

Luca Del Tongo — Tue, 15 Apr 2008 15:57:04 GMT

Oggi voglio analizzare ed illustrare uno dei task maggiormente ricorrenti quando si ha a che fare con operazioni di Data Mining, l' Association Mining. Farò riferimento sia all' implementazione fornita all' interno della suite di algoritmi di Data Mining inclusi in SSAS che ad ulteriori approcci maggiormente efficienti.Defiamo innanzitutto che cosa sia l'Association Mining con riferimento a possibili contesti applicativi.

Un algoritmo di Association Mining permette di identificare all' interno di un insieme di prodotti (itemset) delle regole che correlano la presenza di un insieme di prodotti con quella di un altro insieme; vengono quindi dapprima estratti dei pattern frequenti e successivamente create delle regole di associazione che descrivono come i vari item (item) co-occorrano all' interno ad esempio di un database transazionale. Chiariamo meglio il concetto con un esempio autoesplicativo; supponiamo di dover effettuare data mining su un database transazionale di un supermercato (scusate l'originalità!!!); gli acquisti dei clienti del supermercato vengono quindi memorizzati come transazione nel database transazionale; ogni transazione conterrà quindi una lista di item (latte,birra,mele....) acquistati da un cliente in una visita al supermercato

Lo schema precedente illustra le due fasi principali che caratterizzano un algoritmo di Association Mining. La fase computazionalmente più onerosa e critica per le prestazione dell' intero sistema è la prima ovvero quella in cui si cerca di estrarre i pattern frequenti( itemset con supporto maggiore della soglia di supporto minimo). Per comprendere meglio la terminologia presente nello schema dobbiamo dare alcune definizioni che ci permettono di descrivere lo scenario di mining in termini maggiormente appropriati; gli elementi che entrano in gioco sono:

Un insieme I= i1,i2,i3....iN di item distinti
Una transazione T vista come sottoinsieme di I, T c I
Una regole associativa espressa nella forma A-->B dove A e B sono itemset tali che AcT, BcT ed A intersezione B={insieme vuoto}

Per eseguire l'estrazione dei pattern frequenti e delle regole di associazione si utilizzano due indici che vanno sotto il nome di Supporto e Confidenza(Probabilità)

Supporto (Support)
- Misura statistica che fornisce la popolarità di un itemset, viene quindi definito per un itemset A come numero di transazioni checontengono A rapportato al numero di transazioni totali
Confidenza (Conf)
- Misura statistica legata ad un regola di associazione, indicata talvolta come probabilità condizionata, rappresenta la probabilità condizionale che una transazione che include un itemset A ne includa anche un altro B

Come al solito un semplice esempio con riferimento alla tabella transazionale mostrata nello schema precedente ci farà prendere confidenza con gli indici di Supporto e Confidenza. Supponiamo di voler calcolare le due grandezze per la regola di associazione che ha come antecedente l' itemset composto da {Pannolini,Latte} e come conseguente {Birra}

Pannolini,Latte --> Birra

Cominciamo calcolando il supporto dell' itemset composto da {Pannolini,Latte,Birra} per poi utilizzarlo all'interno del calcolo della confidenza della regole

Support(Pannolini,Latte,Birra) =NumTransazioni(Pannolini,Latte,Birra)/NumTotaleTransazioni=2/5

Conf(Pannolini,Latte-->Birra) = Support(Pannolini,Latte,Birra)/Support(Pannolini,Latte) = 2/3 = 0.66 = 66%

La regola di associazione sopra esposta ci dice quindi che con buona probabilità (66%) un cliente che compra dei pannolini e del latte comprerà anche la birra. Per avere un'analisi qualitativa di un certo rilievo tutti i vari algoritmi di frequent pattern mining ricevono quindi come parametri di input due soglie relative al supporto ed alla confidenza minima ammissibili. Voglio evidenziare come anche all' interno di Sql Server Analysis Service sia possibile specificare il supporto e la confidenza minima anche se non è possibile assegnare valori arbitrariamente bassi in quanto SSAS effettua una stima in base alla potenza di calcolo presente sulla macchina definendo dei valori limite. Solitamente ad esempio in scenari commerciali non si scende al di sotto del' 1% di supporto. Riassumendo quanto visto finora gli algoritmi di association mining fungono da vero e proprio motore di conteggio di correlazione.

Nel prossimo post verranno analizzati gli approcci che si possono adottare nel determinare gli itemset frequenti...

Technorati Tag: Data Mining,AI

Academic Club restart

Luca Del Tongo — Mon, 11 Feb 2008 18:04:30 GMT

Dopo un paio di mesi di lavoro e sbattimenti con Photoshop, Expression Web ed infine con l'sdk di Community Server 2007, sono riuscito a mettere online la nuova versione (quasi completa) del portale dedicato ad Academic Club, associazione composta da studenti e ricercatori che condividono la passione per il framework .NET;

Ringrazio i ragazzi di DotNetMarche per gli ottimi appunti messi a disposizione e prometto che appena ho un pò di tempo, scriverò una survival guide per chi decida di avventurarsi nella creazione di un tema custom from scratch per Community Server; il portale contiene alcuni webcast interessanti, nei prox giorni ne metteremo online altri;

Ad maiora...