{'fraction_non_alphanumeric': 0.03132852178561882, 'fraction_numerical': 0.009783480352846832, 'mean_word_length': 4.460011675423234, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Improvement of PAA on Trend-Based Approximation for Time Series

Piecewise Aggregate Approximation (PAA) is a competitive basic dimension reduction method for high-dimensional time series mining. When deployed, however, the limitations are obvious that some important information will be missed, especially the trend. In this paper, we propose two new approaches for time series that utilize approximate trend feature information. Our first method is based on relative mean value of each segment to record the trend, which divide each segment into two parts and use the numerical average respectively to represent the trend. We proved that this method satisfies lower bound which guarantee no false dismissals. Our second method uses a binary string to record the trend which is also relative to mean in each segment. Our methods are applied on similarity measurement in classification and anomaly detection, the experimental results show the improvement of accuracy and effectiveness by extracting the trend feature suitably.


Introduction
Time series is a series of data points indexed in time order, which is widely existed in fields of medical [6,10,26], business [18], industry [20,25], cyber security [17,24] and so on. Time series mining is one of the attractive research topics and a key issue for the last decade, such as classification [22], clustering [15], anomaly detection [19,27], time series visualization [9,13]. Most of mining technologies require comparison of similarity measurement, which can effect the accuracy and efficiency of mining. A series of measurements have been proposed, such as Manhattan Distance [23], Euclidean Distance [7], Chebyshev Distance [2]. The typical measure is Euclidean Distance(ED), which is the sum of straight line distance between two points through time series.
Time series is a high-dimensional data that leads to expensive time and space cost when processed with the raw data directly by using ED, so dimensionality reduction is required to improve the efficiency. There has been much work in dimensional reduction, and one of the popular approaches is using spatial method to index the data in the transformed space including Discrete Fourier Transform (DFT) [7,14], Singular Value Decomposition (SVD) [7,12], Discrete Wavelet Transform (DWT) [3,11]. And there are piecewise aggregate representation including Piecewise Aggregate Approximation (PAA) [8,12], Symbolic Aggregate approximation (SAX) [14,21]. PAA is competitive with or faster than other methods and it is easy to implement, which allows more flexible distance measure. However, PAA algorithm is easy to lose an amount of information, especially the trend. For instance, if two series have same mean but opposite trend, PAA will judge these two sequences similar. Guo C [8] proposed an approach with PAA based on variance feature, which including forms of linear and square root, to add some important information and solve the problem of same mean value. While Sun Y [21] tried to add trend information by using starting and ending points of segments, whereas the starting and ending points do not reflect the trend in many case like the situation that both points have same value while the trend in segment are different.
In this paper, we propose two new approaches for time series similarity measurement that utilize trend feature. Our first method divides each segment into two parts based on mean value and use the numerical average respectively to represent the trend. And we prove our method satisfies lower bound which guarantee no false dismissals. Our second method uses a binary string to record the trend change of a time series. The trend distance between two sequence is added to the PAA distance as the final distance to measure the similarity in both measures.
The remainder of the paper is organized as follows: Section 2 provides the background knowledge of original PAA and its limitations in detail. Section 3 presents our proposed method and explain the trend representation. Section 4 presents the experimental results of classification and anomaly detection on several data sets. Finally, section 5 concludes the paper.

Background
Piecewise Aggregate Approximation (PAA) is an approach of average dimensional reduction, which divides the time sequence equally and take the mean value of each segment as representation. Given time series, Q = {q 1 , ..., q n } , it will be reduced to a vector of length w and presents asQ = {q 1 ,q 2 ...,q w } , where w ≤ n, the ith element ofq is calculated by: where the time series is divide into w equi-size segments,q i is the mean value of the ith segment, q j is one of the time point in its segment(in which i ∈ w and j ∈ [q i , q i+1 ] ).
The mean value of data falling within the segment will be calculated and the mean value will replace whole segment as the new representation. Once the length of segment becomes larger, it will lead to the loss of trend information as shown in Fig.1. To illustrate this point, Fig.1(a) divide the time series into two subsequences, the length is 96/2 = 48, which lose the trend information a lot and is obviously quite different from the original one. With the increase of the number of segments in Fig.1(b) to Fig.1(d), the reduced dimension sequence is closer to the original one. Besides, the result of reduction will be inaccurate  when two sequence have same mean value while the trends are different. For PAA method, the distance measure was proposed as Equation (2).
Compared with the original Euclidean distance in Equation (3) which is one of the true distance measures [16]. It can be seen from the above two formulas that Euclidean distance calculates every time points' distance while the PAA reduces the n dimension to w dimension and simply multiple n/w to enlarge time series, which roughly cover up information in detail. To illustrate this, Fig.2 shows that ts1 and ts2 are the relative segment in two time series. Even if it can be seen intuitively from the figure that they are two different time series, but their mean values are very close and the distance measure calculated by PAA will obtain that the two time series are similar. Furthermore, PAA is an approximate method to fit the original sequence, so the maximum and minimum value will be missed. To address above problems, we propose two methods to record the trend information, and the detail methods will be describe in section 3.

Our Proposed Methods
As we review above, we know that the original PAA method simply flattens the curve by segments, which will lose a lot of information, especially the trend change information. For the propose of solving this problem, we propose two methods. The first method is based on relative mean value of each segment to record the trend, and we call it Numerical Trend Based On PAA(NT PAA). It divides each segment into two parts by mean value and calculate the numerical average of them separately, with the trend distance calculated by difference. The other is a method of recording the relative trend change for a sequence by using a binary string, we name it Binary Trend Based On PAA(BT PAA). And the trend distance is the number of different binary strings in two time series, which is weighted by the number of segments. Both the final distance combine the trend approximate distance with the PAA distance.

Numerical Trend Based On PAA
The trend representation For the propose of solving this problem, we add the incremental representation by using the numerical mean value on behalf of trend to improve it. A time series of length n represents as Q = {q 1 , ..., q n } which is divided into w segments, Q = {q 1 , ...,q w }, the formula is shown in Equation.1 We define up difference as the difference of all time points in one segment above the mean value, while below difference as the difference of all the time points in one segment below the mean value. Therefore the up-mean value ∆q u and below-mean value ∆q b which are relative to the mean value in each segment can be defined as: where u i is the number of up value in ith segment, and b i is the number of below value , w n = u i + b i , and we can see from the Fig.3 clearly that the time points in red area is the below difference value and time points in blue area is the up difference value.
Distance Measure In order to guarantee no false dismissals, we must produce a distance measure defined in index space. We can define the trend distance based on numerical mean value in one segment as follows.
And the final distance between two time series based on trend approximation can be defined as: Our proposed method is a lower bounding measure to Euclidean Distance(ED) which can be proved as follow.
Proof. According to the [12], the authors have already proved that the PAA distance is lower bound the Euclidean distance: In order to prove the N T Dist(Q, C) lower bounds Euclidean Distance, we should expand the Euclidean first, where q i can be represented as q i =q i − ∆q i , so as c i =c i − ∆c i , and simply make the w = 1.
We already know that (q i −c i ) n i=1 (∆q i − ∆c i ) = 0, therefore, ED can be transformed as follows: And for our method, we can expand our method from Equation (9) that Combine Equation (12) and (13), we only have to prove that Equation (12) can be divided into two parts including up and below area as we mention above due to n where ∆q u and ∆q b are the mean value in different two parts, which can be defined as Equation (4) and (5). In other words, it can be represented as ∆q i = ∆q ui − ∆(∆q i ) and ∆c i = ∆c ui − ∆(∆c i ). To prove Equation (13) and (14), the process are the same as Equation (8). The prove is done.

Binary Trend Based On PAA
The trend representation Another method to represent the trend is based on binary string, which can roughly but efficiently reflect the relative trend change to mean value in each segment. We can use binary string B = {0, 1} n to represent the trend relative to the mean and the bits are defined as follow: in Equation (15), each raw data point segment is represented as 1 when the raw data is greater than the mean value of ith segment, otherwise, if the raw data is less than the mean, it is represented as 0 .
For example, suppose we have one of the corresponding segment in two time series P i and Q i , as we can see in   Distance Measure The trend distance of the binary string between two series is as follows, where the length of time series is n and it is divided into w segment.
b pi , b qi are the binary string of corresponding segment of two series, and the function count is used to sum up the number of 1 in the binary string. The formula can be transformed where B P and B Q are the whole binary strings of two time series. Finally, we can define the BIT Dist measure function based on trend distance and PAA as follows, From Equation (17), it can be seen that the effect of trend distance on the overall distance is weighted by w/n, which n is fixed. The larger of w, the greater the proportion of trend distance and the longer length of one segment. Once the subsequence is very long, the trend among this segment will change into a parallel line with no trend change, therefore, the increase of trend distance helps distinguish between the similarity of two subsequence. On the contrary, the smaller of w, the smaller proportion of trend distance. Because if the length of subsequence is small, even contains only two time points, their trend is similar to linear, which will not lose trend information a lot.

Experiments
In this section, we evaluate our proposed methods and present the results of experiments. First, we introduce the data sets we used in experiments. Then we compare the performance of proposed methods in aspect of classification and anomaly detection. The experiments are performed on 2.5GHz processor with 16GB physical memory. We use cross-validation to find the optimal reduction ratio s = n/w on the training data sets and verify them on the verification data sets.

Dataset
We perform all the experiments over the UCR Time Series Classification Archive repository [4], which is a large and mature open data sets, and each of the datasets is divided into a training data set and a test data set. We choose 24 data sets in UCR and the classes of time series are between 2 and 39, the length of time series are between 84 and 1024 with the total size of the data sets are between 60 and 2000. The detail of data sets is shown in Table 1

Experimental setup
Method: Since our method is to improve the PAA based on trend feature, we compare the accuracy and effectiveness on classification and anomaly detection with Piecewise Aggregate Approximation(PAA), Euclidean Distance(ED) and Cosin Similarity(CO) distance measures. Cosin similarity [5] uses the cosin of the angle between two vectors in vector space as the measure of the difference within two individuals. As for distance representation, it shall be 1 minus the cosin similarity distance in our experiment. For the classification process, we conduct the experiments using the k-Nearest Neighbor (K-NN) classifier and set the k=3, of which the accuracy is determined by the similarity distance between test sample and each of training data. And for the anomaly detection process, we use Local Outlier Factor (LOF) [1] to look for the optimal parameters of nearest neighbor in test sets by cross-validation.
Evaluation metrics: In these experiments, error rate, precision, recall and F1score are used as evaluation metrics to evaluate the performance of classification.  Precision is how much of the retrieved entries is accurate, while recall is how many accurate entries have been retrieved. As for F1-score, it is the harmonic average of precision and Recall. When F1 is higher, the comparison shows that the experimental method is ideal.
Error rate = N umber of incorrect classif ication T otal number of test samples (18) We use Area Under Curve (AUC) evaluation metric to measure the performance of anomaly detection. AUC is defined as the area under the ROC curve and the range of values is between 0.5 and 1. The greater the AUC value, the better the detection algorithm effect.

Comparison in lower bound
As for the NT PAA method, we already prove that our method has tighter lower bound than original PAA, which can be further proved by experiment as shown in Fig.5. We choose the Euclidean distance as the true distance and make the tightness represent as Equation (20), where Dist(P, Q) is the approximate distance measure, s represent the reduction ratio, and T is range in [0, 1], the closer to 1 the better, 200 time series of length 150 are tested. From this Fig.5 we can find that when the reduction ration is 1, the tightness is equal, and as the reduction ratio becomes bigger, the tightness becomes smaller.

Comparison on Classification
In this experiment, our proposed methods BT PAA and NT PAA are compared with three other distance measurements, Cosin [5], Euclidean [?] and PAA, with 24 data sets in UCR are used. The results of classification are shown in Table 2, and the best results are highlighted in bold font.
To measure the improvement that the BT PAA and NT PAA classifier provide, the data sets are trained and tested with a varying window size s comparing with original PAA, Cosin and ED. The results in Table 2 show that all methods have different best number of s ratio. Furthermore, our proposed methods performs better than other three methods in most of the data sets in Table 2, BT PAA has most of lowest error rate in data sets(11/24) while NT PAA is less (8/24). On the other hand, our methods perform almost the same in F1 metric. On average(10/24), our proposed methods outperforms than PAA, Cosin and Euclidean under these evaluation metrics.
In additional, we summarize the result between two methods we mentioned above as shown in Fig.6. If the point(red dot) is in the lower region, the proposed methods are more accurate than PAA or ED, otherwise, the point(blue triangle) are in up region which means they are worsen than original methods. To illustrate the performance, the red dots are the majority apparently in four subfigures, so they works well in classification via different data sets. Fig. 6. Comparison of error rate between our proposed methods(NT PAA and BT PAA) and other methods(PAA and ED) with 24 data sets. The red dots in below region represent that our method is superior to the existing one, the blue triangles in up region represent that existing methods are better than ours, and the green squares represent the equal error rate.

Comparison on Anomaly Detection
In this experiment, we use 12 data sets selected in Table 1, which only have two classes, to conduct the anomaly detection experiment with algorithm of Local Outlier Factor (LOF) [1] to look for relatively anomaly points. We use Area Under Curve (AUC) evaluation metric to measure the performance. The results are shown in Table 3 that our proposed measure BT PAA with LOF is much greater than other four distance methods, which five out of twelve data sets have a significant increase in AUC, and the other seven have a slight increase. As for NT PAA, we have eight out of twelve data sets greater than other four method.
In general, the methods we propose have a much better effect than PAA. To evaluate the computation performance of our two methods, we compare the computation time with our methods and PAA in anomaly detection. Five data sets are chosen to show the results. From the Fig.7, the computation time of NT PAA is approximately twice as PAA, while the BT PAA is a bit lager than PAA, since all three methods have same time-consuming in piecewise and the only difference is the time to convert time series into binary string and up/below-mean. Therefore, BT PAA is better than NT PAA in running time.

Conclusion
In this paper, we propose two new methods for time series similarity measurement that apply trend information. Our first method use the numerical average in segment which is divided into two parts to represent the trend, and another method use a binary string to record the trend change of a time series. And both the trend distance between two sequence are based on the PAA distance as the final distance to measure the similarity. We have evaluate the proposed methods using the UCR Time Series Archive repository for classification and anomaly detection, and from the view of the accuracy shows that the proposed methods are better than others in both two aspects, despite it costs more time than PAA. In our future work, we are planing to reduce the trend space and improve the run time of trend distance by using hashing.