# Incomplete Time Series Prediction Using Max-Margin Classification of Data with Absent Features

Authors: Shang Zhaowei; Zhang Lingfeng; Ma Shangjun; Fang Bin; Zhang  Taiping
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

This paper discusses the prediction of time series with missing data. A novel forecast model is proposed based on max-margin classification of data with absent features. The issue of modeling incomplete time series is considered as classification of data with absent features. We employ the optimal hyperplane of classification to predict the future values. Compared with traditional predicting process of incomplete time series, our method solves the problem directly rather than fills the missing data in advance. In addition, we introduce an imputation method to estimate the missing data in the history series. Experimental results validate the effectiveness of our model in both prediction and imputation.


---

## Body

## 1. Introduction

The subjects of time series prediction have sparked considerable research activities, ranging from short-range-dependent series to long-range-dependent series [1–4], from conventional time series to fractal time series [5, 6]. Traditional predicting technologies are targeted for complete time series, such as Neural networks (NNs) [7], and Support Vector Regression (SVR) [8], and so forth. However, the time series we encountered in real life often contain missing data due to malfunctioned sensors, human factors, and other reasons. When dealing with prediction of incomplete time series, traditional process consists of two steps. The first step is to recover the incomplete time series by an imputation model, and the second step is to estimate the predicting model as complete time series. This process is shown in Figure 1(a). It may consume large number of calculations, and bring deviation for inaccurate imputation. In this paper, we propose a novel predicting model built directly by incomplete time series, which is shown in Figure 1(b).Two distinct processes of incomplete time series prediction.
(a)
Traditional process(b)
Our processThe issue of modeling incomplete time series is interpreted as classification of data with missing features in this paper. We use the optimal hyperplane of the classification to determine the prediction values. A similar approach has been applied to prediction of complete data [9]. In addition, our model is also used as an imputation method, which means estimating the missing data of history series. There have been several works carried out on the imputation of missing data. In the following, these methods are separated into two groups.(1)
Statistical Methods. Examples include Maximum likelihood (ML) algorithm [10], expectation maximization (EM) algorithm [11], Multiple Imputation [12], and so forth. Based on statistical theory, ML and EM algorithms need to know the distribution model of data and often have higher computational complexity. Multiple Imputation, which imputes the missing data M times, assumes that the missing data are Missing At Random (MAR).(2)
Machine Learning Methods. Examples include mean, K-Nearest Neighbor (KNN) [13], Varies Windows Similarity Measure (VWSM) [14] and Regional Gradient Guided Bootstrapping (RGGB) [15], and so forth. KNN algorithm finds a plausible value of missing data by measuring the distance. VWSM algorithm fills the missing data by complete subsequences which are in the similar cycles. RGGB algorithm imputes the missing data by estimating the slopes of the imputing boundary regions. From the results of [15], RGGB algorithm outperforms other traditional imputation methods, such as MI and VWSM. However, it cannot be used to analyze dataset with high fluctuations.Compared with traditional imputation methods, different samples can be selected to calculate the absent data in the history series using our model, which ensures the imputing accuracy of missing data.The rest of this paper is organized as follows. Section2 introduces the establishment of our model. The theory of max-margin classification of data with absent features is reviewed briefly in Section 3. The solution and algorithm of our model are discussed in Section 4. Section 5 follows with the experiments, in which the prediction and imputation performance of our model are tested in detail. Finally, conclusions are presented in Section 6.


## 2. Presentation of Our Model

We start by formalizing the problem of incomplete time series. Assume that a time series with missing data is given as(2.1){x1,x2,?3,…,xd,xd+1,?d+2,…,xq-1,?q,?q+1,…,xn},
where “?” represents the missing data. The sample set X={X1,…,Xd|Xd+1} of the incomplete time series can be formulated as(2.2)X=(x1x2⋯xd|xd+1x2?3⋯xd+1|?d+2?3x4⋯?d+2|xd+3⋮⋮⋱⋮⋮xn-dxn-d+1⋯xn-1|xn),
where d denotes the embedding dimension.Predicting technologies usually establish regression models byX, where Xd+1 acts as the predicting target. In order to predict the value of xk+d,  {xk,xk+1,…,xk+d-1} must be the input data of the model.The implementation process of our model starts by dividing the sample setX into two parts: training set Xt and imputing set Xm. The predicting targets of the training samples in Xt are existing values, while those of the imputing samples in Xm are missing values. Training set is used to construct our predicting model. The role of imputing set is to estimate the missing values.We construct two classes of incomplete dataC1 and C2 by Xt, which can be expressed as(2.3)C1={Xt1,…,Xtp-1,Xtp,…,Xtd+1+ε},C2={Xt1,…,Xtp-1,Xtp,…,Xtd+1-ε},
where  ε is the fitting error. Being the optimal hyperplane of classification of C1 and C2, H is obtained by the theory of max-margin classification of data with missing features. Predicting samples must fall on the hyperplane determined by the training set for a small ε; thus the prediction values can be calculated by H.This model can also be used to predict the missing data of incomplete time series. The imputing samples, taken from the sample set, also fall on the hyperplane. Therefore the missing values can be estimated in the same way as the prediction values. The implementation process of our model is shown in Figure2.Figure 2
The implementation process of our model.In the process of imputation, each missing data can be estimated by all the samples containing it inX, not just the imputing sample in Xm. Assume that xiis absent; the number of different samples we can use to compute the value of xiis (2.4)Ni={i,1≤i≤d,d+1,d+1≤i≤n-d,n-i+1,n-d+1≤i≤n,
where Ni is equal to the frequency of  xiin X.


## 3. Max-Margin Classification of Data with Missing Features

In the previous discussion, the issue of modeling incomplete time series is interpreted as classification of data with missing features. In this section, we review the theory of max-margin classification of data with missing features proposed by Chechik [16].Assume a set of samplesx1,…,xn with missing features. yi denotes the binary class label of xi, and yi∈{-1,1}. Each sample is characterized by a subset of features from a full set 𝔽.The problem of classification can be interpreted as to find an optimal hyperplane with the max-margin framework. In the case of classification of incomplete data, the instance margin treating the margin of each instance in its own relevant subspace is defined as(3.1)ρi(w)=yi(w(i)xi+b)∥w(i)∥,
where w(i) is a vector obtained by taking the entries of w that are related to xi. Considering the geometric margin to be the minimum over all instance margins, it comes to an optimization problem
(3.2)maxw(miniyi(w(i)xi+b)∥w(i)∥).
Define the scaling coefficients si=∥w(i)∥/∥w∥, and rewrite (3.2) as(3.3)maxw(miniyi(w(i)xi+b)∥w(i)∥)=maxw1∥w∥(miniyi(w(i)xi+b)si),si=∥w(i)∥∥w∥.
For a given set of si, we can solve a constrained optimization problem(3.4)maxα∈Rn∑i=1nαi-12∑i,j=1nαiyisi〈xi,xj〉yjsjαjs.t.0≤αi≤C,i=1,…,n,∑i=1nαiyisi=0,
where the inner product  〈·,·〉 is taken only over features that are valid for both xi and xj. The nonlinear classification is solved by using kernels. Thus we obtain the optimal separating hyperplane of classification of data with missing features, which is expressed as (3.5)∑i=1nαiyisiK(x,xi)+b=0,
where b is set as in Support Vector Machines [17, 18].


## 4. Solution and Algorithm

In our model, the hyperplane of classification of data with missing data is used to compute the estimation values. Both predicting samples and imputing samples satisfy (3.5). In this section we introduce the solution and algorithm of our model.


### 4.1. Analytical Solution

Suppose a test samplex′={x1′,x2′,…,xd′,xd+1′}, where xd+1′ is the value to be estimated. In this paper we use the kernel function K′(xi,xj)=(〈xi,xj〉F+1)2. Replacing the kernel of (3.5), we obtain
(4.1)∑i=1nαiyisi(〈x′,xi〉𝔽+1)2+b=0.The simplification of (4.1) is(4.2)∑i=1nαiyisixi,d+12·xd+1′2+2∑i=1nαiyisi(∑j=1dxi,j·xj′+1)xi,d+1·xd+1′+∑i=1nαiyisi(∑j=1dxi,j·xj′+1)2+b=0,
where the product operator  “·”  is taken only over features that are valid for both xi and x′. Equation (4.2) is a quadratic equation of xd+1′, and can be solved easily.


### 4.2. Numerical Solution

Sometimes, analytical solution is meaningless or nonexistent. We need to get numerical solution of our model by iterative algorithms [19, 20]. Still take x′ as an example, supposing we use Newton method, the object function of our model can be represented as(4.3)F(xd+1′)=∑i=1nαiyisiK(x′,xi)+b.The iterative equation ofxd+1′ can be expressed as
(4.4)xd+1′(i+1)=xd+1′(i)-F(xd+1′(i))F(xd+1′(i)).Therefore, the estimation values are calculated by our model effectively. Numerical solution is more complicated, but applicable in every case.In conclusion, we have introduced the establishment and solution of our model. The key idea is to first identify a hyperplane of classification of data with missing features by incomplete time series. Then, the hyperplane is used to calculate the estimation values in predicting and imputing samples. Figure3 provides the algorithms of our model for prediction and imputation.The algorithms of our model for prediction and imputation.
(a)
Incomplete time series prediction algorithm(b)
Incomplete time series imputation algorithm


## 4.1. Analytical Solution

Suppose a test samplex′={x1′,x2′,…,xd′,xd+1′}, where xd+1′ is the value to be estimated. In this paper we use the kernel function K′(xi,xj)=(〈xi,xj〉F+1)2. Replacing the kernel of (3.5), we obtain
(4.1)∑i=1nαiyisi(〈x′,xi〉𝔽+1)2+b=0.The simplification of (4.1) is(4.2)∑i=1nαiyisixi,d+12·xd+1′2+2∑i=1nαiyisi(∑j=1dxi,j·xj′+1)xi,d+1·xd+1′+∑i=1nαiyisi(∑j=1dxi,j·xj′+1)2+b=0,
where the product operator  “·”  is taken only over features that are valid for both xi and x′. Equation (4.2) is a quadratic equation of xd+1′, and can be solved easily.


## 4.2. Numerical Solution

Sometimes, analytical solution is meaningless or nonexistent. We need to get numerical solution of our model by iterative algorithms [19, 20]. Still take x′ as an example, supposing we use Newton method, the object function of our model can be represented as(4.3)F(xd+1′)=∑i=1nαiyisiK(x′,xi)+b.The iterative equation ofxd+1′ can be expressed as
(4.4)xd+1′(i+1)=xd+1′(i)-F(xd+1′(i))F(xd+1′(i)).Therefore, the estimation values are calculated by our model effectively. Numerical solution is more complicated, but applicable in every case.In conclusion, we have introduced the establishment and solution of our model. The key idea is to first identify a hyperplane of classification of data with missing features by incomplete time series. Then, the hyperplane is used to calculate the estimation values in predicting and imputing samples. Figure3 provides the algorithms of our model for prediction and imputation.The algorithms of our model for prediction and imputation.
(a)
Incomplete time series prediction algorithm(b)
Incomplete time series imputation algorithm


## 5. Experiments

To check the validity of our model, four experiments are conducted in this section. Firstly, the prediction performance of our model is evaluated in test A. Given that conventional imputation methods usually perform distinctly when incomplete time series are missing discretely and continuously, we examine the imputation performance of our model in two missing modes in test B and test C, respectively. The performance of our model is compared with that of RGGB and other two classical imputation methods: Mean and KNN. Finally, we verify the prediction performance of incomplete time series imputed by different models in test D.The time series used in the experiments are Mackey-Glass time series and Henon time series. Mackey-Glass time series is generated by the chaotic equation(5.1)dxdt=-b*x(t)+a*x(t-τ)1+x10(t-τ),
where parameter τ is set to 17, a=0.2, and b=0.1. The interval of t is 5. Henon time series is generated by the nonlinear equation(5.2)x(n+1)=1-1.4x(n)2+0.3x(n).By contrast, Henon time series has a higher volatility. The dimension of the sample setd=15. Parameters of our model are ε=0.001 and C=100. The value of K in KNN is set to 5.MSE (Mean Squared Error) and MAE (Mean Absolute Error MAE) are used to evaluate the performance of the experiments. All the results are obtained by repeating the algorithms 10 times.


### 5.1. Prediction of Incomplete Time Series

In this test, continuous 115 data of Mackey-Glass time series with the missing level from 3% to 18% are used to construct the initial sample set,and the next 65 data are for testing the prediction performance of our model. The prediction results are shown in Figure4.Figure 4
Prediction results of our model in Mackey-Glass time series.From Figure4 we can see that, with the increase of the missing level, larger deviations of the prediction results occur inevitably due to the decrease of the number of training samples. However, in practice, we can use an acceptable limit of error as the basis for judgment. For example, set the acceptable limit of error MAEl=0.1, which equals to the minimum scale of Mackey-Glass time series. Thus our model performs well even when the missing level reaches 17%. Figure 5 shows an example of prediction performance of our model in Mackey-Glass time series with the missing level of 3% and 17%. From Figure 5, our model predicts the future time series roughly when 17% of the history data are absent. Compared with the performance of missing level at 3%, only some details are missing. Similar results are obtained in Henon time series, which are shown in Figures 6 and 7.Figure 5
Prediction performance of our model in Mackey-Glass time series.Figure 6
Prediction results of our model in Henon time series.Figure 7
Prediction performance of our model in Henon time series.


### 5.2. Imputation of Incomplete Time Series with Discrete Missing Data

The continuous 115 data of Mackey-Glass time series and Henon time series with discrete missing data are used as the experimental data in this test. The imputation results of different models are shown in Tables1 and 2.Table 1
Imputation results of Mackey-Glass time series with discrete missing data.
Missing levelOurMeanKNNRGGBMSEMAEMSEMAEMSEMAEMSEMAE4–6%0.07160.06260.06280.05450.07280.06020.06920.05947–9%0.07830.07440.08090.06570.08230.06120.08400.077110–12%0.09120.08650.09690.08330.07950.06690.09790.085713–15%0.10640.09330.10100.08360.10860.10500.12420.1098Table 2
Imputation results of Henon time series with discrete missing data.
Missing levelOurMeanKNNRGGBMSEMAEMSEMAEMSEMAEMSEMAE4–6%0.23850.19990.83520.67910.46240.46020.66830.55927–9%0.42230.31200.99540.81480.67070.55340.78880.615610–12%0.64610.44221.39511.26380.67460.61930.83210.637813–15%0.67870.52611.46551.31140.78680.64671.20350.7639From Tables1 and 2 we can see that, the imputation performance of our model is similar to that of KNN and RGGB in Mackey-Glass time series. However, in Henon time series our model outperforms other three methods at every missing level. An example of imputation performance of our model over Henon time series with the missing level of 10% is shown in Figure 8.Figure 8
Imputation performance of our model in Henon time series with the missing level of 10%.Figure8 shows that our model imputes most of the missing data in Henon time series effectively. Compared with other methods, the performance of our model is not sensitive to the fluctuation of time series.


### 5.3. Imputation of Incomplete Time Series with Continuous Missing Data

We evaluate the performance of different imputation methods by incomplete time series with continuous missing data in the same way. Set the maximum length of continuous missing datal=5. The imputation results are shown in Tables 3 and 4.Table 3
Imputation results of Mackey-Glass time series with continuous missing data.
Missing levelOurMeanKNNRGGBMSEMAEMSEMAEMSEMAEMSEMAE4–6%0.07410.06040.10440.09410.08460.06760.12960.10137–9%0.08310.06910.17180.13740.12990.10810.15310.132010–12%0.08320.07480.17910.15080.10910.08530.20200.155313–15%0.10820.08140.19510.15260.13470.11190.22200.1843Table 4
Imputation results of Henon time series with continuous missing data.
Missing levelOurMeanKNNRGGBMSEMAEMSEMAEMSEMAEMSEMAE4–6%0.24090.19660.96330.83160.54490.42470.72940.52167–9%0.39450.33911.02690.89570.54500.50220.82750.577710–12%0.54720.49041.13430.98020.67770.52971.14620.709013–15%0.83400.61901.39371.31010.78950.67111.21370.7657Tables3 and 4 indicate that our model outperforms other three methods in both Mackey-Glass time series and Henon time series when the data are missing continuously. Compared with Tables 1 and 2, no significant difference is observed between the two missing modes in our model, while other methods perform better in the former. Figure 9 shows an example of imputation performance of our model over Mackey-Glass time series with the missing level of 10%.Figure 9
Imputation performance of our model in Mackey-Glass time series with the missing level of 10%.There are three sets of continuous missing data in Figure9. Our method imputes the first two effectively. Based on the above observation, we conclude that our method performs better than other traditional technologies of imputation.


### 5.4. Prediction after Imputation

The prediction performance of incomplete time series imputed by different models in test B and test C is evaluated in this test. We also use the next 65 data to test the prediction performance. The error-tolerant BP algorithm is used to build the predicting model. The prediction results are shown in Figures10 and 11.Figure 10
Prediction results in Mackey-Glass time series imputed by different methods.Figure 11
Prediction results in Henon time series imputed by different methodsFrom Figures10 and 11 we can see that, the prediction performance in Mackey-Glass time series and Henon time series imputed by our model are both superior to that of imputed by other imputation algorithms.


## 5.1. Prediction of Incomplete Time Series

In this test, continuous 115 data of Mackey-Glass time series with the missing level from 3% to 18% are used to construct the initial sample set,and the next 65 data are for testing the prediction performance of our model. The prediction results are shown in Figure4.Figure 4
Prediction results of our model in Mackey-Glass time series.From Figure4 we can see that, with the increase of the missing level, larger deviations of the prediction results occur inevitably due to the decrease of the number of training samples. However, in practice, we can use an acceptable limit of error as the basis for judgment. For example, set the acceptable limit of error MAEl=0.1, which equals to the minimum scale of Mackey-Glass time series. Thus our model performs well even when the missing level reaches 17%. Figure 5 shows an example of prediction performance of our model in Mackey-Glass time series with the missing level of 3% and 17%. From Figure 5, our model predicts the future time series roughly when 17% of the history data are absent. Compared with the performance of missing level at 3%, only some details are missing. Similar results are obtained in Henon time series, which are shown in Figures 6 and 7.Figure 5
Prediction performance of our model in Mackey-Glass time series.Figure 6
Prediction results of our model in Henon time series.Figure 7
Prediction performance of our model in Henon time series.


## 5.2. Imputation of Incomplete Time Series with Discrete Missing Data

The continuous 115 data of Mackey-Glass time series and Henon time series with discrete missing data are used as the experimental data in this test. The imputation results of different models are shown in Tables1 and 2.Table 1
Imputation results of Mackey-Glass time series with discrete missing data.
Missing levelOurMeanKNNRGGBMSEMAEMSEMAEMSEMAEMSEMAE4–6%0.07160.06260.06280.05450.07280.06020.06920.05947–9%0.07830.07440.08090.06570.08230.06120.08400.077110–12%0.09120.08650.09690.08330.07950.06690.09790.085713–15%0.10640.09330.10100.08360.10860.10500.12420.1098Table 2
Imputation results of Henon time series with discrete missing data.
Missing levelOurMeanKNNRGGBMSEMAEMSEMAEMSEMAEMSEMAE4–6%0.23850.19990.83520.67910.46240.46020.66830.55927–9%0.42230.31200.99540.81480.67070.55340.78880.615610–12%0.64610.44221.39511.26380.67460.61930.83210.637813–15%0.67870.52611.46551.31140.78680.64671.20350.7639From Tables1 and 2 we can see that, the imputation performance of our model is similar to that of KNN and RGGB in Mackey-Glass time series. However, in Henon time series our model outperforms other three methods at every missing level. An example of imputation performance of our model over Henon time series with the missing level of 10% is shown in Figure 8.Figure 8
Imputation performance of our model in Henon time series with the missing level of 10%.Figure8 shows that our model imputes most of the missing data in Henon time series effectively. Compared with other methods, the performance of our model is not sensitive to the fluctuation of time series.


## 5.3. Imputation of Incomplete Time Series with Continuous Missing Data

We evaluate the performance of different imputation methods by incomplete time series with continuous missing data in the same way. Set the maximum length of continuous missing datal=5. The imputation results are shown in Tables 3 and 4.Table 3
Imputation results of Mackey-Glass time series with continuous missing data.
Missing levelOurMeanKNNRGGBMSEMAEMSEMAEMSEMAEMSEMAE4–6%0.07410.06040.10440.09410.08460.06760.12960.10137–9%0.08310.06910.17180.13740.12990.10810.15310.132010–12%0.08320.07480.17910.15080.10910.08530.20200.155313–15%0.10820.08140.19510.15260.13470.11190.22200.1843Table 4
Imputation results of Henon time series with continuous missing data.
Missing levelOurMeanKNNRGGBMSEMAEMSEMAEMSEMAEMSEMAE4–6%0.24090.19660.96330.83160.54490.42470.72940.52167–9%0.39450.33911.02690.89570.54500.50220.82750.577710–12%0.54720.49041.13430.98020.67770.52971.14620.709013–15%0.83400.61901.39371.31010.78950.67111.21370.7657Tables3 and 4 indicate that our model outperforms other three methods in both Mackey-Glass time series and Henon time series when the data are missing continuously. Compared with Tables 1 and 2, no significant difference is observed between the two missing modes in our model, while other methods perform better in the former. Figure 9 shows an example of imputation performance of our model over Mackey-Glass time series with the missing level of 10%.Figure 9
Imputation performance of our model in Mackey-Glass time series with the missing level of 10%.There are three sets of continuous missing data in Figure9. Our method imputes the first two effectively. Based on the above observation, we conclude that our method performs better than other traditional technologies of imputation.


## 5.4. Prediction after Imputation

The prediction performance of incomplete time series imputed by different models in test B and test C is evaluated in this test. We also use the next 65 data to test the prediction performance. The error-tolerant BP algorithm is used to build the predicting model. The prediction results are shown in Figures10 and 11.Figure 10
Prediction results in Mackey-Glass time series imputed by different methods.Figure 11
Prediction results in Henon time series imputed by different methodsFrom Figures10 and 11 we can see that, the prediction performance in Mackey-Glass time series and Henon time series imputed by our model are both superior to that of imputed by other imputation algorithms.


## 6. Conclusions

Learning and prediction of incomplete data are still pervasive problems, although extensive studies have been conducted to improve the efficiency of data acquisition and transmission [21, 22]. We have proposed a new prediction model for incomplete time series. Experiments conducted in this paper confirm that our model can be successfully applied to prediction of incomplete time series with a missing level below than that of acceptable error limit. In addition, the imputation performance of our model is superior to that of other imputation methods, and insensitive to the fluctuation of time series. Future work may focus on applications of the model in some relevant fields [23, 24] and real-life problems.



---

*Source: 513810-2010-06-29.xml*