Studio e implementazione di density clustering DBSCAN approssimato

Il clustering è una primitiva di machine learning non supervisionato che consiste nel raggruppare oggetti simili in insiemi omogenei, chiamati cluster. Tali insiemi vengono creati in modo tale che gli oggetti appartenenti allo stesso cluster abbiano un grado di somiglianza maggiore rispetto ad oggetti presenti in altri cluster. Il DBSCAN è un metodo di clustering basato sulla densità: dato un insieme di punti in uno spazio euclideo multidimensionale, lo scopo è creare un cluster per ogni insieme di punti ad alta densità. Per dimensioni superiori a due, la complessità temporale del DBSCAN, nel caso peggiore, è provatamente superlineare, la qual cosa lo rende inadatto a gestire grandi moli di punti. Al fine di affrontare questa problematica, il presente lavoro si propone di analizzare e implementare un algoritmo di DBSCAN approssimato che migliora la complessità temporale, pur restituendo un insieme di cluster ragionevolmente assimilabili a quelli del DBSCAN esatto. L'algoritmo approssimato mira a ridurre significativamente i tempi di esecuzione, consentendo una maggiore scalabilità e adattabilità del metodo di clustering in spazi di alta dimensionialità, a scapito di una soglia quantitativa di errore che può essere resa arbitrariamente piccola.