Studio di un algoritmo di streaming per k-median clustering

Questa tesi presenta un’analisi dell’algoritmo di streaming Partial Least Squares Plus (PLS+). Ci concentriamo in particolare sul k-median problem in spazi metrici generali, nel quale cerchiamo di trovare un insieme di k centri, ognuno delle quali raggruppa un certo numero di punti pesati dello stream iniziale, per ridurre al minimo la somma delle distanze da ciascun punto nel set di dati al suo centro più vicino. Viene utilizzato al suo interno anche l’algoritmo Online Facility Location (OFL) sia come controllore sul costo sia per scegliere se un punto può far parte di una facility già creata o deve essere il centro di una nuova facility. L’obiettivo della tesi è di fare un’analisi sia teorica che sperimentale delle proprietà dell’output di PLS+.