{'fraction_non_alphanumeric': 0.042336018980772085, 'fraction_numerical': 0.015397162770006426, 'mean_word_length': 4.629243183082916, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Time Series Data Cleaning: From Anomaly Detection to Anomaly Repairing (Technical Report)

Errors are prevalent in time series data, such as GPS trajectories or sensor readings. Existing methods focus more on anomaly detection but not on repairing the detected anomalies. By simply filtering out the dirty data via anomaly detection, applications could still be unreliable over the incomplete time series. Instead of simply discarding anomalies, we propose to (iteratively) repair them in time series data, by creatively bonding the beauty of temporal nature in anomaly detection with the widely considered minimum change principle in data repairing. Our major contributions include: (1) a novel framework of iterative minimum repairing (IMR) over time series data, (2) explicit analysis on convergence of the proposed iterative minimum repairing, and (3) efficient estimation of parameters in each iteration. Remarkably, with incremental computation, we reduce the complexity of parameter estimation from O(n) to O(1). Experiments on real datasets demonstrate the superiority of our proposal compared to the state-of-the-art approaches. In particular, we show that (the proposed) repairing indeed improves the time series classification application.


INTRODUCTION
Time series data are often found with dirty or imprecise values, such as GPS trajectories, sensor reading sequences [15], or even stock prices [16]. For example, the price of SALVEPAR (SY) is misused as the price of SYBASE (SY), both of which share the same notation (SY) in some sources. It is different from the interesting anomaly that actually happens in real life, e.g., the temperatures sudden change from 20C to 10C in one day when cold air rushes in. To distinguish such cases, we propose to employ some labeled

Motivation on Anomaly Repairing
Applications, such as pattern mining [17] or classification [31], built upon the dirty time series data are obviously not reliable. Anomaly detection over time series is often applied to filter out the dirty data (see [11] for a comprehensive and structured overview of anomaly detection techniques). That is, the detected anomaly data points are simply discarded as useless noises. Unfortunately, with a large number of consecutive data points eliminated, the applications could be barely performed over the rather incomplete time series.
Recent study [25] shows that repairing dirty values could improve clustering over spatial data. For time series data, we argue that repairing the anomaly can also improve the applications such as time series classification [31]. A repair close to the truth helps greatly the applications.

Potential Methods for Repairing
A straightforward idea is to directly interpret the predication values in anomaly detection, e.g., by AR [3,14,32] or ARX [3,19], as repairs (see details in Section 2). A data point is considered as anomaly if its (truth) predication significantly differs from (noisy) observation. Unfortunately, noisy/erroneous data are often close to the truth in practice, under the intuition that human or systems always try to minimize their mistakes, e.g., misspellings (John Smith vs. Jhon Smith), typos (555-8145 vs. 555-8195) as illustrated in [1], rounding off (76,821,000 vs. 76M) or unit error (76M vs. 76B) as shown in [16]. Owing to such disagreement, the repairing performance of directly applying anomaly detection techniques is poor, as illustrated in both Example 1 below and experiments in Section 6.
On the other hand, constraint-based repairing SCREEN [26], strictly following the minimum change principle in data repairing [1], heavily relies on a proper constraint of speeds on value changes. The repairing is performed based on two consecutive points, i.e., considering only one historical point, and thus does not sense the temporal nature of errors. As shown in the following Example 1, the speed constraintbased SCREEN is effective in repairing spike errors, but can hardly handle a sequence of consecutive dirty points. In short, the anomaly detection method does not expect the minimized mistakes in practice, whereas the constraintbased repairing is not effective in addressing the temporal nature of errors.

Intuition of Our Proposal
Since completely automatic data repairing might not work well in repairing time series data (such as SCREEN [26] observed in our experiments in Figure 10), enlightened by the idea of utilizing master data (a single repository of highquality data) in data repairing [9], we employ some labeled truth of dirty observations to advance the repair. The truth can be obtained either by manual labeling or automatically by more reliable sources. For instance, accurate locations are manually marked in the map by user check-in activities (and utilized to repair the imprecise GPS readings). Moreover, periodical automatic labeling may take place in certain scenarios, e.g., precise equipments report accurate air quality data (as labeled values) in a relatively long sensing period, while crowd and participatory sensing generates unreliable observations in a constant manner [34].
Being aware of both the error nature in anomaly detection and the minimum change principle in data repairing, we propose iterative minimum repairing (IMR). The philosophy behind the proposed iterative minimum repairing is that the high confidence repairs in the former iterations could help the latter repairing. Specifically, IMR minimally changes one point a time to obtain the most confident repair only, referring to the minimum change principle in data repairing that human or systems always try to minimize their mistakes. The high confidence repairs, together with the labeled truth of error points, are utilized to learn and enhance the temporal nature of errors in anomaly detection, and thus generate more accurate repair candidates in the latter iterations. Example 1. Figure 1 presents an example segment of sensor readings, denoted by black line. Suppose that sensor errors occur in the period from time point 370 to 385, where the observations are shifted from the truth, e.g., owing to granularity mismatch or unit error. To repair the errors, the truth of several observations are labeled, including time points {370, 371, 372, 379, 387}.
Existing speed constraint-based cleaning (SCREEN) [26] could not effectively repair such continuous errors in a period (which is indeed also observed in Example 1 in [26]). The reason is that speed constraints, restricting the amount of value changing relative to time difference, can detect sharp deviations such as from time point 369 to 370, but not continuous errors, e.g., in 383 and 384. The exponentially weighted moving average (EWMA) [13] algorithm also hard to find a proper way to clean the trace. These two methods have similar repair trace.
By considering the predication values in anomaly detection as repairs (see more details in Section 2), the result of ARX based repairing is also reported. ARX, considering the errors between truth and observations, shows better repair results than EWMA and SCREEN methods.
Finally, our proposed IMR approach, with both error predication and minimum change considerations, obtains repairs closest to the truth.
The iterative minimum repairing leads to new challenges: (1) whether the repairing process converges; and (2) how to efficiently/incrementally update the parameter of the temporal model over the repaired data after each iteration. Both issues in anomaly repairing are not considered in the anomaly detection studies.
Contributions. Our major contributions in this paper are summarized as follows.
(1) We formalize the anomaly repairing problem, given a time series with some points having labeled truth, in Section 2. The adaption of existing anomaly detection techniques (such as AR and ARX) is introduced for anomaly repairing.
(2) We devise an iterative minimum-change-aware repairing algorithm IMR, in Section 3. Remarkably, we illustrate that the ARX-based approach (in Section 2) is indeed a special case of IMR with static parameter (Proposition 2).
(3) We study the convergence of IMR in various scenarios, in Section 4. In particular, the convergence is explicitly analyzed for the special case of IMR(1) with order p = 1, which is sufficient to achieve high repair accuracy in practice (as shown in the experiments in Section 6). We prove that under certain inputs, the converged repair result could be directly calculated without iterative computing (Proposition 8).
(4) We design efficient pruning and incremental computation for parameter estimation in each repair iteration, in Section 5. Rather than performing parameter estimation over all the n points, matrices for parameter estimation could be pruned by simply removing rows with value 0 (Proposition 9). It is also remarkable that the incremental computation among different repair iterations (Proposition 10) could further reduce the complexity of parameter estimation from O(n) to O(1).
(5) Experiments on real datasets with both real and synthetic errors, in Section 6, demonstrate that our IMR method shows significantly better repair performance than the stateof-the-art approaches, including the aforesaid anomaly detection and constraint-based repairing. Table 1 lists the notations frequently used in this paper.

PRELIMINARIES
This section first introduces the problem of anomaly repairing. We then adapt the existing anomaly detection models for anomaly repairing, i.e., AR without considering labeled data and ARX supporting labeled data.
The major issues of this simple adaption are: (1) Applying predications with significant difference to the observation as repairs contradicts to the minimum change principle in data Let y denote the labeled/repaired sequence of x . Each yi is either the labeled truth or the repaired value of xi.
Given a time series x and a partially labeled subset y of x , the repairing problem is to determine the repairs yi of xi that are not labeled in y.
Example 2 (Observation x , partially labeled y, and fully repaired y). Consider x = {6, 10, 9.6, 8.3, 7.7, 5.4, 5.6, 5.9, 6.3, 6.8, 7.5, 8.5} with twelve data points of observations in Figure 2, where shift (up) errors occur on four points x2, . . . , x5. Suppose that five points are labeled with truth, i.e., the partially labeled y. By repairing (using the methods presented below), we propose to obtain a fully repaired y, e.g., y = {6, 5.6, 5.4, 5.2, 5.4, 5.4, 5.6, 5.9, 6.3, 6.8, 7.5, 8.5} as shown in Figure 2. In the repaired y, x4 and x5 are changed from 8.3 and 7.7 to 5.2 and 5.39, respectively. The labeled y2 and y3 will not be modified in the repair result. Figure 2 also presents another repair y ′ by the approach of connecting the dots with the labeled values, i.e., linear interpolation [30]. As shown in Figure 2 and also indicated in [26], the major issue of this (smoothing) approach is the serious damage of almost all the (unlabeled) data points, such as y ′ 7 . . . y ′ 11 , which are originally correct and should not be modified. In contrast, our proposed method repairs y4 and y5 while leaving y7 . . . y11 unchanged.

AR Model
Intuitively, anomaly detection techniques could be adapted to anomaly repairing. For instance, we consider the AR (autoregression) model [14,32] as follows: where x ′ t is the prediction of xt, p is the order, φi is the parameter of the model, c is a constant defined by c = µ(1 − p i=1 φi), µ is mean value of the process and ǫt is white noise (usually Gaussian white noise [3], a normal random variable generated according to the Gaussian distribution with mean µ = 0 and variance σ 2 ; in other words, c = 0). If x ′ t significantly differs from the original observation xt, having |x ′ t − xt| > τ where τ is a predefined threshold, this predication is accepted xt = x ′ t , a.k.a. a repair. The intuition behind is that a farther distance indicates the higher probability of being an outlier. The threshold τ can be decided by observing the statistical distribution of distances between x ′ t and xt , using the prediction interval [14,12]. The AR-based repairing procedure is thus: (1) replace xt by yt if it is labeled, (2) learn parameter φ of AR(p) from x , and (3) fill all unlabeled yt by AR(p) over x , having Example 3 (Example 2 continued). Consider again x = {6, 10, 9.6, 8.3, 7.7, 5.4, 5.6, 5.9, 6.3, 6.8, 7.5, 8.5} in Figure 2. For simplicity, we use AR(1) with order p = 1 and c = 0, i.e., x ′ t = φ1xt−1. By ordinary least square [20], we estimate the parameter φ from x , having φ1 = 1.022. Let τ = 0.

ARX Model
In order to utilize the labeled y, we consider the ARX model (autoregressive model with exogenous inputs) [19] where y ′ t is the possible repair of xt, and others are the same to the aforesaid AR model. As shown in Equation 3, not only the preceding observations xt−i will affect the determination of y ′ t , but also the previously labeled/repaired yt−i. The ARX-based repairing procedure is thus: (1) learn parameter φ of ARX(p) from x and partially labeled y, and (2) fill all unlabeled yt by ARX(p), similar to Equation 2 by replacing x ′ t with y ′ t .
We consider ARX model since it can capture the difference between the observed errors and labeled truths, while other methods such as AR and SCREEN ignore (cannot utilize) such differences. By modeling such differences between errors and truths rather than original values, both ARX and our proposed IMR may not deal with Spike errors (i.e., with # consecutive errors = 1 in Figure 10) as good as SCREEN [26]. Nevertheless, with iterative repairing, IMR always shows significantly better results in addressing a large number of consecutive errors (see Figure 10 as well). ARX cannot address well such consecutive errors either, since it applies only significant changes which is contradict to the minimum change principle in data repairing as discussed in Section 1.2 in the Introduction.

REPAIR ALGORITHM
Unlike the existing anomaly detection model that may over-change the data via one-pass repairing (as discussed in the introduction, illustrated in Figure 2, and observed in experiments in Section 6), we propose to progressively repair the data, being aware of both the error nature in anomaly detection and the minimum change principle in data repairing, so that the high confidence repairs in the former iterations could help the repairing in the latter steps.

Iterative Repairing
Let y (k) denote the sequence y in the k-th iteration, where y (0) is the partially labeled time series in the input. Since y (0) is incomplete (partially labeled), to initialize, we assign y is not labeled. Recall that the labeled values should not be repaired, i.e., y Algorithm 1 presents the iterative minimum repairing procedure, IMR(p), whose inputs are the observation time series x and partially labeled y (0) . It outputs y (k) with all the labeled y (0) t unchanged and unlabeled y (0) t repaired. The major steps include: (S1) Parameter estimation, in Line 2, learns the parameter of ARX(p) in the k-th iteration, denoted by φ (k) , from x and the current y (k) .
(S3) Repair evaluation, in Line 4, determines one of the repairs to accept, y t , referring to the minimum change principle in data repairing [1].
As shown in Line 5, the procedure repeats, until the repair converges, e.g., having where τ a threshold of convergence, or a maximum number of iterations is reached. Setting max-num-iterations is a remedy to avoid waiting for convergence in practice (see Section 6.1.4 for discussion and evaluation).

Algorithm 1: IMR(p)
Input: time series x and partially labeled y (0) Output: y (k) with all the labeled y (0) i unchanged and unlabeled y

Parameter Estimation
The parameter estimation step S1 (in Line 2 in Algorithm 1) estimates the parameter φ (k) for ARX(p), given x , y (k) . Existing methods such as Ordinary Least Square [20] or Yule-Walker Equations [7] can be directly employed. For instance, by Ordinary Least Square, we have where Example 6 (Parameter estimation on y (0) , Example 5 continued).
Owing to the iterative repairing, online incremental parameter estimation is necessary, which is not studied in the previous studies (see our approach in Section 5).

Candidate Generation
The repair candidate generation step S2 (in Line 3 in Algorithm 1) employs ARX(p) to infer the candidate repair t | > τ need to be considered referring to the convergence condition in Equation 4.

Repair Evaluation
The repair evaluation step S3 (in Line 4 in Algorithm 1) selects one repair to accept, i.e., assigning y (k+1) t =ŷ (k) t the aforesaid generated repair candidate. Following the minimum change principle in data repairing [1], the repair that minimally differs from its original input is preferred with higher confidence. The repaired result in each iteration is: Remarkably, only one data point with the minimum change (most confident) is repaired in each iteration, which is more efficient than the NP-hard problem of minimizing the overall changes w.r.t. integrity constraints [1].
Note that the minimum change principle [1] in data repairing is based on the intuition that human or systems always try to minimize their mistakes. However, it is not guaranteed that the minimum change repair always corresponds to the true value. Therefore, similar to other minimum change-based data repairing studies [1,8], the accuracy of the final results is unlikely to have theoretical guarantees, since there is no constraint on how far the errors may diverge from the truth. For this reason, we can only evaluate the correctness of the proposed repair by comparing to the ground truth in experiments, similar to other data repairing studies [1,8] as well. Nevertheless, we can show that the efficient pruning and incremental computation are safe (Propositions 9 and 10), i.e., the accuracy of the final results with efficient computing is theoretically guaranteed to be the same as the results of original IMR without pruning and incremental computation.

CONVERGENCE ANALYSIS
In this section, we analyze the convergence of iterative repairing, i.e., lim k→+∞ which is essential to the termination of Algorithm 1. While the general convergence problem is still open, we study the convergence of the proposed method in certain special cases in this section for two reasons: (1) we illustrate that the ARXbased approach is indeed a special case of the proposed IMR with static parameter (Proposition 2) in Section 4.1; (2) we identify another special case with convergence guarantee in Section 4.2, which enables online repairing over streaming data without iteration (also see Sections 4.2.2 and 6.2.2 for more details and experiments).

Static Parameter
We study this special case in order to illustrate the relationship between our proposed IMR and the existing ARX. Let us first analyze the convergence of IMR (Proposition 1) and then illustrate their equivalence in certain case (Proposition 2).
Rather than dynamically updating the parameter φ (k) in each iteration, in Line 2 in Algorithm 1, a special case is to specify a static parameter, φ (k) = φ (0) , for all the iterations. Proposition 1. With a static parameter φ (k) = φ, ∀k, the repair result converges, i.e., Proof. Let t be the point repaired in iteration k. We show that y converges (will not change in the following iterations k + i), if the p preceding points of t are converged (no longer change). The reason is thatŷt (k+i) = y (k+1) t , referring to Equation 6 of candidate generation with static parameter φ. That is, no repair candidate will be generated.
If one of the p preceding points of t changes (not converged), say t ′ , the aforesaid derivation applies similarly to t ′ . By recursively applying the derivations, we can finally find a point t * whose p preceding points are either labeled or converged, i.e., a new point t * converges. Such t * always exists, i.e., p + 1, given that the first p points in the sequence will not be modified by the repairing (referring to the repair candidate generation in Equation 6) and thus already converged under the static parameter φ.
Finally, all the data points gradually converge.

Special Case of IMR(1)
We show in the following that for p = 1, the ARX(p)based repairing in Section 2.3 is a special case of our proposed IMR(p) with static parameter φ (0) . This equivalence demonstrates the rationale of our proposal.
Proof. Suppose that the first point is labeled. Consider data point 2. Referring to Proposition 1, y By recursively obtaining the converged yt which is not labeled, it is exactly the procedure of ARX(1)-based repairing.

Converged Parameter
We now consider the dynamically updated parameter φ (k) in each iteration, in Line 2 in Algorithm 1. As shown in the following Proposition 3, if the dynamic parameter converges, the repair converges as well. This converged parameter case is interesting, since the corresponding converged repair result could be directly calculated without iterative computing in certain cases as illustrated below. Proof. When the parameter φ converges, it becomes static. Similar proof for Proposition 1 applies.

Special Case of IMR(1)
Again, we consider the special case of IMR(1) with order p = 1. To show how the repair results could be directly computed without iterations, we first illustrate that any y where 0 < k1 < · · · < ks−1 < ks < k denote iteration numbers, y  Suppose that y (k) t is unchanged since iteration ks. We have Similar provenance applies to y (ks) Combining these s + 1 derivations, the conclusion is proved.

IMR(1) with One Labeled Segment
We consider the case that only one segment with length ℓ is labeled at the beginning of y (0) , i.e., y In this special case, the converged parameter and repair result can be directly calculated without iterating, and most importantly it enables efficient online computation, by interpreting all the historical data as one segment labeled (see Section 6.2.2 for details and evaluation). Remarkably, no threshold needs to be set in this case.
The idea is: (1) We first show in Lemma 6 that under certain inputs, the estimated parameter in each iteration is indeed bounded; (2) Proposition 7 then illustrates that the bounded parameter leads to converged parameter; (3) Finally, analogous to Proposition 5, given the converged parameter, we directly calculate the converged repair without iterative computing in Proposition 8.
Lemma 6. For IMR(1) with first ℓ data points labeled in Proof. According to Equation 5, we have Referring to the given condition, it follows We prove |φ (k) 1 | < 1, 1 ≤ k ≤ n − ℓ in three cases.
The following conclusion illustrates that with a bounded parameter in each iteration, the parameter converges.
Suppose that point t is selected to repair in the k-th iteration, having where t = arg min i∈ [1,n] |ẑ (k) i | referring to the minimum change.
Since one and only one point will be changed in each iteration, we have z For the (k + 1)-th iteration, any point i haŝ That is, (t + 1) = arg min i∈ [1,n] |ẑ (k+1) i |, will be the minimum repair in the (k + 1)-th iteration.
Similar repairing applies in m = n − ℓ iterations, having z ℓ , according to Lemma 4. For the estimation ofẑ That is, point n will always be repaired in the following iterations.
According to Equation 5, we have It is proved that the parameter converges.
It is worth noting that the condition |φ (k) 1 | < 1 in Proposition 7 for the parameter to converge could be commonly observed in real data. First, referring to [5], most time series in practice are stationary, which is guaranteed to have |φ (k) 1 | < 1 for p = 1. Moreover, for non-stationary cases, a typical processing way is to transform it to stationary via differencing [5].
where the converge parameter can be directly calculated by Proof. It is a special case of Proposition 5 with m = 1. Similar to the proof of Proposition 5, we have It is not surprising that the converged parameter φ1 in Equation 11 in Proposition 8 is exactly the solution of Equation 9 in Proposition 5 with m = 1 for the special case of one labeled segment.

EFFICIENT PARAMETER ESTIMATION
Among the three major steps in Algorithm 1, while the repair candidate generation and evaluation (in Sections 3.3 and 3.4) are inevitable for the minimum repair, we show in this section that the costly parameter φ (k) estimation (in Section 3.2) is optimizable in our iterative repairing scenario. First, we identify that the matrices Z (k) , V (k) for parameter estimation could be pruned by simply removing rows with value 0, in Section 5.1. Moreover, incremental computation could be designed such that the complexity of parameter estimation is reduced from O(n) to O(1), in Section 5.2.

Matrix Pruning
Intuition. Recall that when estimating the parameter φ (k) in Equation 5, we need to consider two large matrices Z (k) and V (k) with sizes (n − p) × p and (n − p) × 1, respectively. The value y (k) i − xi in Z (k) and V (k) denotes the difference between the labeled/repaired value y (k) i and the input value xi of point i. In practice, the labeled data is often limited, while the repaired data should not be significantly changed referring to the minimum change principle of repairing. That is, most values in Z (k) and V (k) equal to 0. We show (in Proposition 9 below) that the sparse matrices could be pruned by removing rows with value 0.
Let z − xi for simplicity. We rewrite V (k) , Z (k) in Equation 5 for parameter estimation, The following conclusion states that the same parameter φ (k) could still be computed by Equation 5, after removing the rows in Z (k) , whose values equal to 0, and the corresponding rows in V (k) . V (k) , respectively, which still compute that the same φ (k) .
Proof. We rewrite Equation 5 as φ (k) = (A (k) ) −1 B (k) , where A (k) = (Z (k) ) ′ Z (k) and B (k) = (Z (k) ) ′ V (k) as illustrated in Equations 13 and 14, respectively. To prove the same parameter φ (k) , we show that all the values in A (k) and B (k) are unchanged after removing the r-th row with value 0.
GPS data with real errors. In the GPS dataset, real errors are naturally embedded and the corresponding ground truths are manually labeled. It collects GPS readings by a person carrying a smartphone and walking around at campus. Since we know exactly the path of walking, a number of 186 dirty points out of 742 points in trajectory are manually identified. True locations of dirty points are also manually labeled, as ground truth. (See major results in Section 6.  Figure 9). Such "shifting" errors are very common in practice, for example the sensor is stuck for a short while, or unit error in collection in a period. (See major results in Section 6.2.) Criteria. RMS error [15] is employed to evaluate the repair. Let x truth be the ground truth of clean sequence, x dirty be the observation sequence with faults embedded, and x repair be the repaired sequence. The RMS error [15] is given by: The measure evaluates the distance between the ground truth and its repair result. Low RMS error is preferred.

Experiments on Real Errors
The experiments on real errors over GPS data consider various algorithm settings, including (1) order p, (2) convergence threshold τ , (3) max-num-iterations, and (4) labeling rate. Similar results are also observed in ILD and omitted. Figure 4 illustrates an example part (in latitude, after transformed) of the GPS dataset, including the collected observations with errors, the labeled truth, and the repair results by different methods. Owing to various influences such as buildings, GPS readings may deviate from the truth. For instance, the data between time points 400 and 500 are collected from a place near a high building, where significant errors are observed. As shown, the proposed IMR shows a repair closest to the truth, compared to other methods. Figure 5 presents the results on varying order p, for AR(p), ARX(p) and IMR(p). First, as shown in Figure 5(a), ARbased method shows better performance with the increase of order p, where more historical values take effect in the predication of each value. An excessively large p, however, does not show further improvement, since this simple model may not be able to capture the complicated semantics in a large It is not surprising that the iterative IMR needs higher time costs in Figure 5(b) than other existing methods with only one pass through the data. In addition to the original IMR in Algorithm 1, we also present the results of IMR with matrix pruning (IMR-MP) in Section 5.1 and incremental computation (IMR-IC) in Algorithm 2 for efficient parameter estimation. IMR, IMR-MP and IMR-IC show exactly the same accuracy results in Figure 5(a). Both efficient estimation methods improve the time costs in Figure 5(b). In particular, IMR-IC for incremental parameter estimation with constant time significantly reduces time costs.

Varying Order p
In summary, as illustrated in Figures 5 and 11 over the GPS and ILD datasets, respectively, our proposed IMR has no clear preference of order p in repairing accuracy, while larger order p leads to higher time cost. Figure 6 reports the results by varying the threshold τ (with p = 3). By setting a small τ , IMR needs more iterations to converge. The corresponding time costs in Figure  6(b) are higher. Better repairing performance is achieved by IMR with a small τ , as shown in Figure 6(a). However, by further reducing the threshold τ , e.g., from 0.1 to 0.01, the repair accuracy could hardly be further improved, while the corresponding iterations and time costs significantly increase. On the other hand, by increasing the threshold τ , the time costs reduce. Indeed, the threshold τ provides a trade-off between repair accuracy and time costs for IMR.

Varying Convergence Threshold τ
In summary, a lower threshold indeed leads to better results (lower RMS error) and needs more iterations (higher

Specifying Maximum Number of Iterations
In Section 4, we analyze several special cases, where repairing is guaranteed to converge in theory under some conditions. For general cases where such conditions are not met, (although all the experiments converge in Section 6 under various settings with/without theoretical convergence guarantee), one may specify the maximum number of iterations, as a remedy in practice to avoid waiting for convergence. That is, Algorithm 1 terminates when the iteration number reaches max-num-iterations, even if the convergence condition in Line 5 is not met.
Figures 7 evaluates various settings of maximum number of iterations (average time costs are reported by repeating each test 10 times).As illustrated, a moderately large number of iterations already achieve good repair results, i.e., close to the (right-most) converged results. Figure 8 illustrates the results on various labeling rates. A labeling rate 0.1 denotes that 10% data points are labeled with truth in the dataset. It is not surprising that the higher the labeling rate is, the better the repair performance of IMR and ARX will be, which utilize the labeled truth, as illustrated in Figure 8(a). An interesting result is that with the increase of labeling rate, the corresponding time costs in Figure 8(b), first increase and then drop. The reason is that for a small labeling rate (say 0.06) with points barely modified, the iterative repair can quickly converge, while leaving most dirty data unchanged. The corresponding RMS error is high in this case as shown in Figure 8(a). With more data labeled in the input, more dirty points will be identified and repaired by the algorithm, leading to higher computation costs. When the labeling rate is large, such as 0.25, a great number of dirty points may be labeled. Thereby, the iterative repair could converge quickly again. As anomaly detection methods, the results of Tsay and ARIMA are generally similar to those of AR and ARX. SCREEN and EWMA methods are not affected by order p, threshold τ and labeling rate. It is not surprising that SCREEN performs weakly, which verifies our motivation and analysis in the Introduction. Similarly, since EWMA does not utilize the labeled truth, its performance is weak.

Experiments on Synthetic Errors
The experiments on synthetic errors over ILD data focus on varying the errors. Again, similar results are also observed in the other dataset GPS and thus omitted.

Evaluation on Various Errors
We consider Shift and Innovational errors [2,27], as the example illustrated in Figure 9, where Spike errors are considered as a special case with # consecutive errors = 1. The corresponding accuracy results are reported in Figure 10.  Figure 12: Varying threshold τ , over ILD with p = 3, data size 3k, and labeling rate 0.2 In general, similar results are observed over Innovational and Shift errors. That is, while our proposed IMR may not deal with Spike errors (i.e., with # consecutive errors = 1 in Figure 10) as good as SCREEN [26], IMR always shows significantly better results (lower RMS measure) in addressing a large number of consecutive errors, on both Shift and Innovational error patterns. The results demonstrate again that our proposal works well in repairing consecutive errors. As illustrated in Figure 9(a), not only the proposed IMR but also ARX with a small threshold τ suffers from an overcorrection when the time series shifts back to non-anomalous data. The number attached to each method, e.g., IMR-0.05, denotes τ = 0.05 for IMR. As shown, there is a trade-off in both IMR and ARX: a smaller threshold τ shows better results in dealing with consecutive errors, but leads to overcorrection when the shift ends. Nevertheless, as presented in Figures 6 and 12, a smaller threshold τ generally has better overall accuracy. It is also worth noting that existing methods, EWMA smoothing and SCREEN, cannot handle well the repairing either when the time series shifts back to non-anomalous data, as the example illustrated in Figure 1.

Evaluation on Online Computing
As long as online labeling is available (discussed in Section 1.3), the proposed IMR is applicable. Remarkably, by interpreting all the historical data as one labeled segment, the direct calculation of repairs without iterating in Section 4.2.2 can be applied for efficient online computing. Figure 13 presents the results of online repairing. Since errors are randomly introduced in the dataset, to obtain reliable results, we repeat 10 times for each test with random error introducing and report the average. Troughput of IMR is stable and comparable to others. IMR again shows the best repair. Improvement of IMR compared to ARX is not as significant as in other experiments. It is not surprising, referring to the similar Equation 3 for ARX and Equation 10 for IMR(1). The advantage of IMR is that no threshold parameter is required for IMR(1) with one labeled segment in Section 4.2.2, while ARX needs to set threshold τ .

Experiments on Temperature
To evaluate over cyclic time series, we employ another data set on temperature in years (http://data.cma.cn, with cyclic patterns as illustrated in Figure 14). Similar to ILD, we inject synthetic errors to the temperature data. Figure  15 presents the results over different error types. Again, the results are generally similar to those on ILD in Figure  10. That is, the proposed IMR shows significantly better results when dealing with a large number of consecutive errors. SCREEN shows no better results in this dataset under Spike errors (i.e., # consecutive errors = 1), since the clean data also contain a large number of Spikes as illustrated in Figure 14 and cannot be distinguished from errors.

RELATED WORK
The idea of performing repair in multiple iterations has also been studied [28], where the past repairs could help in recommend more accurate repairs in the future. The continuous data cleaning approach [28] however is not directly applicable in our problem, since it employs FD constraints which is not available over time series data.

Anomaly Detection over Temporal Data
AR and ARX indeed have been widely used for anomaly detection in various areas such as economics and social surveys [3,6]. We consider ARX [19] in this study, since this approach can utilize the labeled truth and could be adapted to cooperate with the minimum change principle in data repairing (as shown in Section 3).
Hellerstein [13] surveys methods on cleaning errors in quantitative attributes of large databases, where time series data are also discussed as a special scenario. For instance, Tsay [27] presents unified methods for detecting and handling outliers and structure changes in a univariate timeseries. Iterative procedures consist of specification-estimation-detectingremoving cycles to handle one-by-one the most significant disturbance. ARIMA [18,3] is a general parametric family of time series, consisting of autoregressive process and moving-average process. It can also incorporate a wide range of nonstationary series.

Smoothing-based Cleaning
Smoothing techniques are often employed to eliminate noisy data. For example, the simple moving average (SMA) [4] smooths time series data by computing the unweighted mean of the last k points. Instead of weighting equally, the exponentially weighted moving average (EWMA) [10] assigns exponentially decreasing weights over time. As indicated in [26], also illustrated in Figure 2 in Example 2 and observed in Figure 4 (EWMA) in the experiments, the smoothing methods may seriously alter the original correct data, and thus have low repair accuracy. In contrast, our minimum change-based approach, applying only high confidence repairs, could preserve most the original values with a better repair accuracy.

Constraint-based Cleaning
Constraint-based repairing is widely considered in cleaning dirty data, such that the repaired data satisfies some given constraints and the repair modification is minimized [1,8]. The constraints are often defined over multiple attributes [22,24,23], which are not available in a univariate time series considered in this study. To clean sequential data, existing study [26] employs a class of speed constraints declaring that the speeds of value changes should be bounded. The repairing is thus to modify the sequence towards the satisfaction of such speed constraints. This constraint-based repairing falls short in two aspects: (1) it cannot handle a sequence of continuous errors, and (2) the labeled truth is not utilized. Rather than hard constraints, the cleaning is further extended to maximizing the likelihood w.r.t. speeds [33]. Finally, the constraints are also utilized to clean the timestamps [21] and the qualitative event data [29], which are different and not applicable to the quantitive time series data studied in this paper.

CONCLUSION
In this paper, we study the problem of repairing dirty time series data, given the labeled truth of some data points.
(1) While existing anomaly detection techniques could be adapted to repairing, we argue that significant deviation (between observation and predication) based anomaly detection is inconsistent with the minimum change principle in data repairing. Our experiments over real datasets illustrate such inconformity of applying anomaly detection in anomaly repairing. (2) We thereby propose an iterative minimum repairing (IMR) algorithm. By creatively performing one minimum repair in each iteration of error predication, the algorithm bonds the beauty of capturing temporal nature in anomaly detection with the minimum change in data repairing. Again, the experiments demonstrate the superiority of our proposal. Remarkably, in contrast to anomaly detection approaches AR and ARX, our proposed IMR is not sensitive to the setting of order p, i.e., a small p is sufficient to achieve high repair accuracy with low time costs.
(3) The convergence of IMR is explicitly analyzed. In particular, we show that the converged repair result could be directly calculated without iterative computing in certain cases, which enables efficient online repairing over streaming data. It is worth noting that unlike the existing ARX, no threshold needs to be specified for IMR in online computing. (4) Finally, we design efficient pruning and incremental computation, which reduce the complexity of parameter estimation from linear time to constant time. Experiments illustrate the significant improvement on time performance by pruning and incremental computation.