Algoritmi distance-based per l'identificazione di outlier

Questa tesi di laurea studia i principali algoritmi di rilevamento di distance-based outlier noti in letteratura. L'obiettivo principale è comprendere le definizioni di outlier adottate, studiare le strategie algoritmiche utilizzate e fornire una dettagliata analisi della complessità degli algoritmi. In una prima parte si fornisce una definizione della nozione di distance-based outlier e il problema del rilevamento di outlier. Successivamente, vengono descritti tre algoritmi proposti in due articoli, esplicitando le scelte implementative relative ad alcuni passaggi chiave e alle strutture dati da utilizzare. Per ciascun algoritmo viene effettuata l'analisi della complessità in termini di numero di operazioni e, in alcuni casi, di numero di blocchi trasferiti da disco a RAM e viceversa. Per un algoritmo viene anche fornita una versione che ne migliora notevolmente l'efficienza a scapito di una moderata perdita di accuratezza negli outlier identificati.