Concept drift detection in high-dimensional spaces

In predictive modeling, the assumption of static relationships between input and output data often fails. The phenomenon can be addressed as \textit{concept drift}, signifying shifts in data patterns over time. In high-dimensional multivariate data streams, common in fields like IoT and text analysis, the curse of dimensionality complicates the identification of meaningful changes. Feature reduction techniques, such as Principal Component Analysis (PCA), offer a solution but come with computational costs. This study addresses the performance of the QuantTree (QT) algorithm in high-dimensional dataframes, extending its exploration to the generalized Kernel-QT (KQT) and its online variant, QT-EWMA. A novel addition to this landscape is proposed—Kernel-QuantTree Exponentially Weighted Moving Average (KQT-EWMA). In evaluating and building a monitoring system, we consider the balance between True Positive Rate (TPR) and False Positive Rate (FPR) to be crucial. We also consider other quantitative criteria such as execution time. The problem formulation revolves around a change detection algorithm's three main components: a model of the initial distribution, a statistic derived from it, and a decision rule. We assume both the initial distribution and the changing distribution to be unknown. The study employs a QuantTree-like histogram fitted on the distribution to estimate the model. Two modes of drift detection - batch-wise and online - are explored. The study investigates the limitations and advantages of different dimensionality reduction techniques, including PCA and Random Projections. The study uncovers the impact of dimensionality together with the availability of training data on QT's performance. We extend the analysis to incorporate $l_p$ norms as alternative kernel functions for KQT, considering quasi-norms with $p \leq 1$ that might be suitable in high dimensional dataframes. Introducing KQT-EWMA, an online nonparametric change-detection algorithm, we extend some previous theoretical results and compare its performance against existing methods; KQT-EWMA stands out as comparable or superior with respect to the state of the art. The complexities addressed in this dynamic environment underscore the ongoing challenges and the need for simple solutions in the ever-evolving landscape of data analysis.

Nel realizzare modelli di classificazione, analisi predittiva, etc., l’assunzione di relazioni statiche tra i dati di input e output - cio`e che le relazioni tipo y = f(x) rimangano vere nel tempo - spesso fallisce. Il fenomeno si può chiamare “concept drift”, o deriva del concetto, indicando cambiamenti fra le quantità e relazioni statistiche. Considerando flussi di dati multivariati, comuni in settori come l’IoT e l’analisi testuale, l’identificazione di cambiamenti significativi è estremamente complicata. Tecniche di riduzione della dimensionalità come l’Analisi delle Componenti Principali (PCA) offrono - a volte - una soluzione ma comportano anche altri problemi e costi computazionali. Questo studio osserva le analisi dell’algoritmo QuantTree (QT) di dataframe ad alta dimensionalità, estende l’osservazione alla sua versione generalizzata Kernel-QT (KQT) e alla sua variante online, QT-EWMA. Viene proposto l’algoritmo Kernel-QuantTree Exponentially Weighted Moving Average (KQT- EWMA). Nel costruire sistemi di monitoraggio, consideriamo l’equilibrio tra il tasso di veri positivi (TPR) e il tasso di falsi positivi (FPR), con particolari attenzioni per quest’ultimo, e altri criteri quantitativi come il tempo di esecuzione, che abbiamo sempre registrato lungo questi esperimenti. La formulazione del problema si fonda sui tre elementi principali di un algoritmo per concept drift detection: un modello della distribuzione iniziale, una statistica derivata da questo e una regola decisionale che valuti un cambiamento come tale. Assumiamo sconosciute sia la distribuzione iniziale che le derive che questa subisce nel tempo. Esploriamo le due modalità batch-wise (offline) e online, indagando limiti e vantaggi delle diverse tecniche di riduzione della dimensionalità d, incluse PCA e Random Projections, proiezioni randomiche. Lo studio mostra l’impatto di d sulle prestazioni di diversi algoritmi insieme alla disponibilità (in generale scarsa) di dati di training. Continuiamo l’analisi di KQT considerando quasi-norme l_p come funzioni kernel alternative, noto che valori di p ≤ 1 possono essere adatti in spazi ad alta dimensionalità. Con l’introduzione di KQT-EWMA, un algoritmo online e non parametrico, estiendiamo alcuni risultati teorici precedenti; ne confrontiamo le prestazioni con metodi esistenti. KQT-EWMA è comparabile allo stato dell’arte, superiore in ambienti controllati (con un sufficiente numero di punti di training). Le complessità affrontate in questo ambiente dinamico portano senz’altro la necessità di soluzioni semplici.