Giuseppe GIORDANO | Progetti

STUDIO DELLE PROPRIETÀ DELLE REGOLE DI ASSOCIAZIONE ESTRATTE DA GRAFI BIPARTITI

Il progetto di ricerca si propone di analizzare lo studio delle proprietà statistiche delle regole di associazione derivate da una matrice di transazioni definita in termini di matrice di incidenza, così da sfruttare le proprietà della teoria dei grafi. Una matrice di incidenza è rappresentabile come un grafo bipartito dove i due set di nodi rappresentano rispettivamente gli oggetti attivi della transazione (ad esempio dei consumatori) e gli oggetti passivi (ad esempio dei beni o dei prodotti).Le regole si basano sui link che collegano i due set di nodi e definiscono delle implicazioni basate sulle co-occorrenze di transazioni per i diversi elementi. Le tipiche misure statistiche della qualità delle regole estratte da un grafo bipartito, note come “confidenza” e “supporto” possono essere interpretate in termini di statistiche di rete.Ad esempio, la regola X->Y indica che nelle transazioni in cui compare X, compare anche Y. Il "supporto" indica la percentuale di transazioni che contengono entrambe X ed Y. La "confidenza" indica, date le transazioni che contengono X, qual è la percentuale di transazioni che contengono Y.L’obiettivo del presente progetto è quello di affiancare a queste misure classiche, nuove misure derivate dalla Network Analysis. Dato che le matrici delle transazioni sono notoriamente di dimensioni molto elevate e tipicamente di forma sparsa, opportuni metodi per la gestione degli aspetti computazionali saranno individuati e affrontati.Una possibilità in tal senso è quella di ridurre il database iniziale in sottoinsiemi utilizzando tecniche e algoritmi di classificazione di sotto-grafi. Si ipotizza il ricorso ad algoritmi di Community Detection, Block modelling, Co-Clustering e simili, al fine di individuare delle sotto-matrici più dense entro le quali estrarre “regole” più robuste.Si ipotizza cioè un processo di raffinamento successivo della dimensionalità dell'analisi, partendo a livello macro a definire le regole scaturite dalla rete nella sua completezza, passando per un livello meso, in cui si analizzano dei sottografi individuati tramite algoritmi di Clustering su grafi e, arrviando a un livello micro, individuando delle Ego-network di interesse per cui definire delle regole ad hoc.Il progetto sarà articolato in più fasi consecutive.Nella prima fase si considererà lo stato dell'arte sulla letteratura specializzata per individuare le conoscenze acquisite nelle più recenti pubblicazioni sull'argomento.Nella seconda fase si metterà a punto una proposta di analisi originale che tenterà di fondere le conoscenze acquisite nell'ambito della Social Network Analysis con le necessità specifiche della definizione e della misura delle Regole Associative. In questa fase verranno messi a punto degli algoritmi per l'implementazione effettiva della metodologia.In una terza fase si valuterà la portata applicativa della metodologia individuata, applicandola a dataset reali e/o simulati.Il ricorso alla simulazione favorirà lo studio delle proprietà teoriche dei risultati statistici perseguiti.