Project Topics
Get Complete Project Material File(s) Now! »
Proactive Drift Detection
In the previous chapter we explored ways to capture the magnitude of concept drift in streaming data. In this chapter we will focus on characterizing the rate of these changes and explore how we can use this information to predict the behaviour of the stream for proactive detection of future drifts. We aim to use meta-knowledge of stream character-istics to improve the accuracy of current drift detection techniques. We believe this could facilitate the development of accurate models that can adapt to dynamic systems and non stationary environments. This chapter is organized as follows. In Section 4.1 we motivate and highlight the di erence between our work with previous research. In Section 4.2 we highlight the importance of mapping drift trends and de ne the key terminology used in this chapter. Section 4.3 presents an overview of our methods. Sections 4.4 and 4.5 discuss the inner workings of our technique. Our experiments are presented and discussed in Section 4.6. Finally we conclude this chapter in Section 4.7.
Introduction
Many drift detection methods have been developed for the detection of changes in the streaming environment [30] [10] [4] [16]. Traditional drift detection methods focus on detecting changes in the underlying model based on the error rate of a classi er. First we will review the traditional drift detection system. In Figure work ow of a typical drift detection system. First the data is passed into a classi er which incrementally builds a model for classi cation based on the input data. The accuracy of the classi er is monitored using a binary error rate stream to detect concept changes signalled by signi cant increases in the error rate. The error rate stream is then passed into a drift detector that detects change using statistical tests. The drift detector can produce three signals. We present an analogy of this in Figure 4.1. The rst is the drift signal which suggests that there is a high probability that a change has occurred. The second is the no change signal. This suggests the concept is stable and that it is unlikely a change has occurred. The third signal is the warning signal. It suggests the concept is likely to be changing and is used to anticipate real changes. Being able to nd these changes allows a classi er to be adapted to changes in the data. However this adaptation process is not well studied. In this chapter we focus on the change detection phase. Currently most methods do not consider additional information such as historical drift trends that could allow the anticipation of future change points. Huang et al. introduced a measure called stream volatility that represents the rate of change of the stream [17]. In their paper, they propose a volatility detector to detect changes in stream volatility and show that there are stream volatility trends for real data streams [17]. Unfortunately they did not use the information beyond nding the volatility trend. By incorporating volatility into traditional drift detectors we can use the additional information to proac-tively determine future changes. This is revolutionary as we are no longer monitoring historical events but anticipating future changes in the data stream. If we are able to map the frequency or interval of changes that occur to a particular pattern we can use this information to predict a future time range that has a high probability of change occurrence. In a recent paper, Huang et al. extend their work to use historical drift points for improving drift detection by introducing a predictive approach using the mean stream volatility to estimate the location of the next drift [16]. However their method assumes that the overall drift rate of the stream is representative of the current drift rate and Data Classi er error rate Drift Detector Volatility Detector adaptation vi = ci ci 1 drift predictions Proactive Detector Drift Predictor does not utilize additional information such as trends of temporal changes in drift rate which may provide more accurate predictions for streams that show reoccurring patterns of volatility change. We believe there are many real life applications that have inherent trends in the rate of changes. For example the rate of electricity usage has both seasonal patterns, and trends that are speci c to the personal habits of a customer. Therefore being able to model these trends may provide us with insights into the behaviour of the entity or concept of interest. We propose a drift predictor for learning stream volatility trends and a proactive drift detector, PROSEED, that uses drift predictions to proactively search for drifts. Our methodology can be summarized by the diagram in Figure 4.2. We modify the traditional drift detection system to incorporate three additional layers, a volatility detector, a drift predictor and a proactive drift detector. The base detector is used to monitor the error rate of the classi er to nd change points ci. Based on this, the volatility detector is used to nd changes in the drift rate vi which represents the time between consecutive drifts. For example, if a change occurred every 15 days, the drift rate would be 15. We use a drift predictor to learn these drift rate trends and predict the possible locations of the next drift. These predictions are then used to modify the behaviour of PROSEED to reduce search e ort during periods where drifts are less likely to occur.
The main contributions of our work are: (1) A drift prediction algorithm that can accurately learn drift trends of a stream and (2) a drift detector which incorporates historical drift rate information that is accurate for streams with reoccurring volatility trends. We analyze our drift prediction technique by comparing it to ground truth in synthetic data streams and show that it can accurately capture trends for streams with reoccurring volatility patterns. We evaluated the performance of our drift detector by comparing it against detectors ADWIN2 [4], SEED [17] and DDM [10] on synthetic and real data streams. We show that our technique is able to lower the rate of false positives for synthetic streams with these trends. Relation to other research: Our research di ers from research in drift detection with recurring patterns [41] as their methods are aimed at detecting models that reoccur whereas our method aims to learn the characteristics of drift rate trends. For example, suppose we are trying to learn the concept of seasons, research in reoccurring patterns focuses on the order that concepts reoccur such as: spring, summer, autumn, winter, spring. Our research aims to look at the rate of concept change, that is the time period between season changes. Unlike research in temporal forecasting for seasonal patterns, we do not assume there is any seasonal e ect to the changes, and the trends do not necessarily occur periodically.
Modelling Stream Volatility
The volatility of a stream describes the rate of change. High volatility indicates frequent changes and low volatility indicates that changes occur less frequently and the stream is more stable. Monitoring volatility can help us understand the nature of changes in a stream and give us important information about where changes may occur in the future. For example, suppose we are interested in modelling tra c ow for GPS systems. Drifts can be analogous to changes in the speed of tra c such as a change in average car speeds from 40km per hour to 20km per hour. Drift volatility can be analogous to the rate of changes in tra c ow. This will tell us how frequent changes in tra c speed are occurring. A high volatility will indicate that changes in tra c speeds are occurring fre-quently, whereas low volatility suggests the tra c speeds are relatively consistent. During peak times such as rush hour, the speed of tra c would be more consistent so changes may occur less frequently. For example, we may observe decreases in tra c speed between 7am-8am, reaching a minimum around 8.30am when the roads are heavily congested. This could be followed by increases in tra c speed after 10am. As there are more changes before and after 8.30am, the volatility would be higher before and after this time period. Therefore modelling these volatility trends may help us estimate when the next change in tra c speed may occur. For example, if we know that a road is currently congested, being able to estimate the future changes may help us predict when there is less tra c. This could help us decide whether we should take an alternate route which could save us time. If we are able to accurately pinpoint when the next change should occur, it may help us develop GPS routing methods that are more adaptive. De nition 9 (Volatility Shift) A volatility shift is a change in the drift rate. A shift in volatility is said to occur when there is a signi cant di erence in the variance of two volatility windows. Let V1 = (vj; vj+1:::; vk) and V2 = (vk+1; vk+2:::; vt 1) represent two volatility windows with sample variances 1; 2 respectively. A volatility shift is detected when 1 7 1:0 +where is a user de ned threshold. We follow the volatility shift de nition proposed by Huang et al. [17] that formalizes this as a change in the variance between two volatility windows. Recall that a volatility window consists of intervals between consecutive drifts. We refer to these intervals as drift intervals, drift rates or volatility. We are interested in modelling the changes in volatility, so we need to keep a history of the volatility changes that we have previously observed. To model the volatility of a stream, we introduce a term called volatility pattern that represents a snapshot of the stream’s volatility at a particular time. We assume that this has a certain distribution. We give a formal de nition of volatility pattern in De nition 10.De nition 10 (Volatility Pattern) A volatility pattern p = fvm; vm+1; :::; vng con-sists of a set of volatility values and a pattern length lp. The set of drift intervals fvm; vm+1; :::; vng is a subset of the intervals in the volatility windows V10 [ V2 where the window V10 = (vi; vi+1; :::; vk) and i j < k. This represents a snapshot of the stream volatility at time t that has a distribution D with a mean of and variance of 2. The pattern length lp is the average number of time steps spent in pattern p prior to a volatility shift at t .For example, given we detected a volatility shift at time t and observed two volatility windows V10 = (100; 150; 100) and V2 = (100; 150; 500). The pattern can be estimated to be p1 = f100; 150; 100; 100; 150g whichhas a distribution with a mean of f100;150;100;100;150g = 120 and a variance of f2100;150;100;100;150g = 750. Pattern p1 represents a snapshot of the stable portion of the stream volatility. This then allows us to characterize the volatility changes as transitions between volatility patterns. De nition 11 (Pattern Transition) A pattern transition p1 ! p2 at time t is a volatil-ity shift at time t, where there is a change in the distribution generating the drift rate from distribution D1 corresponding to the volatility pattern p1 to a distribution D2 which cor-responds to the volatility pattern p2. Following from the previous example. Suppose we rst observed pattern p1, then at a later point in time t we detect a volatility shift and observe the pattern p2. Let p1 = f100; 150; 100; 100; 150g and p2 = f1000; 1500; 1000; 1000; 1500g. A transition p1 ! p2 at time step t means that there is a change in volatility at t from observing a change every 100 time steps to observing a change every 1000 time steps. We generalize streams with volatility changes into two categories: (1) streams with rapid volatility change, and (2) streams with progressive volatility change. Rapid volatility changes represent periods of stable volatility punctuated by large sudden changes in the volatility distribution. Progressive volatility changes represent small incremental changes in the volatility distribution. In Figures 4.3 and 4.4 we show the volatility trends in blue, where each data point represents a drift interval. We highlight the local maxima and minima in yellow. Ideally this is where we would like to detect a volatility shift. For example, suppose the volatility of the stream is 100; 100; 100; 200; 200; 200; 100; ::: as shown in Figure 4.3. This represents a stream with rapid volatility change because there is a sudden change in drift rate from 100 to 300, preceded by periods of stability. For example, suppose the volatility of the stream is 100; 130; 160; 200; 160; 130; 100; ::: as shown in Figure 4.4. This would be considered a progressive volatility change because the volatility changes are incremental in nature. If we are able to capture the volatility shifts at the correct locations, and accurately estimate the patterns this would allow us to predict the future volatility. This may be advantageous for streams with reoccurring volatility trends because predicting the next drift location allows us to anticipate this change and adapt our behaviour based on the gained information. For example, suppose we are using a GPS for routing and we predict that there would be heavy tra c on Great South Road during the next two hours, having this extra information allows us to avoid routes that are potentially congested.
Overview
In this section we provide a general overview of our drift prediction method, DPM, that estimates the next drift point based on historical drift trends and our proposed algorithm, PROSEED, a proactive drift detector that uses the estimates from the drift predictor to guide the search for changes.
Drift Prediction Method
Our drift prediction method has three layers – a drift detector that provides the drift points and drift intervals, a volatility detector that is able to locate local volatility change points using the drift intervals, and a drift prediction algorithm that uses the location of volatility shifts to estimate the next drift. We use a pattern reservoir and probabilistic network to learn the volatility trends of a stream.
1 Introduction
1.1 Motivation
1.2 Problem Statement
1.3 Objectives
1.4 Contributions
1.5 Overview of Research
1.6 Structure of Thesis
2 Background and Related Work
2.1 Concept Drift
2.2 Drift Detectors
2.3 Reoccurring Concepts
2.4 Characterization of Concept Drift
2.5 Datasets
3 Tracking Drift Severity
3.1 Introduction
3.2 Preliminaries
3.3 Overview
3.4 Drift Magnitude Detection
3.5 Alternative approaches
3.6 Experiments
3.7 Conclusions
4 Proactive Drift Detection
4.1 Introduction
4.2 Modelling Stream Volatility
4.3 Overview
4.4 Drift Prediction Method
4.5 Proactive Drift Detection
4.6 Experiments
4.7 Conclusions
5 Conclusions
5.1 Achievements
5.2 Limitations
5.3 Future Work
GET THE COMPLETE PROJECT
Characterizing Drifts for Proactive Drift Detection in Data Streams
