-The paper presents a novel method for reconstruction of missing data in time series. The method is based on the decomposition of known parts of time series into monocomponents (Intrinsic Mode Functions, IMF) using Empirical Mode Decomposition (EMD), construction of prediction models for each IMF using known parts of times series and their composition using weighted average. We demonstrate the efficiency of the proposed approach using a synthetic time series data.
Knowledge-based decision-making processes (such as
business decisions) are very dependent on the availability of data,
from which information can be extracted. These processes
often use predictive models or other computational intelligence
technique that take observed data as inputs. However, in
some cases due to various reasons (power failure, sensor
failure, maintenance, human error, etc.) data could be lost,
corrupted or recorded incompletely, which affects the
quality of data negatively. Most decision-making and machine
learning tools such as the commonly used Artificial Neural
Networks (ANN), Support Vector Machines (SVM), Principal
Component Analysis (PCA) and many other computational
intelligence techniques cannot be used for decision making
if data are not complete [
The task, also known as missing value imputation [
The applications of gap filling (aka missing data imputation)
are numerous and include bioinformatics (gene microarray
data) [
The specific gap filling methods can be categorized
according to the type of information used as global and local. Using
global approach, the algorithms perform missing values
estimation based on global correlation information obtained from
the entire data matrix. An example of such algorithms includes
the SVD imputation [
The signal decomposition methods split the signal into additive components. The time series are then reconstructed using only the components of interest, usually by removing the high frequency components considered as noise. Because the decomposition is performed over a limited temporal window, only a limited amount of information is used when filling gaps.
The Iterative Caterpillar Singular Spectrum Analysis
Method (ICSSA) [
Empirical mode decomposition (EMD) method [
The aim of this paper is to propose and evaluate a novel method for reconstruction of missing data in time series. The method is based on the decomposition of known parts time series into mono-components (IMFs) using EMD, construction of prediction models for each IMF using known parts of times series and their composition using weighted average.
The structure of the remaining parts of the paper is as follows. The proposed method is described in Section II. The metrics for evaluation the accuracy of the solution are discussed in Section III. The experiment is described in Section IV. The results of the experiment are presented in Section V. Finally, conclusions and discussion of future work are presented in Section VI.
Consider a time series X 2 RT with m T 2 data points missing. The missing data are indicated by a vector X^ 2 Rm with components xt = 1 for all t 2 1; 2; : : : ; T where xt is defined, and xt = 1 for all t 2 1; 2; : : : ; T where xt is not defined. Let the zero crossing rate of X be zcr(X) =
T X I xtxt 1 < 0 t=1 (1) here IfAg is the Iverson operator: IfAg is 1 if its argument A is true, and 0 otherwise.
Hereinafter we introduce the simplification and consider only such X; for which zcr(X) = 2 and x0 = 1: That is the time series starts with known data, then follows all missing data, and the time series ends with known data. Hereinafter, we denote the known data at the beginning of the time series X before the missing data as the left series Xl; and the known data at the end of the time series X after the missing data as the right series Xr; and the missing series as Xm:
The proposed method consists of the following steps: 1) Perform decomposition of Xl into a set of IMFs IM Fl; and decompose Xr into a set of IMFs IM Fr using EMD. 2) Perform prediction of IM Fl into the future by m steps using the polynomial prediction model. Let predicted set of series is IM F 0: 3) Perform prediction of IM Fr into the past by m steps using the polynomial prediction model. Let the predicted set of series be IM F 00: 4) Combine the predicted series IM F 0 and IM F 00 using the linearly weighted average. Let the result be IM F: 5) Sum IM F to derive the prediction of Xm: as Y:
The steps comprising EMD method [
As a result, n orthogonal IMFs are obtained from which the original signal may be reconstructed as follows x(t) =
X IM Fi(t) + R(t): i (2)
Prediction is performed using a polynomial model that finds coefficients for a polynomial p(x) of degree n that is a best fit (in a least-squares sense) for the data in y using M previous values of x. Here a linear case of the model is shown: p(xi) = a0xi 1 + a1xi 2 + : : : + aM 1xi M + aM : (3)
The predictions are averaged using the weighted average as follows:
X = X0w(t) + X00(1 w(t)); (4) where w(t) is a linear monotonous increasing function in the range [0; 1] from 0 to m 1:
III. PERFORMANCE EVALUATION USING STATISTICAL
MEASURES
Evaluation of the data gap filling results is a crucial step to demonstrate reliability and accuracy of the proposed method. In validation, the performance indices are computed between the reconstructed and known original values. The quality of the reconstructed data also can be evaluated independently of the original data using the smoothness criterion.
We evaluate the accuracy of the results using the following metrics:
respect to the estimated variable y is defined as the square root of the mean squared error:
RM SE = r Pn i=1(xi n yi)2 ; where x1; x2; : : : ; xn are n observed values and y1; y2; : : : ; yn are the corresponding values predicted.
Mean Absolute Error (MAE) measures the average magnitude of the errors in a set of forecasts, without considering their direction. It is used to measure how close forecasts or predictions are to the eventual outcomes: (5) (6) (7)
Pearson correlation coefficient R2 is a measure of the strength and direction of the linear relationship between two variables that is defined as:
R2 =
P(xi P(xi
x)(yi x)2 P(yi y) 2 y)2 : (8)
We use the following synthetic time series (also analyzed in [18]):
2 2 2 x(t) = sin t cos t + sin t (9) 300 40 2 120
The known data to the left and right of the gap was decomposed using EMD and the IMFs were derived. The polynomial model based prediction method described in Section II.D was used to derive the forward prediction from the IMF data to left side of the gap and the backward prediction from the IMF data to the right side of the gap.
Fig. 1 shows a fragment of the original time series with missing data (gap is in the middle of the time series, gap length = 50). Fig. 2 shows the IMFs derived for known continuous fragments of data before and after the gap. Fig. 3 shows the adjusted IMFs with reconstructed IMF values for the missing data using the combination of forward and backward prediction using linearly weighted averaging. Finally, Fig. 4 shows the true data and reconstructed data (only the gap of time series is shown).
For comparison, the results of reconstruction without signal decomposition are also shown. Even by visual inspection of figures we can see that the proposed method performs better.
To obtain a statistically valid evaluation of the efficiency of the method, we, first, have generated a synthetic series with a large length N = 10000 : Then we have extracted M = 20 different subseries of selected length 500; 1000; 2000 at random locations of the original large time series. The gap in the data is always located in the middle of series and has the length of K(K = 10; 20; : : : ; 100). Gap filling is performed using the proposed method and accuracy is calculated. Results of computational experiments are presented in Section V. n M AE = 1 X n i=1 jxi yij:
Mean Square Error (MSE). If yi is a vector of n predictions, and xi is the vector of observed values corresponding to the inputs to the function which generated the predictions, then the MSE of the predictor can be estimated by:
n M SE = 1 X(xi n i=1 yi)2:
In order to evaluate the performance of the gap-filling, we have repeated the gap filling experiment 20 times with different subseries at random locations of the original time series. The numerical simulation was performed using MATLAB 8.1 (R2013a). The experimental results are presented in Figs. 5-8 for the values of RMSE, MAE, MSE and Pearson correlation values vs the gap ration (length of gap divided by the length of subseries under consideration).
We can see that the EMD decomposition-based method fails to improve the accuracy of missing data reconstruction for large gaps. Yet, when the size of gap is small (10 or less), the method allows to achieve some improvement as compared with the direct prediction of missing data from the known time series data. The results are summarized in Tables I-II.
The paper has presented a novel method for the reconstruction of missing data in time series. The proposed method is model-free, fully data-driven, and does not impose any technical assumptions. The results of experiments with the synthetic data show that better results have not been achieved for gap filling task using the EMD decomposition if gap length is large (more than 10 missing data points). The reasons for that may be the inherent deficiencies of the EMD method
TABLE II RESULTS WITHOUT AND WITH DECOMPOSITION FOR SUBSERIES OF
LENGTH 1000 Gap length
Decomposition the accuracy of analysis results. The correct prediction of locations of minima and maxima in data gap, could allow to better estimate the envelope of data. The main reasoning for using EMD is that IMFs would be less complex than the original data. However, the higher frequency IMFs do not always have a simple waveform, which would allow more accurate prediction of their values. Thus no gain by predicting a simpler could be achieved. Additionally, the method requires more computation, which also negatively affects the accuracy.
Future work will focus on performing more extensive experiments with synthetic time series and the application of the proposed method to real world time series and the examination of other signal decomposition and prediction methods to overcome the shortcoming of EMD and to improve the proposed method. also noted by other researchers such as the boundary problem and the mode mixing problem, which can significantly affect [17] A. Moghtaderi, P. Borgnat, P. Flandrin, Gap-filling by the empirical mode decomposition, Proc. of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3821-3824, 2012. [18] D. Kondrashov and M. Ghil, Spatio-temporal filling of missing points in geophysical data sets Nonlinear Processes in Geophysics, vol. 13, pp. 151-159, 2006.