Enhancing QuantTree using kernel functions

Change detection is a relevant topic in Machine Learning, which addresses the problem of detecting when the distribution of the process that generates the data changes. In recent years, change detection has been extensively used in systems that monitor data for product quality assurance or security purposes. In this problem, it is important to control false alarms, as they can lead to a waste of resources in terms of money and time. The goal of this thesis is to define a new change detection method, based on centroids and a kernel function used as distance, called Kernel QuantTree (KQT), which extends QuantTree (QT), a non-parametric histogram-based algorithm. In particular, we focus on how to partition the input space with non-linear cuts to produce compact bins that are more meaningful than QT, starting from stationary data. In this thesis, we will first see how to formulate the problem, the associated literature, and the necessary background. Then, we will see how histogram construction is performed in KQT. In particular, we will see how to choose centroids using K-means++ and the Gini Index, evaluating them by looking at how the remaining training set points in the last bin are arranged in space. Then we evaluate different distances, starting with Euclidean and Manhattan distances, and then use first the Mahalanobis distance (MD) and then a weighted extension of it (WMD) as kernel functions. In the end, our experiments show that Kernel QuantTree is able to obtain a better AUC than the other methods, while keeping the false positive rate under control according to the target set.

Il rilevamento dei cambiamenti (change detection) è un argomento rilevante in Machine Learning, che affronta il problema di rilevare quando la distribuzione del processo che genera i dati cambia. Negli ultimi anni, change detection è stato ampiamente utilizzato nei sistemi che monitorano i dati per garantire la qualità del prodotto o per scopi di sicurezza. In questo problema, è importante controllare i falsi allarmi, in quanto possono portare a uno spreco di risorse in termini di denaro e tempo. L'obiettivo di questa tesi è definire un nuovo metodo di change detection, basato sui centroidi e su una funzione kernel usata come distanza, chiamato Kernel QuantTree (KQT), che estende QuantTree (QT), un algoritmo non parametrico basato sugli istogrammi. In particolare, ci concentriamo su come suddividere lo spazio di input con tagli non lineari per produrre bins compatti e più significativi rispetto a QT, partendo da dati stazionari. In questa tesi, vedremo innanzitutto come formulare il problema, la letteratura associata e il background necessario. Poi, vedremo come viene eseguita la costruzione dell'istogramma in KQT. In particolare, vedremo come scegliere i centroidi utilizzando K-means++ e l'indice Gini, valutandoli osservando come sono disposti nello spazio i punti del training set rimanenti nell'ultimo bin. Poi valutiamo diverse distanze, partendo da quella Euclidea e da quella di Manhattan, per poi utilizzare prima la distanza di Mahalanobis (MD) e poi una sua estensione ponderata (WMD) come funzioni kernel. Alla fine, i nostri esperimenti dimostrano che Kernel QuantTree è in grado di ottenere un'AUC migliore rispetto agli altri metodi, pur mantenendo sotto controllo il tasso di falsi positivi secondo l'obiettivo impostato.