Many real-world scenarios involving streaming information can be represented as temporal graphs, where data flows through dynamic changes in edges over time. Anomaly detection in this context has the objective of identifying unusual temporal connections within the graph structure. Detecting edge anomalies in real time is crucial for mitigating potential risks. Unlike traditional anomaly detection, this task is particularly challenging due to concept drifts, large data volumes, and the need for real-time response. To face these challenges, we introduce ARES, an unsupervised anomaly detection framework for edge streams. ARES combines Graph Neural Networks (GNNs) for feature extraction with Half-Space Trees (HST) for anomaly scoring. GNNs capture both spike and burst anomalous behaviors within streams by embedding node and edge properties in a latent space, while HST partitions this space to isolate anomalies efficiently. ARES operates in an unsupervised way without the need for prior data labeling. To further validate its detection capabilities, we additionally incorporate a simple yet effective supervised thresholding mechanism. This approach leverages statistical dispersion among anomaly scores to determine the optimal threshold using a minimal set of labeled data, ensuring adaptability across different domains. We validate ARES through extensive evaluations across several real-world cyber-attack scenarios, comparing its performance against existing methods while analyzing its space and time complexity. The code used to perform the experiments is publicly available at https://github.com/AnomalyRecognitionModelForEdgeStreams/ARES.

Abstract Anomaly detection in live trajectory data is a critical task for ensuring safety, security, and legality in global transport. Traditional anomaly detection methods often struggle with dynamic and evolving trajectory patterns, especially as systems must adapt to new scenarios over time due to increased traffic, geopolitical events, or global warming. We propose a continual learning approach to detect anomalous activity in moving vessels. Unlike conventional static models, our method leverages continual learning to enable the model to learn from new data continuously and recognise specific behaviours dependent on position and recent movements. We implement an adapter-based framework, Continual Learning for AIS Anomalies (CLAISA), that adapts to shifting behavioural environments in transportation, ensuring the system can identify novel and evolving patterns of anomalies, such as deviations from expected routes, irregular speed changes, or unusual local movements. Evaluations on synthetic maritime trajectory datasets spanning sparsely populated waters and heavily trafficked shipping lanes demonstrate that CLAISA achieves up to a $$32\%$$ decrease in error for trajectory forecasting and consistently outperforms benchmark methods in anomaly detection on synthetically generated datasets.

Abstract Prediction intervals (PIs) are a practical tool for uncertainty quantification in regression, but comparatively little work has addressed fully incremental PI generation for data streams. In streaming settings, data arrive continuously, each instance is typically processed once, and concept drift can quickly invalidate a previously well-calibrated interval. These properties make many batch PI methods and window-based adaptations difficult to apply efficiently. This paper studies Adaptive Prediction Interval (AdaPI), an online post-calibration framework that adjusts interval width according to observed coverage. We instantiate the framework with a fully incremental variant of Mean and Variance Estimation (MVE) and investigate three adaptive scaling functions. We also adopt an evaluation perspective that jointly considers coverage accuracy and interval width. Experiments on a collection of real-world and synthetic regression streams show that AdaPI can often move coverage closer to the desired confidence level while maintaining competitive interval width; under the default 95% confidence setting and coverage-heavy CING weighting, the linear variant frequently gives the strongest empirical coverage–width trade-off among the three adaptive strategies.

Semi-supervised learning (SSL) problems are challenging, appear in many domains, and are particularly relevant to streaming applications, where data are abundant but labels are not. The problem tackled here is classification over an evolving data stream where labels are rare and distributed randomly. We propose SLEADE (Stream LEArning by Disagreement Ensemble), a novel method that exploits disagreement-based learning and unsupervised drift detection to leverage unlabeled data during training. SLEADE uses pseudo-labeled instances to augment the training set of each member of an ensemble using amajority trains minorityscheme. The pseudo-labeled data impact is controlled by a weighting function that considers the confidence in the prediction attributed by the ensemble members. SLEADE exploits unsupervised drift detection, which allows the ensemble to respond to changes. We present several experiments using real and synthetic data to illustrate the benefits and limitations of SLEADE compared to existing algorithms.

Ensemble methods are widely recognized for their effectiveness in data stream classification. This paper introduces Dynamic Ensemble Member Selection (DEMS), a novel framework that dynamically selects a subset of classifiers from an ensemble for each individual prediction. DEMS ranks base learners based on estimated accuracy and predictive margin, using only the top-K members for prediction, where K is optimized in a self-adaptive manner. The proposed method significantly enhances predictive performance across various state-of-the-art ensemble algorithms, including Streaming Random Patches, Adaptive Random Forest, and Online Smooth Boost. Experimental results demonstrate that DEMS consistently improves classification accuracy while maintaining a minimal runtime overhead of just 11.66% compared to the original methods. This work highlights the potential of DEMS in adapting to concept drift and optimizing ensemble diversity, offering a practical solution for real-time data stream classification.

Hyperparameter optimization is crucial for maximizing machine learning model performance, yet most existing algorithms are designed for batch or offline scenarios and assume static data distributions.Such assumptions fall short in data stream settings, where models must adapt to evolving inputs in real time.To address these limitations, we propose the Bayesian Stream Tuner (BST), a novel framework for online hyperparameter optimization in nonstationary data streams.BST maintains a dynamic set of candidate hyperparameter configurations and periodically refines them using an incremental Bayesian model, which estimates configuration performance based on recent data statistics and hyperparameter values.This systematic exploration and refinement strategy allows BST to detect and respond to concept drift by resetting its adaptation mechanisms whenever necessary, ensuring strong performance under changing distributions.Our theoretical analysis establishes sublinear regret bounds for BST in dynamic environments, and extensive experiments on classification and regression tasks demonstrate that BST consistently outperforms state-of-the-art online hyperparameter optimization methods in both predictive accuracy and adaptability, making it a powerful solution for real-time hyperparameter tuning in evolving data streams.

Abstract Gradient boosting has been extensively studied in batch learning. Recently, its streaming adaptation, Streaming Gradient Boosted Trees (Sgbt), has surpassed existing state-of-the-art random subspace and random patches methods for streaming classification under various drift scenarios. However, its application in streaming regression remains unexplored. Vanilla Sgbt with squared loss exhibits high variance when applied to streaming regression problems. To address this, we utilize bagging streaming regressors in this work to create Streaming Gradient Boosted Regression (Sgbr). Bagging streaming regressors are employed in two ways: first, as base learners within the existing Sgbt framework, and second, as an ensemble method that aggregates multiple Sgbts. Our extensive experiments on 11 streaming regression datasets, encompassing multiple drift scenarios, demonstrate that the Sgb(Oza), a variant of the first Sgbr category, significantly outperforms current state-of-the-art streaming regression methods in terms of both predictive power and computational cost.

Machine Learning for Data Streams has been an important area of research since the late 1990s, and its use in industry has grown significantly over the last few years. However, there is still a gap between the cutting-edge research and the tools that are readily available, which makes it challenging for practitioners, including experienced data scientists, to implement and evaluate these methods in this complex domain. Our tutorial aims to bridge this gap with a dual focus. We will discuss important research topics, such as partially delayed labeled streams, while providing practical demonstrations of their implementation and assessment using CapyMOA, an open-source library that provides efficient algorithm implementations through a high-level Python API. Source code is available in https://github.com/adaptive-machine-learning/CapyMOA while the accompanying tutorials and installation guide are available in https://capymoa.org/.

Continual learning closely emulates human learning, which allows a model to learn from a stream of tasks sequentially without forgetting previously learned knowledge. Replay-based continual learning methods mitigate forgetting and improve performance by reintroducing data belonging to old tasks, however a replay method's performance may deteriorate when the reintroduced data does not effectively represent all experienced data. To address this concern, we propose the Sketch-based Replay Projection (SRP) method to capture and retain the original data stream's distribution within stored memory. SRP augments existing replay frameworks and introduces a two-fold approach. First, we develop a sketch-based sample selection technique to approximate feature distributions within distinct tasks, thereby capturing a wide distribution of examples for subsequent replay. Second, we propose a data compression method which projects examples into a reduced-dimensional space while preserving inter-example relationships and emphasizing inter-class disparities, encouraging diverse representations of each class while maintaining memory requirements similar to existing replay methodologies. Our experimental results demonstrate that SRP enhances replay diversity and improves the performance of existing replay models.

Continuous data generation over time presents new challenges for Machine Learning systems, which must develop real-time models due to memory and latency limitations. Streaming Machine Learning algorithms analyze data streams one sample at a time, progressively updating their models. However, is it necessary to utilize all the data for model updates? This paper introduces the Online Ensemble SPaced Learning (OE-SPL) strategy, an ensemble meta-strategy that combines online ensemble learning and the Spaced Learning heuristic to rapidly learn underlying concepts without using all samples. We evaluated OE-SPL on synthetic and real data streams containing various concept drifts, providing statistical evidence that OE-SPL achieves comparable performance to state-of-the-art ensemble models while recovering from multiple concept drift occurrences more efficiently, using less time and RAM-Hours.

Continual learning aims to create artificial neural networks capable of accumulating knowledge and skills through incremental training on a sequence of tasks. The main challenge of continual learning is catastrophic interference, wherein new knowledge overrides or interferes with past knowledge, leading to forgetting. An associated issue is the problem of learning "cross-task knowledge," where models fail to acquire and retain knowledge that helps differentiate classes across task boundaries. A common solution to both problems is "replay," where a limited buffer of past instances is utilized to learn cross-task knowledge and mitigate catastrophic interference. However, a notable drawback of these methods is their tendency to overfit the limited replay buffer. In contrast, our proposed solution, SurpriseNet, addresses catastrophic interference by employing a parameter isolation method and learning cross-task knowledge using an auto-encoder inspired by anomaly detection. SurpriseNet is applicable to both structured and unstructured data, as it does not rely on image-specific inductive biases. We have conducted empirical experiments demonstrating the strengths of SurpriseNet on various traditional vision continual-learning benchmarks, as well as on structured data datasets. Source code made available at https://doi.org/10.5281/zenodo.8247906 and https://github.com/tachyonicClock/SurpriseNet-CIKM-23

Continuously learning and serving from evolving streaming data and serving in real-time is a challenging problem. Traditionally, data is partitioned and processed in batches to train machine learning (ML) models. In industrial applications, static models’ performance drops over time (model degradation, concept drift), requiring new models to be trained with recent data and redeployed in production. The scientific community has been studying online and adaptive methods to address batch-learning limitations and continuously train AI tasks for industrial applications such as cyber-security, AIOps, anomaly scoring, and drift detection in stock markets. This paper deals with the MLOps aspects of deploying such online and dynamic models to address the requirements in the production systems for real-time applications. Our architectures - based on open-source tools such as Kafka and River - demonstrated how online learning methods could be scaled horizontally in production to meet the demands of a high-velocity streaming pipeline. We demonstrate an MLOps strategy to perform incremental learning from streaming data and continuously deploy the online learning model without pausing the inference pipeline. Indeed, the design satisfies requirements such as model versioning, monitoring, audibility and reproducibility of prediction in both a supervised and semi-supervised setting. Our experiments - for malicious URLs detection task - performed on high-dimensional and feature-evolving streaming data (more than 3 million features) establish the effectiveness and efficiency of online learning models compared to batch (static) machine learning regarding both time and space complexity. Finally, we provide some best practices on data engineering for deploying online models to process a real-time feature stream in production environments. Code is publicly available for reproducibility.

A growing number of tasks require adaptive machine learning systems capable of learning continuously from incoming data and adapting to changes in their environment. In order to enable the widespread adoption of machine learning for streaming data, it is crucial that practitioners and researchers have the tools to efficiently build and evaluate adaptive learning systems. In this paper we demonstrate FALL, a Framework for Adaptive Life-long Learning, which we have developed to enable the full adaptive learning pipeline to be built using modular, reusable components, enabling users to easily and efficiently develop, implement, and evaluate state-of-the-art adaptive learning systems. Source code, documentation, and examples may be found at https://benhalstead.dev/FALL/.

Modern online platforms for user modeling and recommendation require complex data infrastructures to collect and process data. Some of this data has to be kept to later be used in batches to train personalization models. However, since user activity data can be generated at very fast rates it is also useful to have algorithms able to process data streams online, in real time. Given the continuous and potentially fast change of content, context and user preferences or intents, stream-based models, and their synchronization with batch models can be extremely challenging. Therefore, it is important to investigate methods able to transparently and continuously adapt to the inherent dynamics of user interactions, preferably over long periods of time. Models able to continuously learn from such flows of data are gaining attention in the recommender systems community, and are being increasingly deployed in online platforms. However, many challenges associated with learning from streams need further investigation.

Learning from streaming data is challenging as the distribution of incoming data may change over time, a phenomenon known as concept drift. The predictive patterns, or experience learned under one distribution may become irrelevant as conditions change under concept drift, but may become relevant once again when conditions reoccur. Adaptive learning methods adapt a classifier to concept drift by identifying which distribution, or concept , is currently present in order to determine which experience is relevant. Identifying a concept requires some representation to be stored for comparison, with the quality of the representation being key to accurate identification. Existing concept representations are based on meta-features, efficient univariate summaries of a concept. However, no single meta-feature can fully represent a concept, leading to severe accuracy loss when existing representations cannot describe concept drift. To avoid these failure cases, we propose the first general framework for combining a diverse range of meta-features into a single representation. We solve two main challenges, first presenting a method of efficiently computing, storing, and querying an arbitrary set of meta-features as a single representation, showing that a combination of meta-features may successfully avoid failure cases seen with existing methods. Second, we present the first method for dynamically learning which meta-features distinguish concepts in any given dataset, significantly improving performance. Our proposed approach enables state-of-the-art feature selection methods, such as mutual information, to be applied to concept representation meta-features for the first time. We investigate tradeoffs between memory budget and classification performance, observing accuracy increases of up to 16% by dynamically weighting the contribution of each meta-feature.

Knowledge Graphs (KG) are valuable information sources that store knowledge in a domain (healthcare, finance, e-commerce, cyber-security.). Most industrial KGs are dynamic by nature as they are updated regularly with streaming data (customer activity, network traffic, application logs, IT process). However, extracting insights from continuously updated data comes with major challenges, particularly in big data settings. In this paper, we address the following challenges: 1) ingesting heterogeneous data, 2) training and deployment of predictive models on continuously evolving data, and 3) implementation of data pipelines for updating and maintaining the KG in production. We cover multiple aspects of this process, from knowledge collection to its operationalization. We propose Stream2Graph, a stream-based system for building and updating the knowledge base dynamically in real time. Then we show how graph features can be used in downstream online machine learning models. The solution speeds up big data stream learning and knowledge extraction to enhance Graph-based AI applications. Experimental results show the effectiveness of our solution for knowledge base construction and improvement of big data learning capabilities. Using data from Stream2Graph resulted in speedups for training and inference time in the range from 547x to 2000x in downstream ML models. Finally, we provide the lessons learned from applying graph-based online learning on large-scale network processing high-velocity streaming data.

The growing need for predictive analytics over streaming data in the industry requires a flexible and continuously scalable big data system. In real-time big data applications (cybersecurity, AIOps, anomaly detection, predictive maintenance, IoT etc.), efficient machine learning models must be trained and industrialized within existing data processing plat-forms and industrial tools. This requires interoperability between various components: data collection, processing, summarization, modelling and analytics. Existing works focus on building AI models for big data, neglecting real-world challenges when integrating such models into an existing industrial production framework. In this paper, we propose StreamFlow, an operational data pipeline to address industrial challenges for continuous learning over big data streams. We also propose an online method using sliding windows to summarize high-velocity data. The final result of the framework is a feature vector that describes the underlying processes and is ready to use in machine learning tasks. Moreover, we showcase real-world applications such as automated feature engineering for real-time monitoring and online machine learning for event classification. The proposed system has been deployed within production in a banking system, processing billions of daily traffic operations. Our experiments demonstrate the effectiveness and performance of our approach by evaluating it at different levels: processing, summarization, improvement of machine learning performance and effectiveness in an industrial setting. In the case of downstream machine learning tasks, using summarized data generated by StreamFlow results in up to 2 orders of magnitude speedups in training time without compromising predictive performance.

Maintenance is an important support function to ensure the reliability, safety, and availability in the railway. Lately, machine learning has become a major player and allows practitioners to build intricate learning models for machinery maintenance. Commonly, a model is trained on static data and is retrained on new data that exhibit novelties unknown to the model. On the contrary, online machine learning is a learning paradigm that adapts the models to new data, thus enabling adaptive, lifelong learning. Our goal is to leverage online learning on unlabeled data streams to enhance railway machinery maintenance. We propose Continuous Health Monitoring using Online Clustering (CheMoc) as an unsupervised method that learns the health profiles of the systems incrementally, assesses their working condition continuously via an adaptive health score, and works efficiently on streaming data. We evaluate CheMoc on a real-world data set from a national railway company. The results show that CheMoc discovered relevant health clusters, as confirmed by a domain expert, and processed the data of an entire year under two hours using only 600 MB of memory.

The distribution of streaming data often changes over time as conditions change, a phenomenon known as concept drift. Only a subset of previous experience, collected in similar conditions, is relevant to learning an accurate classifier for current data. Learning from irrelevant experience describing a different concept can degrade performance. A system learning from streaming data must identify which recent experience is irrelevant when conditions change and which past experience is relevant when concepts reoccur, e.g., when weather events or financial patterns repeat. Existing streaming approaches either do not consider experience to change in relevance over time and thus cannot handle concept drift, or only consider the recency of experience and thus cannot handle recurring concepts, or only sparsely evaluate relevance and thus fail when concept drift is missed. To enable learning in changing conditions, we propose SELeCT, a probabilistic method for continuously evaluating the relevance of past experience. SELeCT maintains a distinct internal state for each concept, representing relevant experience with a unique classifier. We propose a Bayesian algorithm for estimating state relevance, combining the likelihood of drawing recent observations from a given state with a transition pattern prior based on the system’s current state. The current state is continuously maintained using a Hoeffding bound based algorithm, which unlike existing methods, guarantees that every observation is classified using the state estimated as the most relevant, while also maintaining temporal stability. We find SELeCT is able to choose experience relevant to ground truth concepts with recall and precision above 0.9, significantly outperforming existing methods and close to a theoretical optimum, leading to significantly higher accuracy and enabling new opportunities for learning in complex changing conditions.

Online clustering algorithms play a critical role in data science, especially with the advantages regarding time, memory usage and complexity, while maintaining a high performance compared to traditional clustering methods. This tutorial serves, first, as a survey on online machine learning and, in particular, data stream clustering methods. During this tutorial, state-of-the-art algorithms and the associated core research threads will be presented by identifying different categories based on distance, density grids and hidden statistical models. Clustering validity indices, an important part of the clustering process which are usually neglected or replaced with classification metrics, resulting in misleading interpretation of final results, will also be deeply investigated.

Modern online systems for user modeling and recommendation need to continuously deal with complex data streams generated by users at very fast rates. This can be overwhelming for systems and algorithms designed to train recommendation models in batches, given the continuous and potentially fast change of content, context and user preferences or intents. Therefore, it is important to investigate methods able to transparently and continuously adapt to the inherent dynamics of user interactions, preferably for long periods of time. Online models that continuously learn from such flows of data are gaining attention in the recommender systems community, given their natural ability to deal with data generated in dynamic, complex environments. User modeling and personalization can particularly benefit from algorithms capable of maintaining models incrementally and online.

Abstract Most research in machine learning for data streams has focused on classification algorithms, whereas regression methods have received a lot less attention. This paper proposes Self-Optimising K-Nearest Leaves (SOKNL), a novel forest-based algorithm for streaming regression problems. Specifically, the Adaptive Random Forest Regression, a state-of-the-art online regression algorithm is extended like this: in each leaf, a representative data point – also called centroid – is generated by compressing the information from all instances in that leaf. During the prediction step, instead of letting all trees in the forest participate, the distances between the input instance and all centroids from relevant leaves are calculated, only k trees that possess the smallest distances are utilised for the prediction. Furthermore, we simplify the algorithm by introducing a mechanism for tuning the k values, which is dynamically and automatically optimised based on historical information. This new algorithm produces promising predictive results and achieves a superior ranking according to statistical testing when compared with several standard stream regression methods over typical benchmark datasets. This improvement incurs only a small increase in runtime and memory consumption over the basic Adaptive Random Forest Regressor.

Processing data streams gained much importance in recent years. Standard machine learning algorithms do not cope well with non-stationary streaming data, where decision models evolve and generate so-called concept drift. Online adaptive algorithms emerged to solve these issues. They learn incrementally and generally require explicit forgetting mechanisms to adapt to concept drift. In this paper, we propose the application of Kalman filtering to handle evolving data streams. This novel approach addresses data stream mining and concept drift management challenges from a new perspective, directly modelling a representation suitable for the data streams. First, we study a Kalman filter based learning a pproach and investigate its integration into the Naïve Bayes algorithm, namely KalmanNB. Additionally, we propose the Hoeffding Kalman Tree, a combination of the Hoeffding Tree with KalmanNB. Empirical results demonstrate that the Kalman filter based approach inherently manages concept drifts, and it adapts to the emerging concept more rapidly than the state-of-the-art algorithms. Moreover, it is an accurate and robust approach and requires less storage while still being faster.

Data collected over time often exhibit changes in distribution, or concept drift, caused by changes in hidden context relevant to the classification task, e.g. weather conditions. Adaptive learning methods are able to retain performance in changing conditions by explicitly detecting concept drift and changing the classifier used to make predictions. However, in realworld conditions, existing methods often select classifiers which poorly represent current data due to adaptation errors, where change in context is misidentified. We propose the AiRStream system, which uses a novel repair algorithm to identify and correct adaptation errors. We identify errors by periodically testing the performance of inactive classifiers. If an error is identified, a backtracking procedure repairs training done under the misidentified context. AiRStream achieves higher accuracy compared to baseline methods and selects classifiers which better match changes in context. A case study on a real-world air quality inference task shows that AiRStream is able to build a robust model of environmental conditions, allowing the adaptions made to concept drift to be analysed and related to changes in weather.

Streaming sources of data are becoming more common as the ability to collect data in real-time grows. A major concern in dealing with data streams is concept drift, a change in the distribution of data over time, for example, due to changes in environmental conditions. Representing concepts (stationary periods featuring similar behaviour) is a key idea in adapting to concept drift. By testing the similarity of a concept representation to a window of observations, we can detect concept drift to a new or previously seen recurring concept. Concept representations are constructed using meta-information features, values describing aspects of concept behaviour. We find that previously proposed concept representations rely on small numbers of meta-information features. These representations often cannot distinguish concepts, leaving systems vulnerable to concept drift. We propose FiCSUM, a general framework to represent both supervised and unsupervised behaviours of a concept in a fingerprint, a vector of many distinct meta-information features able to uniquely identify more concepts. Our dynamic weighting strategy learns which meta-information features describe concept drift in a given dataset, allowing a diverse set of meta-information features to be used at once. FiCSUM outperforms state-of-the-art methods over a range of 11 real world and synthetic datasets in both accuracy and modeling underlying concept drift.

Modern online services continuously generate data at very fast rates. This continuous flow of data encompasses content – e.g. posts, news, products, comments –, but also user feedback – e.g. ratings, views, reads, clicks –, together with context data – user device, spacial or temporal data, user task or activity, weather. This can be overwhelming for systems and algorithms designed to train in batches, given the continuous and potentially fast change of content, context and user preferences or intents. Therefore, it is important to investigate online methods able to transparently adapt to the inherent dynamics of online services. Incremental models that learn from data streams are gaining attention in the recommender systems community, given their natural ability to deal with the continuous flows of data generated in dynamic, complex environments. User modeling and personalization can particularly benefit from algorithms capable of maintaining models incrementally and online.

The last few decades have witnessed a significant evolution of technology in different domains, changing the way the world operates, which leads to an overwhelming amount of data generated in an open-ended way as streams. Over the past years, we observed the development of several machine learning algorithms to process big data streams. However, the accuracy of these algorithms is very sensitive to their hyper-parameters, which requires expertise and extensive trials to tune. Another relevant aspect is the high-dimensionality of data, which can causes degradation to computational performance. To cope with these issues, this paper proposes a stream k-nearest neighbors (kNN) algorithm that applies an internal dimension reduction to the stream in order to reduce the resource usage and uses an automatic monitoring system that tunes dynamically the configuration of the kNN algorithm and the output dimension size with big data streams. Experiments over a wide range of datasets show that the predictive and computational performances of the kNN algorithm are improved.

Streaming Machine Learning (SML) studies single-pass learning algorithms that update their models one data item at a time given an unbounded and often non-stationary flow of data (a.k.a., in presence of concept drift). Online class imbalance learning is a branch of SML that combines the challenges of both class imbalance and concept drift. In this paper, we investigate the binary classification problem of rebalancing an imbalanced stream of data in the presence of concept drift, accessing one sample at a time. We propose Continuous Synthetic Minority Oversampling Technique (C-SMOTE), a novel rebalancing meta-strategy to pipeline with SML classification algorithms. C-SMOTE is inspired by the popular SMOTE algorithm but operates continuously. We benchmark C-SMOTE pipelines on ten different groups of data streams. We bring empirical evidence that models learnt with C-SMOTE pipelines outperform models trained on imbalanced data stream without losing the ability to deal with concept drifts. Moreover, we show that they outperform other stream balancing techniques from the literature.

In mining temporal data streams, Dynamic Ensemble Selection (DES) has emerged as one of the most promising approaches of ensemble methods based on the assumption that each member of the ensemble is an expert in some local area of the stream. The aim is to select, on the fly, according to a given test instance x, a subset of experts from a pool of various models. To this end, meta-learning has been widely studied to predict the performance of each base-model and accordingly select the best ones and combine their outputs to compute the final prediction. However, most of the existing selection methods for time series forecasting on data streams do not handle model's dependencies, and therefore maybe missing useful insights. In this paper, we propose a novel approach to harness the potential dependencies within base-models' behavior based on Incremental Multi-Target Regression (MTR) to achieve Dynamic Ensemble Selection (DES). We show that explicitly considering models' dependencies improves overall performance. This work is the first to use Incremental MTR for learning the behavior of each component in an ensemble of forecasters on data streams. Finally, we conduct an extensive experimental study to compare the performance of the proposed methods against state-of-the-art approaches.

Learning from potentially infinite and high-dimensional data streams poses significant challenges in the classification task. For instance, k -Nearest Neighbors ( k NN) is one of the most often used algorithms in the data stream mining area that proved to be very resource-intensive when dealing with high-dimensional spaces. Uniform Manifold Approximation and Projection (UMAP) is a novel manifold technique and one of the most promising dimension reduction and visualization techniques in the non-streaming setting because of its high performance in comparison with competitors. However, there is no version of UMAP that copes with the challenging context of streams. To overcome these restrictions, we propose a batch-incremental approach that pre-processes data streams using UMAP, by producing successive embeddings on a stream of disjoint batches in order to support an incremental k NN classification. Experiments conducted on publicly available synthetic and real-world datasets demonstrate the substantial gains that can be achieved with our proposal compared to state-of-the-art techniques.

Modern online web-based systems continuously generate data at very fast rates. This continuous flow of data encompasses web content – e.g. posts, news, products, comments –, but also user feedback – e.g. ratings, views, reads, clicks, thumbs up –, as well as context information – device used, geographic info, social network, current user activity, weather. This is potentially overwhelming for systems and algorithms design to train in offline batches, given the continuous and potentially fast change of content, context and user preferences. Therefore it is important to investigate online methods to be able to transparently adapt to the inherent dynamics of online systems. Incremental models that learn from data streams are gaining attention in the recommender systems community, given their natural ability to deal with data generated in dynamic, complex environments. User modeling and personalization can particularly benefit from algorithms capable of maintaining models incrementally and online, as data is generated.

Abstract A large portion of the stream mining studies on classification rely on the availability of true labels immediately after making predictions. This approach is well exemplified by the test-then-train evaluation, where predictions immediately precede true label arrival. However, in many real scenarios, labels arrive with non-negligible latency. This raises the question of how to evaluate classifiers trained in such circumstances. This question is of particular importance when stream mining models are expected to refine their predictions between acquiring instance data and receiving its true label. In this work, we propose a novel evaluation methodology for data streams when verification latency takes place, namely continuous re-evaluation. It is applied to reference data streams and it is used to differentiate between stream mining techniques in terms of their ability to refine predictions based on newly arriving instances. Our study points out, discusses and shows empirically the importance of considering the delay of instance labels when evaluating classifiers for data streams.

A well-known challenge in mining temporal data streams is their dynamic nature where changes and recurrent concepts are likely to happen. Ensemble methods are powerful techniques to improve overall accuracy and tackle the aforementioned challenges by combining several classifiers. Dynamic Ensemble Selection allows selecting, on the fly, the most accurate classifiers only to contribute to the final output. This is motivated by the assumption that components of the ensemble have different degrees of expertise on different sub-spaces of the data. Existing Dynamic Ensemble Selection methods are tailored to batch learning or classification tasks but less suited to stream mining and forecasting tasks. In this paper, we propose a new Arbitrated Dynamic Ensemble Selection technique STREAMING-ADE for time-series forecasting on data streams that uses meta-learning to monitor the predictive power of ensemble components and accordingly select and weight experts. Our selection is based on an abstaining policy where poorly performing classifiers are excluded from the experts' committee. Our contribution is twofold: (i) We introduce two different approaches of abstaining: threshold-based and random-based selection and (ii) We conduct an extensive experimental study to compare different methods on both real and synthetic time-series.

In this paper, we present the competition “Real-time Machine Learning Competition on Data Streams a BigData Cup Challenge of the IEEE Big Data 2019 conference. Data streams, such as data originated from sensors, have increasingly gained the interest of researchers and companies and are currently widely studied in data science. Companies in the telecommunication and energy industries are trying to exploit these data and get real-time insights on their services and equipment. In order to extract valuable knowledge from data streams, one must be able to analyze the data as they arrive and make meaningful predictions. For this purpose, we use fast incremental learners. There already exists a great community that is organizing various competitions on machine learning tasks for batch learners. Our goal was to introduce the same approach to engage the whole community in solving essential problems in data stream mining. We performed a new kind of data science competition based on a real-time prediction setting, using a novel competition platform on data streams. The examples to predict were released in real-time, and the predictions had also to be submitted in real-time. To the best of our knowledge, this was the first data science competition conducted in real-time. The task of the competition was to predict network activity, and the data has been provided by one of our partner companies.

Assigning scores to individual features is a popular method for estimating the relevance of features in supervised learning. An accurate feature score estimation provides essential insights in sensitive domains, which is decisive to explain how features influence a given decision, contributing to the interpretability of the model. Learning from streaming data adds several challenges to machine learning tasks, including limited resources and changes to the underlying data distribution (i.e., evolving data streams). In this work, we introduce and analyze methods to efficiently estimate the Mean Decrease in Impurity (MDI) and COVER measures using ensembles of incremental decision trees. To achieve current scores in evolving data streams, we employ tree-ensembles that incorporate active drift detection. Experimental results show how MDI and COVER can be used to track the feature scores when their importance to the ensemble model shift over time. On top of that, we present the impact on the feature scores when the learning problem includes a non-negligible verification latency for the arrival of the labels. We also present a counter-intuitive experiment using a standard benchmark dataset where the feature scores correctly illustrate the importance of two features to the ensemble model. However, these features are prioritized due to biased split decisions, and in their absence, the model increases in predictive performance. We conclude that the presented measures can be used to understand the impact of features in the ensemble model better, still, such measures should be used with caution as they are limited by the underlying tree building and ensemble model biases.

Machine learning algorithms for data streams usually suppose that all data examples available for learning are strictly labeled. Unfortunately, in real-world scenarios, data examples are not always labeled. Semi-supervised learning is a challenging task to learn using labeled and unlabeled data at the same time. It is especially relevant in the context of data streams, where the data is generated in real-time, and the labels may be missing due to various factors (e.g., network delay, errors during the communication between sensors, expensive labeling process, and others). In this paper, we present two novel approaches to handle missing labels for classification learning in data streams, namely cluster-and-label and self-training. We discuss the strengths and weaknesses of each solution to establish a baseline to evaluate semi-supervised learning techniques in data streams. These methods are implemented inside the MOA (Massive Online Analysis) open-source software as an internal benchmark component, to help researchers to run experimental comparisons on semi-supervised learning on data streams easily.

Betweenness centrality and k-path centrality are two important indices that are widely used to analyze social, technological and information networks. In the current paper, first given a directed network G and a vertex $r\in V(G)$, we present a novel adaptive algorithm for estimating betweenness score of r. Our algorithm first computes two subsets of the vertex set of G, called $\mathcalRF (r)$ and $\mathcalRT (r)$. They define the sample spaces of the start-points and the end-points of the samples. Then, it adaptively samples from $\mathcalRF (r)$ and $\mathcalRT (r)$ and stops as soon as some condition is satisfied. The stopping condition depends on the samples met so far, $|\mathcalRF (r)|$ and $|\mathcalRT (r)|$. We show that compared to the well-known existing algorithms, our algorithm gives a better $(łambda,δ)$-approximation. Then, we propose a novel algorithm for estimating k-path centrality of r. Our algorithm is based on computing two sets $\mathcalRF (r)$ and $\mathcalD (r)$. While $\mathcalRF (r)$ defines the sample space of the source vertices of the sampled paths, $\mathcalD (r)$ defines the sample space of the other vertices of the paths. We show that in order to give a $(łambda,δ)$-approximation of the k-path score of r, our algorithm requires considerably less samples. Moreover, it processes each sample faster and with less memory. Finally, we empirically evaluate our proposed algorithms and show their superior performance. Also, we show that they can be used to efficiently compute centrality scores of a set of vertices.

Ensemble methods are a popular choice for learning from evolving data streams. This popularity is due to (i) the ability to simulate simple, yet, successful ensemble learning strategies, such as bagging and random forests; (ii) the possibility of incorporating drift detection and recovery in conjunction to the ensemble algorithm; (iii) the availability of efficient incremental base learners, such as Hoeffding Trees. In this work, we introduce the Streaming Random Patches (SRP) algorithm, an ensemble method specially adapted to stream classification which combines random subspaces and online bagging. We provide theoretical insights and empirical results illustrating different aspects of SRP. In particular, we explain how the widely adopted incremental Hoeffding trees are not, in fact, unstable learners, unlike their batch counterparts, and how this fact significantly influences ensemble methods design and performance. We compare SRP against state-of-the-art ensemble variants for streaming data in a multitude of datasets. The results show how SRP produce a high predictive performance for both real and synthetic datasets. Besides, we analyze the diversity over time and the average tree depth, which provides insights on the differences between local subspace randomization (as in random forest) and global subspace randomization (as in random subspaces).

The ever-growing nature of user generated data in online systems poses obvious challenges on how we process such data. Typically, this issue is regarded as a scalability problem and has been mainly addressed with distributed algorithms able to train on massive amounts of data in short time windows. However, data is inevitably adding up at high speeds. Eventually one needs to discard or archive some of it. Moreover, the dynamic nature of data in user modeling and recommender systems, such as change of user preferences, and the continuous introduction of new users and items make it increasingly difficult to maintain up-to-date, accurate recommendation models. The objective of this workshop is to bring together researchers and practitioners interested in incremental and adaptive approaches to stream-based user modeling, recommendation and personalization, including algorithms, evaluation issues, incremental content and context mining, privacy and transparency, temporal recommendation or software frameworks for continuous learning.

A well-known learning task in big data stream mining is classification. Extensively studied in the offline setting, in the streaming setting - where data are evolving and even infinite - it is still a challenge. In the offline setting, training needs to store all the data in memory for the learning task; yet, in the streaming setting, this is impossible to do due to the massive amount of data that is generated in real-time. To cope with these resource issues, this paper proposes and analyzes several evolving naive Bayes classification algorithms, based on the well-known count-min sketch, in order to minimize the space needed to store the training data. The proposed algorithms also adapt concept drift approaches, such as ADWIN, to deal with the fact that streaming data may be evolving and change over time. However, handling sparse, very high-dimensional data in such framework is highly challenging. Therefore, we include the hashing trick, a technique for dimensionality reduction, to compress that down to a lower dimensional space, which leads to a large memory saving.We give a theoretical analysis which demonstrates that our proposed algorithms provide a similar accuracy quality to the classical big data stream mining algorithms using a reasonable amount of resources. We validate these theoretical results by an extensive evaluation on both synthetic and real-world datasets.

One of the important indices defined for a set of vertices in a graph is group betweenness centrality. While in recent years a number of approximate algorithms have been proposed to estimate this index, there is no comprehensive and in-depth analysis and comparison of these algorithms in the literature. In this paper, we first present a generic algorithm that is used to express different approximate algorithms in terms of probability distributions. Using this generic algorithm, we show that interestingly existing methods have the same theoretical accuracy. Then, we present an extension of distance-based sampling to group betweenness centrality, which is based on a new notion of distance between a single vertex and a set of vertices. In the end, to empirically evaluate efficiency and accuracy of different algorithms, we perform experiments over several real-world networks. Our extensive experiments reveal that those approximate algorithms that are based on shortest path sampling are orders of magnitude faster than those algorithms that are based on pair sampling, while these two types of algorithms have almost comparable empirical accuracy.

An important index widely used to analyze social and information networks is betweenness centrality. In this paper, given a dynamic and directed graph G and a vertex r in G, we present the DyBED algorithm that updates the (approximate) betweenness centrality of r, when an update operation (vertex/edge insertion/deletion) occurs in G. Our algorithm first during pre-processing computes two subsets of the vertex set of G, called ΠT(r) and ΠT(r). The Cartesian product of these two sets defines the sample space of our algorithm. In other words, each sample is a pair, whose first element belongs to ΠT(r) and second element belongs to ΠT(r). Then after each update operation, DyBED updates the sets ΠT(r) and ΠT(r), the sampled pairs, the information stored for each sample and accordingly, the betweenness centrality of r. We theoretically and empirically evaluate DyBED and show that it yields significant improvement over existing work. In particular, our extensive experiments reveal that DyBED is orders of magnitude faster than most efficient existing algorithms.

Data ubiquity highlights the need of efficient and adaptable data-driven solutions. In this paper, we present FAST AND SLOW LEARNING (FSL), a novel unified framework that sheds light on the symbiosis between batch and stream learning. FSL works by employing Fast (stream) and Slow (batch) Learners, emulating the mechanisms used by humans to make decisions. We showcase the applicability of FSL on the task of classification by introducing the FAST AND SLOW CLASSIFIER (FSC). A Fast Learner provides predictions on the spot, continuously updating its model and adapting to changes in the data. On the other hand, the Slow Learner provides predictions considering a wider spectrum of seen data, requiring more time and data to create complex models. Once that enough data has been collected, FSC trains the Slow Learner and starts tracking the performance of both learners. A drift detection mechanism triggers the creation of new Slow models when the current Slow model becomes obsolete. FSC selects between Fast and Slow Learners according to their performance on new incoming data. Test results on real and synthetic data show that FSC effectively drives the positive interaction of stream and batch models for learning from evolving data streams.

Bitcoin is one of the most prominent decentralized digital cryptocurrencies. Ability to understand which factors drive the fluctuations of the Bitcoin price and to what extent they are predictable is interesting both from the theoretical and practical perspective. In this paper, we study the problem of the Bitcoin short-term volatility forecasting based on volatility history and order book data. Order book, consisting of buy and sell orders over time, reflects the intention of the market and is closely related to the evolution of volatility. We propose temporal mixture models capable of adaptively exploiting both volatility history and order book features. By leveraging rolling and incremental learning and evaluation procedures, we demonstrate the prediction performance of our model as well as studying the robustness, in comparison to a variety of statistical and machine learning baselines. Meanwhile, our temporal mixture model enables to decipher the time-varying effect of order book features on volatility. It demonstrates the prospect of our temporal mixture model as an interpretable forecasting framework over heterogeneous Bitcoin data.

Real-time mining of evolving data streams involves new challenges when targeting today's application domains such as the Internet of the Things: increasing volume, velocity and volatility requires data to be processed on-the-fly with fast reaction and adaptation to changes. This paper presents a high performance scalable design for decision trees and ensemble combinations that makes use of the vector SIMD and multicore capabilities available in modern processors to provide the required throughput and accuracy. The proposed design offers very low latency and good scalability with the number of cores on commodity hardware when compared to other state-of-the art implementations. On an Intel i7-based system, processing a single decision tree is 6× faster than MOA (Java), and 7× faster than StreamDM (C++), two well-known reference implementations. On the same system, the use of the 6 cores (and 12 hardware threads) available allow to process an ensemble of 100 learners 85× faster that MOA while providing the same accuracy. Furthermore, our solution is highly scalable: on an Intel Xeon socket with large core counts, the proposed ensemble design achieves up to 16× speedup when employing 24 cores with respect to a single threaded execution.

Detecting over-indebtedness, the difficulties meeting household payment commitments, poses multiple Big Data challenges for banking institutions. We present a novel data-driven framework for predicting over-indebtedness on realworld data. A warning mechanism that generates predictions 6 months ahead, improving the chances of financial recovery. This framework is based on the combination of feature selection and supervised learning techniques, and uses data balancing for fine-tuning the predictive models. We propose two versions of the framework based on state-of-the-art batch and streaming learning techniques. To the best of our knowledge, the proposed framework is the first to cast over-indebtedness prediction as a stream learning problem. The appeal of stream learning rises from the large amount of data continuously generated, and the fact that batch models become obsolete over time as financial data evolves, while stream models are continuously updated as new data is available. We use credit data from two banks from the Groupe BPCE (the second-largest banking institution in France) and apply multi-metric criteria to evaluate model performance and fairness. Test results show the framework's interbank applicability and that the proposed batch and stream frameworks outperform the current solution for both single and multi-metric criteria. Additionally, the generic structure of the framework serves as a template for systematically approaching similar classification problems.

Nowadays real-time industrial applications are generating a huge amount of data continuously every day. To process these large data streams, we need fast and efficient methodologies and systems. A useful feature desired for data scientists and analysts is to have easy to visualize and understand machine learning models. Decision trees are preferred in many real-time applications for this reason, and also, because combined in an ensemble, they are one of the most powerful methods in machine learning.

IoT big data requires new machine learning methods able to scale to large size of data arriving at high speed. Decision trees are popular machine learning models since they are very effective, yet easy to interpret and visualize. In the literature, we can find distributed algorithms for learning decision trees, and also streaming algorithms, but not algorithms that combine both features. In this paper we present the Vertical Hoeffding Tree (VHT), the first distributed streaming algorithm for learning decision trees. It features a novel way of distributing decision trees via vertical parallelism. The algorithm is implemented on top of Apache SAMOA, a platform for mining big data streams, and thus able to run on real-world clusters. Our experiments to study the accuracy and throughput of VHT prove its ability to scale while attaining superior performance compared to sequential decision trees.

The challenge of deriving insights from the Internet of Things (IoT) has been recognized as one of the most exciting and key opportunities for both academia and industry. Advanced analysis of big data streams from sensors and devices is bound to become a key area of data mining research as the number of applications requiring such processing increases. Dealing with the evolution over time of such data streams, i.e., with concepts that drift or change completely, is one of the core issues in IoT stream mining. This tutorial is a gentle introduction to mining IoT big data streams. The first part introduces data stream learners for classification, regression, clustering, and frequent pattern mining. The second part deals with scalability issues inherent in IoT applications, and discusses how to mine data streams on distributed engines such as Spark, Flink, Storm, and Samza.

Decision rules are one of the most expressive and interpretable models for machine learning. In this article, we present Adaptive Model Rules (AMRules), the first stream rule learning algorithm for regression problems. In AMRules, the antecedent of a rule is a conjunction of conditions on the attribute values, and the consequent is a linear combination of the attributes. In order to maintain a regression model compatible with the most recent state of the process generating data, each rule uses a Page-Hinkley test to detect changes in this process and react to changes by pruning the rule set. Online learning might be strongly affected by outliers. AMRules is also equipped with outliers detection mechanisms to avoid model adaption using anomalous examples. In the experimental section, we report the results of AMRules on benchmark regression problems, and compare the performance of our system with other streaming regression algorithms.

The evaluation of classifiers in data streams is fundamental so that poorly-performing models can be identified, and either improved or replaced by better-performing models. This is an increasingly relevant and important task as stream data is generated from more sources, in real-time, in large quantities, and is now considered the largest source of big data. Both researchers and practitioners need to be able to effectively evaluate the performance of the methods they employ. However, there are major challenges for evaluation in a stream. Instances arriving in a data stream are usually time-dependent, and the underlying concept that they represent may evolve over time. Furthermore, the massive quantity of data also tends to exacerbate issues such as class imbalance. Current frameworks for evaluating streaming and online algorithms are able to give predictions in real-time, but as they use a prequential setting, they build only one model, and are thus not able to compute the statistical significance of results in real-time. In this paper we propose a new evaluation methodology for big data streams. This methodology addresses unbalanced data streams, data where change occurs on different time scales, and the question of how to split the data between training and testing, over multiple models.

Decision rules are among the most expressive data mining models. We propose the first distributed streaming algorithm to learn decision rules for regression tasks. The algorithm is available in SAMOA (Scalable Advanced Massive Online Analysis), an open-source platform for mining big data streams. It uses a hybrid of vertical and horizontal parallelism to distribute Adaptive Model Rules (AMRules) on a cluster. The decision rules built by AMRules are comprehensible models, where the antecedent of a rule is a conjunction of conditions on the attribute values, and the consequent is a linear combination of the attributes. Our evaluation shows that this implementation is scalable in relation to CPU and memory consumption. On a small commodity Samza cluster of 9 nodes, it can handle a rate of more than 30000 instances per second, and achieve a speedup of up to 4.7x over the sequential version.

The area of multi-label classification has rapidly developed in recent years. It has become widely known that the baseline binary relevance approach can easily be outperformed by methods which learn labels together. A number of methods have grown around the label power set approach, which models label combinations together as class values in a multi-class problem. We describe the label-power set-based solutions under a general framework of meta-labels and provide some theoretical justification for this framework which has been lacking, explaining how meta-labels essentially allow a random projection into a space where non-linearities can easily be tackled with established linear learning algorithms. The proposed framework enables comparison and combination of related approaches to different multi-label problems. We present a novel model in the framework and evaluate it empirically against several high-performing methods, with respect to predictive performance and scalability, on a number of datasets and evaluation metrics. This deployment obtains competitive accuracy for a fraction of the computation required by the current meta-label methods for multi-label classification.

Influence-driven diffusion of information is a fundamental process in social networks. Learning the latent variables of such process, i.e., the influence strength along each link, is a central question towards understanding the structure and function of complex networks, modeling information cascades, and developing applications such as viral marketing.

The success of simple methods for classification shows that is is often not necessary to model complex attribute interactions to obtain good classification accuracy on practical problems. In this article, we propose to exploit this phenomenon in the data stream context by building an ensemble of Hoeffding trees that are each limited to a small subset of attributes. In this way, each tree is restricted to model interactions between attributes in its corresponding subset. Because it is not known a priori which attribute subsets are relevant for prediction, we build exhaustive ensembles that consider all possible attribute subsets of a given size. As the resulting Hoeffding trees are not all equally important, we weigh them in a suitable manner to obtain accurate classifications. This is done by combining the log-odds of their probability estimates using sigmoid perceptrons, with one perceptron per class. We propose a mechanism for setting the perceptrons’ learning rate using the change detection method for data streams, and also use to reset ensemble members (i.e., Hoeffding trees) when they no longer perform well. Our experiments show that the resulting ensemble classifier outperforms bagging for data streams in terms of accuracy when both are used in conjunction with adaptive naive Bayes Hoeffding trees, at the expense of runtime and memory consumption. We also show that our stacking method can improve the performance of a bagged ensemble.

Graph mining is a challenging task by itself, and even more so when processing data streams which evolve in real-time. Data stream mining faces hard constraints regarding time and space for processing, and also needs to provide for concept drift detection. In this paper we present a framework for studying graph pattern mining on time-varying streams. Three new methods for mining frequent closed subgraphs are presented. All methods work on coresets of closed subgraphs, compressed representations of graph sets, and maintain these sets in a batch-incremental manner, but use different approaches to address potential concept drift. An evaluation study on datasets comprising up to four million graphs explores the strength and limitations of the proposed methods. To the best of our knowledge this is the first work on mining frequent closed subgraphs in non-stationary data streams.

Due to the ever growing presence of data streams, there has been a considerable amount of research on stream mining algorithms. While many algorithms have been introduced that tackle the problem of clustering on evolving data streams, hardly any attention has been paid to appropriate evaluation measures. Measures developed for static scenarios, namely structural measures and ground-truth-based measures, cannot correctly reflect errors attributable to emerging, splitting, or moving clusters. These situations are inherent to the streaming context due to the dynamic changes in the data distribution. In this paper we develop a novel evaluation measure for stream clustering called Cluster Mapping Measure (CMM). CMM effectively indicates different types of errors by taking the important properties of evolving data streams into account. We show in extensive experiments on real and synthetic data that CMM is a robust measure for stream clustering evaluation.

Advanced analysis of data streams is quickly becoming a key area of data mining research as the number of applications demanding such processing increases. Online mining when such data streams evolve over time, that is when concepts drift or change completely, is becoming one of the core issues. When tackling non-stationary concepts, ensembles of classifiers have several advantages over single classifier methods: they are easy to scale and parallelize, they can adapt to change quickly by pruning under-performing parts of the ensemble, and they therefore usually also generate more accurate concept descriptions. This paper proposes a new experimental data stream framework for studying concept drift, and two new variants of Bagging: ADWIN Bagging and Adaptive-Size Hoeffding Tree (ASHT) Bagging. Using the new experimental framework, an evaluation study on synthetic and real-world datasets comprising up to ten million examples shows that the new ensemble methods perform very well compared to several known methods.

Closed patterns are powerful representatives of frequent patterns, since they eliminate redundant information. We propose a new approach for mining closed unlabeled rooted trees adaptively from data streams that change over time. Our approach is based on an efficient representation of trees and a low complexity notion of relaxed closed trees, and leads to an on-line strategy and an adaptive sliding window technique for dealing with changes over time. More precisely, we first present a general methodology to identify closed patterns in a data stream, using Galois Lattice Theory. Using this methodology, we then develop three closed tree mining algorithms: an incremental one IncTreeNat, a sliding-window based one, WinTreeNat, and finally one that mines closed trees adaptively from data streams, AdaTreeNat. To the best of our knowledge this is the first work on mining frequent closed trees in streaming data varying with time. We give a first experimental evaluation of the proposed algorithms.

We present a new approach for dealing with distribution change and concept drift when learning from data sequences that may vary with time. We use sliding windows whose size, instead of being fixed a priori, is recomputed online according to the rate of change observed from the data in the window itself. This delivers the user or programmer from having to guess a time-scale for change. Contrary to many related works, we provide rigorous guarantees of performance, as bounds on the rates of false positives and false negatives. Using ideas from data stream algorithmics, we develop a time- and memory-efficient version of this algorithm, called ADWIN2. We show how to combine ADWIN2 with the Naïve Bayes (NB) predictor, in two ways: one, using it to monitor the error rate of the current model and declare when revision is necessary and, two, putting it inside the NB predictor to maintain up-to-date estimations of conditional probabilities in the data. We test our approach using synthetic and real data streams and compare them to both fixed-size and variable-size window strategies with good results.