Ensemble Online Classifier Based on the One-Class Base Classifiers for Mining Data Streams

The problem addressed in this study concerns mining data streams with concept drift. The goal of the article is to propose and validate a new approach to mining data streams with concept-drift using the ensemble classifier constructed from the one-class base classifiers. It is assumed that base classifiers of the proposed ensemble are induced from incoming chunks of the data stream. Each chunk consists of prototypes and information about whether the class prediction of these instances, carried-out at earlier steps, has been correct. Each data chunk can be updated by using the instance selection technique when new data arrive. When a new data chunk is formed, the ensemble model is also updated on the basis of weights assigned to each one-class classifier. In this article, two well-known instance-based learning algorithms—the CNN and the ENN—have been adopted to solve the one-class classification problems and, consequently, update the proposed classifier ensemble. The proposed approaches have been validated experimentally, and the computational experiment results are shown and discussed. The experiment results prove that the proposed approach using the ensemble classifier constructed from the one-class base classifiers with instance selection for chunk updating can outperform well-known approaches for data streams with concept drift.     

A multi-one-class dynamic classifier for adaptive digitization of document streams

In this paper, we present a new dynamic classifier design based on a set of one-class independent SVM for image data stream categorization. Dynamic or continuous learning and classification has been recently investigated to deal with different situations, like online learning of fixed concepts, learning in non-stationary environments (concept drift) or learning from imbalanced data. Most of solutions are not able to deal at the same time with many of these specificities. Particularly, adding new concepts, merging or splitting concepts are most of the time considered as less important and are consequently less studied, whereas they present a high interest for stream-based document image classification. To deal with that kind of data, we explore a learning and classification scheme based on one-class SVM classifiers that we call mOC-iSVM (multi-one-class incremental SVM). Even if one-class classifiers are suffering from a lack of discriminative power, they have, as a counterpart, a lot of interesting properties coming from their independent modeling. The experiments presented in the paper show the theoretical feasibility on different benchmarks considering addition of new classes. Experiments also demonstrate that the mOC-iSVM model can be efficiently used for tasks dedicated to documents classification (by image quality and image content) in a context of streams, handling many typical scenarii for concepts extension, drift, split and merge.     

基于主要特征抽取的重现概念漂移处理算法

针对重现概念漂移检测中的概念表征和分类器选择问题,提出了一种适用于含重现概念漂移的数据流分类的算法——基于主要特征抽取的概念聚类和预测算法（Conceptual clustering and prediction through main feature extraction, MFCCP）。MFCCP通过计算不同批次样本的主要特征及影响因子的差异度以识别重复出现的概念,为每个概念维持且及时更新一个分类器,并依据Hoeffding不等式选择最合适的分类器对当前样本集实施分类,以 提高对概念漂移的反应能力。在3个数据集上的实验表明：MFCCP在含重现概念漂移的数据集上的分类准确率,对概念漂移的反应能力及对概念漂移检测的准确率均明显优于其他4种 对比算法,且MFCCP也适用于对不含重现概念漂移的数据流进行分类。     

Cross the data desert: generating textual-visual summary on the evolutionary microblog stream

Effectively and efficiently summarizing social media is crucial and non-trivial to analyze social media. On social streams, events which are the main concept of semantic similar social messages, often bring us a firsthand story of daily news. However, to identify the valuable news, it is almost impossible to plough through millions of multi-modal messages one by one with traditional methods. Thus, it is urgent to summarize events with a few representative data samples on the streams. In this paper, we provide a vivid textual-visual media summarization approach for microblog streams, which exploits the incremental latent semantic analysis (LSA) of detected events. Firstly, with a novel weighting scheme for keyword relationship, we can detect and track daily sub-events on a keyword relation graph (WordGraph) of microblog streams effectively. Then, to summarize the stream with representative texts and images, we use cross-modal fusion to analyze the semantics of microblog texts and images incrementally and separately, with a novel incremental cross-modal LSA algorithm. The experimental results on a real microblog dataset show that our method is at least 1.31% better and 23.67% faster than existing state-of-the-art methods, and cross-modal fusion can improve the summarization performance by 4.16% on average.

     

An adaptive ensemble classifier for mining concept drifting data streams

It is challenging to use traditional data mining techniques to deal with real-time data stream classifications. Existing mining classifiers need to be updated frequently to adapt to the changes in data streams. To address this issue, in this paper we propose an adaptive ensemble approach for classification and novel class detection in concept drifting data streams. The proposed approach uses traditional mining classifiers and updates the ensemble model automatically so that it represents the most recent concepts in data streams. For novel class detection we consider the idea that data points belonging to the same class should be closer to each other and should be far apart from the data points belonging to other classes. If a data point is well separated from the existing data clusters, it is identified as a novel class instance. We tested the performance of this proposed stream classification model against that of existing mining algorithms using real benchmark datasets from UCI (University of California, Irvine) machine learning repository. The experimental results prove that our approach shows great flexibility and robustness in novel class detection in concept drifting and outperforms traditional classification models in challenging real-life data stream applications.     

An approach of support approximation to discover frequent patterns from concept-drifting data streams based on concept learning

In an online data stream, the composition and distribution of the data may change over time, which is a phenomenon known as concept drift. The occurrence of concept drift can affect considerably the performance of a data stream mining method, especially in relation to mining accuracy. In this paper, we study the problem of mining frequent patterns from transactional data streams in the presence of concept drift, considering the important issue of mining accuracy preservation. In terms of frequent-pattern mining, we give the definitions of concept and concept drift with respect to streaming data; moreover, we present a categorization for concept drift. The concept of streaming data is considered the relationships of frequency between different patterns. Accordingly, we devise approaches to describe the concept concretely and to learn the concept through frequency relationship modeling. Based on concept learning, we propose a method of support approximation for discovering data stream frequent patterns. Our analyses and experimental results have shown that in several studied cases of concept drift, the proposed method not only performs efficiently in terms of time and memory but also preserves mining accuracy well on concept-drifting data streams.     

概念漂移数据流半监督分类综述

在开放环境下,数据流具有数据高速生成、数据量无限和概念漂移等特性.在数据流分类任务中,利用人工标注产生大量训练数据的方式昂贵且不切实际.包含少量有标记样本和大量无标记样本且还带概念漂移的数据流给机器学习带来了极大挑战.然而,现有研究主要关注有监督的数据流分类,针对带概念漂移的数据流的半监督分类的研究尚未引起足够的重视....     

Ensemble learning for data stream analysis: A survey

In many applications of information systems learning algorithms have to act in dynamic environments where data are collected in the form of transient data streams. Compared to static data mining, processing streams imposes new computational requirements for algorithms to incrementally process incoming examples while using limited memory and time. Furthermore, due to the non-stationary characteristics of streaming data, prediction models are often also required to adapt to concept drifts. Out of several new proposed stream algorithms, ensembles play an important role, in particular for non-stationary environments. This paper surveys research on ensembles for data stream classification as well as regression tasks. Besides presenting a comprehensive spectrum of ensemble approaches for data streams, we also discuss advanced learning concepts such as imbalanced data streams, novelty detection, active and semi-supervised learning, complex data representations and structured outputs. The paper concludes with a discussion of open research problems and lines of future research.     

Tracking recurring contexts using ensemble classifiers: an application to email filtering

Concept drift constitutes a challenging problem for the machine learning and data mining community that frequently appears in real world stream classification problems. It is usually defined as the unforeseeable concept change of the target variable in a prediction task. In this paper, we focus on the problem of recurring contexts, a special sub-type of concept drift, that has not yet met the proper attention from the research community. In the case of recurring contexts, concepts may re-appear in future and thus older classification models might be beneficial for future classifications. We propose a general framework for classifying data streams by exploiting stream clustering in order to dynamically build and update an ensemble of incremental classifiers. To achieve this, a transformation function that maps batches of examples into a new conceptual representation model is proposed. The clustering algorithm is then applied in order to group batches of examples into concepts and identify recurring contexts. The ensemble is produced by creating and maintaining an incremental classifier for every concept discovered in the data stream. An experimental study is performed using (a) two new real-world concept drifting datasets from the email domain, (b) an instantiation of the proposed framework and (c) five methods for dealing with drifting concepts. Results indicate the effectiveness of the proposed representation and the suitability of the concept-specific classifiers for problems with recurring contexts.     

Proposal of a new stability concept to detect changes in unsupervised data streams

Learning from continuous streams of data has been receiving an increasingly attention in the last years. Among the many challenges related to mining data streams, change detection is one topic frequently addressed. Being able to determine whether or not data characteristics are changing along time is a major concern for data stream algorithms, be it on the supervised or unsupervised scenario. The unsupervised scenario is particularly relevant due to many practical applications do not provide target labeling information. In this scenario, most of the strategies induce consecutive models over time and compare them in order to detect data changes. In this situation, model changes are assumed to be a consequence of data modifications. However, there is no guarantee this assumption is true, since those algorithms do not rely on any theoretical background to ensure that model divergences truly indicate data changes. The need for such theoretical framework has motivated this paper to propose a new stability concept to establish bounds on the learning abilities of unsupervised algorithms designed to detect changes on data streams. This stability concept, based on the surrogate data strategy from time series analysis, provides learning guarantees for online unsupervised algorithms even in case of time dependency among observations. Furthermore, we propose a new change detection algorithm that meets the requirements of this stability concept. Experimental results on different synthetical scenarios illustrate how the stability concept proposed in this paper is applied to detect changes in unsupervised data streams.     

Flexible decision tree for data stream classification in the presence of concept change, noise and missing values

In recent years, classification learning for data streams has become an important and active research topic. A major challenge posed by data streams is that their underlying concepts can change over time, which requires current classifiers to be revised accordingly and timely. To detect concept change, a common methodology is to observe the online classification accuracy. If accuracy drops below some threshold value, a concept change is deemed to have taken place. An implicit assumption behind this methodology is that any drop in classification accuracy can be interpreted as a symptom of concept change. Unfortunately however, this assumption is often violated in the real world where data streams carry noise that can also introduce a significant reduction in classification accuracy. To compound this problem, traditional noise cleansing methods are incompetent for data streams. Those methods normally need to scan data multiple times whereas learning for data streams can only afford one-pass scan because of data’s high speed and huge volume. Another open problem in data stream classification is how to deal with missing values. When new instances containing missing values arrive, how a learning model classifies them and how the learning model updates itself according to them is an issue whose solution is far from being explored. To solve these problems, this paper proposes a novel classification algorithm, flexible decision tree (FlexDT), which extends fuzzy logic to data stream classification. The advantages are three-fold. First, FlexDT offers a flexible structure to effectively and efficiently handle concept change. Second, FlexDT is robust to noise. Hence it can prevent noise from interfering with classification accuracy, and accuracy drop can be safely attributed to concept change. Third, it deals with missing values in an elegant way. Extensive evaluations are conducted to compare FlexDT with representative existing data stream classification algorithms using a large suite of data streams and various statistical tests. Experimental results suggest that FlexDT offers a significant benefit to data stream classification in real-world scenarios where concept change, noise and missing values coexist.     

Classifying text streams by keywords using classifier ensemble

Traditional approaches for text data stream classification usually require the manual labeling of a number of documents, which is an expensive and time consuming process. In this paper, to overcome this limitation, we propose to classify text streams by keywords without labeled documents so as to reduce the burden of labeling manually. We build our base text classifiers with the help of keywords and unlabeled documents to classify text streams, and utilize classifier ensemble algorithms to cope with concept drifting in text data streams. Experimental results demonstrate that the proposed method can build good classifiers by keywords without manual labeling, and when the ensemble based algorithm is used, the concept drift in the streams can be well detected and adapted, which performs better than the single window algorithm.     

Fault detection based on one-class deep learning for manufacturing applications limited to an imbalanced database

Despite extensive studies for the industrial applications of deep learning, its actual usage in manufacturing sites has been extremely restrained by the difficulty in obtaining sufficient industrial data, especially for production failure cases. In this study, we introduced a fault-detection module based on one-class deep learning for imbalanced industrial time-series data, which consists of three submodules, namely, time-series prediction based on deep learning, residual calculation, and one-class classification using one-class support vector machine and isolation forest. Four different networks were used for the time-series prediction: multilayer perception (MLP), residual network (ResNet), long–short-term memory (LSTM), and ResNet–LSTM, each trained with the one-class data having only the production success cases. We adopted the residuals of the deep-learning prediction as an elaborated feature for the construction of the one-class classification. We also tested the fault-detection module with the actual mass production data of a die-casting process. By adopting the features elaborated by the deep-learning time-series prediction, we showed that the total accuracy of the one-class classification significantly improved from 90.0% to 96.0%. Especially for its capability to detect production failures, the accuracy improved from 84.0% to 96.0%. The area under the receiver operating characteristics (AUROC) also improved from 87.56% to 98.96%. ResNet showed the best performance for detecting production failures, whereas ResNet–LSTM produced better results for ensuring the production success. Our results suggest that the one-class deep learning is a promising approach for extracting important features from time-series data to realize a one-class fault-detection module.     

Knowledge graph embeddings for dealing with concept drift in machine learning

Data stream learning has been largely studied for extracting knowledge structures from continuous and rapid data records. As data is evolving on a temporal basis, its underlying knowledge is subject to many challenges. Concept drift,¹ as one of core challenge from the stream learning community, is described as changes of statistical properties of the data over time, causing most of machine learning models to be less accurate as changes over time are in unforeseen ways. This is particularly problematic as the evolution of data could derive to dramatic change in knowledge. We address this problem by studying the semantic representation of data streams in the Semantic Web, i.e., ontology streams. Such streams are ordered sequences of data annotated with ontological vocabulary. In particular we exploit three levels of knowledge encoded in ontology streams to deal with concept drifts: i) existence of novel knowledge gained from stream dynamics, ii) significance of knowledge change and evolution, and iii) (in)consistency of knowledge evolution. Such knowledge is encoded as knowledge graph embeddings through a combination of novel representations: entailment vectors, entailment weights, and a consistency vector. We illustrate our approach on classification tasks of supervised learning. Key contributions of the study include: (i) an effective knowledge graph embedding approach for stream ontologies, and (ii) a generic consistent prediction framework with integrated knowledge graph embeddings for dealing with concept drifts. The experiments have shown that our approach provides accurate predictions towards air quality in Beijing and bus delay in Dublin with real world ontology streams.     

Evolving Fuzzy Min–Max Neural Network Based Decision Trees for Data Stream Classification

Learning from data streams is a challenging task which demands a learning algorithm with several high quality features. In addition to space complexity and speed requirements needed for processing the huge volume of data which arrives at high speed, the learning algorithm must have a good balance between stability and plasticity. This paper presents a new approach to induce incremental decision trees on streaming data. In this approach, the internal nodes contain trainable split tests. In contrast with traditional decision trees in which a single attribute is selected as the split test, each internal node of the proposed approach contains a trainable function based on multiple attributes, which not only provides the flexibility needed in the stream context, but also improves stability. Based on this approach, we propose evolving fuzzy min–max decision tree (EFMMDT) learning algorithm in which each internal node of the decision tree contains an evolving fuzzy min–max neural network. EFMMDT splits the instance space non-linearly based on multiple attributes which results in much smaller and shallower decision trees. The extensive experiments reveal that the proposed algorithm achieves much better precision in comparison with the state-of-the-art decision tree learning algorithms on the benchmark data streams, especially in the presence of concept drift.     

Incremental Maintenance of Online Summaries Over Multiple Streams

We propose a novel approach based on predictive quantization (PQ) for online summarization of multiple time-varying data streams. A synopsis over a sliding window of most recent entries is computed in one pass and dynamically updated in constant time. The correlation between consecutive data elements is effectively taken into account without the need for preprocessing. We extend PQ to multiple streams and propose structures for real-time summarization and querying of a massive number of streams. Queries on any subsequence of a sliding window over multiple streams are processed in real time. We examine each component of the proposed approach, prediction, and quantization separately and investigate the space-accuracy trade-off for synopsis generation. Complementing the theoretical optimality of PQ-based approaches, we show that the proposed technique, even for very short prediction windows, significantly outperforms the current techniques for a wide variety of query types on both synthetic and real data sets.     

Speed up gradual rule mining from stream data! A B-Tree and OWA-based approach

Gradual rules allow users to be provided with rules describing the ordering correlations among attributes. Such a rule is for instance given by the higher the salary and the lower the number of cars, the higher the number of tourist travels. Previously intensively used in fuzzy command systems, these rules were manually provided to the system. More recently, they have received attention from the data mining community and methods have been defined to automatically extract and maintain gradual rules from numerical databases. However, no method has been shown to be able to handle data streams, as no method is scalable enough to manage the high rate which stream data arrive at. In this paper, we thus propose an original approach to mine data streams for gradual rules. Our method is based on B-Trees and OWA (Ordered Weighted Aggregation) operator in order to speed up the process. B-Trees are used to store already-known gradual rules in order to maintain the knowledge over time, while OWA operators provide a fast way to discard non relevant data.     

易变数据流的系统资源配置方法

大规模数据流管理系统往往由上层的关系查询系统和下层的流处理系统组成。当用户提交查询请求时,往往需要根据数据流的流速和分布情况动态配置系统参数。然而,由于数据流的易变性,频繁改变参数配置会降低系统性能。针对该问题,提出了OrientStream+框架。设定以用户自定义查询延迟阈值为间隔片段的微批量数据流传输机制;并利用多级别管道缓存,对相同配置的数据流进行批量处理;然后按照数据流的时间戳计算出精准查询结果;引入基于异常检测的增量学习模型,用于提高OrientStream+的预测精度。最后,在Storm上实现了该资源配置框架,并进行了大量的实验。实验结果表明,OrientStream+框架可进一步降低系统的处理延迟并提高系统的吞吐率。     

针对标记数据不足的数据流分类器

大部分数据流分类算法解决了数据流无限长度和概念漂移这两个问题。但是,这些算法需要人工专家将全部实例都标记好作为训练集来训练分类器,这在数据流高速到达并需要快速分类的环境中是不现实的,因为标记实例需要时间和成本。此时,如果采用监督学习的方法来训练分类器,由于标记数据稀少将得到一个弱分类器。提出一种基于主动学习的数据流分类算法,该算法通过选择全部实例中的一小部分来人工标记,其中这小部分实例是分类置信度较低的样本,从而可以极大地减少需要人工标记的实例数量。实验结果表明,该算法可以在数据流存在概念漂移情况下,使用较少的标记数据对数据流训练出分类器,并且分类效果良好。     

基于实例迁移的数据流分类挖掘方法

为解决数据流分类过程中样本标注和概念漂移问题，提出了一种基于实例迁移的数据流分类挖掘模型.首先，该模型用支持向量机作学习器，用所得分类模型中的支持向量构建源领域，待分类的当前数据块为目标域.然后，借助互近邻思想在源域中挑选目标域中样本的真邻居进行实例迁移，避免发生负迁移.最后，通过合并目标域和迁移样本形成训练集，提高标注样本数量，增强模型的泛化能力.理论分析和实验结果表明，所提方法具有可行性，相比其它学习方法在分类准确性方面更具优势.