Fattorizzazione non negativa di matrici nel clustering di grafi

Il problema della fattorizzazione non negativa di matrici consiste nell'approssimare una matrice X non negativa tramite il prodotto di due matrici W e H, anch'esse non negative, con il duplice fine di ridurre le dimensioni dei dati ed ottenere una loro rappresentazione facilmente interpretabile. La generalità del problema porta a diverse varianti a seconda degli ulteriori vincoli da imporre sui dati iniziali e sulle matrici da calcolare. Lo scopo dell'elaborato è utilizzare un algoritmo basato su NMF per suddividere in gruppi i nodi di un grafo nella procedura detta di graph clustering. Data l'equivalenza tra grafi indiretti e matrici di adiacenza ci concentriamo perciò sulla variante simmetrica di NMF (SymNMF), dove si richiede che W'=H e dunque X è approssimata dal prodotto WW'. Dopo aver parlato della variante simmetrica introduciamo i metodi CD ed enunciamo alcuni risultati di convergenza, dimostrandone uno per BCD. Fissando come misura d'errore il quadrato della norma di Frobenius di X-WW' creiamo un algoritmo CD che trova la soluzione della SymNMF aggiornando una colonna di W per volta. Descriviamo la risoluzione del problema di rango uno necessario all'aggiornamento delle colonne, quindi mostriamo la convergenza a punti stazionari della successione delle iterate. Con l'algoritmo scelto effettuiamo tre analisi su dataset diversi, mostrando che nei primi due casi la SymNMF è in grado di riprodurre quasi perfettamente i gruppi osservati nella realtà. Il terzo caso presenta alcune differenze con la realtà ma, effettuando un'analisi delle componenti principali dello stesso dataset, osserviamo che alcune delle lacune sono riconducibili a outliers e che in generale i risultati ottenuti con i due metodi sono altamente compatibili.