Due algoritmi per la fattorizzazione matriciale non negativa con applicazione al clustering

In questa tesi vengono descritti il problema della fattorizzazione non negativa ortogonale (ONMF) con applicazione al clustering e due algoritmi elaborati da F. Pompili, N. Gillis, P.A. Absil e F. Gilneur per l'approssimazione numerica della coppia di matrici soluzione di tale problema: il primo algoritmo legato a una variante delle k-medie sferiche e il secondo basato sul metodo della Lagrangiana aumentata. Particolare attenzione viene prestata alla base teorica su cui si fonda il primo algoritmo, cioè l'equivalenza tra il problema delle k-medie sferiche pesate e il problema ONMF descritta dal Teorema 2.6. Per ciascun algoritmo vengono analizzati punti di forza e di debolezza e suggerita la tipologia di data set per cui risultano più indicati al fine di determinare un'opportuna divisione in cluster. Il primo capitolo, di carattere introduttivo, descrive i concetti di clustering e di fattorizzazione non negativa, proponendo una formulazione matematica utile ai fini della trattazione. Il secondo capitolo è dedicato all'algoritmo EMONMF, di cui è proposta la descrizione teorica e l'applicazione al problema di text clustering con oggetto una matrice termine-documento di articoli medici. Il terzo capitolo è dedicato all'algoritmo ONPMF di cui sono descritti i metodi di ottimizzazione su cui è costruito, cioè il metodo del gradiente proiettato e della Lagrangiana aumentata, e gli esperimenti numerici sono applicati all'Iris data set contenuto nel file matlab fisheriris. Infine, nel quarto e ultimo capitolo vengono proposti due confronti numerici degli algoritmi, che vengono analizzati in termini di iterazioni, tempi di elaborazione, stabilità e precisione della fattorizzazione e del clustering. Il primo confronto è applicato all'hyperspectral unmixing con oggetto il data set Hubble e il secondo è applicato al pattern recognition con oggetto U.S. Postal Service database. I codici Matlab sono disponibili all'indirizzo https://github.com/filippo-p/onmf.