Mining evolving datastreams raises the question how to extrapolate trends in the evolution of densities over time. While approaches for change diagnosis work well for interpolating spatio-temporal densities, they are not designed for extrapolation tasks. This work studies the temporal density extrapolation problem and sketches two approaches that addresses it. Both use a set of pseudo-points in combination with spatio-temporal kernel density estimation. The rst, weightextrapolating approach, uses regression on the weights of stationarylocated pseudo-points. The second, location-extrapolating approach, extrapolates the trajectory of uniformly-weighted pseudo-points within the feature space.
https://kmd.cs.ovgu.de/res/driftmining
Density estimation methods, like kernel density estimation [
We propose and study two approaches to address this problem. Both use extrapolation of pseudo-points in combination with spatio-temporal kernel density estimation. The rst approach extrapolates the weights of stationary located pseudo-points, while the second extrapolates the path of moving pseudo-points of xed weight. Subsequently, these weight- or position-extrapolated pseudo-points are used in a spatio-temporal kernel density estimation.
Copyright©2015 for this paper by its authors. Copying permitted for private and academic purposes.
In the following Section 2, we review the related work, before sketching the two approaches in Section 3 and concluding in Section 4. 2
The task of estimating the probability density based on a sample of
independently and identically distributed (iid) observations has been intensively studied.
Density estimation methods, like kernel density estimation [
In the case of a nonstationary distribution, one might be interested in
estimating the density at di erent points in time and space. In [
Related to change diagnosis is change mining [
Density forecasting approaches [
In contrast to density forecasting above, we are concerned with temporal
density extrapolation of a potentially multi-modal density distribution.
Furthermore, instead of having a time series of single observations at any one time,
our input data consists of multiple observations at any one time. This temporal
density extrapolation is related to spatial density extrapolation [
To address the problem of extrapolating the observed, potentially multi-modal density-distribution of instances to future time points, we propose an approach based on pseudo-points. These pseudo-points are used in the spatio-temporal kernel density estimation in lieu of the originally observed instances. The resulting kernel density estimation model can be interpreted as a mixture model, where each pseudo-point constitutes itself a component. The pseudo-points evolve over time, either by changing their weight (their component's mixing proportion), or by changing their position (their component's location). Therefore, the learning task is to t a trend function to the evolution of each pseudo-point. We present each of the two variants in the next Subsections 3.1 and 3.2, before discussing their potential di culties and limitations in Section 3.3. 3.1
Given a set of stationary pseudo-points, the rst approach models their weights as functions of time. These functions are then t on a window with historical data, such that the distribution therein is modelled with maximum likelihood.
The approach is illustrated for a one-dimensional feature space in Figure 1. At the rst time point in the past (time = 0), a density estimate is calculated using historical data collected at that time (solid blue line). Then, a set of pseudo-points (here 1; 2; 4) is generated, either by placing them equidistant on a grid or by drawing them at random. Next, the weights (w1; w2; w4) of all pseudo-points are calculated such that the divergence is minimised between the kernel density estimate over the weighted pseudo-points and the kernel-density estimate over the original data instances at that time point. The pseudo-point's weights are estimated in the same way for subsequent time points (e.g. t = 1), as soon as instances become available for them. This results for each pseudo-point in a time series of weight values, for which a polynomial trend function (red curves) is learned by regression. Finally, for a future time point (e.g. time = 2), the trend functions' values are predicted (w1; w2; w4 in red at time = 2). Using these weighted pseudo-points in a kernel density estimate at time = 2, one obtains the extrapolated density (red dotted line), which is later evaluated against the observed density (solid blue-gray line). 3.2
Position-Extrapolated, Uniformly-Weighted Pseudo-Points The second approach to address this problem is to use uniformly-weighted, but exibly located pseudo-points. Thus, the pseudo-point's weights are uniform and constant, but their positions are functions of time, tted such that the divergence on the available historical data is minimised.
In analogy to the previous gure, this approach is illustrated for a onedimensional feature space in Figure 2. Given a set of historical instances and a speci ed number of pseudo-points, density estimates (solid blue lines) are made for historical time points (time = 0 and time = 1). Then, a mixture model with each pseudo-point as a single Gaussian component is formulated. Assuming polynomial trajectories (red solid lines) for the pseudo-points, the parameters of this model are the coe cients of the pseudo-points polynomial trajectories, which are learned using Expectation-Maximisation. Finally, for a future time point (time = 2), the pseudo-point's positions are predicted using the polynomial function, and the density (red dotted line) at this time point is estimated using kernel density estimation over the pseudo-points placed at their extrapolated positions. 3.3
Both approaches above rely on a regression over time for extrapolating trends in the development of either weights or positions. In order to make this extrapolation more robust, we recommend using regularised trend functions that consider penalties for the models' complexities. The choice of the type of regression function depends on the type of drift, as for example polynomial functions require gradual drift, while trigonometric functions seem to be interesting candidates for modelling recurring context.
The weight-extrapolation in the rst approach requires a normalisation, such that the extrapolated weights are all non-negative and sum up to one. An important question concerns the choice of the pseudo-point's location in this approach, Temporal Density Extrapolation 5 3 w 2 tim e w feature X 4 4 w 1 w 3 w 2 w
X Observed Density Extrapolated Density Extrapolated Pseudopoint Weight y t i s n e d 0 y t i s n e d 0 1 2 tim e feature X
X
X as it in uences the precision of the extrapolated values: in regions with sparse pseudo-point populations, the model is less exible than in densely populated ones. Therefore, this approach seems better suited for constricted (bounded) feature spaces. A simple equidistant placement of pseudo-points distributes the precision over the whole feature space. Alternatively, the pseudo-points might be placed at the coordinates of a subsample of the observed instances, thus concentrating the precision on areas with previously high density. However, if densities change largely over time, these areas might become less relevant.
In contrast, the second, position-extrapolating approach determines the positions of each pseudo-point automatically. It aims to adjust the future location of the pseudo-points such that they are densely placed in regions with a high expected density. However, in the case polynomial regression functions are used, a potential drawback is that their trajectories diverge in the long run. Thus, in contrast to the rst approach, the second one seems to be better suited for in nite (unbounded) feature spaces.
Related to the choice of the pseudo-points' placements is the question of
optimal bandwidth selection, which for kernel density estimation has already
been reviewed in [
In this paper, we have addressed the problem of temporal density extrapolation, where the objective is the prediction of a (potentially multi-modal) density distribution at future time points, given a sample of historical instances observed at di erent positions in feature space and at di erent times in the past. Two approaches based on pseudo-points were sketched: the rst uses an extrapolation of time-varying weights of stationary located pseudo-points, while the second uses an extrapolation of the trajectory of the time-varying location of pseudo-points with uniform weights. Subsequently, these extrapolated pseudo-points are used in a kernel density estimation at future time points.
Having sketched the idea of the two temporal density extrapolation
approaches, a more detailed speci cation and evaluation of these methods needs
to be done in future work. Furthermore, the conjectures in the discussion above,
in particular the usability of each approach for bounded and unbounded
feature spaces, need to be veri ed. Finally, a known challenge for kernel-based
approaches is the curse of dimensionality on multi-dimensional data. A naive
approach is to combine multiple univariate temporal density extrapolations.
However, an optimisation for multi-variate problems by using either projection
pursuit [