Algoritmi per la diversity maximization con outliers

L’obiettivo di questo lavoro è di proporre e analizzare un algoritmo efficiente per la risoluzione del problema della Diversity Maximization con Outliers, prendendo come punto di partenza lo studio sviluppato da Amagata nell’articolo “Diversity Maximization in the Presence of Outliers” (2023). Mentre il problema classico della Max-Min Diversity Maximization chiede di trovare, dato un insieme di punti presi da uno spazio metrico, un sottoinsieme di elementi tale per cui la distanza minima tra qualsiasi coppia selezionata sia massimizzata, nel problema con outliers si ha la necessità aggiuntiva di escludere gli elementi anomali che andrebbero ad alterare la soluzione. Questo filtraggio, essenziale nell'analisi di dataset reali, viene affrontato in questo lavoro attraverso un modello di calcolo sequenziale, superando le limitazioni e le inefficienze dei precedenti approcci proposti in letteratura. L'algoritmo studiato, basato sull'adattamento della classica euristica di Gonzalez (algoritmo GMM), prevede la costruzione preliminare di un coreset. Nel caso generale, la sola fase di coreset garantisce un fattore di approssimazione pari a 2, che scende a 1+ε (con ε definito dall'utente) se si sfrutta la doubling dimension dello spazio metrico aumentando i punti selezionati. Combinando questo campionamento con la successiva fase di ricerca della soluzione tramite GMM, l'algoritmo esprime un'approssimazione complessiva finale pari a 4 nel caso generale, e pari a 2(1+ε) nella variante con la doubling dimension. Dimostreremo in questa tesi che tale architettura a tre fasi (costruzione del coreset, identificazione esatta degli outliers basata sulla distanza dal Nearest Neighbor e ricerca della soluzione finale) risulta computazionalmente vantaggiosa, poiché consente di calcolare molteplici soluzioni per configurazioni differenti riutilizzando il medesimo coreset. Il lavoro pone infine solide basi per sviluppi futuri, mirati sia a rimuovere la necessità di conoscere a priori il numero di outliers, sia ad estendere la delicata fase di costruzione del coreset al modello di streaming.