{'fraction_non_alphanumeric': 0.025563989036474805, 'fraction_numerical': 0.006852203246890154, 'mean_word_length': 4.872175796966883, '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': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Particle Swarm Optimization of Information-Content Weighting of Symbolic Aggregate Approximation

Bio-inspired optimization algorithms have been gaining more popularity recently. One of the most important of these algorithms is particle swarm optimization (PSO). PSO is based on the collective intelligence of a swam of particles. Each particle explores a part of the search space looking for the optimal position and adjusts its position according to two factors; the first is its own experience and the second is the collective experience of the whole swarm. PSO has been successfully used to solve many optimization problems. In this work we use PSO to improve the performance of a well-known representation method of time series data which is the symbolic aggregate approximation (SAX). As with other time series representation methods, SAX results in loss of information when applied to represent time series. In this paper we use PSO to propose a new minimum distance WMD for SAX to remedy this problem. Unlike the original minimum distance, the new distance sets different weights to different segments of the time series according to their information content. This weighted minimum distance enhances the performance of SAX as we show through experiments using different time series datasets.


Introduction
A time series is a sequence of real numbers over a period of time. Each of these numbers represents the value of the observed phenomenon at a certain time point. Time series data have been used in many applications such as science, medicine, and engineering. Time series data mining handles several tasks such as similarity search, classification, clustering, and others. _ Time series datasets are usually very large so direct search or sequential scanning of these datasets is inefficient. In order to overcome this problem transformations can be applied to reduce the dimensionality of the original time series and to represent them in a space with manageable dimensionality. Such transformations are called dimensionality reduction techniques, or representation methods. The most widely known methods are Discrete Fourier Transform (DFT) [2] and [3], Discrete Wavelet Transform (DWT) [5], Singular Value Decomposition (SVD) [13], Adaptive Piecewise Constant Approximation (APCA) [10], Piecewise Aggregate Approximation (PAA) [9] and [30], Piecewise Linear Approximation (PLA) [17], and Chebyshev Polynomials (CP) [4].
Other methods of time series data mining use multi-resolution approaches. In [16] and [27] a method of multi resolution representation of time series is presented. This symbolic method uses a multi-resolution vector quantized approximation of the time series together with a multi-resolution similarity distance. Using this representation the method keeps both local and global information of the time series data. In [19] and [20] other multi-resolution method are proposed. These methods are based on a fastand-dirty filtering scheme that iteratively reduces the search space using several resolution levels. The technique presented in [22] couples and fast-and-dirty filter with a multi-resolution representation of the time series.
Indexing time series data usually includes establishing a lower bounding distance on time series in the transformed space to guarantee that the representation method will not cause false dismissals. This is achieved by defining a distance, on the transformed space, that underestimates the distance in the original space. This condition is known as the lower-bounding lemma. [2].
Among representation methods of time series data, symbolic representation of time series has several advantages which interested researchers in this field of computer science. One of its main advantages is that symbolic representation permits researchers to benefit from the ample symbolic algorithms known in the text-retrieval and bioinformatics communities [14].
There have been many suggestions to represent time series symbolically. But in general, most of these symbolic representation methods suffered from two main inconveniences [15]; the first is that the dimensionality of the symbolic representation method is the same as that of the original space, so there is no virtual dimensionality reduction. The second drawback is that although distance measures have been defined on the reduced symbolic spaces, these distance measures are poorly correlated with the original distance measures defined on the original spaces.
One of the most widely-known symbolic representation methods of time series is SAX. SAX uses pre-computed distances obtained from lookup tables. This makes SAX fast to compute.
In this work we show how the performance of SAX can be improved by substituting the original similarity measure used with SAX by a new one which assigns different weights to different segments of the time series according to their information content. These weights are set using the particle swarm optimization; a widely used population-based optimization method which has been successful in solving many optimization problems. We show through experiments conducted on different time series dataset how the new similarity measure can give better results than the original one.
The work presented in this paper is organized as follows: in Section 2 we present related background. In Section 3 we introduce the new scheme and we evaluate its performance in Section 4. In Section 5 we give concluding remarks.

The Symbolic Aggregate Approximation (SAX)
The Symbolic Aggregate approXimation method (SAX) [14] is one of the most important symbolic representation methods of time series. The main advantage of SAX is that the similarity measure it uses, called MINDIST, uses statistical lookup tables, which makes it is easy to compute with an overall complexity of ( ) . SAX is based on an assumption that normalized time series have Gaussian distribution, so by determining the breakpoints that correspond to a particular alphabet size, one can obtain equal-sized areas under the Gaussian curve. SAX is applied as follows: 1-The time series are normalized. 2-The dimensionality of the time series is reduced using PAA [9], [30] 3-The PAA representation of the time series is discretized by determining the number and location of the breakpoints (The number of the breakpoints is chosen by the user). Their locations are determined, as mentioned above, using Gaussian lookup tables. The interval between two successive breakpoints is assigned to a symbol of the alphabet, and each segment of PAA that lies within that interval is discretized by that symbol.  The last step of SAX is using the following similarity measure: Where n is the length of the original time series, N is the length of the strings (the number of the segments), Sˆand R are the symbolic representations of the two time series S and R , respectively, and where the function ) ( dist is implemented by using the appropriate lookup table. For instance, the lookup table of MINDIST for an alphabet size of 3 is the one shown in Table 1.
We also need to mention that the similarity measure used in PAA is: Where n is the length of the time series, N is the number of segments.
It is proven in [9], [30] that the above similarity distance is a lower bound of the Euclidean distance applied in the original space of time series. This means that MINDIST is also a lower bound of the Euclidean distance, because it is a lower bound of the similarity measure used in PAA. This guarantees no false dismissals.
There are other versions and extensions of SAX [11], [25], [26], [28]. These versions use it for other applications or apply it to index massive datasets, or compute MINDIST differently [18]. However, the version of SAX that we presented earlier, which is called classic SAX, is the basis of all these versions and extensions and it is actually the most widely-known one.

Information Content
Quantifying the content of information a vector carries was first introduced by Shannon in [24]. This is measured by what is known as entropy and is defined for a discrete probabilistic system by: where the base of the logarithm is 2. This concept has many applications in cryptography, data transmission, natural language processing, data compression, and others.
In time series mining, the concept of information content was implicitly or explicitly present in different representation methods of time series data. DFT [2], [3] and DWT [5], for instance are based on the fact that the first coefficients are the most meaningful ones; i.e. they contain most of the information in the time series, so the other coefficients can be truncated without much loss of information. APCA [10] segments the time series into segments of varying lengths such that their individual reconstruction errors are minimal. The intuition behind this idea is that different regions of the time series contain different amounts of information. So while regions of high activity contain high fluctuations, other regions of low activity show a flat behavior, so a representation method with high fidelity should reflect this difference in behavior.

Particle Swarm Optimization of Information-Content Weighting of Symbolic Aggregate Approximation (PSOWSAX)
In time series mining the distance that is widely used to compute the similarity between the two time series is the Euclidean distance which is defined as follows: One of the variations of the Euclidean distance, which is much related to the topic of this paper, is the Weighted Euclidean Distance. This distance is defined as: where W is the weight vector. Fig. 1 shows the Euclidean distance and the weighted Euclidean distance between two time series. The intuition behind the weighted Euclidean distance is, again, that some parts of the time series may have more importance than other parts so the distance should reflect these regions differently compared with regions that contain less information.
Although weighing different regions differently seems to be a good solution to distinguish parts with high information content from others with less information, the question remains on how to set the weights. In [29] the authors proposed setting the weights using relevance feedback provided by the user. We can easily see that this solution is highly subjective and also inefficient.
It is important to mention that the weighted distance defined in (5) is applied to the raw time series and not to the reduced, lower-dimensional time series used in representation methods.
In this paper we present a modification of SAX based on the concept of information content.
In Section 2.1, we presented MINDIST ; the similarity measure used with SAX.
From relation (1) we can derive the following similarity measure which we call the Weighted Minimum Distance (WMD): in (6) we obtain MINDIST defined in relation (1), so MINDIST is in fact a special case of WMD . Notice also, which is very important, that from (1) and (6) we can easily see that: Since MINDIST is a lower bound of the Euclidean distance in the original space this implies that WMD is also a lower bound of the Euclidean distance, so our proposed distance guarantees no false dismissals. . The weights in (6) will be set for the whole time series in the dataset using the particle swarm optimization. Particle Swarm Optimization: Particle Swarm Optimization (PSO) is a member of a family of naturally-inspired optimization algorithms called Swarm Intelligence which are population-based optimization algorithms. PSO was inspired by the social behavior of some animals, such as bird flocking or fish schooling [8]. [23] proposed a model that simulates a swarm. In this model individuals, also called agents or particles, follow these rules (Fig. 2): Separation: Each particle avoids getting too close to its neighbors. Alignment: Each particle steers towards the general heading of its neighbors. Cohesion: Each particle moves towards the average position of its neighbors.

Fig. 2. Simulating swarm's behavior
The above model was elaborated by adding another rule which is obstacle avoidance which uses steer-to-avoid concept.
As is the case with many other optimization algorithms, there are quite a large number of variations of PSO. In the following we present a standard PSO [7]. PSO starts by initializing a swarm of sSize particles at random positions 0 i X r and velocities In the next step each position is evaluated, and for each iteration, using a fitness function, also called objective function or cost function.
is the best position found by particle i , k G r is the global best position found by the whole swarm, ω is called the inertia , L a is called the local acceleration , and G a is called the global acceleration. These last three parameters are control parameters which are chosen by the algorithm designer.
Move the particle to the new position: 8: The algorithm continues until a stopping criterion terminates it. Fig. 3 presents a pseudo code of PSO.

11: end for 12: end for
As in the case with other evolutionary algorithms, PSO should keep a balance between exploitation, and exploration. Exploration is defined as the act of searching for the purpose of discovery, and exploitation is defined as the act of utilizing something for any purpose [1].
Diversity in PSO comes from two sources [31]; the first is the difference between the particle's current position and that of its best neighbor, and the other is the difference between the particle's current position and its best historical position. Variation, although provides exploration, can only be sustained for a limited number of generations because convergence of the swarm to the best position is necessary to refine the solution (exploitation).

Experimental Validation
We tested our distance on a time series classification task on the datasets available at [12], which is the same repository on which the original SAX was tested. This repository makes up between 90% and 100% of all publicly available, labeled time series data sets in the world, and it represents the interest of the data mining/database community, and not just one group [6].
We tested our method in a classification task based on the first nearest-neighbor (1-NN) rule using leaving-one-out cross validation. This means that every time series is compared to the other time series in the dataset. If the 1-NN does not belong to the same class, the error counter is incremented by 1.
The purpose of the experiments is to compare PSOWSAX (our new method which uses WMD as a similarity measure) with the original method (which uses MINDIST as a similarity measure) on the classification task and see which one gives the smallest error. This means that for each value of the alphabet size tested we perform the three steps of SAX presented in Section 2.1 to obtain the symbolic representation of the time series, and then we apply MINDIST when we test the original method or we apply WMD when we want to test ours, which, as indicated earlier, is based on PSO. The weights i w in relation (6) are obtained during a training phase. This means for each value of the alphabet size tested, we formulate a PSObased optimization problem where the fitness function is the classification error of the time series (we opt to minimize the classification error) and the outcome of this optimization problem is the weights i w that yield this minimum value of the classification error, then we use these values on the corresponding testing datasets to obtain the final classification error. As for MINDIST , there is no training phase and it is applied directly to the testing datasets.
For PSOWSAX, the swarm size we used in the experiments is 16. Each particle is a vector of nPar components representing potential weights of the segments of the time series.
We used a standard PSO, the local acceleration L a was set to 2, the global acceleration G a was set to 2. The dimension of the problem nPar is the dimension of the weight vector, which is the number of segments of the times series in the reduced space; i.e. The number of iterations nItr was set to 20. This is a rather small number of iterations and the algorithm could have been left to evolve more. However, the objective of our experiments was to validate our method rather than to show its best performance which could be achieved using more sophisticated PSO algorithms.
We also have to mention that we know from experience that for some datasets the classification error is always high, or always low, for all methods of time series representation, so a threshold of a classification error, related to the dataset tested, could be set as a stopping criterion. Table 2 summarizes the symbols used in the experiments together with their corresponding values.  In Fig. 4. we present some of the results we obtained for alphabet size equal to 3, 10, and 20, respectively. We chose to report these values because the first version of SAX used alphabet size that varied between 3 and 10. Then in a later version the alphabet size varied between 3 and 20. So these values are benchmark values. Finally, we present in Table 3, for reproducibility purposes, the weights of datasets (CBF) and (ECG) (Because of space restrictions, we present these datasets only). As indicated earlier, these weights are obtained by applying PSOWSAX to the training datasets. The final classification errors of WMD (those shown in Fig. 4) are obtained by using those weights, with WMD , on the corresponding testing datasets.

Conclusion
In this paper we showed through a new scheme PSOWSAX, based on particle swam optimization, how the performance of SAX; one of the most important symbolic representation methods of time series data, can be improved by using a new similarity measure WMD which assigns different weights to different segments of the time series according to their information content. The information loss caused by time series representation methods can be better recovered by setting different weights to different regions of the time series according to their information content. The optimization process takes place at indexing time so the new scheme has the same low complexity as that of the original SAX.
We validated the new scheme by conducting classification task experiments on different datasets. The experiments showed that our new scheme gives better results than the original one.
A possible future work will be to associate the work presented in this paper with the work presented in [20]. This can be achieved in two ways; the first is to use the optimization scheme presented in [20] to locate the breakpoints then to use the optimization scheme presented in this work to set different weights to different segments according to their information content. The second way is to use a one-step optimization problem to locate the breakpoints together with the corresponding weights of segments.