Online hierarchical partitioning of the output space in extreme multi-label data streams

Abstract

In many real-world applications, such as recommendation systems or healthcare monitoring, data arrives continuously and can be associated with multiple labels simultaneously. Learning from such multi-label data streams is particularly challenging due to the dynamic nature of the environment, high-dimensional label spaces, sparse label co-occurrence, and evolving data distributions. These challenges are compounded by concept drift, where not only input distributions but also label correlations and frequencies shift over time. This thesis introduces and evaluates two complementary frameworks: iHomer and its enhanced variant iHomer+. The iHomer framework addresses real-world data by incrementally clustering correlated labels using online divisive-agglomerative strategies based on Jaccard similarity, and by learning over these clusters with a global tree-based model guided by a multivariate Bernoulli process. It integrates drift detection at both global and local levels to dynamically adapt label partitions. Building upon this, iHomer+ extends the method to controlled synthetic data streams by embedding three adaptive global learners and introducing a background replacement mechanism. It targets the systematic evaluation of concept drift types (abrupt, incremental, and recurrent) across label space changes. Empirical results show that iHomer outperforms 17 state-of-the-art baselines on 23 real-world datasets, while iHomer+ further improves predictive performance by up to 29% on 9 synthetic benchmarks with annotated drift. Together, these contributions offer a robust and adaptive solution for online multi-label learning under concept drift.