Incremental quantTree

Change Detection on data streams, defined as the problem of monitoring a stream of data to detect whether a distribution change has occurred, is a relevant topic in machine learning, with applications ranging from wildfires monitoring to quality control. In this thesis we address the problem by proposing a novel non parametric algorithm for change detection on data streams. We begin by analyzing literature on this problem, discussing the change detection algorithms proposed over the years, with a focus on those capable of monitoring multivariate data streams. We then start from QuantTree, a non parametric, histograms-based algorithm for multivariate data streams to build our contributions to the problem, consisting of a novel change detection algorithm, Incremental QuantTree (IQT). IQT requires a very small training set to begin monitoring a data stream, continuously increasing its detection accuracy over time. Furthermore it can be combined with of an Exponentially Weighted Moving Average chart, which controls the false alarms of the algorithm over time, detecting if a change occurred. Our experiments show that Incremental QuantTree is able to obtain a performance comparable to that of QuantTree when having access to a much smaller training set, and is also in line with Hotelling - Change Point Methods.

La rilevazione dei cambiamenti (Change detection) su flussi di dati, fefinito come il problema di monitorare un flusso di dati per stabilire se è avenuto un cambiamento nella distribuzione che genera quei dati, è un problema rilevante di Machine Learning, con applicazioni in campi come il monitoraggio degli incendi, il controllo del traffico e il controllo di qualità. In questa tesi proponiamo un nuovo algoritmo non parametrico per Change Detection su stream di dati. Prima di tutto analizziamo la letteratura sul tema, discutendo le tecniche principali proposte nel corso degli anni. Partendo poi da QuantTree, un algoritmo non parametrico per change detection basato su istogrammi, abbiamo creato un nuovo algoritmo per fare change detection, Incremental QuantTree (IQT). IQT è un algoritmo in grado di iniziare a monitorare un flusso di dati partendo da un training set di dimensioni estremamente ridotte, migliorando progressivamente la propria capacità di individuare cambiamenti. Inoltre può essere esteso con un controllo con un diagramma di Exponentially Weighted Moving Average, che controlla i falsi allarmi dell'algoritmo nel tempo, individuando in questo modo dei cambiamenti. I nostri esperimenti mostrano che Incremental QuantTree è in grado di ottenere una performance comparabile a QuantTree, avendo accesso a un training set molto più ridotto. Inoltre ha una performance in linea con il Change Point Method che fa uso della statistica Hotelling.